Prim算法.doc

数据结构课程设计数据结构课程设计报告 设计题目： 构造可以使n个城市连接的最小生成树 姓名： 吴友文 学号： 211415076 专业： 物联网（嵌入式培养） 院系： 计算机科学与技术学院 班级： 1406 指导教师： 王江涛 2016年 1 月 8 日 摘要英文摘要目 录一、问题描述题目内容：构造可以使n个城市连接的最小生成树给定一个地区的n个城市间的距离网，用Prim算法建立最小生成树，并计算得到的最小生成树的代价。1 基本要求：1) 城市间的距离网采用邻接矩阵表示，若两个城市之间不存在道路，则将相应边的权值设为自己定义的无穷大值。（要求至少10个城市，15条边）2) 最小生成树中包括的边及其权值，并显示得到的最小生成树的代价。二、需求分析1 本程序的功能包括数组表示候选最短边的集合，邻接矩阵的初始化，Prim算法生成最小生成树。2 程序运行后显现提示信息，等候根据提示决定各项信息条件。3 用户输入数据完毕，程序将输出运行结束。4 测试数据应为邻接矩阵的表达、最小生成树以及最小生成树的代价。三、概要设计1 辅助数组数据类型定义为：struct shortEdge int lowcost;/权值 int adjvex;/最短边的邻接点 ; 操作集合：(1)MGraph();初始化邻接矩阵 (2)MGraph()析构函数 (3)void CreateMGraph();创建便所对应的顶点序号，以及其权值(4)void printMGraph();输出邻接矩阵 (5)void Prim();Prim算法生成最小生成树并计算其代价 四、数据结构设计1 元素类型 DataType vertexMaxSize; /存放顶点的数组 int arcsMaxSizeMaxSize; /存放图中边的数组 int versNum, arcsNum; /定点数和边数 shortEdge shortEdgeMaxSize; /最短边数组大小MaxSize 30 /全局变量辅助数组大小INFINITYN 65536 /表示权值无限大五、算法设计 1、算法分析首先，采用Prime算法构造最小生成树，Prime算法基于的存储结构为图的存储结构，由于在算法执行过程中，需要不断读取任意两个顶点之间边的权值，所以，图采用邻接矩阵存储，那么我们就要实现邻接矩阵的初始化。然后，我们还需要自定义边所对应的顶点序号以及其权值，所以就要建立一个自定义的成员函数。其次，题目要求我们输出邻接矩阵，在自定义完的各项数据的基础上，输出邻接矩阵。最后，Prime算法最小生成树，基本思想是：假设G(V，E)是连通的，TE是G上最小生成树中边的集合。算法从Uu0（u0V）、TE开始。重复执行下列操作：在所有uU，vVU的边(u，v)E中找一条权值最小的边(u0,v0)并入集合TE中，同时v0并入U，直到VU为止。此时，TE中必有n-1条边，T=(V，TE)为G的最小生成树。显然，Prime算法的关键是如何找到U和V-U的最短边来扩充生成树T。所以Prime算法基于的另一个存储结构就是候选最短边集：设置一个数组shortEdgen表示候选最短边集，数组元素包括adjvex和lowcost两个域，分别表示候选最短边的邻接点和权值。而最小代价即是最小生成树上边的权值之和。 2、算法实现LinkList CreateList(void) / /尾插法建立带头结点的通讯录链表算法 LinkList head=new ListNode; /申请头结点 ListNode *p,*rear; int flag=0; /结束标志置0 rear=head; /尾指针初始指向头结点 while(flag=0) p=(ListNode *)malloc(sizeof(ListNode); /申请新结点 printf(编号 姓名(8) 性别(2) 电话(11) 地址(31)n); printf(-n); scanf(%d%s%s%s%s,&(p-data.num),,p-data.sex,p-data.phone,p-data.addr);n+; rear-next=p; /新结点连接到尾结点之后 rear=p; /尾指针指向新结点 printf(结束建表吗？(1/0):); scanf(%d,&flag); /读入一个标志数据 rear-next=NULL; /终端结点指针域置空 return head; /返回链表头指针 3、 算法流程图Prime算法构造最小生成树的过程：在红线相交的线上找最小值 (a)从V0开始 (b) (c) (d) (e) (f)六、程序测试与实现1、函数之间的调用关系2、主程序 int main() MGraph m1; m1.CreateMGraph(); m1.printMGraph(); m1.Prim();3、测试数据4、测试结果七、调试分析1链表中的结点变量是通过指针变量来访问的。因为在C语言中是用P来表示P所指的变量，又由于结点类型是一个结构类型，因此可用P data和Pnext分别表示结点的数据域变量和指针域变量。指针变量的值要么为空(NULL)，不指向任何结点；要么其值为非空，即它的值是一个结点的存储地址。注意，当P为空值时，则它不指向任何结点，此时不能通过P来访问结点，否则会引起程序错误。2算法的时空分析：(1)对于本程序的通讯录单链表，其操作运算主要有建立单链表(尾插法)CreateList,查询(按编号和按姓名)ListFind,插入运算InsertNode,删除运算DelNode等。以上各操作运算的平