《计DS课设任务书》由会员分享，可在线阅读，更多相关《计DS课设任务书（60页珍藏版）》请在金锄头文库上搜索。
1、课程设计报课程名称数据结构课题名称1.拓扑排序2?元多项式计算专业计算机科学与技术班级一计算机1491学号201403139135姓 名唐琨指导教师刘铁武 李珍辉李杰君2016 年 3 月 21 日湖南工程学院课程设计任务书设计内容:问题1 :拓扑排序大学期间各专业都要制订相应的教学计划。每个专业开设的课程预先已确定。而各门课程间有的是相互独立的，而有的则有先修后修的限定。试设计相应的课程设置程序，实现对某专业各学期的课程的排布，其中每门课需设定课时，而各学期的总课时不能超过上限。测试数据：学期课时上限数：350 ;各课程所需学时：48;课程先、后修关系如图:5212398106问题2 :hu
2、ffman 编码对于确定的字符集的电文字符串编码，实现最高的通信效率。编程实现对于给定的输入串 及各字符的已知频度，输出其编码方式（各字符的二进制编码）及对应的输出流。测试数据:字符ABCDEFGHIJKLM频度18664132232103211547571232字符NOPQRSTUVWXYZ频度20576315148518023818116问题3:成绩管理编制一应用软件实现对班级成绩管理。基本功能有学生信息的增删（转入或退学）、查找（从当前点向前或向后双向的）、录入、统计（如总分，及格率等）。建议用双链表实现。测试数据自定，不少于 20条记录，字段不少于 5个。问题4:成绩排序对某次考试成绩
3、排序，输入为多门课程成绩，可以任一课程成绩/总分/界值（如80分以上）为关键字进行检索。建议采用快速排序等算法效率高的算法。测试数据自定，不少于20条记录，字段不少于5个问题5:迷宫求解用迷计算机模拟“迷宫问题”，求出其中一条通道。用数组MAZE仁M1.N表示迷宫，有的可以通行（0表示），有的是路障（1表示），MAZE11为迷宫入口 ,MAZEMN为迷宫出口 ，用非递 归算法求出一条通路并用 ”标示所输出的路径 （见运行示例）否则说明没有通路，继续生成 迷宫,直到有 通路。算法思想及提示:实现这一算法的具体方法很多（如堆栈，队列等），但基本思想一般是回溯法使用MAZEMN表示迷宫（如图2），为
4、判定过程中是否越界，在其外围加一圈1作为路障，markMN作为标志数组，move82是行列增量数组（见图1 2）；建堆栈.约定（i,j）表示I行j列direction表 示方向，从入口开始探索路径：沿 0 1八个方向依次试探，若某方向可通（为 0），则该点连同 方向入堆栈，从该点继续 试探；若八个方向都不通，则取出堆栈顶点，从其标记的方向开始试探其余方向；直至找到出口（有通路）或ti-l.jU)u -/ j)(HIJ-I)?Lim问题6:元多项式计算。堆栈为空（没有通路）.下面右图是利用一随机函数生成的0/1方阵及运行示例：对于任意输入的多项式 A=anxn+an-1xn-1+ a1x+a0
5、和 B=bmxm+bm-1xm-1 +? b1x+b0,用链表存储后实现A+B; A-B。测试数据:a?5x83.1x11)(7 5x811x9)(3.1x1111x9 2x 7);b.;3(6xx 4.4x91.2x )(7.8x1.2xx 12x(6x35.4x22x 7.8x )2345 3 4 5 2c. (1 XXx xx ) ( x x ) (x x x 1)；330d. (xx3)(x x3)e. (x 2 x3x3)0(x3 x2 x)；问题7:通讯录管理查询以及信息修设计一个通讯录管理，包括通讯录链表的建立、通讯者的插入、通讯者的删除、通讯者的 改等。要求有运行界面，从菜单中
6、进入选项。设计要求：1选题： 每位学生需完成两个课题，其中一个必选，另一个自选，必选题次为，学号 /7+1 。 2课程设计报告内容说明1 ） 需求分析 程序的功能；输入输出的要求。2）概要设计 程序的模块构成以及模块之间的层次结构、各模块的调用关系；每个模块的功能； 课题涉 及的数据结构和数据库结构；即要存储什么数据，这些数据是什么样的结构，它们之间 有什么关系等。3）详细设计 采用 C 语言定义相关的数据类型； 写出各模块的类 C 码算法；画出各函数的调用关 系 图、主要函数的流程图。4）调试分析以及设计体会 测试数据： 准备典型的测试数据和测试方案， 包括正确的输入及输出 结果 和含有错误
7、的输入及输出结果； 程序调试中遇到的问题以及解决问题的方法； 课程设计过程 经验教训、 心得体会。5 ） 使用说明 用户使用手册：说明如何使用你编写的程序，详细列出每一步的操作步骤。6 ） 书写格式 见附带说明。7） 附录 参考书目； 源程序清单（带注释）3成绩评定： 指导老师负责验收程序的运行结果，并结合学生的工作态度、实际动手能力、创新精神和 设计 报告等进行综合考评，并按优秀、良好、中等、及格和不及格五个等级给出每位同学的课程设计成 绩。 具体考核标准包含以下几个部分：平时出勤 （占10%系统需求分析、功能设计、数据结构设计及程序总体结构合理与否（占10%程序能否完整、准确地运行，个人能
8、否独立、熟练地调试程序（占40%设计报告（占30%注意：不得抄袭他人的报告（或给他人抄袭），一旦 发现，成绩为 零分。独立完成情况（占10%。星期一星期二星期三星期四星期五上午8 0012 : 00V下午13: 3017: 30星期一星期二星期三星期四星期五上午80012 : 00VVV下午13: 3017: 30V三进度安排附课程设计报告装订顺序：封面、任务书、目录、正文、评分、附件（A4大小的图纸及程序清单）。正文的格式：一级标题用3号黑体，二级标题用四号宋体加粗，正文用小四号宋体；行距为220有一个主正文的内容：一、课题的主要功能；二、课题的功能模块的划分（要求画岀模块图）；三、主要功能
9、的实现（至少要 要模块的流程图）；四、程序调试；五、总结；六、附件（所有程序的原代码，要求对程序写岀必要的注释）正文总字数要求在5000字以上（不含程序原代码）。目录一、拓扑排序 11、需求分析 12、概要设计 13、详细设计 14、调试分析以及设计体会 15、使用说明 1二、一元多项式计算 11、需求分析 12、概要设计 13、详细设计 14、调试分析以及设计体会 15、使用说明 1三、附录 11、 拓扑排序 12 、 一元多项式计算 1、拓扑排序1、需求分析拓扑排序是指由某个集合上的一个偏序得到该集合上的一个全序。 更直观地 讲，一 个偏序是自反的、反对称的，用图表示时每个点都有环且只有单
10、向边。拓扑排序 的任务是在这个 偏序上得到一个全序，即得到一个完成整个项目的各步骤的序列。大学 期间各专业都要制订相应 的教学计划。每个专业开设的课程预先已确定。而各门课程间 有的是相互独立的，而有的则有先 修后修的限定。试设计相应的课程设置程序，实现对 某专业各学期的课程的排布， 其中每门课需 设定课时， 而各学期的总课时不能超过上限。 该程序的功能主要是根据图的拓扑排序算法，依某 专业的课程先、后修关系图，实现该 专业课程的排布。其中，每门课程需设定课时，而各学期的 总课时不能超过上限。首先，创建课程先、后关系图。其中，需要输入该关系图的结点数 （ 课程数 ）、 结 点信息及弧的信息等；然
11、后，输入该专业课程的学期数，并在拓扑排序过程中，依次输 入某学期 的课程安排。所以，最终输出为各个学期所安排的课程结果，并且，课程安排 符合课程先、后关 系图的一个拓扑排序。2、概要设计1.模块功能图，如图2.1图2.1模块功能图2.程序调用关系及模块功能运行流程如图2.2 :. 结束图2.2程序调用关系及模块功能流程图图的存储结构有邻接矩阵和邻接表。 在该程序中采用了邻接表来存储有向图。 接表 在邻 中，需要定义头结点的结构体数据类型，用以存储图的结点信息，并且在每个头结 点后连接 一个单链表，用以存储以该头结点为弧尾，链表中结点为弧头的弧。所以还需 定义表结点的结构 体数据类型，用以存储图
12、中弧的信息。最后，定义有向图的结构体数 据类型，其中的数据项包含 一个指向头结点首地址的指针和顶点数、弧数的整型数据类 型。3、 详细设计3.1 采用 C 语言定义结构体数据类型1.1 头结点的顶点信息结构体数据类型typedef structVertexType char name20; char sbname20; int Outdegree; int Indegree; int weight; bool mark; int id;/ VertexType;1.2 头结点结构体数据类型 typedef struct VNodeVertexType data;ArcNode *first;V
13、Node;1.3 表结点结构体数据类型typedef struct ArcNodeint adjvex; structArcNode*next;ArcNode;1.4 图的结构体数据类型 typedef struct Graph VNode *head; int vexnum,arcnum;Graph;1.5 学期课程结构体数据类型 Typedef struct Subject/ 顶点编号，即课程编号/ 课程名称/ 顶点的出度/ 顶点的入度/ 课时/ 在拓扑排序时，标记该结点是否已访问确定该课程属于哪个学期/ 顶点信息/ 指向第一条依附该结点的弧的指针/ 该弧所指向的顶点的位置/ 指向下一条弧的指针/ 指向头结点首地址的指针/ 图的定点数和弧数int count;/ 某学期所安排的课程数
