1 第2章 线性表
线性表是一种最基本、最常用的数据结构，它有两种存储结构——顺序表和链表。本章主要介绍线性表的定义、表示和基本运算的实现。重点讨论了线性表的存储结构，以及在顺序、链式两种存储结构上基本运算的实现。
重点提示：
线性表的逻辑结构特征
线性表的顺序存储和链式存储两种存储结构的特点
在两种存储结构下基本操作的实现
2-1 重点难点指导
2-1-1 相关术语
1．线性表
线性表是具有相同数据类型的n（n≥0）个数据元素的有限序列，通常记为：(a1,a2,…,an)，其中n为表长，n=0时称为空表。
要点：一种逻辑结构，其数据元素属于相同数据类型，之间的关系是线性关系。
2．顺序表
顺序存储的线性表。
要点：按线性表中的元素的逻辑顺序依次存放在地址连续的存储单元里，其存储特点：用物理上的相邻实现逻辑上的相邻。
3．链表
用链表存储的线性表。
要点：链表是通过每个结点的链域将线性表的n个结点按其逻辑顺序链接在一起的，对每个结点的地址是否连续没有要求。
4．单链表
每个结点除了数据域外还有一个指向其后继的指针域。
要点：通常将每个元素的值和其直接后继的地址作为一个结点，通过每个结点中指向后继结点的指针表示线性表的逻辑结构。
5．头指针
要点：头指针是一个指针变量，里面存放的是链表中首结点的地址，并以此来标识一个链表。如链表H，链表L等，表示链表中第一个结点的地址存放在指针变量H、L中。通常用头指针来惟一标识一个链表。
6．头结点
要点：附加在第一个元素结点之前的一个结点，头指针指向头结点。当该链表表示一个非空的线性表时，头结点的指针域指向第一个元素结点；为空表时，该指针域为空。
2 7．头结点的作用
要点：其作用有两个，一是使对空表和非空表的处理得到统一；二是在链表的第一个位置上的操作和在其他位置上的操作一致，无需特殊处理。
2-1-2 线性表的顺序存储
1．顺序表
一、单选题
1、线性表是具有n个 ______ 的有限序列。
A.数据项
B.字符
C.数据元素
D.表元素
正确答案：C
2、线性表是 _______。
A.一个无限序列，可以为空
B.一个有限序列不可以为空
C.一个无限序列，不可以为空
D.一个有限序列，可以为空
正确答案：D
3、关于线性表的正确说法是 _______。
A.每个元素都有一个前驱和一个后继元素
B.除第一个元素和最后一个元素外，其余元素有且仅有一个前驱和一个后继元素
C.表中元素的排序顺序必须是由小到大或由大到小
D.线性表中至少有一个元素
正确答案：B
4、线性表采用链表存储时，其存放各个元素的单元地址是 _______。
A.连续与否均可以
B.部分地址必须是连续的
C.一定是不连续的
D.必须是连续的 正确答案：A
5、链表不具备的特点是 _______。
A.插入删除不需要移动元素
B.所需空间与其长度成正比
C.不必事先估计存储空间
D.可随机访问任一节点
正确答案：D
6、线性表的静态链表存储结构与顺序存储结构相比，优点是 _______。
A.所有的操作算法实现简单
B.便于利用零散的存储器空间
C.便于随机存取
D.便于插入和删除
正确答案：D
7、线性表的顺序存储结构和链式存储结构相比，优点是 _______。
A.便于随机存取
B.便于插入和删除
C.所有的操作算法实现简单
D.节省存储空间
正确答案：A
8、设线性表有n个元素，以下操作中，_______在顺序表上实现比在链表上实现效率高。
A.交换第1个元素第2个元素的值
B.输出与给定值x相等的元素在线性表中的符号
C.输入第i（1<=i<=n）个元素值 D.顺序输出这n个元素的值
正确答案：C
9、对于一个线性表，既要求能够较快地进行插入和删除操作，又要求存储结构能够反映数据元素之间的逻辑关系，则应采用 _______ 存储结构。
A.顺序
C. P1.getData()=='' D. P 2.getNext()==null
习题二参考答案
一、选择题
1. 链式存储结构的最大优点是( D )。
A. 便于随机存取 B.存储密度高
C.无需预分配空间 D.便于进行插入和删除操作
2. 假设在顺序表｛ao,ai,……，an—1｝中，每一个数据元素所占的存储单元的数目为 4,且第0个数据元素的存储地
址为100,则第7个数据元素的存储地址是( D )。
A. 106 B. 107 C.124 D.128
3. 在线性表中若经常要存取第 i个数据元素及其前趋，则宜采用( A )存储方式。
A.顺序表 B.带头结点的单链表
C.不带头结点的单链表 D.循环单链表
4. 在链表中若经常要删除表中最后一个结点或在最后一个结点之后插入一个新结点，则宜采用( C )存储方
式。
A.顺序表 B.用头指针标识的循环单链表
C.用尾指针标识的循环单链表 D.双向链表
5. 在一个单链表中的p和q两个结点之间插入一个新结点， 假设新结点为S,则修改链的java语句序列是(D )。
A. s.setNext(p); q.setNext(s); B. p.setNext(s.getNext()); s.setNext(p);
C. q.setNext(s.getNext()); s.setNext(p); D. p.setNext(s); s.setNext(q);
6. 在一个含有n个结点的有序单链表中插入一个新结点， 使单链表仍然保持有序的算法的时间复杂度是 (C )。
A. O(1) B. O(log 2n) C. O(n) D. O(n2)
7. 要将一个顺序表｛a0,a 1,……，an-J中第i个数据元素a (0 < i < n-1)删除，需要移动(B )个数据元素。
A. i B. n-i-1 C. n-i D. n-i+1
8. 在带头结点的双向循环链表中的 p结点之后插入一个新结点 s，其修改链的java语句序列是(D )。
单元练习2
一．判断题（下列各题，正确的请在前面的括号内打√；错误的打╳ ）
（×）（1）线性表的链式存储结构优于顺序存储。
（×）（2）链表的每个结点都恰好包含一个指针域。
（√）（3）在线性表的链式存储结构中，逻辑上相邻的两个元素在物理位置上并不一定紧邻。
（×）（4）顺序存储方式的优点是存储密度大，插入、删除效率高。
（×）（5）线性链表的删除算法简单，因为当删除链中某个结点后，计算机会自动地将后续的各个单元向前移动。
（×）（6）顺序表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。
（√）（7）线性表链式存储的特点是可以用一组任意的存储单元存储表中的数据元素。
（√）（8）线性表采用顺序存储，必须占用一片连续的存储单元。
（×）（9）顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。
（ㄨ）（10）插入和删除操作是数据结构中最基本的两种操作，所以这两种操作在数组中也经常使用。
二．填空题
（1） 顺序表中逻辑上相邻的元素在物理位置上 必须 相连。
（2） 线性表中结点的集合是有限的，结点间的关系是 一对一 关系。
（3） 顺序表相对于链表的优点是： 节省存储 和随机存取。
（4） 链表相对于顺序表的优点是： 插入、删除 方便。
（5） 采用 顺序 存储结构的线性表叫顺序表。
（6） 顺序表中访问任意一个结点的时间复杂度均为 O(1) 。
（7） 链表相对于顺序表的优点是插入、删除方便；缺点是存储密度 小 。
（8） 在双链表中要删除已知结点*P，其时间复杂度为 O(1) 。
（9） 在单链表中要在已知结点*P之前插入一个新结点，需找到*P的直接前趋结点的地址，其查找的时间复杂度为 O(n) 。
（10） 单链表中需知道 头指针 才能遍历整个链表。
（11） 线性表中第一个结点没有直接前趋，称为 开始 结点。
