[航空航天]数据机构实验报告重要的.doc

淮北师范大学程序设计课程设计通讯录管理系统学 院 计算机科学与技术 专 业 计算机科学与技术(师范) 学 号 20091201019 学 生 姓 名 葛晨晨 指导教师姓名 陈美荣 2011年4月14日(一) 设计目的要求任务n 目的 解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力； 件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能； 合运用所学的理论知识和方法独立分析和解决问题的能力； 用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。n 设计要求 核心数据结构用到的结构体要采用动态内存分配和链表结构。 不同的功能使用不同的函数实现（模块化），对每个函数的功能和调用接口要注释清楚。对程序其它部分也进行必要的注释。 对系统进行功能模块分析、画出总流程图和各模块流程图。 用户界面要求使用方便、简洁明了、美观大方、格式统一。 所有程序需调试通过。n 任务 输入城镇的个数N，和一个N*N的矩阵A，其中元素aij表示城镇i和城镇j的实际距离。 求解能够连通所有城镇的最小公路集（即通过prim算法或者kruskal算法求解如何在N个城镇之间建设最少条（N-1）公路，且公路总里程最短，使得各个城镇之间可以相互到达）。(二) 算法的基本思想1) 运用结构体和链表1. 使用如下结构来存储城镇以及城镇之间距离信息，是本程序的核心数据结构，定义如下：typedef struct Roadint marked; /*修建公路标志*/int vertex1; /*城镇a*/int vertex2; /*城镇b*/int weight; /*城镇a,b间距离*/;2.使用链表实现的存储，链表中结点结构定义如下：typedef struct node /*每个结点的数据结构*/ struct Road data; /*数据域，放学生基本信息*/ struct node *next; /*指针域*/Node,*Edge; 程序应具有以下基本功能：（1） 输入一个二维数组An*n来表示每对城镇间的距离，并根据A建立相应的链表；（2） prim 和kruskal算法的求解最小生成树；（3） 从指定的城镇出发，求解最小公路集，输出公路建设方案，并给出最短公路长度。2) 定义一：图图是有一个非空的顶点集合和一个描述顶点之间的关系即边的集合组成。它可以形式化的定义为：G=(V,E)V= | VertexTypeE=|,VP(,)其中，G表示一个图，V是图G中顶点的集合，E是V中顶点偶对的有限集，这些顶点偶对称为边，VertexType是用于描述顶点类型，集合E中P(,)的含义是：对有向图来说用“”表示，对无向图来说用“（）”表示，即从到 两个顶点之间存在边。3) 定义二：邻接矩阵是表示顶点之间相邻关系的矩阵。设G=(V,E)是一个图，其中V=v1,v2,vn。G的邻接矩阵是一个具有下列性质的n阶方阵：（本文主要为无向图的邻接矩阵）（1） 无向图的邻接矩阵是对称的;有向图的邻接矩阵可能是不对称的。（1）无向图的邻接矩阵中第i行第j列表示i结点到j结点的度即权值，可以表示为某一具体应用的数据。也表示i结点是否与j结点连通。4) 定义三：邻接表 是图的一种链式存储结构。在邻接表中，对图中每个顶点建立一个单链表，在第i个单链表中的结点表示依附于顶点vi的边每个结点由3个域组成，其中邻接点域指示与顶点vi邻接的点在途中的位置，链域指示下一条边或弧的结点；数据域存储和边和弧相关的信息。5) 克鲁斯卡尔算法设G=(V，E)是网络，最小生成树的初始状态为只有n个顶点而无边的非连通图T=(V，)，T中每个顶点自成为一个连通分量。将集合E中的边按权递增顺序排列，从小到大依次选择顶点分别在两个不同连通分量中的边加入图T，则原来的两个连通分量由于该边的连接而成为一个连通分量。依次类推，直到T中所有顶点都在同一个连通分量上为止，该连通分量就是G的一棵最小生成树.初始时，T为只有6个顶点的非连通图。边(v1, v2)的两个顶点v1，v2分别属于两个连通分量，将边(v1, v2)加入T。同理，将边(v1, v3)加入T。由于边(v2, v3)的两个顶点v2，v3属于同一个连通分量，因此，舍去这条边。同理将边(v0, v1)、(v1, v5)加入T，边(v3, v5)舍去，边(v3, v4)加入T。这时T中含的边数为5条，成为一个连通分量，T就是G的一棵最小生成树。 (三) 主要功能模块流程图Krushal算法描述：void kruskal(ALGraph G)int i,j,min=MAX,k=0, cost=0;/min用于记录最小权值int setMAX_VERTEX_NUM; /判断两个点是否在同一集合里Node *p,*q,*s;printf(n公路最优方案方案为：n);printf(起点 终点 路程n);for(i = 0; i G.vexnum; +i) seti = i; /初始化，将每个点自身作为一个集合while(kG.vexnum-1)for(i=0;inext) /查找最小权值的边if(p-data.weightdata.weight;q=p;j=i;if(G.verticesj.firstarc=q) G.verticesj.firstarc=q-next; /if-else用于删除最小权值的边elsefor(p=G.verticesj.firstarc;p!=q;p=p-next) s=p;s-next=q-next;if(setj!=setq-data.marked) /判断两点是否在同一集合，若不在，则输出这条边 printf(%s-%s %dn,G.verticesj.data.vertex1,G.verticesq-data.marked.data.vertex1,q-data.weight);cost=cost+q-data.weight;k+; setj=setq-data.marked;min=MAX; /将min置为最大值printf(n公路总长为：%dn,cost);(四) 系统测试1. 初始界面运行界面如下2. 输入城镇数和边数，按enter键输入个城镇的名称运行界面如下3. 输入每条边的起点终点和距离运行界面如下4. 按enter键输出结果得到邻接矩阵和公路最优方案的公路总长运行界面如下5. 退出（五）结论利用数据结构中的克鲁斯卡尔算法求最小生成树，继而求的公路最优求解方案，得到了个城市之间的最短路径。通过两周的数据结构课程实训，我不仅对图的概念有了一个新的认识，而且对算法和C语言有了更深的理解，在学习离散数学的时候，总觉得图是很抽象的东西，但是在学习了数据结构这门课后，我慢慢地体会到了其中的奥妙，图能够在计算机中存在，首先要捕捉他有哪些具体化、数字化的信息，比如说权值、顶点个数等，这也是说明了想要把生活中的信息转化成到计算机中必须用数字来完整的构成一个信息库，而图的存在，又涉及到了顶点之间的联系，图分为有向图和无向图，而无向图又是有向图在权值双向相等下的一种特例。在这次求可使构成n个城市的最小生成树的程序设计中，我采用了a i j数组利用邻接矩阵方式来储存城市与城市间信息，再利用经典的克鲁斯克尔算法求得了最小生成树。在这次课程设计中，我明白了编写一段代码，我们不仅要考虑它的可行性，更应该考虑它的算法复杂度，运行效率。做同一件事，一万个人有一万种做法，换而言之，一万个人写一段代码实现同一个功能可以得到一万段代码。由此，我们可以看出做一件事要精益求精，多加斟酌。（六）、源程序及系统文件使用说明#include #include #include#define MAX 100#define MAX_NAME 5 /*顶点值最大字符数*/#define MAX_VERTEX_NUM 20 /*最大顶点数*/typedef char VertexMAX_NAME;/*(邻接矩阵用)顶点名字串*/ typedef char VertexTypeMAX_NAME;/*(邻接链表用)顶点名字串*/ typedef int AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;/*邻接距阵*/ typedef struct Roadint marked; /*修建公路标志*/VertexType vertex1; /*城镇a*/int vertex2; /*城镇b*/int weight; /*城镇a,b 间距离*/Road;typedef struct node /*每个结点的数据结构*/struct Road data; /*数据域，放学生基本信息*/struct node *next; /*指针域*/Node,*Edge;/*表头向量的结点-*/typedef struct VNodestruct Road data;/VertexType data; Node *firstarc;VNode,AdjListMAX_VERTEX_NUM;/定义图结点/*链表带权图的结构信息-*/typedef struct Vertex vexsMAX_VERTEX_NUM; /*顶点向量*/ AdjMatrix arcs; /*邻接距阵*/AdjList vertices; /城镇 int vexnum,arcnum;ALGraph;/定义图 int LocateVe(ALGraph G,VertexType u)/链表求出点u所在位置 int i; for(i=0;iG.vexnum;+i)if(strcmp(G.verticesi.data.vertex1,u) = 0)return i; return -1; /*矩阵带权图的结构信息-*/ struct MGraph Vertex vexsMAX_VERTEX_NUM; /*顶点向量*/ AdjMatrix arcs; /*邻接距阵*/ int vexnum,arcnum; /*顶点数和弧数*/; int LocateVex(MGraph G,Vertex u)/矩阵求点u所在位置 int i; for(i=0;iG.vexnum;+i)if(strcmp(u,G.vexsi)=0) return i; return -1; /*-*/*邻接矩阵的存入算法-*/*-*/建立带权邻接矩阵结构/建立带权邻接矩阵结构void CreateGraph(MGraph &G) int i,j,k,w; char c; Vertex va,vb; printf(邻接矩阵请输入城镇数和边数(分别以空格为分隔):n); scanf(%d %d,&G.vexnum,&G.arcnum); printf(邻接矩阵请输入%d个城镇名:n,G.vexnum); for(i=0;iG.vexnum;+i) /* 读入顶点信息*/ scanf(%s,G.vexsi); for(i=0;iG.vexnum;i+) /*初始化邻接矩阵*/ for(j=0;jG.vexnum;j+) G.arcsji=G.arcsij=9999; for(k=0;kG.arcnum;+k) /*读入边*/ printf(邻接矩阵请输入%d条边各自的起点,终点,以及之间的距离(分别用空格分隔):n,k+1); scanf(%s%s,va,vb); scanf(%s,&c); if(0c&c9) w=c-0; else printf(ERRORn); exit (0); i=LocateVex(G,va); j=LocateVex(G,vb); G.arcsij=G.arcsji=w; /*对称*/ printf(所得到的邻接矩阵为:n); for (i=0;iG.vexnum;i+) for (j=0;jG.vexnum;j+) printf( %d ,G.arcsij); printf(n); void k1()MGraph g; CreateGraph(g); /*-*/*邻接表的克鲁斯卡尔算法-*/-*/邻接表创建带权图void CreateGraph(ALGraph &G) int i,j,k,w;VertexType va,vb;printf(请输入城镇数,边数(请用空格分开):n); /*输入顶点数、弧数*/scanf(%d %d,&G.vexnum,&G.arcnum);printf(请输入各城镇的名称:n);for(i = 0; i G.vexnum; +i) /*初始化顶点值*/scanf(%s,G.verticesi.data.vertex1); strcpy(G.vexsi,G.verticesi.data.vertex1);/for(i = 0; i G.vexnum; +i) /初始化vertices数组G.verticesi.firstarc = NULL; for(i=0;iG.vexnum;i+) /*初始化邻接矩阵*/ for(j=0;jG.vexnum;j+) G.arcsji=G.arcsij=9999;for(k = 0; k data.marked=j;/初始化p-data.weight=w;p-next=G.verticesi.firstarc; /插表头G.verticesi.firstarc=p;Node *q = (Node *)malloc(sizeof(Node); q-data.marked=i;q-data.weight=w;q-next=G.verticesj.firstarc;G.verticesj.firstarc=q; printf(所得到的邻接矩阵为:n);/*输出矩正*/ for (i=0;iG.vexnum;i+) for (j=0;jG.vexnum;j+) printf( %d ,G.arcsij); printf(n); /*邻接表的克鲁斯卡尔算法*/void kruskal(ALGraph G)int i,j,min=MAX,k=0, cost=0;/min用于记录最小权值int setMAX_VERTEX_NUM; /判断两个点是否在同一集合里Node *p,*q,*s;printf(n公路最优方案方案为：n);printf(起点 终点 路程n);for(i = 0; i