算法基础——线性表

1、定义

零个或多个数据元素的有限序列

2、线性表的抽象数据类型

个人理解：把能合并的提取出来做成一个通用的

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

1. 顺序存储方式

三个属性：

• 存储空间的起始位置
• 线性表最大存储容量
• 线性表当前的长度

2.数据长度与线性表长度区别

数据长度：存放线性表存储空间的长度
线性表长度 ：线性表中数据元素的个数

4、顺序存储结构的插入与删除

1.插入操作

插入算法思路

• 如果插入位置不合理，抛出异常
• 如果线性表大于等于数组长度，则抛出异常或者动态增容
• 从最后一个元素开始向前遍历到第i个位置，分别将他们都向后移一个位置
• 将插入元素填入位置i处
• 表长+1

插入操作

2.删除操作

• 如果删除位置不合理，抛出异常
• 取出删除元素
• 从删除元素位置开始遍历到最后一个元素的位置，分别将他们都向前移动一个位置
• 表长-1

删除操作

5、线性表顺序存储结构的优缺点

优点：
（1）无需为表中的元素之间的逻辑关系而增加额外的存储空间
（2）可以快速的取表中任意一个元素
缺点：
（1）插入和删除操作需要移动大量元素
（2）当线性表长度变化比较大时，难以确定存储空间的容量
（3）造成存储空间的“碎片”

6、单链表

6.1 读取

获得第 i 个数据思路：
1.声明一个结点 p 指向链表第一个结点，初始化 j 从1开始；
2.当 j<i 时，就遍历链表，让p的指针向后移动，不断指向下一结点，j 累加1；
3.若到链表末尾 p 为空，则说明第 i 个元素不存在；
4.否则查找成功，返回结点 p 的数据。

6.2 插入

单链表第 i 个数据插入结点的算法思路：
1.声明一结点 p 指向链表第一个结点，初始化 j 从1开始；
2.当 j < i 时，就遍历链表，让p的指针向后移动，不断指向下一结点，j 累加1；
3.若到链表末尾 p 为空，则说明第 i 个元素不存在；
4.否则查找成功，在系统中生成一个空结点 s；
5.讲数据元素 e 赋值给 s->data；
6.单链表的插入标准语句 s->next=p->next; p->next=s;
7.返回成功。

6.3 删除

单链表第 i 个数据删除结点的算法思路：
1.声明一结点 p 指向链表第一个结点，初始化 j 从1开始；
2.当 j < i 时，就遍历链表，让 p 的指针向后移动，不断指向下一个结点，j 累加1；
3.若到链表末尾 p 为空，则说明第 i 个元素不存在；
4.否则查找成功，将欲删除的结点 p->next 赋值给 q；
5.单链表的删除标准语句 p->next=q->next；
6.将 q 结点中的数据赋值给 e，作为返回；
7.释放 q 结点；
8.返回成功。

6.4单链表整表创建

单链表整表创建的算法思路：
1.声明一结点 p 和计数器变量 i；
2.初始化一空链表L；
3.让L的头结点的指针指向NULL，即建立一个带头结点的单链表；
4.循环：

• 生成一新结点赋值给 p；
• 随机生成一数字赋值给 p 的数据域 p->data；
• 将 p 插入到头结点与前一新结点之间。

6.5单链表整表删除

单链表整表删除思路：
1.声明一结点 p 和 q；
2.将第一个结点赋值给 p；
3.循环：

• 将下一结点赋值给 q；
• 释放 p；
• 将 q赋值给 p。

6.6单链表结构与顺序存储结构优缺点

6.7静态链表

用数组描述的链表叫静态链表

• 静态链表的优缺点

  
  

6.8循环链表

将单链表中终端结点的指针端由空指针改为指向头结点，就使整个单链表形成一个环，这种头尾相接的单链表称为单循环链表，简称循环链表。

6.9双向链表

双向链表是在单链表的每个结点中，再设置一个指向其前驱结点的指针域。