《数据结构实验》教学大纲
课程英文名称（Experiments of Data Structures）
课程代码：BK002023学时：16学分：0.5
适用专业：测绘，遥感课程性质：必修
撰稿人：朱红梅审定人：张继军
一、实验课的性质与任务
本课程是该专业主干必修课程《数据结构》的同步实践课程，依据《数据结构》课程教学计划指导大纲编制。计算机编程中加工处理的对象是数据，而数据具有一定的组织结构，所以学习编写计算机程序仅仅了解计算机语言是不够的，还必须掌握数据组织、存储和运算的一般方法，这是数据结构课程中学习和研究的内容。由于数据结构的原理和算法较抽象 而该课程一般在本科低年级开设，学生理解和掌握其中的原理较为困难。数据结构实验课程着眼于数据结构原理和应用的结合，使学生学会将书本上学到的知识用于解决实际问题，培养软件工作需要的动手能力。本课程的实践与操作是对学生的一种全面综合训练，是与课堂听讲、自学和练习相辅相成的必不可少的一个教学环节。本实验课程的任务是使学生在实验过程中进一步掌握典型数据结构的逻辑结构、存储结构及算法的程序实现，通过实验深化理解和灵活掌握教学内容，并训练问题的综合分析、解决的能力和编程能力，形成良好的编程风格，同时，培养学生的工作规范和科学作风，为后续课程的学习奠定坚实的理论和实践基础。
二、实验目的与要求
实验目的：学会分析研究计算机加工的数据结构的特性，以便为应用涉及的数据选择适当的逻辑结构、存储结构及其相应的算法 并初步掌握算法的时间分析和空间分析的技术 掌握各种基本数据结构的逻辑结构和存储结构及相应算法。本课程的学习过程也是复杂程序设计的训练过程，要求学生编写的程序结构清楚，正确易读，符合软件过程的规范，从而培养学生的数据抽象能力。通过若干数据结构应用实例，引导学生学习数据类型的使用。
实验要求：熟悉各种基本数据结构的定义，性质和特点，初步掌握算法分析的基本技巧以及如何根据实际问题设计一个有效的算法。会书写类C++语言的算法，并将算法转变为程序实现。正确理解各种数据结构的逻辑特性和存储表示和基本操作的算法实现，有较强的逻辑分析能力。针对问题的不同选择合适的数据结构，提高算法设计的能力和动手实验的技能。
三、实验项目设置情况
序号 | 实验项目名称 | 学时 | 开出要求 | 实验项目类型 |
必做 | 选做 | 基础型 | 综合设计 | 研究创新 |
演示 | 验证 |
1 | 线性表的顺序存储结构的实现 | 2 | √ |
| | | √ | |
2 | 线性表的链接存储结构的实现 | 2 | √ |
|
|
| √ |
|
3 | 栈的算法实现及应用 | 2 | √ | | | | √ | |
4 | 队列的算法实现及应用 | 2 | √ | | | | √ | |
5 | 二叉树的基本操作和应用 | 2 | √ | | | | √ | |
6 | 图及其应用 | 2 | √ | | | | √ | |
7 | 基本查找算法实现 | 2 | √ | | | | √ | |
8 | 基本排序算法实现 | 2 | √ | | | | √ | |
9 | | | | | | | | |
| | | | | | | | |
四、各实验项目教学内容
实验项目一：线性表的顺序存储结构的实现2学时
（一）实验目的要求
实验目的：熟悉顺序表的逻辑特性、存储表示方法和顺序表的基本操作。
实验要求：了解并熟悉顺序表的逻辑特性、存储表示方法和顺序表的基本操作的实现和应用。
（二）实验材料和仪器设备
硬件：计算机
软件：Windows 系列操作系统，Micro Soft Visual C++ 6.0或CodeBlocks8.0以上集成开发环境
（三）实验内容
编写程序实现下列的要求：
(1) 设数据元素为整数，实现这样的线性表的顺序存储表示。
(2) 键盘输入10个数据元素，利用顺序表的基本操作，建立该表。
(3) 利用顺序表的基本操作，找出表中的最大的和最小的数据元素（用于比较的数据元素为整数）。
实验项目二：线性表的链接存储结构的实现2学时
（一）实验目的要求
实验目的：熟悉链式表的逻辑特性、存储表示方法的特点和链式表的基本操作。
实验要求：了解并熟悉顺序表的逻辑特性、存储表示方法和顺序表的基本操作的实现和应用。
（二）实验材料和仪器设备
硬件：计算机
软件：Windows 系列操作系统，Micro Soft Visual C++ 6.0或CodeBlocks8.0以上集成开发环境
（三）实验内容
编写程序实现下列的要求：
(1) 设数据元素为整数，实现这样的线性表的顺序存储表示。
(2) 键盘输入10个数据元素，利用顺序表的基本操作，建立该表。
(3) 利用顺序表的基本操作，找出表中的最大的和最小的数据元素（用于比较的数据元素为整数）。
实验项目三：栈的算法实现及应用2学时
（一）实验目的要求
实验目的：熟悉栈的逻辑特性、存储表示方法和栈的基本操作。
实验要求：了解并熟悉栈的逻辑特性、顺序和链式存储表示方法和栈的基本操作的实现和应用。
（二）实验材料和仪器设备
硬件：计算机
软件：Windows 系列操作系统，Micro Soft Visual C++ 6.0或CodeBlocks8.0以上集成开发环境
（三）实验内容
编写程序实现下列的要求：
(1)编写程序，用不同的存储方法，实现栈的基本操作。
(2) 判断一个表达式中的括号（仅有一种括号，小、中或大括号）是否配对。编写并实现它的算法。
(3) * 若表达式中既有小括号，又有大括号（或中括号），且允许互相嵌套，但不能交叉，写出判断这样的表达式是否合法的算法。如 2+3*（4-{5+2}*3）为合法；2+3*（4-{5+2* 3} 、2+3*（4-[5+2* 3）为不合法。
实验项目四：队列的算法实现及应用2学时
（一）实验目的要求
实验目的：熟悉队列的逻辑特性、存储表示方法和队列的基本操作及应用。
实验要求：了解并熟悉队列的逻辑特性、顺序和链式存储表示方法和队列的基本操作的实现和应用。
（二）实验材料和仪器设备
硬件：计算机
软件：Windows 系列操作系统，Micro Soft Visual C++ 6.0或CodeBlocks8.0以上集成开发环境
（三）实验内容
编写程序实现下列的要求：
(1)编写程序，用不同的存储方法，实现队列的基本操作。
(2)*迷宫问题：求解m*n迷宫问题，输出解的个数及每个解。编写并实现它的算法。
实验项目五：二叉树的基本操作和应用2学时
（一）实验目的要求
实验目的：熟悉树的基本概念，树状结构的逻辑特性、存储表示方法和二叉树的基本操作。
实验要求：熟悉树的基本概念，树状结构的逻辑特性、存储表示方法和树的基本操作，实现二叉树的遍历算法（前序、中序和后序遍历）及其简单应用。
（二）实验材料和仪器设备
硬件：计算机
软件：Windows 系列操作系统，Micro Soft Visual C++ 6.0或CodeBlocks8.0以上集成开发环境
（三）实验内容
编写程序，用二叉链表存储表示方法，实现二叉树的基本操作。
(1) 根据扩展二叉树的前序遍历序列，建立二叉树。
(2) 根据二叉树的前序和中序遍历序列，构造二叉树。
(3) 实现二叉树的前序、中序和后序遍历，输出遍历结果。
实验项目六：图及其应用2学时
（一）实验目的要求
实验目的：熟悉图的基本概念、逻辑特性、存储表示方法、基本操作和基本应用。
实验要求：熟悉图的基本概念、逻辑特性、存储表示方法，实现无向网的存储表示、图的深度优先搜索遍历、广度优先搜索遍历、单源最短路径算法。
（二）实验材料和仪器设备
硬件：计算机
软件：Windows 系列操作系统，Micro Soft Visual C++ 6.0或CodeBlocks8.0以上集成开发环境
（三）实验内容
编写程序，实现以下功能：
(1) 实现交通网、通信网或局域网的邻接矩阵存储表示，设数据元素类型为字符串（如地名、房间号等）。
(2) 实现该网的深度优先搜索遍历，输出遍历结果。
(3) *实现上述网络的邻接表存储表示，实现其广度优先搜索遍历，输出遍历结果。
(4) *求从一个地点到其它各个地点的最短路径。
实验项目七：基本查找算法实现2学时
实验目的要求
实验目的：熟悉顺序查找和二分查找方法。
实验要求：实现顺序查找和二分查找方法。
（二）实验材料和仪器设备
硬件：计算机
软件：Windows 系列操作系统，Micro Soft Visual C++ 6.0或CodeBlocks8.0以上集成开发环境
（三）实验内容
编写程序，实现以下功能：
(1) 建立一个整数构成的顺序表。
(2) 根据用户输入的查找值，实现顺序表的顺序查找。
(3) 建立一个有序的整数构成的顺序表（可直接利用前面排序实验的结果）。
(4) 根据用户输入的查找值，实现二分查找，并输出比较的元素、元素的比较次数等。要求实现递归和非递归算法。
(5) *模拟统计查找长度，随机产生100，200，500，1000，2000等若干个随机整数，在（3）中定义的有序表中查找这些值，统计查找成功和查找不成功的平均查找长度。
实验项目八：基本排序算法实现2学时
实验目的要求
实验目的：熟悉常用基本排序算法及其特点和效率。
实验要求：实现基本排序算法，并对待排序的数据进行排序。
（二）实验材料和仪器设备
硬件：计算机
软件：Windows 系列操作系统，Micro Soft Visual C++ 6.0或CodeBlocks8.0以上集成开发环境
（三）实验内容
假设待排序数据是整型。编写程序，实现以下功能：
(1)实现选择排序（直接选择排序）、插入排序（直接插入排序）和交换排序（快速排序、冒泡排序）、*归并排序等各种排序方法
(2)对于(1)实现的插入排序（直接插入排序）和交换排序（快速排序、冒泡排序），分别输出每一趟（遍）的结果和最终结果，并应用它对上面的数据序列进行排序。
(3) 输入或给定若干个已经有序或逆序的线性表，分别利用选择排序（直接选择排序）、插入排序（直接插入排序）和交换排序（快速排序、冒泡排序）、*归并排序等各种排序方法对他们进行排序，并输出他们各自的比较和移动记录次数。检验实际结果（运行时间和比较、移动记录次数）和理论结果的差异，并进行讨论各种方法的优劣。
(4)* 证明快速排序算法是不稳定的。
(5) * 随机产生100，200，500，1000，2000等若干个随机整数，并将他们存到一个线性表中，再实现（3）的要求。
五、实验报告要求
1.需求和规格说明（问题描述）
描述问题，简述题目要解决的问题是什么，规定软件做什么，原题条件不足时要补全。
2.设计
设计思想：存储结构，主要算法的基本思想。不要画框图。
设计表示：每个函数或过程的头和规格说明；列出每个函数或过程所调用和被调用的过程和函数。
详细设计表示：主要算法的框架。
3. 用户手册：即使用说明，如输入怎样的数据、输入多少、何时输入、如何结束等。
4. 调试报告：测试用例，测试结果，调试过程中遇到的主要问题是如何解决的；对设计和编码的回顾讨论和分析；改进设想；经验和体会等。
5. 附录：源程序清单和结果。程序要加注释，还可手工添加一些注释。测试数据及输出结果。
六、课程考核方式及成绩评定
（一）考核方式
平时成绩：ð课堂提问//☑学习态度//ð课外资料收集整理//ð预习报告//☑实验报告//☑其他；
结课后考试：ð笔试//☑操作。
（二）课程成绩评定办法
成绩构成：考勤10%//平时20%//考试70%
七、实验应配套的主要仪器设备及台（套）数（以一个实验教学班为标准）
硬件：计算机
软件：Windows 系列操作系统，Micro Soft Visual C++ 6.0或CodeBlocks8.0以上集成开发环境
30套/实验教学班
附：教学参考资料
1、选用的教材：
1、选用的教材：
王红梅，胡明，王涛编著，数据结构（C++版）， 清华大学出版社，2011.6，第2版。
2、主要参考书：
[1] 严蔚敏等，《数据结构》，清华大学出版社（C语言版，），1997，第1版。
[2] 殷人昆，数据结构 C＋＋实现，清华大学出版社，1999，第1版。
[3] 耿国华，数据结构-C语言描述，高等教育出版社，2005第1版。
3、其他参考资料：
[1] OpenJudge开放的在线程序评测系统,http://openjudge.cn/。
[2] 杭州电子科技大学开放的在线程序评测系统Online Judge,http://acm.hdu.edu.cn/.