数据结构课程设计任务书.doc

数据结构与算法课程设计任务书一数据结构与算法课程设计的目的和要求(一)设计的目的数据结构与算法课程设计是在学完数据结构与算法课程之后的实践教学环节。该实践教学是软件设计的综合训练，包括问题分析、总体结构设计、用户界面设计、程序设计基本技能和技巧。要求学生在设计中逐步提高程序设计能力，培养科学的软件工作方法。学生通过数据结构课程设计在下述各方面得到锻炼：1能根据实际问题的具体情况，结合数据结构与算法课程中的基本理论和基本算法，正确分析出数据的逻辑结构，合理地选择相应的存储结构，并能设计出解决问题的有效算法。2提高程序设计和调试能力。学生通过上机实习，验证自己设计的算法的正确性。学会有效利用基本调试方法，迅速找出程序代码中的错误并且修改。3培养算法分析能力。分析所设计算法的时间复杂度和空间复杂度，进一步提高程序设计水平。(二)设计要求1学生必须仔细阅读数据结构与算法课程设计方案，认真主动完成课设的要求。有问题及时主动通过各种方式与教师联系沟通。2学生要发挥自主学习的能力，充分利用时间，并在课设过程中不断检测自己的计划完成情况，及时向教师汇报。3课程设计按照教学要求需要一周时间完成，属教师安排上机时间学生不得缺席。二设计内容及步骤1分析问题，给出数学模型，设计相应的数据结构。（1）分析问题的特点，用数学表达式或其它形式描述其数学模型。（2）选择能够体现问题本身特点的逻辑结构。（3）在逻辑结构确定的情况下，为算法的设计选择相应的存储结构，顺序存储结构和非顺序存储结构的不同存储方式，其对应的算法也不相同。2算法设计在已经选择好数据结构的前提下，为解决问题设计算法。（1）确定所需模块对于稍复杂的程序设计，要充分利用模块化程序设计方法，自顶向下，逐步细化，在整体思路确定的情况下，考虑所需模块数，各模块完成功能以及模块之间的数据联系和调用关系。（2）各子模块功能描述给出主要模块的算法描述，用流程图或伪代码表示。（3）模块之间的调用关系给出算法各模块之间的关系图示3源程序清单为了提高工作效率，充分利用上机调试程序的时间，要求学生在上机之前给出源程序清单。4算法分析经过上机调试，源程序运行正确，并且实现算法要求的功能，解决课程设计题目中给出的问题后，分析各模块算法的时间复杂度和空间复杂度。进一步体会：程序=数据结构+ 算法二上交相关材料要求上交的成果的内容由以下两部分组成，缺一不可1上交源程序：学生按照课程设计的具体要求所开发的所有源程序（放一个文件夹中）；2课程设计报告：按照课程设计的具体要求建立的功能模块，每个模块要求按照如下几个内容认真完成；其中包括： Ø 设计题目Ø 设计内容Ø 概要设计：确定所需模块及模块间调用关系Ø 算法描述：给出各模块流程图及代码Ø 算法分析Ø 心得体会Ø 参考资料三课程设计的成绩评定1程序设计结果（40）2实验报告（40）3平时表现 （20）四课程设计完成时间第12周周五下午17：40之前。五上机时间安排表课程设计的时间及教师安排专业班级周次机房安排上机时间指导老师通信工程1421301-3第11-12周软件楼504、50611W星期一(9-12)11W星期三(9-12)11W星期四(9-12)11W星期五(5-8)12W星期二(5-8)12W星期三(9-12)12W星期四(1-4)12W星期五(5-8)刘自强刘志锋六数据结构课程设计题目题目1：任意长的整数加法问题描述：设计一个算法，实现两个任意长的整数的加法运算。基本要求：利用双向循环链表，设计一个实现任意长的整数进行加法运算的演示程序。要求输入和输出每四位一组，组间用逗号隔开。如：1，0000，0000，0000，0000。题目2：集合运算功能：使用链表来表示集合，完成集合的交、并、差等操作。主要包含以下内容：1初步完成总体设计，搭好框架，确定人机对话的界面，确定函数个数；2完成最低要求： 3进一步要求： 题目3：一元多项式加法、乘法运算的实现功能： 完成两个一元多项式作加法、乘法，给出明确的等式形式。即：求：、分步实施：1初步完成总体设计，搭好框架，确定人机对话的界面，确定函数个数；2完成最低要求：建立一个文件，实现两个一元二次多项式作乘法。题目4：二叉排序树的实现 用二叉链表为存储结构 1以回车('n')为输入结束标志,输入数列L，生成一棵二叉排序树T；2对二叉排序树T作中序遍历，输出结果；3输入元素x,查找二叉排序树T,若存在含x的结点,则删除该结点,并作中序遍历(执行操作；否则输出信息“无x”；题目5: 内部排序算法的性能分析 利用随机函数产生N个随机整数（20000以上），对这些数进行多种方法进行排序。要求：1至少采用三种方法实现上述问题求解（提示，可采用的方法有插入排序、希尔排序、起泡排序、快速排序、选择排序、堆排序、归并排序）。并把排序后的结果保存在不同的文件中。2 统计每一种排序方法的性能（以上机运行程序所花费的时间为准进行对比），找出其中两种较快的方法。3如果采用4种或4种以上的方法者，可适当加分。题目6：哈希表的设计与实现问题描述： 设计哈希表实现电话号码查询系统。基本要求：1、设每个记录有下列数据项：电话号码、用户名、地址；2、从键盘输入各记录，分别以电话号码和用户名为关键字建立哈希表；3、采用再哈希法解决冲突；4、查找并显示给定电话号码的记录；5、查找并显示给定用户名的记录。6、在哈希函数确定的前提下，尝试各种不同类型处理冲突的方法（至少两种），考察平均查找长度的变化。题目7：树的应用家谱查询系统问题描述：讨论对任意树的存储，并讨论在此存储结构下的基本操作。1建立树（家谱）存储结构；2树（家谱）的遍历方法；3结点（家谱成员）查询；4求树上结点（家谱成员）的路径（即从根结点到此结点的路径）；等操作，可以自由发挥。题目8：队列的应用火车厢重排问题假设一列货运列车共有n节编号分别为1n的车厢，在进站前这n节车厢并不是按其编号有序排列；现要求重新排列各车厢，使该列车在进入车站时，所有车厢从前到后按编号1n的次序排列，以便各车厢能够停靠在与其编号一致的站点。为了达到这样的效果，可以在一个转轨站里完成车厢的重排工作。在转轨站中有一个入轨，一个出轨和K个位于入轨与出轨间的缓冲铁轨。如下图所示。开始时，具有n节车厢的货车从入轨处进入转轨站；转轨结束时，各车厢从右到左按照编号1n的次序通过出轨处离开转轨站。要求：给了算法分析与完整的算法程序。题目9：栈的应用火车厢重排问题假设一列货运列车共有n节编号分别为1n的车厢，在进站前这n节车厢并不是按其编号有序排列；现要求重新排列各车厢，使该列车在进入车站时，所有车厢从前到后按编号1n的次序排列，以便各车厢能够停靠在与其编号一致的站点。为了达到这样的效果，可以在一个转轨站里完成车厢的重排工作。在转轨站中有一个入轨，一个出轨和K个位于入轨与出轨间的缓冲铁轨。如下图所示。开始时，具有n节车厢的货车从入轨处进入转轨站；转轨结束时，各车厢从右到左按照编号1n的次序通过出轨处离开转轨站。要求：给了算法分析与完整的算法程序。题目10：二叉树非递归遍历算法集成功能要求：1界面友好，易与操作。可采用菜单或其它人机对话方式进行选择。2实现各种二叉树的遍历。包括先序遍历、中序遍历、后序遍历、层次遍历的非递归算法。3演示程序以人机对话的形式进行。每次测试完毕正确显示各种遍历序列。在报告中要注明：存储结构、基本算法（可以使用程序流程图）、源程序、测试数据和结果、算法的时间复杂度、另外可以提出算法的改进方法。题目11：哈夫曼编码及实现问题描述参见课本.题目12：二叉树线索化实现以前序遍历的方式线索化二叉树。题目13：二叉树线索化实现以中序遍历的方式线索化二叉树。题目14：二叉树线索化实现以后序遍历的方式线索化二叉树。题目15：多栈共享的实现采用顺序存储结构实现多栈共享，要求模拟完成进栈、出栈等过程。题目16：平衡二叉排序树的实现任意给定一组数据，完成二叉排序树的建立，若为非平衡二叉树，自动调整为平衡二叉排序树。要求：完成建立、插入、删除等操作。题目17：宿舍管理查询系统的设计为宿舍管理人员编写一个宿舍管理查询软件, 程序设计要求：1采用交互工作方式；2建立数据文件，数据文件按关键字（姓名、学号、房号）进行排序；3查询菜单: (用二分查找实现以下操作)按姓名查询、按学号查询、按房号查询4输出任一查询结果（可以连续操作） 题目18：学生成绩管理系统的设计实现功能：输入、输出、插入、删除、查找、追加、读入、显示、保存、拷贝、排序、索引、分类合计、退出。 题目19：最小生成树问题设计要求：在n个城市之间建设网络，只需保证连通即可，求最经济的架设方法。存储结构采用多种。求解算法多种。 题目20：图书管理系统的设计设计一个计算机管理系统完成图书管理基本业务。 基本要求：1每种书的登记内容包括书号、书名、著作者、现存量和库存量；2对书号建立索引表（线性表）以提高查找效率；3系统主要功能如下：Ø 采编入库：新购一种书，确定书号后，登记到图书帐目表中，如果表中已有，则只将库存量增加； Ø 借阅：如果一种书的现存量大于0，则借出一本，登记借阅者的书证号和归还期限，改变现存量； Ø 归还：注销对借阅者的登记，改变该书的现存量。 进一步完成内容Ø 系统功能的进一步完善；Ø 索引表采用树表。题目21：稀疏矩阵应用要求：实现三元组，十字链表下的稀疏矩阵的加、转、乘的实现。（1）稀疏矩阵的存储；（2）稀疏矩阵加法；（3）矩阵乘法；（4）矩阵转置。 题目22：最小生成树的应用问题描述：给定一个地区的n个城市间的距离网，用Prim算法或Kruskal算法建立最小生成树，并计算得到的最小生成树的代价。基本要求：1城市间的距离网采用邻接矩阵表示，邻接矩阵的存储结构定义采用课本中给出的定义，若两个城市之间不存在道路，则将相应边的权值设为自己定义的无穷大值。要求在屏幕上显示得到的最小生成树中包括了哪些城市间的道路，并显示得到的最小生成树的代价。2表示城市间距离网的邻接矩阵（要求至少6个城市，10条边）3最小生成树中包括的边及其权值，并显示得到的最小生成树的代价。 题目23：广义表的应用 由于广义表在结构上较线性表复杂得多，因此，广义表的运算也不如线性表简单。本设计要求实现的广义表的建立、查找、输出、取表头和取表尾以及求深度、求逆表等。本设计用一个主控菜单程序控制，共分为6个子系统。1建立广义表;2输出广义表;3结点的查找;4求广义表表头;5求广义表表尾;6求广义表的深度。七附件附1：课程设计封面附2：课程设计成绩评定页装订说明：装订顺序依次为：封面、成绩评定页、目录、正文（任务书中第七条所列内容）附件1课程设计报告课程设计题目：专 业：班 级：学 号：学生姓名：指导教师：日 期： 年 月 日 附件2数据结构与算法设计课程设计评分表班级： 姓名： 学号： 项目内容满分实 评程序设计能体现创造性思维，或有独特见解10利用数据结构课程所学知识，设计并完成任务书所列功能的完整性15代码规范性5代码注视详细程度10实验报告内容完整性8测试用例10综合评价14报告排版质量8平时成绩平时表现（以考勤为主）20总 分100指导教师评语： 指导教师签名： 2014年 1月 20 日