2022年阅读书单

本文目录

1. 1、栈的定义
2. 2、栈的两种存储结构及实现
3. 3、栈的应用
   1. 3.1、 递归
   2. 3.2、 四则运算表达式求值
4. THE END!

1、栈的定义

栈的定义：
限定仅在表尾（指栈顶）进行插入和删除操作的线性表。
栈的插入操作称为 入栈；
栈的删除操作称为 出栈。

栈是一种特殊的线性表，特殊之处在于其插入和删除只能在栈顶进行。

2、栈的两种存储结构及实现

栈是一种线性表，因此也有两种实现：
1、顺序存储结构：顺序栈
2、链式存储结构：链栈

#include <stdio.h>
#include <stdlib.h>

#define  MAX_DATA_SIZE  (100)
typedef int SElemType;

// 1.栈的顺序存储结构：顺序栈
typedef struct SqStack
{
    SElemType data[MAX_DATA_SIZE];
    int   top; // 表示栈顶指针
} SqStack;

// 1.1 入栈操作：将元素e插入到栈顶，栈长度加1
int Stack_push(SqStack *S, SElemType e)
{
    if (S->top == MAX_DATA_SIZE-1) //表示栈满
    {
        printf("栈满, 无法入栈！\n");
        return -1;
    }

    S->top++;
    S->data[S->top] = e;

    return 0;
}


// 1.2 出栈操作：将栈顶元素出栈，出栈元素值赋给e
int Stack_pop(SqStack *S, int *e)
{
    if (S->top == -1) //空栈
    {
        printf("空栈, 无法出栈!\n");
    }

    *e = S->data[S->top];
    S->top--;

    return 0;
}

//  1.3 顺序栈的遍历输出：从栈顶到栈底
int Stack_traverse(SqStack *S)
{
    int top_count = 0;
    if(S->top == -1)
    {
        printf("空栈！\n");
        return -1;
    }

    top_count = S->top;
    while (top_count != -1)
    {
        printf("%d\t", S->data[top_count]);
        top_count--;
    }
    printf("\n");
}

// 1.4 顺序栈的遍历输出：从栈底到栈顶
int Stack_traverse_sequence(SqStack *S)
{
    int i = 0;
    if(S->top == -1)
    {
        printf("空栈！\n");
        return -1;
    }

    while (i <= S->top)
    {
        printf("%d\t", S->data[i++]);
    }
    printf("\n");
    return 0;

}

/* 1.5 返回S的元素个数，即栈的长度 */
int Stack_length(SqStack *S)
{
    return S->top+1;
}

// 1.6 顺序栈获取栈顶元素
int Stack_getTop(SqStack *S, int *e)
{
    if (S->top == -1)
    {
        printf("空栈!\n");
    }

    *e = S->data[S->top];

    return 0;
}

/*  1.7 构造一个空栈S */
int InitStack(SqStack *S)
{
    /* S.data=(SElemType *)malloc(MAXSIZE*sizeof(SElemType)); */
    S->top=-1;
    return 0;
}

/*  1.8 把S置为空栈 */
int ClearStack(SqStack *S)
{
    S->top=-1;
    return 0;
}


// 2. 栈的链式存储结构：链栈
typedef struct StackNode
{
    SElemType data;
    struct StackNode *next;
} StackNode, *LinkStackPtr;

typedef struct LinkStack
{
    LinkStackPtr top;
    int count;
} LinkStack;

// 2.1 链栈的入栈操作
int LinkStack_push(LinkStack *LS, SElemType e)
{
    LinkStackPtr s = (LinkStackPtr)malloc(sizeof(StackNode));
    if (NULL == s)
    {
        printf("malloc failed!\n");
        return -1;
    }

    s->data = e;
    s->next = LS->top;
    LS->top = s;
    LS->count++;

    return 0;
}

// 2.2 链栈的出栈操作
int LinkStack_pop(LinkStack *LS, SElemType *e)
{
    LinkStackPtr p;

    if (LS->top == -1)
    {
        printf("空栈!\n");
        return -1;
    }

    *e = LS->top->data;  // 先取出出栈元素值
    p = LS->top;         // 将栈顶结点赋值给p
    LS->top = LS->top->next;
    free(p);

    LS->count--;
    return 0;
}


// 栈的应用：Fibonacci数列
int Fbi(int i)
{
    if (i < 2)
    {
        return i == 0 ? 0 : 1;
    }
    return Fbi(i-1) + Fbi(i-2);
}
int main(int argc, char *argv[])
{
    int e = 0;

    // 1、初始化空栈
    SqStack SS;
    //SS.top = -1;  
    InitStack(&SS);
    Stack_traverse_sequence(&SS);

    // 2、入栈操作
    Stack_push(&SS, 1);
    Stack_traverse_sequence(&SS);

    Stack_push(&SS, 2);
    Stack_traverse_sequence(&SS);

    Stack_push(&SS, 3);
    Stack_traverse_sequence(&SS);

    // 3、获取栈顶元素
    Stack_getTop(&SS, &e);
    printf("栈顶元素: %d\n", e);


    // 4、出栈操作
    Stack_pop(&SS, &e);
    printf("出栈元素: %d\n", e);
    Stack_traverse_sequence(&SS);

    Stack_pop(&SS, &e);
    printf("出栈元素: %d\n", e);

    Stack_traverse_sequence(&SS);

    Stack_pop(&SS, &e);
    printf("出栈元素: %d\n", e);

    Stack_traverse_sequence(&SS);

    // 5、栈的应用：递归实现
    printf("%d", Fbi(5));
    return 0;
}

3、栈的应用

3.1、 递归

// 栈的应用：Fibonacci数列
int Fbi(int i)
{
    if (i < 2)
    {
        return i == 0 ? 0 : 1;
    }
    return Fbi(i-1) + Fbi(i-2);
}

3.2、 四则运算表达式求值

1、后缀表达式求值
2、中缀表示式转后缀表达式

---

THE END!

---

本博文只能阅读，谢绝转载，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 2963033731@qq.com