数据结构与算法学习笔记（C语言）
链栈
在开始链栈的学习之前，我们先实现一下上一篇文章中提到的检查括号匹配的小程序，鉴于水平有限，本人就随便写一下代码好了，目标仅限于对功能的实现。
/*用顺序栈这种数据结构，实现一个检查括号匹配的小程序*//*头文件*/#include <stdio.h>#include <stdlib.h>#include <stdbool.h>/*定义类型*/typedef char SElemType;typedef int Status;/*定义状态码*/#define OK 1#define ERROR 0#define OVERFLOW -2/*顺序栈的C定义*/#define INIT_SIZE 100 //存储空间初始分配量#define INCREMENT 10 //存储空间分配增量typedef struct {SElemType *base; //存储空间基址SElemType *top;//栈顶指针int stacksize; //当前已分配的存储空间}SqStack;/*所需要的函数原型的声明*/void Match_Check(); /*匹配检查函数*/Status InitStack(SqStack *S); /*初始化栈函数*/bool Is_Empty(SqStack); /*判断栈中是否有元素*/Status GetTop(SqStack S, SElemType *e); /*取栈顶元素函数*/Status Push(SqStack *S, SElemType e); /*压栈函数*/Status Pop(SqStack *S, SElemType *e);/*弹栈函数*/int main(void){/*在主函数中调用匹配检查函数*/Match_Check();return 0;} /*匹配检查函数的实现*//*请用英文输入法输入文本以及括号，所写的程序中用来检查的括号是英文括号*/void Match_Check(){SqStack S; SElemType e; bool Is_Match = true; int ch;/*没有字符输入的时候，先假定是括号是匹配的*/InitStack(&S);printf("请输入一段文本：\n");while ((ch = getchar()) != EOF && Is_Match) {/*从括号失配开始，后面的字符都不需要再读取了。在大多数UNIX和Linux系统中，在一行开始处按下Ctrl+D会传输文件结尾信号。Windows系统把一行开始处的Ctrl+Z识别为文件结尾信号。*/if (ch == '{' || ch == '[' || ch == '(') {/*如果是左括号，则压栈*/Push(&S, ch);}if (ch == '}') {if(GetTop(S, &e) && e == '{')/*如果栈里面有元素并且栈顶元素是 { ，弹出 { */Pop(&S, &e);}else Is_Match = false;}if (ch == ']') {if(GetTop(S, &e) && e == '[')/*如果栈里面有元素并且栈顶元素是 [ ，弹出 [ */Pop(&S, &e);}else Is_Match = false;}if (ch == ')') {if(GetTop(S, &e) && e == '(')/*如果栈里面有元素并且栈顶元素是 ( ，弹出 ( */Pop(&S, &e);}else Is_Match = false;}}//while/*while 循环结束表示文本输入结束或者括号失配了，括号匹配的话，栈里面一定没有元素并且Is_Match == true*/if (Is_Empty && Is_Match) {printf("你所输入的文本括号匹配！");}else {printf("你所输入的文本括号不匹配！");}}/*初始化栈函数的实现*/Status InitStack(SqStack *S) {S->base = (SElemType *)malloc(INIT_SIZE * sizeof(SElemType));if (!S->base) exit(OVERFLOW);S->top = S->base;S->stacksize = INIT_SIZE;return OK;}/*判断栈是否为空的函数*/bool Is_Empty(SqStack S){if (S.top == S.base) return true;else return false;}/*取栈顶元素函数的实现*/Status GetTop(SqStack S, SElemType *e) {if (S.top == S.base) return ERROR;/*栈空*/*e = *(S.top - 1);return OK;}/*压栈函数的实现*/Status Push(SqStack *S, SElemType e) {/*如果栈满*/if (S->top - S->base == S->stacksize) {/*这里涉及指针相减，在连续空间上，指针相减得到存储单元的个数，是int型，有疑问的翻下书再复习一下指针部分*/ SElemType *new_base;new_base = (SElemType *)realloc(S->base, (S->stacksize + INCREMENT) * sizeof(SElemType));if(!newbase) exit(OVERFLOW);/*将栈底和栈顶指针移到新动到的存储空间来*/S->base = new_base;S->top = S->base + S->stacksize;S->stacksize += INCREMENT;}*S->top++ = e;return OK;}/*弹栈函数的实现*/Status Pop(SqStack *S, SElemType *e){if (S->top == S->base) return ERROR;*e = *--S->top;return OK;}
运行结果展示如下，在Win 10环境下，IDE用的是Dev C++，因为自己的电脑暂时没带，就凑合使用以下无需配置操作简单的Dev C++做演示
括号匹配：
括号不匹配：
好了，接下来进入正题：
由于顺序栈的初始空间空间固定大小，在元素满了之后需要重新申请空间，在元素很少时又有很多空间的浪费，链栈可以解决这个问题。
链栈是指用链式存储结构实现的栈，通常用单链表表示。
下面是链栈的C语言描述
typedef struct SNode {SElemType data;struct SNode *next;}SNode, *LinkStack;
老规矩，将LinkStack作为栈顶指针，其他结点指针用SNode *加以区分
1.栈的初始化
/*因为栈的插入删除操作只在栈顶进行，栈不需要设头结点*/Status InitStack(LinkStack *S){S = NULL;return OK;}
2.入栈
/*动态申请节点空间，所以没有栈满一说*/Status Push(LinkStack *S, SElemType e){SNode *p;p = (SNode *)malloc(sizeof(SNode));if (!p) exit(OVERFLOW);/*插入节点，让e成为新的栈顶元素*/p->data = e;p->next = *S;*S = p;return OK;}
3.出栈
Status Pop(LinkStack *S, SElemType *e){SNode *p;if (*S == NULL) return ERROR;/*栈空*/*e = (*S)->data;/*让p指向栈顶元素空间，以备释放*/p = *S;*S = (*S)->next;free(p);return OK;}
4.取栈顶元素
Status GetTop(LinkStack S, SElemType *e){if (S = NULL) return ERROR;*e = S->data;return OK;}
剩下的一些比如清空、销毁栈、遍历栈里面的元素和链表的操作几乎一样，自己实现就可以了
那接下来说一下栈的应用：其实我们写的程序中的函数调用就是栈的逻辑，将连续调用（这个词不准确，但一时不知道用什么词，就是a调用b，b又调用c，c又…）的函数依次压栈，直到最后一个被调用的函数入栈，再依次出栈。函数的返回过程和调用过程相反，正好与栈的特性吻合。
一个很常用的例子就是递归函数了，函数通过不停地调用自身，直到到达递归基，就是递归结束的条件满足，函数开始依次返回。
比如有趣的汉诺塔传说：在世界中心贝拿勒斯（在印度北部）的圣庙里，一块黄铜板上插着三根宝石针。印度教的主神梵天在创造世界的时候，在其中一根针上从下到上地穿好了由大到小的64片金片，这就是所谓的汉诺塔。不论白天黑夜，总有一个僧侣在按照下面的法则移动这些金片：一次只移动一片，不管在哪根针上，小片必须在大片上面。僧侣们预言，当所有的金片都从梵天穿好的那根针上移到另外一根针上时，世界就将在一声霹雳中消灭，而梵塔、庙宇和众生也都将同归于尽。
那我们如果累了，想毁灭宇宙，就得会解决这道问题吧。
假设是要将金片从A柱子移动到C柱子上，要保证最大的一片在最下面，那肯定另外63片先借助C柱子放到B柱子上（63片的Hanoi问题） 然后将A柱子上剩下的最大的一片搬到C柱子上去。 再将B柱子上上面的63片借助A移动到C柱子上去，那不是又和最开始A需要借助B把64片金片放到C上的问题一样的吗（63片的Hanoi问题）
自己先尝试写下代码解决这个问题，没思路再参考下面的。
代码实现如下：
#include <stdio.h>int count = 0; /*全局变量计步骤*//*函数声明*/void Hanoi(char x, char y, char z, int n);void move(int i, char a, char b);int main(void){int n = 64;/*呃，移动64片步骤太多，可以先设置个移动20片，看看要多少步*/Hanoi('A', 'B', 'C', n);return 0;}/*搬金片动作的实现*/void move(int i, char a, char b){printf("%d: 搬第%d片, %c->%c\n", ++count, i, a, b);}/*汉诺塔问题的递归解决方法*/void Hanoi(char x, char y, char z, int n){if (n == 1) move(1, x, z);else {Hanoi(x, z, y, n - 1);move(n, x, z);Hanoi(y, x, z, n - 1);}}
上面的运行结果是n = 20的，我天价2000多的电脑运行了10分钟才得到的结果，需要1048575步。
由数学推导易知 n 片金片需要搬动 2^n - 1 次，那么搬完64片，需要 2^64 - 1 步，反正我的电脑是得不到结果了。
需要 18,446,744,073,709,551,615 步！假设搬动一片需要 2 秒，那么昼夜不停完成移动需要427,007,964,669,203天！需要1,169,884,834,710年！
科学家分析地球已经诞生了46亿年，还将存在50亿年，而汉诺塔问题的金片搬完要1169亿年，那还真是搬完地球都没了。
好了，下一章将开始队列的学习！
