复习三：线性表
一、线性表定义
线性表是具有
相同
数据类型的n
（n
>
0
）
个
数据元素
的
有限序列
,其中
n
为表长
，
当
n
=
0
时线性表是一个空表
。
线性表是一种逻辑结构，顺序表与链表是存储结构
线性表特点：
- 表中元素的个数有限
- 表中元素具有逻辑上的顺序性，表中元素有其先后次序。
- 表中元素都是数据元素，每个元素都是单个元素。
- 表中元素的数据类型都相同，这意味着每个元素占有相同大小的存储空间。
- 表中元素具有抽象性，即仅讨论元素间的逻辑关系，而不考虑元素究竟表示什么内容。
二、顺序表
线性表的顺序存储又称顺序表。顺序表的特点是表中元素的逻辑顺序与其物理顺序相同；
顺序表最主要的特点是
随机访问
，
即通过首地址和元素序号可在时间
0(1)
内找到指定的
元素
。顺序表的存储密度高，
每个结点只存储数据元素
。 顺序表逻辑上相邻的元素物理上也相邻，
所以
插入和删除操作需要移动大量元素
。
静态顺序表定义【用数组表示】
动态顺序表定义【利用指针、malloc()函数】
初始动态分配语句
动态分配并不是链式存储、它同样属于顺序存储结构，物理结构没有变化，依然是随
机存取方式，只是分配的空间大小可以在运行时动态决定。
三、顺序表基本操作
(1)
插入操作
在顺序表L的第
i
(l<=i<=L.
length+1)
个位置插入新元素
e
。
若
i
的输入不合法
，
则返回false,
表示插入失败
；
否则
，
将第
i
个元素及其后的所有元素依次往后移动一个位置
，
腾岀一个空位置插入新元素e,
顺序表长度增加1
,
插入成功
，
返回
true
。
最好情况∶在表尾插入（即 i=n+1），元素后移语句将不执行，时间复杂度为 O（1）。
最坏情况∶在表头插入（即i=1），元素后移语句将执行n次，时间复杂度为O（n）。
平均情况∶时间复杂度为
0(n
)
。
(2)
删除操作
删除顺序表L中第
i
(l<=i<=L.
length)
个位置的元素
，
用引用变量
e
返回
。
若
i的输入不合法，则返回false；否则，将被删元素赋给引用变量e,并将第i+ l个元素及其后的所有
元素依次往前移动一个位置
，线性表长度减一，返回true
最好情况
：
删除表尾元素(即
i
=n)
,无须移动元素，时间复杂度为0(1)。
最坏情况
：
删除表头元素(即i=l),需移动除表头元素外的所有元素，时间复杂度为0(n)
。
平均情况：时间复杂度为O(n)
(3)按值查找(顺序查找)
在顺序表L中查找第一个元素值等于
e
的元素
，
并返回其位序
。
四、顺序表的链式表示
1、单链表：线性表的链式存储又称单链表，它是指通过一组任意的存储单元来存储线性表中的数据元素。单链表结点结构如图2.3所示，其中data为数据域，存放数据元素；next为指针域，存放其后继结点的地址。
单链表中结点类型：
头结点和头指针的区分
：
不管带不带头结点
，
头指针都始终指向链表的第一个结点
，
而头结
点是带头结点的链表中的第一个结点
，
结点内通常不存储信息
2、单链表的创建
（1）头插法建立单链表：将新结点插入到当前链表的表头
，
即头结点之后
采用头插法建立单链表时，读入数据的顺序与生成的链表中的元素的顺序是相反的。每个结
点插入的时间为O1），设单链表长为n，则总时间复杂度为 O（n）
（2）尾插法建立单链表：将新结点插入到当前链表的表尾，为此必须增加一个尾指针r，使其始终指向当前链表的尾结点
3、双链表
双链表结点中有两个指针prior和next,分 别指向其前驱结点和后继结点，如图2.9所示
（1）双链表的插入
4、循环单链表
循环单链表和单链表的区别在于，表中最后一个结点的指针不是NULL，而改为指向头结点， 从而整个链表形成一个环，如图2.12所示。 在循环单链表中，表尾结点*r的 next 域指向L，故表中没有指针域为 NULL的结点，因此， 循环单链表的判空条件不是头结点的指针是否为空，而是它
是否等于头指针
5、循环双链表
由循环单链表的定义不难推出循环双链表。不同的是在循环双链表中，头结点的prior指 针还要指向表尾结点，如图2.13所示
在循环双链表L中，某结点*p为尾结点时，p->next==L;当循环双链表为空表时，其
头结点的 prior域和 next域都等于L
6、静态链表
静态链表借助数组来描述线性表的链式存储结构，结点也有数据域 data 和指针域 next，静态链表也要预先分配一块连续的内存空间
习题
参考答案：C
参考答案：A