《数据结构》课程设计任务书。
软件教研室。
一、课程设计目的
学习算法与数据结构的最终目的是解决实际的应用问题，特别是非数值计算类型的应用问题。
本课程是在学完数据结构课程后，进行知识综合训练的一个实践教学环节。该实践教学是软件设计的综合训练，包括问题分析、总体结构设计、用户界面设计、程序设计基本技能和技巧。课程设计要求独立完成一个较为完整的应用需求分析，在完成设计和编程大型作业的同时，达到如下效果：
1、深化对算法与数据结构课程中基本概念、理论和方法的理解；
2、训练综合运用所学知识处理实际问题的能力，强化面向对象的程序设计理念；
3、使程序设计与调试水平有一个明显的提高；
4、培养科学的软件工作方法。
通过数据结构课程设计可以在下述各方面得到锻炼：
1、能根据实际问题的具体情况，结合数据结构课程中的基本理论和基本算法，正确分析出数据的逻辑结构，合理地选择相应的存储结构，并能设计出解决问题的有效算法。
2、提高程序设计和调试能力，通过上机实习，验证自己设计的算法的正确性。学会有效利用基本调试方法，迅速找出程序**中的错误并且修改。
3、培养算法分析能力，分析所设计算法的时间复杂度和空间复杂度，进一步提高程序设计水平，从而提高算法设计和算法分析能力。
4、经过查找参考资料、技术手册和撰写文档的实践，进一步培养软件工程师的综合素质。
5、 培养独立开发较大程序的能力，提高软件开发能力和软件调试技术，培养开发大型程序的方法和相互合作的精神，培养创新意识。
二、课程设计要求
本课程设计属于综合设计类型，实验方式包括系统分析与设计、程序编制和调试。
1、必须仔细阅读《数据结构》课程设计方案，认真主动完成课程设计的要求。有问题及时主动通过各种方式与教师联系沟通。
2、要发挥自主学习的能力，充分利用时间，安排好课程设计的时间计划，并在课程设计过程中不断检测自己的计划完成情况，及时向教师汇报。
3、在处理每一个题目的时候，要从分析题目的需求入手，按照设计抽象数据类型、构思算法、通过类的设计实现抽象数据类型、编制上机程序**并调试的步骤完成题目，最终写出完整的实验报告。见到题目，案头工作准备不足，忙于上机敲程序不是优秀程序员的工作风格。注意设计与实现过程的经验积累，编码应尽量利用前阶段的成熟数据结构包，加大**的重用率。
课程设计所安排的题目，在难度和深度方面都大于课内实验。
三、《数据结构》课程设计的内容及步骤
课程设计就是要运用本课程以及到目前为止的有关课程中的知识和技术来解决实际问题，解决问题的基本步骤是：
1、分析问题，给出数学模型，设计相应的数据结构。
1）、建立模型
分析问题的特点，用数学表达式或其它形式描述其数学模型。用形式模型来刻画问题，将有益于问题的解决。对于形式化的问题，我们容易知道是否有现成的算法或程序可以利用。
如涉及到多个对象及相互关系的问题时所用的模型可以为图论；在符号与文本处理问题时常用字符串来做模型。这里《数据结构》课程中所介绍的各种数据结构均可作为一种模型。
2）、选择数据结构
a、选择能够体现问题本身特点的逻辑结构。
b、在逻辑结构确定的情况下，为算法的设计选择相应的存储结构，顺序存储结构和非顺序存储结构的不同存储方式对算法的时间、空间、性能方面可能有不同的影响，其对应的算法也不相同。除了要能将所需的数据元素及其关系存储起来外，还需要考虑所选择的结构是否便于问题的求解，时间和空间复杂度是否符合要求。
2、算法设计
在建立了适当的数学模型和选择好数据结构的前提下， 问题就可以转换为一些经典问题的综合或变异形式的求解。如模型为图，则可借助于图的深度遍历、广度遍历、求最小生成树、求最短路径、拓扑排序、关键路径等。
1)确定所需模块
对于稍复杂的程序设计，要充分利用模块化程序设计方法，自顶向下，逐步细化，在整体思路确定的情况下，考虑所需模块数，各模块完成功能以及模块之间的数据联系和调用关系。
2)各子模块功能描述
给出主要模块的算法描述，用流程图或伪**表示。
3)模块之间的调用关系
给出算法各模块之间的关系图示。
3、编程 将问题的描述算法和数据结构，用计算机语言来表示并将其转换为完整的程序。
4、算法分析与验证
经过上机调试，源程序运行正确，并且实现算法要求的功能，解决课程设计题目中给出的问题后，分析算法的时间复杂度和空间复杂度；用测试数据去验证算法及程序的正确性。
5、总结 对设计进行总结和讨论，包括本设计的优点、缺点、时间性能、空间性能、与其他可能存在的求解方法之间的比较等。
6、编写设计报告
说明：在设计的过程中，步骤1、步骤2是最为重要的步骤，必须在分析验证无误后，再进入第3步，避免在后面步骤中发现问题，而引起从头重新分析、设计，造成时间、精力的浪费。
四、进度安排
按教学计划规定， 总学时数为10学时。在课程设计过程中，大家可以根据设计的步骤来安排自己的计划。
五、课程设计考核方法及成绩评定
课程设计成绩=程序验收成绩50%+设计报告质量50%
按照百分制给予成绩。
六、课程设计报告要求
完成设计任务后，应按要求提交课程设计报告，设计报告内容包括：
1. 设计题目、专业、班级、学生姓名、学生学号、指导教师姓名、起止时间。
2. 具体任务。
3. 软硬件环境。
4. 算法设计思想及算法描述（给出各模块内流程图及各模块间交互图），包括下面内容：
a)需求分析
在该部分中叙述每个模块的功能要求。
b)概要设计
在此说明每个部分的算法设计说明（可以是描述算法的流程图），每个程序中使用的存储结构设计说明（如果指定存储结构请写出该存储结构的定义）。
c)详细设计
5. 调试分析： 测试数据、测试输出的结果、时间复杂度分析、每个模块设计和调试时存在问题的思考（问题是哪些？问题如何解决？）、算法的改进设想。
6. 参考文献。
七、选题 选题原则是数据结构算法实现及在具体问题中的应用。可选择下列与实际应用紧密结合的较综合性的题目。要求通过课程设计的实践，在数据结构的表示、数据结构的选择及应用、算法设计与实现等方面加深对数据结构课程基本内容的理解和综合运用能力的提高。
题目1：一元多项式计算
设计目的 1．掌握线性链表的建立。
2．掌握线性链表的基本操作。
设计内容和要求
1. 建立链式存储的一元多项式
2. 一元多项式的输出。
3. 两个一元多项式的求和
4. 两个一元多项式的求积。
参考课本上的算法。
题目2：哈夫曼树与哈夫曼编码
利用哈夫曼编码进行信息通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（复原）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。
试为这样的信息收发站写一个哈夫曼编/译码系统。
设计目的 1．掌握哈夫曼树的建树原理
2. 掌握哈夫曼树与哈夫曼码逻辑结构和存储结构。
3．掌握哈夫曼树与哈夫曼码的基本操作。
设计内容和要求
1.输入一个文本，统计各字符出现的频度，输出结果
2.使用二叉链表或三叉链表或者顺序存贮结构，构造哈夫曼树
3.确定和输出各字符的哈夫曼码
4．输入一个由0和1组成的**序列，翻译并输出与之对应的文体，若最后的**子序列不能译为文本，则输出相关信息。
题目3：火车票销售。
编制一个简单的火车票销售系统，可完成售票、退票、车票剩余情况查询等功能。每张车票包含车次、座位信息。
要求：在售票、退票、车票剩余情况查询等环节中，都必须显示出车票的具体信息（车次、座位信息）；退票时，必须是车站售出的票才能退。
数据结构课程设计任务书
数据结构 课程设计任务书。一 数据结构课程设计要求。仔细阅读 数据结构课程设计指导 一书，选好题目，认真制定课程设计方案，在规定的时间内设计完成并按一定格式以书面形式上交报告。设计报告内容一般包括以下几个方面 1 问题描述 2 设计思路 3 数据结构定义 4 系统功能模块介绍。5 程序清单 6 运行...
数据结构 课程设计任务书for
学年学期 2011 2012学年第1学期。专业班级 10软件工程1班。指导教师 吴芸。设计时间 2011 12 12至2011 12 16 学时周数 1周。一 设计目的。1 培养学生运用算法与数据结构的基本知识解决实际编程中的数据结构设计和算法设计问题。2 培养学生独立设计程序与解决问题的能力，培养...
数据结构课程设计任务书
题目 哈夫曼树应用功能 1 从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树并将它存于文件hfmtree中。将已在内存中的哈夫曼树以直观的方式 比如树 显示在终端上 2 利用已经建好的哈夫曼树 如不在内存，则从文件htmtree中读入 对文件tobetran中的正文进行编码，然后将结果存...