数据结构课程设计-拓扑问题

数据结构课程设计题目:拓扑排序 学院：班级：学生姓名：学生学号：指导教师：课程设计任务书姓名班级学号设计题目拓扑排序理论要点拓扑排序是指由某个集合上的一个偏序得到该集合上的一个全序。更直观地讲，一个偏序是自反的、反对称的，用图表示时每个点都有环且只有单向边。设计目标拓扑排序的任务是在这个偏序上得到一个全序，即得到一个完成整个项目的各步骤的序列。研究方法步骤在有向图中选一个没有前驱的顶点且输出之。从图中删除该顶点和所有以它为尾的弧。预期结果直至全部顶点均已输出，或者当前图中不存在无前驱的顶点。计划与进步的安排按时并分部完成任务。PAGEII摘要拓扑排序是有向无环图的一种重要应用,实现算法与数据结构关系密切,本文以邻接表作为图的存储结构,详细讨论了拓扑排序算法在计算机上的实现方法,并对该算法作了必要的分析。关键词拓扑排序，有向无环图，邻接表目录摘要 I课程设计题目 11需求分析 12概要设计 13详细设计 14调试分析 35用户使用说明 36测试结果 87结论 10参考文献 11数据结构课程设计13-拓扑排序1.需求分析拓扑排序是指由某个集合上的一个偏序得到该集合上的一个全序。更直观地讲，一个偏序是自反的、反对称的，用图表示时每个点都有环且只有单向边。拓扑排序的任务是在这个偏序上得到一个全序，即得到一个完成整个项目的各步骤的序列。2．概要设计：说明本程序中用到的所有抽象数据类型的定义、主程序的流程以及各程序模块之间的层次(调用)关系。概要设计（1）在有向图中选一个没有前驱的顶点且输出之。（2）从图中删除该顶点和所有以它为尾的弧。重复上述两步，直至全部顶点均已输出，或者当前图中不存在无前驱的顶点为止。后一种情况则说明有向图中存在环。具体的算法实现参照源程序。3.详细设计构造邻接表图：typedefstruct{ AdjListvertices; intvexnum,arcnum;}Graph;//邻接表图为了避免重复检测入度为零的顶点，源程序中设了一个栈，暂存所有入度为零的顶点：typedefstructstack{int*base; int*top; intstacksize;}sqstack;//栈的结构，存储图的顶点序号算法的流程图开始设辅助数组indegree记录图的各顶点的入度值，并将indegree数组各变量赋初值。输入图的顶点数、边数建立一个栈，存储图的顶点的序号用邻接表法建图，并计算出indegree数组中各变量值开始设辅助数组indegree记录图的各顶点的入度值，并将indegree数组各变量赋初值。输入图的顶点数、边数建立一个栈，存储图的顶点的序号用邻接表法建图，并计算出indegree数组中各变量值根据indegree数组将入度为0的顶点入栈count对输出顶点计数0=>count栈不空删除栈顶元素,赋给icount++将与第i个顶点链接的各顶点入度减1输出第i个顶点值顶点入度为0顶点序号入栈count<G.vexnum输出“拓扑排序成功”输出“拓扑排序不成功”结束4．调试分析（1）它的时间复杂度是O(G.vexnum+G.arcnum)。（2）整个程序的关键就是采用尾插法创的邻接表图，运用栈来实现各个数值的输入输出及存储。（3）注意*的使用，并不是什么情况下都用*，它有时候会造成数据破坏，利用破坏的值进行运算，结果可想而知，所以，如果没返回值时，一般不要用。（4） 为了避免重复检测入度为零的顶点，源程序中设了一个栈，暂存所有入度为零的顶点，此程序段书写如下： InitStack(S); for(i=0;i<G.vexnum;++i)//建零入度顶点栈S if(!indegree[i])Push(S,i);//入度为0者进栈 count=0;//对输出顶点计数 while(!StackEmpty(S)){ Pop(S,i);printf(i,G.vertices[i].data);++count;//输出i号顶点并计数 for(p=G.vertices[i].firstarc;p;p=p->next){ k=p->adj;//对i号顶点的每个邻接点的入度减1 if(!(--indegree[k]))Push(S,k);//一旦入度为0，则入栈 }//for }//while5．用户使用说明//采用尾插法创的邻接图#include<iostream>usingnamespacestd;constintMAX=20;constintSTACK_INIT_SIZE=100;constintERROR=0;typedefstructstack{int*base;int*top;intstacksize;}sqstack;//栈的结构，存储图的顶点序号typedefstructlnode{intadjvex;structlnode*next;}ArcNode;//弧结点typedefstructnode2{chardata;ArcNode*fristarc;}VNode,AdjList[MAX];//顶点数组,fristarc指向与顶点邻接的第一条弧typedefstruct{ AdjListvertices; intvexnum,arcnum;}Graph;//邻接表图voidInitstack(sqstack&s){ s.base=newint; if(!s.base) exit(0); s.top=s.base; s.stacksize=STACK_INIT_SIZE;}voidPush(sqstack&s,int&e){ *s.top++=e;}intEmptystack(sqstack&s){ if(s.base==s.top) return1; else return0;}intPop(sqstack&s,int&e){ if(s.base==s.top) returnERROR; e=*--s.top;}voidCreatGraph(Graph&G,int*indegree){inti;cout<<"请输入图的顶点数和弧数(且顶点数不能超过"<<MAX<<")"<<endl;cin>>G.vexnum>>G.arcnum; cout<<"请输入顶点值:"<<endl; for(inti=0;i<G.vexnum;i++)//输入图的顶点 { cin>>G.vertices[i].data; G.vertices[i].fristarc=NULL; indegree[i]=0; } for(i=0;i<G.arcnum;i++)//输入图的弧 { intm,n; ArcNode*p; cout<<"请输入第"<<i+1<<"条弧的弧尾和弧头:"<<endl; cin>>m>>n; p=newArcNode; if(!p) exit(0); indegree[n-1]++;//求每个顶点的入度值 p->adjvex=n-1; p->next=G.vertices[m-1].fristarc; G.vertices[m-1].fristarc=p; }}intToposort(Graph&G,int*indegree){inti; sqstackS; Initstack(S); for(inti=0;i<G.vexnum;i++)//0入度顶点入栈 { if(!indegree[i]) Push(S,i); } intcount=0; while(!Emptystack(S)) { Pop(S,i); cout<<G.vertices[i].data<<""; count++;//记录输出的顶点数 for(ArcNode*p=G.vertices[i].fristarc;p;p=p->next)//把与顶点 { //相邻接的顶点的入度 intk=p->adjvex; if(!(--indegree[k])) Push(S,k); } } if(count<G.vexnum) return0; else return1;} intmain(){GraphG; int*indegree; indegree=newint;CreatGraph(G,indegree); if(!Toposort(G,indegree)) { cout<<endl; cout<<"拓扑排序不成功!"<<endl; } else { cout<<endl; cout<<"拓扑排序成功!"<<endl; } system("pause"); return0;}测试结果第一组结果（有向无环图）：对应的图如下：115432第二组结果（有向有环图）：对应的图如下：115432结论做一个课程设计要注意很多方面，无论是格式，还是书写的内容和要表达的思想都得严格要求自己，所以做起来真的不算容易。本次课程设计涉及了很多知识，由于往日没有学得很扎实，对某些问题仍然比较疑惑，所以要进行充足的补习。数据结构及其算法在解决现实生活中的常见问题和书写软件设计方面上都有着重要的意义，我们应该好好掌握它的相关知识，在以后的学习过程中，更多的去学会如何运用知识。8.参考文献傅清祥,王晓东.算法与数据结构,电子工业出版社,1993严蔚敏,吴伟民.数据结构,清华大学出版社,1997许卓群,张乃孝,杨冬青.唐世渭«数据结构»,高等教育出版社,1988张友生,远程控制编程技术.电子工业出版社.2002陆丽娜,伍卫国等译.分布式操作系统.电子工业出版社.2002王达,计算机网络远程访问与远程启动.清华大学出版社.2003课程设计评阅书课程设计报告评语：（评阅意见主要对设计任务的合理性、规范性和正确性以及设计报告书的完整性、规