数据结构课程报告书

1、数 据 结 构课程设计报告书设计题目： 安排教学计划 专 业: 计算机科学与技术(师范) 班 级： 10 级 1 班 姓 名： 关莹(李瑞男) 指导教师： 孙 蕾 目录1、问题描述22、基本要求23、测试数据24、算法思想35、模块划分36、数据结构57、源程序58、界面设计149、运行与测试1410、总结1911、思考与感悟191、问题描述学校每个学期开设的课程是有先后顺序的，如计算机专业：开设数据结构课程之前，必须先开设C语言程序设计和离散数学课程，这种课程开设的先后顺序关系称为先行、后继课程关系。现在需要根据给定的课程信息及课程之间的先行、后继关系，合理安排出开设各门课程的先后顺序。2、

2、基本要求1)对输入的课程先行、后继关系如果存在回路关系时应提示出现错误。2)根据读入的课程信息及其先行、后继关系，计算出安排教学计划的序列。3)输出教学计划的安排顺序或给出错误提示信息。3、测试数据正确结果：输入：顶点数6，弧数7。顶点为A、B、C、D、E、F。顶点关系为 A B、A C、B C、C D、C E、D E、E F。 输出：A-B-C-D-E-F错误结果1）输入：顶点数1，弧数5。 输出：顶点数或弧数不正确，有向图建立失败！2）输入：顶点数6，弧数8。 顶点为A、B、C、D、E、F。 顶点关系为A B、AG。 输出：顶点G不存在，有向图建立失败！3）输入：顶点数6，弧数8。 顶点为

3、A、B、C、D、E、F。 顶点关系为A B、A C、B C、C D、C E、D E、E F、F D。 输出：该有向图有回路，无法完成拓扑排序。4、算法思想1、采用邻接表存储结构实现有向图；有向图需通过顶点数、弧数、顶点以及弧等信息建立。2、拓扑排序算法void TopologicalSort(ALGraph G) 中，先输出入度为零的顶点，然后输出新的入度为零的顶点，此操作利用栈实现。3、拓扑排序算法void TopologicalSort(ALGraph G)，大体思想为： 1)遍历有向图各顶点的入度，将所有入度为零的顶点入栈； 2)栈非空时，输出一个顶点，并对输出的顶点数计数； 3)该顶点

4、的所有邻接点入度减一，若减一后入度为零则入栈； 4)重复2)、3)，直到栈空，若输出的顶点数与图的顶点数相等则该图可拓扑排序，否则图中有环；5、模块划分1、顺序栈操作1) void Initstack(ssqstack *S)功能：初始化顺序栈2) int emptystack(sqstack S)功能：判断栈空。栈空返回 1；栈非空返回 03) int push(sqstack *S,ElemType e)功能：元素入栈4) int pop(sqstack *S,ElemType *e)功能：元素出栈2、有向图(DAG)邻接表存储结构(ALG)的操作1) int LocateVex(ALGr

5、aph G,VertexType v)功能：顶点在头结点数组中的定位2) int CreateGraph(ALGraph *G)功能：建立图。函数内包含了由用户输入顶点数、弧数、顶点以及弧的操作错误判断：包含顶点数、弧数是否正确的判断；包含用户输入的弧的顶点是否存在的判断3) void PrintGraph(ALGraph G)功能：输出有向图4) int CreateGraph2(ALGraph *G)功能：建立预置课程图（输出函数内预置课程信息，并自动建立有向图）图建立成功返回1；图建立失败返回0错误判断：包含顶点数、弧数是否正确的判断。包含弧的顶点是否存在的判断3、拓扑排序1) void

6、 TopologicalSort(ALGraph G)功能：实现拓扑排序错误判断：包含有向图是否有回路的判断4、主函数void main()功能：主函数。利用while语句和switch语句实现菜单化调用函数各模块之间的调用关系图：主函数拓扑排序有向图邻接表顺序栈6、数据结构1、顺序栈的存储类型为：typedef int ElemType;typedef struct QNodeint top;ElemType *base;Int stacksize; QNode,sqstack;理由：用栈来存储入度为0的顶点，符合栈先进后出的特点。 2、图的类型（邻接表存储结构）为：typedef char

7、 VertexType20;/顶点信息（名称）typedef struct ArcNode/链表结点int vexpos;/该弧所指向的顶点在数组中的位置struct ArcNode *next;/指向当前起点的下一条弧的指针ArcNode;typedef struct VNode/头结点VertexType name;/顶点信息（名称）int indegree;/顶点入度ArcNode *firstarc;/指向当前顶点的第一条弧的指针VNode,AdjListMAXVEX;typedef structAdjList vexhead;/邻接表头结点数组int vexnum,arcnum;/图

8、的顶点数和弧数ALGraph;理由：此程序的有向图为稀疏图，符合邻接表的特点。7、源程序(1)程序中包括的文件清单：1.c(2)文件中包括的函数清单：1）顺序栈：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#include string.h/字符数组/*/* 以下为顺序栈操作 */*/* 定义顺序栈类型

9、*/#define MAXNUM 30#define INITSIZE 100typedef int ElemType;typedef struct QNodeint top;ElemType *base; int stacksize;QNode,sqstack;/* 1.初始化 */void Initstack(sqstack *S)S-base=(ElemType *)malloc(INITSIZE*sizeof(ElemType);S-top=0;S-stacksize=INITSIZE;/* 2.判断栈空 */int emptystack(sqstack S)if(S.top=0)re

10、turn 1;else return 0; /* 3.入栈 */int push(sqstack *S, ElemType e)if(S-top=S-stacksize);S-base=(ElemType *)realloc(S-base,(S-stacksize+1) *sizeof(ElemType);if(!S-base) return 0;S-stacksize+;S-baseS-top+=e;return 1;/* 4.出栈 */int pop(sqstack *S,ElemType *e)/*e记录出栈元素的变量/int i; if(S-top=0) return 0;*e=S-b

11、ase-S-top;return 1;/*/* 以下为有向图(DAG)邻接表存储结构(ALG)的操作 */*/#define MAXVEX 30 /最大顶点个数#define MAXNAME 20typedef char VertexType20; /顶点信息（名称）/* 图的类型定义（邻接表存储结构） */typedef struct ArcNode /链表结点int vexpos; /该弧所指向的顶点在数组中的位置struct ArcNode *next; /指向当前起点的下一条弧的指针ArcNode;typedef struct VNode /头结点VertexType name; /顶

12、点信息（名称）int indegree; /顶点入度ArcNode *firstarc; /指向当前顶点的第一条弧的指针VNode,AdjListMAXVEX;typedef structAdjList vexhead; /邻接表头结点数组int vexnum,arcnum; /图的顶点数和弧数ALGraph;/* 5.顶点在头结点数组中的定位 */int LocateVex(ALGraph G,VertexType v)/G带操作的图；v要在图中定位的顶点int i;for(i=0;iG.vexnum;i+)if(strcmp(v,G.)=0) break;retu

13、rn i; /顶点存在则返回在头结点数组中的下标；否则返回图的定点数/* 6.建立图（邻接表） */int CreateGraph(ALGraph *G) /成功建立返回1，不成功则返回0int i,j,k; VertexType v1,v2;ArcNode *newarc;printf(n输入有向图顶点数和弧数vexnum,arcnum:); /输入顶点数和弧数scanf(%d,%d,&(*G).vexnum,&(*G).arcnum); /输入并判断顶点数和弧数是否正确if(*G).vexnum0|(*G).arcnum(*G).vexnum*(*G).vexnum-1)printf(n顶

14、点数或弧数不正确，有向图建立失败！n);return 0; printf(n输入 %d 个顶点:,(*G).vexnum); /输入顶点名称for(i=0;i(*G).vexnum;i+)scanf(%s,(*G).); printf(n顶点列表:n共有%d个顶点: ,(*G).vexnum);/输出顶点名称for(i=0;i(*G).vexnum;i+)printf(%s ,(*G).);for(i=0;i(*G).vexnum;i+) /邻接表初始化(*G).vexheadi.firstarc=NULL;(*G).vexheadi.ind

15、egree=0;printf(nn输入 %d 条边:vi vjn,(*G).arcnum); /输入有向图的边for(k=0;k=(*G).vexnum)printf(顶点%s不存在，有向图建立失败！n,v1);return 0; if(j=(*G).vexnum)printf(顶点%s不存在，有向图建立失败！n,v2);return 0; newarc=(ArcNode*)malloc(sizeof(ArcNode); /前插法建顶点链表newarc-vexpos=j;if(*G).vexheadi.firstarc=NULL)newarc-next=NULL;(*G).vexheadi.f

16、irstarc=newarc; elsenewarc-next=(*G).vexheadi.firstarc-next;(*G).vexheadi.firstarc-next=newarc; (*G).vexheadj.indegree+; /对应顶点入度计数加1printf(n有向图建立成功！n);return 1;/* 7.按邻接表方式输出有向图 */void PrintGraph(ALGraph G)int i;ArcNode *p;printf(n输出有向图:n);for(i=0; );p=p-next; printf(n);/为避免演示时要输入过多数据，以下函

17、数将课程编号、课程间的先后关系通过数组预置/* 8.建立预置课程图（邻接表） */int CreateGraph2(ALGraph *G) /成功建立返回1，不成功则返回0int i,j,k;VertexType v1,v2;ArcNode *newarc;VertexTypeSubjectName12=C1,C2,C3,C4, /课程名称C5,C6,C7,C8,C9,C10,C11,C12 ,RelationV116=C1,C1,C2,C1, /基础课C3,C4,C11,C5,C3,C3,C6,C9,C9,C9,C10,C11,RelationV216=C2,C3,C3,C4, /以上面课程

18、为基础的课C5,C5,C6,C7,C7,C8,C8,C10,C11,C12,C12,C12,;/*/system(PAUSE);(*G).vexnum=12;(*G).arcnum=16;if(*G).vexnum0|(*G).arcnum(*G).vexnum*(*G).vexnum-1)printf(n课程数或先后关系不正确，有向图建立失败！n);return 0; /判断课程数和弧数是否正确for(i=0;i(*G).vexnum;i+)strcpy(*G).,SubjectNamei); for(i=0;i(*G).vexnum;i+) /邻接表初始化(*G)

19、.vexheadi.firstarc=NULL;(*G).vexheadi.indegree=0; for(k=0;k=(*G).vexnum)printf(课程%s不存在，有向图建立失败！n,v1);return 0; if(j=(*G).vexnum)printf(课程%s不存在，有向图建立失败！n,v2);return 0; newarc=(ArcNode*)malloc(sizeof(ArcNode); /前插法建课程链表newarc-vexpos=j;if(*G).vexheadi.firstarc=NULL)newarc-next=NULL;(*G).vexheadi.firsta

20、rc=newarc; elsenewarc-next=(*G).vexheadi.firstarc-next;(*G).vexheadi.firstarc-next=newarc; (*G).vexheadj.indegree+; /对应课程入度计数加1printf(n有向图建立成功！n);return 1;/*/* 以下为拓扑排序算法 */*/* 9.拓扑排序 */void TopologicalSort(ALGraph G)int i,k,count;ElemType e;ArcNode *p;/弧结点，指向边表结点的指针sqstack S; /*定义栈*/Initstack(&S);fo

21、r(i=0; i,G.);count+; /对输出的顶点计数for(p=G.vexheade.firstarc;p;p=p-next) /遍历当前课程的邻接点k=p-vexpos; /邻接点位置if(!(-G.vexheadk.indegree) /每个邻接点入度减1后若为零则入栈push(&S,k);printf(n);if(countG.vexnum)printf(n该有向图有回路，无法完成拓扑排序！n); void main()ALGraph G;int menu;while(1)printf(n*n);printf(*1.建立有向图并求一个拓扑排序序列 *n);printf(*2.清屏 *n);printf(*3.退出 *n);printf(*n);printf(请输入你的选择:);scanf(%d,&menu);switch(menu)case 1:if(CreateGraph(&G) /有向图建成则执操作system(PAUSE);/暂停，等待用户按键PrintGraph(G);system(PAUSE);/按邻接表方式输出有向图TopologicalSort(G); /拓扑排序break;case 2:system(CLS);/清屏break;case 3:return;/退出当前函数，返回调用点8