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

实验学时：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等