C++实践.doc

苏州科技学院二一 二一一学年第一学期电子信息工程学院课程设计报告书课程名称： 面向对象技术 班 级： 组 号： 组长姓名： 组成员姓名： 指导教师： 二一一年七月一 类设计class edgetype /定义含权边类protected:char v1; /两个结点char v2; float edgeweight; /权值public:friend graph; ;class graph /定义含权无向图类public:graph(); /构造函数 graph(graph&g); /拷贝构造函数 graph(); /析构函数 void addnode(char a); /添加结点 void delenode(char c); /删除结点 void addedge(char p,char q,float weight); /增加含权的边 void deledge(char c,char b); /删除含权的边，该边的权值以MAX表示 void printnodenum(); /求图中结点的个数 void printedgenum(); /求图中边的个数 void Ppath(int path,int i,int v); /前向递归查找路径上的顶点 void Dispath(float dist,int path,float s,int n,int v); /输出路径（以MAX表示两点重合的情况） void Dijkstra(int v); /用Dijkstra算法求单源最短路径 void build(); /建立图的邻接矩阵存储 void print(); /输出邻接矩阵 int locate(char v); /找顶点V在图中的位置 int find(int father,int v,int num); /找下标为v的结点的根父节点 void kruskal(int father); /kruskal算法求最小生成树 void open(); /从文件中读取数据void save(); /保存数据protected:int nodenum; /顶点数int arcnum; /边数char *vex; /顶点信息（动态） float *a; /邻接矩阵（动态） edgetype *edge; /边数组（动态）二 ;小组成员分工graph:graph() /构造函数 graph:graph(graph &g) /拷贝构造函数 graph:graph() /析构函数 void graph:addnode(char w) /添加结点 void graph:delenode(char c) /删除结点 void graph:addedge(char p,char q,float weight) /增加含权的边 void graph:deledge(char c,char b) /删除含权的边，该边的权值以MAX表示 void graph:printnodenum() /求图中结点的个数 void graph:printedgenum() /求图中边的个数 void graph:Ppath(int path,int i,int v) /前向递归查找路径上的顶点 void graph:Dispath(float dist,int path,float s,int n,int v) /输出路径（以MAX表示两点重合的情况） void graph:Dijkstra(int v) /用Dijkstra算法求单源最短路径 void graph:build() /建立图的邻接矩阵存储 void graph:print() /输出邻接矩阵 int graph:locate(char v) /找顶点V在图中的位置 int graph:find(int *father,int v,int num) /找下标为v的结点的根父节点 void graph:kruskal(int *father) /kruskal算法求最小生成树 void graph:save() /保存数据 void graph:open() /从文件中读取数据 void printname() / void menu() /菜单 int main() /main函数，验证(主)程序设计int main() graph g;int i,*father,v;float weight;char q,a,c;father=NULL;printname();menu();cini;while(i!=0)switch(i)case 1:g.build ();break;case 2:g.print ();break;case 3:printf(请输入你要添加的结点:);cina;g.addnode(a);break;case 4:printf(请输入你要删除的结点:);cinc;g.delenode(c);break;case 5:printf(请输入要增加的边的两个端点和该边的权值:n); cinacweight;g.addedge(a,c,weight);break;case 6:printf(请输入用两个端点表示你要删除的含权的边:); cinac;g.deledge(a,c);break;case 7:g.printnodenum();break;case 8:g.printedgenum();break;case 9:printf(请输入源点:);cinq;v=g.locate(q);g.Dijkstra(v);break;case 10:g.kruskal(father);break;case 11:g.save();break;case 12:g.open();break;menu(); cini;return 0; 三 类源程序代码class graph; /提前引用声明class edgetype /定义含权边类protected:char v1; /两个结点char v2; float edgeweight; /权值public:friend graph; ;class graph /定义含权无向图类public:graph(); /构造函数 graph(graph&g); /拷贝构造函数 graph(); /析构函数 void addnode(char a); /添加结点 void delenode(char c); /删除结点 void addedge(char p,char q,float weight); /增加含权的边 void deledge(char c,char b); /删除含权的边，该边的权值以MAX表示 void printnodenum(); /求图中结点的个数 void printedgenum(); /求图中边的个数 void Ppath(int path,int i,int v);/前向递归查找路径上的顶点 void Dispath(float dist,int path,float s,int n,int v);/输出路径（以MAX表示两点重合的情况） void Dijkstra(int v); /用Dijkstra算法求单源最短路径 void build(); /建立图的邻接矩阵存储 void print(); /输出邻接矩阵 int locate(char v);/找顶点V在图中的位置 int find(int father,int v,int num);/找下标为v的结点的根父节点 void kruskal(int father);/kruskal算法求最小生成树 void open(); /从文件中读取数据void save(); /保存数据protected:int nodenum; /顶点数int arcnum; /边数char *vex; /顶点信息（动态） float *a; /邻接矩阵（动态） edgetype *edge; /边数组（动态） ;graph:graph() /构造函数 vex=NULL;a=NULL;edge=NULL;arcnum=0;nodenum=0;graph:graph(graph &g) /拷贝构造函数 int i,j;arcnum=g.arcnum;nodenum=g.nodenum;vex=new charnodenum; a=new float*nodenum; for(i=0;inodenum;i+) ai=new floatnodenum;for(i=0;inodenum;i+)for(j=0;jnodenum;j+)aij=g.aij;for(i=0;inodenum;i+)vexi=g.vexi;edge=new edgetypearcnum;for(i=0;iarcnum;i+)edgei=g.edgei;graph:graph() /析构函数 delete vex;delete edge;delete a;/* Method Name: 无向图中包含结点类的对象* Discription: 可以在无向图中增加结点* Parameter:int i,c,j,k,b;* float weight,*a1;* char p,q,*vex1; * Return:None* Author: 柏雪,田晓霞,华丽娜* Date:2011/07/03* Version: V0.1*/void graph:addnode(char w) /添加结点 int i,c,j,k,b;float weight,*a1;char p,q,*vex1;edgetype *edge1;nodenum+;vex1=vex;vex=new charnodenum;for(i=0;inodenum-1;i+)vexi=vex1i;vexnodenum-1=w;a1=a;a=new float*nodenum;for(i=0;inodenum;i+)ai=new floatnodenum;for(i=0;inodenum-1;i+)for(j=0;jb;arcnum=arcnum+b;edge1=edge;edge=new edgetypearcnum;for(i=0;iarcnum-b;i+)edgei=edge1i;for(c=0;cnodenum;c+) acnodenum-1=MAX; anodenum-1c=MAX; for(i=0;ipqweight; for(c=0;cnodenum;c+) if(vexc=p) j=c; if(vexc=q) k=c; ajk=weight; akj=weight; /建立邻接矩阵 edgearcnum-b+i.v1=vexj; /建立弧数组 edgearcnum-b+i.v2=vexk; edgearcnum-b+i.edgeweight=weight; /* Method Name: 无向图中包含结点类的对象* Discription: 可以在无向图中删除结点* Parameter:int i,j,flag=0; * Return:None* Author: 柏雪,田晓霞,华丽娜* Date:2011/07/03* Version: V0.1*/void graph:delenode(char c) /删除结点 int i,j,flag=0;for(i=0;iarcnum;i+)if(edgei.v1=c|edgei.v2=c)edgei.edgeweight=MAX; /该边权值为MAX表示两点之间不连通或者两点重合 for(i=0;inodenum;i+)if(vexi=c)vexi=*; /以*表示改点已被删除j=i;flag=1;if(flag=0)printf(n该结点不存在!n);return;for(i=0;inodenum;i+)aji=MAX;aij=MAX;/* Method Name: 无向图中包含结点类的对象* Discription: 可以在无向图中增加含权的边* Parameter:int j,k,c,i;* Author: 柏雪,田晓霞,华丽娜* Date:2011/07/03* Version: V0.1*/void graph:addedge(char p,char q,float weight) /增加含权的边 int j,k,c,i; edgetype *edge1; arcnum+; edge1=edge; edge=new edgetypearcnum;for(i=0;iarcnum-1;i+)edgei=edge1i;for(c=0;cnodenum;c+) if(vexc=p) j=c; if(vexc=q) k=c; ajk=weight; akj=weight; /建立邻接矩阵 edgearcnum-1.v1=vexj; edgearcnum-1.v2=vexk; edgearcnum-1.edgeweight=weight; /* Method Name: 无向图中包含结点类的对象* Discription: 可以在无向图中删除含权的边* Parameter:int i,j,k,flag=0;* Return: None;* Author: 柏雪,田晓霞,华丽娜* Date:2011/07/03* Version: V0.1*/void graph:deledge(char c,char b) /删除含权的边，该边的权值以MAX表示 int i,j,k,flag=0;for(i=0;iarcnum;i+) if(edgei.v1=c&edgei.v2=b)|(edgei.v1=b&edgei.v2=c) edgei.edgeweight=MAX; flag=1; if(flag=0) printf(n该边不存在!n); return; for(i=0;inodenum;i+) if(vexi=c) j=i; if(vexi=b) k=i; ajk=MAX; akj=MAX; /* Method Name: 无向图中包含结点类的对象* Discription: 可以在无向图中求图中结点的个数* Parameter:int i,num=0; * Author: 柏雪,田晓霞,华丽娜* Date:2011/07/03* Version: V0.1*/void graph:printnodenum() /求图中结点的个数 int i,num=0; for(i=0;inodenum;i+) if(vexi!=*) num+; printf(图中结点的个数为:%d,num);printf( 结点分别为:);for(i=0;inodenum;i+)if(vexi!=*)printf(%c ,vexi); /* Method Name: 无向图中包含结点类的对象* Discription: 可以在无向图中求图中边的个数* Parameter:int i,j,num=0; * Author: 柏雪,田晓霞,华丽娜* Date:2011/07/03* Version: V0.1*/void graph:printedgenum() /求图中边的个数 int i,j,num=0;for(i=0;inodenum;i+)for(j=0;jnodenum;j+)if(aij!=MAX)num+;printf(图中边的个数为:%d,num/2);/* Method Name: 无向图中包含结点类的对象* Discription:前向递归查找路径上的顶点 * Parameter:int k; * Return:None;* Author: 柏雪,田晓霞,华丽娜* Date:2011/07/03* Version: V0.1*/void graph:Ppath(int path,int i,int v)/前向递归查找路径上的顶点 int k; k=pathi; if(k=v) return; /找到了起点则返回Ppath(path,k,v); /找顶点k的前一个顶点printf(%c,vexk); /输出顶点k/* Method Name: 无向图中包含结点类的对象* Discription:输出路径* Parameter:int i; * Author: 柏雪,田晓霞,华丽娜* Date:2011/07/03* Version: V0.1*/void graph:Dispath(float dist,int path,float s,int n,int v) /输出路径（以MAX表示两点重合的情况） int i;for(i=0;in;i+)if(si=1)if(v!=i)printf(从%c到%c的最短路径长度为:%f 路径为:,vexv,vexi,disti);printf(%c,vexv); /输出路径上的起点Ppath(path,i,v); /输出路径上的中间点printf(%cn,vexi); /输出路径上的终点else if(vexi!=*)printf(从%c到%c不存在路径n,vexv,vexi);delete dist;delete path; delete s;/* Method Name: 无向图中包含结点类的对象* Discription:用Dijkstra算法求单源最短路径即在无向图中查找两结点间的最小连通边 * Parameter:float *s,*dist,mindis;* int *path;* int i,j,u; * Author: 柏雪,田晓霞,华丽娜* Date:2011/07/03* Version: V0.1*/void graph:Dijkstra(int v) /用Dijkstra算法求单源最短路径 float *s,*dist,mindis;int *path;int i,j,u;s=new floatnodenum;dist=new floatnodenum;path=new intnodenum;for(i=0;inodenum;i+) /分别对distN，pathN，和sN初始化disti=avi; /距离初始化si=0; /s置空if(aviMAX) /路径初始化pathi=v;elsepathi=-1;sv=1;pathv=0; /源点编号v放入s中for(i=0;inodenum;i+) /循环直到所有顶点的最短路径都求出mindis=MAX; /mindis置最小长度初值for(j=0;jnodenum;j+) /选取不在s中具有最小距离的顶点uif(sj=0&distjmindis)u=j;mindis=distj;su=1; /顶点u加入s中for(j=0;jnodenum;j+) /修改不在s中的顶点的距离if(sj=0)if(aujMAX&distu+aujdistj)distj=distu+auj;pathj=u;Dispath(dist,path,s,nodenum,v); /输出最短路径/* Method Name: 无向图中包含结点类的对象* Discription:建立图的邻接矩阵存储及邻接距阵的初始化* Parameter: int j,k,i;* float weight;* char p,q;* int c;* Author: 柏雪,田晓霞,华丽娜* Date:2011/07/03* Version: V0.1*/void graph:build() /建立图的邻接矩阵存储 int j,k,i; float weight; char p,q; int c; printf(请输入结点的个数:); scanf(%d,&nodenum); vex=new charnodenum; a=new float*nodenum; for(i=0;inodenum;i+) ai=new floatnodenum; printf(请输入各个结点: ); scanf(%c,&vex0); for(i=0;inodenum;i+) scanf(%c,&vexi); for(i=0;inodenum;i+) for(j=0;jnodenum;j+) /邻接矩阵初始化 aij=MAX; printf(请输入边的个数:); scanf(%d,&arcnum); edge=new edgetypearcnum; for(i=0;ipqweight; for(c=0;cnodenum;c+) if(vexc=p) j=c; if(vexc=q) k=c; ajk=weight;akj=weight; /建立邻接矩阵 edgei.v1=vexj; edgei.v2=vexk; edgei.edgeweight=weight; /建立弧数组 /* Method Name: 无向图中包含结点类的对象* Discription:输出邻接矩阵 * Parameter: int i,j;* int k;* int t;* Return: return k;* return -1;* return (t);* Author: 柏雪,田晓霞,华丽娜* Date:2011/07/03* Version: V0.1*/ void graph:print() /输出邻接矩阵 int i,j; printf(n邻接矩阵为n); printf( ); for(i=0;inodenum;i+) printf(%8c,vexi); printf(n); printf(n); for(i=0;inodenum;i+) printf(%5c ,vexi); for(j=0;jnodenum;j+) coutaijt; coutendl; coutendl; int graph:locate(char v) /找顶点V在图中的位置 int k; for(k=0;k=0 & tnum)t=fathert; return (t); /* Method Name: 无向图中包含结点类的对象* Discription: kruskal算法求最小生成树 * Parameter: int vf1;* int vf2,i,j,k,flag=0;* Author: 柏雪,田晓霞,华丽娜* Date:2011/07/03* Version: V0.1*/ void graph:kruskal(int *father) /kruskal算法求最小生成树 edgetype temp; int vf1; int vf2,i,j,k,flag=0; father=new intnodenum; for(i=0;iarcnum;i+) /对所有的弧按权值大小进行排序 k=i; for(j=i+1;jarcnum;j+) if(edgej.edgeweightedgek.edgeweight) k=j; if(k!=i) temp=edgei; edgei=edgek; edgek=temp; for(i=0;inodenum;i+) fatheri=-1; /作标记，fatheri=-1 表示i点没有父结点 printf(n最小生成树为:n); i=0;j=0; while(iarcnum & jnodenum-1) /在所有的边中找n-1条进入最小生成树，从第一条边开始试起，不能构成回路 vf1=find(father,locate(edgei.v1),nodenum); vf2=find(father,locate(edgei.v2),nodenum); if(vf1!=vf2) fathervf2=vf1; j+; /i边进入最小生成树 if(edgei.edgeweight!=MAX) printf(第%d条边为:(%c,%c) 该边的权值为:%fn,flag,edgei.v1,edgei.v2,edgei.edgeweight);/输出最小生成树中的边 flag+; i+; /* Method Name: 无向图中包含结点类的对象* Discription: 保存数据 * Parameter: int i,j;* Author: 柏雪,田晓霞,华丽娜* Date:2011/07/03* Version: V0.1*/ void graph:save() /保存数据 FILE *fp; int i,j; if(fp=fopen(d:data.txt,w)=NULL) cout不能打开文件n; exit(0); else fprintf(fp,%d,nodenum); for(i=0;inodenum;i+) fprintf(fp,%c,vexi); fprintf(fp,%dn,arcnum); for(i=0;inodenum;i+) for(j=0;jnodenum;j+) fprintf(fp,%fn,aij);for(i=0;iarcnum;i+)fprintf(fp,%c%c%fn,edgei.v1,edgei.v2,edgei.edgeweight); fclose(fp); /* Method Name: 无向图中包含结点类的对象* Discription:从文件中读取数据 * Parameter: int i,j; * Author: 柏雪,田晓霞,华丽娜* Date:2011/07/03* Version: V0.1*/void graph:open() /从文件中读取数据 FILE *fp; int i,j; if(fp=fopen(d:data.txt,r)=NULL) cout不能打开文件n; exit(0); else fscanf(fp,%d,&nodenum); vex=new charnodenum; a=new float*nodenum; for(i=0;inodenum;i+) ai=new floatnodenum; for(i=0;inodenum;i+) fscanf(fp,%c,&vexi); fscanf(fp,%dn,&arcnum); edge=new edgetypearcnum; for(i=0;inodenum;i+) for(j=0;jnodenum;j+) fscanf(fp,%fn,&aij);for(i=0;iarcnum;i+)fscanf(fp,%c%c%fn,&edgei.v1,&edgei.v2,&edgei.edgeweight); fclose(fp);/* Method Name: 无向图中包含结点类的对象* Discription:菜单 * Author: 柏雪,田晓霞,华丽娜* Date:2011/07/03* Version: V0.1*/void printname() printf(n *n);void menu() /菜单 printf(n);printf( *含权边类与含权无向图类*nn);printf( 01.-建立图的邻接矩阵存储- 02.-输出邻接矩阵-nn);printf( 03.-添加结点- 04.-删除结点-nn);printf( 05.-增加含权的边- 06.-删除含权的边-nn);printf( 07.-求图中结点的个数- 08.-求图中边的个数-nn);printf( 09.-用Dijkstra算法求单源最短路径-