数据结构课程设计本课程设计已调试通过，请放心使用。请到：道客巴巴或豆丁网充值购买word版，省打字，直接修改即可，价格较便宜，在这里百度较贵！搜索：数据结构_邻接表以及邻接矩阵的运用_课程设计_实验报告
设计题目：邻接表以及邻接矩阵的运用
目录
课题名称邻接表以及邻接矩阵的运用院系年级专业学号姓名成绩
课题设计目的与设计意义1、课题设计目的：（1）、学会用邻接矩阵和邻接表实现图结构和对图的基本操作；（2）、掌握对图操作的具体实现；（3）、掌握图的两种遍历算法（深度优先、广度优先）；（4）、掌握求图的最小生成树和顶点间最短路径的算法；（5）、实现使用邻接表存储结构存储一个图。2、课题设计意义：图的邻接表存储结构是一种顺序存储与链式存储相结合的存储方法。从空间性能上说，图越稀疏邻接表的空间效率相应的越高。从时间性能上来说，邻接表在图的算法中时间代价较邻接矩阵要低。本课程设计主要是实现使用邻接表存储结构存储一个图，并在所存储的图中实现深度优先和广度优先遍历以及其链表结构的输出。当然，这学到的也只是书本上的知识，课程设计小组化的分配，更能很好的锻炼我们的团队意识，让我们在一个团队中更好的融入，更好的工作，更好的适应社会对人才的需要。亲力亲为的上机操作也更能锻炼我们的实际操作能力，将课本上的知识运用在实际中。指导教师：
年月日
第一章课程设计的目的和意义..................................................................................1第二章课程设计分析..................................................................................................12.1原理.................................................................................................................12.1程序所实现的功能：.....................................................................................12.2程序的输入，包含输入的数据格式和说明.................................................12.3程序的输出，程序输出的形式......................................................................22.4程序的主要函数.............................................................................................22.5函数说明.........................................................................................................2第三章算法描述..........................................................................................................23.1深度优先遍历算法，利用递归......................................................................23.2广度优先遍历算法，利用队列先入先出......................................................23.3函数调用图.....................................................................................................3
第四章运行结果分析..................................................................................................44.1运行步骤：..................................................................................................4第五章结束语..............................................................................................................7第六章参考文献..........................................................................................................7附录：源代码................................................................................................................8
1
第一章课程设计的目的和意义众所周知，图是一种复杂的非线性结构。在人工智能、工程、数学、物理、化学、计算机科学等领域中，图结构有着广泛的应用。由图的重要性，针对此次课程设计，我们要深入实现对图的操作。学会用邻接矩阵和邻接表实现图结构和对图的基本操作。掌握图的两种遍历算法，即深度优先和广度优先以及掌握求图的最小生成树和顶点间最短路径的算法。本学期我们学习了很多图的存储结构，有邻接矩阵、邻接表等。其中邻接矩阵和邻接表为图的主要存储结构。图的邻接矩阵存储结构的主要特点是把图的边信息存储在一个矩阵中，是一种静态存储方法。图的邻接表存储结构是一种顺序存储与链式存储相结合的存储方法。从空间性能上说，图越稀疏邻接表的空间效率相应的越高。从时间性能上来说，邻接表在图的算法中时间代价较邻接矩阵要低。本课程设计主要是实现使用邻接表存储结构存储一个图，并在所存储的图中实现深度优先和广度优先遍历以及其链表结构的输出。当然，这学到的也只是书本上的知识，课
程设计小组化的分配，更能很好的锻炼我们的团队意识，让我们在一个团队中更好的融入，更好的工作，更好的适应社会对人才的需要。亲力亲为的上机操作也更能锻炼我们的实际操作能力，将课本上的知识运用在实际中。第二章课程设计分析2.1原理当图比较稀疏时，邻接表存储是最佳的选择。并且在存储图的时候邻接表要比邻接矩阵节省时间。在图存储在系统中后，我们有时还需要对图进行一些操作，如需要添加一个顶点，修改一个顶点，或者删除一个顶点，而这些操作都需要一图的深度优先及广度优先遍历为基础。本系统将构建一个图，图的结点存储的是int型数据。运行本系统可对该图进行链式结构输出、深度优先及广度优先遍历。2.1程序所实现的功能：
（1）建立并显示图的邻接表。（2）深度优先遍历，显示遍历结果。（3）对该图进行拓扑排序，显示排序结果。（4）给出某一确定顶点到所有其它顶点的最短路径。2.2程序的输入，包含输入的数据格式和说明(1)输入顶点数,及各顶点信息(数据格式为整形)(2)输入边数,及权值(数据格式为整形)2.3程序的输出，程序输出的形式(1)输出图的邻接表、深度优先遍历结果、拓扑排序结果。(2)输入某一确定顶点到其它所有顶点的最短路径。
2
2.4程序的主要函数Graph、link()、DFTraverse()、TopologicalOrder()、TopologicalOrder()、GetVertexPos()、ShortestPath2.5函数说明
第三章算法描述3.1深度优先遍历算法，利用递归voiddpv(grapha[],vtxptrv0){//从点v开始进行深度访问//a为连通图或非连通图的一个连通分量visit（v0）；//访问v结点mark[v0]=1;//标记为已访问w=v0的第一个邻接点；while(当邻接点w存在时1){if(w未访问)dpv(a,w);w=下一个邻接点；}
}//dpv3.2广度优先遍历算法，利用队列先入先出voidwdv(grapha[],vtxptrv){//从v点开始广度优先，a是连通图或是连通分量visit（v）；//访问点vmark[v]=1;//并标记为以访问initqueue（Q)；enqueue(Q,v);//v进队列while(!queueempty(Q)){delqueue(Q,v1);w=v1的第一个邻接点；
函数名称函数功能creatMGraph创建一张无向网的邻接矩阵printMGraph输出一张无向网的邻接矩阵DFS遍历一张无向网MiniSpanTree_PRIM生成最优数
3
while(当邻接点w存在时){if(w为访问){visit（w）；mark[w]=1;enqueue(Q,w);}w=下一个邻接点；}}}//wdv3.3函数调用图Main（）
Creatgraph()Print()Dpv()Wdv()
Enqueue()Delqueue()Queueempyt()Qutput
4
第四章运行结果分析4.1运行步骤：（1）.编译无误运行界面如下所示：
（2）.输入顶点数和边数
5
（3）邻接矩阵的输出
（4）.邻接矩阵的深度遍历
6
(5)邻接表的广度遍历
（6）继续循环
7
第五章结束语数据结构这门课的思想性很强，它包纳了线性表、树、图等等逻辑结构。但学习这门课，光靠上课听讲还远远不能满足学习的需要，必须亲自编写源程序，不断地调试、运行、反复地思考，才能加深对本学科的认识，强化对所学知识的应用。我认为数据结构的相关知识和C语言的学习完全可以融为一体。一方面学习算法思想，另一方面用语言去实践，相得益彰，趣味盎然。在实际的上机操作过程中，不仅是让我们了解数据结构的理论知识，更重要的是培养解决实际问题的能力。所以相信通过此次实习可以提高我们分析设计能力和编程能力，为后续课程的学习及实践打下良好的基础。在这次短短的课程实践里，我们得到了老师的关心和帮助。她给了我们很多的信息，与我们一起探讨问题，询问我们遇到了哪些问题并耐心给予指导。当我们遇到技术上难以解决的问题时。她就会指导我们解决问题，她把自己多年来积累的经验教授给我们，使我们顺利地完成了课程实践任务。感谢老师！
第六章参考文献[1]唐策善，黄刘生.数据结构—用C语言描述.高等教育出版社，1994[2]孙家启，万家华，刘运，张怡文，汪红霞.——C语言程序设计教程.高等教育出版社[3]张国锋.C++语言及其程序设计教程.电子工业出版社，1992[4]严蔚敏，陈博文.数据结构.机械工业出版社，1990
8
附录：源代码#include#includetypedefintdatatype;typedefcharvextype;#definemaxsize64typedefstructpnode{datatypedata;structpnodenext;}linklist;typedefstruct
{linklistfront,rear;}linkqueue;linkqueueq;typedefstruct{charvexs[maxsize];intarcs[maxsize][maxsize];intvexnum,arcnum;}graph;graphga;typedefstructnode
{intadjvex;structnodenext;}edgenode;typedefstruct{vextypetopvex;edgenodelink;}topnode;topnodegl[20];voidsetnull(linkqueueq)
9
{q->front=(linklist)malloc(sizeof(linklist));q->front->next=NULL;q->rear=q->front;}intempty(linkqueueq){if(q->front==q->rear)return1;elsereturn0;
}voidenqueue(linkqueueq,datatypex){q->rear->next=(linklist)malloc(sizeof(linklist));q->rear=q->rear->next;q->rear->data=x;q->rear->next=NULL;}intdequeue(linkqueueq){linkqueues;
if(empty(q)){printf("队为空!");returnNULL;}else{s=q->front;q->front=q->front->next;free(s);return(q->front->data);}
10
}voidcreat_juzhe(graphga)//无向图邻接矩阵的建立{inti,j,k;getchar();printf("请输入%d个元素:",ga->vexnum);for(i=0;ivexnum;i++)scanf("%c",&ga->vexs[i]);for(i=0;ivexnum;i++)for(j=0;jvexnum;j++)ga->arcs[i][j]=0;printf("请输入邻接的俩个顶点的下标:\n");
for(k=0;karcnum;k++){scanf("%d%d",&i,&j);ga->arcs[i][j]=1;ga->arcs[j][i]=1;}}voidprint_juzhe(graphga)//无向图邻接矩阵的输出{inti,j;printf("建立好后的无向图的邻接矩阵为:\n");for(i=0;ivexnum;i++)
{printf("%c\t",ga->vexs[i]);for(j=0;jvexnum;j++)printf("%d\t",ga->arcs[i][j]);printf("\n\n\n");}}voidcreat_ljbiao(topnodegl[],intn,inte)//无向图邻接表的建立{inti,j,k;edgenodep;getchar();
11
printf("请输入%d个顶点的元素:",n);for(i=0;iadjvex=j;
p->next=gl[i].link;gl[i].link=p;p=(edgenode)malloc(sizeof(edgenode));p->adjvex=i;p->next=gl[j].link;gl[j].link=p;}}voidprint_ljbiao(topnodegl[],intn)//无向图邻接表的输出{inti;edgenodep;
printf("建立后的无向图的邻接表为:\n");for(i=0;iadjvex);p=p->next;}printf("\n");}
12
}intvisited_lj[20]={0};voidDFSL(topnodegl[],inti)//无向图邻接表的深度遍历{edgenodep;printf("%c",gl[i].topvex);visited_lj[i]=1;p=gl[i].link;while(p!=NULL){if(visited_lj[p->adjvex]==0)DFSL(gl,p->adjvex);
p=p->next;}}intvisited[20]={0};voidDFS(graphga,inti)//无向图邻接矩阵的深度遍历{intj,n;printf("%c",ga->vexs[i]);visited[i]=1;for(j=0;jvexnum;j++)if((ga->arcs[i][j]==1)&&(visited[j]==0))
DFS(ga,j);}intvisited_ljb[20]={0};voidBFSL(topnodegl[],intk)//无向图邻接表的广度遍历{inti;edgenodep;linkqueueQ;setnull(&Q);printf("%c",gl[k].topvex);visited_ljb[k]=1;enqueue(&Q,k);
13
while(!empty(&Q)){i=dequeue(&Q);p=gl[i].link;while(p!=NULL){if(!visited_ljb[p->adjvex]){printf("%c",gl[p->adjvex].topvex);visited_ljb[p->adjvex]=1;enqueue(&Q,p->adjvex);}
p=p->next;}}}intvisited_jz[20]={0};voidBFS(graphga,intk)//无向图邻接矩阵的广度遍历{inti,j;linkqueueQ;setnull(&Q);printf("%c",ga->vexs[k]);visited_jz[k]=1;
enqueue(&Q,k);while(!empty(&Q)){i=dequeue(&Q);for(j=0;jvexnum;j++)if((ga->arcs[i][j]==1)&&(!visited_jz[j])){printf("%c",ga->vexs[j]);visited_jz[j]=1;enqueue(&Q,j);}
14
}}voidmain(){inti=1,j,n,e;graphga;topnodegl;while(i){printf("\n0:无向图邻接矩阵的建立\n1:无向图邻接表的建立\n2:邻接矩阵的输出\n3:邻接表的输出\n4:邻接矩阵的深度遍历
\n5:邻接表的深度遍历\n6:邻接矩阵的广度遍历\n7:邻接表的广度遍历\n");scanf("%d",&i);switch(i){case0:printf("请输入顶点数和边数:");scanf("%d%d",&ga.vexnum,&ga.arcnum);creat_juzhe(&ga);break;case1:printf("请输入顶点数和边数:");scanf("%d%d",&n,&e);creat_ljbiao(&gl,n,e);
break;case2:print_juzhe(&ga);break;case3:print_ljbiao(&gl,n);break;case4:printf("请输入要遍历的起始位置:");scanf("%d",&j);printf("邻接矩阵深度遍历后的结果为:");DFS(&ga,j);break;case5:printf("请输入要遍历的起始位置:");scanf("%d",&j);
15
printf("邻接表深度遍历后的结果为:");DFSL(&gl,j);break;case6:printf("请输入要遍历的起始位置:");scanf("%d",&j);printf("邻接矩阵广度遍历后的结果为:");BFS(&ga,j,n);break;case7:printf("请输入要遍历的起始位置:");scanf("%d",&j);printf("邻接表广度遍历后的结果为:");BFSL(&gl,j);
break;}printf("\n0:结束\n1:继续\n");scanf("%d",&i);}}
|
|
