数据结构Ch3

第三章 栈、队列和数组

栈

栈的基本概念

栈的定义

• 栈是只允许在一段进行插入或删除操作的线性表。
• 栈顶：线性表允许进行插入和删除操作的那一端
• 栈底：固定的，不允许进行插入和删除的另一端
• 空栈：不含任何元素的空表

栈的基本操作

• InitStack(&S)：初始化一个空栈S
• StackEmpty(S)：判断一个栈是否为空
• Push(&S,x)：入栈，若栈S未满，则将x加入使之成为新的栈顶
• Pop(&S,&x)：出栈，若栈S非空,则弹出栈顶元素,并用x返回
• GetTop(S,&x)：读栈顶元素，但不出栈，若栈S非空，则用x返回栈顶元素
• DestroyStack(&S)：销毁栈，并释放S占用的存储空间

栈的顺序存储结构

顺序栈的实现

• 采用顺序存储的栈称为顺序栈，它利用一组地址连续的存储单元存放自栈底到栈顶的数据元素，同时带有一个top指针指向栈顶元素

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

• 声明一个顺序栈后，会在内存中开辟一片连续的、大小为MaxSize*sizeof(Elemtype)字节的空间，top指针为栈顶元素的索引，空栈为-1

进栈操作

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

bool Push(SqStack &S,ElemType x){
    if(S.top==MaxSize-1) 
        return false;
    
    //这两句可以合并为S.data[++S.top]=x;
    S.top = S.top + 1;
    S.data[S.top]=x;
    return true;
}

出栈操作

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

bool Pop(SqStack &S,ElemType &x){
    if(S.top==-1)
        return false;

    //这两行可以合并为x=S.data[S.top--];
    x=S.data[S.top];
    S.top=S.top-1;
    return true;
}

读取栈顶元素操作

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

bool GetTop(SqStack S,ElemType &x){
    if(S.top==-1)
        return false;
    x=S.data[S.top];
    return true;
}

共享栈

#define MaxSize 10
typedef struct{
    Elemtype data[MaxSize];
    int top0;
    int top1;
}SqStack;

• 当共享栈满时，top1=top0+1

栈的链式存储结构

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

队列

队列的基本概念

队列的定义

• 队列是一种操作受限的线性表，只允许在表的一端进行插入，而在表的另一端进行删除。先进先出
• 队头：允许删除的一端
• 队尾：允许插入的一端
• 空队列：不含任何元素的空表

队列的常见操作

• InitQueue(&Q)：初始化队列，构造一个空队列
• QueueEmpty(Q)：判断队列空
• EnQueue(&Q,x)：入队，若队列未满，将x加入，并使之称为新的队尾
• DeQueue(&Q,&x)：出队，若队列非空，删除队首元素，并用x返回
• GetHead(Q,&x)：读取队首元素，若队列非空，则把队首元素赋给x

队列的顺序存储结构

队列的实现

• 使用静态数组实现队列

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

入队

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

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;
}

出队

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

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;
}

• 队列元素个数=(rear+MaxSize-front)%MaxSize

判满/判空方案二

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

• 根据size的值判断是否为空/满

判满/判空方案三

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

• 只有删除操作会导致队空，只有插入操作会导致队满
• 当删除成功时，tag赋值为-，插入成功时，tag赋值为1
• 初始tag为0
• 队满条件：front==rear&&tag==1

队尾指针指向队尾元素时

• 初始化：front=0,rear=n-1
• 判空：front=(rear+1)%MaxSize
• 判满：front=(rear+2)%MaxSize
• 牺牲一个存储单元，或者tag/size

队列的链式存储

定义

typedef struct LinkNode{
    ElemType data;
    struct LinkNode *next;
}LinkNode;

typedef struct {
    LinkNode *front,*near;
}LinkQueue;

初始化（带头结点）

typedef struct LinkNode{
    ElemType data;
    struct LinkNode *next;
}LinkNode;

typedef struct {
    LinkNode *front,*near;
}LinkQueue;

void InitQueue(LinkQueue &Q){
    Q.front=Q.rear=(LinkNode*)malloc(sizeof(LinkNode));
    Q.front->next=NULL;
}

• 先声明，再初始化

入队（带头节点）

void EnQueue(LinkQueue &Q,ElemType x){
    LinkNode *s=(LinkNode*)malloc(sizeof(LinkNode));
    s->data=x;
    s->data=NULL;
    Q.rear->next=s;
    Q.rear=s;
}

入队（不带头节点）

void EnQueue(LinkQueue &Q,ElemType x){
    LinkNode *s=(LinkNode*)malloc(sizeof(LinkNode));
    s->data=x;
    s->next=NULL;
    if(Q.front==NULL){
        Q.front=s;
        Q.rear=s;
    } else {
        Q.rear->next=s;
        Q.rear=s;
    }
}

出队（带头节点）

bool DeQueue(Linkqueue &Q,ElemType &x){
    if(Q.front==Q.rear)
        return false;
    LinkNode *p=Q.front->next;
    x=p->data;
    Q.front->next=p->next;
    if(Q.rear==p)
        Q.rear=Q.front;
    free(p);
    return true;
}

出队（不带头节点）

bool DeQuquq(LinkNode &Q,ElemType &x){
    if(Q.front==NULL)
        return false;
    LinkNode *p=Q.front;
    x=p->data;
    Q.front=p->next;
    if(Q.rear==p){
        Q.front=NULL;
        Q.rear=NULL;
    }
    free(p);
    return true;
}

双端队列

定义

• 只允许从两端插入、两端删除的线性表

操作受限的双端队列：判断输出序列的合法性

• 如果一个序列符合栈的规则，那一定符合受限的双端序列
• 卡特兰数：合法的出栈序列个数
  $$
  C_n = \frac{1}{n+1}\binom{2n}{n} = \frac{(2n)!}{(n+1)!n!}
  $$

括号匹配问题

流程图

代码实现

bool bracketCheck(char str[], int length) {
    SqStack S; 
    InitStack(S);
    for (int i = 0; i < length; i++) {
        if (str[i] == '(' || str[i] == '[' || str[i] == '{') {
            Push(S,str[i]);
        } else {
            if (StackEmpty(S)) { // 扫描到右括号，但栈为空
                return false; // 匹配失败
            }
            char topElem;
            Pop(S,topElem);// 弹出栈顶元素
            
            // 检查括号是否匹配
            if (str[i] == ')' && topElem != '(') {
                return false;
            }
            if (str[i] == ']' && topElem != '[') {
                return false;
            }
            if (str[i] == '}' && topElem != '{') {
                return false;
            }
        }
    }
    return StackEmpty(S); // 栈空说明所有括号匹配成功
}

表达式求值

三种算术表达式

中缀表达式

• 运算符在操作数中间

后缀表达式（逆波兰式）

• 运算符在两个操作数后边

前缀表达式（波兰式）

• 运算符在两个操作数前边

中缀转后缀

步骤（机算）

• 初始化一个栈，用于保存暂时不能确定运算顺序的运算符
• 从左到右处理各个元素，直到末尾
  • 遇到操作数。直接加入后缀表达式
  • 遇到界限符。遇到“（”直接入栈；遇到“）”则依次弹出栈内运算符并加入后缀表达式，直到弹出“（”为止。注意：括号不加入后缀表达式
  • 遇到运算符。依次弹出栈中优先级高于或等于当前运算符的所有运算符，加入后缀表达式，若碰到“（”或栈空则停止。之后再把当前运算符入栈。
• 将剩余运算符依次弹出，并加入后缀表达式

后缀转中缀

思想

• 从左往右扫描，每遇到一个运算符，就将<左操作数 右操作数 运算符>变为（左操作数 运算符 右操作数）的形式

后缀表达式计算

思想

• 从左往右扫描，遇到操作数则入栈，遇到运算符则弹出两个栈顶元素运算后入栈（注意：先弹出的是右操作数）

前缀表达式计算

思想

• 从右往左扫描，遇到操作数入栈，遇到运算符则弹出两个栈顶元素运算后入栈（注意：先弹出左操作数）

中缀表达式计算（用栈和后缀实现）

思想

• 初始化两个栈，操作符栈和操作数栈
• 若扫描到操作数，压入操作数栈
• 若扫描到运算符或界限符，按照“中缀转后缀”的规则压入运算符栈（也会弹出运算符，当弹出时，需要同时弹出两个操作数进行计算，再将结果压入操作数栈）

矩阵的压缩存储

数组的存储结构

一维数组的存储结构

• 数组元素a[i]的存放地址=LOC+i*sizeof(ElemType)

二维数组的存储结构

• 行优先存储
  • 二维数组b[m][n]中，b[i][j]的存放地址LOC+(i*N+j)*sizeof(ElemType)
• 列优先存储
  • 二维数组b[m][n]中，b[i][j]的存放地址LOC+(j*M+i)*sizeof(ElemType)

矩阵的存储

普通矩阵

• 使用二维数组方法

对称矩阵的压缩存储

• 只需要存储上三角/下三角，压缩为一维数组
• 需要存储1+2+…+n个元素
• 将矩阵下表映射为一维数组下标a[i][j]->B[k]（i>j）：
  $$
  k = \frac{i(i-1)}{2} + j-1
  $$
• 当i<j时，访问a[j][i]
  $$
  k = \frac{j(j-1)}{2} + i-1
  $$7

三角矩阵的压缩存储（下三角）

• 按行优先原则将三角部分元素存入一维数组中。并在最后一个位置存储常量c
• 当i≥j时
  $$
  k = \frac{i(i-1)}{2} + j-1
  $$
• 当i<j时
  $$
  k= \frac{n(n-1)}{2}
  $$
• 上三角同理

三对角矩阵的压缩存储（带状矩阵）

• 当|i-j|>1时， $a_{ij}=0$
• 压缩存储策略：按行优先（列优先）原则，只存储带状部分
• 前面的$i-1$行有$3(i-1)-1$个元素
• $a_{ij}$是第$i$行第$j-i+2$个元素
• 因此$a_{ij}$是第$2i+j-2$个元素
• 已知k如何求i，j
  
• 法一：这个元素是k+1个元素，因此右边取等
• 法二：这个元素前边有k个元素，左边取等

稀疏矩阵

• 压缩存储策略;
  • 顺序存储：三元组<行，列，值>
    • 失去随机存取特性
  • 十字链表法