数据结构(1)：线性表

1 线性表的顺序实现

创建的新项目是cpp类型哦！

1.1 初始化

1.1.1  静态分配

#define _CRT_SECURE_NO_WARNINGS#include <stdio.h>
#define MaxSize 10 //定义顺序表的长度
typedef struct {int data[MaxSize];//用静态的数组存放元素！int length;
}SqList;
//相当于python中的类，这个类有一个属性是 长度//基本操作--初始化一个顺序表
void InitList(SqList& L) {for (int i = 0; i < MaxSize; i++) {L.data[i] = 0;}//初始化每一个值为0L.length = 0;
}//主函数
int main() {SqList L;//创建一个顺序表InitList(L);//初始化一个顺序表！！！return 0;
}

脏数据！

1.1.2 动态分配

1.2 基本操作【基于静态分配】

1.2.1 插入

1.2.2 删除操作

1.2.3 查找

【1】按位查找

静态分配：

动态分配：

注意指针！！！

【2】按值查找

数据是结构类型的时候比较不能用==

c语言程序设计！

2 线性表的链式表示-单链表

2.1 单链表的定义

用代码实现，带头结点/不带头结点，一般使用带头结点

代码实现：

【1】长一点的写法

【2】

2.2 初始化

2.2.1 不带头结点

2.2.2 带头结点

头结点不存储数据，

不带头结点那么这个头指针指向的就是实际用于存放数据的结点

而带头结点 这个头指针指向的是头结点 这个结点不存放数据，这个头结点之后的下一个结点才会用于存放数据！！！

2.3 按位序插入

2.3.1 带头结点

当i=1时

2.3.2 不带头指针

要对第一个结点做单独的处理！

2.4 给定结点在结点之后插入

时间复杂度o(1)

2.5 给定结点之前插入【前插】

2.5.1 方法一：传入头指针

o（n）

利用头阶段找到给定节点的前区结点！

2.5.2 方法二：偷天换日

时间复杂度0(1)

2.6 按位序删除

平均：o（n）

2.7 删除给定结点

偷天换日

如果p是最后一个结点的话：【只能采用方法一来弄！】

2.8 查找

2.8.1 按位查找

平均时间复杂度：o(n) 顺序表的按位置查找

可以封装起来，在插入和删除里进行调用！！

2.8.2 按值查找

o(n)

2.9 表的长度

2.10 建立单链表

2.10.1 尾插法建立

这样的问题是每次都要遍历到找到最后一个元素，那么时间复杂度就是0+1+2+3+.....+(n-1)这样的话时间复杂度就是o(n^2)

太高了，引入尾指针！

9999就是一个特殊的出口

时间复杂度就是o(n)

2.10.2 头插法

写代码的时候 去掉的那句写上就是好习惯！！！

头插法最后得到的是逆序的链表！

3 顺序表的链式表示-双链表

3.1 初始化

3.2 插入--后插

更严谨一点：

修改指针的顺序一定要先后面再前面

3.3 删除

3.4 销毁

3.5 遍历

注意指针修改的顺序！！！

注意边界的情况！！！

4 循环单链表

4.1 初始化

在删除的时候找不到前驱结点

找到最后一个结点

L指针放在表尾的时候就会 自己指向的是尾结点，下一个是头结点，当应用场景是要频繁的使用头结点和尾结点的时候，就把指针放在最后！

5 循环双链表

插入：

删除：

循环双链表不用考虑最后一盒结点

6 静态链表

初始化：

用数组存放，书本上的写法后面：

基本操作：

初始化：

查找某个位序的节点时间复杂度o(n)

插入：

空闲标记成-2

尽管是一整片连续的区域，但是各个在逻辑上相邻的元素在物理上也可以不相邻!

先后关系是通过游标实现的！

文件分配表FAT就是静态链表！

7 链表和顺序表比较

奶茶店排队取号

查询操作比较多，课堂点名