数据结构课程报告书

1《数据结构》课程设计报告书设计题目：安排教学计划专业:计算机科学与技术(师范)班级：10级1班姓名：关莹(李瑞男)指导教师：孙蕾2目录1、问题描述......................................................32、基本要求......................................................33、测试数据......................................................34、算法思想......................................................45、模块划分......................................................46、数据结构......................................................67、源程序..........................................................68、界面设计....................................................159、运行与测试.................................................1510、总结.........................................................1911、思考与感悟...............................................1931、问题描述学校每个学期开设的课程是有先后顺序的，如计算机专业：开设《数据结构》课程之前，必须先开设《C语言程序设计》和《离散数学》课程，这种课程开设的先后顺序关系称为先行、后继课程关系。现在需要根据给定的课程信息及课程之间的先行、后继关系，合理安排出开设各门课程的先后顺序。2、基本要求1)对输入的课程先行、后继关系如果存在回路关系时应提示出现错误。2)根据读入的课程信息及其先行、后继关系，计算出安排教学计划的序列。3)输出教学计划的安排顺序或给出错误提示信息。3、测试数据正确结果：输入：顶点数6，弧数7。顶点为A、B、C、D、E、F。顶点关系为AB、AC、BC、CD、CE、DE、EF。输出：A-B-C-D-E-F错误结果1）输入：顶点数1，弧数5。输出：顶点数或弧数不正确，有向图建立失败！2）输入：顶点数6，弧数8。顶点为A、B、C、D、E、F。顶点关系为AB、AG。输出：顶点G不存在，有向图建立失败！3）输入：顶点数6，弧数8。顶点为A、B、C、D、E、F。4顶点关系为AB、AC、BC、CD、CE、DE、EF、FD。输出：该有向图有回路，无法完成拓扑排序。4、算法思想1、采用邻接表存储结构实现有向图；有向图需通过顶点数、弧数、顶点以及弧等信息建立。2、拓扑排序算法voidTopologicalSort(ALGraphG)中，先输出入度为零的顶点，然后输出新的入度为零的顶点，此操作利用栈实现。3、拓扑排序算法voidTopologicalSort(ALGraphG)，大体思想为：1)遍历有向图各顶点的入度，将所有入度为零的顶点入栈；2)栈非空时，输出一个顶点，并对输出的顶点数计数；3)该顶点的所有邻接点入度减一，若减一后入度为零则入栈；4)重复2)、3)，直到栈空，若输出的顶点数与图的顶点数相等则该图可拓扑排序，否则图中有环；5、模块划分1、顺序栈操作1)voidInitstack(ssqstack*S)功能：初始化顺序栈2)intemptystack(sqstackS)功能：判断栈空。栈空返回1；栈非空返回03)intpush(sqstack*S,ElemTypee)功能：元素入栈4)intpop(sqstack*S,ElemType*e)功能：元素出栈2、有向图(DAG)邻接表存储结构(ALG)的操作1)intLocateVex(ALGraphG,VertexTypev)功能：顶点在头结点数组中的定位2)intCreateGraph(ALGraph*G)功能：建立图。函数内包含了由用户输入顶点数、弧数、顶点以及弧的操作错误判断：包含顶点数、弧数是否正确的判断；包含用户输入的弧的顶点是否存在的判断53)voidPrintGraph(ALGraphG)功能：输出有向图4)intCreateGraph2(ALGraph*G)功能：建立预置课程图（输出函数内预置课程信息，并自动建立有向图）图建立成功返回1；图建立失败返回0错误判断：包含顶点数、弧数是否正确的判断。包含弧的顶点是否存在的判断3、拓扑排序1)voidTopologicalSort(ALGraphG)功能：实现拓扑排序错误判断：包含有向图是否有回路的判断4、主函数voidmain()功能：主函数。利用while语句和switch语句实现菜单化调用函数各模块之间的调用关系图：主函数拓扑排序有向图邻接表顺序栈66、数据结构1、顺序栈的存储类型为：typedefintElemType;typedefstructQNode{inttop;ElemType*base;Intstacksize;}QNode,sqstack;理由：用栈来存储入度为0的顶点，符合栈先进后出的特点。2、图的类型（邻接表存储结构）为：typedefcharVertexType[20];//顶点信息（名称）typedefstructArcNode//链表结点{intvexpos;//该弧所指向的顶点在数组中的位置structArcNode*next;//指向当前起点的下一条弧的指针}ArcNode;typedefstructVNode//头结点{VertexTypename;//顶点信息（名称）intindegree;//顶点入度ArcNode*firstarc;//指向当前顶点的第一条弧的指针}VNode,AdjList[MAXVEX];typedefstruct{AdjListvexhead;//邻接表头结点数组intvexnum,arcnum;//图的顶点数和弧数}ALGraph;理由：此程序的有向图为稀疏图，符合邻接表的特点。7、源程序(1)程序中包括的文件清单：1.c(2)文件中包括的函数清单：1）顺序栈：voidInitstack(ssqstack*S)2）有向图邻接表：voidPrintGraph(ALGraphG)intCreateGraph2(ALGraph*G)3）拓扑排序：voidTopologicalSort(ALGraphG)(3)源程序#includestdlib.h7#includestdio.h#includestring.h//字符数组/*******************************************//*以下为顺序栈操作*//*******************************************//*定义顺序栈类型*/#defineMAXNUM30#defineINITSIZE100typedefintElemType;typedefstructQNode{inttop;ElemType*base;intstacksize;}QNode,sqstack;/*1.初始化*/voidInitstack(sqstack*S){S-base=(ElemType*)malloc(INITSIZE*sizeof(ElemType));S-top=0;S-stacksize=INITSIZE;}/*2.判断栈空*/intemptystack(sqstackS){if(S.top==0)return1;elsereturn0;}8/*3.入栈*/intpush(sqstack*S,ElemTypee){if(S-top=S-stacksize);{S-base=(ElemType*)realloc(S-base,(S-stacksize+1)*sizeof(ElemType));if(!S-base)return0;S-stacksize++;}S-base[S-top++]=e;return1;}/*4.出栈*/intpop(sqstack*S,ElemType*e)//*e记录出栈元素的变量{//inti;if(S-top==0)return0;*e=S-base[--S-top];return1;}/****************************************************//*以下为有向图(DAG)邻接表存储结构(ALG)的操作*//****************************************************/#defineMAXVEX30//最大顶点个数#defineMAXNAME20typedefcharVertexType[20];//顶点信息（名称）/*图的类型定义（邻接表存储结构）*/9typedefstructArcNode//链表结点{intvexpos;//该弧所指向的顶点在数组中的位置structArcNode*next;//指向当前起点的下一条弧的指针}ArcNode;typedefstructVNode//头结点{VertexTypename;//顶点信息（名称）intindegree;//顶点入度ArcNode*firstarc;//指向当前顶点的第一条弧的指针}VNode,AdjList[MAXVEX];typedefstruct{AdjListvexhead;//邻接表头结点数组intvexnum,arcnum;//图的顶点数和弧数}ALGraph;/*5.顶点在头结点数组中的定位*/intLocateVex(ALGraphG,VertexTypev)//G带操作的图；v要在图中定位的顶点{inti;for(i=0;iG.vexnum;i++)if(strcmp(v,G.vexhead[i].name)==0)break;returni;}//顶点存在则返回在头结点数组中的下标；否则返回图的定点数/*6.建立图（邻接表）*/intCreateGraph(ALGraph*G)//成功建立返回1，不成功则返回0{inti,j,k;VertexTypev1,v2;ArcNode*newarc;printf(\n输入有向图顶点数和弧数vexnum,arcnum:);//输入顶点数和弧数scanf(%d,%d,&(*G).vexnum,&(*G).arcnum);//输入并判断顶点数和弧数是否正确10if((*G).vexnum0||(*G).arcnum0||(*G).arcnum(*G).vexnum*((*G).vexnum-1)){printf(\n顶点数或弧数不正确，有向图建立失败！\n);return0;}printf(\n输入%d个顶点:,(*G).vexnum);//输入顶点名称for(i=0;i(*G).vexnum;i++){scanf(%s,(*G).vexhead[i].name);}printf(\n顶点列表:\n共有%d个顶点:,(*G).vexnum);//输出顶点名称for(i=0;i(*G).vexnum;i++)printf(%s,(*G).vexhead[i].name);for(i=0;i(*G).vexnum;i++)//邻接表初始化{(*G).vexhead[i].firstarc=NULL;(*G).vexhead[i].indegree=0;}printf(\n\n输入%d条边:vivj\n,(*G).arcnum);//输入有向图的边for(k=0;k(*G).arcnum;k++){scanf