数据结构课程设计本课程设计已调试通过，请放心使用。请到：道客巴巴或豆丁网充值购买word版，省打字，直接修改即可，价格较便宜，在这里百度较贵！搜索：数据结构_图的邻接矩阵建立及其遍历_课程设计_实验报告
设计题目：图的邻接矩阵的建立及其遍历
课题名称图的邻接矩阵建立及其遍历院系年级专业学号姓名成绩
课题设计目的与设计意义1、课题设计目的：（1）巩固和加深课堂教学内容，提高学生的实际动手操作能力。（2）建立图的存储结构建立图的存储结构，图的类型包括：无向图和有向图﹑无向网和有向网，能够输入图的顶点和边的信息放入相应的存储结构，而后输出邻接矩阵，最后再以一个顶点为出发点对得到的图的邻接矩阵进行深度优先遍历和广度优先遍历。2、课题设计意义：图是一种较复杂的数据结构，图的搜索在图书索引，城市道路建设，人工智能等领域中发挥着重要作用。图的搜索有深度优先搜索和广度优先搜索，我们可以通过图的邻接矩阵实现图的这种搜索。我们学习两年的有关C语言和数据结构的相关知识，而课程设计是将我们把所学的理论和生产实践相结合的重要环节，通过这次课程设计，可以使我们所学的专业技能得到巩固、扩大、深入和系统化；培养综合运用所学知识解决图的搜索的能力，初步掌握数据结构程序设计的方法和步骤。指导教师：
年月日
目录第一章需求分析...............................................................................................................11.1课题设计的目的及意义..........................................................................................1第二章概要设计...............................................................................................................22.1程序设计的基本分析图如下..........................................................................22.2图的邻接矩阵及遍历实现的概述........................................................................22.2.1基本函数的应用............................................................................................2第三章详细设计...............................................................................................................43.1数据类型的定义....................................................................................................43.1.1无向图和有向图的定义.............................................................................4
3.1.2链队列的定义.............................................................................................43.2主函数程序............................................................................................................43.2.1主函数的主菜单的功能...............................................................................43.2.5有向网的操作.............................................................................................8第四章测试分析.................................................................................................................84.1主功能菜单..........................................................................................................84.2各子函数功能操作..............................................................................................9第五章心得体会...............................................................................................................13第六章源程序代码...........................................................................................................14第七章参考文献.............................................................................................................24
1
第一章需求分析1.1课题设计的目的及意义1﹑课题设计目的：巩固和加深课堂教学内容，提高学生的实际动手操作能力，使学生熟练掌握数据结构中所学的理论知识，通过综合应用数据结构的基本知识来解决实际问题，加强学生分析和解决问题的能力。建立图的存储结构，图的类型包括：无向图和有向图﹑无向网和有向网，能够输入图的顶点和边的信息放入相应的存储结构，而后输出邻接矩阵，最后再以一个顶点为出发点对得到的图的邻接矩阵进行深度优先遍历和广度优先遍历2﹑课题设计意义：
图是一种较复杂的数据结构，图的搜索在图书索引，城市道路建设，人工智能等领域中发挥着重要作用。图的搜索有深度优先搜索和广度优先搜索，我们可以通过图的邻接矩阵或邻接表实现图的这两种搜索。本次程序设计我们通过C语言编写程序实现图的搜索。在编写过程中我们将图定义为邻接矩阵类型，通过深度优先搜索遍历和广度优先搜索遍历分别实现图的搜索。我们学习两年的有关C语言和数据结构的相关知识，而课程设计是将我们把所学的理论和生产实践相结合的重要环节，通过这次课程设计，可以使我们所学的专业技能得到巩固、扩大、深入和系统化；培养综合运用所学知识解决图的搜索的能力，初步掌握数据结构程序设计的方法和步骤；使我们进一步提高编写程序的效率；提高我们独立钻研问题的能力，培养严肃认真，实事求是，刻苦钻研的工作作风。1.2课程的要求分析1﹑以邻接矩阵为存储结构，存储各个顶点信息﹑边的信息以及顶点与边的关系；
2﹑实现无向图和有向图﹑无向网和有向网的邻接矩阵的建立及其深度优先遍历和广度优先遍历；3﹑要求利用队列实现无向图和有向图﹑无向网和有向网的邻接矩阵的深度优先遍历和广度优先遍历；4﹑以用户指定的结点为起点,分别输出两种遍历下的结点访问序列5﹑运用C语言在MicrosoftVisualC++6.0中编写源代码，得到正确的程序；
2
第二章概要设计2.1程序设计的基本分析图如下
2.2图的邻接矩阵及遍历实现的概述2.2.1基本函数的应用：
图的操作无向图的操
作有向图的操作无向网的操作有向网的操作邻接矩阵的建立图的深度优先遍历和广度优先遍历
3
1﹑结构体的定义：运用结构体的typedefstruct类型定义无向图和有向图﹑无向网和有向网的顶点vertex和边adjvex的信息，结构体定义队列和指针link和next域，用于广度优先遍历。2、基本函数：
3、子程序功能菜单：（1）voidcreatyouxianggraph(graphga,intn,inte)/有向图邻接矩阵的建立/（2）voidcreatwuxianggraph(graphga,intn,inte)/无向图邻接矩阵的建立/（3）voidcreatyouxiangwang(graphga,intn,inte)/有向网邻接矩阵的建立/（4）voidcreatwuxiangwang(graphga,intn,inte)/无向网邻接矩阵的建立/（5）setnull(linkqueueq)/置空队/（6）intempty(linkqueueq)/判断队空/（7）enqueue(linkqueueq,intx)/入队/
（8）DFS(graphga,inti,intn)/深度遍历/（9）BFS(graphga,intk,intn)/广度遍历/
图函数名的类型图的邻接矩阵建立深度遍历广度遍历结果输出无向图Creatwuxianggraph()DFS()BFS()print()有向图Creatyouxianggraph()DFS()BFS()print()无向网Creatwuxiangwa
ng()DFS()BFS()print()有向网Creatyouxiangwang()DFS()BFS()print()
4
（10）voidprint(graphga,intn,inte)/邻接矩阵的输出/第三章详细设计3.1数据类型的定义：3.1.1无向图和有向图的定义#definemaxsize64/邻接矩阵数组存储的最大空间/typedefstruct{charvexs[maxsize];/定义存储顶点信息的一维数组/
intarcs[maxsize][maxsize];/定义存储边与顶点关系的二维数组/}graph;3.1.2链队列的定义typedefstructpnode{datatypedata;/定义链表的数据域、structpnodenext;/定义链表的指针域/}linklist;typedefstruct{linklistfront,rear;/用linklist类型定义队头和队尾/
}linkqueue;linkqueueq;/q是链队列指针/3.2主函数程序3.2.1主函数的主菜单的功能，调用子函数的程序：voidmain(){inti=1;while(i){
printf("\n");
5
printf("\t\t\t~~~~~~~~功能菜单~~~~~~~\n");printf("\n");printf("\t\t\t\n");printf("\t\t\t0.无向图的操作\n");printf("\t\t\t\n");printf("\t\t\t1.有向图的操作\n");printf("\t\t\t\n");printf("\t\t\t2.无向网的操作\n");printf("\t\t\t\n");printf("\t\t\t3.有向网的操作\n");printf("\t\t\t\n");printf("\t\t\t\n");
printf("\n\t\t\t请输入选择的功能编号（0-3）:\n");scanf("%d",&i);}3.2.2无向图操作while(k){printf("\n0:无向图邻接矩阵的建立\n1:无向图的深度遍历\n2:无向图的广度遍历:\n3无向图邻接矩阵的输出:\n");scanf("%d",&k);switch(k){case0:
printf("请输入无向图的顶点数和边数:");scanf("%d%d",&n,&e);creatwuxianggraph(&ga,n,e);break;case1:printf("请输入遍历顶点下标和顶点数:");scanf("%d%d",&i,&n);printf("深度遍历后的结果为:");DFS(&ga,i,n);break;case2:printf("请输入遍历顶点下标和顶点数:");
6
scanf("%d%d",&k,&n);BFS(&ga,k,n);break;case3:printf("输出的图为:\n");print(&ga,n,e);break;}printf("\n0:结束\n1:继续\n");scanf("%d",&k);
}3.2.3有向图的操作while(j){printf("0:有向图邻接矩阵的建立\n1:有向图的深度遍历\n2:有向图的广度遍历:\n3有向图邻接矩阵的输出:");scanf("%d",&j);switch(j){case0:printf("请输入有向图的顶点数和边数:");scanf("%d%d",&n,&e);
creatyouxianggraph(&ga,n,e);break;case1:printf("请输入遍历顶点下标和顶点数:");scanf("%d%d",&i,&n);DFS(&ga,i,n);break;case2:printf("请输入遍历顶点下标和顶点数:");scanf("%d%d",&k,&n);BFS(&ga,k,n);break;
case3:printf("输出的图为:\n");
7
print(&ga,n,e);break;}printf("\n0:结束\n1:继续\n");scanf("%d",&j);3.2.4无向网的操作while(m){printf("0:无向网邻接矩阵的建立\n1:无向网的深度遍历\n2:无向网的广度遍历:\n3无向网邻接矩阵的输出:");scanf("%d",&m);switch(m)
{case0:printf("请输入无向网的顶点数和边数:");scanf("%d%d",&n,&e);creatwuxiangwang(&ga,n,e);break;case1:printf("请输入遍历顶点下标和顶点数:");scanf("%d%d",&i,&n);DFS(&ga,i,n);break;case2:
printf("请输入遍历顶点下标和顶点数:");scanf("%d%d",&k,&n);BFS(&ga,k,n);break;case3:printf("输出的网为:\n");print(&ga,n,e);break;}printf("\n0:结束\n1:继续\n");scanf("%d",&m);
8
3.2.5有向网的操作while(t){printf("0:无向网邻接矩阵的建立\n1:无向网的深度遍历\n2:无向网的广度遍历:\n3无向网邻接矩阵的输出:");scanf("%d",&t);switch(t){case0:printf("请输入无向网的顶点数和边数:");scanf("%d%d",&n,&e);
creatyouxiangwang(&ga,n,e);break;case1:printf("请输入遍历顶点下标和顶点数:");scanf("%d%d",&i,&n);DFS(&ga,i,n);break;case2:printf("请输入遍历顶点下标和顶点数:");scanf("%d%d",&k,&n);BFS(&ga,k,n);break;
case3:printf("输出的网为:\n");print(&ga,n,e);break;}printf("\n0:结束\n1:继续\n");scanf("%d",&t);第四章测试分析4.1主功能菜单
功能主页面图的操作如下图1
9
图1图的操作4.2各子函数功能操作4.2.1无向图的操作1、无向图的建立与输出无向图的建立与输出首先用户输入‘0’选择无向图的建立，然后根据提示语输入顶点和边的信息建立邻接矩阵，测试结果如图2。
图2无向图的建立建立好无向图后，用户再输入‘3’选择邻接矩阵的输出，得到结果如图3
10
图3无向图邻接矩阵输出2、无向图的深度优先遍历和广度优先遍历图4无向图的深度优先遍历
图5无向图的广度优先遍历4.2.2有向图的操作1、有向图的建立与输出有向图的建立与输出首先用户输入‘0’选择有向图的建立，然后根据提示语输入顶点和边的信息建立邻接矩阵，测试结果如图6
11
图6有向图的邻接矩阵建立建立好有向图后，用户再输入‘3’选择邻接矩阵的输出，得到结果如图7
图7有向图的邻接矩阵输出图8有向图深度遍历图9有向图广度遍历4.2.3无向网的操作1、无向网的建立与输出无向网的建立与输出首先用户输入‘0’选择无向网的建立，然后根据提示语输入顶
点和边的信息建立邻接矩阵，测试结果如图10
12
图10无向网邻接矩阵的建立建立好无向网后，用户再输入‘3’选择邻接矩阵的输出，得到结果如图11
图11无向网的邻接矩阵输出2、无向网的深度优先遍历和广度优先遍历图12深度优先遍历图13广度优先遍历4.2.4有向网的操作
1、有向网的建立与输出有向网的建立与输出首先用户输入‘0’选择有向网的建立，然后根据提示语输入顶点和边的信息建立邻接矩阵，测试结果如图14
13
图14有向网的邻接矩阵建立建立好无向网后，用户再输入‘3’选择邻接矩阵的输出，得到结果如图15
图15有向网邻接矩阵的输出2、有线网的深度优先遍历和广度优先遍历图16有向网的深度遍历图17有向网的广度遍历
第五章心得体会1、实际完成的情况说明主要程序参考教材《数据结构——用C语言描述》2、程序的性能分析
14
可连续建图3、上机过程中出现的问题及其解决方案。编译没有错误，但结果有问题。解决方案：虽然程序的编译通过，只能说明语法上没有问题，结果只所以不正确是因为算法上原因。4、程序中可以改进的地方说明程序中的深度优先遍历，浪费空间较大，可以考虑用循环来做。但这样将付出代码长度加长的代价。5、程序中可以扩充的功能及设计实现假想实现假想：随用户的输入可以随时动态的显示图的生成。6、收获及体会通过这次课程设计实践，加深了我对图的邻接矩阵的建立及其遍历的认识和了解，对图的一些概念更加清晰了，提高了我的实际动手操作能力，在上机操作的时候
不断编译改错，尽量的完善程序，也增强了我使用word书写报告和画图的能力，不断的修改，我更好的掌握了图的无向图和有向图、无向网和有向网的邻接矩阵建立及其深度优先遍历和广度优先遍历的操作。编写程序即是一件艰苦的工作，又是一件愉快的事情。最大的收获：编程时如果遇到看似简单但又无法解决的问题，很容易灰心丧气。此时切不可烦躁，一定要冷静的思考，认真的分析。查询一些资料为自己的报告做准备，询问老师不懂的问题，要勇敢的面对问题，勇敢的接受问题，勇敢的处理问题，最后最勇敢的解决问题，更好的总结自己的成果，态度认真。第六章源程序代码
图的基本操作源代码：#include#includetypedefcharvextype;typedefintdatatype;#definemaxsize64typedefstruct{charvexs[maxsize];intarcs[maxsize][maxsize];}graph;typedefstructnode
{
15
intadjvex;structnodenext;}edgenode;typedefstruct{vextypevertex;edgenodelink;}vexnode;typedefstructpnode{datatypedata;structpnodenext;
}linklist;typedefstruct{linklistfront,rear;}linkqueue;linkqueueq;voidcreatyouxianggraph(graphga,intn,inte)/有向图邻接矩阵的建立/{inti,j,k;getchar();printf("请输入顶点字符:");
for(i=0;ivexs[i]);for(i=0;iarcs[i][j]=0;for(k=0;karcs[i][j]=1;}
16
}voidcreatwuxianggraph(graphga,intn,inte)/无向图邻接矩阵的建立/{inti,j,k;getchar();printf("请输入顶点字符:");for(i=0;ivexs[i]);for(i=0;iarcs[i][j]=0;for(k=0;k
{printf("请输入第%d边的行标和列标:",k+1);scanf("%d%d",&i,&j);ga->arcs[i][j]=1;ga->arcs[j][i]=1;}}voidcreatyouxiangwang(graphga,intn,inte)/有向网邻接矩阵的建立/{inti,j,k,w;getchar();printf("请输入顶点字符:");
for(i=0;ivexs[i]);for(i=0;iarcs[i][j]=0;for(k=0;karcs[i][j]=w;}
17
}voidcreatwuxiangwang(graphga,intn,inte)/无向网邻接矩阵的建立/{inti,j,k,w;getchar();printf("请输入顶点字符:");for(i=0;ivexs[i]);for(i=0;iarcs[i][j]=0;for(k=0;k
{printf("请输入第%d个顶点的行标和列标及权值:",k+1);scanf("%d%d%d",&i,&j,&w);ga->arcs[i][j]=w;ga->arcs[j][i]=w;}}voidprint(graphga,intn,inte)/邻接矩阵的输出/{inti,j;for(i=0;i
{printf("%c\t",ga->vexs[i]);for(j=0;jarcs[i][j]);printf("\n");}}setnull(linkqueueq){q->front=(linklist)malloc(sizeof(linklist));q->front->next=NULL;q->rear=q->front;
18
}intempty(linkqueueq){if(q->front==q->rear)return1;elsereturn0;}enqueue(linkqueueq,intx){q->rear->next=(linklist)malloc(sizeof(linklist));q->rear=q->rear->next;
q->rear->data=x;q->rear->next=NULL;}datatypedequeue(linkqueueq){linkqueues;if(empty(q)){printf("队为空!");returnNULL;}else
{s=q->front;q->front=q->front->next;free(s);return(q->front->data);}}intvisited[maxsize]={0};DFS(graphga,inti,intn)/遍历起始点/{intj;printf("%c",ga->vexs[i]);
19
visited[i]=1;for(j=0;jarcs[i][j]!=0)&&(!visited[j]))DFS(ga,j,n);}intvisit[maxsize]={0};BFS(graphga,intk,intn){inti,j;linklistQ;setnull(&Q);printf("%c",ga->vexs[k]);
visit[k]=1;enqueue(&Q,k);while(!empty(&Q)){i=dequeue(&Q);for(j=0;jarcs[i][j]!=0)&&(!visit[j])){printf("%c",ga->vexs[j]);visit[j]=1;enqueue(&Q,j);}
}}voidmain(){inti=1,j=1,k=1,m=1,t=1;intn,e;graphga;while(i){printf("\n");printf("\t\t\t~~~~~~~~功能菜单~~~~~~~\n");printf("\n");
20
printf("\t\t\t\n");printf("\t\t\t0.无向图的操作\n");printf("\t\t\t\n");printf("\t\t\t1.有向图的操作\n");printf("\t\t\t\n");printf("\t\t\t2.无向网的操作\n");printf("\t\t\t\n");printf("\t\t\t3.有向网的操作\n");printf("\t\t\t\n");printf("\t\t\t\n");printf("\n\t\t\t请输入选择的功能编号（0-3）:\n");scanf("%d",&i);
switch(i){case0:while(k){printf("\n0:无向图邻接矩阵的建立\n1:无向图的深度遍历\n2:无向图的广度遍历:\n3无向图邻接矩阵的输出:\n");scanf("%d",&k);switch(k){case0:printf("请输入无向图的顶点数和边数:");scanf("%d%d",&n,&e);
creatwuxianggraph(&ga,n,e);break;case1:printf("请输入遍历顶点下标和顶点数:");scanf("%d%d",&i,&n);printf("深度遍历后的结果为:");DFS(&ga,i,n);break;case2:printf("请输入遍历顶点下标和顶点数:");scanf("%d%d",&k,&n);printf("广度遍历的结果为:");
21
BFS(&ga,k,n);break;case3:printf("输出的图为:\n");print(&ga,n,e);break;}printf("\n0:结束\n1:继续\n");scanf("%d",&k);}break;
case1:while(j){printf("0:有向图邻接矩阵的建立\n1:有向图的深度遍历\n2:有向图的广度遍历:\n3有向图邻接矩阵的输出:");scanf("%d",&j);switch(j){case0:printf("请输入有向图的顶点数和边数:");scanf("%d%d",&n,&e);creatyouxianggraph(&ga,n,e);break;
case1:printf("请输入遍历顶点下标和顶点数:");scanf("%d%d",&i,&n);printf("深度遍历后的结果为:");DFS(&ga,i,n);break;case2:printf("请输入遍历顶点下标和顶点数:");scanf("%d%d",&k,&n);printf("广度遍历后的结果为:");BFS(&ga,k,n);break;
22
case3:printf("输出的图为:\n");print(&ga,n,e);break}printf("\n0:结束\n1:继续\n");scanf("%d",&j);}break;case2:while(m){printf("0:无向网邻接矩阵的建立\n1:无向网的深度遍历\n2:无向网的广度遍历:\n3无向网邻接矩阵的输出:");
scanf("%d",&m);switch(m){case0:printf("请输入无向网的顶点数和边数:");scanf("%d%d",&n,&e);creatwuxiangwang(&ga,n,e);break;case1:printf("请输入遍历顶点下标和顶点数:");scanf("%d%d",&i,&n);printf("深度遍历后的结果为:");
DFS(&ga,i,n);break;case2:printf("请输入遍历顶点下标和顶点数:");scanf("%d%d",&k,&n);printf("广度遍历后的结果为:");BFS(&ga,k,n);break;case3:printf("输出的网为:\n");print(&ga,n,e);break;
23
}printf("\n0:结束\n1:继续\n");scanf("%d",&m);}break;case3:while(t){printf("0:有向网邻接矩阵的建立\n1:有向网的深度遍历\n2:有向网的广度遍历:\n3有向网邻接矩阵的输出:");scanf("%d",&t);switch(t)case0:printf("请输入无向网的顶点数和边数:");
scanf("%d%d",&n,&e);creatyouxiangwang(&ga,n,e);break;case1:printf("请输入遍历顶点下标和顶点数:");scanf("%d%d",&i,&n);printf("深度遍历后的结果为:");DFS(&ga,i,n);break;case2:printf("请输入遍历顶点下标和顶点数:");scanf("%d%d",&k,&n);
printf("广度遍历后的结果为:");BFS(&ga,k,n);break;case3:printf("输出的网为:\n");print(&ga,n,e);break;}printf("\n0:结束\n1:继续\n");scanf("%d",&t);}break;}
24
printf("0:结束图的操作\n1:继续图的操作\n");scanf("%d",&i);}}第七章参考文献[1]唐策善等，数据结构．中国科学技术大学出版社．1992[2]许卓群等，数据结构高等教育出版社．1987[3]严蔚敏，吴伟民，数据结构第二版清．华大学出版社1992[4]徐德民，最新C语言程序设计电．子工业出版社1992
|
|
