长江大学数据结构程序设计报告

算法与数据结构课程设计报告系（院）：计算机科学学院专业班级：计科11101 姓名：袁斌学号： 201103258 指导教师：周云才设计时间： 2013.6.17 - 2012.6.29一、设计目的... 错误！未定义书签。

二、设计任务及要求错误！未定义书签。

三、设计方案... 错误！未定义书签。

四、代码实现... 错误！未定义书签。

五、测试六、可改进的的地方七、难点与收获一．设计目的1．能根据实际问题的具体情况，结合数据结构课程中的基本理论和基本算法，分析并正确确定数据的逻辑结构，合理地选择相应的存储结构，并能设计出解决问题的有效算法。

2．提高程序设计和调试能力。

学生通过上机实习，验证自己设计的算法的正确性。

学会有效利用基本调试方法，迅速找出程序代码中的错误并且修改。

3．初步掌握软件开发过程中问题分析、系统设计、程序编码、测试等基本方法和技能。

4．训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。

5．培养根据选题需要选择学习书籍，查阅文献资料的自学能力。

二、设计任务：设计一个基于DOS菜单的应用程序。

要利用多级菜单实现各种功能。

内容如下：1．无向图的基本操作及应用①创建无向图的邻接矩阵②创建无向图的邻接表③无向图的深度优先遍历④无向图的广度优先遍历2．无向网的基本操作及应用①创建无向网的邻接矩阵②创建无向网的邻接表③求最小生成树3．有向图的基本操作及应用①创建有向图的邻接矩阵②创建有向图的邻接表③拓扑排序4．有向网的基本操作及应用①创建有向网的邻接矩阵②创建有向网的邻接表③关键路径④单源最短路径⑤每对顶点之间的最短路径三、设计方案DOS界面的主菜单void ShowMainMenu(){cout<<"\n";cout<<"*****************图的基本操作及应用****************\n";cout<<"* 1 无向图的基本操作及应用 *\n";cout<<"* 2 无向网的基本操作及应用 *\n";cout<<"* 3 有向图的基本操作及应用 *\n";cout<<"* 4 有向网的基本操作及应用 *\n";cout<<"* 5 退出 *\n";cout<<"***************************************************\n"; }void UDG1(){do{cout<<"\n";cout<<"****************无向图的基本操作及应用*************\n";cout<<"* 1 创建无向图的邻接矩阵 *\n";cout<<"* 2 创建无向图的邻接表 *\n";cout<<"* 3 无向图的深度优先遍历 *\n";cout<<"* 4 无向图的广度优先遍历 *\n";cout<<"* 5 退出 *\n";cout<<"***************************************************\n";cin>>n;switch(n){case 1:创建无向图的邻接矩阵break;case 2:创建无向图的邻接表break;case 3:无向图的深度优先遍历break;case 4:无向图的广度优先遍历break;default:if(n!=5)cout<<"错误,重新输入\n";}}while(n!=5);}void UDN1(){do{cout<<"\n";cout<<"***************无向网的基本操作及应用**************\n";cout<<"* 1 创建无向网的邻接矩阵 *\n";cout<<"* 2 创建无向网的邻接表 *\n";cout<<"* 3 最小生成树 *\n";cout<<"* 4 退出 *\n";cout<<"***************************************************\n";cin>>n;switch(n){case 1:创建无向网的邻接矩阵break;case 2:创建无向网的邻接表break;case 3:最小生成树break;default:if(n!=4)cout<<"错误，重新输入\n";}}while(n!=4);}void DG1(){do{cout<<"\n";cout<<"***************有向图的基本操作及应用**************\n";cout<<"* 1 创建有向图的邻接表 *\n";cout<<"* 2 创建有向图的邻接矩阵 *\n";cout<<"* 3 拓扑排序 *\n";cout<<"* 4 退出 *\n";cout<<"***************************************************\n";cin>>n;switch(n){case 1:创建有向图的邻接表break;case 2:创建有向图的邻接矩阵break;case 3:拓扑排序break;default:if(n!=4)cout<<"错误，重新输入\n";}}while(n!=4);}void DN1(){do{cout<<"\n";cout<<"***************有向网的基本操作及应用**************\n";cout<<"* 1 创建有向网的邻接矩阵 *\n";cout<<"* 2 创建有向网的邻接表 *\n";cout<<"* 3 关键路径 *\n";cout<<"* 4 单源最短路径 *\n";cout<<"* 5 每对顶点间的最短路径 *\n";cout<<"* 6 退出 *\n";cout<<"***************************************************\n";cin>>n;switch(n){case 1:创建有向网的邻接矩阵break;case 2:创建有向网的邻接表break;case 3:关键路径break;case 4:单源最短路径break;case 5:每对顶点间的最短路径print1(MK);break;default:if(n!=6)cout<<"错误，重新输入\n";}}while(n!=6);}void main(){int n;do{ShowMainMenu();cin>>n;switch(n){case 1:UDG1();break;case 2:UDN1();break;case 3:DG1();break;case 4:DN1();break;default:if(n!=5)cout<<"错误，重新输入";}}while(n!=5);}四、实现代码：#include<iostream>#include<stdlib.h>#include<iomanip>#include<stdio.h>#include<stack>using namespace std;#define MAX_VERTEX_NUM 100//最大顶点个数#define INFINITY 10000//最大值#define FALSE 0#define TRUE 1typedef int VRType; //顶点关系( 表示是否相邻)typedef char VertexType;typedef int InfoType;//弧相关信息typedef enum{DG,DN,UDG,UDN} GraphKind;//{有向图，有向网，无向图，无向网} typedef struct ArcCell{VRType adj;//权值InfoType *info;//该弧相关信息的指针}ArcCell,AdjMartix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];typedef struct{VertexType vexs[MAX_VERTEX_NUM]; //顶点向量AdjMartix arcs; //邻接矩阵int vexnum,arcnum; //图当前顶点数,弧数GraphKind Kind; //图的类型}MGraph;int LocateVex(MGraph G,VertexType v) //若图中存在v，返回v在图中的位置{for(int i=0;i<G.vexnum;i++){if(v==G.vexs[i])return i;}return -2;}//***********************创建无向网的邻接矩阵**********************int CreatMUDN(MGraph &G) //构造无向网{int i,j,w;char ch;VertexType v1,v2;cout<<"输入顶点数,弧数："<<endl;cin>>G.vexnum>>G.arcnum; //输入当前顶点数弧数是否有弧信息cout<<"输入顶点（字符型）："<<endl;for(i=0;i<G.vexnum;i++) //初始化邻接矩阵{for(j=0;j<G.vexnum;j++){G.arcs[i][j].adj=INFINITY;G.arcs[i][j].info=NULL;}}for(i=0;i<G.vexnum;i++) //顶点信息{cout<<"输入第"<<i+1<<"个顶点：";cin>>ch;G.vexs[i]=ch;}for(int k=0;k<G.arcnum;k++){cout<<"输入第"<<k+1<<"条弧："<<endl;cin>>v1>>v2;cout<<"输入弧的权值："<<endl;cin>>w;if((i=LocateVex(G,v1))!=-2)//if((j=LocateVex(G,v2))!=-2){G.arcs[i][j].adj=w;//对弧写入权值G.arcs[j][i].adj=w;//对称弧赋值}}return 1;}//***********************创建无向图的邻接矩阵********************** void CreatUDG(MGraph &G){int i,j,k;char ch;VertexType v1,v2;cout<<"输入顶点数,弧数："<<endl;cin>>G.vexnum >>G.arcnum;cout<<"输入顶点（字符型）："<<endl;for(i=0;i<G.vexnum;i++){for(j=0;j<G.vexnum;j++){G.arcs[i][j].adj=0;G.arcs[i][j].info=NULL;}}for(i=0;i<G.vexnum;i++) //顶点信息{cout<<"输入第"<<i+1<<"个顶点：";cin>>ch;G.vexs[i]=ch;}for(k=0;k<G.arcnum;k++){cout<<"输入第"<<k+1<<"条弧："<<endl;cin>>v1>>v2;if((i=LocateVex(G,v1))!=-2)//if((j=LocateVex(G,v2))!=-2){G.arcs[i][j].adj=1;//对弧写入权值G.arcs[j][i].adj=1;//对称弧赋值}}}//***********************显示邻接矩阵的信息********************** void ScanAll(MGraph G){int i;cout<<"图中顶点信息如下："<<endl;for(i=0;i<G.vexnum;i++)cout<<G.vexs[i]<<" ";cout<<"邻接矩阵如下："<<endl;cout<<setw(5)<<"矩阵：";for(i=0;i<G.vexnum;i++)cout<<setw(8)<<G.vexs[i];cout<<endl;for(i=0;i<G.vexnum;i++){cout<<setw(6)<<G.vexs[i];for(int j=0;j<G.vexnum;j++)cout<<setw(8)<<G.arcs[i][j].adj;cout<<endl;}}typedef struct ArcNode{int adjvex;//该弧指向顶点的位置struct ArcNode *nextarc;//指向下一条弧的指针InfoType *info;//该弧相关信息的指针}ArcNode;typedef struct VNode{VertexType data;//顶点信息ArcNode *firstarc;//指向第一条依附该顶点弧的指针}VNode,AdjList[MAX_VERTEX_NUM];typedef struct{AdjList vertices;int vexnum,arcnum;int kind;}ALGraph;//************************创建无向图的邻接表**************************void CreatALGUDG(ALGraph&G){int i,s,d;ArcNode *p,*q;cout<<"输入图的顶点数和边数:";cin>>G.vexnum >>G.arcnum ;for(i=1;i<=G.vexnum ;i++){cout<<"\n输入第"<<i<<"个顶点的信息:";cin>>G.vertices[i].data ;G.vertices [i].firstarc =NULL;}for(i=1;i<=G.arcnum ;i++){cout<<"\n输入第"<<i<<"条边的头结点和尾结点(整数):";cin>>s>>d;p=new ArcNode;p->adjvex =d;p->nextarc=G.vertices [s].firstarc ;G.vertices [s].firstarc =p;//将新建的以d为信息的表结点p插入s单链表的头结点后q=new ArcNode;q->adjvex =s;q->nextarc =G.vertices[d].firstarc ;G.vertices[d].firstarc =q;}G.kind =UDG;}//***********************输出邻接表**********************void PrintALGUDG(ALGraph G){ArcNode *p;int i;for(i=1;i<=G.vexnum;i++){p=G.vertices[i].firstarc ;cout<<G.vertices[i].data ;while(p!=NULL){cout<<"<"<<G.vertices[i].data <<","<<G.vertices[p->adjvex ].data <<">";p=p->nextarc;}printf("\n");}}//****************************无向图的深度遍历****************************** int visited[MAX_VERTEX_NUM];void DFS(ALGraph G,int v){ArcNode *p;cout<<G.vertices[v].data ;visited[v]=1;p=G.vertices[v].firstarc ;while(p!=NULL){if(visited[p->adjvex]==0)DFS(G,p->adjvex);p=p->nextarc;}}void DFSTraverse(ALGraph G){int v;for(v=1;v<=G.vexnum ;v++)visited[v]=0;for(v=1;v<=G.vexnum ;v++)if(visited[v]==0)DFS(G,v);}//****************************无向图的广度遍历****************************** int FirstAdjvex(ALGraph G,int v){ArcNode *p;if(p=G.vertices[v].firstarc )return p->adjvex ;return 0;}int NextAdjVex(ALGraph G,int v,int w){ArcNode *p;p=G.vertices[v].firstarc ;while(p->adjvex !=w)p=p->nextarc ;if(p->nextarc )return p->nextarc->adjvex ;elsereturn 0;}typedef struct Qnode{int data;struct Qnode *next;}Qnode;typedef struct{Qnode *front;Qnode *rear;}Linkqueue;int Initqueue(Linkqueue *Q){Q->front =(Qnode*)malloc(sizeof(Qnode));Q->rear =Q->front ;if(!Q->front )return 0;Q->front ->next =NULL;return 1;}int Enqueue(Linkqueue *Q,int *e){Qnode *p;p=(Qnode*)malloc(sizeof(Qnode));if(!p)return 0;p->data =*e;p->next =NULL;Q->rear ->next =p;Q->rear=p;return 1;}void Dequeue(Linkqueue *Q,int *e){Qnode *p;if(Q->front ==Q->rear )cout<<"空"<<endl;p=Q->front ->next ;*e=p->data ;Q->front ->next =p->next ;if(Q->rear ==p)Q->rear =Q->front ;free(p);}void BFSTraverse(ALGraph G){int v,w,u;for(v=1;v<=G.vexnum ;++v)visited[v]=0;Linkqueue Q;Initqueue(&Q);for(v=1;v<=G.vexnum ;v++)if(!visited[v]){visited[v]=1;cout<<G.vertices[v].data ;Enqueue(&Q,&v);while(Q.front !=Q.rear ){Dequeue(&Q,&u);for(w=FirstAdjvex(G,u);w>=1;w=NextAdjVex(G,u,w))if(!visited[w]){visited[w]=1;cout<<G.vertices[w].data ;Enqueue(&Q,&w);}}}}//*********************************最小生成树***************************void MiniSpanTree(MGraph G,VertexType u){int k;int j,i;int count=0,min;struct{VertexType adjvex;int lowcost;}closedge[ MAX_VERTEX_NUM];k=LocateVex(G,u);for(j=0;j<G.vexnum;j++)if(j!=k){closedge[j].adjvex=u;closedge[j].lowcost=G.arcs[k][j].adj;};closedge[k].lowcost=0;count=1;cout<<"最小生成树的各个边信息如下："<<endl;while(count!=G.vexnum){min=1000;for(i=0;i<G.vexnum;i++){if(closedge[i].lowcost==INFINITY||closedge[i].lowcost==0) continue;if(closedge[i].lowcost<min){min=closedge[i].lowcost;k=i;}}cout<<closedge[k].adjvex<<"-"<<G.vexs[k]<<":"<<closedge[k].lowcost<<endl;closedge[k].lowcost = 0; // 第k顶点并入U集count++;for (i=0; i<G.vexnum; ++i){if(closedge[i].lowcost==-1){closedge[i].adjvex = G.vexs[k];closedge[i].lowcost = G.arcs[k][i].adj;continue;}if(closedge[i].lowcost==0) continue;if (G.arcs[k][i].adj ==-1 ) continue;if(G.arcs[k][i].adj<closedge[i].lowcost){closedge[i].adjvex = G.vexs[k];closedge[i].lowcost = G.arcs[k][i].adj;continue;}}}}//***********************无向网邻接表的创建************************** void CreatALGUDN(ALGraph&G){int i,s,d,w;ArcNode *p,*q;cout<<"输入图的顶点数和边数:";cin>>G.vexnum >>G.arcnum ;for(i=1;i<=G.vexnum ;i++){cout<<"\n输入第"<<i<<"个顶点的信息:";cin>>G.vertices[i].data ;G.vertices [i].firstarc =NULL;}for(i=1;i<=G.arcnum ;i++){cout<<"\n输入第"<<i<<"条边的头结点,尾结点和权值:";cin>>s>>d>>w;p=new ArcNode;p->info =(InfoType*)malloc(sizeof(struct ArcNode));p->adjvex =d;*(p->info)=w;p->nextarc=G.vertices [s].firstarc ;G.vertices [s].firstarc =p;//将新建的以d为信息的表结点p插入s单链表的头结点后q=new ArcNode;q->info =(InfoType*)malloc(sizeof(struct ArcNode));q->adjvex =s;*(q->info)=w;q->nextarc =G.vertices[d].firstarc ;G.vertices[d].firstarc =q;}}//***********************无向网邻接表的输出**************************void PrintALGUDN(ALGraph G){ArcNode *p;int i;for(i=1;i<=G.vexnum;i++){p=G.vertices[i].firstarc ;cout<<G.vertices[i].data<<"--" ;while(p!=NULL){cout<<"<"<<G.vertices[i].data <<","<<G.vertices[p->adjvex ].data <<">"<<*(p->info)<<"--";p=p->nextarc;}printf("\n");}}//************************有向图的邻接矩阵******************************void CreatMDG(MGraph&G){int i,j,k;char ch;VertexType v1,v2;cout<<"输入顶点数,弧数："<<endl;cin>>G.vexnum >>G.arcnum;cout<<"输入顶点（字符型）："<<endl;for(i=0;i<G.vexnum;i++){for(j=0;j<G.vexnum;j++){G.arcs[i][j].adj=0;G.arcs[i][j].info=NULL;}}for(i=0;i<G.vexnum;i++) //顶点信息{cout<<"输入第"<<i+1<<"个顶点：";cin>>ch;G.vexs[i]=ch;}for(k=0;k<G.arcnum;k++){cout<<"输入第"<<k+1<<"条弧："<<endl;cin>>v1>>v2;if((i=LocateVex(G,v1))!=-2)//if((j=LocateVex(G,v2))!=-2){G.arcs[i][j].adj=1;//对弧写入权值//G.arcs[j][i].adj=1;//对称弧赋值}}}//******************************有向图的邻接表************************* void CreatALDG(ALGraph&G){int i,s,d;ArcNode *p;cout<<"输入图的顶点数和边数:";cin>>G.vexnum >>G.arcnum ;for(i=1;i<=G.vexnum ;i++){cout<<"\n输入第"<<i<<"个顶点的信息:";cin>>G.vertices[i].data ;G.vertices [i].firstarc =NULL;}for(i=1;i<=G.arcnum ;i++){cout<<"\n输入第"<<i<<"条边的头结点和尾结点(整数):";cin>>s>>d;p=new ArcNode;p->adjvex =d;p->nextarc=G.vertices [s].firstarc ;G.vertices [s].firstarc =p;//将新建的以d为信息的表结点p插入s单链表的头结点后/*q=new ArcNode;q->adjvex =s;q->nextarc =G.vertices[d].firstarc ;G.vertices[d].firstarc =q;*/}G.kind =UDG;}//****************************有向图的拓扑排序****************************** void FindDegree(ALGraph G,int indegree[]){int i;ArcNode *p;for(i=1;i<=G.vexnum ;i++)indegree[i]=0;for(i=1;i<=G.vexnum ;i++){p=G.vertices [i].firstarc ;while(p){indegree[p->adjvex]++;p=p->nextarc ;}}}int TopologicalSort(ALGraph G){int count,v,k;int *indegree=new int[G.vexnum ];for(int i=1;i<=G.vexnum;i++)indegree[i]=0;FindDegree(G,indegree);stack<int> S;for(int i=1;i<=G.vexnum ;i++)if(indegree[i]==0)S.push(i);count=0;while(!S.empty()){v=S.top();S.pop();cout<<v<<"-"<<G.vertices[v].data<<"\n" ;++count;for(ArcNode *p=G.vertices[v].firstarc ;p;p=p->nextarc ){k=p->adjvex ;if(!--indegree[k])S.push(k);}}if(count<G.vexnum ) return 0;else return 1;}//****************************创建有向网的邻接矩阵*****************************int CreatMUDG(MGraph &G){int i,j,w;char ch;VertexType v1,v2;cout<<"输入顶点数,弧数："<<endl;cin>>G.vexnum>>G.arcnum; //输入当前顶点数弧数是否有弧信息cout<<"输入顶点（字符型）："<<endl;for(i=0;i<G.vexnum;i++) //初始化邻接矩阵{for(j=0;j<G.vexnum;j++){G.arcs[i][j].adj=INFINITY;G.arcs[i][j].info=NULL;}}for(i=0;i<G.vexnum;i++) //顶点信息{cout<<"输入第"<<i+1<<"个顶点：";cin>>ch;G.vexs[i]=ch;}for(int k=0;k<G.arcnum;k++){cout<<"输入第"<<k+1<<"条弧："<<endl;cin>>v1>>v2;cout<<"输入弧的权值："<<endl;cin>>w;if((i=LocateVex(G,v1))!=-2)//if((j=LocateVex(G,v2))!=-2){G.arcs[i][j].adj=w;//对弧写入权值//G.arcs[j][i].adj=w;//对称弧赋值}}return 1;}//****************************创建有向网的邻接表***************************** void CreatALGUN(ALGraph&G){int i,s,d,w;ArcNode *p;cout<<"输入图的顶点数和边数:";cin>>G.vexnum >>G.arcnum ;for(i=1;i<=G.vexnum ;i++){cout<<"\n输入第"<<i<<"个顶点的信息:";cin>>G.vertices[i].data ;G.vertices [i].firstarc =NULL;}for(i=1;i<=G.arcnum ;i++){cout<<"\n输入第"<<i<<"条边的头结点,尾结点和权值:";cin>>s>>d>>w;p=new ArcNode;p->info =(InfoType*)malloc(sizeof(struct ArcNode));p->adjvex =d;*(p->info)=w;p->nextarc=G.vertices [s].firstarc ;G.vertices [s].firstarc =p;//将新建的以d为信息的表结点p插入s单链表的头结点后/* q=new ArcNode;q->info =(InfoType*)malloc(sizeof(struct ArcNode));q->adjvex =s;*(q->info)=w;q->nextarc =G.vertices[d].firstarc ;G.vertices[d].firstarc =q;*/}}//****************************迪杰斯特拉*****************************void ShortestPath(MGraph g,int v0,int p[][MAX_VERTEX_NUM],int d[]){int v;int w;int min;int i,j;int final[MAX_VERTEX_NUM];for (v = 0;v<g.vexnum;++v){final[v] = FALSE;d[v] = g.arcs[v0][v].adj ;for(w= 0;w<g.vexnum;++w){p[v][w]=FALSE;}if (d[v]<INFINITY){p[v][v0]=TRUE;p[v][v] =TRUE;}}d[v0]=0;final[v0]=TRUE;for (i=1;i<g.vexnum;++i){min=INFINITY;for (w=0;w<g.vexnum; ++w){if (!final[w]){if (d[w]<min){v=w;min=d[w];}}}final[v] = TRUE;for (w=0;w<g.vexnum;++w){if (!final[w] && (min+g.arcs[v][w].adj< d[w]) ){d[w] = min+g.arcs[v][w].adj;for (j=0;j<g.vexnum;j++){p[w][j] = p[v][j];}p[w][w]=TRUE;}}}}//****************************单源最短路径***************************** void print(MGraph G){int i,j;int p[MAX_VERTEX_NUM][MAX_VERTEX_NUM];int d[MAX_VERTEX_NUM];int v0=0;ShortestPath(G,v0,p,d);for(i=0;i<G.vexnum;i++){printf("Path%c to %c:\n",G.vexs[v0],G.vexs[i]);if(p[i][v0]=TRUE)for(j=0;j<G.vexnum;j++)printf("%d ",p[i][j]);printf("长度:%d\n",d[i]);printf("\n");}}void print1(MGraph G){int i,j;int p[MAX_VERTEX_NUM][MAX_VERTEX_NUM];int d[MAX_VERTEX_NUM];int v0;for(v0=0;v0<G.vexnum;v0++){ShortestPath(G,v0,p,d);for(i=0;i<G.vexnum;i++){printf("Path%c to %c:\n",G.vexs[v0],G.vexs[i]);if(p[i][v0]=TRUE)for(j=0;j<G.vexnum;j++)printf("%d ",p[i][j]);printf("长度:%d\n",d[i]);printf("\n");}}}//****************************关键路径*****************************int CriticalPath(ALGraph G)//??????????????????????????无法显示最后一个结点{//--------------------求ve-----------------------int *indegree=new int[G.vexnum ];for(int i=1;i<=G.vexnum ;++i)indegree[i]=0;//初始化FindDegree(G,indegree);//求各顶点入度stack<int> S,T;for(int i=1;i<=G.vexnum ;++i)if(indegree[i]==0)S.push (i);//入度为进栈int *ve=new int[G.vexnum ];for(int i=1;i<=G.vexnum ;++i)ve[i]=0;//初始化各顶点事件的最早发生时间while(!S.empty ()){int v=S.top();S.pop();T.push (v);for(ArcNode *p=G.vertices[v].firstarc ;p!=NULL;p=p->nextarc ){if(--indegree[p->adjvex ]==0)S.push (p->adjvex );//入度为进栈if(ve[v]+*(p->info) >ve[p->adjvex ])ve[p->adjvex ]=ve[v]+*(p->info) ;}}//-----------------------求v[l]--------------------------int *vl=new int[G.vexnum ];for(int i=1;i<=G.vexnum;++i){vl[i]=ve[G.vexnum];//初始化顶点事件的最迟发生时间}while(!T.empty ())//按拓扑逆序求各定点的vl值{int v=T.top();T.pop();for(ArcNode *p=G.vertices[v].firstarc ;p!=NULL;p=p->nextarc ){if(vl[p->adjvex ]-*(p->info) <vl[v])vl[v]=vl[p->adjvex ]-*(p->info) ;}}//------------------------判断是否是关键活动---------------------for(int i=1;i<=G.vexnum ;++i){for(ArcNode *p=G.vertices[i].firstarc;p;p=p->nextarc ){int k=p->adjvex;int dut=*(p->info );int e=ve[i];int l=vl[k]-dut;if(e==l)cout<<i<<"--"<<G.vertices[i].data<<"\n";}}return 0;}void ShowMainMenu(){cout<<"\n";cout<<"*****************图的基本操作及应用****************\n";cout<<"* 1 无向图的基本操作及应用 *\n";cout<<"* 2 无向网的基本操作及应用 *\n";cout<<"* 3 有向图的基本操作及应用 *\n";cout<<"* 4 有向网的基本操作及应用 *\n";cout<<"* 5 退出 *\n";cout<<"***************************************************\n";}void UDG1(){MGraph MG;ALGraph ALG;int n;do{cout<<"\n";cout<<"****************无向图的基本操作及应用*************\n";cout<<"* 1 创建无向图的邻接矩阵 *\n";cout<<"* 2 创建无向图的邻接表 *\n";cout<<"* 3 无向图的深度优先遍历 *\n";cout<<"* 4 无向图的广度优先遍历 *\n";cout<<"* 5 退出 *\n";cout<<"***************************************************\n";cin>>n;switch(n){case 1:CreatUDG(MG);ScanAll(MG);break;case 2:CreatALGUDG(ALG);PrintALGUDG(ALG);break;case 3:CreatALGUDG(ALG);PrintALGUDG(ALG);cout<<"深度优先遍历:"<<endl;DFSTraverse(ALG);break;case 4:CreatALGUDG(ALG);PrintALGUDG(ALG);cout<<"广度优先优先遍历："<<endl;BFSTraverse(ALG);break;default:if(n!=5)cout<<"错误,重新输入\n";}}while(n!=5);}void UDN1(){MGraph MN;ALGraph ALN;int n;VertexType u;do{cout<<"\n";cout<<"***************无向网的基本操作及应用**************\n";cout<<"* 1 创建无向网的邻接矩阵 *\n";cout<<"* 2 创建无向网的邻接表 *\n";cout<<"* 3 最小生成树 *\n";cout<<"* 4 退出 *\n";cout<<"***************************************************\n";cin>>n;switch(n){case 1:CreatMUDN(MN);ScanAll(MN);break;case 2:CreatALGUDN(ALN);PrintALGUDN(ALN);break;case 3:CreatMUDN(MN);ScanAll(MN);cin>>u;MiniSpanTree(MN,u);break;default:if(n!=4)cout<<"错误，重新输入\n";}}while(n!=4);}void DG1(){MGraph MH;ALGraph ALH;int n;do{cout<<"\n";cout<<"***************有向图的基本操作及应用**************\n";cout<<"* 1 创建有向图的邻接表 *\n";cout<<"* 2 创建有向图的邻接矩阵 *\n";cout<<"* 3 拓扑排序 *\n";cout<<"* 4 退出 *\n";cout<<"***************************************************\n";cin>>n;switch(n){case 1:CreatALDG(ALH);cout<<"邻接表为"<<endl;PrintALGUDG(ALH);break;case 2:CreatMDG(MH);ScanAll(MH);break;case 3:CreatALDG(ALH);cout<<"邻接表为"<<endl;PrintALGUDG(ALH);cout<<"拓扑排序:"<<endl;TopologicalSort(ALH);break;default:if(n!=4)cout<<"错误，重新输入\n";}}while(n!=4);}void DN1(){MGraph MK;ALGraph ALK;//int p[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//int d[MAX_VERTEX_NUM];//int v0=0;int n;do{cout<<"\n";cout<<"***************有向网的基本操作及应用**************\n";cout<<"* 1 创建有向网的邻接矩阵 *\n";cout<<"* 2 创建有向网的邻接表 *\n";cout<<"* 3 关键路径 *\n";cout<<"* 4 单源最短路径 *\n";cout<<"* 5 每对顶点间的最短路径 *\n";cout<<"* 6 退出 *\n";cout<<"***************************************************\n";cin>>n;switch(n){case 1:CreatMUDG(MK);ScanAll(MK);break;case 2:CreatALGUN(ALK);PrintALGUDN(ALK);break;case 3:CreatALGUN(ALK);PrintALGUDN(ALK);cout<<"关键路径为:"<<endl;CriticalPath(ALK);break;case 4:CreatMUDG(MK);ScanAll(MK);print(MK);break;case 5:CreatMUDG(MK);ScanAll(MK);print1(MK);break;default:if(n!=6)cout<<"错误，重新输入\n";}}while(n!=6);}void main(){int n;do{ShowMainMenu();cin>>n;switch(n){case 1:UDG1();break;case 2:UDN1();break;case 3:DG1();break;case 4:DN1();break;default:if(n!=5)cout<<"错误，重新输入";}}while(n!=5);}五、测试一无向图的基本操作及应用1、无向图邻接矩阵的创建2、无向图邻接表的创建3、深度优先遍历4、广度优先遍历二、无向网的基本操作及应用1、无向网邻接矩阵的创建2、无向网邻接表的创建2、最小生成树三、有向图的基本操作及应用1、有向图邻接表的创建2、有向图邻接矩阵的创建3、拓扑排序四、有向网的基本操作及应用1、有向网邻接矩阵的创建2、有向网邻接表的创建3、关键路径4、单源最短路径5、每对顶点之间的最短路径六、可改进的地方：1、关键路径的最后一个结点显示不出来，有待改进；2、迪杰斯特拉算法的程序，最短路径上的各个结点没有显示出来，创建的某些无向网还会出现乱码七、难点与收获：难点1：对指针的理解。