电脑桌面
添加小米粒文库到电脑桌面
安装后可以在桌面快捷访问

拓扑排序课程设计报告

拓扑排序课程设计报告_第1页
1/13
拓扑排序课程设计报告_第2页
2/13
拓扑排序课程设计报告_第3页
3/13
拓扑排序 一 问题描述 本次课程设计题目是:编写函数实现图的拓扑排序 二 概要设计 1. 算法中用到的所有各种数据类型的定义 在该程序中用邻接表作为图的存储结构。首先,定义表结点和头结点的结构类型,然后定义图的结构类型。创建图用邻接表存储的函数,其中根据要求输入图的顶点和边数,并根据要求设定每条边的起始位置,构建邻接表依次将顶点插入到邻接表中。 拓扑排序的函数在该函数中首先要对各顶点求入度,其中要用到求入度的函数,为了避免重复检测入度为零的顶点,设置一个辅助栈,因此要定义顺序栈类型,以及栈的函数:入栈,出栈,判断栈是否为空。 2.各程序模块之间的层次调用关系 第一部分,void CreatGraph(ALGraph *G)函数构建图,用邻接表存储。这个函数没有调用函数。 第二部分,void TopologicalSort(ALGraph *G)输出拓扑排序函数,这个函数首先调用FindInDegree(G,indegree)对各顶点求入度indegree[0……vernum-1];然后设置了一个辅助栈,调用InitStack(&S)初始化栈,在调用Push(&S,i)入度为0 者进栈,while(!StackEmpty(&S))栈不为空时,调用Pop(&sS,&n)输出栈中顶点并将以该顶点为起点的边删除,入度indegree[k]--,当输出某一入度为0 的顶点时,便将它从栈中删除。 第三部分,主函数,先后调用void CreatGraph(ALGraph *G)函数构建图、 void TopologicalSort(ALGraph *G)函数输出拓扑排序实现整个程序。 3.设计的主程序流程 开始 调用建图函数 输入顶点数、弧数、顶点值 输入存在弧的两个顶点 建零入度顶点栈 S, 入度为 0 者进栈 !StackEmpty (&S) 判断并输出相应信息 结束 Pop(&S,&n) P=G.v ertices[n].firstarc P!=NULL K=P->adjv es !(--indegree[k]) P=p->nex tarc Pu sh(&S,k); 三 详细设计 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; //该弧所指向的顶点的位置// struct ArcNode *nextarc; //指向下一条弧的指针// }ArcNode; //*表结点*// typedef struct...

1、当您付费下载文档后,您只拥有了使用权限,并不意味着购买了版权,文档只能用于自身使用,不得用于其他商业用途(如 [转卖]进行直接盈利或[编辑后售卖]进行间接盈利)。
2、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。
3、如文档内容存在违规,或者侵犯商业秘密、侵犯著作权等,请点击“违规举报”。

碎片内容

拓扑排序课程设计报告

确认删除?
VIP
微信客服
  • 扫码咨询
会员Q群
  • 会员专属群点击这里加入QQ群
客服邮箱
回到顶部