数据结构-其他线性结构（栈和队列）

大纲：

1. *掌握栈的定义、栈的存贮结构及基本操作的实现。
2. 理解用栈实现表达式的求值，递归过程及实现。
3. 掌握队列的定义、存贮结构及基本操作的实现。
4. 理解串的逻辑定义及其基本操作；理解串的存贮结构。
5. 理解数组的定义、数组的顺序存贮结构及矩阵的存贮压缩。
6. 理解广义表的定义及存贮结构。

---

栈

栈的基本概念

1. 栈的定义

   只允许在一端进行插入或删除操作的线性表

   • 栈顶：栈允许进行插入和删除的那一端
   • 栈底：固定的，不允许进行插入和删除的另一端
   • 栈是一个后进先出的线性表

2. 栈的基本操作

• InitStack(&S)：栈的初始化
• StackEmpty(S)：判断栈是否为空
• Push(&S,x)：进栈
• Pop(&S,&x)：出栈
• GetTop(S,&x)：读栈顶元素
• ClearStack(&S)：销毁栈

---

顺序栈

栈的顺序存储

#define MaxSize 50  //定义栈中元素的最大个数
typedef struct{
  Elemtype data[MaxSize];  //存放栈中元素
  int top;  //栈顶指针
}SqStack;

• 栈空条件：S.top=-1；栈满条件：S.top=MaxSize-1；栈长：S.top+1
• 顺序栈的基本操作相关代码

  //初始化
  void InitStack(&S){
  S.top=-1;  //初始化栈顶指针
  }
  //判栈空
  bool StackEmpty(S){
    if(S.top==-1)
      return true;
    else
      return false;
  }
  //进栈
  bool Push(SqStack &S,ElemType x){
    if(S.top==MaxSize-1)  //栈满
      return false;
    S.data[++S.top]=x;  //指针自增1，入栈
    return true;
  }
  //出栈
  bool Pop(SqStack &S,ElemType &x){
    if(S.top==-1)  //栈空
      return false;
    x=S.data[S.top--];  //出栈，指针减一
    return true;
  }
  //读栈顶元素
  bool GetTop(SqStack S,ElemType &x){
    if(S.top==-1)
      return false;
    x=S.data[S.top];
    return true;
  }
  

• 共享栈

  利用栈底位置不变的特性，让两个栈共享一个一维数组空间，将两个栈的栈底分别设置在共享空间的两端，两个栈顶向共享空间的中间延伸

  • top0=-1是0号栈为空，top1=MaxSize时1号栈为空
  • 仅当两个栈顶指针相邻时，判断为栈满

---

链栈

采用链式存储的栈，通常采用单链表实现，并规定所有操作在单链表的表头进行，且链栈没有头结点，Lhead指向栈顶元素。

结构体描述

typedef struct Linknode{
  ElemType data;
  struct Linknode *next;
}*LiStack;

• 采用链式存储，便于插入、删除操作，具体步骤与单链表类似。
• 对n个不同元素进栈，出栈序列的个数为 卡特兰数

---

队列

队列的基本概念

1. 队列的定义

   只允许在表的一段进行插入，表的另一端进行删除

   • 队头：允许删除的一端
   • 队尾：允许插入的一端
   • 空队列：不含任何元素的空表
   • 队列是一个先进先出的线性表

2. 队列的基本操作

   • InitQueue(&Q)：初始化队列
   • QueueEmpty(Q)：判队列空
   • EnQueue(&Q)：入队
   • DeQueue(&Q,&x)：出队
   • GetHead(Q,&x)：读队头元素

---

队列的顺序存储结构

队列的顺序存储

分配一块连续的存储单元存放队列中的元素，并设置两个指针front和rear分别指示队头元素和队尾元素的位置。

结构体描述

#define MaxSize 50
typedef struct{
  ElemType data[MaxSize];
  int front,rear;
}SqQueue;

• 队头指针指向对头元素，队尾指针指向队尾元素的下一个位置
• 队列判空条件：Q.front=Q.rear=0
• 队列会出现假溢出的情况

循环队列

将顺序队列想象成一个环状空间，也就是逻辑上将存储队列元素的表看成一个环，即循环队列

• 初始时：Q.front=Q.rear=0
• 对首指针进1：Q.front=(Q.front+1)%MaxSize
• 对尾指针进1：Q.rear=(Q.rear+1)%MaxSize
• 队列长度：(Q.rear+MaxSize-Q.front)%MaxSize
• 队满判断：一般有三种
  • 牺牲一个单元来区分队空队满，即队头指针在队尾指针的下一位置作为队满的标志
    • 队满条件：(Q.rear+1)%MaxSize==Q.front
    • 队空条件：Q.front==Q.front
    • 队列中元素的个数：(Q.rear-Q.front+MaxSize)%MaxSize
  • 类型中增设表示元素个数的数据成员size，则队空条件为Q.size=0，队满条件为Q.size=MaxSize，两种情况中都有Q.front=Q.rear
  • 类型中增设tag数据成员，区分队空还是队满。则tag等于0的情况下，因删除导致Q.front==Q.rear则为队空，tag=1的情况下，因插入导致Q.front==Q.rear则为队满
• 循环队列的基本操作相关代码

//初始化
void InitQueue(&Q){
  Q.front=Q.rear=0;
}
//判队空
bool isEmpty(Q){
  if(Q.rear==Q.front)
    return true;
  else
    return false;
}
//入队
bool EnQueue(SqQueue &Q,ElemType x){
  if((Q.rear+1)%MaxSize==Q.front)  //队满
    return false;
  Q.data[Q.rear]=x;
  Q.rear=(Q.rear+1)%MaxSize;  //队尾指针加一取模
  return true;
}
//出队
bool DeQueue(SqQueue &Q,ElemType &x){
  if(Q.rear==Q.front)
    return false;
  x=Q.data[Q.front];
  Q.front=(Q.front+1)%MaxSize;  //队头指针加一取模
  return true;
}

---

队列的链式存储结构

队列的链式表示即链队列

• 结构体描述

typedef struct{  //链式队列结点
  ElemType data;
  struct LinkNode *next;
}LinkNode;
typedef struct{  //链式队列
  LinkNode *front,*rear;  //队列的队头和队尾指针
}LinkQueue;

• Q.front==NULL和Q.rear==NULL时，队列为空
• 链队列通常设计成带头结点的单链表，这样插入删除操作统一
• 链队列基本操作相关代码

//初始化
void InitQueue(LinkQueue &Q){
  Q.front=Q.rear=(LinkNode*)malloc(sizeof(LinkNode));
  Q.front->next=NULL;
}
//判队空
bool IsEmpty(LinkQueue Q){
  if(Q.front==Q.rear)
    return true;
  else
    return false;
}
//入队
void EnQueue(LinkQueue &Q,ElemType x){
  s=(LinkNode *)malloc(sizeof(LinkNode));
  s->data=x;
  s->next=NULL;
  Q.rear->next=s;
  Q.rear=s;
}
//出队
void DeQueue(LinkNode &Q,Elemtype &x){
  if(Q.front==Q.rear)
    return false;
  p=Q.front->next;
  x=P->data;
  Q.front->next=p->next;
  if(Q.rear==p)   //若原队列中只有一个结点，删除后变空
    Q.rear=Q.front;
  free(p);
  return true;
}

---

双端队列

双端队列是指允许两端都可以进行入队和出队操作的

• 输出受限的双端队列：允许一端进行插入和删除，但在另一端只允许插入的双端队列
• 输入受限的双端队列：允许一端进行插入和删除，但在另一端只允许删除的双端队列

---

栈和队列的应用

1. 中缀转后缀表达式
   • 若为‘(’，入栈
   • 若为‘)’，则依次把栈中的运算符加入后缀表达式，直到出现‘(’，并从栈中删除‘(’
   • 若为‘+’，‘-’，‘*’，‘/’
     • 栈空，入栈
     • 栈顶元素为‘(’，入栈
     • 高于栈顶元素优先级，入栈
     • 否则，依次弹出栈顶运算符，直到一个优先级比他低的运算符或‘)’为止
       *遍历完成，若栈非空，依次弹出所有元素

---

矩阵

压缩矩阵：指多个值相同的元素只分配一个存储空间，对零元素不分配存储空间。其目的是为了节省存储空间
特殊矩阵：指具有许多相同矩阵元素或零元素，并且这些相同矩阵元素或零元素的分布有一定规律性的矩阵。常见特殊矩阵有对称矩阵、上（下）三角矩阵、对角矩阵等
特殊矩阵的压缩存储方法：找出特殊矩阵中值相同的矩阵元素的分布规律，把那些呈现规律性分布的值的多个矩阵元素压缩存储到一个存储空间中

1. 对称矩阵
   元素下标的对应关系
   k = i * ( i - 1 ) / 2 + j - 1 ; i >= j
   k = j * ( j - 1 ) / 2 + i - 1 ; i < j
2. 三角矩阵
   下三角矩阵元素下标的对应关系
   k = i * ( i - 1 ) / 2 + j - 1 ; i >= j
   k = n * ( n + 1 ) / 2 ; i < j
   上三角矩阵元素下标的对应关系
   k = ( i - 1 ) * ( 2n - i + 2 ) / 2 + ( j - i ) ; i <= j
   k = n * ( n + 1 ) / 2 ; i > j
3. 三对角矩阵
   元素下标的对应关系
   k = 3 * ( i - 1 ) - 1 + j - i + 1 = 2i + j - 3
   已知k求i、j
   i = [ ( k + 1 ) / 3 + 1 ] ; j = k - 2i + 3

稀疏矩阵

矩阵元素个数远大于非零元素个数的矩阵

• 一般采用三元组（行标，列标，值）的形式存储
• 稀疏矩阵压缩存储后失去随机存取特性