目录
一．需求分析说明 (1)
二．概要设计说明 (1)
三．详细设计说明 (2)
四．调试分析 (6)
五．用户使用说明 (6)
六．课程设计总结 (7)
七．测试结果 (8)
八．参考书目 (9)
九. 附录 (10)
一、需求分析说明
为了更好的学习数据结构，深刻理解数据结构在解决实际问题中的应用，体会其重要性，熟练掌握线性表、栈和队列、串、数组、树、图等常用的数据结构，熟悉各自的特点和应用场合。
同时锻炼自己独立分析理解问题的能力，学会根据不同的问题选择合适的数据结构，然后结合适当的算法解决问题。锻炼自己的设计和编写程序的技巧，进一步调试和测试自己所写的程序，使其功能更加完善，养成较好的编写程序习惯。
提高综合运用所学的理论知识和方法独立分析和解决问题的能力，训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。本课程设计的目的就是要达到理论与实际应用相结合，使同学们能够根据数据对象的特性，学会数据组织的方法，能把现实世界中的实际问题在计算机内部表示出来，并培养基本的、良好的程序设计技能。
设计的基本要求：1）选择邻接表作为有向图的存储结构模拟整个过程，并输出拓扑排序的顶点序列。2）给出逆向的拓扑有序序列。
二、概要设计说明
2.1 算法思想
采用邻接表存储结构实现有向图；有向图需通过顶点数、边数、顶点以及边等信息建立。
拓扑排序算法大体思想为：
1)遍历有向图各顶点的入度，将所有入度为零的顶点入栈；
2)栈非空时，输出一个顶点，并对输出的顶点数计数；
3)该顶点的所有邻接点入度减一，若减一后入度为零则入栈；
4)重复2)、3)，直到栈为空，若输出的顶点数与图的顶点数相等则该图可拓扑排序，否则图中有环；
5)重复2)、3)、4)直到序列中所有元素均被遍历，则该序列是拓扑序列，否则不是拓扑序列。
2.2 系统功能模块结构图
本程序包括拓扑排序模块和拓扑排序核心算法模块。
3.1
3.2 数据结构
1）图
typedef struct stack{
int *base;
int *top;
int stacksize;
}sqstack;//栈的结构，存储图的顶点序号
typedef struct lnode
{
int adjvex;
struct lnode *next;
}ArcNode;//弧结点
typedef struct node2
{
int data;
ArcNode *fristarc;
}VNode,AdjList[MAX];//顶点数组,fristarc指向与顶点邻接的第一条弧typedef struct{
AdjList vertices;
int vexnum,arcnum;
}Graph;//邻接表图
void CreatGraph(Graph &G,int *indegree)
{
cout<<"请输入图的顶点数和边数(且顶点数不能超过"<cin>>G.vexnum>>G.arcnum;
cout<<"请输入各个顶点值(整形):"<for(int i=0;i{
cin>>G.vertices[i].data;
G.vertices[i].fristarc=NULL;
indegree[i]=0;
}
for(i=0;i{
int m,n;
ArcNode *p;
cout<<"请输入第"<cin>>m>>n;
p=new ArcNode;
if(!p)
exit(0);
indegree[n-1]++;//求每个顶点的入度值
p->adjvex=n-1;
p->next=G.vertices[m-1].fristarc;
G.vertices[m-1].fristarc=p;
}
}
2)栈
void Initstack(sqstack &s)
{
s.base=new int;
if(!s.base)
exit(0);
s.top=s.base;
s.stacksize= STACK_INIT_SIZE;
}
void Push(sqstack &s,int &e)
{
*s.top++=e;
}
int Emptystack(sqstack &s)
{
if(s.base==s.top)
return 1;
else
return 0;
}
int Pop(sqstack &s,int &e)
{
if(s.base==s.top)
return ERROR;
e=*--s.top;
}
3.3 具体实现函数
1）程序所需头文件及全局变量
#include
using namespace std;
const int MAX=30;
const int STACK_INIT_SIZE=100;
const int ERROR=0;
2）栈的操作
①void Initstack(sqstack &s)
功能：初始化栈，构造一个空栈S
参数：S待初始化的栈
②i nt Emptystack(sqstack &s)
功能：判断栈是否为空
参数：S 待判断的栈
返回值：栈为空返回1，栈非空返回0
③void Push(sqstack &s,int &e)
功能：元素入栈
参数：S 待操作的栈：插入元素e为新的栈顶元素
④int Pop(sqstack &s,int &e)
功能：元素出栈
参数：S 待操作的栈：若栈不空，则删除S的栈顶元素，用e返回其值，并返回1，否则返回0
3）图的建立
void CreatGraph(Graph &G,int *indegree)
功能：建立有向图，并记录每个节点的入度值
参数：G 待建立的图：用indegree记录节点的入度值
4）拓扑排序
int Toposort(Graph &G,int *indegree)
功能：对有向图进行拓扑排序，对排序结果进行顺序和逆序输出
参数：G 待排序的图：indegree是节点的入度值
5）主函数
int main()
对各个函数进行调用，实现程序功能
判断是否排序成功
