数据结构课程设计报告-(拓扑排序-课程安排)

课程设计报告课程名称数据结构课题名称1.拓扑排序2.通讯录管理专业计算机科学与技术班级计算机1001学号201003010106姓名贺填填指导教师刘铁武周铁山李杰君2011年7月3日湖南工程学院课程设计任务书一．设计内容：问题1：拓扑排序大学期间各专业都要制订相应的教学计划。每个专业开设的课程预先已确定。而各门课程间有的是相互独立的，而有的则有先修后修的限定。试设计相应的课程设置程序，实现对某专业各学期的课程的排布，其中每门课需设定课时，而各学期的总课时不能超过上限。测试数据：学期课时上限数：350；各课程所需学时：48；课程先、后修关系如图：问题2：huffman编码对于确定的字符集的电文字符串编码，实现最高的通信效率。编程实现对于给定的输入串及各字符的已知频度，输出其编码方式（各字符的二进制编码）及对应的输出流。测试数据：字符ABCDEFGHIJKLM频度18664132232103211547571232194212101136578字符NOPQRSTUVWXYZ频度20576315148518023818116问题3：成绩管理编制一应用软件实现对班级成绩管理。基本功能有学生信息的增删（转入或退学）、查找（从当前点向前或向后双向的）、录入、统计（如总分，及格率等）。建议用双链表实现。问题4：成绩排序对某次考试成绩排序，输入为多门课程成绩，可以任一课程成绩为关键字进行检索。建议采用快速排序等算法效率高的算法。问题5：迷宫求解一个M*N的长方阵迷宫，0和1分别表示迷宫中的通路和墙壁。对任意设定的迷宫，东、南、西、北四个方向是可能的行走方向。求出一条从入口到出口的路径。（或没有通路）。测试数据：迷宫的测试数据如下：左上角（1,1）为入口，右下角（8,9）为出口。问题6：一元多项式计算001000100010001000001101011100100001000001000101011110011100010111000000对于任意输入的多项式A=anxn+an-1xn-1+…a1x+a0和B=bmxm+bm-1xm-1+…b1x+b0，用链表存储后实现A+B；A-B。测试数据：a.)72111.3()1157()1.352(91198118xxxxxxxx；b.；391515223923122.18.7()8.74.56()2.14.46(xxxxxxxxxxxxc.)1()()1(25435432xxxxxxxxxx；d.0)()(33xxxx；e.)(0)(2332xxxxxx；问题7:通讯录管理设计一个通讯录管理，包括通讯录链表的建立、通讯者的插入、通讯者的删除、通讯者的查询以及信息修改等。要求有运行界面,从菜单中进入选项。二．设计要求：1．选题：每位学生需完成两个课题，其中一个必选，另一个自选，必选题次为，学号/7+1。2．课程设计报告内容说明1)需求分析程序的功能；输入输出的要求。2)概要设计程序的模块构成以及模块之间的层次结构、各模块的调用关系；每个模块的功能；课题涉及的数据结构和数据库结构；即要存储什么数据，这些数据是什么样的结构，它们之间有什么关系等。3)详细设计采用C语言定义相关的数据类型；写出各模块的类C码算法；画出各函数的调用关系图、主要函数的流程图。4)调试分析以及设计体会测试数据：准备典型的测试数据和测试方案，包括正确的输入及输出结果和含有错误的输入及输出结果；程序调试中遇到的问题以及解决问题的方法；课程设计过程经验教训、心得体会。5)使用说明用户使用手册：说明如何使用你编写的程序，详细列出每一步的操作步骤。6)书写格式见附带说明。7)附录参考书目；源程序清单（带注释）3．成绩评定：指导老师负责验收程序的运行结果，并结合学生的工作态度、实际动手能力、创新精神和设计报告等进行综合考评，并按优秀、良好、中等、及格和不及格五个等级给出每位同学的课程设计成绩。具体考核标准包含以下几个部分：①平时出勤（占10%）②系统需求分析、功能设计、数据结构设计及程序总体结构合理与否（占10%）③程序能否完整、准确地运行，个人能否独立、熟练地调试程序（占40%）④设计报告（占30%）注意：不得抄袭他人的报告（或给他人抄袭），一旦发现，成绩为零分。⑤独立完成情况（占10%）。三．进度安排第一周星期一星期二星期三星期四星期五上午8：00~12：00下午13：30~17：30第二周星期一星期二星期三星期四星期五上午8：00~12：00下午13：30~17：30附：课程设计报告装订顺序：封面、任务书、目录、正文、评分、附件（A4大小的图纸及程序清单）。正文的格式:一级标题用3号黑体,二级标题用四号宋体加粗,正文用小四号宋体;行距为22。正文的内容:一、课题的主要功能；二、课题的功能模块的划分（要求画出模块图）；三、主要功能的实现（至少要有一个主要模块的流程图）；四、程序调试；五、总结；六、附件（所有程序的原代码，要求对程序写出必要的注释）。正文总字数要求在5000字以上（不含程序原代码）。目录1.拓扑排序................................错误!未定义书签。1.1需求分析...........................................11.2概要设计...........................................11.3详细设计...........................................21.4调试分析及设计体会.................................71.5使用说明...........................................152.通讯录管理..............................................162.1需求分析...........................................162.2概要设计...........................................162.3详细设计...........................................172.4调试分析及设计体会.................................272.5使用说明...........................................313.附录...................................................32湖南工程学院课程设计报告11拓扑排序1.1需求分析1.1.1程序的功能该程序的功能主要是根据图的拓扑排序算法，依某专业的课程先、后修关系图，实现该专业课程的排布。其中，每门课程需设定课时，而各学期的总课时不能超过上限。1.1.2输入输出要求首先，创建课程先、后关系图。其中，需要输入该关系图的结点数(课程数)、结点信息及弧的信息等；然后，输入该专业课程的学期数，并在拓扑排序过程中，依次输入某学期的课程安排。所以，最终输出为各个学期所安排的课程结果，并且，课程安排符合课程先、后关系图的一个拓扑排序。1.2概要设计1.2.1模块功能流程图程序调用关系及模块功能运行流程如下：123图1.1程序调用关系及模块功能流程图1.2.2数据结构及数据类型图的存储结构有邻接矩阵和邻接表。在该程序中采用了邻接表来存储有向图。在开始主函数main()分支选择处理创建图拓扑排序退出系统结束湖南工程学院课程设计报告2邻接表中，需要定义头结点的结构体数据类型，用以存储图的结点信息，并且在每个头结点后连接一个单链表，用以存储以该头结点为弧尾，链表中结点为弧头的弧。所以还需定义表结点的结构体数据类型，用以存储图中弧的信息。最后，定义有向图的结构体数据类型，其中的数据项包含一个指向头结点首地址的指针和顶点数、弧数的整型数据类型。1.2.3拓扑排序算法拓扑排序算法描述如下：(1)在有向图中选一个没有前驱的顶点且输出之。即入度为零的结点。(2)从图中删除该顶点和所有以它为尾的弧。即以该结点为弧尾的弧的弧头结点的入度值减一。(3)重复上述两步，直至全部结点均已输出，或者当前结点中不存在无前驱的顶点为止。后一种情况则说明有向图中存在环，拓扑排序失败。然而，在此课题中是为了依拓扑排序算法而设计课程的安排序列。显然，在同一学期里的课程是相互独立的，不存在先、后修关系。由此，对于某个学期课程的安排，其安排的课程范围是有向图中某次拓扑排序中所有没有前驱顶点结点的集合，则该学期课程的安排可以在该集合中选择，并且选择结果满足的总课时没有超过上限。同时，由此次选择结果，可以产生下个学期课程安排的范围。重复上述操作，直至所有课程都选择完。另外，还应设计一个能够检测所有课程是否在规定的学期内修完。若检测到在规定学期内课程没有修完，则需重新设定学期数或者重新进行课程安排。1.3详细设计1.3.1采用C语言定义结构体数据类型1.3.1.1头结点的顶点信息结构体数据类型typedefstructVertexType{charname[20];//顶点编号，即课程编号charsbname[20];//课程名称intOutdegree;//顶点的出度intIndegree;//顶点的入度intweight;//课时boolmark;//在拓扑排序时，标记该结点是否已访问湖南工程学院课程设计报告3intid;//确定该课程属于哪个学期}VertexType;1.3.1.2头结点结构体数据类型typedefstructVNode{VertexTypedata;//顶点信息ArcNode*first;//指向第一条依附该结点的弧的指针}VNode;1.3.1.3表结点结构体数据类型typedefstructArcNode{intadjvex;//该弧所指向的顶点的位置structArcNode*next;//指向下一条弧的指针}ArcNode;1.3.1.4图的结构体数据类型typedefstructGraph{VNode*head;//指向头结点首地址的指针intvexnum,arcnum;//图的定点数和弧数}Graph;1.3.1.5学期课程结构体数据类型TypedefstructSubject{intcount;//某学期所安排的课程数int*head;//某学期所安排课程对应结点在图中的存储置}Subject,*PSubject;1.3.2各模块的类C码算法1.3.2.1创建有向图的类C码算法：StatusGCreate(Graph&G){scanf(%d,G.vexnum);if(!(G.head=(VNode*)malloc(G.vexnum*sizeof(VNode))))exit(OVERFLOW);for(i=0;iG.vexnum;i++)scanf(%s%s%d,&G.head[i].data.name,&G.head[i].data.sbname,&G.Head[i].data.weight);湖南工程学院课程设计报告4//输入结点信息，各头结点的入度、出度、学期编号id均初始化为零//访问标记mark初始化为false,并给指针域first分配内存空间j=0;while(1){//输入弧，并以输入字符#结束scanf(%s%s,ch1,ch2);if(strcmp(ch1,#)==0)break;n=GLocateVex(G,ch1);//获取弧尾结点存储位置m=GLocateVex(G,ch2);//获取弧头结点存储位置if(n!=-1&&m!=-1){//输入的弧存在j++;ptr1=G.head[n].first;while(ptr1-next!=NULL)ptr1=ptr1-next;if(!(ptr2=(ArcNode*)malloc(sizeof(Arc