一、目的和要求（需求分析）：
1、掌握邻接表的存储结构及邻接表的创建和操作。
2、制作无向图的邻接表，用键盘输入图的顶点数和图的边数，要求显示制作的邻接表)
基本要求：1.做无向图邻表
2 .屏幕输出
实验展开：1.构造有向图的邻接表
2 .判断边缘是否存在
3 .求出顶点的度数
二、程序设计的基本思想，原理和算法描述：
根据实验要求，根据以下图例：
首先定义邻接表的结构，然后根据输入的图的顶点数和图的边数分别构造有向图和有向图的邻接表。 邻接表的结构具体如下。
typedef struct ArcNode{ int adjvex； //邻接点编号VertexType data； //相邻点信息struct ArcNode* next； //指向下一边的指针}ArcNode； typedefstructvnode { vertextypevertex； //顶点信息ArcNode* first； //指向下一个边缘节点}VNode，AdjList[vnum]； //顶点节点向量typedef struct{ AdjList adjlist； //旁边的表int vexnum，arcnum； //顶点和边数}ALGraph； 具体的输入输出代码如下。
int choice1、choice2； 请选择cout '功能。' endl； cout '1.有向图邻接表的结构和打印' endl； cout '2.有向图邻接表的结构' endl； 结束计数3 .结束； cin choice1； wile(choice1) if (choice1==1) ) { ALGraph G； 创建分配(g )； printalgraph(g； 布雷克； (if ) choice1==2) { ALGraph G； 创建链接(g )； 请选择“计数”功能。 ' endl； cout '1.确定是否存在边缘' endl； cout '2.求出顶点的度数' endl； 结束计数3 .结束； cin choice2； 打印有向图表的邻接表相关代码如下。
cout '生成邻接表为以下：' endl； cout----------------endl； for(intI=0； i G.vexnum； I ) { cout G.adjlist[i].vertex； //输出顶点信息的ArcNode* p=G.adjlist[i].first； while(p！=NULL ) {//遍历输出cout '--' p-adjvex； p=p-next； } cout endl； (cout----------------endl； } 三、调试和运行程序过程中产生的问题及采取的措施：
调试过程中发生如下图所示的错误。
已发现这可能是由已分配但未初始化的内存空间导致的。 修改后就会正常。
在寻找ps:有向图的某一边是否存在时出现了问题…但是不知道哪里错了(叹息)
四、源程序及注释：
# include iostream # define vnum 30 usingnamespacestd； typedef char VertexType； typedef struct ArcNode{ int adjvex； //邻接点编号VertexType data； //相邻点信息struct ArcNode* next； //指向下一边的手指
针}ArcNode;typedef struct VNode{ VertexType vertex; //顶点信息 ArcNode* first; //指向下一个边结点}VNode,AdjList[vnum];//顶点结点向量typedef struct{ AdjList adjlist; //邻接表 int vexnum, arcnum; //顶点和边的个数}ALGraph;int LocateVex(ALGraph& G, char v){//查找顶点信息 int k, j = 0; for (k = 0; k < G.vexnum; k++) if (G.adjlist[k].vertex == v){ j = k; break; } return j;}void CreateALGraph(ALGraph& G){//建立无向图的邻接表表示 int i, j, k; char v1, v2; ArcNode* s; cout<<"请输入顶点数和边数（vexnum,arcnum）:"<< endl; cin >> G.vexnum >> G.arcnum; for (i = 0; i < G.vexnum; i++){//建立顶点表 cout<<"请输入第"<<i+1<<"顶点信息："<<endl; cin >> G.adjlist[i].vertex;//读入顶点信息 G.adjlist[i].first = NULL;//边表置为空表 } for (k = 0; k < G.arcnum; k++){//建立边表 cout << "请输入第" << k + 1 << "条边的两个顶点信息:" << endl; cin >> v1 >> v2; i = LocateVex(G, v1); j = LocateVex(G, v2); s = (ArcNode*)malloc(sizeof(ArcNode)); //生成边表结点 s->adjvex = j;//邻接点序号为j s->next = G.adjlist[i].first;//将结点j链接到i的单链表中 G.adjlist[i].first = s; //将新结点*s插入顶点vi的边表头部 s = (ArcNode*)malloc(sizeof(ArcNode));//生成i的表结点 s->adjvex = i; s->next = G.adjlist[j].first;//将结点i链接到j的单链表中 G.adjlist[j].first = s; }}void PrintALGraph(ALGraph& G){ //打印图 cout << "生成邻接表如下:" << endl; cout << "-----------------------------------" << endl; for (int i = 0; i < G.vexnum; i++){ cout << G.adjlist[i].vertex;//输出顶点信息 ArcNode* p = G.adjlist[i].first; while (p != NULL){//遍历输出 cout << "-->" << p->adjvex; p = p->next; } cout << endl; } cout << "-----------------------------------" << endl;}void CreateLink(ALGraph& G) {//建立有向图的邻接表表示 int i, j, k; char v1, v2; ArcNode* s; cout << "请输入顶点数和边数（vexnum,arcnum）:" << endl; cin >> G.vexnum >> G.arcnum; for (i = 0; i < G.vexnum; i++) {//建立顶点表 cout << "请输入第" << i + 1 << "顶点信息：" << endl; cin >> G.adjlist[i].vertex;//读入顶点信息 G.adjlist[i].first = NULL;//边表置为空表 } for (k = 0; k < G.arcnum; k++) {//建立边表 cout << "请输入第" << k + 1 << "条边的两个顶点信息:" << endl; cin >> v1 >> v2; i = LocateVex(G, v1); j = LocateVex(G, v2); s = (ArcNode*)malloc(sizeof(ArcNode)); //生成边表结点 s->adjvex = j;//邻接点序号为j s->next = G.adjlist[i].first;//将结点j链接到i的单链表中 G.adjlist[i].first = s; //将新结点*s插入顶点vi的边表头部 }}void Judge(ALGraph& G) { //判断有向图中是否存在边 int i, j, m, n; ArcNode* p; p = (ArcNode*)malloc(sizeof(ArcNode)); cout << "请输入需要判断的边："; cin >> i >> j; m = LocateVex(G, i); n = LocateVex(G, j); p = G.adjlist[m].first; while (p) { if (p->adjvex == n) { cout << "该边存在" << endl; break; } else { p = p->next; } } if (p == NULL) { cout << "该边不存在" << endl; }}void CountDegree(ALGraph& G) {//计算有向图中顶点的出度入度 int i; ArcNode* p; int out = 0, in = 0;//out储存出度，in储存入度 cout << "请输入顶点编号（从0开始）："; cin >> i; if (G.adjlist[i].first == NULL) { out = 0; } else { p = (ArcNode*)malloc(sizeof(ArcNode)); p = G.adjlist[i].first; while (p != NULL) { out++; p = p->next; } } for (int k = 0; k < G.vexnum; k++){ p = (ArcNode*)malloc(sizeof(ArcNode)); p = G.adjlist[k].first; while (p != NULL){ if (p->adjvex == i) { in++; break; } p = p->next; } } cout << "该顶点的出度为:" << out << endl; cout << "该顶点的入度为:" << in << endl;}int main() { int choice1,choice2; cout << "请选择功能：" << endl; cout << "1.无向图的邻接表的构造及打印" << endl; cout << "2.有向图的邻接表的构造 " << endl; cout << "3.退出" << endl; cin >> choice1; while (choice1) { if (choice1 == 1) { ALGraph G; CreateALGraph(G); PrintALGraph(G); break; } if (choice1 == 2) { ALGraph G; CreateLink(G); cout << "请选择功能：" << endl; cout << "1.判断边是否存在" << endl; cout << "2.求顶点的度数 " << endl; cout << "3.退出" << endl; cin >> choice2; while (choice2) { if (choice2 == 1) { Judge(G); break; } if (choice2 == 2) { CountDegree(G); break; } if (choice2 == 3) { break; } } break; } if (choice1 == 3) { break; } } return 0;}五、运行输出结果：
这里判断就很离谱。。。（也许以后就能发现错在哪里了）
六、心得与体会：
首先掌握了邻接表的存储结构以及邻接表的建立和操作。在此基础上学会了如何构造无向图及有向图的邻接表。虽然上课讲的方法都能听懂，但做了实验才知道自己到底理解了多少。写程序之前可以通过画图自己把逻辑搞清楚，再动手写代码效果会好很多。
附：
一、无向图邻接表例子：
二、结构体定义：
#define MAXVEX 30
typedef char VertexType;
typedef struct ArcNode {
int adjvex; /邻接点序号/
VertexType data; /邻接点信息/
struct ArcNode *next;
} ArcNode;
typedef struct VNode {
VertexType data; /结点信息/
ArcNode *firsrarc; /指向下一个边结点/
}VNode,AdjList[MAXVEX];