I
数据结构课程设计指导书
（用于22级软件工程专业）
数据结构课程组
物联网工程学院
2023 年 9 月
I
第1部分 概 述 ...............................1
1.1 课程设计的一般过程 ............................................................................................................1
1.1.1 课程设计安排 ................................................................................................................1
1.1.2 设计实验和综合实验的一般过程 .............................................................................1
1.1.3 提升实验 ...................................................................................................................2
1.2 VC++编程工具的使用.........................................................................................................4
1.2.1 控制台程序 .................................................................................................................4
1.2.2 单文件结构 .................................................................................................................4
1.2.3 多文件结构 .................................................................................................................5
1.2.4 程序的调试 .................................................................................................................8
第2部分 设计实验 ...........................13
2.1 约瑟夫环问题.....................................................................................................................13
2.2 用单链表实现集合的操作.................................................................................................14
//*2.3 汉诺塔问题.....................................................................................................................16
2.4 火车车厢重排问题.............................................................................................................17
2.5 统计文本中单词的个数.....................................................................................................19
//*2.6 幻方.................................................................................................................................19
2.7 求二叉树中叶子结点的个数.............................................................................................21
2.8 二叉表示树.........................................................................................................................23
//*2.9 TSP 问题.........................................................................................................................24
2.10 哈密顿路径.......................................................................................................................25
2.11 二叉排序树的查找性能...................................................................................................26
2.12 闭散列表和开散列表查找性能的比较...........................................................................26
2.13 直接插入排序基于单链表的实现...................................................................................27
2.14 双向起泡排序...................................................................................................................28
第3部分 综合实验 ...........................30
3.1 大整数的代数运算.............................................................................................................30
3.2 一元多项式相加.................................................................................................................31
3.3 表达式求值.........................................................................................................................32
3.4 迷宫问题.............................................................................................................................33
3.5 近似串匹配.........................................................................................................................35
//*3.6 数字旋转方阵.................................................................................................................37
3.7 棋盘覆盖问题.....................................................................................................................38
3.8 信号放大器.........................................................................................................................40
3.9 哈夫曼算法的应用.............................................................................................................42
//*3.10 农夫过河.......................................................................................................................42
II
3.11 医院选址问题...................................................................................................................43
3.12 个人电话号码查询系统...................................................................................................44
//*3.13 斐波那契查找...............................................................................................................45
3.14 各种排序算法时间性能的比较.......................................................................................46
3.15 机器调度问题...................................................................................................................46
第4部分 提升实验 ...........................49
4.1 出栈合法性 ..........................................................................................................................49
4.2 链表的基本操作 ..................................................................................................................49
4.3 二叉树遍历应用 ..................................................................................................................51
4.4 图的应用——最少步数 ......................................................................................................51
4.5 图的应用——最优布线问题 ..............................................................................................52
4.6 散列应用——Sakiya 的对拍程序 ......................................................................................52
//*4.7 王校长的 Party ................................................................................................................53
//*4.8 Mj 的袜子 ......................................................................................................................54
//*4.9 有序表的折半查找..........................................................................................................55
4.10 快速排序 ............................................................................................................................55
4.11 回文问题 ............................................................................................................................56
1
第 1 部分 概 述
1.1 课程设计的一般过程
1.1.1 课程设计安排
数据结构是一门实践性很强的课程，只靠读书和做习题是不能提高实践能力的，尤其
是在数据结构中要解决的问题更接近于实际。数据结构的实验是对学生的一种全面的综合
训练，与程序设计语言课程中的实验不同，数据结构课程中的实践多属创造性的活动，要
求学生能够根据实际问题来选择、扩展甚至是设计全新的数据结构，然后设计相应的存储
结构并加以实现，从而最终完成问题求解。数据结构的课程设计是一种自主性很强的学习
过程，其教学目标主要有两个：⑴ 深化理解和掌握课程的理论知识，将理论知识变
“活”；⑵ 理论和实践相结合，使学生学会如何把课堂上讲述的有关数据结构和算法的知
识用于解决实际问题，培养数据结构的应用能力和程序设计能力。
为了达到上述目标，本学期课程设计提供三类实验项目供学生选择：
⑴设计实验：其主要内容是针对具体问题，应用某一个知识点设计相应的数据结构和
算法，并上机实现，目的是培养学生对数据结构的简单应用能力；
⑵综合实验：其主要内容是针对具体问题，应用某几个知识点设计相应的数据结构和
算法，并上机实现，目的是培养学生对数据结构的综合应用能力。
⑶ 提升实验：其主要内容是针对 ACM-ICPC 中有关数据结构设计的具体问题，并学生
参加 CSP 认证及 PAT 能力测试进行前期培训。
设计实验和综合实验由问题描述、基本要求、设计思想、思考题等四部分组成，其中
问题描述是为学生建立问题的背景环境，指明“问题是什么”；基本要求是对问题的实现
进行基本规范，保证预定的训练意图，使某些难点和重点不会被绕过去，而且也便于教学
检查；设计思想给出了设计数据结构和算法的主要思路；思考题引导学生在做完实验后进
行总结和扩充。
虽然在设计实验和综合实验中都给出了一定的设计方案，但是，学生不应拘泥于这些分析
和设计，要尽量发挥想象力和创造力。对于一个实际问题，每个人可能会有不同的解决办
法，课程设计指导书给出的范例方案，只是希望把学生的思路引入正轨，提出了思考问题
的方法，但是不希望限制学生的思维，鼓励学生自己设计解决方案。
1.1.2 设计实验和综合实验的一般过程
设计实验和综合实验的自主性比较强，涉及到的知识点也比较多，可以在实验环节或
课程设计中完成，设计实验推荐单人完成，综合实验推荐多人完成，主要目的是为了培养
数据结构的应用能力、软件工程的规范训练、团队精神和良好的科学作风。
1. 问题分析
在设计实验和综合实验中的问题描述通常都很简洁，因此，首先要充分理解问题，明
确问题要求做什么，限制条件是什么，也就是对所需完成的任务做出明确的描述。例如：
