先前写了括号匹配,这里再给出两个栈的应用-回文数和进制转换;
首先是回文数,回文数理解起来很简单的,但是--我写的太麻烦了。。。。。。
看来还是需要加强自己的代码质量,这里权当复习。。。
回文数在我的理解中就是中心对称的字符串(assa)。所以如果想用栈来解决回文数的判断我的理解是一半字符串入栈,然后依次和后面一半的字符串进行逐字符的比较。
但是要注意对于字符串长度为奇数的字符串,要把中间的字符去掉(如asdfgfdsa)。这里我用了两个栈来判断回文数。
void Judge(SqStack s,SqStack tmps) { char ch; int flag=0,temp; while((ch = getchar())!='\n') { Push(&s,ch); } flag = StackLength(&s); temp = flag; while(flag != (temp/2)) { Push(&tmps,GetTop(&s)); Pop(&s); flag--; } if(temp%2==1)Pop(&tmps); while(flag) { if(GetTop(&s) != GetTop(&tmps))break; flag--; } if(flag == 0)printf("这是回文字符.\n"); else printf("这不是回文字符.\n"); }
这个代码是越看越挫啊。。。。。
不管这些还有一个基于栈的应用:进制转换。
进制转换的内容很多,但是可以触类旁通,这里写写十进制转换为其它进制的程序:
十进制转各进制
要将十进制转为各进制的方式,只需除以各进制的权值,取得其余数,第一次的余数当个位数,第二次余数当十位数,
其余依此类推,直到被除数小于权值,最后的被除数当最高位数。
一、十进制转二进制
如:55转为二进制
2|55
27――1 个位
13――1 第二位
6――1 第三位
3――0 第四位
1――1 第五位
最后被除数1为第七位,即得110111
二、十进制转八进制
如:5621转为八进制
8|5621
702 ―― 5 第一位(个位)
87 ―― 6 第二位
10 ―― 7 第三位
1 ―― 2 第四位
最后得八进制数:127658
三、十进制数十六进制
如:76521转为十六进制
16|76521
4726 ――5 第一位(个位)
295 ――6 第二位
18 ――6 第三位
1 ―― 2 第四位
最后得1276516
有了这些进制转换的代码不难写:
void SysConvert(int number,SqStack s,int newscale) //number转换的数字(10进制) s进制转换利用的栈,newscale转换后新的进制。 { while(number) { Push(&s,number%newscale); number /= newscale; } StackTraverse(&s); }
进制转换之后的数字就保存在栈里面,遍历栈即可。
下面给出完整代码:
#include <stdio.h> #include <stdlib.h> #define STACK_INIT_SIZE 100 //栈空间的初始分配量 #define STACKINCREMENT 10 //存储空间的分配增量 typedef char SElemType; typedef struct { SElemType *base; //在构造栈之前和销毁栈之后,base的数值为NULL SElemType *top; //栈顶指针 int stacksize; //显示栈当前的容量 }SqStack; //创建一个空栈 int InitStack(SqStack *s); //销毁栈 int DestroyStack(SqStack *s); //清空栈 int ClearStack(SqStack *s); //判断栈是否为空栈 int StackEmpty(SqStack *s); //计算栈的长度 int StackLength(SqStack *s); //获取栈顶元素 int GetTop(SqStack *s); //将一个元素推入站内 int Push(SqStack *s,SElemType data); //将一个元素退出栈 int Pop(SqStack *s); //对于栈内的每一个元素调用函数 int StackTraverse(SqStack *s); int InitStack(SqStack *s) { s->base = (SElemType *)malloc(sizeof(SElemType)*STACK_INIT_SIZE); //为栈分配基础空间 if(!s->base)exit(1); //分配失败的话就退出 s->top = s->base; //栈顶指针指向栈底 s->stacksize = STACK_INIT_SIZE; //初始化栈的大小 return 1; } int Push(SqStack *s,SElemType data) { if(s->top-s->base >= s->stacksize) //如果栈的空间不够再增加 { s->base = (SElemType *)realloc(s->base,(s->stacksize + STACKINCREMENT)*sizeof(SElemType)); if(!s->base)exit(1); //在原来空间的基础上额外增加空间 s->top = s->base + s->stacksize; //栈顶指针加1 s->stacksize += STACKINCREMENT; //栈大小增加 } *s->top++ = data; //元素入栈,栈顶指针加1 return 1; //入栈成功 } int Pop(SqStack *s) { if(s->base == s->top) return 0; //如果栈为空栈返回出栈失败 (*--s->top); //栈顶指针减1 return 1; //出栈成功 } int GetTop(SqStack *s) { if(s->base == s->top) return 0; //空栈返回失败 return *(s->top-1); //返回栈顶元素 } int StackLength(SqStack *s) { SElemType *tmp = s->top; //设置临时变量和栈顶指针相同 int flag = 0; while(tmp != s->base) //栈顶指针逐个减1知道栈底 { flag ++; tmp--; } return flag; //返回栈的长度 } int DestroyStack(SqStack *s) { free(s->base); //释放掉栈的分配空间 s->base = s->top = NULL; //栈顶和栈底指向NULL s->stacksize = 0; //栈的长度还原为0 return 1; } int ClearStack(SqStack *s) { s->top = s->base; //栈清空最方便只需要将栈顶指针指向栈底 return 1; } int StackTraverse(SqStack *s) { SElemType *tmp = (s->top-1); if(s->top == s->base)return 0; while(1) { printf("%d",*tmp); if(tmp == s->base) break; //这个地方我刚刚犯了一个错误就是忽视栈底base指针指向的区域也有一个数据 tmp--; } return 1; } void Judge(SqStack s,SqStack tmps) { char ch; int flag=0,temp; while((ch = getchar())!='\n') { Push(&s,ch); } flag = StackLength(&s); temp = flag; while(flag != (temp/2)) { Push(&tmps,GetTop(&s)); Pop(&s); flag--; } if(temp%2==1)Pop(&tmps); while(flag) { if(GetTop(&s) != GetTop(&tmps))break; flag--; } if(flag == 0)printf("这是回文字符.\n"); else printf("这不是回文字符.\n"); } void SysConvert(int number,SqStack s,int newscale) //number转换的数字(10进制) s进制转换利用的栈,newscale转换后新的进制。 { while(number) { Push(&s,number%newscale); number /= newscale; } StackTraverse(&s); } int main() { SqStack s; int number,newscale; InitStack(&s); scanf("%d%d",&number,&newscale); SysConvert(number,s,newscale); ClearStack(&s); DestroyStack(&s); return 0; }