解密回文——栈

绝地灬酷狼 2022-09-09 09:15 124阅读 0赞

*  栈限定为只能在一端进行插入和删除操作
 *  队列，先进先出

--------------------

栈的实现很简单，只需要一个一维数组和一个指向栈顶的变量 top 就可以了。  
通过 top 进行插入和删除操作。

*  作用  
    “xyzyx” 是一个回文字符串，所谓回文字符串就是指正读反读均相同的字符序列。  
    通过栈这个数据结构我们将很容易判断一个字符串是否为回文。

--------------------

首先，我们需要读取这行字符串，并求出这个字符串的长度。

char a[101];
    int len;
    gets(a);
    len=strlen(a);

如果一个字符串是回文的话，那么它必须是中间对称的，我们需要求中点，即：

mid=len/2-1;

接下来，就轮到栈出场了。  
我们先将 mid 之前的字符全部入栈。因为这里的栈是用来存储字符的，所以这里用来实现栈的数组类型是字符数组即 `char s[101];`,初始化栈很简单，`top=0；`，就可以了。入栈的操作就是 `top++ ；`，`s[top]=x;`,（假设需要入站的字符暂存在字符变量x中），其实可以简写为 `s[++top]=x;`.  
现在我们就来将 mid 之前的字符依次全部入栈。

for(i=0;i<=mid;i++)
    { 
        s[++top]=a[i];
    }

接下来进入判断回文的关键步骤。将当前栈中的字符依次出栈，看看是否能与 mid 之后的字符一一配对，如果都能配对则说明这个字符串是回文字符串，否则这个字符串就不是回文字符串。

for(i=mid+1;i<=len-1;i++){ 
    	if(a[i]!=s[top])
    	{ 
    		break;
    	}
    	top--;
    }
    if(top==0)
        printf("YES");
    else 
        printf("NO");

最后如果 top 的值为0，就说明栈内所有的字符都被一一匹配了，那么这个字符串就是回文字符串。完整的代码如下：

#include <iostream>
    #include <algorithm>
    #include <cstring>
    #include <cstdio>
    using namespace std;
    int main(){ 
    	char a[101],s[101];
    	int i,len,mid,next,top;
    	gets(a);
    	//读入一行字符串
    	len=strlen(a);
    	//求字符串的长度 
    	mid=len/2-1;
    	//求字符串的中点
    	top=0;
    	//栈的初始化
    	//将 mid 前的字符依次入栈
    	for(i=0;i<=mid;i++)
    	    s[++top]=a[i];
    	//判断字符串的长度是奇数还是偶数，并找出需要进行字符匹配的起始下标 
    	if(len%2==0)
    	    next=mid+1;
    	else 
    	    next=mid+2;
    	//开始匹配
    	for(i=next;i<=len-1;i++){ 
    		if(a[i]!=s[top])
    		    break;
    		top--;
    	} 
    	//如果 top 的值为0，则说明栈内所有的字符都被一一匹配了
    	if(top==0)
    	    printf("YES");
    	else 
    	    printf("NO");
    	getchar();
    	getchar(); 
    	return 0;
    }

--------------------