0x01：栈（Stack）

  • 定义
    只能在表的一端（栈顶）进行插入和删除运算的线性表
  • 逻辑结构
    与线性表相同，仍为一对一关系
  • 存储结构
    用顺序栈或链栈存储均可，但以顺序栈更常见
  • 运算规则
    只能在栈顶运算，且访问结点时依照后进先出（LIFO）或者先进后出（FILO）的原则

  • 主要操作

    • 入栈和出栈函数，具体实现依顺序栈或链栈的不同而不同
    • 基本操作有入栈、出栈、读栈顶元素值、建栈、判断栈满、栈空等
      栈

0x02：栈的表示与操作实现

一、顺序栈的表示

顺序栈是分配一段连续的空间，需要两个指针，top 指示真正的栈顶元素之上的下标地址，base 指向栈的底部

  • 空栈状态
    当$ base = top $时表示栈空，是栈空标志

空栈

  • 将数据压入栈

数据压入栈中

$$ “进” = 压入 = PUSH() $$

$$ “出” = 弹出 = POP() $$

  • 栈满状态
    栈满时的处理方法：

    1. 报错、返回操作系统
    2. 分配更大的空间，作为栈的存储空间，将原栈的内容移入新栈

栈满

  • 栈的描述

    #define MAXSIZE 100
typedef struct{
    SElemType *base;
    SElemType *top;
    int stacksize;
}SqStack;

二、顺序栈的基本操作

  • 顺序栈的初始化（构建一个空栈）

    1. 分配空间并检查空间是否分配成功，若失败则返回错误
    2. 设置栈底和栈顶指针$ top = base $
    3. 设置栈大小
    Status initStack(SqStack &S){
    S.base = new SElemType[MAXSIZE];
    if(!S.base){
        return OVERFLOW;
    }
    S.top = S.base;
    S.stackSize = MAXSIZE;
    return OK;
}

  • 判断是否栈空

    1. 判断栈顶指针域栈底指针俩个指针是否相等
    bool stackEmpty(SqStack S){
    if(S.top == S.base){
        return true;
    }else{
        return false;
    }
}

  • 求顺序栈的长度

    1. 栈顶和栈底俩个指针相减
      （在顺序栈中，栈顶指针地址减去栈底指针地址所得到的就是在这俩个地址之间所包含的元素个数）
    int stackLength(SqStack S){
    return S.top - S.base;
}

  • 清空顺序栈

    1. 让栈顶指针域栈底指针有相同指向，即都指向栈底
    Status clearStack(SqStack &S){
    if(S.base){
        S.top = S.base;
    }
    return OK;
}

  • 销毁顺序栈

    1. 释放所有内存空间
    2. 顺序栈的三个成员变量置零
    Status destroyStack(SqStack &S){
    if(S.base){
        delete S.base;
        S.stacksize = 0;
        S.base = S.top = NULL;
    }
    return OK;
}

  • 顺序栈进栈

    1. 判断是否栈满，若栈满则抛出错误
    2. 将元素 e 压入栈顶
    3. 栈顶指针 +1
    Status Push(SqStack &S, SElemType e){
    if(S.top - S.base == S.stacksize){
        // 栈满
        return ERROR;
    }
    *S.top++=e;            // 相当于 *S.top = e; S.top++;
    return OK;
}

  • 顺序栈出栈

    1. 判断是否空栈，若空栈则抛出错误
    2. 获取栈顶元素 e
    3. 栈顶指针 -1
    Status Pop(SqStack &S, SElemType &e){
    if(S.top == S.base){
        // 栈空
        return ERROR;
    }
    e=*--S.top;            // 相当于 --S.top; e = *S.top;
    return OK;
}

  • 顺序栈取栈顶元素

    1. 判断是否空栈，若空栈则抛出错误
    2. 若不为空栈则通过栈顶指针获取栈顶元素
    Status getTop(SqStack S, SElemType &e){
    if(S.top == S.base){
        // 栈空
        return ERROR;
    }
    e = *(S.top - 1);
    return OK;
}

三、链栈的表示

链栈每个结点的地址是不连续的，从图中可以看出，链栈的每个结点都包含两个域：数据域和指针域；链栈有点类似于单链表，不同的地方就链栈是只能在栈顶上操作，所以只需要一个栈顶指针即可。

链栈

typedef struct StackNode{
    SElemType data;
    struct StackNode *next;
}StackNode, *LinkStack;

LinkStack S;

四、链栈的基本操作

  • 链栈的初始化
    初始化链栈

    void initStack(LinkStack &S){
    S = NULL;
}

  • 判断链栈是否为空

    1. 链栈为空返回真，否则返回假
    Status stackEmpty(LinkStack S){
    if(S = NULL){
        return true;
    }else{
        return false;
    }
}

  • 链栈进栈

    1. 申请一个结点，由 p 指向
      新结点
    2. 如果申请成功则将 e 写入 p 数据域中，失败则返回错误
      将e写入新结点
    3. 进栈（将 p 的指针域指向栈顶指针指向的下一个结点）
      进栈
    4. 修改栈顶指针
      修改栈顶
    Status Push(LinkStack &S, SElemType e){
    p = new StackNode;
    if(!p){
        return OVERFLOW;
    }
    p->data = e;
    p->next = S;
    S = p;
    return OK;
}

  • 链栈出栈

    1. 判断链栈是否为空
    2. 结点出栈
    3. 修改栈顶指针，释放出栈结点
      链栈出栈
    Status Pop(LinkStack &S, SElemType &e){
    if(S = NULL){
        return ERROR;
    }
    e = S->data;
    p = S;
    S = S->next;
    delete p;
    return OK;
}

  • 取链栈栈顶元素

    1. 判断链栈是否为空
    2. 若不为空则读取栈顶元素，若为空则抛出错误
    SElemType getTop(LinkStack S){
    if(S = NULL){
        return ERROR;
    }else{
        return S->data;
    }
}

五、栈与递归

  • 递归的定义

    • 若一个对象部分地包含自己，或用 它自己给自己定义，则称这个对象是递归的
    • 若一个过程直接地或间接地调用自己，则称这个过程是递归的过程

  • 递归举例

    • 阶乘函数

$$ Fact(n)=\left\{\begin{matrix} 1 & 若n=0 \\ n * Fact(n-1) & 若n>0 \end{matrix}\right. $$

  • 二阶 Fibonaci 数列

$$ Fact(n)=\left\{\begin{matrix} 1 & 若n=1或2 \\ Fib(n-1) + Fib(n-2) & 其他 \end{matrix}\right. $$

  • 广义表

$$ A=(a,A) $$

  • 求解递归问题的方法

    • 分治法
      对于一个较为复杂的问题，能够分解成几个相对简单的且解法相同或类似的子问题来求解

    能用分治法处理问题的三个条件：

    1. 能将一个问题转变成一个新问题，而新问题与原问题的解法相同或类同，不同的仅是处理的对象，且这些处理对象是变化有规律的
    2. 可以通过上述转化使问题简化
    3. 必须有一个明确的递归出口，或称递归的边界

    • 分治法求解递归问题算法的一般形式

      void p(参数){
    if(递归结束的条件){        // 基线条件
        可直接求解步骤;        // 基本项
    }else{
        return p(较小的参数); // 归纳项
    }
}

      栗如

      long Fact(long n){
    if(n == 0){
        return 1;
    }else{
        return n * Fact(n-1)
    }
}

0x03：队列（Queue）

  • 定义

    • 队列是一种先进先出（FIFO）的线性表；
    • 在表一端（队尾）插入，在另一端（队首）删除

$$ Q = (a_1,a_2,a_3,...,a_n) $$

队列

  • 逻辑结构
    与线性表相同，仍为一对一关系
  • 存储结构
    用顺序存储或链式均可
  • 运算规则
    先进先出（FIFO）
  • 主要操作
    入队和出队函数，具体实现依顺序栈或链栈的不同而不同

0x04：队列与栈的区别

  • 相同之处

    • 栈、队列都是一种特殊（操作受限）的线性表

  • 不同之处

    • 仅在于运算规则不同
    • 队列的运算规则是先进先出，而栈的运算规则是后进先出
一般线性表队列栈
逻辑结构一对一一对一一对一
存储结构顺序表、链表顺序队列、链式队列顺序栈、链式栈
运算规则随机、顺序存取先进先出后进先出

0x05： 队列的表示与操作实现

  • 队列数据对象：$ D=\{a_i|a_i\in ElemSet,i=1,2,3,...,n，n \geq 0\} $
  • 队列数据关系：$ R_1=\{<a_{i-1},a_i>|a_{i-1},a_i \in D,i=1,2,3,...,n\} $，约定$ a_1 $端为队列头，$ a_n $端为队列尾

一、顺序队列的表示

  • 采用一堆数组 base[MAXSIZE]

    #define MAXSIZE 100        // 队列最大长度
typedef struct{
    QElemType *base;    // 初始化的动态分配存储空间
    int front;            // 头指针
    int rear;            // 尾指针
}SqQueue;
    • 空队标志：front == rear
    • 入队： base[ rear++ ] = x
    • 出队：x = base[ front++ ]
      队列操作

    • 存在的问题：

      • 当 front = 0, rear = MAXSIZE 时，再入队则为真溢出（真满）
      • 当 front ≠ 0, rear = MAXSIZE 时，再入队则为假溢出（假满）
        存在的问题
    • 解决方案：采用循环队列的方式

  • 采用循环队列的方式

    • 若 base[ MAXSIZE ] 接在 base[ MAXSIZE - 1 ] 之后，若 rear + 1 = MAXSIZE ，则令 rear = 0
    • 实现方法 ： 利用“模”运算
    // 入队
base[rear]  = x;
rear = (rear+1)%M;

// 出队
x = base[front];
front = (front+1)%M;

    循环队列

    • 新的问题：

      • 无法区分队空队满

    • 解决方案：

      1. 另外设一个标志以区分队空、队满
      2. 少用一个元素空间
        队空： front == rear

      队满： ( rear + 1 ) % M == front

二、顺序循环队列的基本操作

  • 循环队列初始化

    1. 申请一个空队
    2. 设置空队的队首、队尾标志
    Status initQueue(SqQueue &Q){
    Q.base = new QElemType[MAXSIZE];
    if(!Q.base){
        return OVERFLOW;
    }
    Q.front = Q.rear = 0;
    return OK;
}

  • 求循环队列的长度

    1. 若 front 在 rear 前，则计算长度方式为$ rear - front $
    2. 但是如果 rear 在 front 前，就不能使用$ front - rear $进行计算了
      求循环队列的真实长度

所以最后选用$ (rear - front + MAXSIZE) \% MAXSIZE $来计算循环队列的长度

int queueLength(SqQueue Q){
    return (Q.rear - Q.front + MAXSIZE) % MAXSIZE
}

  • 循环队列入队

    1. 判断队列是否满队，若满队则抛出错误
    2. 队列尾部入队
    3. 队列尾指针移动
    Status enQueue(SqQueue &Q, QElemType e){
    if((Q.rear + 1) % MAXSIZE == Q.front){
        return ERROR;
    }
    Q.base[Q.rear] = e;
    Q.rear = (Q.rear + 1) % MAXSIZE;
    return OK;
}

  • 循环队列出队

    1. 判断队列是否为空队，若为空队则抛出错误
    2. 队首出队
    3. 队列首指针移动
    Status deQueue(SqQueue &Q, QElemType &e){
    if(Q.front == Q.rear){
        return ERROR;
    }
    e = Q.base[Q.front];
    Q.front = (Q.front + 1) % MAXSIZE;
    return OK;
}

三、链循环队列的表示

typedef struct QNode{
    QElemType data;
    struct Qnode *next;
}Qnode, *QueuePtr;

typedef struct{
    QueuePtr front;        // 队头指针
    QueuePtr rear;        // 队尾指针
}LinkQueue;

链式队列

四、链循环队列的基本操作

  • 链式队列初始化

    Status initQueue(LinkQueue &Q){
Q.front = Q.rear = (QueuePtr)malloc(sizeof(QNode));
if(!Q.front){
  return OVERFLOW;
}
Q.front->next = NULL;
return OK;
}

  • 销毁链式队列

    Status destroyQueue(LinkQueue &Q){
while(Q.front){
  Q.rear = Q.front->next;
  free(Q.front);
  Q.front = Q.rear;
}
return OK;
}

  • 判断链式队列是否为空
    空队

    Status queueEmpty(LinkQueue Q){
return (Q.front == Q.rear);
}

  • 获取链式队列的队头元素

    Status getQueueHead(LinkQueue Q, QElemType &e){
if(Q.front == Q.rear){
  return ERROR;
}
e = Q.front->next->data;
return OK;
}

  • 链队入队
    链队入队

    Status enQueue(LinkQueue &Q, QElemType e){
p = (QueuePtr)malloc(sizeof(QNode));
if(!p){
  return OVERFLOW;
}
p->data = e;
p->next = NULL;
Q.rear->next = p;
Q.rear = p;
return OK;
}

  • 链队出队
    元素Y出队

    Status deQueue(LinkQueue &Q, QElemType %e){
if(Q.front == Q.rear){
  return ERROR;
}
p = Q.front->next;
e = p->data;
Q.front->next = p->next;
if(Q.rear == p){
  Q.rear = Q.front;
}
delete p;
return OK;
}
Last modification：November 11th, 2020 at 06:25 pm
© 允许规范转载
给狐宝打点钱⑧