《数据结构_邻接表以及邻接矩阵的运用_课程设计_实验报告》由会员分享，可在线阅读，更多相关《数据结构_邻接表以及邻接矩阵的运用_课程设计_实验报告（18页珍藏版）》请在金锄头文库上搜索。
1、数 据 结 构 课 程 设 计 本课程设计已调试通过，请放心使用。请到：道客巴 巴 道客巴 巴或豆丁网豆丁网充值购买 word 版，省打字，直接修改即可，价 格较便宜，在这里百度较贵！ 搜索：数据结构_邻接表以及邻接矩阵的运用_课程设计_实 验报告 设计题目：邻接表以及邻接矩阵的运用 目录目录 课题名称邻接表以及邻接矩阵的运用 院系年级专业 学号姓名成 绩 课题设计 目的与 设计意义 1、课题设计目的： （1） 、学会用邻接矩阵和邻接表实现图结构和对图的基本操作； （2） 、掌握对图操作的具体实现； （3） 、掌握图的两种遍历算法（深度优先、广度优先） ； （4） 、掌握求图的最小生成树和顶点
2、间最短路径的算法； （5） 、实现使用邻接表存储结构存储一个图。 2、课题设计意义： 图的邻接表存储结构是一种顺序存储与链式存储相结合的存储 方法。从空间性能上说，图越稀疏邻接表的空间效率相应的越高。 从时间性能上来说，邻接表在图的算法中时间代价较邻接矩阵要低。 本课程设计主要是实现使用邻接表存储结构存储一个图，并在所存 储的图中实现深度优先和广度优先遍历以及其链表结构的输出。当 然，这学到的也只是书本上的知识，课程设计小组化的分配，更能 很好的锻炼我们的团队意识，让我们在一个团队中更好的融入，更 好的工作，更好的适应社会对人才的需要。亲力亲为的上机操作也 更能锻炼我们的实际操作能力，将课本上
3、的知识运用在实际中。 指导教师： 年月日 第一章 课程设计的目的和意义1 第二章 课程设计分析1 2.1 原理.1 2.1 程序所实现的功能：.1 2.2 程序的输入，包含输入的数据格式和说明.1 2.3 程序的输出，程序输出的形式2 2.4 程序的主要函数.2 2.5 函数说明.2 第三章 算法描述2 3.1 深度优先遍历算法，利用递归2 3.2 广度优先遍历算法，利用队列先入先出2 3.3 函数调用图.3 第四章 运行结果分析4 4.1 运行步骤：4 第五章 结束语7 第六章 参考文献7 附录：源代码8 1 第一章 课程设计的目的和意义第一章 课程设计的目的和意义 众所周知，图是一种复杂的
4、非线性结构。在人工智能、工程、数学、物理、化学、 计算机科学等领域中，图结构有着广泛的应用。由图的重要性，针对此次课程设计， 我们要深入实现对图的操作。学会用邻接矩阵和邻接表实现图结构和对图的基本操 作。掌握图的两种遍历算法，即深度优先和广度优先以及掌握求图的最小生成树和顶 点间最短路径的算法。 本学期我们学习了很多图的存储结构， 有邻接矩阵、 邻接表等。 其中邻接矩阵和邻接表为图的主要存储结构。图的邻接矩阵存储结构的主要特点是把 图的边信息存储在一个矩阵中，是一种静态存储方法。图的邻接表存储结构是一种顺 序存储与链式存储相结合的存储方法。从空间性能上说，图越稀疏邻接表的空间效率 相应的越高。
5、从时间性能上来说，邻接表在图的算法中时间代价较邻接矩阵要低。本 课程设计主要是实现使用邻接表存储结构存储一个图，并在所存储的图中实现深度优 先和广度优先遍历以及其链表结构的输出。当然，这学到的也只是书本上的知识，课 程设计小组化的分配，更能很好的锻炼我们的团队意识，让我们在一个团队中更好的 融入，更好的工作，更好的适应社会对人才的需要。亲力亲为的上机操作也更能锻炼 我们的实际操作能力，将课本上的知识运用在实际中。 第二章 课程设计分析第二章 课程设计分析 2.1 原理 当图比较稀疏时，邻接表存储是最佳的选择。并且在存储图的时候邻接表要比邻接 矩阵节省时间。在图存储在系统中后，我们有时还需要对图
6、进行一些操作，如需要添 加一个顶点，修改一个顶点，或者删除一个顶点，而这些操作都需要一图的深度优先 及广度优先遍历为基础。本系统将构建一个图，图的结点存储的是 int 型数据。运行 本系统可对该图进行链式结构输出、深度优先及广度优先遍历。 2.1 程序所实现的功能： （1）建立并显示图的邻接表。 （2）深度优先遍历，显示遍历结果。 （3）对该图进行拓扑排序，显示排序结果。 （4）给出某一确定顶点到所有其它顶点的最短路径。 2.2 程序的输入，包含输入的数据格式和说明 (1) 输入顶点数,及各顶点信息(数据格式为整形) (2) 输入边数,及权值(数据格式为整形) 2.3 程序的输出，程序输出的形
7、式 (1) 输出图的邻接表、深度优先遍历结果、拓扑排序结果。 (2) 输入某一确定顶点到其它所有顶点的最短路径。 2 2.4 程序的主要函数 Graph、link()、DFTraverse()、TopologicalOrder()、 TopologicalOrder()、 GetVertexPos()、ShortestPath 2.5 函数说明 第三章 算法描述第三章 算法描述 3.1 深度优先遍历算法，利用递归 void dpv(graph a,vtxptr v0) /从点 v 开始进行深度访问/a 为连通图或非连通图的一个连通分量 visit（v0） ；/访问 v 结点 markv0=1;
8、/标记为已访问 w=v0 的第一个邻接点； while(当邻接点 w 存在时 1) if(w 未访问) dpv(a,w); w=下一个邻接点； /dpv 3.2 广度优先遍历算法，利用队列先入先出 void wdv(graph a,vtxptr v) /从 v 点开始广度优先，a 是连通图或是连通分量 visit（v） ；/访问点 v markv=1;/并标记为以访问 initqueue（Q)； enqueue(Q,v);/v 进队列 while(!queueempty(Q) delqueue(Q,v1);w=v1 的第一个邻接点； 函数名称函数功能 creatMGraph创建一张无向网的邻接
9、矩阵 printMGraph输出一张无向网的邻接矩阵 DFS遍历一张无向网 MiniSpanTree_PRIM生成最优数 3 while(当邻接点 w 存在时) if(w 为访问) visit（w） ； markw=1; enqueue(Q,w); w=下一个邻接点； /wdv 3.3 函数调用图 Main（） Creatgraph() Print()Dpv()Wdv() Enqueue() Delqueue()Queueempyt() Qutput 4 第四章 运行结果分析第四章 运行结果分析 4.1 运行步骤： （1）.编译无误运行界面如下所示： （2）.输入顶点数和边数 5 （3）邻接矩
10、阵的输出 （4）.邻接矩阵的深度遍历 6 (5) 邻接表的广度遍历 （6）继续循环 7 第五章 结束语第五章 结束语 数据结构这门课的思想性很强，它包纳了线性表、树、图等等逻辑结构。但学 习这门课，光靠上课听讲还远远不能满足学习的需要，必须亲自编写源程序，不断地 调试、运行、反复地思考，才能加深对本学科的认识，强化对所学知识的应用。我认 为数据结构的相关知识和 C 语言的学习完全可以融为一体。一方面学习算法思想，另 一方面用语言去实践，相得益彰，趣味盎然。在实际的上机操作过程中，不仅是让我 们了解数据结构的理论知识，更重要的是培养解决实际问题的能力。所以相信通过此 次实习可以提高我们分析设计能
11、力和编程能力，为后续课程的学习及实践打下良好的 基础。在这次短短的课程实践里，我们得到了老师的关心和帮助。她给了我们很多的 信息，与我们一起探讨问题，询问我们遇到了哪些问题并耐心给予指导。当我们遇到 技术上难以解决的问题时。她就会指导我们解决问题，她把自己多年来积累的经验教 授给我们，使我们顺利地完成了课程实践任务。感谢老师！ 第六章 参考文献第六章 参考文献 1 唐策善，黄刘生.数据结构 用 C 语言描述.高等教育出版社，1994 2 孙家启，万家华，刘运，张怡文，汪红霞. C 语言程序设计教程.高等教育出 版社 3 张国锋.C+语言及其程序设计教程.电子工业出版社，1992 4 严蔚敏，陈
12、博文.数据结构.机械工业出版社，1990 8 附录：源代码附录：源代码 #include #include typedef int datatype; typedef char vextype; #define maxsize 64 typedef struct pnode datatype data; struct pnode *next; linklist; typedef struct linklist *front,*rear; linkqueue; linkqueue *q; typedef struct char vexsmaxsize; int arcsmaxsizemaxsiz
13、e; int vexnum,arcnum; graph; graph *ga; typedef struct node int adjvex; struct node *next; edgenode; typedef struct vextype topvex; edgenode *link; topnode; topnode gl20; void setnull(linkqueue *q) 9 q-front=(linklist *)malloc(sizeof(linklist); q-front-next=NULL; q-rear=q-front; int empty(linkqueue
14、*q) if(q-front=q-rear) return 1; else return 0; void enqueue(linkqueue *q,datatype x) q-rear-next=(linklist *)malloc(sizeof(linklist); q-rear=q-rear-next; q-rear-data=x; q-rear-next=NULL; int dequeue(linkqueue *q) linkqueue *s; if(empty(q) printf(“队为空!“); return NULL; else s=q-front; q-front=q-front
15、-next; free(s); return(q-front-data); 10 void creat_juzhe(graph *ga)/无向图邻接矩阵的建立 int i,j,k; getchar(); printf(“请输入%d 个元素:“,ga-vexnum); for(i=0;ivexnum;i+) scanf(“%c“, for(i=0;ivexnum;i+) for(j=0;jvexnum;j+) ga-arcsij=0; printf(“请输入邻接的俩个顶点的下标:n“); for(k=0;karcnum;k+) scanf(“%d%d“, ga-arcsij=1; ga-arcs
16、ji=1; void print_juzhe(graph *ga)/无向图邻接矩阵的输出 int i,j; printf(“建立好后的无向图的邻接矩阵为:n“); for(i=0;ivexnum;i+) printf(“%ct“,ga-vexsi); for(j=0;jvexnum;j+) printf(“%dt“,ga-arcsij); printf(“nnn“); void creat_ljbiao(topnode gl,int n,int e)/无向图邻接表的建立 int i,j,k; edgenode *p; getchar(); 11 printf(“请输入%d 个顶点的元素:“,n); for(i=0;iadjvex=j; p-next=gli.link; gli
