存储结构
顺序存储结构（顺序表）
- 概念：
在逻辑上相邻的元素在物理上也相邻 - 特点：1. 随机访问 2. 占用连续的存储空间 3.存储密度高 4. 插入删除不方便
操作：
1. 插入 ：从目标位置开始，将元素向后移动一个位置，空出一个位置 2. 删除：从目标位置开始，将后面的向前移动一个位置 3. 查找：顺序遍历查找
链式存储结构（链表）
链表的特点
不支持随机访问
节点存储空间的利用率相较于顺序表较低
支持存储空间的动态分配单链表
- 判断是否为空：
- 插入操作：
- 删除一个节点：
- 判断是否为空：
p为待删除的节点的前一个节点
q=p->next;
p->next=p->next->next;
free(q);
- 双链表
在单链表的基础上添加一个指针域，指向当前节点的前驱，和循环链表可不一样，循环链表可以理解为一个圈。
循环链表
- 循环单链表
- 循环双链表、
- 循环单链表
- 静态链表
静态链表是一个结构体数组：
数组中每一个节点：data是数据，还有一个指针分量，指向下一个节点
栈
==后进先出，先进后出，一端操作==
栈的存储结构
栈的顺序存储结构（顺序栈）
栈空：st.top==-1
栈满：st.top==maxSize-1
定义一个栈，并初始化：
int stack[maxSize]; int top =-1;
元素x进栈：
stack[++top]=x;
元素x出栈
x=stack[top--];栈的链式存储结构（链式栈）
栈空：lst->next=NULL;
链栈的初始化代码：
lst=（LNode*）malloc（sizeof(LNode)）;
lst->next=NULL;
进栈：(头插法)
p->next=lst->next;lst->next=p;
出栈：
p=lst->next；x=p->data;lst->next=p->next;free(p);- 数学性质
当n个元素以某种顺序进栈，并且可在任意时刻出栈，所得元素排列数目N：
栈的应用
括号匹配问题
思路：
扫描这个表达式，遇到左括号入栈，遇到右括号判断栈顶元素是否为左括号，如果是左括号，则弹出左括号。一直扫描，如果最终栈空，则说明表达式的括号是匹配的，如果栈无法清空，则表示括号是不匹配的
后缀表达式
中缀表达式转后缀表达式：
手算：1. 首先给中缀表达式的所有运算单位加上括号 2. 把运算符号移动到对应的括号后，去掉括号 机算：
优先级：* / 优先级相同- 后缀表达式的计算：
队列
先进先出，后进后出，可进行插入的一端叫队尾，可进行删除的一端叫队头(出队在队首，入队在队尾)==
队列的存储结构
队列的顺序存储
实现思想：
用取模运算将存储空间在逻辑上变为环状
用静态数组存放队列元素
front指针指向队首元素的位置
rear指针指向队尾元素的 下一个位置
操作
初始化
rear==front
入队
rear=(rear+1)%maxsize
出队
front=(front+1)%maxsize
队长
(rear+maxsize-front)%maxsize
判断队列空or满
法一：
牺牲一个存储单元
满：(rear+1)%maxsize==front
空：rear==front
法二：
增加成员size
满：size==maxsize
空：size==0
法三：
增加成员tag
tag=0表示因为删除导致的rear==front
tag=1表示因为加入导致的rear==front
空：(rea==front)&&tag=0
满：（rear==front）&&tag=1
队列的链式存储
实现思想：
front指向头结点
rear指向队尾结点
操作
初始化
rear==front;front->next=null
判空
rear==front
判满：不会满
入队
加入队尾，rear->next=s；rear=s；
出队：删除链表头
注意要判断删除前是否只有一个元素
如果只有一个元素，删除之后rear==front
如果还有其他元素，直接free();
队列的应用
- 树的层次遍历
- 图的广度优先搜索
- 缓冲区
- FIFO页面替换算法
