解密回文——栈

一、关于栈的介绍

栈是一种后进先出的数据结构,它限定为只能在一端进行插入和删除操作。

比如说有一个小桶,小桶的直径只能放一个小球,我们现在在小桶内依次放入2、1、3号小球。假如你现在需要拿出2号小球,那就必须先将3号小球拿出,再拿出1号小球,最后才能将2号小球拿出来。在刚才取小球的过程中,我们最先放进去的小球最后才能拿出来,最后放进去的小球却可以最先拿出来。

栈的实现需要一个一维数组和一个指向栈顶的变量top,通过top来对栈进行插入和删除的操作。

通过栈这个数据结构我们将很容易判断一个字符串是否为回文。什么是回文?就是指正读反读均相同的字符序列,如“记书记” “abcba”均是回文。

二、解密回文的步骤

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

    char a[101];
    int ,en;
    gets(a);  //读入一行字符串
    len=strlen(a);  //求字符串的长度

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

    mid=len/2-1; //求字符串的中点 

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

    for(i=0;i<=mid;i++)  //将mid前的字符依次入栈 
        s[++top]=a[i]; 

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

    /*开始匹配*/
    for(i=next;i<=len-1;i++)
    {
        if(a[i]!=s[top])
            break;
        top--;
    } 
    /*如果top的值为0,则说明栈内所有的字符都被一一匹配了*/
    if(top==0)
        printf("YES");
    else
        printf("NO");

5,最后如果top的值为0,就说明栈内所有的字符都被一一匹配了,那么这个字符串就是回文字符串。

三、完整代码

#include<stdio.h>
#include<string.h>
int main()
{
    char a[101],s[101];
    int i,len,mid,next,top;
    gets(a);  //读入一行字符串
    len=strlen(a);  //求字符串的长度
    mid=len/2-1; //求字符串的中点 
    top=0;  //栈的初始化
    for(i=0;i<=mid;i++)  //将mid前的字符依次入栈 
        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");

    return 0; 
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 用OpenGL进行曲线、曲面的绘制

    Zoctopus
  • 《算法图解》第七章笔记_迪杰斯特拉算法

    Zoctopus
  • 【总结】牛客职播第十期:程盟有你,way来可期

    Zoctopus
  • 如何学python-第三课 基础字符串操作

    在上一篇文章中,我们学习了有关变量和输出的一些基础知识。大家应该还记得在上一篇文章中出现的字符串类型(string)吧!说白了,string类型其实就是一堆单词...

    用户1631416
  • C语言中的字符处理

    C语言中,提供的字符为 char,通常情况下,char 为 unsigned char,即无符号字符,表示单个字符,对于多个字符(字符串),C没有提供相应的类型...

    鲁郭大侠
  • 京东版“Dash Button”问世,支持一键购买快消品

    镁客网
  • IT人如何打造个性化的个人网站(在线简历)

    众所周知,IT行业人员在求职时,如果拥有自己的技术博客和个人网站多少是可以加些分的,因为这也是IT人的技术证明之一。内容丰富的技术博客就不必多少了,往往技术博客...

    朝雨忆轻尘
  • 高级架构进阶之HashMap源码就该这么学

    “当然用过,HashMap是一种<key,value>的存储结构,能够快速将key的数据put方式存储起来,然后很快的通过get取出来”,然后说“HashMap...

    技术zhai
  • “安利”一款debug神器:在AI面前,bug都不是事儿

    你可以这么想,如果在开发和测试阶段没有发现 bug 问题,那么 bug 将会随着产品发布,在生产环节触发,其后果将视情况而定。

    AI科技大本营
  • 制作滑动条菜单,如何延时处理滑动效果,避免动画卡顿

        前几日在利用JQuery做菜单滑动标记这个效果的时候,最后发现滑动条在我用鼠标快速滑动的时候,会出现滑动条延迟滑动,并且有卡顿的现象,相当影响体验感受。...

    八哥

扫码关注云+社区

领取腾讯云代金券