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 链表和顺序表比较
奶茶店排队取号
查询操作比较多,课堂点名