数据结构矩阵处理

1算法与数据结构课程设计班级:姓名:指导老师：2015年6月22~2015年7月3日2目录1．设计方案…………………………………….32．实现过程……………………………………33．测试…………………………………………34．使用说明…………………………………….135．难点与收获…………………………………..136．实现代码……………………………………….137．可改进的地方………………………………..253一．设计方案能根据实际问题的具体情况，结合数据结构课程中的基本理论和基本算法，选择相应的存储结构，设计出解决问题的有效算法，实现图的一些基本操作，此次设计主要需要解决对无向图，无向网，有向图，有向网的一些基本操作和应用，因此可以设计一个基于VC或VS的应用程序，数据可以从键盘输入，然后设计程序利用多级菜单实现各种功能。二．实现过程实现过程的主函数为：voidmain()1．对无向图的基本操作及应用的实现①创建无向图的邻接矩阵（voidcreat_mg(MgraphG)）②创建无向图的邻接表（voidCreatAdjList(Graph*G)）③无向图的深度优先遍历（voidDFS(Graph*G,inti,intvisited[])）④无向图的广度优先遍历（voidBFS(Graph*G,intv,intvisited[])）2．对无向网的基本操作及应用的实现①创建无向网的邻接矩阵（CreateNDNGraphics(Graphics&G)）②创建无向网的邻接表（CreateUDN(ALGraph&G)）③求最小生成树（Prim(intgraph[][MAX],intn)）3．对有向图的基本操作及应用的实现①创建有向图的邻接矩阵（CreateDGraphics(Graphics&G)）②创建有向图的邻接表（CreateDG(ALGraph&G)）③拓扑排序（TopSort(Graphaa&g)）4．对有向网的基本操作及应用的实现①创建有向网的邻接矩阵（CreateDNGraphics(Graphics&G)）②创建有向网的邻接表（CreateUDN(ALGraphh&G,indegreeindegree)）③关键路径（CriticalPath(ALGraphh&g,indegreeindegree)）④单源最短路径（myDijstra(n,1)）三．测试数据输入：从键盘输入操作对应的序号1.最初入口界面42.无向图：无向图的邻接矩阵：5无向图的邻接表：无向图的深度优先遍历：6无向图的广度优先遍历：73.无向网的基本操作及应用无向网的邻接矩阵：无向网的邻接表：8最小生成树：94.有向图的基本操作及应用创建有向图的邻接矩阵：创建有向图的连接表10有向图的拓扑排序;5.有向网的基本操作及应用有向网的邻接矩阵：11创建有向网的邻接表;12有向网的关键路径：4.单源顶点路径最短问题：13四．使用说明总共有三级选择菜单，根据需要从键盘输入对应菜单序号，进入相应输入界面，输入待测数据，对图或网进行相应的操作五．难点与收获用代码实现各种操作时，代码容易出现逻辑上的错，个人觉得这种错误易发现但比较难修改，比如，在实现图的深度优先遍历时，利用了递归函数（DFS(G,i,visited)），通过查找资料和看书，多次调试，在程序中实现调用，实现了对图的深度优先遍历。这次通过上机实习，我更加深入的学习了图和网的相关内容和掌握了图和网的一些基本操作，也学会有效利用基本调试方法，会找出程序代码中的错误并且修改，提高了自己发现问题和解决问题的能力，受益匪浅。六．实现代码无向图：//=================创建无向图（邻接表）===================//voidCreatAdjList(Graph*G){inti,j,k;edgenode*p1;edgenode*p2;cout请输入无向图的顶点数和边数(如：21):endl;cinG-vexnumG-arcnum;coutendl;cout开始输入顶点表（如：12）endl;for(i=1;i=G-vexnum;i++){14cinG-adjlists[i].vertex;G-adjlists[i].edgelink=NULL;}coutendl;cout开始输入边表信息:endl;coutendl;for(k=1;k=G-arcnum;k++){cout请输入边Vi,Vj对应的顶点序号（如：23）:;cinij;coutendl;p1=newedgenode;p1-endver=j;p1-edgenext=G-adjlists[i].edgelink;G-adjlists[i].edgelink=p1;p2=newedgenode;p2-endver=i;p2-edgenext=G-adjlists[j].edgelink;G-adjlists[j].edgelink=p2;//因为是无向图，所以有两次建立边表的过程}}voidcreat_mg(MgraphG){inti,j,k;printf(\n请输入无向图的顶点数和边数，如(6,5)每次回车键输入：);scanf(%d,%d,&n,&e);for(i=1;i=n;i++)for(j=1;j=n;j++)G[i][j]=0;//将邻接矩阵初始化for(k=1;k=e;k++){printf(\n请输入每条边的两个顶点编号，如(2,5)每次回车键输入:);scanf(%d,%d,&i,&j);G[i][j]=1;G[j][i]=1;}inta,b;for(a=1;a=n;a++){15printf(\n);for(b=1;b=n;b++)printf(%5d,G[a][b]);}printf(\n);}//----------------------------------广度优先遍历--------------------------------//voidBFS(Graph*G,intv,intvisited[]){//从第v个顶点出发非递归地广度优先搜索遍历无向图G。QueueList*Q=newQueueList;Q-front=Q-rear=NULL;//初始化队列QEnQueue(Q,v);//V入队列while(Q-rear!=NULL){inte;DeQueue(Q,&e);//队头(指定的)元素出队并置值为ecoutG-adjlists[e].vertex;//输出顶点信息visited[e]=1;edgenode*p=newedgenode;p=G-adjlists[e].edgelink;//指向第一条依附于该顶点的边的指针if(p){intm=p-endver;//该边所指向的顶点的位置if(m==0){EnQueue(Q,m);while(visited[m]==0){p=p-edgenext;if(p==NULL)break;m=p-endver;EnQueue(Q,m);}}}16}}有向网，无向网，无向图的邻接矩阵构造;intCreateDGraphics(Graphics&G){//构造一个有向图printf(分别输入弧数、顶点数（用空格）:);Infoinfo=NULL;//这里忽略info信息scanf(%d%d,&G.arcnum,&G.vexnum);//先把邻接矩阵中的adj设置为0for(inti=0;iG.vexnum;++i){for(intj=0;jG.vexnum;++j){G.arc[i][j].adj=0;}}//扫描进入顶点元素for(i=0;iG.vexnum;++i){printf(请依次输入顶点元素值:\n);scanf(%d,&G.vexs[i]);}printf(输入完毕!\n);//输入弧信息for(i=0;iG.arcnum;++i){printf(请输入具有邻接关系的顶点:\n);DataTyped1,d2;scanf(%d%d,&d1,&d2);intp1=LocateVex(G,d1);intp2=LocateVex(G,d2);G.arc[p1][p2].adj=1;}printf(该有向图的邻接矩阵构造完毕);return1;}//CreateDGraphicsintCreateNDNGraphics(Graphics&G){//构造一个无向网printf(分别输入弧数、顶点数（用空格）:\n);Infoinfo=NULL;//这里忽略info信息scanf(%d%d,&G.arcnum,&G.vexnum);//先把邻接矩阵中的adj设置为0for(inti=0;iG.vexnum;++i){for(intj=0;jG.vexnum;++j){G.arc[i][j].adj=0;//借用改值为最大值17}}//扫描进入顶点元素for(i=0;iG.vexnum;++i){printf(请依次输入顶点元素值:\n);scanf(%d,&G.vexs[i]);}printf(输入完毕!\n);//输入弧信息for(i=0;iG.arcnum;++i){printf(请输入具有邻接关系的顶点,以及他们的权重（如213）:\n);DataTyped1,d2,d3;scanf(%d%d%d,&d1,&d2,&d3);intp1=LocateVex(G,d1);intp2=LocateVex(G,d2);G.arc[p1][p2].adj=d3;//因为是无向，所以对称设置G.arc[p2][p1].adj=d3;}printf(该无向网的邻接矩阵构造完毕);return1;}//CreateNDNGraphicsintCreateDNGraphics(Graphics&G){//构造一个有向网printf(分别输入弧数、顶点数（用空格）:\n);Infoinfo=NULL;//这里忽略info信息scanf(%d%d,&G.arcnum,&G.vexnum);//先把邻接矩阵中的adj设置为0for(inti=0;iG.vexnum;++i){for(intj=0;jG.vexnum;++j){G.arc[i][j].adj=0;//借用改值为最大值}}//扫描进入顶点元素for(i=0;iG.vexnum;++i){printf(请依次输入顶点元素值:\n);scanf(%d,&G.vexs[i]);}printf(输入完毕);//输入弧信息for(i=0;iG.arcnum;++i){printf(请输入具有邻接关系的顶点,以及他们的权重:\n);DataTyped1,d2,d3;18scanf(%d%d%d,&d1,&d2,&d3);intp1=LocateVex(G,d1);intp2=LocateVex(G,d2);G.arc[p1][p2].adj=d3;}printf(该有向网的邻接矩阵构造完毕);return1;}//CreateDNGraphics//邻接表建立无向网intCreateUDN(ALGraph&G)/*邻接表建立无向网*/{inti,s,d,w;ArcNode*p,*q;printf(输入结点数目和边数（用空格）:);scanf(%d%d,&G.vexnum,&G.arcnum);/*输入结点数目和边数*/getchar();for(i=1;i=G.vexnum;i++)/*输入顶点*/{printf(输入顶点（每一个按回车键):);scanf(%c,&G.vertices[i].data);/*输入顶点*/getchar();G.vertices[i].firstarc=NULL;/*首先初始化为NULL*/}for(i=1;i=G.arcnum;i++){printf(依次输入每条边依附的顶点序号，权值（空格/每一个按回车键):);scanf(