数据结构课程设计指导书

课程设计是数据结构课程的一个综合实践练习，是有别于课程实验的一个独立实践教学环节。课程设计一般在课程结束后进行，教学时数为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）对系统用到的数据要从能够文件中读取；

2）系统中的排序操作至少要用到快速排序、堆排序和归并排序中的两种排序方法；

3）系统中查找过程至少用到两种查找方法。

知识点】1）线性表；

2）排序算法；

3）查找算法。

问题描述】图书管理基本业务活动包括：对一本书进行采编入库、清除库存、借阅和归还等。试设计一个图书管理系统，将上述业务活动借助于计算机系统完成。

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

2）系统应实现的操作及功能定义如下：

1）采编入库：新购入一种书，经分类和确定书号后登记到图书账目中去。如果这种书在账目中已有，则只将总库存量增加；

2）清除库存：某种书已无保留价值，将它从图书帐目中注销；

3）某种书的现存量大于零，则借出一本，登记借阅者的图书证号和归还期限；

4）归还：注销对借阅者的登记，改变该书的现存量。

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

知识点】1）线性表；

2）查找算法；

3）b树。

问题描述】设计一种编码，让使用频率高的字符的编码尽可能的短，并且要求一字符的编码不能与另一个字符的编码的前一部分相同。把每个叶子的使用频率作为权，构造哈夫曼树。然后能够通过字符和他的权值来构造哈夫曼编码，并且能够通过编码相反的过程来实现哈夫曼的译码功能。

基本要求】1）能够通过键盘或者纯文本文件读入字符集的大小n，以及n个字符和权值来建立哈夫曼树，并且把建立好的哈夫曼树存入到中去。

2）利用已经建立好的哈夫曼树，对文件中的正文进行编码，将结果存入到文件中。

3）利用已经建立好的哈夫曼树将中的哈夫曼编码进行译码，结果存入到中。

4）能够按照垂直输出二叉树的方式，将存储在纯文本文件中的哈夫曼树垂直输出。并且在打印哈夫曼编码是，要求字符与编码之间是一一对应的。

实现提示】1）在程序运行时，能够出现一个主选择菜单，用户能够自主选择功能：建立哈夫曼树；对哈夫曼树进行编码、译码等功能。

2）在建立哈夫曼树时，用到文本文件的读取时，需要用到头文件“fstream”来对文本文件进行处理。

关键技术与知识点】

1）优先级队列；

2）哈夫曼树；

3）啥夫曼编码。

问题描述】八皇后问题是一个古老而著名的问题，是回溯算法的典型例题。问题描述如下：在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）栈与队列。

问题描述】以一个m*n的长方阵表示迷宫，如图1所示，阴影部分表示此路不能，空白部分表示此路可行。规定每次只能走上下左右相邻的一格。设计一个c++程序，求出从入口到出口所有路径。

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

2）求得的路径，应该以从入口到出口的路径上的各个方格的坐标的线性序列输出。当无通路时，应该报告无路径的信息。

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

实现提示】1）将迷宫转换为图，即把迷宫中的空白看作图的顶点，空白的上下左右邻接关系看作图的无向边。图的顶点存储迷宫空白坐标。这样图1所示的迷宫可以转换成图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）栈与队列。

问题描述】排序是一个将记录的无序序列调整成为一个有序序列的过程。排序算法是计算机程序设计中的重要过程，不同的排序算法性能各有不同。在程序中，我们通过随机函数产生规模不同的随机整型数组，然后分别让不同的排序算法来从小到大进行排序。

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

基本要求】1）每种排序算法在同一规模的数组测试中使用的原始数据是相同的。例如：不同排序算法对一个含有100个元素的无序数组进行排序时，他们的无序序列是相同的。

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

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

4）对以下排序算法进行性能分析，尽量采用结构化程序设计方法，要求对各个模块的功能及参数作必要的说明。(直接插入排序，折半插入排序，希尔排序，起泡排序，快速排序，直接选择排序，堆排序(加黑的着重要求)，树型选择排序，归并排序以及基数排序)

实现提示】1）通过在程序中插入计数器来实现排序算法中对移动次数的记录。

数据结构课程设计指导书

数据结构课程设计指导书

数据结构课程设计指导书

数据结构课程设计指导书

其他用户还读了