数据结构与算法第四讲:[栈]

作者: 85ca4232089b | 来源:发表于2020-04-11 13:17 被阅读0次

文章末尾提供demo和简单的练习题

数据结构与算法.jpg

栈

栈是一种线性序列结构，它的特殊之处在于，栈对于其中的元素的访问做了限制，只能从序列的某一端进行读写操作。我们知道，对于向量或者是列表，我们可以访问其中的任意一个元素。但是对于栈，我们只能访问位于栈的某一特定端的元素（栈顶）。

栈的示意图

既然栈是一种数据结构，那么它必然也有自己的操作接口:

操作结构	功能
size()	报告栈的规模
empty()	判断栈是否为空
push(e)	将元素 e 插至栈顶（入栈）
pop()	删除栈顶对象，并返回该对象的引用（出栈）
top()	引用栈顶对象

由此可以看出栈最底部的元素是最先入栈的，而栈顶元素是最后入栈的，但是出栈时则倒了过来，栈顶元素先出栈，栈底元素最后出栈。所以，栈中元素遵循「后进先出」（last-in-first-out，LIFO）的规律。

进栈&出栈

在实际应用中通常只会对栈执行以下两种操作:
• 向栈中添加元素，此过程被称为"进栈"（入栈或压栈）
• 栈中提取出指定元素，此过程被称为"出栈"（或弹栈）

栈的具体实现

栈是一种 "特殊" 的线性存储结构，因此栈的具体实现有以下两种方式：
• 顺序栈：采用顺序存储结构可以模拟栈存储数据的特点，从而实现栈存储结构；
• 链栈：采用链式存储结构实现栈结构；

两种实现方式的区别，仅限于数据元素在实际物理空间上存放的相对位置，顺序栈底层采用的是数组，链栈底层采用的是链表.

顺序栈

创建一个空栈

栈顶指针并不是一个指针变量当栈顶指针top==-1的时候我们就认为是一个空栈。

/* 顺序栈结构 */
typedef struct
{
    SElemType data[MAXSIZE];
    int top; /* 用于栈顶指针 */
}SqStack;
Status initStack(SqStack *S){
    
    S->top = -1 ;
    return OK;
}

判断栈是否为空

Status StackEmpty(SqStack S){
    if (S.top == -1)
        return TRUE;
    else
        return FALSE;
}

置空栈

将栈置空,不需要将顺序栈的元素都清空,只需要修改top标签就可以了.

Status ClearStack(SqStack *S){
    S->top = -1;
    return OK;
}

栈的长度

int StackLength(SqStack S){
    return S.top + 1;
}

获取栈顶元素

Status GetTop(SqStack S,SElemType *e){
    if (S.top == -1)
        return ERROR;
    else
        *e = S.data[S.top];
   
    return OK;
    
}

插入元素到栈顶（入栈）

Status PushData(SqStack *S, SElemType e){
    
    //栈已满
    if (S->top == MAXSIZE -1) {
        return ERROR;
    }
    
    //栈顶指针+1;
    S->top ++;
    //将新插入的元素赋值给栈顶空间
    S->data[S->top] = e;
    
    return OK;
}

删除栈顶元素（出栈）

Status Pop(SqStack *S,SElemType *e){
   
    //空栈,则返回error;
    if (S->top == -1) {
        return ERROR;
    }
    
    //将要删除的栈顶元素赋值给e
    *e = S->data[S->top];
    //栈顶指针--;
    S->top--;
    
    return OK;
}

遍历栈元素

Status StackTraverse(SqStack S){
    int i = 0;
    printf("此栈中所有元素");
    while (i<=S.top) {
        printf("%d ",S.data[i++]);
    }
    printf("\n");
    return OK;
}

链栈

链式栈：就是一种操作受限的单向链表
链式栈的操作一般含有：出栈、入栈、栈的初始化、判断栈是否为空、清空
链式栈：新一个节点->将新建节点的指针域指向原栈顶节点->将栈顶指针移动到新建节点

链栈结构图.png

链式栈的初始化

/*构造一个空栈S */
Status InitStack(LinkStack *S)
{
*S = (LinkStack )malloc(ziseof(StackNode));
if(*S->top == NULL){
return ERROR ;
}
    S->top=NULL;
    S->count=0;
    return OK;
}

链式栈的置空

Status ClearStack(LinkStack *S){
    LinkStackPtr p,q;
    p = S->top;
    while (p) {
        q = p;
        p = p->next;
        free(q);
    }
    S->count = 0;
    return OK;
    
}

链式栈的长度

int StackLength(LinkStack S){
    return S.count;

链式栈的是否为空

Status StackEmpty(LinkStack S){
    if (S.count == 0)
        return TRUE;
    else
        return FALSE;
}

链式栈的获取栈顶元素

Status GetTop(LinkStack S,SElemType *e){
    if(S.top == NULL)
        return ERROR;
    else
        *e = S.top->data;
    return OK;
}

链式栈的插入元素到栈顶位置

1 新建结点temp，赋值
2.把新结点temp的next指向制定指针top。temp->next = s->top
3.更新栈顶指针top s->top = temp
4.栈S的count++

链式栈插入栈顶元素

Status Push(LinkStack *S, SElemType e){
    
    //创建新结点temp
    LinkStackPtr temp = (LinkStackPtr)malloc(sizeof(StackNode));
    //赋值
    temp->data = e;
    //把当前的栈顶元素赋值给新结点的直接后继, 参考图例第①步骤;
    temp->next = S->top;
    //将新结点temp 赋值给栈顶指针,参考图例第②步骤;
    S->top = temp;
    S->count++;
    return OK;
}

链式栈的删除栈顶元素

新建节点p指向S->top
栈顶指针下移一位, 指向后一结点 S->top= S->top->next
释放p free(p);
S->count--

删除栈顶元素.png

/*5.7 若栈不为空,则删除S的栈顶元素,用e返回其值. 并返回OK,否则返回ERROR*/
Status Pop(LinkStack *S,SElemType *e){
    LinkStackPtr p;
    if (StackEmpty(*S)) {
        return ERROR;
    }
    
    //将栈顶元素赋值给*e
    *e = S->top->data;
    //将栈顶结点赋值给p,参考图例①
    p = S->top;
    //使得栈顶指针下移一位, 指向后一结点. 参考图例②
    S->top= S->top->next;
    //释放p
    free(p);
    //个数--
    S->count--;
    
    return OK;
}

链式栈的遍历

Status StackTraverse(LinkStack S){
    LinkStackPtr p;
    p = S.top;
    while (p) {
        printf("%d ",p->data);
        p = p->next;
    }
    printf("\n");
    return OK;
}

栈和递归

递归的基本思想

所谓递归，就是有去有回。
递归的基本思想，是把规模较大的一个问题，分解成规模较小的多个子问题去解决，而每一个子问题又可以继续拆分成多个更小的子问题。
最重要的一点就是假设子问题已经解决了，现在要基于已经解决的子问题来解决当前问题；或者说，必须先解决子问题，再基于子问题来解决当前问题
直接或者间接调用本身就是递归

什么场景下使用递归

• 定义是本身就是递归：阶乘、斐波拉契数列
• 数据结构式递归的链表的数据结构定义（指针域）
其数据结构本身具有递归特点
例如，对于链表其结点Node的定义是由数据域date和指针域next组成，而其指针域next是一种指向Node类的指针，即Node的定义中用到了本身，所以链表是一种递归的数据结构
• 问题是递归的汉诺塔问题

分治法解决递归问题的条件

• 一个大的问题可以差分成一个晓得问题，并且小问题的实现和大问题高度的雷同
• 通过分治，可以简化问题的解决
• 必须要有一个递归出口、递归边界

函数调用看递归函数栈

funcA{
funcB();
}
funcB{
funcC();
}
funcC{
}

调用函数A；
调用函数B；
调用函数C；
函数C返回；
函数B返回；
函数A返回；

递归函数调⽤用分析.png
调用函数和被调用函数链接和信息交换通过栈空间进行的。先调用后返回的规则

一个函数在运行期间调用另一个函数，在运行被调用函数之前，系统需要先完成3件事情：
• 把所有的实参和函数的返回地址信息传递给被调用的函数保存起来(栈空间)
• 为被调用函数的局部变量分配存储空间
• 把代码编译的控制权交给被调用函数

被调用函数返回调用函数之前，系统做的3件事情：
• 保存被调用函数的计算结构
• 释放被调用函数的数据去
• 根据保存的返回地址信息把控制权交给调用函数

int second(int d){ int x,y;
//...
}
int first(int s ,int t){ int i;
//... second(i)
//2.⼊入栈 //...
}
void main( ){ int m,n;
first(m ,n); //1.⼊入栈
//...
}

递归过程与递归⼯工作栈.png

汉诺塔问题

从左到右有A、B、C三根柱子，其中A柱子上面有从小叠到大的n个圆盘，现要求将A柱子上的圆盘移到C柱子上去，期间只有一个原则：一次只能移到一个盘子且大盘子不能在小盘子上面，求移动的步骤和移动的次数

汉诺塔问题.jpg

解：（1）n == 1
第1次 1号盘 A---->C sum = 1 次
(2) n == 2
　　　　　　第1次 1号盘 A---->B
　　　　　　第2次 2号盘 A---->C
　　　　　　第3次 1号盘 B---->C sum = 3 次
（3）n == 3
　　　　　　　第1次 1号盘 A---->C
　　　　　　　第2次 2号盘 A---->B
　　　　　　　第3次 1号盘 C---->B
　　　　　　　第4次 3号盘 A---->C
　　　　　　　第5次 1号盘 B---->A
　　　　　　　第6次 2号盘 B---->C
　　　　　　　第7次 1号盘 A---->C sum = 7 次
不难发现规律：1个圆盘的次数 2的1次方减1
　　　　　　　2个圆盘的次数 2的2次方减1
3个圆盘的次数 2的3次方减1
n个圆盘的次数 2的n次方减1

故：移动次数为：2^n - 1

调用方法的栈机制:（特点：先进后出）

    从主线程开始调用方法（函数）进行不停的压栈和出栈操作，函数的调用就是将函数压如栈中，函数的结束就是函数出栈的过程，这样就保证了方法调用的顺序流，即当函数出现多层嵌套时，需要从外到内一层层把函数压入栈中，最后栈顶的函数先执行结束（最内层的函数先执行结束）后出栈，再倒数第二层的函数执行结束出栈，到最后，第一个进栈的函数调用结束后从栈中弹出回到主线程，并且结束。

算法分析（递归算法）：

    我们在利用计算机求汉诺塔问题时，必不可少的一步是对整个实现求解进行算法分析。到目前为止，求解汉诺塔问题最简单的算法还是同过递归来求，至于是什么是递归，递归实现的机制是什么，我们说的简单点就是自己是一个方法或者说是函数，但是在自己这个函数里有调用自己这个函数的语句，而这个调用怎么才能调用结束呢？，这里还必须有一个结束点，或者具体的说是在调用到某一次后函数能返回一个确定的值，接着倒数第二个就能返回一个确定的值，一直到第一次调用的这个函数能返回一个确定的值。

实现这个算法可以简单分为三个步骤：
　　　　（1）把n-1个盘子由A 移到 B；
　　　　（2）把第n个盘子由 A移到 C；
　　　　（3）把n-1个盘子由B 移到 C；
从这里入手，在加上上面数学问题解法的分析，我们不难发现，移到的步数必定为奇数步：
　　　　（1）中间的一步是把最大的一个盘子由A移到C上去；
　　　　（2）中间一步之上可以看成把A上n-1个盘子通过借助辅助塔（C塔）移到了B上，
　　　　（3）中间一步之下可以看成把B上n-1个盘子通过借助辅助塔（A塔）移到了C上；

int m = 0;
void moves(char X,int n,char Y){
   m++;
   printf("%d: from %c ——> %c \n",n,X,Y);
}

//n为当前盘子编号. ABC为塔盘
void Hanoi(int n ,char A,char B,char C){
   
   //目标: 将塔盘A上的圆盘按规则移动到塔盘C上,B作为辅助塔盘;
   
   //将编号为1的圆盘从A移动到C上
   if(n==1) moves(A, 1, C);
   else
   {
       //将塔盘A上的编号为1至n-1的圆盘移动到塔盘B上,C作为辅助塔;
       Hanoi(n-1, A, C, B);
       //将编号为n的圆盘从A移动到C上;
       moves(A, n, C);
       //将塔盘B上的编号为1至n-1的圆盘移动到塔盘C上,A作为辅助塔;
       Hanoi(n-1, B, A, C);
   }
}
   Hanoi(4, 'A', 'B', 'C');
   printf("盘子数量为4:一共实现搬到次数:%d\n",m);
1: from A ——> B 
2: from A ——> C 
1: from B ——> C 
3: from A ——> B 
1: from C ——> A 
2: from C ——> B 
1: from A ——> B 
4: from A ——> C 
1: from B ——> C 
2: from B ——> A 
1: from C ——> A 
3: from B ——> C 
1: from A ——> B 
2: from A ——> C 
1: from B ——> C 
盘子数量为4:一共实现搬到次数:15

斐波拉契数列

int Fbi(int i){
    if(i<2)
        return i == 0?0:1;
    return Fbi(i-1)+Fbi(i-2);
}
    for (int i =0; i < 10; i++) {
         printf("%d  ",Fbi(i));
    }

一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

可以把n级台阶时的跳法看成是n的函数，记为f(n)。当n>2时，第一次跳的时候就有两种不同的选择：一是第一次只跳1级，此时跳法数目等于后面剩下的n-1级台阶的跳法数目，即为f(n-1);另一种选择是第一次跳2级，此时跳法数目等于后面剩下n-2级台阶的跳法数目，即为f(n-2)。因此，n级台阶的不同跳法的总数f(n)=f(n-1)+f(n-2)。分析到这里，不难看出这实际上就是斐波那契数列了。

与斐波那契数列不同的是，其初始值定义稍有不同，
当n=1时，只能跳一级台阶，一种跳法
当n=2时，一次跳一级或两级，两种跳法

青蛙跳台阶的定义.png

int FrogJump12StepRecursive(int n)
{
    if (n == 1)
    return 1;
    if (n == 2)
    return 2;
    return FrogJump12StepRecursive(n - 1) + FrogJump12StepRecursive(n - 2);
}

一只青蛙一次可以跳上1级台阶，也可以跳上2级,它也可以跳上n级，此时该青蛙跳上一个n级的台阶总共有多少种跳法？

用数学归纳法可以证明：f(n)=2n−1f(n)=2n−1.

递归式证明：
当n = 1 时，只有一种跳法，即1阶跳：Fib(1) = 1;
当n = 2 时，有两种跳的方式，一阶跳和二阶跳：Fib(2) = Fib(1) + Fib(0) = 2;
当n = 3 时，有三种跳的方式，第一次跳出一阶后，后面还有Fib(3-1)中跳法；第一次跳出二阶后，后面还有Fib(3-2)中跳法；第一次跳出三阶后，后面还有Fib(3-3)中跳法
Fib(3) = Fib(2) + Fib(1)+Fib(0)=4;
当n = n 时，共有n种跳的方式，第一次跳出一阶后，后面还有Fib(n-1)中跳法；第一次跳出二阶后，后面还有Fib(n-2)中跳法……………………..第一次跳出n阶后, 后面还有 Fib(n-n)中跳法.
Fib(n) = Fib(n-1)+Fib(n-2)+Fib(n-3)+……….+Fib(n-n)=Fib(0)+Fib(1)+Fib(2)+…….+Fib(n-1)
又因为Fib(n-1)=Fib(0)+Fib(1)+Fib(2)+…….+Fib(n-2)
两式相减得：Fib(n)-Fib(n-1)=Fib(n-1)
=====》 Fib(n) = 2*Fib(n-1) n >= 2
递归等式如下：
n = 1 f(n) = 1;
n = 2 f(n) = 2;
n > 2 f(n) = 2 * f(n-1);

所以：f(n)=2∗f(n−1)=2∗2(n−2)....=2n−1∗f(0)=2n−1f(n)=2∗f(n−1)=2∗2(n−2)....=2n−1∗f(0)=2n−1

int FrogJump12nStepRecursive(int n)
{
    if (n == 1){
        return 1;
    }else if (n == 2){
        return 2;
    }else{
        return 2 * FrogJump12nStepRecursive(n - 1);
    }
}

demo