数据结构 —— 利用栈实现回文判断

迈不过友情╰ 2022-05-11 15:40 166阅读 0赞

**一、先理解什么是栈、什么是回文**

栈的性质：先进后出或后进先出的特性，栈的实现也很简单，只需要一个一维数组和一个指向栈顶的变量top就可以了。我们通过变量top来对栈进行插入和删除操作。

回文：回文字符串就是从前向后看个从后向前看都是一样的字符串。例如，dad，abcba，sees都是回文串，但是”hello“就不是的。检查回文字符串的一个方法就是用栈。

**二、算法实现的两个代码**

#include<stdio.h>
    #include<stack>
    #include<string.h>
    using namespace std;
    int main()
    {
        stack <char>s;
        char str[100];
        scanf("%s",&str);
        int len=strlen(str);
        int mid=len/2; //求字符串的中点（需要入栈的字符串）
    
        int i;
        int flag=1;
    
        //将mid前的字符依次入栈
        for( i=0; i<mid; i++)
        {
            s.push(str[i]);
        }
    
        //判断字符串的长度的是奇数还是偶数，并找出需要进行字符匹配的起始下标
        if(len%2==1)
        {
            i+=1;
        }
    
        //开始匹配
        while(!s.empty())
        {
            int temp=s.top();
            if(temp!=str[i])
            {
                flag=0;
                break;
            }
            else
            {
                i+=1;
                s.pop();
            }
        }
    
        if(!flag)
        {
            printf("no!!");
        }
        else
            printf("yes!!");
    
        return 0;
    }

#include<stdio.h>
    #include<string.h>
    int main()
    {
        char a[100],s[100];
        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;
    }