线性表

线性表的概念及运算

定义

线性表(Linear List)是由n (n≥0)个类型相同的数据元素a1,a2,…，an组成的有限序列。

特性

同一性、有穷性、有序性

抽象数据类型定义

顺序存储

定义

线性表的顺序存储是指用一组地址连续的存储单元依次存储线性表中的各个元素，使得线性表中在逻辑结构上相邻的数据元素存储在相邻的物理存储单元中，即通过数据元素物理存储的相邻关系来反映数据元素之间逻辑上的相邻关系。

采用顺序存储结构的线性表通常称为顺序表。

C语言定义如下：

操作

查找操作

1. 按序号查找GetData(L,i)：要求查找线性表L中第i个数据元素，其结果是L.elem[i-1]或L->elem[i-1]。
2. 按内容查找Locate（L,e）: 要求查找线性表L中与给定值e相等的数据元素，其结果是：若在表L中找到与e相等的元素，则返回该元素在表中的序号；若找不到，则返回一个“空序号”，如-1。

插入操作

线性表的插入运算是指在表的第i (1≤i≤n+1)个位置，插入一个新元素e，使长度为n的线性表 (e1，…，ei-1，ei，…，en) 变成长度为n+1的线性表（e1，…,ei-1，e，ei，…，en）。

删除操作

线性表的删除运算是指将表的第i(1≤i≤n)个元素删去，使长度为n的线性表 (e1，…,ei-1，ei，ei+1，…，en)，变成长度为n-1的线性表(e1，…,ei-1， ei+1，…，en)。

合并操作

已知 ：有两个顺序表LA和LB，其元素均为非递减有序排列，编写一个算法，将它们合并成一个顺序表LC，要求LC也是非递减有序排列。

算法思想 ：设表LC是一个空表，为使LC也是非递减有序排列，可设两个指针i、j分别指向表LA和LB中的元素，若LA.elem[i]>LB.elem[j]，则当前先将LB.elem[j]插入到表LC中，若LA.elem[i]≤LB.elem[j] ，当前先将LA.elem[i]插入到表LC中，如此进行下去，直到其中一个表被扫描完毕，然后再将未扫描完的表中剩余的所有元素放到表LC中。

链式存储

定义

采用链式存储结构的线性表称为链表 。

单链表

结点（Node）为了正确地表示结点间的逻辑关系，必须在存储线性表的每个数据元素值的同时，存储指示其后继结点的地址（或位置）信息，这两部分信息组成的存储映象叫做结点（Node）。

单链表：链表中的每个结点只有一个指针域，我们将这种链表称为单链表。

单链表包括两个域，数据域用来存储结点的值，指针域用来存储数据元素的直接后继的地址（或位置）。

头指针 ：指向链表头结点的指针。

1、头插法建表：从一个空表开始，重复读入数据，生成新结点，将读入数据存放到新结点的数据域中，然后将新结点插入到当前链表的表头结点之后，直至读入结束标志为止。

2、尾插法建表：

3、按序号查找

4、按值查找

5、插入节点

6、删除节点

7、求链表长度

8、两个有序单链表的合并

循环链表

将单链表最后一个结点的指针域由NULL改为指向头结点或线性表中的第一个结点，就得到了单链形式的循环链表，并称为循环单链表。在循环单链表中，表中所有结点被链在一个环上。

1、循环单链表合并为一个循环单链表

循环链表

在单链表的每个结点里再增加一个指向其前趋的指针域prior。这样形成的链表中就有两条方向不同的链，我们称之为双 ( 向) 链表 (Double Linked List)。

1、前插节点

2、删除节点

静态链表（？）

逻辑结构上相邻的数据元素，存储在指定的一块内存空间中，数据元素只允许在这块内存空间中随机存放，这样的存储结构生成的链表称为静态链表。也就是说静态链表是用数组来实现链式存储结构，目的是方便在不设指针类型的高级程序设计语言中使用链式结构。它的优点是和动态链表一样，删除和插入元素时间复杂度低；不足是和数组一样，需要提前分配一块较大的空间。

1、初始化

2、分配结点

3、回收结点

一元多项式

在链式存储中，对一元多项式只存非零项，则该多项式中每一非零项由两部分构成（指数项和系数项）。

1、建立一元多项式链式存储

通过键盘输入一组多项式的系数和指数，用尾插法建立一元多项式的链表。以输入系数0为结束标志，并约定建立多项式链表时，总是按指数从小到大的顺序排列。

2、一元多项式求和