数据结构与算法学习笔记(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亿年,那还真是搬完地球都没了。
好了,下一章将开始队列的学习!