数据结构课程设计指导书

数据结构课程设计指导

一、课程设计要求

课程设计是数据结构课程的一个综合实践练习，是有别于课程实验的一个独立实践教学环节。课程设计一般在课程结束后进行，教学时数为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中的clock函数获取程序的开始时间和结束时间，相减得到程序的运行时间。 【知识点】

（1）排序算法。 （2）算法性能分析。

7交通咨询系统（最短路径问题） （*****）

【问题描述】

设计一个交通咨询系统，能让旅客咨询从任一个城市顶点到另一个城市顶点之间的最短路径或最低费用或最少时间等问题。对于不同咨询要求，可以输入城市间的路程或所需要时间或所需费用。设计分三个部分，一是建立交通网络图的存储结构；二是解决单源最短路径问题；最后再实现两个城市顶点之间的最短路径问题。 【基本要求】

（1）对城市信息(城市名、城市间的里程)进行编辑：具备添加、修改、删除功能； （2）对飞机航班和列车时刻表进行编辑：里程、航班和列车班次的添加、修改、删除； （3）提供两种最优决策：最快到达或最省钱到达。全程只考虑一种交通工具，可以不考虑回程；

（4）旅途中的耗费的总时间应包括中转站的等候时间。其中飞机至少二小时，火车至少一小时；

（5）咨询以用户和计算机对话方式进行，要注意人机交互的屏幕界面。由用户选择最优决策原则和交通工具，输入起始站、终点站、出发时间，输出信息：最快需要多长时间才能到达及旅费，或者最少需要多少旅费才能到达及时间。 【实现提示】

（1）数据存储。城市信息(城市名、代码)、交通信息(城市间的里程、各航班和列车时刻)存储于磁盘文件中。

（2）数据的逻辑结构。根据设计任务的描述，其城市之间的旅游交通问题是典型的图结构，可看作为有向图，图的顶点是城市，边是城市之间所耗费的时间（要包括中转站的等候时间）或旅费。

（3）数据的存储结构。采用邻接表作为数据的存储结构。

（4）求最优决策（最短路径和最小费用）功能模块：用Dijkstra算法求出出发城市到其它各城市的最优值(最短时间或最小的费用)。

（6）主程序可以有系统界面、菜单；也可用命令提示方式；选择功能模块执行，要求在程序运行过程中可以反复操作。 【知识点】

（1）单源最短路径。

（2）一顶点对之间的最短路径。 （3）所有顶点对之间的最短路径。

8重排九宫格（*****）

【问题描述】

将1、2、3、4、5、6、7、8等八个数字随机放在一个3x3的九宫格中，其中有一个格子为空。移动空格可以改变九宫格的状态。移动规则是，每次将与空格（上、下、左、右）相邻的一个数字平移到空格中。假设九宫格的初态和终态分别为图1的（a）和（b）所示，试给出从初态到终态的最少移动步数。

1 2 3 2 8 3 1 7 6 4 5 8 7 6 4 5

（a）九宫格的初态S0 （b）九宫格的终态Sg

图1 九宫格的初态和络态

【基本要求】

（1）空格只能与空格相邻（上、下、左、右）的一个数字交换位置。

（2）空格不能连续两次与同一个数字交换位置（为了防止循环，规定状态不能返回父结点）。

（3）求出从初状态S0到目标状态Sg的调整过程，即从初态到终态的路径。 （4）扩展内容：在屏幕上显示九宫格的图形形式，并能动态演示移动过程。 【实现提示】

（1）隐式图搜索。九宫格求解是一个典型的状态搜索问题。如果用状态空间的显示表示，则应把其全部状态（共有9！个）存入计算机中，这是一个相当大的数字，不现实。一般采用隐式图搜索法，即从初态开始，逐步地生成问题的状态空间并检查解是否在其中。如图2所示，先从S0开始，产生4状态，如果解不在其中，则分别从这4状态开始产生新的状态。为了防止循环，规定不能返回到父结点。 （2）广度优先搜索算法步骤：

1）将初始状态S0压入队列S中。

2）若队列S为空，则搜索失败，问题无解。

3）取队列S首元素结点N取出放入栈K中并将其以顺序编号n。 4）若目标Sg=N，则搜索成功，问题有解。 5）若N无子结点则返回步骤2.

6）扩展N，将其所有子结点配上指向N的返回指针后，再依次放入队列S中，返回步骤2。

注意：返回指针的值要对应编号。 （3）深度优先搜索法

1）将初始状态S0压入栈S中。

2）若栈S为空，则搜索失败，问题无解。

3）取栈S顶元素结点N放入栈K中并将其以顺序编号n。 4）若目标Sg=N，则搜索成功，问题有解。 5）若N无子结点，则返回步骤2.

6）扩展N，将其所有子结点配上指向N的返回指针后，再依次压入栈S中，返回步骤2。

注意：返回指针要对应编号。

图 九宫格图搜索求解过程

【知识点】

（1）图的遍历；

（2）栈、队列和优先级队列； （3）状态空间搜索。

9 野人过河（*****）

【问题描述】

有3个野人和3个传教士来到河边渡河，河岸有一条船，每次至多可供2人乘渡，野人

和传教士都会划船。在河岸，如果野人人数多于传教士人数，则野人会吃掉传教士。请设计一个程序来描述安全过河过程。 【基本要求】

（1）在河两岸和船上要求野人的人数不大于传教士的人数。

（2）要求输出所有可能的过程。(即不同方法的每个步骤如示例1) （3）要求对各个模块的功能及参数作必要的说明。 【实现提示】

（1）先设定两个状态数组确定左岸和右岸，再确定状态变量：野人数，传教士数和船。 （2）先从开始岸考虑传教士数>=野人数，河对岸野人数<=传教士数。并且始终保证开过去两人，开回来一人实现有效转换。

（3）可以考虑使用图搜索方法，通过检测结点来实现路径的输出。 输出示例:

第1次：左岸到右岸，传教士过去1人，野人过去1人 第2次：右岸到左岸，传教士过去1人，野人过去0人 第3次：左岸到右岸，传教士过去0人，野人过去2人 第4次：右岸到左岸，传教士过去0人，野人过去1人 第5次：左岸到右岸，传教士过去2人，野人过去0人 第6次：右岸到左岸，传教士过去1人，野人过去1人 第7次：左岸到右岸，传教士过去2人，野人过去0人 第8次：右岸到左岸，传教士过去0人，野人过去1人 第9次：左岸到右岸，传教士过去0人，野人过去2人 第10次：右岸到左岸，传教士过去0人，野人过去1人 第11次：左岸到右岸，传教士过去0人，野人过去2人 【知识点】

（1）图的遍历。 （2）状态空间搜索。

10校园导游系统（****）

【问题描述】

设计一个校园导游系统，为来访的客人提供导游咨询服务，如景点查询、路径查询等。 【基本要求】

（1）设计所在学校的校园平面图，所含景点不少于10个。 （2）为来访客人提供图中任意景点相关信息的查询。 （3）为来访客人提供图中任意景点的问路查询，即查询任意两个景点之间的一条通路，包括任意两个景点之间的所有路径，任意两个景点之间的最短路径等。

（4）扩展内容：提供景点和道路的扩充及撤销功能。 【实现提示】

（1）用图存储校园平面图中的基本信息。图的顶点表示校园内各景点，存放景点名称、代号、简介等信息；图的边表示景点之间的可达关系；图的边的权植表示两个景点之间的路径长度。

（2）数据的存储结构。采用邻接表作为数据的存储结构。

（3）用迪杰斯特算法（Dijkstra）求出从一个景点到其他所有景点的最短路径，用弗洛伊德算法（Floyd）求所有景点之间的最短路径。

（6）主程序可以有系统界面、菜单；也可用命令提示方式；选择功能模块执行，要求在程序运行过程中可以反复操作。 【知识点】

（1）单源最短路径。

（2）所有顶点对之间的最短路径。

11文本分析（*****）

【问题描述】

编写程序，求出文本中每个单词出现的频次，并比较不同文本的相似度。 【基本要求】

（1）各文本存放在文件中，程序能读取文本文件；

（2）程序能对文本文件进行分词，将分词得到的单词存放到单词表中；

（3）如果一个单词多次出现，要统计单词出现的频率，其频率也要存入到单词表中； （4）扩展内容：根据不同文本各单词出现的频率，建立文本向量，计算文本的相似度。 【实现提示】

（1）定义一个结构体StringCount，其中字符串成员str和整数成员num分别记录单词及其出现的次数。

（2）创建单词表，程序扫描到一个单词后要先在单词表中查找该单词是否存在，如果不存在就把该单词存放到单词表中，并将该单词计数设为1；如果该单词存在，就修改单词表中该单词出现的频次，即把该单词计数增1。

（2）为了提高查找速度，建立平衡二叉搜索树，其结点存放单词基本信息（包括单词字符串和单词出现的频次），插入单词结点时要对平衡二叉搜索树进行动态平衡调整。

（3）建立文本向量，它由单词频次转换而来，通过计算向量距离得出文本之间的相似度。向量距离公式如下：

ii), Wj=(wj,wj,...,wj)，定义向量相似度为： 设有向量: Wi=(w1i,w2,...,wn12nS(Wi,Wj)=(Wi,Wj)(PWiP?PWjP)

,其中(WiWj=)jk?jiiPWP=(?ww为向量内积， kkk=1nnk=1(wki)2)12，

PWjP=(?nk=1(w)2)12为向量的范数(长度)。将S(Wi,Wj)简记为Sij。S(Wi,Wj)的物

理意义是两个向量的空间夹角的余弦数值。

【知识点】

（1）字符串处理。

（2）平衡二叉搜索树。

（3）扩展内容：向量相似度计算。

12大学教学计划编制（***）

【问题描述】

大学每个专业都要制定教学计划。假设某个专业有40门课程，分8个学期开设。每门课程均在一个学期内完成。课程之间存在先修关系，即一门课程只有其所有先修课程都完成后才能开始。教学计划中至少有5门课程没有先修课程，先修关系路径长度不超过7。同一学期内开设的课程不存在先修关系，即可以并行执行。试设计实现一个教学计划编制程序，

把课程分到不同学期，保证所有课程满足先修关系，且能对课程基本信息和上课学期进行查询。

【基本要求】

（1）每门课的信息包括课程基本信息（如课程号、学分等）和课程之间的关系信息（即课程之间的先修关系）。 课程信息存储在文件中。程序从文件中读取课程信息。

（2）允许用户指定下列两种编排策略之一：一是使学生在各学期中的学习负担尽量均匀，即每个学期课程门数和学分尽量相近；二是把课程尽可能地排在前几个学期中，即课程安排前紧后松。

（3）课程编排结果也要写入文件中。 【实现提示】 （1）课程基本信息和课程之间先修关系信息用图表示，图的顶点存储课程的基本信息，图的边存储课程之间的先修关系。

（2）先采用拓扑排序生成所有课程的之间的先后关系，再根据拓扑排序把课程分解到不同学期。 【知识点】

（1）程序文件读写； （2）图的邻接表表示法； （3）图的拓扑排序算法。

把课程分到不同学期，保证所有课程满足先修关系，且能对课程基本信息和上课学期进行查询。

【基本要求】

（1）每门课的信息包括课程基本信息（如课程号、学分等）和课程之间的关系信息（即课程之间的先修关系）。 课程信息存储在文件中。程序从文件中读取课程信息。

（2）允许用户指定下列两种编排策略之一：一是使学生在各学期中的学习负担尽量均匀，即每个学期课程门数和学分尽量相近；二是把课程尽可能地排在前几个学期中，即课程安排前紧后松。

（3）课程编排结果也要写入文件中。 【实现提示】 （1）课程基本信息和课程之间先修关系信息用图表示，图的顶点存储课程的基本信息，图的边存储课程之间的先修关系。

（2）先采用拓扑排序生成所有课程的之间的先后关系，再根据拓扑排序把课程分解到不同学期。 【知识点】

（1）程序文件读写； （2）图的邻接表表示法； （3）图的拓扑排序算法。

本文来源：https://www.bwwdw.com/article/f3b6.html