数据结构实验讲义(校)

《数据结构实验讲义(校)》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、数据结构实验指^导（C语言版）李岩芳何巍李晓荣内容简介《数据结构实验讲义》（C语言版）是为配合数据结构课程的教学，加强学牛对数据结构的抽彖数据类型的理解，提高学牛分析问题、解决问题的能力，及对学牛进行数据结构算法的实际应用技能的训练而编写的讲义，也对作为教师讲解数据结构及其算法、指导学生上机的参考资料。本实验讲义按照数据结构课程的教学内容分别描述了线性、树形、图形、集合四种数据结构的抽象数据类型及其它们的基本操作算法在C语言平台上的实现过程，特别注重对算法的分析及理解，并进行了适当的拓展提问，方便学生更加深入地理解数据结构的抽彖数据类型的描述。目录引言4实验一：顺序存储的线

2、性表的操作6实验二：链式存储的线性表的操作23实验三：栈的操作35实验四：循环队列的操作47实验五：数组的操作56实验六：树的操作69实验七：图的操作78实验八：排序92引言数据结构是一门研究非数值计算程序设计问题中的计算机操作对彖以及它们z间关系和操作等的学科。数据的组织结构以及対这些结构化数据操作的实现是这门学科的核心问题。而以数据对象、数据关系和基本操作为考察内容的抽象数据类型正好体现了这门学科的研究中心。所以对抽象数据类型的理解是掌握数据结构的基础。线性结构、树形结构和图形结构是三种基本的抽象数据类型。对这三种抽彖数据类型的实现和应川的理解和掌握，不但是学习数据结构

3、的基本要求，也是学习数据结构的基木手段和方法。这三种抽象数据类型除了有空间上的可理解性以外，也具冇操作上的易理解性。所以，在学习数据结构的时候，除了建立空间上数据的关系和操作概念以外,通过实际操作实现这些基木抽象数据类型，是降低抽象数据类型的抽象性，提高对数据结构理解能力的一个有效途径。这也是发挥数据结构在设计和实现中主导作用的必经Z路。木书正是从这三种某本抽象数据类型的数据描述、结构与操作分析和算法实现等入手，从实践的角度对抽象数据类型和数据结构进行了讲解和阐述。在基本抽象数据类型空间概念的基础Z上，重点讲述了基于这些抽彖数据类型、基于所包含元素及其关系的操作的实现过程。

4、同时，在对本书的学习过程中，希望读者能重点体会：1.抽象数据类型的概念。即：数据对彖、数据关系以及这Z上的操作。数据及其关系是实现操作的基础。而操作是抽象数据类型特性的真止体现。2.线性结构、树形结构和图形结构这三种基本抽象数据类型的结构特性和操作特性。对这三种抽彖数据类型的理解和应用不仅是其他后续课程的基础，也是应用系统设计实现的基础。3.算法实现对物理结构的依赖性。抽象数据类型所描述的操作，只是一种逻辑操作,具体的实现依赖丁•对这个抽象数据类型元素的物理存储结构。比较有代表性的例子就是:以顺序存储结构和链式存储结构为皋础的线形表，基木操作的算法却完全不同。4.程序的实现

5、过程人体上是从结构设计、算法设计到算法实现。应该在学习程序设计的开始培养好这种良好习惯。把结构和算法设计作为程序设计的一个重要任务來完成。结构和算法设计上的缺陷，将导致程序的最终失败。木书设计有八个实验。实验一到实验五为线性结构的设计与应用。实验六和实验七分别为树形结构和图形结构的设计与应用。实验八排序是基于线性结构的具体应用，也是数据结构课程中的经典算法。书中每个实验都分为实验目的及要求、实验内容、功能函数的分析设计及源代码和习题四个部分。其中，源代码为参考代码，供读者在编码的时候参考。正确设计程序结构，书写流程图和独立完成编码是非常亜要的一种能力，希望读者能够从本书中得

6、到借鉴。实验一：顺序存储的线性表的操作-＞实验目的及要求1.理解线性表顺序存储的抽象数据类型的定义，及在C语言环境中的表示方法。2.理解线性表在顺序存储时的基木操作的算法，及在C语言环境中一些主要基木操作的实现。3.在C语言环境下实现线性表在顺序存储时的应用操作：将两个非递减的线性表合并成一个新的非递减的线性表。二、实验内容经过对实验目的及要求的分析，确定了本实验实现如图1.1所示的功能。线性表顺序存够功能一览表11输输插删査判输输合入IH入除找断in111并线线元元指线指指两性性索索定性定定个表表元表兀兀线元元素是素素性素索否的的表为前后空驱继7G7E素素图1.1SqLi

7、st.c程序功能一览表在合并两个线性表这个功能上，用两种方式实现，一•种是利用己有的基本操作集完成合并，另一种是对线性表进行直接合并操作。因此，本实验编写了两个程序：SqList.c,包含基本操作集函数及利用基本操作集函数编写的合并线性表的函数。SqlMerge.c,没有利用基本操作集函数，直接对线性表操作实现两个线性表的合并。在SqList.c中包含的函数如图1.2所示。r1建取查输输插删访输比清判销合立示线找出出入除问出较空断毀并线线性指指指兀兀线兀两线线线线性性表定定定素素性索个性性性性表表指元元元表儿农农农