数据结构试验报告

1、实验四 用普利姆算法求最小生成树题目：编制一个用邻接表存储图，用普利姆算法求最小生成树的程序班级： 计科0906 姓名： 于兆杰 学号： 200948140626 完成日期： 2010-12-7 - - 一、需求分析1、在本次试验中，定义了多种的struct结构，分别存储结点信息，及相连的结点位置及结点信息加边上的权值。2、演示程序以用户和计算机的对话方式执行，即在计算机显示“提示信息”后之后，由用户在键盘上输入演示程序中规定的运算命令；相应的输入数据（滤去输入中不符合要求的字符）和运算结果显示在其后。3、程序执行的命令包括：（1）创建带权无向图（2）输出图（3）返回结点位置（4）求于当前结点

2、连接最小权值的下一条边（5）求最小生成树4、测试数据二、概要设计为实现上述功能，采用了邻接表存储图中结点信息，及链式存储与同一个结点相连的结点信息。1本程序包含五个模块：（1）主程序模块：int main()定义变量；接受命令；处理命令；退出（return 0）；（2）创建带权无向图生成一个带权值的无向图；（3）输出图将五项图的信息输出；（4）返回结点位置给出结点信息，返回其位置；（5）求于当前结点连接最小权值的下一条边将下一个结点找出；（6）求最小生成树生成最小生成树。各模块之间的调用关系如下：主函数创建无向图输出图求最小生成树返回结点位置求最小权值的下一个结点三、详细设计1、定义头文件#i

3、nclude<iostream>#include<stdio.h>#include<stdlib.h>#include<string.h>#define MAX 20#define OK 1#define ERROR 0typedef int InfoType;typedef char VertexType;using namespace std;2、元素类型、节点类型和指针类型typedef struct ArcNodeint adjvex;struct ArcNode * nextarc;InfoType info;ArcNode;typed

4、ef struct VNodeVertexType data;ArcNode * firstarc;VNode,AdjListMAX;typedef struct AdjList vertices;int vexnum,arcnum;int kind;ALGraph;typedef structVertexType adj;/*当前点*/int lowcost;/*代价*/minsideMAX;3、创建带权无向图int CreatUDG(ALGraph & G)int i,s,d,w;ArcNode *p,*q;cout<<"请输入结点数目:"cin&g

5、t;>G.vexnum;cout<<"请输入边数:"cin>>G.arcnum;getchar();for(i=1;i<=G.vexnum;i+)cout<<"请输入第"<<i<<"顶点:"cin>>G.verticesi.data;getchar();G.verticesi.firstarc=NULL;for(i=1;i<=G.arcnum;i+)cout<<"请输入第"<<i<<&quo

6、t;条边的起点序号和终点序号及权值"<<endl;cin>>s>>d>>w;getchar();p=(struct ArcNode *)malloc(sizeof ( struct ArcNode);q=(struct ArcNode *)malloc(sizeof ( struct ArcNode);p->adjvex=d;p->info=w;q->adjvex=s;q->info=w;p->nextarc=G.verticess.firstarc;G.verticess.firstarc=p;q->

7、;nextarc=G.verticesd.firstarc;G.verticesd.firstarc=q;return OK; 4、输出图int PrintALGraph(ALGraph * G)int i;cout<<"打印无向图:"<<endl;for(i=1;i<=G->vexnum;i+)cout<<"第"<<i<<"个结点的信息为"<<G->verticesi.data<<endl;while(G->verticesi

8、.firstarc->nextarc!=NULL)cout<<"所连结点的信息为:"cout<<G->verticesG->verticesi.firstarc->adjvex.data<<endl;cout<<"此边上的权值为:"cout<<G->verticesi.firstarc->info<<endl;G->verticesi.firstarc=G->verticesi.firstarc->nextarc;cout<

9、<"所连结点的信息为:"cout<<G->verticesG->verticesi.firstarc->adjvex.data<<endl;cout<<"此边上的权值为:"cout<<G->verticesi.firstarc->info<<endl;return OK; 5、返回结点位置void PlusList(Number *L1,Number *L2,char a) /两个长整数加减运算int Locatevex(ALGraph G,char v)in

10、t i=0;while(G.verticesi.data!=v)+i;return i; 6、求于当前结点连接最小权值的下一条边int minimum(minside SZ,ALGraph G)return k;int i=0,j,k,min;while(!SZi.lowcost)i+;min=SZi.lowcost;k=i;for(j=i+1;j<G.vexnum;j+)if(SZj.lowcost>0&&min>SZj.lowcost)min=SZj.lowcost;k=j;7求最小生成树void MiniSpanTree_PRIM(ALGraph G,V

11、ertexType u)int i,j,k;minside closedge;k=Locatevex(G,u);while(G.verticesk.firstarc->nextarc!=NULL)strcpy(closedgeG.verticesk.firstarc->adjvex.adj,u);closedgeG.verticesk.firstarc->adjvex.lowcost=G.verticesk.firstarc->info;closedgek.lowcost=0; cout<<"最小代价生成树的各条边为:n"for(i=1;

12、i<G.vexnum;+i)k=minimum(closedge,G);cout<<"n"<<closedgek.adj<<'-'<<G.verticesk.data<<endl;closedgek.lowcost=0;while(G.verticesk.firstarc->nextarc!=NULL)j=G.verticesk.firstarc->adjvex;if(G.verticesk.firstarc->info<closedgej.lowcost)strcpy

13、(closedgej.adj,G.verticesk.data);closedgej.lowcost=G.verticesk.firstarc->info;G.verticesk.firstarc=G.verticesk.firstarc->nextarc;7、主程序模块int main()ALGraph G;minside SZ;int i,j;char v;CreatUDG( G);PrintALGraph(&G);cin>>v;getchar();i=Locatevex(G,v);cout<<i<<endl;j=minimum(SZ,G);cout<<j;MiniSpanTree_PRIM(G,G.vertices1.data);return 0;四、调试分析1在存储边的权值时开始用的是存储信息的指针，不知道怎样赋予边于权值，最后将权值赋给已给变量，而不用指针指向，达到了想要的结果。如图1五、运行结果图1六、实验环境（1）Windows XP系统下（2）编程环境：VC6.0+ ，T