数据结构最短路径程序设计

教学单位　计算机科学与技术  学生学号　 111714217　 数据结构 课程报告书 题  目管道铺设施工的最佳方式选择 学生姓名　        潘程　 　    专业名称      网络工程  　 　 指导教师    　李志敏    　 目  录 一、问题描述    1 二、引言    1 三、需求    1 四、概要设计    1 4.1普利姆算法分析    1 4.1.1普利姆算法思想    1 4.1.2算法过程描述    2 4.2模块分析    2 4.3抽象数据类型分析    3 五、详细设计    3 5.1信息输入模块    3 5.2建立最小生成树并输出结果    4 六、测试结果    5 七、设计体会    6 八、实验总结    6 参考文献    7 附录    7 源程序代码    7 谢辞    16 一、问题描述 N(N>10)个居民区之间需要铺设煤气管道。假设任意两个居民区之间都可以铺设煤气管道，但代价不同。问题的实质就是编写相应程序求解最小生成树问题。 程序要求： 事先任意两个居民区之间铺设煤气管道的代价存入磁盘文件中。设计一个最佳使得这N个居民区之间铺设煤气管道所需代价最小，并将结果以图形方式在屏幕上输出。 二、引言 C语言作为一门最通用的语言，从语言产生到现在，它已经成为最重要和最流行的编程语言之一。在各种流行编程语言中，都能看到C语言的影子。学习掌握C语言是每一个计算机技术人员的基本功之一。 实际生活中最小生成树的问题具有很大的意义。例如，本文所讨论的构架居民区之间铺设煤气管道代价最小，还有在若干地区铺设光缆等等。最小生成树让许多诸如求造价最小、最短路径等最优化的现实问题找到了理论依据，并提供了有效的解决。 三、需求分析 在N（N>10）个居民区之间铺设煤气管道所需代价最小，即求最小生成树问题。在我们的课本中介绍了两种求解方法：普利姆算法和克鲁斯卡尔算法。普利姆算法与网的变数无关， 适宜求解边稠密的网的最小生成树。而克鲁斯卡尔算法正好相反，适宜求解边稀疏的最小生成树。 由于在实际问题中，居民数量一般很有限，而任何两个居民区都可能有连线，即这样的图应该是边较为稠密的。因此，我们选择了普利姆算法对问题进行求解。 四、概要设计 4.1普利姆算法分析 4.1.1普利姆算法思想 普利姆算法的思想是：在图中人去一个定点k0作为开始点，令U={k0}，W=V-U，其中V为图中所有顶点集，然后找一个顶点在U中，另一个顶点在w中的边中最短的一条，找到后，将该边作为最小生成树的树边保存起来，并将该边顶点全部加入U集合中，并从W中删除这些顶点，然后重新调整U中顶点到W中顶点的距离，使之保持最小，再重复此过程，直到W为空集。 4.1.2算法过程描述 （1）在图G=（V，E）（V是顶点，E是边）中，从集合V中任取一个顶点，如k0放入集合U中，这时，U={k0}，集合T（E）为空。 （2）从k0出发寻找与U中顶点相邻权值最小的边的另一顶点k1 ，并使k1加入U。即U={k0，k1}，同时将该边加入集合T（E）中。 （3）重复（2），直到U=V为止。 （4）这时T（E）中有n-1条边，T=（U，T（E））就是一一颗最小生成树。                     4.2模块分析 根据对模型的功能分析，该管道铺设设计可以具有以下功能： 管道铺设信息的输入； 最小生成树信息的输出； 功能模块图： 4.3抽象数据类型分析 areanum      居民区总数（顶点总数）； edgenum      边的总数； date[ ][20]    邻接矩阵存储图结构； s              边的权值； short-way[i]    居民区i到目前生成树中所有点集U中某个居民区的路程最小值 near-area[i]    U中能使其最小的居民区 五、详细设计 5.1信息输入模块 //读入图的信息，并将邻接矩阵输出 void  read() { int  areanum, edgenum,data[20][20]; printf("请依次输入顶点数和边数:\n"); scanf("%d,%d",&areanum,&edgenum); //初始化邻接矩阵各元素值 int  i, j; for(i=0;i #include #include #include #include #define MAX_VERTEX_NUM 20    // 最大顶点个数 #define MAX_NAME 3 // 顶点字符串的最大长度+1 //#define MAX_INFO 20 // 相关信息字符串的最大长度+1 #define INFINITY INT_MAX    // 用整型最大值代替∞ typedef int VRType; typedef char InfoType; typedef char VertexType[MAX_NAME]; // 邻接矩阵的数据结构 typedef struct { VRType adj; // 顶点关系类型。对无权图，用1(是)或0(否)表示相邻否； // 对带权图，则为权值类型 InfoType *info; // 该弧相关信息的指针(可无) }ArcCell, AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 图的数据结构 typedef struct { VertexType vexs[MAX_VERTEX_NUM];    // 顶点向量 AdjMatrix arcs;        // 邻接矩阵 int vexnum,            // 图的当前顶点数 arcnum;            // 图的当前弧数 } MGraph; // 记录从顶点集U到V-U的代价最小的边的辅助数组定义 typedef struct { VertexType adjvex; VRType lowcost; }minside[MAX_VERTEX_NUM]; // 若G中存在顶点u,则返回该顶点在图中位置;否则返回-1。 int LocateVex(MGraph G,VertexType u) { int i; for(i = 0; i < G.vexnum; ++i) if( strcmp(u, G.vexs[i]) == 0) return i; return -1; } //代价保存为文件 //代价存入文件 void  wenjian() { //system("cls"); FILE *fp; char s[50],ch; strcpy(s,"D:\\record.txt"); if((fp=fopen(s,"ab+"))==NULL) {      printf("无法打开此文件\n"); exit(0); } else { //    printf("请向磁盘中输入原点总数和边的总数：\n"); //    printf("请输入顶点数边数\n"); //    scanf("%d %d",&G.vexnum,&G.arcnum); //    printf("请输入各居民点:"); //    for(int i=1;i<=N;i++) //    { //        scanf("%c",&G.vexs[i]); //    }in //    fput(G.vexs[i],fp); //    } //    printf("请向磁盘中输入各原点和边的总数同时记录原点，目的点，及相应的权值:(输入#键表示结束)\n"); printf("请向磁盘中输入各原点和边的总数:(输入$键表示结束)\n"); ch=getchar(); while(ch!='$') { fputc(ch,fp); ch=getchar(); } printf("请向磁盘中输入原点，目的点，及相应的权值:(输入#键表示结束)\n"); ch=getchar(); while(ch!='#') { fputc(ch,fp); ch=getchar(); } } fclose(fp); system("pause"); } //从文件中得到信息构成图 void xianshi () { //system("cls"); FILE *fp; char s[50],ch; strcpy(s,"D:\\record.txt"); if((fp=fopen(s,"r"))==NULL) {      printf("无法打开此文件\n"); exit(0); } else { while(!feof(fp)) { ch=fgetc(fp); putchar(ch); } } putchar(10); fclose(fp); system("pause"); } // 算法7.2  P162 // 采用数组(邻接矩阵)表示法,构造无向网G。 int CreateAN(MGraph *G) { //system("cls"); int i,j,k,w; //char s[MAX_INFO],*info; //    char *info; VertexType va,vb; printf("请输入无向网G的顶点数,边数,(空格区分) "); scanf("%d%d",&(*G).vexnum,&(*G).arcnum); printf("请输入%d个顶点的值:\n",(*G).vexnum); for(i=0;i<(*G).vexnum;++i) // 构造顶点向量 scanf("%s",(*G).vexs[i]); for(i=0;i<(*G).vexnum;++i) // 初始化邻接矩阵 for(j=0;j<(*G).vexnum;++j) { (*G).arcs[i][j].adj=INFINITY; // 网初始化为无穷大 //    (*G).arcs[i][j].info=NULL; } printf("请输入%d条边的顶点1 顶点2 权值(以空格作为间隔): \n",(*G).arcnum); for(k=0;k<(*G).arcnum;++k) { scanf("%s%s%d%*c",va,vb,&w); // %*c吃掉回车符 i=LocateVex(*G,va); j=LocateVex(*G,vb); (*G).arcs[i][j].adj=(*G).arcs[j][i].adj=w; // 无向 //    if(IncInfo) //    { //        printf("请输入该边的相关信息(<%d个字符): ",MAX_INFO); //        gets(s); //        w=strlen(s); //        if(w) //        { //            info=(char*)malloc((w+1)*sizeof(char)); //            strcpy(info,s); //            (*G).arcs[i][j].info=(*G).arcs[j][i].info=info; // 无向 //        } //    } } printf("输出临接矩阵：\n"); for(i=0;i<(*G).vexnum;++i) for(j=0;j<(*G).vexnum;++j) {  if( j%3==0)printf("\n"); printf("%d ", (*G).arcs[i][j].adj); } return 1; system("pause"); } // 求closedge.lowcost的最小正值 int minimum(minside SZ,MGraph G) { int i=0,j,k,min; while(!SZ[i].lowcost) i++; min=SZ[i].lowcost; // 第一个不为0的值 k=i; for(j=i+1;j0) if(min>SZ[j].lowcost) { min=SZ[j].lowcost; k=j; } return k; } // 算法7.9 P175 // 用普里姆算法从第u个顶点出发构造网G的最小生成树T,输出T的各条边 void MiniSpanTree_PRIM(MGraph G,VertexType u) {  //system("cls"); int i,j,k; minside closedge; k=LocateVex(G,u); for(j=0;j论文

政研论文下载论文大学下载论文大学下载关于长拳的论文浙大论文封面下载