05--栈 递归

栈

栈（Stack） 又名 堆栈 ，它是一种重要的 数据结构 。从数据结构角度看， 栈 也是 线性表 ，其特殊性在于栈的基本操作是线性表操作的子集，它是操作受限的线性表，因此，可称为限定性的数据结构。限定它仅在表尾进行插入或删除操作。 表尾称为栈顶 ，相应地， 表头称为栈底 。 栈 的基本操作除了在 栈顶进行插入和删除 外，还有栈的初始化，判空以及取栈顶元素等。

栈 顺序表实现

初始化 创建

#include "stdlib.h"
#include "math.h"
#include "time.h"
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 10 /* 存储空间初始分配量 */
// 指针指向的对象需要开辟内存空间
typedef int YZStatus;
typedef int YZSElemType; /* SElemType类型根据实际情况而定，这里假设为int */
typedef struct YZSqStack{
    int top;
    YZSElemType data[MAXSIZE];
}YZSqStack;
YZStatus InitStack(YZSqStack *S);
YZStatus CLearStack(YZSqStack *S);
YZStatus GetTop(YZSqStack S,YZSElemType *e);
YZStatus PushData(YZSqStack *S, YZSElemType e);
YZStatus PopData(YZSqStack *S, YZSElemType *e);
YZStatus StackTraverse(YZSqStack S);
//初始化
YZStatus InitStack(YZSqStack *S){
    S->top = -1;
    return OK;
}

置空

//疑问: 将栈置空,需要将顺序栈的元素都清空吗?
//不需要,只需要修改top标签就可以了.
YZStatus CLearStack(YZSqStack *S){
    S->top = -1;
    return OK;
}

栈是否为空

//判断top=-1
YZStatus isEmptyStack(YZSqStack S){
    if (S.top == -1) return TRUE;
    return FALSE;
}

栈 长度

//返回栈的长度
int returnStackLength(YZSqStack S){
    //栈从0开始计算 所以长度是top+1,当时栈为空top+1=0
    return (S.top+1);
}

获取栈顶

//获去栈顶
YZStatus GetTop(YZSqStack S,YZSElemType *e){
    if(S.top == -1){
        return ERROR;
    }else{
        *e = S.data[S.top];
    }
    return OK;
}

插入元素

//插入元素 push
YZStatus PushData(YZSqStack *S, YZSElemType e){
    //栈已满
    if (S->top == MAXSIZE-1){
        return ERROR;
    }
    S->top++;
    S->data[S->top] = e;
    
    return OK;
}

删除元素

//删除元素
YZStatus PopData(YZSqStack *S, YZSElemType *e){

    if (S->top == -1){
        return ERROR;
    }
    *e = S->data[S->top];
    S->top--;
    return OK;
}

遍历

//遍历打印 从栈顶打印
YZStatus StackTraverse(YZSqStack S){
    if (S.top == -1){
        return ERROR;
    }
    int I=0;
    while (i<=S.top) {
        printf("  %d  ",S.data[I]);
        I++;
    }
    return OK;
}

示例

YZSqStack S;
    InitStack(&S);
    for (int i=1; i<=10; i++) {
        PushData(&S, i);
    }
    StackTraverse(S);
    int a;
    PopData(&S, &a);
    printf("\n");
    printf("删除栈顶 -- %d",a);
    printf("\n");
    StackTraverse(S);

打印

  1    2    3    4    5    6    7    8    9    10  
  删除栈顶 -- 10
  1    2    3    4    5    6    7    8    9  

栈 链式实现

设计一个结构体LinkStack,里面有个top数据项,指向StackNode结构体结构

初始化 宏定义

#include <stdio.h>
#import "SqStack.h"

typedef int YZStatus;
typedef int YZSElemType; /* SElemType类型根据实际情况而定，这里假设为int */

/* 链栈结构 */
typedef struct YZStackNode
{
    YZSElemType data;
    struct YZStackNode *next;
}YZStackNode;
typedef struct YZStackNode* YZLinkStackPtr;
typedef struct YZLinkStack
{
    YZLinkStackPtr top;
    int count;
}YZLinkStack;
YZStatus InitSStack(YZLinkStack *S);
YZStatus ClearStack(YZLinkStack *S);
YZStatus StackEmpty(YZLinkStack S);
int StackLength(YZLinkStack S);
YZStatus GetSTop(YZLinkStack S,YZSElemType *e);
YZStatus Push(YZLinkStack *S, YZSElemType e);
YZStatus Pop(YZLinkStack *S,YZSElemType *e);
YZStatus StackSTraverse(YZLinkStack S);

// 构建一个空栈
YZStatus InitSStack(YZLinkStack *S){
    S->top = NULL;
    S->count = 0;
    return OK;
}

置空

YZStatus ClearStack(YZLinkStack *S){
    YZLinkStackPtr q,p;
    q = S->top;
    while (q) {
        p = q;
        q = q->next;
        free(p);
    }
    return OK;
}

判断是否为空栈

YZStatus StackEmpty(YZLinkStack S){
    if (S.count == 0){
        return TRUE;
    }
    return FALSE;
}

栈长度

int StackLength(YZLinkStack S){
    return S.count;
}

获取栈顶元素

若链栈S不为空,则用e返回栈顶元素,并返回OK ,否则返回ERROR
YZStatus GetSTop(YZLinkStack S,YZSElemType *e){
    if(S.count == 0) {
        return ERROR;
    }
    *e = S.top->data;
    return OK;
}

push

插入元素e到链栈S (成为栈顶新元素)
YZStatus Push(YZLinkStack *S, YZSElemType e){
    YZLinkStackPtr temp = (YZLinkStackPtr)malloc(sizeof(YZStackNode));
    temp->data = e;
    temp->next = S->top;
    S->top = temp;
    S->count ++;
    return OK;
}

pop

YZStatus Pop(YZLinkStack *S,YZSElemType *e){
    YZLinkStackPtr temp;
    if (StackEmpty(*S)){
        return ERROR;
    }
    *e = S->top->data;
    temp = S->top;
    S->top = S->top->next;
    S->count--;
    free(temp);
    return OK;
}

遍历

YZStatus StackSTraverse(YZLinkStack S){
    YZLinkStackPtr q;
    q = S.top;
    while (q) {
        printf(" %d ",q->data);
        q = q->next;
    }
    return OK;
}

示例

YZLinkStack SS;
   InitSStack(&SS);
   for (int i=1; i<=10; i++) {
       Push(&SS, i);
   }
   StackSTraverse(SS);
   int b;
   Pop(&SS, &b);
   printf("删除栈顶 -- %d",b);
   printf("\n");
   StackSTraverse(SS);

打印

 10  9  8  7  6  5  4  3  2  1 删除栈顶 -- 10
 9  8  7  6  5  4  3  2  1 

递归与栈

什么是递归

简单地说，就是如果在 函数中存在着调用函数本身的情况 ，这种现象就叫 递归 。

在数学上，关于递归函数的定义如下：对于某一函数 f(x) ，其定义域是集合A，那么若对于 A 集合中的某一个值 X0 ，其函数值 f(x0) 由 f(f(x0)) 决定，那么就称f(x)为递归函数。

以阶乘函数为例,如下, 在 factorial 函数中存在着 `factorial(n - 1)` 的调用，所以此函数是递归函数
 int factorial(int n){
 if (n < =1) {
 return1; 
 }
 return n * factorial(n - 1)}

进一步剖析「递归」，先有「递」再有「归」，「递」的意思是将问题拆解成子问题来解决， 子问题再拆解成子子问题，...，直到被拆解的子问题无需再拆分成更细的子问题（即可以求解），「归」是说最小的子问题解决了，那么它的上一层子问题也就解决了，上一层的子问题解决了，上上层子问题自然也就解决了,....,直到最开始的问题解决,文字说可能有点抽象，那我们就以阶层 f(6) 为例来看下它的「递」和「归」。

c763b86260c6d02682662223a5af6b1e