线性表
1. 顺序存储结构 [ 数组 ]
定义： 用一段地址连续的存储单元一次存储线性表的数据元素
-
描述顺序存储结构需要三个属性：
- 存储空间的起始位置
- 线性表的最大存储容量（数组长度）MaxSize
- 线性表的当前长度 length
-
由于线性表顺序存储，任意位置均是相等时间，所以存入或取出数据的时间性能为O(1)
因此叫做 随机存取结构
-
插入与删除：
- 插入时，之后的每个元素要后退
- 删除时，之后的每个元素要前进
- 插入与删除 时间复杂度都是O(n)
-
优点：
- 快速存取任意位置元素
- 无需为元素之间的逻辑关系增加额外存储空间
-
缺点：
- 插入和删除需要移动大量元素
- 长度变化较大时，难以确定存储空间的容量
2. 链式存储结构（联想 有向图）
2.1 单链表
-
特点：
数据元素存储在任意位置 可以不连续
每个元素除了存储数据以外 还要存储后继元素的存储地址
单线索 无分支
单链表 = n个结点的链结 = 头指针 + n*( 数据域＋指针域 )
<img src="upload%5Cimage-20200311203215475.png" alt="单链表" style="zoom:80%;" />
- 设p是指向线性表第 i 个元素的指针
- p -> date 表示 ai 的数据域
- p -> next 表示 ai 的指针域 （指向第 i+1 个元素）
单链表的读取
获得链表第 i 个数据：
声明一个指针p 指向链表第一个节点 初始化 j 为1
当 j < i 时，遍历链表，p后移不断指向下一节点，j累加1
- 若到末尾p为空指针，则第i个元素不存在
- 否则查找成功，返回节点p指向的数据
时间复杂度为 O(n)
关键语句
while (p && j<i) { …… }
单链表的插入与删除
-
将 e 插入到 ai 和 ai+1 之间， 设p指向ai ，p->next 指向 ai+1，s指向e
s->next = p->next; p->next = s;- 该顺序不可颠倒
-
插入算法：
- 声明一个节点p 指向链表第一个元素 初始化 j 为1
- 当 j < i 时，遍历链表，p不断后移指向下一节点，j++
- 若到链表末尾p为空说明第i个元素不存在
- 否则查找成功，此时生成一个节点s
- 将 e 的数据赋给 s->data
- 单链表插入标准语句
s->next = p->next; p->next = s - 返回插入成功
-
将 ai 删除 设ai节点为q，ai-1 的节点为p
p->next = p->next->next;
-
算法：
- 声明节点p， 指向链表第一个元素， 初始化j = 1
- 当 j < i 时，遍历链表，p不断指向下一节点，j++
- 若到链表末尾p为空说明第i个元素不存在
- 否则查找成功，将即将删除的节点
p->next = p->next->next - 返回成功
- 插入与删除 比较与总结：
- 相比于顺序表，对于一个数据时间复杂度都为O(n)
- 但是，一次性插入或删除数据越多，单链表优势更明显：
- 顺序表， 每次都是O(n)
- 单链表，第一次O(n)，之后都是O(1)
单链表整表创建与删除
创建单链表 实质 动态生成链表：从“空表”初始状态开始，依次建立各元素的结点，并逐个插入列表
-
头插法算法:
初始化空链表L，让L头节点的指针指向NULL，即建立一个带头节点的单链表
声明一节点p和计数器变量
-
循环：
生成一个新节点，令p指向它（地址赋值给p）
将数据赋值给p->data
-
将p插入到头节点与前一个新节点之间
即
p->next = (*L)->next; (*L)->next = p;
-
尾插法算法：
初始化空链表L，让L头节点的指针指向NULL，即建立一个带头节点的单链表
声明一节点p, r和计数器变量，r初始化为头节点
-
循环：
生成一个新节点，令p指向它（地址赋值给p）
将数据赋值给p->data
-
将p插入到尾端：**// 注意 r 的重要性 永远属于尾端 **
`r->next = p; r=p;
r->next = NULL// 表示当前链表结束
2.2 静态链表
问题提出： 如果没有指针该咋办
-
解决： 用数组来代替指针 从而描述单链表
- 对于不提供Struct的语言，可以使用一对并行数组data和cur来处理
-
数组的元素 = data + cur
- data 存放数据元素
- cur 相当于next指针 存放该元素的后继在数组中的下标
#define MAXSIZE 1000
typedef struct{
ElemType data;
int cur; //游标 Cursor
}Component, StaticLinkList[MAXSIZE];
-
数组第一个元素和最后一个元素为特殊元素，不存data
// 备用链表：未被使用的后续的数组元素
[0].cur 存放备用链表的第一个节点的下标
[END].cur 存放第一个有数值的元素的下标，相当于头节点静态链表初始化
- 插入与删除 等到 java描述 再详细讨论
2.3 循环链表
-
将单链表中尾端节点的指针端 由空指针改为指向头节点，
使得整个单链表形成一个环
这种头尾相连的单链表就被称为 单循环链表，简称循环链表（circular linked list）
2.4 双向链表
- 在单链表每个节点中 除了设置next指针 还设置一个指向前驱的prior指针
