数据结构课程设计指导
一、课程设计要求
课程设计是数据结构课程的一个综合实践练习，是有别于课程实验的一个独立实践教学环节。课程设计一般在课程结束后进行，教学时数为1周。具体要求如下：
1、结合实际问题进一步理解和深化课程理论知识，做到理论与实际相结合。
2、能对实际问题进行分析和抽象，并进行数据结构设计和算法设计，具有初步的分析问题和解决问题的能力。
3、了解软件工程的理论与方法，初步掌握软件开发过程中的需求分析、系统设计、编码、测试等基本方法和技能。
4、进一步强化编程训练，提高程序设计能力。
5、设计内容要有一定的深度和难度，达到一定工作量，代码量不低于500行。
二、课程设计内容
课程设计的主要工作如下：
1、问题定义与需求分析：根据设计题目的要求，对问题进行分析，确定系统的功能需求和性能需求。
2、数据结构与算法设计：对问题描述中涉及的数据对象定义相应的数据结构，包括逻辑结构、存储定义和主要操作。对主要算法要进行时间和空间复杂度分析。
3、概要设计：采用面向对象方法设计软件结构，定义类及类之间的关系。要求系统结构合理、易于实现。
4、详细设计：对数据结构和基本操作做进一步的求精，写出数据存储定义，用程序流程图或伪码对算法进行描述。
5、编码与测试：用C++编程实现系统，并设计测试用例对系统进行测试，修改程序中的错误，形成格式和风格良好的源程序清单。
6、设计结果分析：对系统应用效果进行分析，评价系统的先进性、实际应用价值及在在的问题。
7、撰写课程设计报告。
三、课程设计考核
课程设计考核内容包括设计作品和设计报告两个部分。设计作品包括可运行的源程序（刻录成光盘），系统使用说明，主要程序代码（打印附在课程报告内）。 课程设计报告主要报告系统分析、设计和实现过程，内容如下：
1、问题定义及设计要求；
2、主要设计内容：详细报告课程设计中所做的主要工作，包括系统分析、概要设计、数据结构设计、算法设计及模块设计和编程及测试等。
3、总结与体会：写出本次课程设计的主要创新点及存在的问题。 4、参考文献：列出所参考的主要文献。 5、小组成员及分工。
课程设计成绩分两部分，设计报告占50％，设计作品占50％。评价因素主要有：
1、知识点覆盖范围及运用能力； 2、数据结构设计与算法设计能力； 3、系统规模（代码行数）； 4、数据存储方式；
5、人机交互（用户体验或评价）
四、时间安排：
另行通知。
五、课程设计参考题目 1、学生成绩管理系统（***）
【问题描述】
设计并实现一个能够对学生信息以及其成绩信息进行管理的系统。其中学生信息包括：学号、姓名、年龄、性别；课程成绩信息包括：课程号、课程名、成绩、任课教师。能够根据学生信息和成绩信息对数据进行插入、删除、更新、查询、排序、统计等操作。 【基本要求】
（1）对系统用到的数据要能够从文件中读取；
（2）系统中的排序操作至少要用到快速排序、堆排序和归并排序中的两种排序方法； （3）系统中查找过程至少用到两种查找方法。 【知识点】
（1）线性表； （2）排序算法； （3）查找算法。
2、图书管理系统（***）
【问题描述】
图书管理基本业务活动包括：对一本书进行采编入库、清除库存、借阅和归还等。试设计一个图书管理系统，将上述业务活动借助于计算机系统完成。 【基本要求】
（1）每种书的登记内容至少包括书号、书名、作者、现存量和总库存量等5种。 （2）系统应实现的操作及功能定义如下：
1）采编入库：新购入一种书，经分类和确定书号后登记到图书账目中去。如果这种书在账目中已有，则只将总库存量增加；
2）清除库存：某种书已无保留价值，将它从图书帐目中注销；
3）某种书的现存量大于零，则借出一本，登记借阅者的图书证号和归还期限； 4）归还：注销对借阅者的登记，改变该书的现存量。 【知识点】
（1）线性表； （2）查找算法；
3哈夫曼编码译码（****）
【问题描述】
设计一种编码，让使用频率高的字符的编码尽可能的短，并且要求一字符的编码不能与另一个字符的编码的前一部分相同。把每个叶子的使用频率作为权，构造哈夫曼树。然后能够通过字符和他的权值来构造哈夫曼编码，并且能够通过编码相反的过程来实现哈夫曼的译码功能。 【基本要求】
（1）能够通过键盘或者纯文本文件读入字符集的大小n，以及n个字符和权值来建立哈夫曼树，并且把建立好的哈夫曼树存入到HuffmanTree.txt中去。
（2）利用已经建立好的哈夫曼树，对文件中的正文进行编码，将结果存入到文件HuffmanCode.txt中。
（3）利用已经建立好的哈夫曼树将HuffmanCode.txt中的哈夫曼编码进行译码，结果存入到HuffmanText.txt中。
（4）能够按照垂直输出二叉树的方式，将存储在HuffmanTree.txt纯文本文件中的哈夫曼树垂直输出。并且在打印哈夫曼编码是，要求字符与编码之间是一一对应的。 【实现提示】
（1）在程序运行时，能够出现一个主选择菜单，用户能够自主选择功能：①建立哈夫曼树；②对哈夫曼树进行编码、译码等功能。
（2）在建立哈夫曼树时，用到文本文件的读取时，需要用到头文件“fstream”来对文本文件进行处理。 【关键技术与知识点】
（1）优先级队列； （2）哈夫曼树； （3）啥夫曼编码。
4八皇后问题（***）
【问题描述】
八皇后问题是一个古老而著名的问题，是回溯算法的典型例题。问题描述如下：在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。 【基本要求】
（1）在8×8格的国际象棋上摆放八个皇后。 （2）任意两个皇后不能处于同一列中。 （3）任意两个皇后不能处于同一行中。 （4）任意两个皇后不能处于对角线中。 （5）程序中包含递归和非递归两种算法。 【实现提示】
最深层的叶子结点才有可能是合法的布局。深度优先遍历这棵“状态树”，寻找这些叶子便是求解过程。
（1）用三个一维数组A、B、C记录棋盘占用情况，称为状态数组，状态数组的初始值为0，表示棋盘上还没有皇后。如果一个皇后占据了某一位置（x0，y0)令