数据结构课程设计

课程设计报告。

课程名称数据结构

课题名称拓扑排序

专业。班级。

学号。姓名。

指导教师。20**年 *月 **日。

课程设计任务书。

一）课程设计题目：拓扑排序。

二）问题描述：

大学期间各专业都要制订相应的教学计划。每个专业开设的课程预先已确定。而各门课程间有的是相互独立的，而有的则有先修后修的限定。

试设计相应的课程设置程序，实现对某专业各学期的课程的排布，其中每门课需一定的课时，而各学期的总课时不能超过上限。

测试数据。学期课时上限数：350 各课程所需学时：48

课程先、后修关系如图：

三）答辩与评分标准。

指导老师负责验收程序的运行结果，并结合学生的工作态度、实际动手能力、创新精神和设计报告等进行综合考评，并按优秀、良好、中等、及格和不及格五个等级给出每位同学的课程设计成绩。具体考核标准包含以下几个部分：

1 平时出勤（占10%）

2 系统需求分析、功能设计、数据结构设计及程序总体结构合理与否（占10%）

3 程序能否完整、准确地运行，个人能否独立、熟练地调试程序（占40%）

4 设计报告（占30%）

注意：不得抄袭他人的报告（或给他人抄袭），一旦发现，成绩为零分。

5 独立完成情况（占10%）。

6 运行所设计的系统。

目录。1.封面1

2.任务书3

3.目录44.正文5

5.附件13

6. 评分表17

正文。一．需求分析：

本次课程设计要求是：用邻接表存储图，然后进行拓扑排序，输出拓扑排序序列。

1. 拓扑排序的基本思想为：

1 在有向图中选一个没有前驱的顶点输出；

2 从图中删除该顶点和所有以它为尾的弧。

3 重复1,2直到全部顶点均已输出，或者当前图中不存在无前驱的顶点为止；

4 若此时输出的顶点数小于有向图中的顶点数，则说明有向图中存在回路，否则输出的顶点的顺序即为一个拓扑序列。

2. 基于邻接表的存储结构。

入度为零的顶点即为没有前驱的顶点，我们可以附设一个存放各顶点入度的数组indegree[ ]于是有。

1）找g中无前驱的顶点——查找indegree[i]为零的顶点vi；

2）删除以i为起点的所有弧——对链在顶点i后面的所有邻接顶点k，将对应的indegree[k] 减1。

为了避免重复检测入度为零的顶点，可以再设置一个辅助栈，若某一顶点的入度减为0，则将它入栈。每当输出某一入度为0的顶点时，便将它从栈中删除。

3. 基本要求。

1) 输入的形式和输入值的范围；

首先是输入要排序的顶点数和弧数，都为整型，中间用空格隔开；再输入各顶点的值，为整型，中间用分隔符隔开；然后输入各条弧的两个顶点值，先输入弧头，再输入弧尾，中间用空格隔开，输入的值只能是开始输入的顶点值否则系统会提示输入的值的顶点值不正确，请重新输入，只要继续输入正确的值就行。

2) 输出的形式；

首先输出建立的邻接表，然后是最终各顶点的出度数，再是拓扑排序的序列，并且每输出一个顶点，就会输出一次各顶点的入度数。

3) 程序所能达到的功能；

因为该程序是求拓扑排序，所以算法的功能就是要输出拓扑排序的序列，在一个有向图中，若用顶点表示活动，有向边就表示活动间先后顺序，那么输出的拓扑序列就表示各顶点间的关系为反映出各点的存储结构，以邻接表存储并输出各顶点的入度。

二概要设计。

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)函数输出拓扑排序实现整个程序。

三：详细设计：

1 实现概要设计中定义的所有数据类型。

#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 vnode

char data顶点信息。

arcnode *firstarc指向第一条依附该顶点的弧的指针//

vnode,adjlist[max_vextex_num];

typedef struct

adjlist vertices

int vexnum, arcnum图的当前顶点数和弧数//

algraph;

typedef struct构建栈//

elemtype *base;//在栈构造之前的指针*//

elemtype *top;//栈顶指针*//

int stacksize;//定义所分配的存储空间*//

sqstack;//顺序栈*//

2.算法和各模块的**。

程序中各函数算法思想如下：

2.1 void initstack(sqstack *s)

初始化栈将栈的空间设为 stack-init-size。

2.2 int pop(sqstack *s,elemtype *e)

出栈操作，若站不空，删除s的栈顶元素，用e返回其值，并返回ok；否则返回error。

2.3 void push(sqstack *s,elemtype e)

进栈操作，插入元素e为新的栈顶元素。

2.4 int stackempty(sqstack *s)

判断栈是否为空，语句if (s->top=s->base )判断，若栈不为空，则删除s的栈顶元素，并返回ok；否则返回error。

2.5 void creatgraph (algraph *g)

构建图，用邻接表存储，首先定义邻接表指针变量，输入顶点数和弧数，初始化邻接表，将表头向量域置空，输入存在弧的点集合，当输入顶点值超出输入值的范围就会出错，否则依次插入进邻接表，最后输出建立好的邻接表。

2.6 void findindegree(algrap g, int indegreee)

求入度操作，设一个存放各顶点入度的数组indegreee，然后。

indegreee[i]=0赋初值，for循环indegreee+存储入度数。

2.7 void topologicalisort(algraph g)

输出拓扑排序函数。其思路是若g无回路，则输出g的顶点的一个拓扑序列并返回ok，否则返回error。首先由于邻接表的存储结构入度为零的顶点即为没有前驱的顶点，我们可以附设一个存放个顶点入度的数组，调用findindegree( g, indegreee)对各顶点求入度；为了避免重复检测入度为零0的顶点，设置一个栈，调用initstack(&s)初始化栈，在调用push(&s,i)入度为0者进栈，while(!

stackempty(&s))栈不为空时，调用pop(&ss,&n)输出栈中顶点并将以该顶点为起点的边删除，入度indegree[k]--当输出某一入度为0的顶点时，便将它从栈中删除。

数据结构课程设计

数据结构课程设计

数据结构课程设计

数据结构课程设计

其他用户还读了