数据结构课程设计指导一、课程设计要求课程设计是数据结构课程的一个综合实践练习，是有别于课程实验的一个独立实践教学环节。

课程设计一般在课程结束后进行，教学时数为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、人机交互（用户体验或评价）四、时间安排：冬季短学期，第19周周一开题，第19周周四中期检查，下学期开学第一天课程设计答辩。

19周安排课程组老师在指定地点值班辅导。

五、课程设计参考题目1、学生成绩管理系统（***）【问题描述】设计并实现一个能够对学生信息以及其成绩信息进行管理的系统。

其中学生信息包括：学号、姓名、年龄、性别；课程成绩信息包括：课程号、课程名、成绩、任课教师。

能够根据学生信息和成绩信息对数据进行插入、删除、更新、查询、排序、统计等操作。

【基本要求】（1）对系统用到的数据要从能够文件中读取；（2）系统中的排序操作至少要用到快速排序、堆排序和归并排序中的两种排序方法；（3）系统中查找过程至少用到两种查找方法。

【知识点】（1）线性表；（2）排序算法；（3）查找算法。

2、图书管理系统（****）【问题描述】图书管理基本业务活动包括：对一本书进行采编入库、清除库存、借阅和归还等。

试设计一个图书管理系统，将上述业务活动借助于计算机系统完成。

【基本要求】（1）每种书的登记内容至少包括书号、书名、作者、现存量和总库存量等5种。

（2）系统应实现的操作及功能定义如下：1）采编入库：新购入一种书，经分类和确定书号后登记到图书账目中去。

如果这种书在账目中已有，则只将总库存量增加；2）清除库存：某种书已无保留价值，将它从图书帐目中注销；3）某种书的现存量大于零，则借出一本，登记借阅者的图书证号和归还期限；4）归还：注销对借阅者的登记，改变该书的现存量。

（3）扩展内容：用B树对书号进行索引，以获得高的查找效率。

【知识点】（1）线性表；（2）查找算法；（3）B树。

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)令A[x0]=B[x0+y0]=C[x0-y0]=1，那么下一个皇后能够占据另一个位置（x1，y1）的前提是A[x1]=B[x1+y1]=C[x1-y1]=0.（2）作为数组下标，x和y的取值范围是0~7，因此x+y和x-y的取值范围分别为0~14和-7~7，整个取值范围是-7~14。

按照习惯，数组下标从0开始，这就需要加7，使下标范围等价的转换为0~21，数组A、B、C的长度为22.原来的数组元素A[x]、B[x+y]、C[x-y]现在分别等价于A[x+7]、B[x+y+7]、C[x-y-7]。

（3）利用长度为8的一维数组Y记录皇后的位置，如果Y[y]=x(0<=y<8)表示皇后占据了第y行第x列。

（4）求解过程就是深度优先遍历。

如果叶子是合法的布局，就输出记录的结果。

然后回溯，在回到上一层递归之前，要把状态数组在当前位置上的值恢复为0。

【知识点】（1）树的遍历；（2）递归与非递归算法；（3）栈与队列。

5迷宫求解（***）【问题描述】以一个m*n的长方阵表示迷宫，如图1所示，阴影部分表示此路不能，空白部分表示此路可行。

规定每次只能走上下左右相邻的一格。

设计一个C++程序，求出从入口到出口所有路径。

图1迷宫【基本要求】（1）迷宫的规格（即行数与列数）、状态设置（即各方格能否通行的状态）、入口和出口的位置，均应由输入随机确定。

（2）求得的路径，应该以从入口到出口的路径上的各个方格的坐标的线性序列输出。

当无通路时，应该报告无路径的信息。

（3）扩展内容：求出从入口到出口的最短路径。

【实现提示】（1）将迷宫转换为图，即把迷宫中的空白看作图的顶点，空白的上下左右邻接关系看作图的无向边。

图的顶点存储迷宫空白坐标。

这样图1所示的迷宫可以转换成图2所示的图。

迷宫求解问题可以转换为图的遍历问题。

图2 迷宫问题转换为图（2）存储结构：迷宫可以采用二维数组maze[][]表示。

row与col分别表示迷宫的行数与列数。

而maze[i][j]表示迷宫中第i行第j列的一个方格，用maze[i][j]=0表示该方格可以通行，用maze[i][j]=1表示该方格不可以通行。

可在迷宫的四周加一圈障碍，这样可以保证从任一顶点出发，都可以有4个方向的选择。

（3）可以采用递归算法或非递归算法求出所有路径。

非递归算法需要借助栈保存迷宫搜索程中已走过的路径信息，以便在遇到障碍时沿原路返回，在搜索结束后输出栈中保存的最终路径。

（4）求迷宫最短路径可以采用图的广度优先搜索遍历算法，这时需要采用队列作为辅助数据结构。

【知识点】（1）图的遍历；（2）单源最短路径；（3）递归与非递归算法；（4）栈与队列。

6各种排序算法的性能分析（****）【问题描述】排序是一个将记录的无序序列调整成为一个有序序列的过程。

排序算法是计算机程序设计中的重要过程，不同的排序算法性能各有不同。

在程序中，我们通过随机函数产生规模不同的随机整型数组，然后分别让不同的排序算法来从小到大进行排序。

通过排序时间和排序的交换次数上对不同的排序算法进行性能分析。

【基本要求】（1）每种排序算法在同一规模的数组测试中使用的原始数据是相同的。

例如:不同排序算法对一个含有100个元素的无序数组进行排序时，他们的无序序列是相同的。

（2）对用于测试的随机数组规模不少于100个元素，其待测排序数组不少于5组。

（3）对不同的排序算法要求记录排序所需执行时间和移动次数。

（4）对以下排序算法进行性能分析，尽量采用结构化程序设计方法，要求对各个模块的功能及参数作必要的说明。

(直接插入排序，折半插入排序，希尔排序，起泡排序，快速排序，直接选择排序，堆排序(加黑的着重要求)，树型选择排序，归并排序以及基数排序) 【实现提示】（1）通过在程序中插入计数器来实现排序算法中对移动次数的记录。

（2）调用#include<ctime>中的clock函数获取程序的开始时间和结束时间，相减得到程序的运行时间。

【知识点】（1）排序算法。

（2）算法性能分析。

7交通咨询系统（最短路径问题）（*****）【问题描述】设计一个交通咨询系统，能让旅客咨询从任一个城市顶点到另一个城市顶点之间的最短路径或最低费用或最少时间等问题。

对于不同咨询要求，可以输入城市间的路程或所需要时间或所需费用。

设计分三个部分，一是建立交通网络图的存储结构；二是解决单源最短路径问题；最后再实现两个城市顶点之间的最短路径问题。

【基本要求】（1）对城市信息(城市名、城市间的里程)进行编辑：具备添加、修改、删除功能；（2）对飞机航班和列车时刻表进行编辑：里程、航班和列车班次的添加、修改、删除；（3）提供两种最优决策：最快到达或最省钱到达。