最小生成树问题.doc

数 据 结 构课 程 设 计 说 明 书学生姓名:学 号：0学 院:软件学院专 业:信息管理与信息系统题 目:最小生成树问题成绩指导教师李华玲 李玉蓉2010年1月7日1 设计目的数据结构课程主要介绍最常用的数据结构，阐明各种数据结构内在的逻辑关系，讨论其在计算机中的存储表示，以及在其上进行各种运算时的实现算法，并对算法的效率进行简单的分析和讨论。进行数据结构课程设计要达到以下目的：n 了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力；n 初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；n 提高综合运用所学的理论知识和方法独立分析和解决问题的能力；训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。.2. 设计内容和要求设计内容：在n个城市之间建设网络，只需保证连通即可，求最经济的架设方法。存储结构采用（邻接表和邻接矩阵）两种，采用课本上的两种求解算法。设计要求：(1) 符合课题要求，实现相应功能；(2) 要求界面友好美观，操作方便易行；(3) 注意程序的实用性、安全性。3本设计所采用的数据结构*数据对象V：v是具有相同特性的数据元素的集合，称为顶点集。*数据关系R：R=VR VR=|v,w属于v且p(v,w),(v,w)表示从v到w的弧，谓词p(v,w)定义了弧的意义或信息*所用函数：void ljjzprint(MGraph_L G)void adjprint(algraph gra)void kruscal_arc(MGraph_L G,algraph gra)int localvex(MGraph_L G,char v)int creatMGraph_L(MGraph_L &G)int creatadj(algraph &gra,MGraph_L G)int firstadjvex(algraph gra,vnode v)/返回依附顶点V的第一个点int prim(int gmax,int n) int find*结构体：typedef struct ArcCell int adj; char *info;ArcCell,AdjMatrix2020;typedef struct char vexs20; AdjMatrix arcs; int vexnum,arcnum;MGraph_L;typedef struct arcnode/弧结点 int adjvex;/该弧指向的顶点的位置 struct arcnode *nextarc;/弧尾相同的下一条弧 char *info;/该弧信息arcnode;typedef struct vnode/邻接链表顶点头接点 char data;/结点信息 arcnode *firstarc;/指向第一条依附该结点的弧的指针vnode,adjlist;typedef struct/图的定义 adjlist verticesmax; int vexnum,arcnum; int kind;algraph;typedef struct acrint pre;int bak;int weight;edg;Typedef struct int adjvex; int lowcost; closedge;4功能模块详细设计4.1 详细设计思想在该函数中主要有五段代码块，分别是主函数代码块、邻接矩阵模块代码、邻接表模块代码、最小生成树Prim算法及代价模块代码与最小生成树kruskal算法及代价模块代码，五段代码块分别有着不同的作用，共同满足了课程功能。在程序开头要对其进行内存空间分配，定义多个结构体数组和结构体链表，以便对分程序的进行。通过主函数调用菜单功能，然后通过菜单所对应的函数进行功能的实现。选择0菜单，实现对图的邻接矩阵输出。对于邻接矩阵，有权值的输出其值，没有连接的两个顶点输出最大值10000 ，用数组对其进行输出。选择1菜单实现对图的邻接表的输出。对于邻接表，对应位置后是其相连的顶点的存储位置。选择2菜单，实现用普里姆算法求最小生成树。该算法是从最小权值的边所对应的两个顶点开始的，依次将顶点放入集合U中，直至便利完毕。选择3菜单，是实现用克鲁斯卡尔算法求最小生成树。该算法是从第一个顶点开始一次找与其相连的权值最小的顶点。找完后，i加1，开始新的顶点的循环，直至所有点完毕。当选择n时，从系统菜单退出，完成整个程序实现的任务。执行main()函数switch(ch) ch=getche()ch=getche();，ch=getche();选择操作编号开始0邻接矩阵1邻接表 2普里姆算法3克鲁斯卡尔算法输入边和相应的权值4.2 核心代码#include #include #include #define int_max 10000#define inf 9999 #define max 20/邻接矩阵定义typedef struct ArcCell int adj; char *info;ArcCell,AdjMatrix2020;typedef struct char vexs20; AdjMatrix arcs; int vexnum,arcnum;MGraph_L;/int localvex(MGraph_L G,char v)/返回V的位置 int i=0; while(G.vexsi!=v) +i; return i;int creatMGraph_L(MGraph_L &G)/创建图用邻接矩阵表示 char v1,v2; int i,j,w; printf(创建无向图n); printf( 请输入图G顶点和弧的个数:(8 16)不包括(); scanf(%d%d,&G.vexnum,&G.arcnum); for(i=0;i!=G.vexnum;+i) printf(输入顶点%d,i); scanf(%s,&G.vexsi); for(i=0;i!=G.vexnum;+i) for(j=0;j!=G.vexnum;+j) G.arcsij.adj=int_max; G.=NULL; for(int k=0;k!=G.arcnum;+k) printf(输入一条边依附的顶点和权:(a b 3)不包括(); scanf(%s%s%d,&v1,&v2,&w); i=localvex(G,v1);/确定顶点V1和V2在图中的位置 j=localvex(G,v2); G.arcsij.adj=w; G.arcsji.adj=w; printf(图G邻接矩阵创建成功！n); return G.vexnum;void ljjzprint(MGraph_L G) int i,j; for(i=0;i!=G.vexnum;+i) for(j=0;j!=G.vexnum;+j) printf(%dt, G.arcsij); printf(n); int visitedmax;/访问标记int we;typedef struct arcnode/弧结点 int adjvex;/该弧指向的顶点的位置 struct arcnode *nextarc;/弧尾相同的下一条弧 char *info;/该弧信息arcnode;typedef struct vnode/邻接链表顶点头接点 char data;/结点信息 arcnode *firstarc;/指向第一条依附该结点的弧的指针vnode,adjlist;typedef struct/图的定义 adjlist verticesmax; int vexnum,arcnum; int kind;algraph;typedef struct acr int pre;/弧的一结点 int bak;/弧另一结点 int weight;/弧的权edg;int creatadj(algraph &gra,MGraph_L G)/用邻接表存储图 int i=0,j=0; arcnode *arc,*tem,*p; for(i=0;i!=G.vexnum;+i) gra.verticesi.data=G.vexsi; gra.verticesi.firstarc=NULL; for(i=0;i!=G.vexnum;+i) for(j=0;j!=G.vexnum;+j) if(gra.verticesi.firstarc=NULL) if(G.arcsij.adj!=int_max&j!=G.vexnum) arc=(arcnode *)malloc(sizeof(arcnode); arc-adjvex=j; gra.verticesi.firstarc=arc; arc-nextarc=NULL; p=arc; +j; while(G.arcsij.adj!=int_max&j!=G.vexnum) tem=(arcnode *)malloc(sizeof(arcnode); tem-adjvex=j; gra.verticesi.firstarc=tem; tem-nextarc=arc; arc=tem; +j; -j; else if(G.arcsij.adj!=int_max&j!=G.vexnum) arc=(arcnode *)malloc(sizeof(arcnode); arc-adjvex=j; p-nextarc=arc; arc-nextarc=NULL; p=arc; gra.vexnum=G.vexnum; gra.arcnum=G.arcnum; printf(图G邻接表创建成功！n); return 1;void adjprint(algraph gra) int i; for(i=0;i!=gra.vexnum;+i) arcnode *p; printf(%d,i); p=gra.verticesi.firstarc; while(p!=NULL) printf(%d,p-adjvex); p=p-nextarc; printf(n); int firstadjvex(algraph gra,vnode v)/返回依附顶点V的第一个点 /即以V为尾的第一个结点 if(v.firstarc!=NULL) return v.firstarc-adjvex;int nextadjvex(algraph gra,vnode v,int w)/返回依附顶点V的相对于W的下一个顶点 arcnode *p; p=v.firstarc; while(p!=NULL&p-adjvex!=w) p=p-nextarc; if(p-adjvex=w&p-nextarc!=NULL) p=p-nextarc; return p-adjvex; if(p-adjvex=w&p-nextarc=NULL) return -10; typedef struct int adjvex; int lowcost; closedge;int prim(int gmax,int n) /最小生成树PRIM算法 int lowcostmax,prevexmax; /LOWCOST存储当前集合U分别到剩余结点的最短路径 /prevex存储最短路径在U中的结点 int i,j,k,min; for(i=2;i=n;i+) /n个顶点，n-1条边 lowcosti=g1i; /初始化 prevexi=1; /顶点未加入到最小生成树中 lowcost1=0; /标志顶点1加入U集合 for(i=2;i=n;i+) /形成n-1条边的生成树 min=inf; k=0; for(j=2;j=n;j+) /寻找满足边的一个顶点在U,另一个顶点在V的最小边 if(lowcostjmin)&(lowcostj!=0) min=lowcostj; k=j; printf(%d,%d)%dt,prevexk,k,min); lowcostk=0; /顶点k加入U for(j=2;j=n;j+) /修改由顶点k到其他顶点边的权值 if(gkj0) f=acrvisitedf; return f;void kruscal_arc(MGraph_L G,algraph gra) edg edgs20; int i,j,k=0; for(i=0;i!=G.vexnum;+i) for(j=i;j!=G.vexnum;+j) if(G.arcsij.adj!=10000) edgsk.pre=i; edgsk.bak=j; edgsk.weight=G.arcsij.adj; +k; int x,y,m,n; int buf,edf; for(i=0;i!=gra.arcnum;+i) acrvisitedi=0; for(j=0;j!=G.arcnum;+j) m=10000; for(i=0;i!=G.arcnum;+i) if(edgsi.weightm) m=edgsi.weight; x=edgsi.pre; y=edgsi.bak; n=i; buf=find(acrvisited,x); edf=find(acrvisited,y); edgsn.weight=10000; if(buf!=edf) acrvisitedbuf=edf; printf(%d%d%d,x+1,y+1,m); printf(n); void main() algraph gra; MGraph_L G; int i,d,g2020; char a=a; d=creatMGraph_L(G); creatadj(gra,G); vnode v; printf(* - 菜单 - *n); printf(*0、显示该图的邻接矩阵*n); printf(*1、显示该图的邻接表 *n); printf(*2、最小生成树PRIM算法*n); printf(*3、最小生成树KRUSCAL算法*n); int s; char y=y; while(y=y) printf(请选择菜单：);