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双向链表
双向链表是在单链表的每个结点中，再设置一个指向其前驱结点的指针域。
网友评论