C语言如何用顺序栈实现回文序列判断

这篇文章主要为大家介绍了C语言如何用顺序栈来实现回文序列的判断，文中含有详细的代码示例及分析，有需要的朋友可以借鉴参考下，希望能够有所帮助

我是采用了两个栈值得比较大小判断得(可能比较浪费空间但是代码我感觉简单一点)

首先是定义一个栈的结构元素,由于是字符串类型就直接定义一个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;kdata[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 #include #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;kdata[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是否为回文序列