企业官网建设流程全解析

栈 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.即使某结点仅有一个子树，也必须明确是左子树还是右子树。

访问节点顺序

前序遍历： 根 – 左 – 右
中序遍历： 左 – 根 – 右
后序遍历： 左 – 右 – 根
层序遍历：需要通过队列链表实现

通过排序反推树形结构

1. 前序 + 中序：能唯一确定二叉树。原因：前序提供根节点，中序利用根节点切分左右子树，逻辑唯一
2. 后序 + 中序：能唯一确定二叉树。原因：后序提供根节点，中序利用根节点切分左右子树，逻辑唯一
3. 前序 + 后序：不能唯一确定二叉树。原因：只能确定根节点，但无法划分哪些节点属于左子树，哪些属于右子树

创建二叉树

前序遍历代码
前序，中序，后序代码逻辑一样，写法相同，调整输出时间即可看到效果

三种排序输出的结果：

5. 哈希表

基本思想:记录"存储位置”与"关键字(要处理的数据相关的一个值)"之间的对应关系

• 组成：一个数组，数组每个位置挂载一条单链表
• 作用：利用哈希函数计算下标，用链表处理哈希冲突
• 特点：查找速度快；链表用来存放哈希值相同的元素
• 操作：插入、查找、删除、销毁

哈希冲突

不同关键字，经过同一个哈希函数计算后，得到相同哈希地址（下标），此时常见解决方法有：

1.通过开发地址法
2.链地址法

哈希链表创建（单向链表）
代码示例：

哈希链表打印函数

桶数组在栈，由函数结束自动回收桶数组，与在堆区空间开辟相比，内存小，且不能动态分配

哈希链表寻找值
注意：由于是数组所以需要传递数组的地址（二级指针）

哈希表修改指定的值

哈希表删除指定的值

哈希表销毁