第2章 线性表
2.1 复习笔记
一、线性表的类型定义
1线性表的定义
含有n个相同数据类型的数据元素的有限序列称为线性表。
一般可表示为：
L＝（a1，a2，…，ai－1，ai，ai＋1，…，an－1，an）；
【说明】ai－1是ai的直接前驱元素，ai＋1是ai的直接后继元素。线性表中数据元素的个数n（n＞0）为线性表的长度。当n＝0时称线性表为空表。
线性表是最常用且最简单的一种数据结构。
2线性表的基本操作
（1）INITIATE(L)：初始化操作。
（2）LENGTH(L)：求线性表长度。
（3）GET(L,i)：取元素函数。
（4）PRIOR(L,elm)：求前驱函数。
（5）NEXT(L,elm)：求后继函数。
（6）LOCATE(L,X)：定位函数。
（7）INSERT(L,i,b)：前插操作。
（8）DELETE(L,i)：删除操作。
（9）EMPTY(L)：判空表函数。
（10）CLEAR(L)：表置空操作。
二、线性表的顺序表示和实现
1顺序存储结构的表示
顺序存储结构（又称顺序表）是一种随机存取的结构，逻辑关系上相邻的元素物理位置上也相邻。数组是表示顺序存储结构最简单的一个方式。如图2-1所示，只要确定了存储线性表的起始位置，线性表中任一数据元素都可随机存取。
图2-1 线性表的顺序存储结构示意图
2顺序存储结构的特点
优点：
①它是一个记录型的结构。数据元素的存储位置可用数组的下标值（即相对于线性表的起始位置的值）来表示；
②在顺序存储结构中，线性表的某些操作容易实现，如求表长的操作；
缺点：
①在做插入或删除操作时，需移动大量元素；
②在给长度变化较大的线性表预先分配空间时，必须按最大空间分配，易造成了空间的浪费；
③表的容量难以扩充。
三、线性表的链式表示和实现
链式存储结构，由于它不要求逻辑上相邻的元素在物理位置上也相邻，因此它没有顺序存储结构所具有的缺点。
1定义
借助指针等手段来表示数据元素ai和直接后继元素ai＋1之间的关系，ai不仅存储本身的信息，还存储指向后继的指针。数据元素（数据域）和指向后继的指针（指针域）合起来称为一个结点，n个结点链接成一个链表即为线性表的链式存储结构。
2链式存储结构的特点
（1）不要求逻辑上相邻的元素在物理位置上也相邻；
（2）数据元素之间的逻辑关系是由结点中的指针指示的；
3链式存储结构的分类
链式存储结构种类繁多，按照实现方式的不同，可分为借助指针实现的链式存储结构和借助数组实现的链式存储结构。
（1）借助指针实现的链式存储结构
①单链表
在单链表中，对于每个结点来说，除了存储本身的信息外，还需要存放一个指向其后继的指针。逻辑位置相邻但物理位置不相邻的数据元素用单链表链接如图2-2所示。
图2-2 单链表的逻辑状态
②双链表
双链表的结点中除了数据域外，还有两个指针域，一个指向直接后继，另一个指向直接前驱。
在双向链表中，有些操作如：LENGTH(L)、GET(L,i)、LOCATE(L,x)等仅需涉及一个方向的指针，但插入、删除时，需同时修改两个方向上的指针，图2-3和图2-4分别显示了删除和插入结点时指针修改的情况。
图2-3 双向链表中删除结点时指针变化情况
图2-4 双向链表中插入结点时指针变化情况
③循环链表
循环链表是一种首尾相连的链表，它的最后一个结点的指针域指向头结点，形成一个环。循环链表包括单循环链表和双循环链表。其中单循环链表如图2-5所示。
双链表也可以有循环链表，带有图2-6（a）这种结点结构的双循环链表一般如图2-6（c）所示，链表中存有两个环。图2-6（b）所示为只有一个表头结点的空表。
图2-5 单循环链表
图2-6 双向链表示例
（2）借助数组实现的链式存储结构——静态链表
预先分配一个较大的空间，使用数组下标将逻辑上相邻的元素链接起来的特殊链表叫静态链表。
其中插入删除等操作具有和指针实现的链表一样的优点。例如，图2-7（b）展示了图2-7（a）所示线性表在插入数据元素“SHI”和删除数据元素“ZHENG”之后的状况。
图2-7 静态链表示例
【注意】
①采用指针实现的链式存储结构是非随机存取的存储结构；
②头结点和头指针的区别：
头结点是在链表的第一个结点之前附加一个结点（该结点可以不存储任何信息，也可以存储链表长度等信息），从而使得链表的第一个结点和其他结点在处理问题上的操作保持一致。
头指针是为了标识一个链表而产生的，当链表存在头结点时，则头指针指向头结点，当链表不存在头结点时，头指针指向链表的第一个元素（也可能为空）。
如图2-8（a）所示，此时，单链表的头指针指向头结点。若线性表为空表，则头结点的指针域为“空”，如图2-8（b）所示。
图2-8 带头结点的单链表
四、一元多项式的表示及相加