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;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语言顺序栈实现回文序列判断的资料请关注其它相关文章！