数据结构课程设计拓扑排序顺序逆序输出Word格式.docx
- 文档编号:7425321
- 上传时间:2023-05-08
- 格式:DOCX
- 页数:17
- 大小:75.49KB
数据结构课程设计拓扑排序顺序逆序输出Word格式.docx
《数据结构课程设计拓扑排序顺序逆序输出Word格式.docx》由会员分享,可在线阅读,更多相关《数据结构课程设计拓扑排序顺序逆序输出Word格式.docx(17页珍藏版)》请在冰点文库上搜索。
5)重复2)、3)、4)直到序列中所有元素均被遍历,则该序列是拓扑序列,否则不是拓扑序列。
2.2系统功能模块结构图
本程序包括拓扑排序模块和拓扑排序核心算法模块。
拓扑排序模块
拓扑排序核心算法
显示排序结果
判断是否有环
栈操作
求顶点入度
0入度出栈,其余顶点入度-1
否
是
开始
输入顶点及边的信息
符合条件
根据输入信息建立邻接表,建立有向图
建立栈
在邻接表中寻找入度为0的顶点,将其顺序入栈
进行拓扑排序,将栈顶元素找出出栈,并输出。
将与栈顶元素邻接的顶点的入度减一
栈是否为空
结束
三、详细设计说明
3.1系统流程设计
3.2数据结构
1)图
typedefstructstack{
int*base;
int*top;
intstacksize;
}sqstack;
//栈的结构,存储图的顶点序号
typedefstructlnode
{
intadjvex;
structlnode*next;
}ArcNode;
//弧结点
typedefstructnode2
intdata;
ArcNode*fristarc;
}VNode,AdjList[MAX];
//顶点数组,fristarc指向与顶点邻接的第一条弧
typedefstruct{
AdjListvertices;
intvexnum,arcnum;
}Graph;
//邻接表图
voidCreatGraph(Graph&
G,int*indegree)
cout<
<
"
请输入图的顶点数和边数(且顶点数不能超过"
MAX<
个)"
endl;
cin>
>
G.vexnum>
G.arcnum;
请输入各个顶点值(整形):
for(inti=0;
i<
G.vexnum;
i++)//输入图的顶点
{
cin>
G.vertices[i].data;
G.vertices[i].fristarc=NULL;
indegree[i]=0;
}
for(i=0;
i++)//输入图的边
intm,n;
ArcNode*p;
cout<
请输入第"
i+1<
条边的头结点和尾结点:
m>
n;
p=newArcNode;
if(!
p)
exit(0);
indegree[n-1]++;
//求每个顶点的入度值
p->
adjvex=n-1;
next=G.vertices[m-1].fristarc;
G.vertices[m-1].fristarc=p;
}
2)栈
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&
if(s.base==s.top)
return1;
else
return0;
intPop(sqstack&
returnERROR;
e=*--s.top;
3.3具体实现函数
1)程序所需头文件及全局变量
#include<
iostream>
usingnamespacestd;
constintMAX=30;
constintSTACK_INIT_SIZE=100;
constintERROR=0;
2)栈的操作
voidInitstack(sqstack&
功能:
初始化栈,构造一个空栈S
参数:
S待初始化的栈
intEmptystack(sqstack&
判断栈是否为空
S待判断的栈
返回值:
栈为空返回1,栈非空返回0
voidPush(sqstack&
元素入栈
S待操作的栈:
插入元素e为新的栈顶元素
④intPop(sqstack&
元素出栈
若栈不空,则删除S的栈顶元素,用e返回其值,并返回1,否则返回0
3)图的建立
建立有向图,并记录每个节点的入度值
G待建立的图:
用indegree记录节点的入度值
4)拓扑排序
intToposort(Graph&
对有向图进行拓扑排序,对排序结果进行顺序和逆序输出
G待排序的图:
indegree是节点的入度值
5)主函数
intmain()
对各个函数进行调用,实现程序功能
判断是否排序成功
4、调试分析
4.1数据测试
1、对存在环的有向图进行测试
有向图的顶点数和边数:
44
各顶点的值:
1234
第1条边12
第2条边的头结点和尾结点:
23
第3条边的头结点和尾结点:
34
第4条边的头结点和尾结点:
41
测试结果:
拓扑排序不成功。
2、对错误的输入结果进行测试
32
123
第1条边的头结点和尾结点:
12
14
运行错误,停止工作
4.2遇到的问题及修改
问题:
逆序输出的时候,输出结果不对。
错误:
没有将存放结点的数组逆序输出
修改:
逆序输出数组
for(intj=G.vexnum-1;
j>
=0;
j--)//拓扑排序的逆序
arr[j]<
"
;
5、用户使用说明
1请输入图的顶点数和边数(顶点数和边数之间用空格隔开,且顶点数不超过30)。
2请输入各顶点的值(整形)。
3请依次输入每条边的头结点和尾结点。
举了个例子并附上截图,使用方法一目了然
1
4
2
3
本例子对应的有向图为:
6、课程设计总结
这次课程设计使我进一步认识到数据结构在程序中的重要作用,拓扑排序在现实生活中有着广泛的应用,该算法核心比较简单,但循环思想却起着巨大的作用。
根据本课程设计的实验,从中学到了编程也是一项很有挑战性的工作,从很大程度上提高了我们对这门课程的了解和学习,并学会在实践中总结经验,从试验中找到方法,通过本次课程设计加深了对所学知识的理解。
大家都知道,编程是一件很需要耐心的事,因为几乎每一个程序的编写,都需要学习新的知识才能进行,同时程序调试过程很枯燥,有时候一点小错意味着长时间的查错。
完成本次设计之后,我加深了对程序结构的了解程度,对各种语句理解也更透彻,学会了灵活运用。
总之,受益匪浅。
7、测试结果
用上面的有向图进行测试
结果为:
8、参考书目
[1]数据结构,汤文兵,华东理工大学出版社
[2]数据结构——习题与解析,李春葆,清华大学出版社
9、附录
源程序代码
sqstackS;
Initstack(S);
int*arr=newint[G.vexnum];
//定义存放逆序的数组内存空间
i++)//0入度顶点入栈
indegree[i])
{
Push(S,i);
}
intcount=0;
intn=0;
//数组下标
拓扑排序的顺序输出为:
;
while(!
Emptystack(S))
Pop(S,i);
G.vertices[i].data<
arr[n]=G.vertices[i].data;
//将结点存入数组
n++;
count++;
//记录输出的顶点数
for(ArcNode*p=G.vertices[i].fristarc;
p;
p=p->
next)//把与顶点
{//相邻接的顶点的入度-1
intk=p->
adjvex;
if(!
(--indegree[k]))
Push(S,k);
拓扑排序的逆序输出为:
delete[]arr;
//释放内存,防止内存泄露
arr=NULL;
if(count<
G.vexnum)//判断是否存在环
return0;
else
return1;
}
intmain()
GraphG;
int*indegree;
indegree=newint;
CreatGraph(G,indegree);
Toposort(G,indegree))
拓扑排序不成功!
拓扑排序成功!
return0;
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 课程设计 拓扑 排序 顺序 逆序 输出