《数据结构》课程设计



一、课程设计的目的与任务

课程设计是学生对课程所学知识的综合运用，它与课堂听讲、上机实验、课外练习、自学研究相辅相成，构成一个完整的课程教学体系。《数据结构》是一门实践性强的课程，其中对算法设计和程序编写的掌握尤为重要。学生虽然可以通过与课堂教学同步的上机实验完成相关内容的练习，但却往往局限于一些功能简单、彼此之间关系独立的算法和程序。课程设计是一种综合训练，致力于培养学生全面、灵活的算法设计思想和较高的编程能力，为今后从事计算机开发与应用打下基础。新世纪需要具有丰富科学知识、独立解决实际问题、有创造能力的新型人才，这也是该课程设计的最终目的。

二、本课程设计的基本理论

《数据结构》课程设计中牵涉到本课程中的六个主要章节的基本理论，包括基本数据结构（线性结构（线性表、栈、队列）、图、树）的特点、存储方式、运算原理和方法、典型应用和两种重要操作查找、排序的基本原理与方法。

三、课程设计的基本要求

基本要求：通过这次设计，要求在分析计算机处理对象的逻辑特性和物理表示、数据结构的选择和应用、算法的设计及其实现等方面加深对课程基本内容的理解。要求每个学生在规定的时间内完成应用问题，并根据所选问题分析设计思路、选择数据结构描述、确立算法过程、用一种计算机语言（例如C++、Java）（最好是C++）编写出详细的实现程序，然后通过上机反复调试与修改，直到获得满意的结果为止。对于要解决的同一问题，由于所采用的数据结构可能不同、所选择的算法可能不同、编写的程序也不仅相同，但只要结果正确且有效（具有较好的时间复杂度和空间复杂度）即可，即不要求编写的算法和程序完全一致，但力求编写的算法和程序更优秀、综合指标更好。

四、课程设计的内容

1. 文本处理

【问题描述】打开一篇英文文章，在该文章中统计单词个数，统计单词出现次数。能够找出所有给定的单词，然后对所有给定的单词替换为另外一个单词，再存盘

【基本要求】（80分）

(1)完成上述功能，数据结构不限

(2)尽量高效

【选做内容】

(1) 同时给定几个单词进行查找

(2) 中文文章类似功能的实现

（3）其他文本编辑功能

2. 任意长整数求和

【问题描述】

设计一个程序实现两个任意长的整数的求和运算。

【基本要求】（80分）

利用双向循环链表，设计一个实现任意长的整数进行加法运算的演示程序。要求输入和输出每四位一组，组间用逗号隔开。如：1，0000，0000，0000，0000。

【选做内容】

(1)乘法功能的实现；

(2)界面设计的优化。

3. 迷宫求解

【问题描述】

以一个m×n长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍，设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。

【基本要求】（70分）

(1)以二维数组存储迷宫数据；

(2)求得的通路以二元组( i , j )的形式输出，其中（i, j）指示迷宫中的一个坐标。

【选做内容】

(1)以方阵形式输出迷宫及其通路；

(2)显示整个寻找通路的动态过程。

4. 迷宫的随机生成

【问题描述】

以一个m×n长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍，设计一个程序，能够随机生成一个只有唯一一条通路的可求解迷宫。

【基本要求】（80分）

(1)以二维数组存储迷宫数据；

(2)通路以二元组( i , j )的形式输出，其中（i, j）指示迷宫中的一个坐标。

【选做内容】

(1)以方阵形式输出迷宫及其通路；

(2)更多的迷惑性路线。


5. 哈夫曼编码/译码器

【问题描述】

设计一个利用哈夫曼算法的编码和译码系统，对txt文件重编码和解码。

【基本要求】（85分）

(1)输入：读入txt文件

(2)编码：对读入的内容建好哈夫曼树，并生成哈夫曼编码；

(3)对文件编码保存；

(4)对文件解码：

【选做内容】

(1)输入的内容按文本编码，比如“我是一个大学生，我是大一学生喜欢学数据结构”，这句话我出现了两次，学出现了两次，等等

(2)界面设计的优化：可视化程度的提高。

6. 学生信息管理系统

【问题描述】

设计一个学生信息管理系统完成学生管理基本业务。

【基本要求】（85分）

(1) 数据结构不限；

(2) 每位同学信息包括学号、名字、性别、专业、成绩；

(2)对名字建立建立索引表以提高查找效率；

(3)系统主要功能如下：

信息入库： 增加新的学生信息；

信息查询：给定名字，迅速给出其他信息

成绩排序：按照成绩对学生排序，给出排序后的学生信息列表

【选做内容】

(1)系统功能的进一步完善：比如百万级别的快速查找。

(2)界面设计。

6．内部排序算法的性能分析

【问题描述】

设计一个测试程序比较几种内部排序算法的关键字比较次数和移动次数以取得直观感受。

【基本要求】（90分）

(1)对起泡排序、直接插入排序、简单选择排序、快速排序、希尔排序进行比较；

(2)待排序表的表长不小于10000，表中数据随机产生，至少用5组不同数据作比较，比较指标有：关键字参加比较次数和关键字的移动次数（关键字交换记为3次移动）；

(3)输出比较结果。

【选做内容】

(1)对不同表长进行比较；

(2)验证各算法的稳定性；

(3)输出界面的优化。

7. 背包问题求解

【问题描述】

设有不同价值,不同重的物品n件,求从这n件物品中选取一部分物品的方案,使选中物品的总重量不超过指定的限制重量,但选中物品的价值之和为最大.

【基本要求】（75分）

(1) 分别输入n件物品的重量和价值

(2) 采用递归寻找物品的选择方案.

(3) 输出最佳的装填方案: 包括选中的是哪几种物品,总价值为多少.

8. 五子棋的棋盘局面估值

【问题描述】

在一个８×８的棋盘里下五子棋，当下到一定程度时对当前的局面进行估值，看看对谁有利。

【问题分析】当前棋局可以用一个二维数组存储。 不同时间段的棋局可以组织成树结构。谁先胜出谁赢。

【基本要求】（95分）

（1） 能给出一个分值用以估计双方的有利程度。

【选做】

（1） 考虑棋盘比较大的情况

（2） 可视化

9．最小生成树求解

【问题描述】

在n个城市之间建设网络，只需保证连通即可，求最经济的架设方法。

【基本要求】（70分）

（1）假设已知n个城市之间的网络是一个带权连通无向图。

（2）用邻接矩阵COST表示给定的带权连通无向图。知阵元素定义为

wij

Cost=   0

∞

（3）利用普里姆或克鲁斯卡尔算法求图的最小生成树。

10．二叉树的建立

【问题描述】

已知二叉树T中结点的中序和后序遍历序列，编写算法实现构造满足上述条件的二叉树。

【基本要求】（70分）

（1） 假设二叉树T的结点值是字符。

（2） 建立的二叉树以二叉链表的存储结构进行存储。

（3） 输出二叉树的先序遍历序列。

【选做内容】

（1）二叉树的显示

（2）遍历过程的显示

11.算术表达式的求解

【问题描述】

给定一个算术表达式，通过程序求出最后的结果。

【基本要求】（80分）

(1)从键盘输入要求解的算术表达式；

(2)采用栈结构进行算术表达式的求解过程；

(3)能够判断算术表达式正确与否；

(4)对于错误表达式给出提示；

(5)对于正确的表达式给出最后的结果；


五、课程设计实习报告内容与要求（参考附件）

《数据结构》课程设计实验报告要求完成的内容包括：

1．问题描述

根据你所选做题目，写出其问题的文字描述。

2．问题分析

根据自身对课程的掌握程度，充分分析和理解问题的设计要求，给出较为明确、简洁的设计思路和解决方法。

3．数据结构描述

根据要解决的问题，考虑各种可能的数据结构类型，从中选择一种较为有效的数据结构，确定其存储形式并写出存储结构的描述。

4．算法设计

根据问题分析的结果，及存储结构的描述，写出合理的算法设计过程，特别要注意所使用函数间的调用与被调用关系，可以用程序总模块图及程序流程图表示。

5．详细程序清单

根据算法的内容，用计算机语言（如Java或 C）编写完整的程序，并将程序在机器上反复调试，直到结果正确为止，最后将程序清单打印出来，要求附上详细注解。特别要注意算法与程序的区别以及上下层模块间的接口处理（即参数的设置）。同时要求只写一个主程序，每个问题的处理通过主程序对函数的调用来实现，而且要求在主程序中要求设计一个界面，用户在运行程序时可通过界面的提示选择执行相应的功能模块。

6．程序运行结果

利用典型的测试用例，将数据输入到程序执行过程中去，记下执行过程中屏幕显示情况与相应结果。

7．写出使用说明，实习体会心得等；