一、线性表的定义及其基本操作

线性表的定义

线性表是由n(n>=0)个属于同一个数据对象的数据元素a1,a2,...,an-1,an组成的有限序列。n为线性表的长度。长度为0的表称为空表。
一个线性表可以用一个标志符来命名。则有A = (a1,a2,...,an-1,an)
同一个线性表中的数据元素必定具有相同特性，即它们都属于同一个数据对象。

线性表的操作

对线性表的基本操作有如下几种：

1. 置线性表为空表。该操作生成一个空的线性表。
2. 测试一个线性表是否为空表。该操作的结果是，若线性表为空表则返回真，否则返回假。
3. 求线性表的长度。操作结果为一个非负的整数，即求得线性表中数据元素的个数。
4. 检索线性表中第i个数据元素。操作结果为一个数据元素ai或者ai的存储位置（1<=i<=n，n为线性表长度）
5. 根据数据元素的某个数据项（通常称之为关键字）的值求该数据元素在线性表中的位置，也称为数据元素定位。操作的结果为一个非负整数。
6. 在线性表的第i个位置插入一个新的数据元素，并使线性表的长度加1。显然，这种操作只有当1<=i<=n+1时才有意义。
7. 在线性表的第i个位置存入一个新的值。请注意区别于第6种操作，前者每进行一次操作会使表的长度加1，而本操作不会改变线性表的长度。
8. 删除线性表中的第i个数据元素，并使线性表的长度减1。该操作只有当1<=i<=n+1时才有意义。另外，对空的线性表不能进行删除操作。
9. 删除线性表中重复出现的数据元素。
10. 对线性表的数据元素按照某一个数据项值的大小做升序或者降序排序。
11. 复制一个线性表，即产生一个与已有线性表相同的新的线性表。
12. 按照一定的原则，将两个或者两个以上的线性表合并为一个线性表。
13. 按照一定的原则，将一个线性表分解为两个或者多个线性表。

上面仅仅是一些主要的基本操作，有这些基本操作还可以构成其他较为复杂的操作。
上述每一种操作具体是如何进行的由操作所对应的算法来体现，也就是说，根据线性表的操作和采用的存储结构可以写出相应的算法。存储结构选择的不同，写出的算法也会不同。

二、线性表的顺序存储结构

顺序存储结构的构造

在计算机中可以采用不同的方式来存储一个线性表，其中最简单的方式就是用一组地址连续的存储单元来依次存储线性表中的数据元素。这种存储结构称为线性表的顺序存储结构，并称此时的线性表为顺序表。
假设线性表的每个数据元素占用k个存储单元，那么LOC(ai+1) = LOC(ai) + k。符号LOC(ai)通常被称为寻址函数，他表示数据元素ai的存储位置，即数据元素ai占用的k个连续存储单元的第1个单元的地址。LOC(ai)=LOC(a1)+(i-1)k。由此可见，只要确定了首地址，线性表中的任意一个数据元素都可以随机存取。因此，又称线性表的顺序存储结构为一种随机存取的存储结构*。

特点

最大的特点是 逻辑上相邻的两个数据元素在物理位置上也相邻，也正是这一特点使得线性表在顺序存储结构下具有明显的优点和缺点。

优点

1. 构造原理简单，较直观，易理解。
2. 若已知每个数据元素所占用的存储单元个数，并且知道第1个数据元素的位置，则表中的任意一个数据元素的位置可以通过一个简单的解析式计算出来。
3. 可以随机存取表中任意一个数据元素，存取速度快，并且存取任意一个数据元素的时间代价都相同。
4. 只需存放数据元素本身的信息，而无其他额外空间开销，相对于链式存储结构，存储空间开销小。

缺点

1. 需要一片地址连续的存储单元作为线性表的存储空间
2. 存储空间的分配需要事先进行，因而使得应该分配的存储空间大小不易估计。尤其在线性表的长度变化较大时，必须按照可能的最大空间的需求量分配，估计过大，容易导致分配的存储空间不能得到充分使用；估计过小，空间容量的扩充通常比较困难。
3. 进行插入或者删除操作时，需要先对插入或删除位置后面的所有数据元素逐个进行移动，操作的时间效率低，尤其当表较长，且插入或删除点的位置靠前时，更是如此。

因此，顺序存储结构比较适合于线性表的长度不经常发生变化，或者只需要在顺序存取设备上做批处理的场合。

几种常见操作的实现

1. 插入。在长度为n的线性表A的第i个位置插入一个新数据元素item
2. 删除。删除长度为n的线性表A的第i个数据元素
3. 查找。确定元素item在长度为n的线性表A中的位置
4. 删除。删除表中重复出现的元素
5. 排序。对线性表中元素进行排序
   线性表的排序操作是指按照线性表中数据元素的值或者某个数据项值的大小排列数据元素，使之成为一个有序表。这里我们采用选择排序进行介绍。

例题：

1. 删除表中数据信息为item的元素
2. 插入item到一个按值有序排列的顺序表中

三、线性链表及其操作

线性链表的构造

线性表的链式存储结构 是用一组地址任意的存储单位（可以是连续的，也可以是不连续的）来依次存储线性表中的各个数据元素。
链结点包括data和link两部分。一是用于存储一个数据元素本身信息的域称为数据域，用符号data作为该域的域名；一是存储一个数据元素逻辑关系上的直接后继元素的存储位置的域称为指针域，用符号link作为该域的域名。由于线性表的最后一个数据元素没有后继元素，故相应链结点的指针域存放”空“（NULL），作图时用符号^来表示。
于是，具有n个数据元素的线性表对应的n个链结点通过链接方式链接成一个链表，即为线性表的链式存储结构。由于链表中的每一个链结点中除了数据域以外仅设置了一个指针域，故称这样的链表为线性链表或单链表。
我们用list作为链表的入口地址，也叫头结点指针，整个链表的存取必须从该地址开始。要想取得线性表中的某个数据元素，就必须从链表的第1个链结点出发进行查找。可见线性链表是一种非随机存取的存储结构。
需要说明的是，链表中的各个链结点占用的存储空间之间不要求连续，但是每一个链结点内部占用的一系列存储单元则必须连续，所谓一个链结点的地址是指该链结点占用的一片连续的存储单元的第1个单元的地址。
用线性链表存储线性表时，数据元数之间的逻辑关系是通过指针反映出来的，指针是数据元素之间逻辑关系的映像，逻辑上相邻的两个数据元素其物理位置不要求相邻，因此，称这种存储结构为非顺序映像或链式映像。其实，在大多数实际应用中，人们关心较多的是线性表中数据元素之间的逻辑关系，而不是每一个数据元素在存储器中的实际位置。

若指针变量p为指向线性链表中某个结点的指针（即指针变量p的内容为链表中某个链结点的存储地址），则

1. p->data出现在表达式中，它表示由p所指的链结点的数据域信息（内容）；否则，表示由p所指的那个链结点的数据域（位置）。
2. p->link出现在表达式中，它表示由p所指的链结点的指针域信息（指针域的内容），也就是p所指的链结点的下一个链结点的存储地址；否则，表示由p所指的那个链结点的指针域（位置）。

把某个地址（不妨假设该地址保存在指针位置q中）送到由p所指链结点的指针域中，可以通过下面语句赋值：p->link = q。
当p指向链表中的某个链结点时，要想使p改变为指向下一个链结点，只需执行一次赋值语句：p = p->link。不难设想，如果最初让p指向链表的第1个链结点，然后反复执行这条赋值语句，直到p的内容为NULL，此时变量p已经遍历了整个链表。

特点

在线性表的链式存储结构中，逻辑上相邻的两个数据元素对应的存储位置是通过指针来反映的，不要求物理位置上也相邻。

优点

1. 合理利用存储空间。不需要预先设置好空间。
2. 在表中插入或者删除元素时不需要移动表中其他元素，操作效率高

缺点

1. 存储空间开销大
2. 非随机存取

说明

当有新的数据元素插入到链表中时，需要临时从一个被称为存储库的机构中取得一个空的结点空间，填入必要的信息，然后将它插入到线性链表中。而这个存储空间并非为某一个链表所专用，当任何链表操作需要新的链结点时都可以从中获取链结点空间（只要还有可用的存储空间）；一旦某个链结点不再使用时，可以将其送还到该存储库，通常称这种操作为存储释放或者回收（不释放不再使用的链结点空间，虽然不是很大的错误，但用完及时释放是一个好习惯）。free(p)。

线性链表的基本算法

下面是几个有关线性链表常用的算法。

1. 创建 建立一个线性链表
2. 长度 求线性链表的长度
3. 是否空 测试线性链表是否为空
4. 查找 确定元素item在线性链表中的位置
5. 插入 在非空线性链表的第1个链结点前插入一个数据信息为item的链结点
6. 插入 在非空线性链表的末尾插入一个数据信息为item的链结点
7. 插入 在线性链表中有指针q指出的链结点后面插入一个数据信息为item的链结点
8. 插入 在线性链表中第i个链结点后面插入一个数据信息为item的链结点
9. 插入 在按值有序链接的线性链表中插入一个数据元素为item的链结点
10. 删除 在非空线性链表中删除q所指的链结点
11. 销毁 销毁一个线性链表
12. 删除 删除线性链表中数据域值为item的所有链结点
13. 逆转 逆转一个线性链表
14. 连接 将两个非空线性链表连接成一个线性链表
15. 合并 将两个按值有序链表的非空线性链表合并成一个按值有序链接的线性链表
16. 复制 复制一个线性链表
17. 排序 利用线性链表进行数据排序
18. 查找 确定第m个链结点在线性链表中的位置
19. 移动 移动链表中数据域值最大的那个链结点移至链表的末尾

四、循环链表及其操作

所谓循环链表是指链表中最后那个链结点的指针域不再存放NULL，而是指向链表的第1个链结点，整个链表形成一个环。可以有 空的单向循环链表 和 非空的单向循环链表。
有时为了解决问题方便或需要，可以在链表的第1个链结点的前面设置一个特殊结点，称之为头结点。头结点的构造与链表中其他链结点的构造相同，但数据域可以不存放信息，也可以存放一些诸如线性表长度的信息；指针域存放线性表第1个数据元素对应的链结点的位置。如果线性表为空，相应的循环链表此时并不为空链表，它还要一个头结点，其指针域指向头结点自己。
循环链表的操作与前面讨论过的线性链表的操作基本相同，只是算法中循环条件不是判断p后者p->link是否为null,而是判断他们是否为链表最前面那个链结点的指针。
如何建立一个循环链表
例题1：在循环链表中查找数据信息为item的链结点
例题2：约瑟夫问题

五、双向链表及其操作

双向链表是指链表的每一个链结点中除了数据域以为设置两个指针域，一个指向结点的直接前驱结点，另一个指向结点的直接后继结点。其中，llink域指向直接前驱结点（称为左指针域）；rlink域指向直接后继结点（称为右指针域）
双向链表有一个特性，即若p为指向链表中某结点的指针，则在表达式中，有
p->llink->rlink = p->rlink->llink = p

建立一个双向链表

双向链表的插入与删除算法

1. 在带有头结点的双向循环列表中第1个数据域内容为x的结点右边插入一个数据信息为item的新结点
2. 从带有头结点的双向循环链表中删除第1个数据域内容为x的链结点