C语言顺序栈实现回文序列判断与字符过滤

周末不加班

发布时间：2026-10-16| 4人浏览过

原创

在C语言数据结构学习中，利用顺序栈解决回文判断是一个经典案例。本例通过一个包含特殊分隔符的逻辑，实现了将一段输入流拆分为前后两部分，并校验后半部分是否为前半部分的逆序排列。文章提供了完整的结构体定义、栈操作方法以及核心比较算法的代码实现。

设计思路与目标

本方案的核心目标是：读取一串包含分隔符的输入，将其视为两个连续的序列，并判断这两个序列是否构成“回文”关系（即后一串是前一串的倒序）。为了实现这一目标，我们需要：

存储空间：使用动态分配的堆内存模拟一个空栈，用于暂存数据。
标记机制：引入特定字符作为序列结束的标志，从而在逻辑上划分两个需要比较的对象。
核心算法：利用栈“先进后出”的特性，通过遍历和对比两个栈的数据，验证其对称性。

准备条件与结构体定义

首先，我们需要定义顺序栈的结构。由于处理的是字符串片段，栈内部直接使用字符数组存储。

#include<stdio.h>
#include<stdlib.h>
#define MAX_SIZE 100
typedef struct stack
{
    char data[MAX_SIZE];      //储存字符串// 
    int top;                  //记录栈顶// 
}SeqStack;

第1步：初始化栈

目的是让新创建的栈处于就绪状态。这里采用将 top 指针设为 -1 的方式，表示栈为空。

void Initstack(SeqStack *S)   //初始化栈,让top指向栈顶// 
{
	S->top=-1;
}

第2步：执行压栈操作

该函数负责将字符 x 存入栈中。需要注意检查栈满情况，防止越界。

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掉分配的空间// 
}

在该函数中，通过计算 S->top/2 找到中间点，并将后半段数据复制到新栈 p 中。随后通过双重递减索引 S->top 和 p->top 进行逐位比对，若发现不等则跳出循环，最后根据计数器 j 的值输出结果。完成所有判定后，务必调用 free(p) 释放动态分配的堆内存。

主函数实现与运行环境搭建

以下 main 函数演示了如何组装上述功能模块，并在控制台进行交互测试。

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;
}

在输入阶段，程序会持续接收字符，遇到符号 @ 时增加一个状态标记 m。这允许我们在同一个输入流中连续键入两段文本。当输入结束时，直接调用前文定义的 Pop 函数即可完成复杂的逻辑判断。