数据结构课程设计任务书

《数据结构课程设计任务书》由会员分享，可在线阅读，更多相关《数据结构课程设计任务书（8页珍藏版）》请在金锄头文库上搜索。

1、数据构造课程设计任务书 数据构造与算法课程设计任务书 一数据构造与算法课程设计的目的和要求 (一)设计的目的 数据构造与算法课程设计是在学完数据构造与算法课程之后的理论教学环节。该理论教学是软件设计的综合训练，包括问题分析p 、总体构造设计、用户界面设计、程序设计根本技能和技巧。要求学生在设计中逐步进步程序设计才能，培养科学的软件工作方法。学生通过数据构造课程设计在下述各方面得到锻炼： 1能根据实际问题的详细情况，结合数据构造与算法课程中的根本理论和根本算法，正确分析p 出数据的逻辑构造，合理地选择相应的存储构造，并能设计出解决问题的有效算法。 2进步程序设计和调试才能。学生通过上机实习，验证

2、自己设计的算法的正确性。学会有效利用根本调试方法，迅速找出程序代码中的错误并且修改。 3培养算法分析p 才能。分析p 所设计算法的时间复杂度和空间复杂度，进一步进步程序设计程度。 (二)设计要求 1学生必须仔细阅读数据构造与算法课程设计方案，认真主动完成课设的要求。有问题及时主动通过各种方式与老师联络沟通。 2学生要发挥自主学习的才能，充分利用时间，并在课设过程中不断检测自己的方案完成情况，及时向老师汇报。 3课程设计按照教学要求需要一周时间完成，属老师安排上机时间学生不得缺席。 二设计内容及步骤 1分析p 问题，给出数学模型，设计相应的数据构造。 1分析p 问题的特点，用数学表达式或其它形式

3、描绘其数学模型。 2选择可以表达问题本身特点的逻辑构造。 3在逻辑构造确定的情况下，为算法的设计选择相应的存储构造，顺序存储构造和非顺序存储构造的不同存储方式，其对应的算法也不一样。 2算法设计 在已经选择好数据构造的前提下，为解决问题设计算法。 1确定所需模块 对于稍复杂的程序设计，要充分利用模块化程序设计方法，自顶向下，逐步细化，在整体思路确定的情况下，考虑所需模块数，各模块完成功能以及模块之间的数据联络和调用关系。 2各子模块功能描绘 给出主要模块的算法描绘，用流程图或伪代码表示。 3模块之间的调用关系 给出算法各模块之间的关系图示 3程序清单 为了进步工作效率，充分利用上机调试程序的时

4、间，要求学生在上机之前给出程序清单。 4算法分析p 经过上机调试，程序运行正确，并且实现算法要求的功能，解决课程设计题目中给出的问题后，分析p 各模块算法的时间复杂度和空间复杂度。进一步体会：程序=数据构造+ 算法 二上交相关材料要求 上交的成果的内容由以下两局部组成，缺一不可 1上交程序：学生按照课程设计的详细要求所开发的所有程序放一个文件夹中； 2课程设计报告：按照课程设计的详细要求建立的功能模块，每个模块要求按照如下几个内容认真完成；其中包括： ? 设计题目 ? 设计内容 ? 概要设计：确定所需模块及模块间调用关系 ? 算法描绘：给出各模块流程图及代码 ? 算法分析p ? 心得体会 ?

5、参考资料 三课程设计的成绩评定 1程序设计结果40 2实验报告40 3平时表现 20 四课程设计完成时间 第12周周五下午17：40之前。 五上机时间安排表 课程设计的时间及老师安排 专业 班级 周次 机房安排 上机时间 11W星期一(9-12) 11W星期三(9-12) 11W星期四(9-12) 指导老师 软件楼通信工程 1421301-3 第11-12周 504、506 11W星期五(5-8) 12W星期二(5-8) 12W星期三(9-12) 12W星期四(1-4) 12W星期五(5-8) 刘自强 锋 六数据构造课程设计题目 题目1：任意长的整数加法 问题描绘：设计一个算法，实现两个任意长

6、的整数的加法运算。 根本要求：利用双向循环链表，设计一个实现任意长的整数进展加法运算的演示程序。要求输入和输出每四位一组，组间用逗号隔开。如：1，0000，0000，0000，0000。 题目2：集合运算 功能：使用链表来表示集合，完成集合的交、并、差等操作。 主要包含以下内容： 1初步完成总体设计，搭好框架，确定人机对话的界面，确定函数个数； 2完成最低要求： 3进一步要求： 题目3：一元多项式加法、乘法运算的实现 功能： 完成两个一元多项式作加法、乘法，给出明确的等式形式。 即： Am(x)?A0?A1x1?A2x2-Amxm Bn(x)?B0?B1x1?B2x2-Bnxn 求：Am(x)

7、?Bnxn、Am(x)?Bnxn 分步施行： 1初步完成总体设计，搭好框架，确定人机对话的界面，确定函数个数； 2完成最低要求：建立一个文件，实现两个一元二次多项式作乘法。 题目4：二叉排序树的实现 用二叉链表为存储构造 1以回车(n)为输入完毕标志,输入数列L，生成一棵二叉排序树T； 2对二叉排序树T作中序遍历，输出结果； 3输入元素x,查找二叉排序树T,假设存在含x的结点,那么删除该结点,并作中序遍历(执行操作；否那么输出信息“无x”； 题目5: 内部排序算法的性能分析p 利用随机函数产生N个随机整数20000以上，对这些数进展多种方法进展排序。 要求： 1至少采用三种方法实现上述问题求解

8、提示，可采用的方法有插入排序、希尔排序、起泡排序、快速排序、选择排序、堆排序、归并排序。并把排序后的结果保存在不同的文件中。 2 统计每一种排序方法的性能以上机运行程序所花费的时间为准进展比照，找出其中两种较快的方法。 3假如采用4种或4种以上的方法者，可适当加分。 题目6：哈希表的设计与实现 问题描绘： 设计哈希表实现 号码查询系统。 根本要求： 1、设每个记录有以下数据项： 号码、用户名、地址； 2、从键盘输入各记录，分别以 号码和用户名为关键字建立哈希表； 3、采用再哈希法解决冲突； 4、查找并显示给定 号码的记录； 5、查找并显示给定用户名的记录。 6、在哈希函数确定的前提下，尝试各种

9、不同类型处理冲突的方法至少两种，考察平均查找长度的变化。 题目7：树的应用家谱查询系统 问题描绘：讨论对任意树的存储，并讨论在此存储构造下的根本操作。 1建立树家谱存储构造； 2树家谱的遍历方法； 3结点家谱成员查询； 4求树上结点家谱成员的途径即从根结点到此结点的途径； 等操作，可以自由发挥。 题目8：队列的应用火车厢重排问题 假设一列货运列车共有n节编号分别为1n的车厢，在进站前这n节车厢并不是按其编号有序排列；现要求重新排列各车厢，使该列车在进入车站时，所有车厢从前到后按编号1n的次序排列，以便各车厢可以停靠在与其编号一致的站点。 为了到达这样的效果，可以在一个转轨站里完成车厢的重排工作

10、。在转轨站中有一个入轨，一个出轨和K个位于入轨与出轨间的缓冲铁轨。如以下图所示。开场时，具有n节车厢的货车从入轨处进入转轨站；转轨完毕时，各车厢从右到左按照编号1n的次序通过出轨处分开转轨站。 要求：给了算法分析p 与完好的算法程序。 题目9：栈的应用火车厢重排问题 假设一列货运列车共有n节编号分别为1n的车厢，在进站前这n节车厢并不是按其编号有序排列；现要求重新排列各车厢，使该列车在进入车站时，所有车厢从前到后按编号1n的次序排列，以便各车厢可以停靠在与其编号一致的站点。 为了到达这样的效果，可以在一个转轨站里完成车厢的重排工作。在转轨站中有一个入轨，一个出轨和K个位于入轨与出轨间的缓冲铁轨。如以下图所示。开场时，具有n节车厢的货车从入轨处进入转轨站；转轨完毕时，各车厢从右到左按照编号1n的次序通过出轨处分开转轨站。 要求：给了算法分析p 与完好的算法程序。 题目10：二叉树非递归遍历算法集成 功能要求： 第 页 共 页