第三章 线性表
最后更新于：2022-04-01 23:02:03
### 一、线性表定义
线性表：零个或多个数据元素的**有限**序列。（零个的时候是空表）
线性表的特性是：除了第一个元素（只有后继）和最后一个元素（只有前驱），每个元素都只有一个前驱和后继。
### 二、线性表的抽象数据类型
线性表的抽象数据类型定义如下：
### 三、线性表的顺序存储结构
线性表的顺序存储结构，指的是用一段地址连续的存储单元依次存储线性表的数据元素。
来看线性表顺序存储结构代码：
发现描述顺序存储结构需要三个属性：
1.储存空间的起始位置：数组data，它的存储位置就是存储空间的存储位置。
2.线性表的最大存储容量：数组长度MaxSize。
3.线性表的当前长度：length。
下面再讨论一下地址的计算方法：
### 四、顺序存储结构的插入与删除
获得元素的操作：
插入操作：
删除操作：
线性表的顺序存储结构的优缺点：
优点：1.无需为表示表中元素之间的逻辑关系而增加额外的存储空间2.可以快速地存取表中任一位置的元素。
缺点：1.插入和删除操作需要移动大量元素2.当线性表长度变化较大时，难以确定存储空间的容量3.造成存储空间的碎片。
### 五、线性表的链式存储结构
n个节点链结成一个链表，即为线性表的链式存储结构，因为此链表的每一个节点中只包含一个指针域，所以叫做单链表。
把链表中第一个节点的存储位置叫做头指针，最后一个节点指针为空。
一般为了方便对链表进行操作，会在单链表的第一个结点前附设一个结点，成为头结点。头结点的**数据域可以不保存任何信息**。
头指针和头结点的异同：
**头指针**是指向头结点的指针；头指针具有标识作用，所以常用头指针冠以链表的名字；无论链表是否为空，头指针均不为空。头指针是链表的必要元素。
**头结点**是为了操作的统一和方便而设立的，放在第一个元素的结点之前，其数据域一般无意义（也可以存放链表的长度）；有了头结点，对在第一个元素结点前插入结点和删除第一结点，其操作与其他结点的操作就统一了；头结点不一定是链表的必须元素。
结点的概念：结点由存放数据元素的**数据域**存放后继结点的**指针域**组成。
假设P是指向线性表的第i个元素的指针，则该节点aI的数据域我们可以用p->data来表示，p->data的值是一个数据元素，结点aI的指针域可以用p->next来表示，p->next的值是一个指针。如果p->data=ai,那么p->next->data=aI+1。即：
### 六、单链表的读取
由上面程序看出来，获取链表获取第i个元素比较麻烦。
### 七、单链表的插入与删除
插入结点：
删除结点：
由算法可以看出，插入和删除对于链表来说每次只需要简单地通过赋值移动指针而已，时间复杂度都是O(1),显然，对于插入和删除数据越频繁的操作，单链表的效率优势就越是明显。
### 八、单链表的整表创建
头插法：
尾插法：
### 九、单链表的整表删除
十、单链表结构与顺序存储结构优缺点
### 十一、循环链表
将单链表的终端结点的指针端由空指针改为指向头结点，就使整个单链表形成了一个环，这种头尾相连的单链表称为单循环链表，简称循环链表。
下面研究一下循环链表的合并：
分成4步：
1.p=rearA->next;
2.rearA->next=rearB->next->next;
3.rearB->next=p;
4.free(p).
### 十二、双向链表
双向链表概念：双向链表是在单链表的每个结点中，再设置一个指向其前驱结点的指针域。
双向链表插入操作：
同样也分成4步：
1.s->prior=p;
2.s->next=p->next;
3.p->next->prior=s;
4.p->next=s.
双向链表的删除操作：
分成3步：
1.p->prior->next=p->next;
2.p->next->prior=p->prior;
3.free(p).
### 十三、总结
';