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

1、课 程 设 计 报 告课程名称 数据结构 课题名称 1.拓扑排序 2.通讯录管理 专 业 计算机科学与技术 班 级 计算机 1001 学 号 6 姓 名 贺填填 指导教师 刘铁武 周铁山 李杰君 2011年 7 月 3日湖南工程学院课 程 设 计 任 务 书一设计内容：问题1：拓扑排序大学期间各专业都要制订相应的教学计划。每个专业开设的课程预先已确定。而各门课程间有的是相互独立的，而有的则有先修后修的限定。试设计相应的课程设置程序，实现对某专业各学期的课程的排布，其中每门课需设定课时，而各学期的总课时不能超过上限。测试数据：学期课时上限数：350 ；各课程所需学时：48；课程先、 后修关系如图

2、：194212101136578问题2：huffman编码对于确定的字符集的电文字符串编码，实现最高的通信效率。编程实现对于给定的输入串及各字符的已知频度，输出其编码方式（各字符的二进制编码）及对应的输出流。测试数据： 字符ABCDEFGHIJKLM频度18664132232103211547571232字符NOPQRSTUVWXYZ频度20576315148518023818116问题3：成绩管理编制一应用软件实现对班级成绩管理。基本功能有学生信息的增删（转入或退学）、查找（从当前点向前或向后双向的）、录入、统计（如总分，及格率等）。建议用双链表实现。问题4：成绩排序对某次考试成绩排序，输入

3、为多门课程成绩，可以任一课程成绩为关键字进行检索。建议采用快速排序等算法效率高的算法。问题5：迷宫求解一个M*N的长方阵迷宫，0和1分别表示迷宫中的通路和墙壁。对任意设定的迷宫，东、南、西、北四个方向是可能的行走方向。求出一条从入口到出口的路径。（或没有通路）。测试数据：001000100010001000001101011100100001000001000101011110011100010111000000迷宫的测试数据如下：左上角（1,1）为入口，右下角（8,9）为出口。 问题6：一元多项式计算对于任意输入的多项式A=anxn+an-1xn-1+a1x+a0和B=bmxm+bm-1xm

4、-1+b1x+b0，用链表存储后实现A+B；A-B。测试数据：a.；b.；c.；d.；e. ；问题7: 通讯录管理设计一个通讯录管理，包括通讯录链表的建立、通讯者的插入、通讯者的删除、通讯者的查询以及信息修改等。要求有运行界面,从菜单中进入选项。二设计要求：1选题：每位学生需完成两个课题，其中一个必选，另一个自选，必选题次为，学号/7+1。2课程设计报告内容说明1)需求分析 程序的功能；输入输出的要求。2)概要设计 程序的模块构成以及模块之间的层次结构、各模块的调用关系；每个模块的功能；课题涉及的数据结构和数据库结构；即要存储什么数据，这些数据是什么样的结构，它们之间有什么关系等。3)详细设计

5、 采用C语言定义相关的数据类型；写出各模块的类C码算法；画出各函数的调用关系图、主要函数的流程图。4)调试分析以及设计体会 测试数据：准备典型的测试数据和测试方案，包括正确的输入及输出结果和含有错误的输入及输出结果；程序调试中遇到的问题以及解决问题的方法；课程设计过程经验教训、心得体会。5)使用说明 用户使用手册：说明如何使用你编写的程序，详细列出每一步的操作步骤。6)书写格式 见附带说明。7)附录 参考书目； 源程序清单（带注释）3成绩评定：指导老师负责验收程序的运行结果，并结合学生的工作态度、实际动手能力、创新精神和设计报告等进行综合考评，并按优秀、良好、中等、及格和不及格五个等级给出每位

6、同学的课程设计成绩。具体考核标准包含以下几个部分： 平时出勤 （占10%） 系统需求分析、功能设计、数据结构设计及程序总体结构合理与否（占10%） 程序能否完整、准确地运行，个人能否独立、熟练地调试程序（占40%） 设计报告（占30%）注意：不得抄袭他人的报告（或给他人抄袭），一旦发现，成绩为零分。 独立完成情况（占10%）。三进度安排第 一周星期一星期二星期三星期四星期五上午8：0012：00下午13：3017：30第二 周星期一星期二星期三星期四星期五上午8：0012：00下午13：3017：30附：课程设计报告装订顺序：封面、任务书、目录、正文、评分、附件（A4大小的图纸及程序清单）。

7、正文的格式:一级标题用3号黑体,二级标题用四号宋体加粗,正文用小四号宋体;行距为22。正文的内容:一、课题的主要功能；二、课题的功能模块的划分（要求画出模块图）；三、主要功能的实现（至少要有一个主要模块的流程图）；四、程序调试；五、总结；六、附件（所有程序的原代码，要求对程序写出必要的注释）。正文总字数要求在5000字以上（不含程序原代码）。 目 录1.拓扑排序1 1.1需求分析1 1.2概要设计1 1.3详细设计2 1.4调试分析及设计体会7 1.5使用说明152.通讯录管理16 2.1需求分析16 2.2概要设计16 2.3详细设计17 2.4调试分析及设计体会27 2.5使用说明313.

8、附录 32 1拓扑排序1.1需求分析 1.1.1 程序的功能 该程序的功能主要是根据图的拓扑排序算法，依某专业的课程先、后修关系图，实现该专业课程的排布。其中，每门课程需设定课时，而各学期的总课时不能超过上限。 1.1.2 输入输出要求 首先，创建课程先、后关系图。其中，需要输入该关系图的结点数(课程数)、结点信息及弧的信息等；然后，输入该专业课程的学期数，并在拓扑排序过程中，依次输入某学期的课程安排。所以，最终输出为各个学期所安排的课程结果，并且，课程安排符合课程先、后关系图的一个拓扑排序。1.2 概要设计 1.2.1 模块功能流程图 程序调用关系及模块功能运行流程如下： 结束拓扑排序创建图

9、退出系统分支选择处理 主函数main() 开始 1 2 3 图1.1 程序调用关系及模块功能流程图 1.2.2 数据结构及数据类型 图的存储结构有邻接矩阵和邻接表。在该程序中采用了邻接表来存储有向图。在邻接表中，需要定义头结点的结构体数据类型，用以存储图的结点信息，并且在每个头结点后连接一个单链表，用以存储以该头结点为弧尾，链表中结点为弧头的弧。所以还需定义表结点的结构体数据类型，用以存储图中弧的信息。最后，定义有向图的结构体数据类型，其中的数据项包含一个指向头结点首地址的指针和顶点数、弧数的整型数据类型。 1.2.3 拓扑排序算法 拓扑排序算法描述如下： (1)在有向图中选一个没有前驱的顶点

10、且输出之。即入度为零的结点。 (2)从图中删除该顶点和所有以它为尾的弧。即以该结点为弧尾的弧的弧头结点的入度值减一。 (3)重复上述两步，直至全部结点均已输出，或者当前结点中不存在无 前驱的顶点为止。后一种情况则说明有向图中存在环，拓扑排序失败。 然而，在此课题中是为了依拓扑排序算法而设计课程的安排序列。显然，在同一学期里的课程是相互独立的，不存在先、后修关系。由此，对于某个学期课程的安排，其安排的课程范围是有向图中某次拓扑排序中所有没有前驱顶点结点的集合，则该学期课程的安排可以在该集合中选择，并且选择结果满足的总课时没有超过上限。同时，由此次选择结果，可以产生下个学期课程安排的范围。重复上述

11、操作，直至所有课程都选择完。另外，还应设计一个能够检测所有课程是否在规定的学期内修完。若检测到在规定学期内课程没有修完，则需重新设定学期数或者重新进行课程安排。1.3 详细设计 1.3.1 采用C语言定义结构体数据类型 1.3.1.1 头结点的顶点信息结构体数据类型 typedef struct VertexType char name20;/顶点编号，即课程编号 char sbname20;/课程名称 int Outdegree;/顶点的出度 int Indegree;/顶点的入度 int weight;/课时 bool mark;/在拓扑排序时，标记该结点是否已访问 int id;/确定该

12、课程属于哪个学期 VertexType; 1.3.1.2 头结点结构体数据类型 typedef struct VNode VertexType data;/顶点信息 ArcNode *first;/指向第一条依附该结点的弧的指针 VNode; 1.3.1.3 表结点结构体数据类型 typedef struct ArcNode int adjvex;/该弧所指向的顶点的位置 struct ArcNode*next;/指向下一条弧的指针 ArcNode; 1.3.1.4 图的结构体数据类型 typedef struct Graph VNode *head;/指向头结点首地址的指针 int vexn

13、um,arcnum;/图的定点数和弧数 Graph; 1.3.1.5 学期课程结构体数据类型 Typedef struct Subject int count;/某学期所安排的课程数 int *head;/某学期所安排课程对应结点在图中的存储置 Subject,*PSubject; 1.3.2 各模块的类C码算法 1.3.2.1 创建有向图的类C码算法： Status GCreate(Graph&G) scanf(%d,G.vexnum); if(!(G.head=(VNode*)malloc(G.vexnum*sizeof(VNode) exit(OVERFLOW); for(i=0;ine

14、xt!=NULL) ptr1=ptr1-next; if(!(ptr2=(ArcNode*)malloc(sizeof( ArcNode)exit(OVERFLOW); ptr2-adjvex=m; ptr1-next=ptr2; Ptr2-next=NULL; G.headn.data.Outdegree+; G.headm.data.Indegree+; return OK; 1.3.2.2 拓扑排序的类C码算法： Status GSort(Graph G,int MAX) scanf(%d,&n);/输入学期数 PSubject p;/对p分配连续的n个空间，并对p进行初始化 /其中，c

15、ount初始化为零，指针head分配连续的G.vexnum个空间 k=0;i=0; while(k=n) while(iG.vexnum) max=0;x=0;mark=false; /max标记某学期的总课时，x标记某学期的课程数 /mark用于判断有向图中是否存在回路 for(j=0;jMAX) max-=G.headm.data.weight; /若所选课程的总课时超出上限，则选择其 它可选课程或退出当前学期的课程安排 选择 else if(k=n) break;/课程安排已超过所安排的 学期数，则推出课程选择 pk.headx=m;/存储该学期所选 课程所对应头结点在在图中的存储位置

16、G.headm.data.mark=true;/标 记该头结点已被排序了 ptr2=G.headm.first-next; i+; x+; while(ptr2!=NULL)/使以该头结 点为弧尾的所有弧的弧头结点的入度减 一及其学期标号作相应的变换 if(G.headptr2-adjvex. data.id=k+1) G.headptr2-adjvex. data.id+; G.headptr2-adjvex. data.Indegree-; ptr2=ptr2-next; if(n=k)/若课程安排已超过所安排的学期数，则重新设定 学期数或重新进行课程安排 scanf(%d,&y);/输入

17、操作选择项 switch(y) case 1:/重新设定学期数 scanf(%d,&n);/重新输入学期数，并对p重 新分配连续的n个空间，并对其进行初始化 break; case 2:/重新进行课程安排 break; default:break; G=SetG(G);/对图进行初始化处理，并依存储结构产生各 头结点的度值 i=0;k=0; continue; pk.count=x; k+; /课程以选完，而学期的课程没有安排完 if(k=n) break; printf(.n);/输出课程已安排完，该学期没有课程 安排 k+; printf(p);/输出各学期的课程安排 return OK;

18、 1.4 调试分析及设计体会 1.4.1 调试分析 1.4.1.1 测试数据：(如下图所示的有向图) 194212101136578 图1.2 课程先、后修关系图 另外，学期课时上限数为：120 1.4.1.2 测试方案 (1)正确的输入及输出： 1、构建图1.2所示的有向图 图1.3 输入图中的顶点信息 图 1.4 输入图中的弧 2、拓扑排序过程(即课程安排过程) 图 1.5 输入学期课时上限数及学期数 图 1.6 第一学期的课程安排 图1.7 第二、三学期的课程安排 图1.8 第四学期的课程安排 图 1.9 学期课程安排已超过学期数并重新输入学期数或重新安排学期课程 图1.10 重新安排第

19、一、二学期的课程 图1.11 重新安排第三、四学期的课程 图1.12 重新安排第五、六学期的课程 图1.13 各学期课程安排结果 3、构建一个存在环的有向图并进行拓扑排序 图1.14 构建一个存在环的有向图 图1.15 因图中存在回路，拓扑排序失败 (2)错误的输入及输出 若在创建图时，输入有相同编号的结点，则可能使程序的输出发生错误,使程序不能结束。 图1.16 在创建图的过程中，输入的结点编号存在相同 图1.17 因图中有结点编号相同的结点而产生错误的选定课程的结果 1.4.1.3 程序调试过程中遇到的问题及解决方法 在开始调试程序的过程中，遇到的主要问题是逻辑错误及程序不能实现所需的要求

20、。第一个问题是：怎样依拓扑排序的算法来产生某个学期的课程安排，另外，怎样确定某个学期到底安排几门课程。若把所有拓扑排序结果都输出出来，显然，这是一个非常不好的想法。经过对这个问题的思考后，若把某个学期所能选的课都显示出来，然后，用户根据显示出来的课程来安排该学期的课程，随后，依安排结果产生下个学期所能选的课程的集合。该种想法不仅解决了怎样依拓扑排序来安排某个学期的课程，并且给用户安排课程提供了很大的灵活性，用户可以根据需求来安排某个学期的课程。第一个问题得到解决并编写程序后，便产生了第二个问题：在产生的某个学期所能安排的课程范围里存在有先后关系的课程或程序不能结束。经过分析发现：在选取某个学期

21、所能安排课程的集合的过程中，会使图中的某些结点的入度由非零减到成零，使原本应为下一学期的课程变换到当前学期中，所以应设定一个课程学期标号，标记课程在拓扑排序过程中所对应的学期。由此，在头结点的信息域中增设了一个整型变量id，用以标记在拓扑排序中该结点应该属于哪个学期，并为拓扑排序增设了一个条件限制。 1.4.2 设计总结 通过对该课题的设计过程，不仅让我对图的存储方法及图的拓扑排序算法加深了理解，更让我深深的了解到理论知识与实践应用上的区别。该课题在理论上是应用了图的拓扑排序的思想，然而它不是单纯的拓扑排序，而是在拓扑排序的基础上，应用图的拓扑排序来解决课程安排的问题。课程安排的结果不仅要符合

22、拓扑排序的要求，并且在同一学期的课程是相互独立的，所以，这就要设计新的算法，对拓扑序列的产生添加新的限制条件。同时，也让我认识到算法在程序设计中的重要性，算法是程序设计的灵魂。1.5 使用说明 1.5.1 数据输入要求 虽然程序能处理一些错误的数据输入，但输入的数据应该要按程序运行的要求，以防止因某些数据的错误输入而导致程序运行产生错误。另外，在构建有向图时，输入其结点标号时，不能输入有标号相同的结点。并且一般是先构造课程先、后修关系图，后进行拓扑排序。 1.5.2 操作要求 操作上没什么特殊要求，在程序运行的过程中，一般有操作的提示说明，但要按提示说明进行操作。例如，在选择某学期的课程时，若

23、所选课程已超过学期课时上限数，此时程序会显示选择该课程会使总课时超过上限，并提示用户选择其它可选课程或结束课程选择。此时，用户按提示信息操作就可以了。 2 通讯录管理 2.1需求分析 2.1.1 程序的功能 该程序是为了实现通讯录的管理。其功能包括通讯录的建立、通讯录成员的查找、通讯录人员的添加、修改通讯人员信息及通讯录人员的删除等。并且建立菜单，在菜单中选择所需的功能。另外，用文件将通讯录人员的信息保存起来。2.1.2 输入输出要求 在程序运行过程中对输入有所提示及要求。由于通讯录管理系统是主要字段是通讯录人员的基本信息，该基本信息包括姓名、性别、年龄及电话号码等。并且，大部分信息是采用字符

24、串进行存储。所以，在输入时，应该特别字符串的输入。另外，还需注意输入结束符的标志。 2.2 概要设计 2.2.1 模块功能流程图 程序调用关系及模块功能运行流程如下： 开始 主函数main() 分支选择处理 创建通讯录通讯者信息查询修改通讯者信息删除通讯者退出系统显示通讯者信息插入通讯者 1 2 3 4 5 6 7结束 图2.1 程序调用关系及模块功能流程图 2.2.2 数据结构及数据类型 在该程序中采用双向链表来存储通讯录人员信息。由此，需定义双端链表的结点结构体数据类型，在该结点中包含数据域和指针域，数据域包含的字段有姓名、性别、年龄及电话号码；指针域包含指向前驱结点的指针和指向后继结点的

25、指针。另外，还定义了链表结构体数据类型，其中包含的字段有指向链表头及链尾结点的指针和链表结点数目。同时，还定义了输入通讯录人员信息的结构体数据类型，用以存储输入的通讯人员的基本信息和查找的通讯录人员的结点指针。 2.2.3 各功能模块采用的算法简介在该程序中采用的算法主要包括双端链表的建立、采用插入排序对双端链表进行排序、采用顺序查找算法在双端链表中进行查找、在双端链表中插入或删除某个结点以及对某个结点进行信息修改等。其中，建立链表为最基本的要求，另外，插入或删除结点及修改结点都要以查找为基础，首先根据某个关键字，以顺序查找算法在链表中找到该结点或链表中的某个位置，然后再进行插入、删除、修改操

26、作。2.3 详细设计 2.3.1 采用C语言定义结构体数据类型 2.3.1.1 通讯录人员基本信息结点的结构体数据类型 typedef struct Element char name20;/姓名 cahr Tnumber20;/电话号码 int age;/年龄 char sex3;/性别 struct Element*next;/指向后继结点的指针 struct Element*prior;/指向前驱结点的指针 Element,*PElement;2.3.1.2 通讯录链表结构体数据类型 typedef struct EList PElement first;/指向链表头结点的指针 PEle

27、ment last;/指向链表尾结点的指针 int size;/链表结点数目 EList; 2.3.1.3 通讯录结点指针的动态数组结构体类型 typedef struct Array/用以存储通讯录结点的指针 PElement*start; PElement*end; int size; Array; 2.3.1.4 通讯人员名单结构体数据类型 typedef struct String char name20;/姓名 char Tnumber20;/电话号码 Array A;/存储链表中以该姓名的所有结点的指针 struct String *link;/在链表中指向后继结点 String,

28、*PString; 2.3.2 各模块的类C码算法 2.3.2.1 建立双端链表 Status ECreate(EList&L) n=0; ptr2=NULL; if(ptr1=(PElement)malloc(sizeof(Element)=NULL) exit(OVERFLOW); while(1) scanf(%s,ptr1-name); if(strcmp(ptr1-name,#)=0)break; scanf(%s%d%s,ptr1-sex,&ptr1-age,ptr1-Tnumber); n+; if(ptr2=NULL) head=ptr1; ptr2=ptr1; ptr1-pr

29、ior=NULL; else ptr2-next=ptr1; ptr1-prior=ptr2; ptr2=ptr1; if(ptr1=(PElement)malloc(sizeof(Element)=NULL) exit(OVERFLOW); if(ptr2!=NULL) ptr2-next=NULL; L.first=head; L.last=ptr2; L.size=n; return OK; 2.3.2.2 依通讯录人员年龄从小到大进行排序(采用插入排序) 插入排序的基本操作是将一个记录插入到已排好序的有序表中，从而得到一个新的、记录数增1的有序表。 Status Sort(EList

30、&L) if(!L.first) return ERROR; ptr1=L.first-next; while(ptr1!=NULL)/添加新记录 ptr3=ptr1; ptr2=ptr3-prior; while(ptr2!=NULL&ptr2-ageptr3-age)/寻找插入位 置并插入 if(ptr3-next=NULL) L.last=ptr2; if(ptr2-prior=NULL) L.first=ptr3; ptr3-prior=NULL; ptr2-prior=ptr3; if(ptr3-next!=NULL) ptr3-next-prior=ptr2; ptr2-next=ptr3-next; ptr3-next=ptr2; else ptr3-prior=ptr2-pr