线性表小回顾
1.线性表介绍
线性表简单来说就是0或多个数据元素的有限序列
在现实中有许多应用场景 如一个学校某月的考试成绩整合 对应了姓名、科目、分数、排名 或者一个公司的工资发放情况。
2.顺序存储结构
2.1定义
简单来说就是用一段连续空间来存储数据内容 可以理解成一维数组
2.2代码实现（C语言）
要想实现代码我们必须搞清楚顺序结构具备什么 第一就是数据元素 第二就是一个连续的空间 我们还要考虑这个空间的大小以及自动分配内存大小（stdlib.h） 和想要随时改变元素类型（使用typedef 实现） 首先写出以下代码
这里我们定义了基础结构 通过size与capacty比较来进行空间的增加
这样就完成了初步的定义 可以对这个顺序表进行进一步的增、删、改、查、插等 这里就不再过多赘述代码
这里要注意定义函数需要使用指针才能传参 每次增加元素 函数都需要判断空间预留情况
2.3顺序结构优缺点
优点：由其特性连续空间可知 其查找元素还是挺快的 且不用为元素之间的联系增加额外的存储空间
缺点：还是因为其特性 在数据过多情况下使得想要插入元素时会大量挪动数据位置 造成大量的时间浪费 且空间分配容易造成空余空间浪费 难以确定储存空间容量
3.链式存储结构
3.1定义
而链式存储结构的特点 正好可以解决顺序存储结构的缺点 因为其为每个数据以节点的形式相连接 空间内存可以连续也可以不连续 可以看成一列火车 每节车厢代表数据元素 而连接车厢之间的钩子可以看成连接点 当想要插入元素只需要考虑怎么拆连接点 而正是这个特性 使得链表的操作性极强
3.2代码实现
相当于顺序表 链表不需要考虑空间 但是增加了“连接点” next
且要注意当插入或者操作时要改变头节点时 注意使用双指针防止头指针遗失使得整个链表遗失
头指针是必须要存在的 头节点可以选择存在或不存在
初始化如上图
4.静态链表
4.1引言
其实C语言指针这个东西很好用 可以实现很多东西 也可以之间调用内存空间直接进行修改 但在早期高级语言并没有 而他们就想到用数组来解决链表问题 是对数组下标的引用 那么用数组来描述链表就叫做静态链表巧妙的利用游标cur来充当链表的next
静态链表是通过游标实现链表 但本身没有malloc函数 和free函数 还需自己创建
malloc函数实现
虽然实现了基础链表 但是还是没有解决连续存储带来表长的问题 失去链式存储随机存取的特性
5.循环链表
其实循环链表就是将链表的尾节点的next指向头节点 an->next=a1 循环链表解决了单链表只能从头到尾的问题 现在可以从任意位置出发
5.1两个循环链表合并
单说的话很不好理解 将两个链表运行到尾节点时 使A链表尾节点的next指向B链表的头节点 让B链表尾节点的next指向A头节点的next 这样保存了一个头节点 但是对这里的理解有点含糊 代码如下
p=Atail->next
Atail->next=Btail->next;
q=Btail->next;
Btail->next=p->next;
free(q)
6.双向链表
相当于给节点新增一个指向前节点地址的head 实现单向链表不能回头的问题