实验六图的应用.docVIP

实验六 图的应用 一、实验目的 1、使学生可以巩固所学的有关图的基本知识。 2、熟练掌握图的存储结构。 3、掌握如何应用图解决各种实际问题。 二、实验内容 本次实验提供2个题目，学生可以任选一个！ 题目一：最小生成树问题 [问题描述] 若要在n个城市之间建设通信网络，只需要假设n-1条线路即可。如何以最低的经济代价建设这个通信网，是一个网的最小生成树问题。。由学生依据软件工程的测试技术自己确定。 四、调试分析 输入点的个数： 输入边数 输出最小生成树 总结 写程序之前，要综合考虑各种因素，选取自己需要的数据结构。然后选定一种或几种存储结构来具体的决定后面的函数的主要风格。最后在编写每一个函数之前，可以仔细斟酌比较，挑选出最适合当前状况的算法。这样，即使在完整的程序还没有写出来之前，自己心中已经有了明确的原图了。另外，我还体会到深刻理解数据结构的重要性。只有真正理解这样定义数据类型的好处，才能用好这样一种数据结构。了解典型数据结构的性质是非常有用的，它往往是编写程序的关键。在这次试验中，我对参数的调用也进行了很多种尝试，已经能够相对准确的选择合适的参数形式来实现函数之间的数据传输交互了。 六、源代码 #includestdio.h #includestdlib.h typedef struct{ char v1; char v2; int weight; }Edge; typedef struct{ Edge space[100]; int Elength; }Headtype; typedef struct { char v; int flag; }Dgree; typedef struct{ Dgree biao[20]; int Glength; }Mark; void InitMark(Mark M,int x){ int j; M.Glength=x; printf(请依次输入这些点:\n); for(j=1;j=x;j++) { scanf(%s,M.biao[j].v); M.biao[j].flag=-1; } } void InitHeadType(Headtype H,int y){ int k; H.Elength=y; for(k=1;k=y;k++) { printf(请输入边的关系:\n); scanf(%s%s%d,H.space[k].v1,H.space[k].v2,H.space[k].weight); } } void HeadAdjust(Headtype H,int s,int m) { Edge rc; int p; rc=H.space[s]; for(p=2*s;p=m;p*=2) { if(pm(H.space[p].weightH.space[p+1].weight)) ++p; if(rc.weightH.space[p].weight) break; H.space[s]=H.space[p]; s=p; } H.space[s]=rc; } void HeadSort(Headtype H){ int q; Edge rb; for(q=H.Elength/2;q0;--q) HeadAdjust(H,q,H.Elength); for(q=H.Elength;q1;--q) { rb=H.space[1]; H.space[1]=H.space[q]; H.space[q]=rb; HeadAdjust(H,1,q-1); } } void main(){ int Gnumber,Enumber,a,b,c; printf(请输入点的个数:\n); scanf(%d,Gnumber); printf(请输入边数:\n); scanf(%d,Enumber); Headtype H; Mark M; Dgree e1,e2; InitMark(M,Gnumber); InitHeadType(H,Enumber); HeadSort(H); printf(输出最小生成树;\n); for(a=1;a=Enumber;a++) { for(b=1;b=Gnumber;b++) { if(M.biao[b].v==H.space[a].v1) {e1=M.biao[b]; break; } } for(c=1;c=Gnumber;c++) { if(M.biao[c].v==H.space[a].v2