数据结构 二、线性表、栈、队列和数组

# 一、线性表
## （一）线性表的基本概念
### 线性表是具有**相同数据类型**的n个数据元素的**有限序列**
### 特点
- 数量有限
- 有先后顺序
- 都是数据元素且类型相同
- 抽象性
## （二）线性表的实现
### 顺序表
#### 数据结构
- ```
  #define MAXSIZE 100
  typedef struct{
    ElemType data[MAXSIZE];
    int length;
  }SqList;
#### 初始化
- ```
  L.data = new ElemType[MAXSIZE];
  L.length = 0;
#### 插入
- ```
  bool insert(SqList &L,int i,ElemType e){
    if(i<0 || i>L.length)
      return false;
    if(L.length == MAXSIZE)
      return false;
    for(int j = L.length;j>=i;j--){
      L.data[j] = L.data[j-1];
    }
    L.data[i-1] = e;
    L.length++;
    return true;
  }
  
  时间复杂度：
  最好情况：O(1)
  最坏情况：O(n)
  平均情况：O(n)
#### 删除
- ```
  bool delete(SqList &L,int i,ElemType &e){
    if(i<0 || i>L.length)
      return false;
    if(i>L.length)
      return false;
    e = L.data[i-1];
    for(int j = i ;j<L.length;j++){
      L.data[j-1] = L.data[j]
    }
    L.length--;
    return true;
  }

  时间复杂度：
  最好情况：O(1)
  最坏情况：O(n)
  平均情况：O(n)
#### 查找
- ```
  int find(SqList &L,ElemType e){
    for(int i = 0;i<L.length;i++){
      if(L.data[i] == e)
        return i+1;
    }
    return 0;
  }
  
  时间复杂度：
  最好情况：O(1)
  最坏情况：O(n)
  平均情况：O(n)
#### 特点
- 随机访问
- 存储密度高
- 不利于插入和删除
### 单链表
#### 数据结构
- ```
  typedef struct LNode{
    ElemType data;
    sturct LNode *next;
  }LNode,*LinkList;
#### 初始化
- ```
  // 前插法
  L = (LinkList)maloc(sizeof(LNode));
  L->next = null;
  LNode *s = (LNode *)malloc(size(LNode));
  s->data = x;
  s->next = L->next;
  L->next = s;

  // 后插法
    L = (LinkList)maloc(sizeof(LNode));
  L->next = null;
  LNode *s = (LNode *)malloc(size(LNode));
  s->data = x;
  L->next = s;
  L = s;
#### 插入
- ```
  // 将*s结点插入到*p节点之前的主要代码
  s->next = p->next;
  p->next = s;
#### 删除
- ```
  // 移动到待删除的节点前驱p
  q = p->next;
  p->next = q->next;
  free(q);
#### 查找
- ```
  // 将p指向第一个与x相等的节点
  while(p->next != null && p->next->data != x)
    p = p->next;
  if(p->next == null)
    return null;
  else
    return p->next;
## （三）线性表的应用
### 双链表
#### 数据结构
- ```
  typedef sturct DNode{
    ElemType data;
    struct DNode *pre,next;
  }DNode,*DLinkList;
#### 插入
- ```
  // 在p后面插入s结点
  s->next = p->next;
  s->pre = p;
  p->next->pre = s;
  p->next = s;
#### 删除
- ```
  // 删除q节点
  p->next = q->next;
  q->next->pre = p;
  free(q);
### 循环链表
- 判空条件不是头节点的指针是否为空，而是它是否等于头指针
### 顺序表和链表的比较
#### 存取方式
- 顺序表：顺序存取、随机存取
- 链表：只能从头顺序存取
#### 逻辑结构和物理结构
- 顺序表：逻辑相邻也物理相邻
- 链表：逻辑相邻不是物理相邻
#### 基本操作
#### 空间分配
### 如何选取
#### 存储角度
- 难以估计规模采用链表，但存储密度低
#### 运算角度
- 若经常运算是按序号访问，考虑顺序表
- 插入删除操作比较频繁，考虑链表
#### 环境角度
- 顺序表易实现
- 较稳定的线性表选择顺序存储
- 动态性强选择链式存储



# 二、栈、队列和数组
## （一）栈和队列的基本概念
## （二）栈和队列的顺序存储结构
### 栈
### 队列
#### 存储结构
- ```
  typedef struct{
    ElemType base[MAXSIZE];
    int front;
    int rear;
  }SqQueue;
#### 队空
- Q.front == Q.rear == 0
#### 进队
- 值送到队尾，尾指针加一
- Q.rear = （Q.rear+1)%MaxSize;
#### 出队
- 取对头，头指针加一
- Q.front = （Qfront+1)%MaxSize;
#### 队满
- Q.front == (Q.rear+1)%MaxSize
#### 长度
- (Q.rear-Q.front+MaxSize)%MaxSize
## （三）栈和队列的链式存储结构
### 栈
### 队列
#### 双端队列
- 输出受限：允许一端插入和删除，另一端只允许插入
- 输入受限：允许一端插入和删除，另一端只允许删除
## （四）多维数组的存储
### 一维数组
- LOC(a~I~) = LOC(a~0~) + i * L
### 二维数组
#### 设行下标最大时h~1~,列下标最大时h~2~，L是每个元素所占的存储单元
#### 行优先
- LOC(a~i~ ~j~) = LOC(a~0~ ~0~) + (i * (h~2~ + 1) + j) * L
#### 列优先
- LOC(a~i~ ~j~) = LOC(a~0~ ~0~) + (j * (h~1~ + 1) + i) * L
## （五）特殊矩阵的压缩存储
### 对称矩阵
- 只存放下三角部分
### 三角矩阵
- 与对称矩阵相似，但接着存储对角线上方的常量一次
### 三对角矩阵
- 当|i-j| > 1 时，a~i~ ~j~ = 0
### 稀疏矩阵
- 仅存储非零元素
- 失去了随机存取特性
- 三元组可采用数组存储或十字链表法存储
## （六）栈、队列和数组的应用
- 栈在括号匹配中的应用
- 栈在表达式求值中的应用
- 栈在递归中的应用
- 队列在层次遍历中的应用
- 队列在计算机系统中的应用