图的邻接矩阵存储结构建立.doc

课程名称: 数据结构课程设计课程设计题目:图的邻接矩阵存储 结构建立姓名:XXX院系:计算机学院专业:计算机科学技术 年级:11级学号:XXXXXXXX指导教师:XXX2013年9月28日目录1 课程设计的目的32需求分析33 课程设计报告内容 3 3.1 概要设计3 3.2 详细设计4 3.3 调试分析5 3.4 用户手册5 3.5 程序清单5 3.6 测试结果104 小结125 参考文献121.课程设计的目的(1) 熟练使用 C 语言编写程序，解决实际问题;(2) 了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力;(3) 初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能;(4) 提高综合运用所学的理论知识和方法独立分析和解决问题的能力;2.需求分析问题描述:建立图的邻接矩阵存储结构(图的类型可以是有向图或有向网、无向图或无向网，学生可以任选一种类型)，能够输入图的顶点和边的信息，并存储到相应存储结构中，而后给出图的 DFS,BFS次序。要求：先任意创建一个图；图的DFS,BFS的递归和非递归算法的实现。3.课程设计报告内容3.1概要设计 1.函数主函数：main( )创建无向图：CreateGraph( )深度优先遍历图：DFS( )广度优先遍历图：BFS( )3.2详细设计1.使用邻接矩阵作为图的存储结构，程序中主要用到的抽象数据类型：typedef struct char vexsMAX; /顶点向量 int arcsMAXMAX; /邻接矩阵 int vexnum,arcnum; /图的当前顶点数和弧数 Graph;2.程序流程图：主函数main( )创建无向图数据输入功能选择深度优先遍历退出程序广度优先遍历数据输出程序结束数据输出3.3调试分析程序的设计严格遵循结构化的程序设计思想，由简单到复杂，注意规范。在此次程序运行中，出现了很多的错误，开始的时候，不能很好的创建一个图，后来改进了算法，使得程序能够正确的运行。3.4用户手册进入程序后，您会看到以下提示：“无向图的创建及DFS和BFS的递归和非递归实现!”1.“创建无向图!”；2.“图的深度优先遍历!”；3.“图的广度优先遍历!”；4.“退出!”；请选择相应的数字键实现相应的功能。在执行图的遍历前必须先创建图，创建图时，按照系统的提示进行操作即可。3.5程序清单#include#include#define MAX 20int visitedMAX; /访问标志数组typedef struct char vexsMAX; /顶点向量int arcsMAXMAX; /邻接矩阵int vexnum,arcnum; /图的当前顶点数和边数Graph;typedef struct Qnodeint data;struct Qnode *next;Qnode,*Queueptr;typedef structQueueptr front;Queueptr rear; Linkqueue;void InitQueue(Linkqueue &Q)Q.front=Q.rear=(Queueptr)malloc(sizeof(Qnode);if(Q.front)Q.front-next=NULL;void EnQueue(Linkqueue &Q,int e) Queueptr p;p=(Queueptr)malloc(sizeof(Qnode);if(p)p-data=e;p-next=NULL;Q.rear-next=p;Q.rear=p;int DeQueue(Linkqueue &Q)int e;Queueptr p;if(Q.rear!=Q.front)p=Q.front-next; e=p-data; Q.front-next=p-next; if(Q.rear=p)Q.rear=Q.front; free(p);if(Q.front=p)Q.rear=Q.front;return e;int Locatevex(Graph G,char v) /返回元素v的位置 int i;for(i=0;iG.vexnum;i+) if(G.vexsi=v)return i; return -1; void CreateGraph(Graph &G)/创建无向图的邻接矩阵 int i,j,w,m,n; char a,b,c; printf(请输入图G的顶点数和弧数:); scanf(%d%d,&G.vexnum,&G.arcnum); getchar(); for(i=0;iG.vexnum;i+) visitedi=0;for(i=0;iG.vexnum;i+)printf(请输入第%d个顶点信息:,i+1); scanf(%c,&G.vexsi); getchar(); for(i=0;iG.vexnum;i+) for(j=0;jG.vexnum;j+) G.arcsij=0; for(i=0;iG.arcnum;i+) printf(请输入第%d条弧依附的两个顶点及权值: ,i+1); scanf(%c %c %d%c,&a,&b,&w,&c); m=Locatevex(G,a); n=Locatevex(G,b); G.arcsmn=w;G.arcsnm=w; void PrintMatrix(Graph G) /输出邻接矩阵int i,j;printf(n由图G生成的邻接矩阵如下:n);for(i=0;iG.vexnum;+i)for(j=0;j=0&vG.vexnum) for(i=0;i=0&i=0&jG.vexnum) for(k=j+1;k=0)if(!visitedu)DFS(G,u); u=NextAdVex(G,v,u);void BFS(Graph G)/广度非递归遍历 int i,w,k; Linkqueue Q; InitQueue(Q);for(i=0;iMAX;i+) visitedi=0; for(i=0;i=0;w=NextAdVex(G,k,w) if(!visitedw) visitedw=1; printf(%2c,G.vexsw); EnQueue(Q,w); int main()int m;Graph G;printf(无向图的创建及DFS和BFS的递归和非递归实现!nn);while(1)printf(1.创建无向图!n); printf(2.图的深度优先遍历!n); printf(3.图的广度优先遍历!n); printf(4.退出!n); printf(请选择功能:); scanf(%d,&m); if(m=1)CreateGraph(G); PrintMatrix(G); else if(m=2) printf(图G的深度递归优先遍历序列为:n); DFS(G,0); printf(n); else if(m=3) printf(图G的广度非递归优先遍历序列为:n); BFS(G); printf(n); else if(m=4) printf(成功退出!n); break; else printf(重新输入!n);return 0;3.6测试结果测试数据如下： ABCED深度优先遍历序列：A-B-D-C-E广度优先遍历序列：A-B-C-E-D（1）程序开始的界面。（2）创建无向图。(3)图的深度优先遍历。(4)图的广度优先遍历。4.小结在数