栈 Stack
- 逻辑特性：后进先出（LIFO）
- 分类：顺序栈（数组实现）、链栈（单链表实现）
- 操作：入栈、出栈、取栈顶元素、判空
- 特点：插入和删除只在同一端（栈顶）进行
操作：
- push 入栈：头插，新节点变成新 top
- pop 出栈：删头，top 往后移动
- 后进先出 LIFO
- 只保存一个 top（栈顶指针）
2. 队列 Queue
- 逻辑特性：先进先出（FIFO）
- 分类：顺序队列、循环队列、链队列
- 操作：入队、出队、取队头、判空
- 特点：一端入队（队尾），另一端出队（队头）
操作：
- enQueue 入队：尾插，用 rear 直接挂新节点
- deQueue 出队：删头；删空队列时，rear 要置 NULL
- 先进先出 FIFO
3. 双向链表（双链表）
- 类型：线性结构
- 节点特点：每个节点保存数据 + 前驱地址 + 后继地址
- 特点：可以正向、反向遍历；删除节点不需要额外遍历寻找前驱
双向链表头节点创建：
代码示例
双向链表头插
与单向链表思路相近，但是需要同时维护next（前）和prev（后）两条指针。往前、往后两个方向箭头都要修改
双向链表的整体操作都与单向链表的逻辑相近，只有增删节点时，需要修改相邻节点的next与prev两个方向指针
4. 二叉链表
- 类型：非线性（树形结构），二叉树的链式存储
- 节点特点：每个节点保存数据 + 左孩子指针 + 右孩子指针
- 遍历方式：前序、中序、后序、层序遍历
1.定义—递归式的定义
树是n(n≥0)个结点的有限集合:
- 当n=0时，称为空树;
- 当n>0时，满足:
有且仅有一个根结点(Root);** - 其余结点可分为m(m ≥0)个互不相交的有限集合T,T2…Tm
每个集合本身也是一棵树，称为根的子树
2.结点的特点
1.每个结点最多有两个子树;
2.左、右子树有顺序，不可互换;
3.即使某结点仅有一个子树，也必须明确是左子树还是右子树。
访问节点顺序
前序遍历： 根 – 左 – 右
中序遍历： 左 – 根 – 右
后序遍历： 左 – 右 – 根
层序遍历：需要通过队列链表实现
通过排序反推树形结构
- 前序 + 中序：能唯一确定二叉树。原因：前序提供根节点，中序利用根节点切分左右子树，逻辑唯一
- 后序 + 中序：能唯一确定二叉树。原因：后序提供根节点，中序利用根节点切分左右子树，逻辑唯一
- 前序 + 后序：不能唯一确定二叉树。原因：只能确定根节点，但无法划分哪些节点属于左子树，哪些属于右子树
创建二叉树
前序遍历代码
前序，中序，后序代码逻辑一样，写法相同，调整输出时间即可看到效果
三种排序输出的结果：
5. 哈希表
基本思想:记录"存储位置”与"关键字(要处理的数据相关的一个值)"之间的对应关系
- 组成：一个数组，数组每个位置挂载一条单链表
- 作用：利用哈希函数计算下标，用链表处理哈希冲突
- 特点：查找速度快；链表用来存放哈希值相同的元素
- 操作：插入、查找、删除、销毁
哈希冲突
不同关键字，经过同一个哈希函数计算后，得到相同哈希地址（下标），此时常见解决方法有：
1.通过开发地址法
2.链地址法
哈希链表创建（单向链表）
代码示例：
哈希链表打印函数
桶数组在栈，由函数结束自动回收桶数组，与在堆区空间开辟相比，内存小，且不能动态分配
哈希链表寻找值
注意：由于是数组所以需要传递数组的地址（二级指针）
哈希表修改指定的值
哈希表删除指定的值
哈希表销毁
