1、 数据结构课程设计总结报告 设计题目设计题目：以邻接链表的方式确定一个无向网以邻接链表的方式确定一个无向网 学生姓名学生姓名： 学学 院院： 专专 业：业： 班班 级级： 学学 号号： 指导教师指导教师： 年 月 日 一、设计题目一、设计题目 题目题目 3 以邻接链表的方式确定一个无向网，完成：以邻接链表的方式确定一个无向网，完成： 建立并显示出它的邻接矩阵；建立并显示出它的邻接矩阵； 对该图进行广度优先遍历，显示遍历的结果， （并随时显示队列的入、出情况） ；对该图进行广度优先遍历，显示遍历的结果， （并随时显示队列的入、出情况） ； 用普里姆算法构造其最小生成树，随时显示其构造的过程；用普
2、里姆算法构造其最小生成树，随时显示其构造的过程； 用用克鲁斯卡尔算法构造其最小生成树，随时显示其构造的过程；克鲁斯卡尔算法构造其最小生成树，随时显示其构造的过程； 二、运行环境（软、硬件环境）二、运行环境（软、硬件环境） 硬件环境：硬件环境： CPU：1000MHz 以上 内存：256MB以上 硬盘：60G 以上 软件环境：软件环境： 系统平台：Windows 2000 / Windows XP / Windows Vista / Windows 7 运行环境：TC 3.0 / Microsoft Visual C+ 6.0 三、算法设计的思想三、算法设计的思想 1、存储结构：邻接矩阵, 邻接
3、表。 2、遍历方式： 广度优先搜索(BFS) 3、实现最小生成树的方式： 普里姆算法 （Prime 算法） 和克鲁斯卡尔算法 （kruskai 算法） ，具体实现见代码。 四、算法的流程图四、算法的流程图 五、算法设计分析及截图五、算法设计分析及截图 （1）邻接表的建立. 邻接链表的头结点所使用的结构体： typedef struct node int adjvex; struct node *next; JD; typedef struct tnode int vexdata; struct node *firstarc; TD; 建立某无向图的邻接链表，所用函数：int crt_linkl
4、ist(TD g,int aM)，其中调用函数 int loc_vertex(TD g,int vex,int n)：找出边的头尾结点。主要利用 for 循环实现顶点和边 的输出，在确定边的时候，将该边的权值取地址给 ai-1j-1和 aj-1i-1。 测试结果： 邻接表的建立： 邻接矩阵的建立： （2）广度优先遍历 使用 void traver(TD g,int n)函数实现， 调用函数 void bfs(TD g,int v,int visited)： 利用 队列实现遍历过程，并用 for 循环输出每次入队出队情况。 测试结果： （3）最小生成树的方式：普里姆算法（Prime 算法） .
5、使用函数： void minispantree_PRIM(int aM,int n)，利用邻接矩阵实现 测试结果： 2-4； 1-2； 3-4； （4） 最小生成树的方式：克鲁斯卡尔算法（kruskai算法） 算法思想：设 N=(V,E)是连通网，TE 是 N 上最小生成树中边的集合 初始令 U=u0,(u0V), TE= 在所有 uU,vV-U 的边(u,v)E 中，找一条代价最小的边(u0,v0) 将(u0,v0)并入集合 TE，同时 v0 并入 U 重复上述操作直至 U=V 为止，则 T=(V,TE)为 N 的最小生成树 算法实现：图用邻接矩阵表示 边的表示方式：typedef stru
6、ct int vexh,vext; int weight; int flag; EDGE; 测试结果： 六、源代码六、源代码 #include #include #define M 10 #define MAX 100 typedef struct node int adjvex; struct node *next; JD; typedef struct tnode int vexdata; struct node *firstarc; TD; typedef struct int data; int jihe; VEX; typedef struct int vexh,vext; int weight; int flag; EDGE; void minitree_KRUSKAL(void) int n,i,m,min,k,j; VEX tM; EDGE eM; print
