数据结构课程报告书.docVIP

《数 据 结 构》 课程设计报告书 设计题目： 专 业计算机科学与技术 班 级：级班 姓 名： 指导教师： 目录 1、问题描述 2 2、基本要求 2 3、测试数据 2 4、算法思想 3 5、模块划分 3 6、数据结构 5 7、源程序 5 8、界面设计 14 9、运行与测试 14 10、总结 19 11、思考与感悟 19 1、1、void TopologicalSort(ALGraph G) 中，先输出入度为零的顶点，然后输出新的入度为零的顶点，此操作利用栈实现。 3、拓扑排序算法void TopologicalSort(ALGraph G)，大体思想为： 1)遍历有向图各顶点的入度，将所有入度为零的顶点入栈； 2)栈非空时，输出一个顶点，并对输出的顶点数计数； 3)该顶点的所有邻接点入度减一，若减一后入度为零则入栈； 4)重复2)、3)，直到栈空，若输出的顶点数与图的顶点数相等则该图可拓扑排序，否则图中有环； 5、模块划分 1、顺序栈操作 1) void Initstack(ssqstack *S) 功能：初始化2) int emptystack(sqstack S) 功能：判断3) int push(sqstack *S,ElemType e) 功能：元素入4) int pop(sqstack *S,ElemType *e) 功能：元素出2、有向图(DAG)邻接表存储结构(ALG)的操作 int LocateVex(ALGraph G,VertexType v) 功能：顶点在头结点数组中的定位int CreateGraph(ALGraph *G) 功能：建立图 3) void PrintGraph(ALGraph G) 功能：输出有向图int CreateGraph2(ALGraph *G) 功能：建立预置课程图 3、拓扑排序 void TopologicalSort(ALGraph G) 功能：实现拓扑排序 4、主函数 void main()主函数用while和switch 各模块之间的调用关系图： 6、数据结构 1、顺序栈的存储类型为： typedef int ElemType; typedef struct QNode { int top; ElemType *base; Int stacksize; } QNode,sqstack; 理由：用栈来存储入度为0的顶点，符合栈先进后出的特点。 2、图的类型（邻接表存储结构） typedef char VertexType[20];//顶点信息（名称） typedef struct ArcNode//链表结点 {int vexpos;//该弧所指向的顶点在数组中的位置 struct ArcNode *next;//指向当前起点的下一条弧的指针 }ArcNode; typedef struct VNode//头结点 {VertexType name;//顶点信息（名称）int indegree;//顶点入度 ArcNode *firstarc;//指向当前顶点的第一条弧的指针 }VNode,AdjList[MAXVEX]; typedef struct { AdjList vexhead;//邻接表头结点数组 int vexnum,arcnum;//图的顶点数和弧数 }ALGraph; 理由：此程序的有向图为稀疏图，符合邻接表的特点。 7、源程序 (1)程序中包括的文件清单(2)文件中包括的函数清单void Initstack(ssqstack *S) 2）有向图邻接表：void PrintGraph(ALGraph G) int CreateGraph2(ALGraph *G) 3）拓扑排序：void TopologicalSort(ALGraph G) (3)源程序 #include stdlib.h #include stdio.h /*******************************************/ /* 以下为顺序栈操作 */ /*******************************************/ /* 定义顺序栈类型 */ #define MAXNUM 30 #define INITSIZE 100 typedef int ElemType; typedef struct QNode { int