实验大纲+《数据结构》+廖雪花

《数据结构》实验教学大纲

实验学时：24

程

实验个数：7 实验学分： 1.5

适用专业： 计算机科学与技术、网络工程、软件工

课程性质：专业必修课 教材及参考书：

1. 《数据结构（C语言版）》，严蔚敏 吴伟民，北京：清华大学出版社，2004

2.

《数据结构题集（C语言版）》实习题部分，北京：清华大学出版社，2004；

3. 《数据结构实验教程》，王玲 刘芳等著，成都：四川大学出版社，2002 4. 《数据结构实验》，刘芳 揭安全等著，重庆：西南师范大学出版社，2010 大纲执笔人：刘芳

一、实验课的性质与任务

本课程实验大纲是面向计算机相关专业学生开设的《数据结构》实验课计划指导大纲，是依据《数据结构》课程教学计划指导大纲编制。

计算机编程中加工处理的对象是数据，而数据具有一定的组织结构，所以学习编写计算机程序仅仅了解计算机语言是不够的，还必须掌握数据组织、存储和运算的一般方法，这是数据结构课程中学习和研究的内容。由于数据结构的原理和算法较抽象，而该课程一般在本科低年级开设，对于计算机程序设计知识的初学者，理解和掌握其中的原理就显得较为困难。数据结构实验课程着眼于数据结构原理和应用的结合点，使读者学会如何将书上学到的知识用于解决实际问题，培养软件工作需要的动手能力；另一方面，能使书上的知识变“活”，起到深化理解和灵活掌握教学内容的目的。

本实验课程主要结合数据结构课程的教学大纲的相应内容，设计了7个实验（包括验证型、综合型、设计型实验），力求提高学生的动手能力，做到理论和实践相结合。使学生在实验过程中进一步掌握典型数据结构的逻辑结构、存储结构及算法的程序实现，并训练问题的综合分析能力和编程能力，形成良好的编程风格，为后续课程的学习奠定坚实的理论和实践基础。

大纲审定人：郭涛

二、实验课程目的与要求

1. 实验目的

根据《数据结构》课程的任务与要求，帮助学生拓宽知识面。并达到以下教学要求： （1） 学会分析研究计算机加工的数据结构的特性，以便为应用涉及的数据选择适当的逻

辑结构、存储结构及其相应的算法，并初步掌握算法的时间分析和空间分析的技术；掌握各种基本数据结构的逻辑结构和存储结构及相应算法。

（2） 本课程的学习过程也是复杂程序设计的训练过程，要求学生编写的程序结构清楚、

正确易读，符合软件过程的规范，从而培养学生的数据抽象能力；

（3） 通过若干数据结构应用实例，引导学生学习数据类型的使用，为今后学习面向对象

的程序做一些铺垫。

2. 实验要求

（1） 熟悉各种基本数据结构的定义，性质和特点，初步掌握算法分析的基本技巧以及如

何根据实际问题设计一个有效的算法。

（2） 会书写类C语言的算法，并将算法转变为程序实现。

（3） 正确理解各种数据结构的逻辑特性和存储表示和基本操作的算法实现，有较强的逻

辑分析能力。

（4） 针对问题的不同选择合适的数据结构，提高算法设计的能力和动手实验的技能。

三、实验内容安排：

实验一 抽象数据类型的表示与实现 （基本操作、验证型实验 2学时）

1.目的要求：

（1） 熟悉类C语言的描述方法，学会将类C语言描述的算法转换为C源程序实现； （2） 理解抽象数据类型的定义，编写完整的程序实现一个抽象数据类型（如三元组）； （3） 认真阅读和掌握本实验的参考程序，上机运行程序，保存和打印出程序的运行

结果，并结合程序进行分析。

2.实验内容：

（1） 编程实现对一组从键盘输入的数据，计算它们的最大值、最小值等，并输出。

要求：将计算过程写成一个函数，并采用引用参数实现值的求解。

（2） 编程实现抽象数据类型三元组的定义、存储和基本操作，并设计一个主菜单完

成各个功能的调用。

注：（1）为必做题，（2）选做。 3.主要仪器设备及软件

（1） PC机

（2） Dev C++ ,Visual C++, VS2010等

实验二 线性表及其实现 （基本操作、验证型实验 4学时）

1.目的要求：

（1） 熟悉线性表的基本运算在两种存储结构（顺序结构和链式结构）上的实现，以

线性表的各种操作（建立、插入、删除等）的实现为实验重点；

（2） 通过本次实验帮助学生加深对顺序表、链表的理解，并加以应用； （3） 掌握循环链表和双链表的定义和构造方法 2. 实验内容：

（1） 编程实现线性表两种存储结构（顺序存储、链式存储）中的基本操作的实现（线

性表的创建、插入、删除、查找（顺序查找、折半查找）、排序等），并设计一个菜单调用线性表的基本操作。

（2） 建立一个按元素递增有序的单链表L，并编写程序实现：

a） b） c）

将x插入其中后仍保持L的有序性；

将数据值介于min和max之间的结点删除，并保持L的有序性； 将单链表L逆置并输出；

（3） 编程实现将两个按元素递增有序的单链表合并为一个新的按元素递增的单链表。 注：（1）为必做题，（2）~（3）选做。

3.主要仪器设备及软件

（1） PC机

（2） Dev C++ ,Visual C++, VS2010等

实验三 栈和队列及其应用 （验证型、设计型实验 4学时）

1.目的要求：

（1） 掌握栈和队列这两种特殊的线性表，熟悉它们的特性，在实际问题背景下灵活

运用它们；

（2） 本实验训练的要点是“栈”的观点及其典型用法；

（3） 掌握问题求解的状态表示及其递归算法，以及由递归程序到非递归程序的转化

方法。

2.实验内容：

（1） 编程实现栈在两种存储结构中的基本操作（栈的初始化、判栈空、入栈、出栈

等）；

（2） 应用栈的基本操作，实现数制转换（任意进制）；

（3） 编程实现队列在两种存储结构中的基本操作（队列的初始化、判队列空、入队

列、出队列）；

（4） 利用栈实现任一个表达式中的语法检查（括号的匹配）。 （5） 利用栈实现表达式的求值。 注：（1）～（3）必做，（4）～（5）选做。 3.主要仪器设备及软件

（1） PC机

（2） Dev C++ ,Visual C++, VS2010等

实验四 字符串、稀疏矩阵实验

（验证型实验 2学时）

1.目的要求：

（1） 熟悉字符串类型的实现方法，并完成串的一些基本操作； （2） 掌握稀疏矩阵的三元组顺序表存储表示，并实现矩阵的转置运算。 2.实验内容：

（1） 编程实现两个串S1和S2的比较。（要求自己设计串的存储结构，并编写比较函

数，不要调用系统提供的函数）

（2） 编程实现稀疏矩阵的三元组顺序表示方法及基本操作的实现（建立、输出、转

置等）。

（3） 编程实现稀疏矩阵的十字链表存储表示及基本操作的实现（建立、输出等）。 注：（2）必做，（1）（3）选做。

3.主要仪器设备及软件

（1） PC机

（2） Dev C++ ,Visual C++, VS2010等

实验五 二叉树及其应用 （验证型、综合型实验 4学时）

1.目的要求：

（1） 通过实验掌握二叉树的两种基本的存储结构，及二叉树的建立、遍历，并加以

应用。

（2） Huffman树建立、编码。 2.实验内容：

（1） 按先序次序输入二叉树中结点的值，建立一棵以二叉链表作存储结构的二叉树，

然后按先序、中序、后序顺序分别遍历这棵二叉树，并完成二叉树的相应信息的统计（如各种结点数目、二叉树的高度等）；

（2） 建立一棵二叉排序树，并对其进行先序、中序、后序遍历。 （3） 应用队列结构实现二叉树的层次遍历。

（4） 设计一个完整的编码系统：针对一篇文档，统计各个字符的出现次数，并为其设

计Huffman编码。

注：（1）～（2）必做，（3）～（4）选做。 3.主要仪器设备及软件

（1） PC机

（2） Dev C++ ,Visual C++, VS2010等

实验六 图及其应用 （验证型、综合型实验 4学时）

1.目的要求：

（1） 通过完成本实验，掌握图的两种基本的存储结构（邻接矩阵、邻接表），以及图

的基本算法实现（建立、遍历），并能运用图结构分析解决一些实际问题。

（2） 本实验训练的要点是：图的两种基本存储结构，及各种操作的算法实现（建立、

遍历、图的典型应用）。

2.实验内容：

（1） 建立无向图和有向图的邻接矩阵存储，计算顶点的度，并输出图的基本信息。 （2） 建立有向图的邻接表存储表示，并根据存储计算顶点的出度和入度，然后输出

图的基本信息。

（3） 编写完整的程序实现AOV网的拓扑排序。 （4） 编程求AOE网的关键路径。

（5） 编程实现单源点最短路径的Dijkstra算法。 注：（1）～（2）必做，（3）～（5）选做。 3.主要仪器设备及软件

（1） PC机

（2） Dev C++ ,Visual C++, VS2010等

实验七 查找和排序算法的实现 （基本操作、验证型实验 2学时）

1.目的要求：

（1） 学生在实验中体会各种查找和内部排序算法的基本思想、适用场合，理解开发

高效算法的可能性和寻找、构造高效算法的方法。

（2） 掌握运用查找和排序解决一些实际应用问题。 2.实验内容：

（1） 编程实现一种查找算法（如折半查找、二叉排序树的查找、哈希查找等），并计

算相应的ASL。

（2） 编程实现一种内部排序算法（如插入排序、快速排序等）。

注：该部分的教学内容在教材上分别是第9章和第10章，由于相关的教学内容在教学过程中进行了调整（将查找和排序的内容融入在第2章 线性表、第6章 树和二叉树的教学中进行，实验的内容也是穿插在相应的实验中完成。在学生提交实验报告时，不必单独提交实验7，可以将实验内容在教学对应的章节实验中完成。） 3.主要仪器设备及软件

（1） PC机

（2） Dev C++ ,Visual C++, VS2010等