C语言如何用顺序栈实现回文序列判断
程序员文章站
2022-03-07 12:12:30
我是采用了两个栈值得比较大小判断得(可能比较浪费空间但是代码我感觉简单一点)首先是定义一个栈的结构元素,由于是字符串类型就直接定义一个char的数组就可以:.typedef struct stack{...
我是采用了两个栈值得比较大小判断得(可能比较浪费空间但是代码我感觉简单一点)
首先是定义一个栈的结构元素,由于是字符串类型就直接定义一个char的数组就可以:.
typedef struct stack { char data[max_size]; //储存字符串// int top; //记录栈顶// }seqstack;
下来就是初始化,我这里是用的耿国华老师的方法就直接给一个top元素指向栈顶,传入的指针地址:.
void initstack(seqstack *s) //初始化栈,让top指向栈顶// { s->top=-1; }
下面就是创建顺序栈了,元素只要没满就一直可以入住:
int push(seqstack *s,char x) //压栈,只要top小于max_size-1就可以继续入栈// { if(s->top<=max_size-1) { s->top++; s->data[s->top]=x; }else{ return -1;; } }
下面是核心函数,操作实现回文序列的判断,我注释的比较清楚直接看就可以了:
void pop(seqstack *s) //出栈操作,也是最主要的操作// { seqstack *p; p=(seqstack*)malloc(sizeof(seqstack)); //建立一个新的空栈,由于是指针类型要分配动态地址// initstack(p); //给新的栈进行初始化// int i=s->top/2; //i用来分割两个字符串,将第二个字符串赋给新的空栈// int j=i-1; //j用来记录除了@之外的其他字符数量大小// while(s->top!=i) //开始对空栈进行赋值,对原来的栈开始清空(清空一般大小)// { p->top++; p->data[p->top]=s->data[s->top]; s->top--; } s->top=s->top-2; //让原来的栈直接指向数字,跨过了字符@// for(int k=0;k<i-1;k++) //循环次数由i-1决定,也就是出去@字符之后的其他需要比较的字符// { if(s->data[s->top]==p->data[p->top]) //由于栈的特点先进后出,所以新栈的存储顺序和去掉@字符之后的旧栈的存储顺序是一样的,所以这里直接比较// { j--; //j是定义需要比较字符的大小,只要两个栈的元素ascll相等j就减一,如果全部相等j为0,该字符串就是互为回文序列// } s->top--; //两个top指针向下值// p->top--; if(j==0) //判断// { printf("两个字符串互为回文序列!"); } } if(j!=0) { printf("两个字符串不互为回文序列!"); } free(p); //free掉分配的空间// }
下面附上整个代码:
#include<stdio.h> #include<stdlib.h> #define max_size 100 typedef struct stack { char data[max_size]; //储存字符串// int top; //记录栈顶// }seqstack; void initstack(seqstack *s) //初始化栈,让top指向栈顶// { s->top=-1; } int push(seqstack *s,char x) //压栈,只要top小于max_size-1就可以继续入栈// { if(s->top<=max_size-1) { s->top++; s->data[s->top]=x; }else{ return -1;; } } void pop(seqstack *s) //出栈操作,也是最主要的操作// { seqstack *p; p=(seqstack*)malloc(sizeof(seqstack)); //建立一个新的空栈,由于是指针类型要分配动态地址// initstack(p); //给新的栈进行初始化// int i=s->top/2; //i用来分割两个字符串,将第二个字符串赋给新的空栈// int j=i-1; //j用来记录除了@之外的其他字符数量大小// while(s->top!=i) //开始对空栈进行赋值,对原来的栈开始清空(清空一般大小)// { p->top++; p->data[p->top]=s->data[s->top]; s->top--; } s->top=s->top-2; //让原来的栈直接指向数字,跨过了字符@// for(int k=0;k<i-1;k++) //循环次数由i-1决定,也就是出去@字符之后的其他需要比较的字符// { if(s->data[s->top]==p->data[p->top]) //由于栈的特点先进后出,所以新栈的存储顺序和去掉@字符之后的旧栈的存储顺序是一样的,所以这里直接比较// { j--; //j是定义需要比较字符的大小,只要两个栈的元素ascll相等j就减一,如果全部相等j为0,该字符串就是互为回文序列// } s->top--; //两个top指针向下值// p->top--; if(j==0) //判断// { printf("两个字符串互为回文序列!"); } } if(j!=0) { printf("两个字符串不互为回文序列!"); } free(p); //free掉分配的空间// } int main() { seqstack s; char x; int m=0; initstack(&s); printf("请输入第一串字符\n"); while(m!=2) //因为只需要输入两个字符串的判断,判断条件为m!=2// { scanf("%c",&x); if(x=='@') //输入@后表明第一个字符串结束// { m++; if(m==1) { printf("请输入第二串字符:\n"); } } push(&s,x); } pop(&s); return 0; }
下面加一个例子:
判断3+1与1+3是否为回文序列
以上就是c语言如何用顺序栈实现回文序列判断的详细内容,更多关于c语言顺序栈实现回文序列判断的资料请关注其它相关文章!