2010数据结构实验指导书48

实验一 线性表

实验目的

1、 掌握线性表的逻辑结构和物理实现；

2、 掌握线性表的顺序存储结构和链式存储结构，熟悉对线性表的基本操作； 3、 在学有余力的情况下，掌握循环链表的实现及其基本操作；

4、 根据实验要求设计并完成程序，把理论的基本操作知识转化到实际的实践应用中。

实验原理

线性表是最简单的一种数据结构。线性表是由n（n>=0）个数据元素组成的有限序列。线性表中的数据元素可以是各种各样的，但同一线性表中的数据元素必须有相同的属性，因此是属于同一数据类型的。

在计算机内，可以用不同的方式来表示线性表，其中最简单和最常用的方式是用一组地址连续存储单元依次存储线性表中的元素。其特点是逻辑关系上相邻的两个元素在物理位置上也相邻。一般地，线性表的顺序存储结构可用一个一维数组结构来描述。用这种方法存储的线性表简称为顺序表。线性表的链式存储结构（也称链表）的特点是用一组任意的存储单元存储线性表中的数据元素，不要求逻辑上相邻的元素在物理位置上也相邻。链表中的结点可用C语言中的结构数据类型来描述，也可以用C++语言中类来实现。链表中的结点只有一个链域的链表称为单链表。循环链表则是一种首尾相接的链表。

对线性表首先要掌握作为抽象数据类型（ADT）的那些基本操作，其次才是具体实现的细节。

实验要求（课题一必做，课题二选做）

实验课题一：

a、（C++语言实现）：

1、 使用教材参考代码中给出的线性表类构造一个表，查找表内是否有某元素，如果有则交换该元素和

它相邻的下一元素的位置；

2、 （2和3中选一个即可）为链表类List增加一个成员函数reverse，使其具备能倒置链表中元素的功

能。写好的表倒置函数的时间复杂度应该是 (n)；

3、 为List链表实现增加逆转迭代器类（reverse iterators），并增加方法rbegin和rend，具体要求参见

教科书109页习题3.16。

b、（C语言实现）在给出参考代码中给出的线性表结构体以及与之相关的函数的基础上，编写程序，实现

以下操作：

1、构造一个表，然后查找表内是否有某元素，如果有则交换该元素和它相邻的下一元素的位置； 2、写一个函数reverse，使其能倒置线性表中元素。这个表倒置函数的时间复杂度应该是 (n)。 课题一的具体实验内容

1、构造元素类型为整型的线性表，将以下元素插入分别插入线性表：

<34 56 20 9 15 5> 2、查找表中是否存在元素20，实现元素20与元素9的交换；