徐州工程学院数据结构最小生成树实验文档

实验九图的最小生成树算法的实现实验预备知识：1．理解图最小生成树的意义和相应算法。2．掌握带权图的存储结构。一、实验目的1．使学生熟悉最小生成树的算法实现。2．掌握带权图的存储结构和处理方法。二、实验环境⒈硬件：每个学生需配备计算机一台。操作系统：DOS或Windows；⒉软件：DOS或Windows操作系统+TurboC；三、实验要求1．能够独立完成带权图的存储和最小生成树的生成四、实验内容1．在自己的U盘的“姓名+学号”文件夹中创建“实验9”文件夹，本次实验的所有程序和数据都要求存储到本文件夹中。2．现在某电信公司要对如下图的几个城市之间进行光纤连接布线，请用合适的存储结构将下图存储到计算机中方便进行处理。3．现在公司想以最小的代价将所有城市连通，方便所有城市间通信，请用普里姆算法和克鲁斯卡尔算法实现本图的最小生成树#includestdio.h#includestdlib.h#defineINF50typedefstructArcNode{intadjvex;//该弧所指向的顶点位置structArcNode*nextarc;//下一个临接点intweight;//弧的权重}ArcNode;//表结点typedefstructVNode{chardata;//顶点信息ArcNode*firstarc;//指向下一个结点}VNode,AdjList[6];typedefstruct{AdjListLH;//创建头结点数组intvexnum;//图的点的个数intarcnum;//图的边的个数}Graph;typedefstruct{charnextvex;intlowcost;intknow;}Auxiliary_array;//辅助数组结构体voidmain(void){voidbuildtu(Graph*);voidprintgraph(Graph*);voidprim(Graph*G,charu);charu;GraphUDG;Graph*G=&UDG;buildtu(G);printgraph(G);//打印图printf(请输入起始顶点：\n);while(getchar()!='\n');u=getchar();prim(G,u);}voidbuildtu(Graph*G){//建图intsearch(Graph*G,chara);inti,n1,n2,w;chara,b;ArcNode*p,*q;printf(请输入顶点个数和边的条数：\n);scanf(%d%d,&G-vexnum,&G-arcnum);printf(请输入顶点信息\n);for(i=0;iG-vexnum;++i){while(getchar()!='\n');scanf(%c,&G-LH[i].data);G-LH[i].firstarc=NULL;}printf(请输入有关系的结点和该边的权重:\n);for(i=0;iG-arcnum;++i){while(getchar()!='\n');scanf(%c%c%d,&a,&b,&w);n1=search(G,a);n2=search(G,b);p=G-LH[n1].firstarc;if(p==NULL){p=G-LH[n1].firstarc=(ArcNode*)malloc(sizeof(ArcNode));}else{while(p-nextarc!=NULL){p=p-nextarc;}p=p-nextarc=(ArcNode*)malloc(sizeof(ArcNode));}q=G-LH[n2].firstarc;if(q==NULL){q=G-LH[n2].firstarc=(ArcNode*)malloc(sizeof(ArcNode));}else{while(q-nextarc!=NULL){q=q-nextarc;}q=q-nextarc=(ArcNode*)malloc(sizeof(ArcNode));}p-adjvex=n2;p-weight=w;p-nextarc=NULL;q-adjvex=n1;q-weight=w;q-nextarc=NULL;}}intsearch(Graph*G,chara){//确定顶点a在头结点数组中的位置inti;for(i=0;iG-vexnum;++i){if(G-LH[i].data==a){returni;}}}voidprintgraph(Graph*G){//打印图inti;ArcNode*p;for(i=0;iG-vexnum;++i){p=G-LH[i].firstarc;printf(data:%c\t,G-LH[i].data);while(p!=NULL){printf(firstarc-adjvex=%d,p-adjvex);p=p-nextarc;}printf(\n);}}voidprim(Graph*G,charu){//用prim算法实现最小生成树intsearch(Graph*G,chara);intminimize(Graph*G,Auxiliary_array[]);voidprinttable(Auxiliary_array[]);Auxiliary_arrayA[6];//创建辅助数组inti,j,seat;intlocation;ArcNode*p;for(i=0;iG-vexnum;++i){A[i].nextvex='0';A[i].know=0;A[i].lowcost=INF;}location=search(G,u);//确定u元素在头结点数组中的位置for(p=G-LH[location].firstarc;p!=NULL;p=p-nextarc){i=p-adjvex;A[i].nextvex=G-LH[location].data;A[i].lowcost=p-weight;A[i].know=0;}A[location].know=1;A[location].lowcost=0;A[location].nextvex='0';for(j=0;jG-vexnum-1;++j){seat=minimize(G,A);printf(selectmin:%d\n,seat);A[seat].know=1;p=G-LH[seat].firstarc;for(p;p!=NULL;p=p-nextarc){i=p-adjvex;if(A[i].know==0&&p-weightA[i].lowcost){A[i].nextvex=G-LH[seat].data;A[i].lowcost=p-weight;}}}printtable(A);//打印辅助数组中的信息for(j=0;jG-vexnum;++j)if(j!=location)printf(%c----%c\n,A[j].nextvex,G-LH[j].data);}intminimize(Graph*G,Auxiliary_arrayA[]){//取出辅助数组中权值最小的顶点所在的位置inti,place,num;num=INF;for(i=0;iG-vexnum;++i){if(A[i].know==0&&num=A[i].lowcost){num=A[i].lowcost;place=i;}}returnplace;}voidprinttable(Auxiliary_arrayA[]){//打印辅助数组inti;for(i=0;i6;i++){printf(modifier:%clowcost:%dknown:%d\n,A[i].nextvex,A[i].lowcost,A[i].know);}}实验总结：通过该实验，我深刻明白到了自己对循环的能力不足，书写代码的逻辑性也不够强，相信在以后的学习中能加强这方面的学习，争取在以后的学习中解决这两个方面的问题。