《2022年拓扑排序课程设计报告 .pdf》由会员分享，可在线阅读，更多相关《2022年拓扑排序课程设计报告 .pdf（13页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、拓扑排序一 问题描述本次课程设计题目是：编写函数实现图的拓扑排序二 概要设计1.算法中用到的所有各种数据类型的定义在该程序中用邻接表作为图的存储结构。首先，定义表结点和头结点的结构类型，然后定义图的结构类型。创建图用邻接表存储的函数，其中根据要求输入图的顶点和边数，并根据要求设定每条边的起始位置，构建邻接表依次将顶点插入到邻接表中。拓扑排序的函数在该函数中首先要对各顶点求入度，其中要用到求入度的函数，为了避免重复检测入度为零的顶点，设置一个辅助栈，因此要定义顺序栈类型，以及栈的函数：入栈，出栈，判断栈是否为空。2.各程序模块之间的层次调用关系第一部分，void CreatGraph(ALGra
2、ph*G)函数构建图，用邻接表存储。这个函数没有调用函数。第二部分，void TopologicalSort(ALGraph*G)输出拓扑排序函数，这个函数首先调用 FindInDegree(G,indegree)对各顶点求入度 indegree0vernum-1;然后设置了一个辅助栈，调用InitStack(&S)初始化栈，在调用Push(&S,i)入度为 0 者进栈，while(!StackEmpty(&S)栈不为空时，调用 Pop(&sS,&n)输出栈中顶点并将以该顶点为起点的边删除，入度indegreek-,当输出某一入度为0 的顶点时，便将它从栈中删除。第三部分，主函数，先后调用vo
3、id CreatGraph(ALGraph*G)函数构建图、void TopologicalSort(ALGraph*G)函数输出拓扑排序实现整个程序。3.设计的主程序流程名师资料总结-精品资料欢迎下载-名师精心整理-第 1 页，共 13 页 -开始调用建图函数输入顶点数、弧数、顶点值输入存在弧的两个顶点建零入度顶点栈S，入度为 0 者进栈!StackEmpty(&S)判断并输出相应信息结束Pop(&S,&n)P=G.verticesn.firstarc P!=NULL K=P-adjves!(-indegreek)P=p-nextarc Push(&S,k);名师资料总结-精品资料欢迎下载-
4、名师精心整理-第 2 页，共 13 页 -三 详细设计1.实现概要设计中定义的所有数据类型#include#include#include#define MAX_VEXTEX_NUM 20/*定义点最大的数值为顶30*/#define M 20#define STACK_INIT_SIZE 100/*定义点最大的数值为顶30*/#define STACKINCREMENT 10/*定义栈的增量为 10*/#define OK 1#define ERROR 0 typedef char ElemType;/*定义栈顶元素类型*/typedef struct ArcNode int adjvex;
5、/该弧所指向的顶点的位置/struct ArcNode*nextarc;/指向下一条弧的指针/ArcNode;/*表结点*/typedef struct VNode char data;/顶点信息ArcNode*firstarc;/指向第一条依附该顶点的弧的指针/VNode,AdjListMAX_VEXTEX_NUM;typedef struct AdjList vertices;int vexnum,arcnum;/图的当前顶点数和弧数/ALGraph;typedef struct/构建栈/ElemType*base;/*在栈构造之前的指针*/ElemType*top;/*栈顶指针*/int
6、 stacksize;/*定义所分配的存储空间*/SqStack;/*顺序栈*/名师资料总结-精品资料欢迎下载-名师精心整理-第 3 页，共 13 页 -2.算法和各模块的代码程序中各函数算法思想如下：1void InitStack(SqStack*S)初始化栈将栈的空间设为STACK-INIT-SIZE。2int Pop(SqStack*S,ElemType*e)出栈操作，若站不空，删除S 的栈顶元素，用e 返回其值，并返回OK；否则返回 ERROR。3void Push(SqStack*S,ElemType e)进栈操作，插入元素e为新的栈顶元素。4int StackEmpty(SqSta
7、ck*S)判断栈是否为空,语句 if(S-top=S-base)判断，若栈不为空，则删除S 的栈顶元素，并返回 OK；否则返回 ERROR。5void CreatGraph(ALGraph*G)构建图，用邻接表存储，首先定义邻接表指针变量，输入顶点数和弧数，初始化邻接表，将表头向量域置空，输入存在弧的点集合，当输入顶点值超出输入值的范围就会出错，否则依次插入进邻接表，最后输出建立好的邻接表。6void FindInDegree(ALGrap G,int indegreee)求入度操作，设一个存放各顶点入度的数组indegreee，然后indegreeei=0赋初值，for 循环 indegre
8、ee+，存储入度数。7void TopologicalISort(ALGraph G)输出拓扑排序函数。其思路是若 G 无回路，则输出 G 的顶点的一个拓扑序列并返回 OK，否则返回ERROR。首先由于邻接表的存储结构入度为零的顶点即为 没 有 前 驱 的 顶 点，我 们 可 以 附 设 一 个 存 放 个 顶 点 入度 的 数 组，调 用FindInDegree(G,indegreee)对各顶点求入度；为了避免重复检测入度为零0 的顶点，设置一个栈，调用InitStack(&S)初始化栈，在调用Push(&S,i)入度为 0 者进栈，while(!StackEmpty(&S)栈不为空时，调用
9、 Pop(&sS,&n)输出栈中顶点并将以该顶点为起点的边删除，入度indegreek-,当输出某一入度为0 的顶点时，便将它从栈中删除。3.算法的时间复杂度和空间复杂度拓扑排序实际是对邻接表表示的图G 进行遍历的过程，每次访问一个入度名师资料总结-精品资料欢迎下载-名师精心整理-第 4 页，共 13 页 -为零的顶点，若图G 中没有回路，则需扫描邻接表中的所有边结点，在算法开始时，为建立入度数组D 需访问表头向量中的所有边结点，算法的时间复杂度为 O(n+e)。四 调试分析对如下有向无环图进行拓扑排序。输入：名师资料总结-精品资料欢迎下载-名师精心整理-第 5 页，共 13 页 -结果如下：
10、五 心得体会在进行拓扑排序的课程设计中，更好的认识了拓扑排序。在设计中，我们遇到了程序正确，却对某些无向图无法进行拓扑排序的问题。多次对程序进行修改后，才可以进行拓扑排序。问题出在调用函数的错误理解，模块之间的联系模糊不清,在同学的帮助和自己的努力思考下，我最终把这些问题一一解决，并把教训牢记在心，努力使自己得到更大的收获和提高。因为在理论学习中没有好好的掌握，现在要独立完成一个较复杂的程序编写，确实有困难。今后我必需扎实基础理论、认真思考，而且要践行我的承诺，一步一个脚印的走下去，才可以达到我们预期的彼岸！名师资料总结-精品资料欢迎下载-名师精心整理-第 6 页，共 13 页 -六 程序清单
11、#include#include#include#define MAX_VEXTEX_NUM 20/*定义点最大的数值为顶30*/#define M 20#define STACK_INIT_SIZE 100/*定义点最大的数值为顶30*/#define STACKINCREMENT 10/*定义栈的增量为 10*/#define OK 1#define ERROR 0 typedef char ElemType;/*定义栈顶元素类型*/typedef struct ArcNode int adjvex;/*该弧所指向的顶点的位置*/struct ArcNode*nextarc;/*指向下一条
12、弧的指针*/ArcNode;/*表结点*/typedef struct VNode char data;/*顶点信息*/ArcNode*firstarc;/*指向第一条依附该顶点的弧的指针*/VNode,AdjListMAX_VEXTEX_NUM;typedef struct AdjList vertices;int vexnum,arcnum;/*图的当前顶点数和弧数*/ALGraph;typedef struct/*构建栈*/ElemType*base;/*在栈构造之前的指针*/ElemType*top;/*栈顶指针*/名师资料总结-精品资料欢迎下载-名师精心整理-第 7 页，共 13 页
13、 -int stacksize;/*定义所分配的存储空间*/SqStack;/*顺序栈*/void InitStack(SqStack*);/*函数声明*/int Pop(SqStack*,ElemType&);void Push(SqStack*,ElemType);int StackEmpty(SqStack*);void CreatGraph(ALGraph*);void FindInDegree(ALGraph,int*);void TopologicalSort(ALGraph);void InitStack(SqStack*S)/*初始化栈*/S-base=(ElemType*)m
14、alloc(STACK_INIT_SIZE*sizeof(ElemType);/*申请新的结点并由 s-base指向*/if(!S-base)/*存储分配失败*/printf(memory allocation failed,goodbye);exit(1);S-top=S-base;/*空栈之前的指针赋给头指针*/S-stacksize=STACK_INIT_SIZE;/*栈的空间设为 Stack_init_size*/int Pop(SqStack*S,ElemType&e)/*出栈操作*/if(S-top=S-base)/*栈空返回 OK*/return ERROR;/*删除 S的栈顶元
15、素*/e=*-S-top;return 0;名师资料总结-精品资料欢迎下载-名师精心整理-第 8 页，共 13 页 -void Push(SqStack*S,ElemType e)/*进栈操作，插入元素e 为新的栈顶元素*/if(S-top-S-base=S-stacksize)S-base=(ElemType*)realloc(S-base,(S-stacksize+STACKINCREMENT)*sizeof(ElemType);if(!S-base)/*存储分配失败*/printf(memory allocation failed,goodbye);exit(1);S-top=S-bas
16、e+S-stacksize;S-stacksize+=STACKINCREMENT;*S-top+=e;int StackEmpty(SqStack*S)/*判断栈是否为空*/if(S-top=S-base)/*栈不为空,则删除 S 的栈顶元素,并返回 OK;否则返回*/return OK;else return ERROR;int locatevex(ALGraph G,char u)/*若 G 图中存在顶点 u,则返回该顶点在图中的位置;否则返回-2.*/int i;for(i=0;ivexnum,&G-arcnum);printf(输入顶点的值(用空格隔开):n);for(i=0;ive
17、xnum;i+)/*构造表头向量*/scanf(%s,&G-verticesi.data);/*输入顶点的值*/G-verticesi.firstarc=NULL;/*初始化指针*/for(k=0;karcnum;k+)char v1,v2;int i,j;loop:printf(输入一条弧的起点和终点(用空格隔开):n);scanf(%s%s,&v1,&v2);i=locatevex(*G,v1);/*确定 v1,v2 在 G 中的位置*/j=locatevex(*G,v2);if(i=-2|j=-2)printf(输入有误！);break;goto loop;名师资料总结-精品资料欢迎下载
18、-名师精心整理-第 10 页，共 13 页 -ArcNode*p;p=(ArcNode*)malloc(sizeof(ArcNode);if(p=NULL)printf(memory allocation failed,goodbey);exit(1);p-adjvex=j;/*对弧结点赋值*/p-nextarc=G-verticesi.firstarc;G-verticesi.firstarc=p;/*插入到表头向量后面*/ArcNode*p;/*定义邻接表指针变量*/p=(ArcNode*)malloc(sizeof(ArcNode);if(p=NULL)printf(memory all
19、ocation failed,goodbey);exit(1);printf(建立的邻接表为:n);/*输出建立好的邻接表*/for(i=0;i vexnum;i+)printf(%c,G-verticesi.data);for(p=G-verticesi.firstarc;p;p=p-nextarc)printf(%3d,p-adjvex);printf(n);void FindInDegree(ALGraph G,int indegree)/*求入度操作*/int i;for(i=0;i G.vexnum;i+)名师资料总结-精品资料欢迎下载-名师精心整理-第 11 页，共 13 页 -i
20、ndegreei=0;for(i=0;i adjvex+;G.verticesi.firstarc=G.verticesi.firstarc-nextarc;void TopologicalSort(ALGraph G)/*输出拓扑排序函数。若G 无回路，则输出G 的顶点的一个拓扑序列并返回OK，否则返回 ERROR*/int indegreeM;int i,k,j;char n;int count=0;ArcNode*p;SqStack S;FindInDegree(G,indegree);/*对各顶点求入度 indegree0.vernum-1*/InitStack(&S);/*初始化栈*
21、/for(i=0;i G.vexnum;i+)printf(结点%c 的入度为%d n,G.verticesi.data,indegreei);printf(n);for(i=0;i nextarc)k=p-adjvex;if(!(-indegreek)Push(&S,G.verticesk.data);printf(n);if(count G.vexnum)printf(该图有环,出现错误,无法排序.n);else printf(排序成功 n);main()/*主函数*/printf(*建立有向图的拓扑排序，请按如下要求进行输入*n);ALGraph G;/*定义一个图的变量*/CreatGraph(&G);/*调用建图函数*/TopologicalSort(G);/*调用拓扑排序函数*/return 0;名师资料总结-精品资料欢迎下载-名师精心整理-第 13 页，共 13 页 -