数据结构课程设计.ppt.doc

山东建筑大学计算机学院课程设计说明书目 录课程设计任务书I图的创建及相关操作的实现3一、问题描述3二、数据结构3三、逻辑设计3四、编码3五、测试数据3六、测试情况3结 论4参考文献5课程设计指导教师评语6I山东建筑大学计算机学院课程设计说明书山东建筑大学计算机科学与技术学院课程设计任务书设计题目图的创建及相关操作的实现已知技术参数和设计要求对任意给定的图（顶点数不小于20，边数不少于30，图的类型可以是有向图、无向图、有向网、无向网），能够输入图的顶点和边（或弧）的信息，并存储到相应存储结构（邻接矩阵、邻接表、十字链表、邻接多重表，任选其中两种类型），对自己所创建的图完成以下操作：1、 对无向图求每个顶点的度，或对有向图求每个顶点的入度和出度（5分）2、 完成插入顶点和边（或弧）的功能（5分）3、 完成删除顶点和边（或弧）的功能（5分）4、 两种存储结构的转换（5分），如果其中一种存储结构为十字链表或邻接多重表则增加5分。5、 输出图的深度优先遍历序列或广度优先遍历序列（5分）6、 求图的深度优先或广度优先的生成树（或生成森林）（存储结构为孩子-兄弟链表），并对生成树进行遍历（15分）7、 判断图的连通性，输出连通分量的个数（5分）8、 判断图中是否存在环，无向图5分，有向图10分9、 给出顶点u和v，判断u到v是否存在路径（5分）10、求顶点u到v的一条简单路径（10分）11、求顶点u到v的所有简单路径（15分）12、求顶点u到v的最短路径（10分）13、求顶点u到其余各顶点的最短路径（15分）14、求任两个顶点之间的最短路径（15分）15、求最小生成树（15分）16、对于有一个源点和一个汇点的有向网，求关键路径（20分）设计内容与步骤1、 设计存储结构2、 设计算法3、 编写程序，进行调试4、 总结并进行演示、讲解设计工作计划与进度安排根据自己选作的题目，给出完成每项工作的时间表，包括起止时间、工作内容、地点设计考核要求1、 考勤20%2、 课程设计说明书50%3、 成果展示30%指导教师（签字）： 教研室主任（签字）31计算机学院课程设计说明书图的创建及相关操作的实现一、问题描述用图示的方法描述所处理的图的形态二、数据结构针对所处理的图：1、 画出2种存储结构邻接表： 邻接矩阵： 23 26 16 13 10 10 11 35 45 22 63 46 17 31 42 19 23 14 19 24 6 4 36 37 21 24 60 3 34 19 2、 使用所选用语言的功能，实现上述的2种存储结构邻接表：typedef struct ArcNode int weight; int adjvex; / 该弧所指向的顶点的位置 struct ArcNode *nextarc; / 指向下一条弧的指针 InfoType *info; / 该弧相关信息的指针2、 使用所选用语言的功能，实现上述的2种存储结构邻接表：typedef struct ArcNode int weight; int adjvex; / 该弧所指向的顶点的位置 struct ArcNode *nextarc; / 指向下一条弧的指针 InfoType *info; / 该弧相关信息的指针ArcNode;typedef struct VNode VertexType data; / 顶点信息 ArcNode *firstarc; / 指向第一条依附该顶点的弧VNode, AdjListMAX_VERTEX_NUM;typedef struct AdjList vertices; int vexnum, arcnum; / 图的当前顶点数和弧数 GraphKind kind; / 图的种类标志ALGraph; 邻接矩阵：typedef struct ArcCell VRType adj; / VRType是顶点关系类型。对无权图，用1或0表示相邻否； / 对带权图，则为权值类型。 InfoType *info; / 该弧相关信息的指针ArcCell, AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;typedef struct VertexType vexsMAX_VERTEX_NUM; / 顶点向量 AdjMatrix arcs; / 邻接矩阵 int vexnum, arcnum; / 图的当前顶点数和弧数 GraphKind kind; / 图的种类标志MGraph;三、逻辑设计1、总体思路根据设计题目的要求，充分地分析和理解问题，对问题描述中涉及的操作对象定义相应的数据类型，并按照以数据结构为中心的原则划分模块，定义主程序模块和各抽象数据类型。然后定义相应的存储结构并写出各函数的伪代码算法。综合考虑系统功能，使得系统结构清晰、合理、简单和易于调试， 程序编码时同时加入一些注解和断言，使程序中逻辑概念清楚。掌握调试工具的各种功能，设计测试数据确定疑点，通过修改程序来证实它或绕过它。调试正确后，整理源程序及其注释，形成格式和风格良好的源程序清单和结果。2、模块划分（以图示的方法给出各个函数的调用关系）选项函数1:创建有向图的邻接表CreateADG(a); printGra(a);2:创建有向图的邻接矩阵createMDG(m);3:显示已创建的有向图的邻接矩阵PrintMGraph(m);4:显示已创建的有向图的邻接表PrintADG(a);5:求每个顶点的入度，出度printGra(a); degree(a);6:深度优先遍历有向图,并判断其连通性printGra(a); DFSTraverse(a);7:在有向图中插入弧GraphAdd(a); printGra(a);8:在有向图中删除弧GraphDel(a); printGra(a);9:在有向图中插入顶点NodeAdd(a); printGra(a);10:在有向图中删除顶点NodeDel(a); printGra(a);11:邻接矩阵转换成邻接表TranlateDG(m,a); printGra(a);12:邻接表转换成邻接矩阵TranlateAl(a,m); printMg(m);13:有向图深度优先生成树，并进行遍历printGra(a); DFSforest(a,T);14:判断有向图中是否存在环printGra(a); ToplogicalSort(a);15:两顶点是否存在路径，存在时输出一条简单路径printGra(a); exist_path(a);16:某顶点到其他顶点的最短路径InitStack(s); printGra(a); locateALG(a,c); ShortestPath_DIJ(a,m); printPath(a,m);17:任两点间的最短路径printGra(a); AllShortestPath(a);3、 函数或类的具体定义和功能1) CreateADG(a): 创建有向图的邻接表。2) printGra(a): 输出图的信息。3) createMDG(m): 创建有向图的邻接矩阵。4) PrintMGraph(m): 显示已创建的有向图的邻接矩阵。5) PrintADG(a): 显示已创建的有向图的邻接表。6) degree(a): 求每个顶点的入度，出度。7) DFSTraverse(a): 深度优先遍历有向图,并判断其连通性。8) GraphAdd(a): 在有向图中插入弧。9) GraphDel(a): 在有向图中删除弧。10) NodeAdd(a): 在有向图中插入顶点。11) NodeDel(a): 在有向图中删除顶点。12) TranlateDG(m,a): 邻接矩阵转换成邻接表。13) TranlateAl(a,m): 邻接表转换成邻接矩阵。14) printMg(m):输出邻接矩阵的图的信息。15) DFSforest(a,T): 有向图深度优先生成树，并进行遍历。16) ToplogicalSort(a): 判断有向图中是否存在环。17) exist_path(a):顶点是否存在路径，存在时输出一条简单路径18) InitStack(s):初始化栈。19) locateALG(a,c): 元素在图中的位置。20) ShortestPath_DIJ(a,m): 某顶点到其他顶点的最短路径。21) printPath(a,m):输出路径。22) AllShortestPath(a): 任两点间的最短路径。四、编码给出具体的程序代码1) 四、编码#include stdio.h#include math.h#includemalloc.h#include stack#include #define OK 1#define ERROR -1#define MAX 32764 / 最大值/#define MaxLen 1000 #define STACK_INIT_SIZE 100#define STACKINCREMENT 10#define MAX_VERTEX_NUM 50 / 最大顶点个数typedef enum DG, DN, AG, AN GraphKind; /有向图,有向网,无向图,无向网typedef int status;typedef int VRType;typedef int InfoType;typedef char VertexType;typedef char TElemType;typedef char QElemType;/*图的邻接矩阵存储表示*/typedef struct ArcCell VRType adj; / VRType是顶点关系类型。对无权图，用1或0表示相邻否； / 对带权图，则为权值类型。 InfoType *info; / 该弧相关信息的指针ArcCell, AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;typedef struct VertexType vexsMAX_VERTEX_NUM; / 顶点向量 AdjMatrix arcs; / 邻接矩阵 int vexnum, arcnum; / 图的当前顶点数和弧数 GraphKind kind; / 图的种类标志MGraph;/*图的邻接表存储表示*/typedef struct ArcNode int weight; int adjvex; / 该弧所指向的顶点的位置 struct ArcNode *nextarc; / 指向下一条弧的指针 InfoType *info; / 该弧相关信息的指针ArcNode;typedef struct VNode VertexType data; / 顶点信息 ArcNode *firstarc; / 指向第一条依附该顶点的弧VNode, AdjListMAX_VERTEX_NUM;typedef struct AdjList vertices; int vexnum, arcnum; / 图的当前顶点数和弧数 GraphKind kind; / 图的种类标志ALGraph;/*树的孩子兄弟存储表示*/typedef struct CSNode TElemType data; struct CSNode *firstchild,*nextsibling; CSNode, *CSTree;/*队列的存储结构*/typedef struct QNode QElemType data; struct QNode *next; QNode, *QueuePtr;typedef struct QueuePtr front; QueuePtr rear; LinkQueue;/*单链队列的相关算法*/构造空队列status InitQueue(LinkQueue &Q) Q.rear=Q.front=(QueuePtr)malloc(sizeof(QNode); if(!Q.front) return (OVERFLOW); Q.front-next=NULL; return OK;/队是否为空bool QueueEmpty(LinkQueue Q) if(!Q.front-next) return (true); return (false);/入队status EQueue(LinkQueue &Q, QElemType e) QNode *p; p=(QNode *)malloc( sizeof(QNode); if (!p) return (OVERFLOW); p-data= e; p-next=NULL; Q.rear-next=p; Q.rear=p; return(OK);/出队status DeQueue(LinkQueue &Q, QElemType &e) QNode *p; if(!Q.front) return (OVERFLOW); p=Q.front-next; e=p-data; Q.front-next=p-next; if(Q.rear=p) Q.rear=Q.front; free(p); return (OK);/*栈的基本操作*/栈的存储结构typedef char SElemType;typedef struct SElemType *base; /栈底指针 SElemType *top; /栈顶指针 int stacksize; /栈的大小SqStack;/构造空栈status InitStack (SqStack &S) S.base=(SElemType *)malloc(STACK_INIT_SIZE * sizeof(SElemType); if (!S.base) return(OVERFLOW); S.stacksize = STACK_INIT_SIZE; S.top = S.base; return(OK);/出栈status Pop(SqStack &S, SElemType &e) if(S.base = S.top) return(ERROR);/栈空 e=*-S.top; return(OK); /入栈status Push(SqStack &s,SElemType e) if(s.top-s.base=s.stacksize) return OVERFLOW; *s.top+=e; return OK;/销毁栈status DestroyStack(SqStack &S) S.top=NULL; S.base=NULL; delete S.base; S.stacksize=0; return OK;/判断栈是否为空int EmptyStack(SqStack s) if(s.top=s.base) return 1; else return 0;/得到栈顶元素status GetTop(SqStack &s,SElemType &e) if(s.top=s.base) return ERROR; e=*(s.top-1); return OK;/栈的长度int StackLength(SqStack s) return s.top-s.base;/得到栈的所有元素值status Get(SqStack s) int i,n; n=StackLength(s); if(!n) return ERROR; for(i=0;in;i+) printf(%ct,*(s.base+i); return OK;/*创建有向图的邻接矩阵*/元素在图中的位置int locateMG(MGraph g,VertexType v) for(int i=0;ig.vexnum;i+) if(g.vexsi=v) return i; return -1;/边是否存在status arcExist(MGraph g,int i,int j) if(g.arcsij.adj=MAX) return 0; return 1; /图是否存在int ExistM(MGraph g) if(g.vexnumi) printf(n输入有误,边数不能超过%d，请重新输入！,i); printf(n请输入有向图的弧数：); scanf(%d,&g.arcnum); for(i=0;ig.vexnum;i+)/初始化邻接矩阵 for(j=0;jg.vexnum;j+) g.arcsij.adj=MAX; printf(请依次输入有向图的各个顶点(用回车分隔):); for(i=0;i0) printf(输入的顶点重复，请重新输入n); i-; continue; g.vexsi=v; for(k=1;k=g.arcnum;k+)/构造邻接矩阵 getchar(); printf(请输入第%d条弧的起点与终点(用逗号分隔)：,k); scanf(%c,%c,&v1,&v2); i=locateMG(g,v1); j=locateMG(g,v2); if(i0|j0|i=j|arcExist(g,i,j) printf(输入错误,请重新输入n); k-; continue; printf(请输入第%d条弧的权值：,k); scanf(%d,&n); g.arcsij.adj=n; printf(有向图的邻接矩阵创建成功n); return OK;/*显示创建的图*/void PrintMGraph(MGraph g)printf(已创建图的邻接矩阵n);int i,j;for(i=0;ig.vexnum;i+)printf( n);printf(%c,g.vexsi);printf(n);for( i=0;ig.vexnum;i+)printf(%c,g.vexsi);printf( );for( j=0;jg.vexnum;j+)if(g.arcsij.adj!=MAX)printf(%c,g.arcsij.adj);printf( );elseprintf();printf( );printf(n);printf( );printf(n);/*创建有向图的邻接表*/元素在图中的位置int locateALG(ALGraph g,VertexType v) for(int i=0;ig.vexnum;i+) if(g.verticesi.data=v) return i; return -1;/当前有向图中是否存在边int GraphExist(ALGraph G,int i,int j) ArcNode *s; s=G.verticesi.firstarc; while(s&s-adjvex!=j) s=s-nextarc; if(s) return 1; else return 0;/图是否存在int ExistG(ALGraph g) if(g.vexnumMAX_VERTEX_NUM) printf(n输入有误,顶点数不能超过%d，请重新输入！,MAX_VERTEX_NUM); printf(n请输入有向图的顶点数：); scanf(%d,&g.vexnum); i=g.vexnum*(g.vexnum-1); printf(请输入有向图的边数:); scanf(%d,&g.arcnum); while(g.arcnumi) printf(n输入有误,边数不能超过%d，请重新输入！,i); printf(n请输入有向图的边数：); scanf(%d,&g.arcnum); printf(请依次输入有向图的各个顶点(用回车分隔):); for(i=0;i=0) printf(输入的顶点重复，请重新输入n); i-; continue; g.verticesi.data=c; g.verticesi.firstarc=NULL; for(k=0;kg.arcnum;k+)/输入边的信息 getchar(); printf(请输入第%d条弧的起点与终点(用逗号分隔)：,k+1); scanf(%c,%c,&v1,&v2); i=locateALG(g,v1); j=locateALG(g,v2); if(i0|jadjvex=j; p-nextarc=g.verticesi.firstarc;/顶点i的链表 g.verticesi.firstarc=p;/添加到最左边 p-weight=n; printf(有向图的邻接表创建成功n); return OK;/*输出图的信息*/void printGra(ALGraph G) ArcNode *p; int i; printf(图中有%d个顶点，%d条弧：n,G.vexnum,G.arcnum); for(i=0;iG.vexnum;i+) p=G.verticesi.firstarc; printf(%ct,G.verticesi.data); while(p) printf(t,G.verticesi.data,G.verticesp-adjvex.data,p-weight); p=p-nextarc; printf(n); void printMg(MGraph g) int i,j; for(i=0;ig.vexnum;i+) printf(%ct,g.vexsi); for(j=0;jg.vexnum;j+) if (g.arcsij.adj!=MAX) printf(t,g.vexsi,g.vexsj,g.arcsij.adj); printf(n); /*输出图的邻接表存储结构*/void PrintADG(ALGraph G)int i;ArcNode *p;/cout邻接表图每个顶点：endl;printf(邻接表图的每个顶点n);for(i=0;iG.vexnum;i+)printf(%c,G.verticesi.data);printf( );printf(n);/cout图的邻接表：endl;printf(该图的邻接表：n);for(i=0;i);printf(%c,p-adjvex);p=p-nextarc;printf(n);/*邻接表深度优先遍历并判断图的连通性 */ArcNode *nextnode=NULL;/全局变量bool visited21;/全局变量/得到i号顶点的第一个邻接点int FirstAdjVex(ALGraph g,int i) ArcNode *p; p=g.verticesi.firstarc; if(!p) return -1; nextnode=p-nextarc; return(p-adjvex);/得到i号顶点的下一个邻接点int NextAdjVex(ALGraph g,int i) if(!nextnode) return -1; int m=nextnode-adjvex; nextnode=nextnode-nextarc; return m;/访问图中的i号顶点void visitvex(ALGraph g,int i) printf(%ct,g.verticesi.data);/从图某个顶点进行深度优先遍历int DFS(ALGraph g,int i) int w; visitedi=true; visitvex(g,i); for(w=FirstAdjVex(g,i);w=0;w=NextAdjVex(g,i) if(!visitedw) DFS(g,w); return OK;/对图进行深度优先遍历status DFSTraverse(ALGraph g) int v,u,x; int count100; for(v=0;vg.vexnum;v+) countv=0; printf(从%c开始深度优先遍历的结果：,g.verticesv.data); for(u=0;ug.vexnum;u+) visitedu=false; for(x=v;xg.vexnum+v;x+) int a; a=x; a=a%g.vexnum; if(!visiteda) DFS(g,a); countv+; printf(n); int min; min=count0; for(int i=0;icounti) min=counti; if(min!=1) printf(n该有向图是不连通图！连通分量为：%dn,min); else printf(n该有向图是连通图！n); return OK;/*返回当前有向图中的每个顶点的入度与出度*/图中某个顶点的入度status InDegree(ALGraph G,int i) int j; int n=0; for(j=0;jnextarc; return j;/每个顶点的与出度入度void degree(ALGraph G) int i,n,m; char a; for(i=0;ik) printf(n输入有误,增加的边数不能超过%d，请重新输入！,k); printf(n请输入有向图的边数：); scanf(%d,&n); for(k=0;kn;k+) getchar(); printf(请输入要增加的弧的起点与终点(用逗号分隔)：); scanf(%c,%c,&v1,&v2); i=locateALG(G,v1); j=locateALG(G,v2); if(i0|jadjvex=j; p-weight=w; p-nextarc=G.verticesi.firstarc; G.verticesi.firstarc=p; G.arcnum+; printf(插入弧成功n); return 1;/*当前有向图中插入顶点*/int NodeAdd(ALGraph &G) int i,l,n; char c; printf(请输入要增加的顶点个数：); scanf(%d,&n); /增加的定点个数判断 if(G.vexnum+nMAX_VERTEX_NUM) printf(输入错误，最多有50个顶点n); return ERROR; for(i=0;i=0) printf(输入的顶点重复，请重新输入n); i-; continue; G.verticesG.vexnum.data=c; G.verticesG.vexnum.firstarc=NULL; G.vexnum+; printf(增加顶点成功n); return OK;/*当前有向图删除弧*/int delArc(ALGraph &G,int i,int j) ArcNode *p,*q; p=G.verticesi.firstarc; if(p-adjvex=j) G.verticesi.firstarc=p-nextarc; free(p); else while(p-nextarc&p-nextarc-adjvex!=j) p=p-nextarc; if(p) q=p-nextarc; p-nextarc=q-nextarc; free(q); G.arcnum-; return OK;int GraphDel(ALGraph &G) int n,k,i,j; VertexType v1,v2; printf(请输入要删除的弧数：); scanf(%d,&n); while(nG.arcnum) printf(删除的弧数不能超过%d，请重新输入n,G.arcnum); printf(请输入要删除的弧数：); scanf(%d,&n); for(k=0;kn;k+) getchar(); printf(请输入要删除的弧的起点与终点(用逗号分隔)：); scanf(%c,%c,&v1,&v2); i=locateALG(G,v1); j=locateALG(G,v2); if(i0|jG.vexnum) printf(输入错误n); return ERROR; for(k=0;kn;k+)/输入要删除顶点信息 getchar(); printf(请输入要删除的顶点:); scanf(%c,&c); l=locateALG(G,c)