栈 - stack

1. 顺序存储

优点：

• 实现简单

缺点：

• 长度有限

1.1 结构定义

#define MAXSIZE 20

typedef int Status;
typedef int SElemType;

typedef struct
{
    SElemType data[MAXSIZE];
    int top;
} SqStack;

1.2 函数实现

// 1.构建一个空栈S
Status InitStack(SqStack *S) {
    if (!S) return ERROR;
    S->top = -1;
    return OK;
}

// 2.将栈置空
Status ClearStack(SqStack *S) {
    if (!S) return ERROR;
    S->top = -1;
    return OK;
}

// 3.判断顺序栈是否为空;
Status StackEmpty(SqStack S) {
    if (S.top == -1)
        return TRUE;
    else
        return FALSE;
}

// 4.返回栈的长度
int StackLength(SqStack S) {
    return S.top + 1;
}

// 5.获取栈顶元素
Status GetTop(SqStack S, SElemType *e) {
    if (S.top == -1)
        return ERROR;
    else
        *e = S.data[S.top];
    return OK;
}

// 6.压栈
Status Push(SqStack *S, SElemType e) {
    if (!S || S->top == MAXSIZE -1) return ERROR;
    S->data[++S->top] = e;
    return OK;
}

// 7.出栈
Status Pop(SqStack *S,SElemType *e) {
    if (!S || S->top == -1) return ERROR;
    *e = S->data[S->top--];
    return OK;
}

// 8.从栈底到栈顶依次对栈中的每个元素打印
Status StackTraverse(SqStack S) {
    int i = S.top;
    while (i >= 0) {
        printf("%d ",S.data[i--]);
    }
    printf("\n");
    return OK;
}
// 输出
顺序栈的表示与实现!
顺序栈中元素为: 
9 8 7 6 5 4 3 2 1 
弹出栈顶元素为: 9
8 7 6 5 4 3 2 1 
是否为空栈: 0
栈顶元素: 8 
栈长度: 8
是否已经清空栈 1, 栈长度为: 0

2. 链式存储

优点：

• 长度无限(只要内存够)

缺点：

• 实现复杂
• 节点的内存管理

2.1 结构定义

typedef int Status;
typedef int SElemType;

/* 链栈结构 */
typedef struct StackNode
{
    SElemType data;
    struct StackNode *next;
} StackNode, *StackNodePtr;

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

2.2 函数实现

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

// 2.栈S置为空栈
Status ClearStack(LinkStack *S){
    if (!S) return ERROR;
    StackNodePtr p, q;
    p = S->top;
    while (p) {
        q = p;
        p = p->next;
        free(q);
    }
    S->top = NULL;
    S->count = 0;
    return OK;
}

// 3.栈S是否为空栈
Status StackEmpty(LinkStack S) {
    if (!S.top)
        return TRUE;
    else
        return FALSE;
    /*
     if (S.count == 0)
         return TRUE;
     else
         return FALSE;
     */
}

// 4.栈S的长度
int StackLength(LinkStack S) {
    return S.count;
}

// 5.返回栈顶元素
Status GetTop(LinkStack S, SElemType *e) {
    if (!S.top)
        return ERROR;
    else
        *e = S.top->data;
    return OK;
}

// 6.压栈
Status Push(LinkStack *S, SElemType e) {
    if (!S) return ERROR;
    StackNodePtr node = (StackNodePtr)malloc(sizeof(StackNode));
    node->data = e;
    node->next = S->top; // 头插法
    S->top = node; // 更换头结点
    S->count++;
    return OK;
}

// 7.出栈
Status Pop(LinkStack *S, SElemType *e) {
    if (!S || !S->top) return ERROR;
    *e = S->top->data;
    StackNodePtr node = S->top;
    S->top = S->top->next; // 更换头结点
    free(node);
    S->count--;
    return OK;
}

// 8.遍历栈
Status StackTraverse(LinkStack S) {
    StackNodePtr node;
    node = S.top;
    while (node) {
        printf("%d ",node->data);
        node = node->next;
    }
    printf("\n");
    return OK;
}

int main(int argc, const char * argv[]) {
    printf("链栈定义与实现\n");
    int j;
    LinkStack S;
    int e;
    if (InitStack(&S) == OK)
        for (j=1; j <= 10; j++) Push(&S,j);
    printf("栈中元素依次为:\n");
    StackTraverse(S);
    Pop(&S, &e);
    printf("弹出的栈顶元素: %d\n",e);
    StackTraverse(S);
    printf("栈空否: %d (1:空 0:否)\n",StackEmpty(S));
    GetTop(S,&e);
    printf("栈顶元素: %d 栈的长度为%d\n",e,StackLength(S));
    ClearStack(&S);
    printf("清空栈后，栈空否: %d (1:空 0:否)\n",StackEmpty(S));
    return 0;
}
// 输出
链栈定义与实现
栈中元素依次为:
10 9 8 7 6 5 4 3 2 1 
弹出的栈顶元素: 10
9 8 7 6 5 4 3 2 1 
栈空否: 0 (1:空 0:否)
栈顶元素: 9 栈的长度为9
清空栈后，栈空否: 1 (1:空 0:否)

3. 递归

递归方法就是直接或者间接的调用自己，它可以将一些发杂问题简化。

递归在下列方法中经常会用到：

• 定义是递归的。

  如斐波拉契数列、阶乘等。

• 数据结构是递归的。

  数据结构本身具有递归性，如链表、树等。

• 问题的解法是递归的。

  有一类问题，虽然问题本身没有明显的递归结构，但采用递归求解比迭代求解更简单。如汉诺塔问题、八皇后问题、迷宫问题。

在求解时，我们会先求解，然后再进一步分解进行求解，这种求解叫做分治法。

使用分治法需要满足3个条件：

• 能将一个问题转换成一个小问题，新问题和原问题的解法相同或类同。

  不同的只是被处理的对象，并且这些处理更小且变化是有规律的。

• 可以通过上述转换而使得问题简化。

• 必须有一个明确的递归出口，或成为递归边界。

4. 汉诺塔问题

在经典汉诺塔问题中，有 3 根柱子及 N 个不同大小的穿孔圆盘，盘子可以滑入任意一根柱子。一开始，所有盘子自上而下按升序依次套在第一根柱子上(即每一个盘子只能放在更大的盘子上面)。

移动圆盘时受到以下限制:

• 每次只能移动一个盘子；
• 盘子只能从柱子顶端滑出移到下一根柱子；
• 盘子只能叠在比它大的盘子上。

4.1 解决思路

我们使用递归来解决：

• 时，直接把盘子从A移动到C就行了。(递归边界)
• 时：
  • 先把个盘子从A移动到B；(子问题，递归)
  • 将最大的盘子从A移动到C；
  • 再将B上个盘子移动到C。(子问题，递归)

4.2 用栈解决

static void move(LinkStack *A, LinkStack *B, LinkStack *C, int n) {
    if (n == 1) {
        int elem;
        Pop(A, &elem);
        Push(C, elem);
    } else {
          // 把栈A中n-1个盘子放到栈B
        move(A, C, B, n - 1);
        // A栈出栈放入C栈
        int elem;
        Pop(A, &elem);
        Push(C, elem);
          // 把栈B中n-1个盘子放到栈C
        move(B, A, C, n - 1);
    }
}

void hanoi(LinkStack *A, LinkStack *B, LinkStack *C) {
    move(A, B, C, StackLength(*A));
}

int main(int argc, const char * argv[]) {
    int n = 5;
    LinkStack A, B, C;
    InitStack(&A);
    InitStack(&B);
    InitStack(&C);
    for (int i = n; i > 0; i--) {
        Push(&A, i);
    }
    printf("原始栈A：");
    StackTraverse(A);
    printf("原始栈C：");
    StackTraverse(C);

    hanoi(&A, &B, &C);

    printf("移动后栈A：");
    StackTraverse(A);
    printf("移动后栈C：");
    StackTraverse(C);

    return 0;
}
// 输出
原始栈A：1 2 3 4 5 
原始栈C：
移动后栈A：
移动后栈C：1 2 3 4 5 

4.3 移动过程

void hanoi2(char *A, char *B, char *C, int n) {
    if (n == 1) {
        printf("move %s to %s\n", A, C);
    } else {
        hanoi2(A, C, B, n - 1);
        printf("move %s to %s\n", A, C);
        hanoi2(B, A, C, n - 1);
    }
}
int main(int argc, const char * argv[]) {
    hanoi2("a", "b", "c", 3);
    return 0;
}
// 输出
move a to c
move a to b
move c to b
move a to c
move b to a
move b to c
move a to c

汉诺塔问题