【数据结构】线性表学习

存储结构

顺序存储结构（顺序表）

概念：
在逻辑上相邻的元素在物理上也相邻
特点：1. 随机访问 2. 占用连续的存储空间 3.存储密度高 4. 插入删除不方便

操作：

1. 插入 ：从目标位置开始，将元素向后移动一个位置，空出一个位置
2. 删除：从目标位置开始，将后面的向前移动一个位置
3. 查找：顺序遍历查找

链式存储结构（链表）

链表的特点

不支持随机访问
节点存储空间的利用率相较于顺序表较低
支持存储空间的动态分配
单链表
1. 判断是否为空：
2. 插入操作：
3. 删除一个节点：

    ```c
    p为待删除的节点的前一个节点
    q=p->next;
    p->next=p->next->next;
    free(q);
    ```

双链表

在单链表的基础上添加一个指针域，指向当前节点的前驱，和循环链表可不一样，循环链表可以理解为一个圈。
循环链表
1. 循环单链表
2. 循环双链表、
静态链表
静态链表是一个结构体数组：
数组中每一个节点：data是数据，还有一个指针分量，指向下一个节点

栈

后进先出，先进后出，一端操作

栈的存储结构

栈的顺序存储结构（顺序栈）

```c
栈空：st.top==-1
栈满：st.top==maxSize-1

定义一个栈，并初始化：
int stack[maxSize]; int top =-1;

元素x进栈：
stack[++top]=x;

元素x出栈
x=stack[top--];
```

栈的链式存储结构（链式栈）

```c
栈空：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. 把运算符号移动到对应的括号后，去掉括号
  
  机算：
优先级：* / 优先级相同
1. 后缀表达式的计算：

在这里插入图片描述

队列

先进先出，后进后出，可进行插入的一端叫队尾，可进行删除的一端叫队头(出队在队首，入队在队尾)

队列的存储结构

队列的顺序存储

实现思想：

用取模运算将存储空间在逻辑上变为环状
用静态数组存放队列元素
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();