徐州工程学院数据结构

1、实验九 图的最小生成树算法的实现实验预备知识：1 .理解图最小生成树的意义和相应算法。2掌握带权图的存储结构。一、实验目的1. 使学生熟悉最小生成树的算法实现。2. 掌握带权图的存储结构和处理方法。二、实验环境1. 硬件：每个学生需配备计算机一台。操作系统：DOS或Windows2. 软件：DOS或 Windows操作系统 +Turbo C三、实验要求1. 能够独立完成带权图的存储和最小生成树的生成四、实验内容1. 在自己的U盘的“姓名+学号”文件夹中创建“实验9”文件夹，本 次实验的所有程序和数据都要求存储到本文件夹中。2. 现在某电信公司要对如下图的几个城市之间进行光纤连接布线，请 用合适

2、的存储结构将下图存储到计算机中方便进行处理。3. 现在公司想以最小的代价将所有城市连通，方便所有城市间通信，请用 普里姆算法和克鲁斯卡尔算法实现本图的最小生成树#include <stdio.h> #include <stdlib.h> #define INF 50typedef struct ArcNodeint adjvex;struct ArcNode *nextarc; int weight;ArcNode;typedef struct VNodechar data;ArcNode *firstarc; VNode,AdjList6;typedef struct

3、AdjList LH; int vexnum; int arcnum;Graph;typedef structchar nextvex; int lowcost; int know;Auxiliary_array;/ 该弧所指向的顶点位置/ 下一个临接点/ 弧的权重/ 表结点/ 顶点信息/ 指向下一个结点/ 创建头结点数组/ 图的点的个数/ 图的边的个数/ 辅助数组结构体void main (void)void buildtu (Graph*);void printgraph(Graph*);void prim( Graph *G, char u);char u;Graph UDG;Graph

4、 *G = &UDG;buildtu(G);printgraph(G); / 打印图 printf(" 请输入起始顶点： n"); while(getchar()!='n');u = getchar();prim(G ,u);void buildtu (Graph *G) / 建图int search(Graph *G,char a);int i,n1,n2,w;char a,b;ArcNode *p, *q;printf(" 请输入顶点个数和边的条数： n"); scanf("%d %d",&G-&g

5、t;vexnum,&G->arcnum);printf(" 请输入顶点信息 n");for (i = 0; i < G->vexnum; +i) while (getchar()!='n'); scanf("%c",&G->LHi.data); G->LHi.firstarc = NULL;printf(" 请输入有关系的结点和该边的权重 :n"); for(i=0;i<G->arcnum;+i) while (getchar()!='n');

6、scanf("%c %c %d",&a,&b,&w); n1=search(G,a); n2=search(G,b);p=G->LHn1.firstarc; if(p = NULL)p=G->LHn1.firstarc=(ArcNode *) malloc (sizeof(ArcNode); elsewhile( p->nextarc !=NULL ) p=p->nextarc; p=p->nextarc=(ArcNode *) malloc (sizeof(ArcNode);q=G->LHn2.firstarc;

7、 if(q = NULL)q=G->LHn2.firstarc=(ArcNode *) malloc (sizeof(ArcNode); elsewhile( 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;int search (Graph *G,char a

8、) / 确定顶点 a 在头结点数组中的位置 int i;for(i=0;i<G->vexnum;+i)if(G->LHi.data=a)return i;void printgraph(Graph *G)/ 打印图int i;ArcNode *p;for (i=0 ; i < G->vexnum; +i)p=G->LHi.firstarc;printf("data:%c t",G->LHi.data);while(p!=NULL) printf("firstarc->adjvex=%d",p->adj

9、vex); p=p->nextarc;printf("n");void prim( Graph *G, char u)/ 用 prim 算法实现最小生成树int search (Graph *G,char a);int minimize(Graph *G, Auxiliary_array);void printtable(Auxiliary_array);Auxiliary_array A6; / 创建辅助数组int i,j,seat;int location;ArcNode *p ;for (i = 0; i < G->vexnum; +i) Ai.ne

10、xtvex = '0'Ai.know = 0;Ai.lowcost = INF;location = search(G ,u);/ 确定 u 元素在头结点数组中的位置 for (p=G->LHlocation.firstarc ; p != NULL; p=p->nextarc ) i = p->adjvex;Ai.nextvex = G->LHlocation.data;Ai.lowcost = p->weight; Ai.know = 0;Alocation.know = 1;Alocation.lowcost = 0;Alocation.ne

11、xtvex = '0'for(j=0;j<G->vexnum-1;+j)seat = minimize( G,A ); printf("select min: %dn", seat);Aseat.know = 1; p=G->LHseat.firstarc; for (p; p != NULL; p=p->nextarc) i=p->adjvex;if(Ai.know = 0 && p->weight < Ai.lowcost) Ai.nextvex = G->LHseat.data; Ai.l

12、owcost = p->weight;printtable(A); / 打印辅助数组中的信息for (j = 0; j < G->vexnum; +j)if (j != location)printf("%c<>%cn",Aj.nextvex,G->LHj.data);int minimize(Graph *G, Auxiliary_array A)/ 取出辅助数组中权值最小的顶点所在的位 置int i,place,num;num = INF;for (i = 0; i < G->vexnum; +i)if(Ai.know =

13、 0 && num >= Ai.lowcost)num = Ai.lowcost;place = i;return place;void printtable(Auxiliary_array A) / 打印辅助数组int i;for (i = 0; i < 6; i+) printf("modifier:%c lowcost:%d known:%dn", Ai.nextvex, Ai.lowcost, Ai.know);实验总结： 通过该实验，我深刻明白到了自己对循环的能力不足，书写代码的逻辑性也不够强，相信在以后的学习中能加强这方面的学习，争取

14、在以后的学习中解决这两个方面 的问题。渭輛入顶点亍数和讪的煤数;渭軟人顶弋佬总*恫辆人有关展的幻人刊裟迪初釈蚩:b b &eelp d 5” o 3C 4 CL F 4W f 2fa c 5c d SL F £data：a firstarc->adjuex=1 Firstarc-iadjv#x=2firstarc>adju*x=3dta ： b f irctairc_>ad juM-Of i r st arc->ad j vp 4Firs t 曰厂jsk-2d a t a：c firstarc->adjusx=Gfiratarc-Jadjvess

15、firstarc->adj ux= 5fir&tarc?Bdjuex=1 f irstarc>adjuM= 3data：dl fir5tarc->adjuex=Gfiratarc-Jadjves=5firstarc>adju#x=2dita : p f irEtBrc'>adjuM-1 f irstarc- >ad jve)c-2firstarc- >adj ux-5 data：f fir5tarc->adjuBX=2Firstarc->adj ueK=3Firstarc>adj u»x=>l 怙紈人起给顶人=select in： 2 select Binlokicost ： Bknopn：1lDHCOEtknown： 1lOLlCOSt: 1knoun：1lDHCOEt：2knon： 1lcucost ： 3knoun：1lQHC