图的基本操作及应用数据结构课程设计报告.doc

算法与数据结构课程设计报告系 （院）： 计算机科学学院 专业班级： 教育技术学1001班 姓 名： 宋佳 学 号： 201003901 指导教师： 詹泽梅 设计时间： 2012.6.16 - 2012.6.24 设计地点： 4号楼2号机房 算法与数据结构课程设计任务书班级：教育技术11001课程设计题目：图的基本操作及应用数据结构课程设计是在学完数据结构课程之后的实践教学环节。本实践教学是培养学生数据抽象能力，进行复杂程序设计的训练过程。要求学生能对所涉及问题选择合适的数据结构、存储结构及算法，并编写出结构清楚且正确易读的程序，提高程序设计基本技能和技巧。一设计目的1提高数据抽象能力。根据实际问题，能利用数据结构理论课中所学到的知识选择合适的逻辑结构以及存储结构，并设计出有效解决问题的算法。2提高程序设计和调试能力。学生通过上机实习，验证自己设计的算法的正确性。学会有效利用基本调试方法，迅速找出程序代码中的错误并且修改。3初步了解开发过程中问题分析、整体设计、程序编码、测试等基本方法和技能。二设计任务设计一个基于DOS菜单的应用程序。要利用多级菜单实现各种功能。内容如下：1 无向图的基本操作及应用 创建无向图的邻接矩阵 创建无向图的邻接表 无向图的深度优先遍历 无向图的广度优先遍历2 有向图的基本操作及应用 创建有向图的邻接矩阵 创建有向图的邻接表 拓扑排序3 无向网的基本操作及应用 创建无向网的邻接矩阵 创建无向网的邻接表 求最小生成树 4 有向网的基本操作及应用 创建有向网的邻接矩阵 创建有向网的邻接表 关键路径 单源最短路径 三设计指导第一步：根据设计任务，设计DOS菜单。第二步：设计菜单（c语言）#includevoid ShowMainMenu()printf(n);printf(*图的基本操作及应用*n);printf(* 1 无向图的基本操作及应用 *n);printf(* 2 有向图的基本操作及应用 *n);printf(* 3 无向网的基本操作及应用 *n);printf(* 4 有向网的基本操作及应用 *n);printf(* 5 退出n);printf(*n);void UDG()int n;doprintf(n);printf(*无向图的基本操作及应用*n);printf(* 1 创建无向图的邻接矩阵 *n);printf(* 2 创建无向图的邻接表 *n);printf(* 3 无向图的深度优先遍历 *n);printf(* 4 无向图的广度优先遍历 *n);printf(* 5 退出n);printf(*n);printf(请选择：);scanf(%d,&n);switch(n)case 1:printf(-wait-);break;case 2:printf(-wait-);break;case 3:printf(-wait-);break;case 4:printf(-wait-);break;case 5:break;default:printf(ERROR!);while(n!=5);void DG() int n;doprintf(n);printf(*有向图的基本操作及应用*n);printf(* 1 创建有向图的邻接矩阵 *n);printf(* 2 创建有向图的邻接表 *n);printf(* 3 拓扑排序 *n);printf(* 4 退出 *n);printf(*n);printf(请选择：);scanf(%d,&n);switch(n)case 1:printf(-wait-);break;case 2:printf(-wait-);break;case 3:printf(-wait-);break;case 4:break;default:printf(ERROR!);while(n!=4);void UDN() int n;doprintf(n);printf(*无向网的基本操作及 *n);printf(* 1 创建无向网的邻接矩阵 *n);printf(* 2 创建无向网的邻接表 *n);printf(* 3 Prim算法求最小生成树 *n);printf(* 4 kraskal算法求最小生成树 *n);printf(* 5 退出n);printf(*n);printf(请选择：);scanf(%d,&n);switch(n)case 1:printf(-wait-);break;case 2:printf(- -wait-);break;case 3:printf(-wait-);break;case 4:printf(-wait-);break;case 5:break;default:printf(ERROR!);while(n!=5);void DN() int n;doprintf(n);printf(*有向网的基本操作*n);printf(* 1 创建有向网的邻接矩阵 *n);printf(* 2 创建有向网的邻接表 *n);printf(* 3 关键路径 *n);printf(* 4 单源顶点最短路径问题 *n);printf(* 5 退出n);printf(*n);printf(请选择：);scanf(%d,&n);switch(n)case 1:printf(-wait-);break;case 2:printf(-wait-);break;case 3:printf(-wait-);break;case 4:printf(-wait-);break;case 5:break;default:printf(ERROR!);while(n!=5);void main()int n;doShowMainMenu();printf(请选择：);scanf(%d,&n);switch(n)case 1:UDG();break;case 2:DG();break;case 3:UDN();break;case 4:DN();break;case 5:break;default:printf(ERROR!);break;while(n!=5);第三步：添加功能函数。在主程序的合适位置添加相应的函数实现各功能（提示：语句printf(“-wait-”)所在位置）。四成绩评定l 实习报告（文字不得少于4000字）一、 设计方案；二、 实现过程；三、 实现代码；四、 测试；五、 结论；六、 难点与收获。l 程序实现1. 程序运行正确，无编译错误，无逻辑错误；2. 在第一条的基础上，任务完成的越多，成绩等级越高。l 成绩由三部分组成：平时考核(20%)、程序实现(50%)、实习报告(30%)一、 设计方案由课程设计任务书，按照要求，需要设计有向图3、有向网、无向图 、无向网四种图，邻接矩阵、邻接表两种数据存储结构，共十六种基本操作及应用，三层以上的显示菜单。图的操作中又包含有有关线性表、栈和队列的基本操作。由于显示菜单已给出，剩下的只是把函数写入其中，而线性表、栈和队列的基本操作并不复杂，很容易实现，我们只有完成图的相关操作即可。图的操作都是以两种存储结构为基础的，邻接矩阵存储结构和邻接表存储结构，如四种图（有向图，有向网，无向图，无向网）的创建，其他的操作都是在四种图创建后才开始进行的。所以，首先必须理解两种存储结构的定义。图的邻接矩阵存储结构即图的数组表示法。用两个数组分别存储数据元素（顶点）的信息和数据元素之间的关系（边或弧）的信息。用邻接矩阵存储结构的图具有以下几点特征：（一）：顶点数：vexnum，边（弧）数：arcnum，图的种类：kind；（二）：邻接矩阵：arcs(1顶点关系类型:adj 2相关信息:*info)；（三）：顶点向量（顶点名）：vexs；其优点是以二维数组表示有n个顶点的图时，需存放n顶点的信息和n*n个弧的信息存储量。借助于邻接矩阵容易判定任意两个顶点之间是否有边或弧相连，并容易求各个顶点的度。缺点其时间复杂度是O（n*n）,例如，构造一个具有n个顶点和e条边的无向网的时间复杂度为O（n*n+e*n）。图的邻接表存储结构是图的一种链式存储结构。对图中的每个顶点建立一个单链表，每个结点有三个域组成，邻接点域adjvex（弧尾在邻接表链表中的位序），链域nextarc（下一条弧），数据域info(权值)。还要建立一个邻接表链表，用以存放顶点名data和后继指针firstarc,表头结点以顺序结构的形式存储，便于随机访问任一顶点的单链表。邻接表存储结构的优点在于其时间复杂度小。除此之外，还有十字链表存储结构和多重链表存储结构。由于，没有用到他们，故不再详细描述。树的深度优先搜索遍历类似于树的先根遍历，是树的先根遍历的推广。从图中的某个顶点出发，访问此顶点，然后依次从该顶点出发深度优先搜索遍历图，直至图中所有与该顶点有关的路径都被访问到；此时图中若还有顶点未被访问到，则另选图中的一个未被访问的顶点作为起始点，重述上述过程，直至所有顶点都被访问到。广度优先搜索遍历类似于树的按层次遍历的过程。以某个顶点为起始顶点，由近至远，依次访问和该顶点有路径相通的且路径长度为1， 2， 3，的顶点。当图中所有顶点都被访问到后，就完成了图的广度优先搜索遍历。求无向网的最小生成树问题有两种算法：Prima算法和Kruskal算法。Prima算法是从网中的某个顶点出发，选择与该顶点有路径的所有顶点中路径最小的一条路径，从该最小路径的另一顶点出发，重复上述过程，直至图中所有顶点都被访问完成。Kruskal算法是从网中找出所有路径最小的一条路径，记下已访问该路径的两个顶点，再次从图中找出剩下路径中的最小路径，重复上述过程，直至所有顶点都被访问完成，按访问的顺序依次输出各顶点，即构造了一棵最小生成树。由某个集合上的一个偏序得到该集合的一个全序的操作就叫做拓扑排序。拓扑排序主要有两个方面的操作：（1）在有向图中选择一个没有前驱的顶点并输出；（2）在图中删除该顶点和所有以它为尾的弧。重复上述两步，直至全部顶点均已输出，就得到了一个拓扑有序序列。求关键路径的算法如下：输入e条弧，建立AOE网的存储结构；从源点v0出发,令ve0=0，按拓扑有序求其余各顶点的最早发生时间。如果得到的拓扑有序序列中的顶点个数小于网中的顶点数，则说明网中存在环，不能求关键路径，算法终止；否则执行第三步。从汇点vn出发，令vln-1=ven-1，按逆拓扑有序求其余各顶点的最迟发生时间vli；根据各顶点的和值，求每条弧的最早开始时间e(s)和最迟开始时间e(s)，若某条弧满足条件e(s)=l(s)，则为关键活动。从某个源点到其余各顶点的最短路径问题：若从v到vi有弧，则Di为弧上的权值，否则Di为无穷大。显然，长度为Dj=MinDi|vi属于V的路径就是从v出发的长度最短的一条路径。二、 实现及测试过程按照设计任务的要求，我先完成了存储结点、边、邻接矩阵、邻接表、队列、栈等储存结构体的设计。其次是栈和队列的基本操作和实现，四种图的创建和显示，然后是基于两种存储结构的各种算法的现，最后是三层显示输出菜单。测试样图：三、实现代码#include #include#include #define ERROR 0#define OK 1#define INFINITY INT_MAX#define MAX_VERTEX_NUM 21#define STACK_INIT_SIZE 100#define STACKINCREAMENT 10typedef enumDG,DN,UDG,UDNGraphKind;typedef struct ArcCell int adj; /infotype *info;ArcCell, AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;typedef struct char vexsMAX_VERTEX_NUM; AdjMatrix arcs; int vexnum,arcnum; GraphKind kind;MGraph; /邻接矩阵typedef struct ArcNode int adjvex; int quan; struct ArcNode *nextarc; ArcNode,*AList;typedef struct VNode char data; AList firstarc;VNode,AdjListMAX_VERTEX_NUM;typedef struct AdjList vertices; int vexnum,arcnum; GraphKind kind;ALGraph; /邻接表typedef struct QNodechar data;struct QNode *next;QNode,*QueuePre;typedef structQueuePre front;QueuePre rear;LinkQueue; /队列typedef struct int *base;int *top;int stacksize;SqStack; /栈typedef struct char adjvex;int lowcost;closedgesMAX_VERTEX_NUM; /求最小生成树中的辅助数组int option; int visitedMAX_VERTEX_NUM; /顶点访问标记数组int indegreeMAX_VERTEX_NUM; /顶点入度记录数组int veMAX_VERTEX_NUM; /顶点权值记录数组int SetGraphKind(MGraph &G,int option) switch(option) case 1: G.kind=DG;break; case 2: G.kind=DN;break; case 3: G.kind=UDG;break; case 4: G.kind=UDN;break; default: return ERROR; return OK; /邻接矩阵类型设置int SetGraphKind(ALGraph &G,int option) switch(option) case 1: G.kind=DG;break; case 2: G.kind=DN;break; case 3: G.kind=UDG;break; case 4: G.kind=UDN;break; default: return ERROR; return OK; /邻接表类型设置int LocateVex(MGraph G,char v) int m; for(m=1;m=G.vexnum;m+) if(G.vexsm=v) return m; return ERROR; /邻接矩阵顶点定位int LocateVex(ALGraph G,char v) int m; for(m=1;mnext=NULL;return OK; /队列创建int EnQueue(LinkQueue &Q,int e)QueuePre p;p=(QueuePre)malloc(sizeof(QNode);if(!p) return OK;p-data=e;p-next=NULL;Q.rear-next=p;Q.rear=p;return OK; /元素入队列int DeQueue(LinkQueue &Q,int &e)QueuePre p;if(Q.front=Q.rear) return ERROR;p=Q.front-next;e=p-data;Q.front-next=p-next;if(Q.rear=p) Q.rear=Q.front;free(p);return OK; /元素出队列int QueueEmpty(LinkQueue Q)if(Q.front=Q.rear)return OK;return ERROR; /判断队列是否为空int InitStack(SqStack &S)S.base=(int*)malloc(STACK_INIT_SIZE*sizeof(int);if(!S.base) return ERROR;S.top=S.base;S.stacksize=STACK_INIT_SIZE;return OK; /栈创建int Push(SqStack &S,int e)if(S.top-S.base=S.stacksize)S.base=(int*)realloc(S.base,(S.stacksize+STACKINCREAMENT)*sizeof(int);if(!S.base) return ERROR;S.top=S.base+S.stacksize;S.stacksize+=STACKINCREAMENT;*S.top+=e;return OK; /元素入栈int Pop(SqStack &S,int &e)if(S.top=S.base) return ERROR;e=*-S.top;return OK; /元素出栈int StackEmpty(SqStack S)if(S.top=S.base) return OK;return ERROR; /判断栈是否为空int CreatGraph(MGraph &G) int i,j,k,w;char x,y; if(!SetGraphKind(G,option) printf(对图类型的设置失败);return ERROR; printf(邻接矩阵：请输入定点的个数、弧的个数：); scanf(%d %d,&G.vexnum,&G.arcnum); if(G.vexnum20) printf(您输入的顶点个数超过最大值); return ERROR; printf(请输入%d个顶点n,G.vexnum); for(i=1;i=G.vexnum;+i) fflush(stdin); scanf(%c,&G.vexsi); if(G.kind=DG|G.kind=UDG) for(i=1;i=G.vexnum;i+) for(j=1;j=G.vexnum;j+) G.arcsij.adj=0; if(G.kind=DG) printf(请输入有向图的两个相邻的顶点（如果互相邻接则也要输入）：n); for(k=1;k=G.arcnum;k+)fflush(stdin); scanf(%c%c,&x,&y); i=LocateVex(G,x);j=LocateVex(G,y); G.arcsij.adj=1; else printf(请输入无向图的两个相邻的顶点（x,y）：n); for(k=1;k=G.arcnum;k+)fflush(stdin); scanf(%c%c,&x,&y); i=LocateVex(G,x); j=LocateVex(G,y); G.arcsij.adj=1; G.arcsji.adj=G.arcsij.adj; else for(i=1;i=G.vexnum;i+) for(j=1;j=G.vexnum;j+) G.arcsij.adj=INT_MAX; if(G.kind=DN) printf(请输入有向网的两个相邻的顶点以及相应的权值w（如果互相邻接则也要输入）：n); for(k=1;k=G.arcnum;k+)fflush(stdin); scanf(%c%c %d,&x,&y,&w); i=LocateVex(G,x); j=LocateVex(G,y); G.arcsij.adj=w; else printf(请输入无向网的两个相邻的顶点（x,y）以及相应的权值w：n); for(k=1;k20) printf(您输入的顶点个数超过最大值); return ERROR; printf(请输入个顶点：n);for(i=1;i=G.vexnum;i+)fflush(stdin);scanf(%c,&G.verticesi.data);G.verticesi.firstarc=NULL;keyi=0;if(G.kind=DG)printf(请输入弧（如AB,其中AB与BA是不同的弧）：n);for(j=1;jnextarc=NULL;q-adjvex=n;while(keym&p-nextarc)p=p-nextarc;keym+;if(!keym)G.verticesm.firstarc=q;keym+;else p-nextarc=q; if(G.kind=UDG)printf(请输入弧（如AB,其中AB与BA是不同的弧）：n);for(j=1;jnextarc=NULL;q-adjvex=n;while(keym&p-nextarc)p=p-nextarc;keym+;if(!keym)G.verticesm.firstarc=q;keym+;else p-nextarc=q; if(G.kind=DN)printf(请输入依次输入弧以及这条弧的权值（如AB 8,其中AB与BA是不同的弧）：n); for(j=1;jnextarc=NULL;q-quan=w;q-adjvex=n;while(keym&p-nextarc)p=p-nextarc;keym+;if(!keym)G.verticesm.firstarc=q;keym+;else p-nextarc=q ; if(G.kind=UDN)printf(请输入依次输入弧以及这条弧的权值（如AB 8,其中AB与BA是不同的弧）：n); for(j=1;jnextarc=NULL;q-quan=w;q-adjvex=n;while(keym&p-nextarc)p=p-nextarc;keym+;if(!keym)G.verticesm.firstarc=q;keym+;else p-nextarc=q ; return OK; /创建邻接表int FirstAdjVex(ALGraph G,int v)if(G.verticesv.firstarc)return G.verticesv.firstarc-adjvex;return 0;int NextAdjVex(ALGraph G,int v,int w)AList s;s=G.verticesv.firstarc;while(s-adjvex!=w)s=s-nextarc;if(s-nextarc)return s-nextarc-adjvex;return 0;void DFS(ALGraph G,int v)int w;visitedv=1; printf(%c ,G.verticesv);for(w=FirstAdjVex(G,v);w=1;w=NextAdjVex(G,v,w)if(!visitedw) DFS(G,w); void DFSTraverse(ALGraph G)int v;visited0=1;for(v=1;v=G.vexnum;v+) visitedv=0;for(v=1;v=G.vexnum;v+)if(!visitedv) DFS(G,v); /图的深度遍历void BFSTraverse(ALGraph G)int v,w,u;LinkQueue Q;for(v=1;v=G.vexnum;v+) visitedv=0;visited0=1;InitQueue(Q);for(v=1;v=1;w=NextAdjVex(G,u,w) if(!visitedw)visitedw=1; printf(%c ,G.verticesw);EnQueue(Q,w); else break; /图的广度遍历void FindInDegree(ALGraph G,int in)int i,j,k;AList p;for(k=1;k=G.vexnum;k+) ink=0;for(i=1;iadjvex;inj+;p=p-nextarc; /计算各顶点入度 int TopologicalSort(ALGraph G)int i,k,count;AList p;SqStack S;FindInDegree(G,indegree);InitStack(S);for(i=1;inextarc)k=p-adjvex;if(!(-indegreek) Push(S,k);if(count=G.vexnum) return ERROR;else return OK; /拓扑排序int Minimum(MGraph G,closedges m)int i,j,min=INFINITY;for(i=1;i=G.vexnum;i+)if(mi.lowcost)if(mi.lowcostmin)min=mi.lowcost;j=i; return j;void MinSpanTree_PRIM(MGraph G,char u)int i,j,k;closedges closedge;k=LocateVex(G,u);for(j=1;j=G.vexnum;j+)if(j!=k) closedgej.adjvex=u;closedgej.lowcost=G.arcskj.adj;closedgek.lowcost=0;for(i=2;i=G.vexnum;i+)k=Minimum(G,closedge);printf(%c%c ,closedgek.adjvex,G.vexsk);closedgek.lowcost=0;for(j=1;j=G.vexnum;j+)if(G.arcs