003线性表的定义和基本操作

学习要求

在前面提到过，数据结构的逻辑结构有线性结构和非线性结构，线性结构的元素是具有前趋和后续的 1:1 的关系。非线性结构有集合、图、树。

本篇讨论的线性表是线性结构，要求掌握线性表的定义和基本操作。

线性表的定义和基本操作

【1】线性表的定义

线性表示例：

A、B、C、D ... Z 等26个字母组成的英文字母表。

线性表(Linear List)可以表示由 n(n≧0) 个数据元素(结点)组成的有限序列，其中元素个数 n 表示为表的长度。当 n = 0 时，称为空线性表。

【2】线性表的种类

线性表是数据结构中的一种逻辑结构，而在存储结构中，线性表有顺序存储结构和链式存储结构，前者称为顺序表，后者称为链表。

（1）顺序表

把线性表中的每个元素按照其逻辑顺序，依次存储到指定的存储位置开始的一块连续存储空间中。

顺序表具有两个特性，第一个是随机访问特性，只需要知道它的位置(结点序号)就可以马上找到它。第二个特性是顺序表要求占用连续的存储空间。

顺序表做插入操作时需要移动多个元素。

（2）链表

在链表存储结构中，每个结构不仅包含所存元素的信息，还包含元素之间的逻辑关系的信息。链表还有单链表、双链表、循环单链表、循环双链表、静态链表。

链表不支持随机访问，必须在从 HEAD 开始查找；并且链表个每个结点必须划出一些空间来存储指向下一个结点位置的指针，链表中的结点可以散落在内存的任何位置。

下图为单链表。

[图：https://www.studytonight.com/data-structures/linear-linked-list]

测试

1．将l6个数据元素的线性表按顺序存储方式存储在数组中，若第一个元素的存储地

址是l000，第6个元素的存储地址是1040，则最后一个元素的存储地址是

A．1112 B．1120 C．1124 D．1128

2．线性表是一种由 n 个数据元素组成的数据结构，n 的取值是：

A.0或任意一个正整数

B.非负整数

C.任意一个正整数或∞

D.某个正整数

3．线性表的存储方式中，能够随机存取表中任一元素的存储结构是 ____ 。

4．下列选项中，属于顺序存储结构优点的是

A．插入运算方便 B．删除运算方便

C．存储密度大 D．方便存储各种逻辑结构

5．某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，

则下列存储结构中，最节省运算时间的是

A．单链表 B．仅有头指针的单循环链表

C．双向链表 D．仅有尾指针的单循环链表

注：后面文章介绍；

6．用不带头结点的单链表存储队列，在进行删除运算时

A．仅修改头指针 B．仅修改尾指针

C．头、尾指针一定都要修改 D．头、尾指针可能都要修改

注：后面文章介绍；

答案：1，B；2，A；3，顺序存储结构 ；4，C；5，D；6，D；