MENU

利用堆栈判断回文

• October 28, 2020 • 队列和堆栈

编写函数,判断一个字符序列是否是回文。回文是指一个字符序列以中间字符为基准,两边字符相同,如字符序列“ABCDEDCBA”就是回文,而字符序列“ABCDEDBAC”不是回文。


题目分析:

有中间字符,那么就说明这个字符串必须有奇数个字符。中间字符的左边与右边必须相同,如果此题不要求使用堆栈解决的话,我们又可以利用1+到99快捷思想,将第一个字符与最后一个字符比较,第二个字符与倒数第二个字符比较,如果出现不一致情况,则不是回文,直到中间只剩一个字符,就判断是回文。

但是我们学习数据结构,就是为了能够使用它,在这里我们必须用堆栈来解决这个问题。堆栈的特性是什么?1.栈顶操作;2.先进后出。如果把字符串第一个字符先放进堆栈,那么这个将会是最后一个出栈,而如果我们将中间字符的前一个字符最后进栈,那么它会第一个出来。所以我们可以利用堆栈的先进后出特性来搞定这个算法。

思路:遍历字符串字符,挨个将字符放进堆栈,直到遍历到中间字符则停止放入堆栈。然后继续遍历中间字符后面的字符序列,与此同时,每遍历一个字符,我们从堆栈里面取一个字符出来和它比较,如果相同则继续遍历,继续取出,如果不同,则判断不是回文,直到字符串遍历到末尾最后一个字符并且此时堆栈为空,则判断是回文。


考点:

1.堆栈进栈、出栈操作


代码实现:

说明:此代码利用顺序存储结构,包含一个头文件"Stack.h",以及一个源文件"main.c"
Stack.h 部分:

#pragma once
#include<stdio.h>
#include<string.h>
#define MAX 26                     //设置顺序表存储空间
typedef char dataType;             //数据类型为char
//定义结构体
typedef struct stack
{
    char stack[MAX];               //用来存储字符
    int top;                       //存储的字符个数
} Stack;
//初始化
void stackInitiate(Stack *stack)
{
    stack->top = 0;                //存储的字符个数为0
}
//判断是否空栈
bool stackNotEmpty(Stack *stack)
{
    if (stack->top <= 0)
        return false;
    else
        return true;
}
//进栈操作,成功返1,否则返0
int stackPush(Stack *stack, dataType x)
{
    if (stack->top >= MAX)
    {
        printf("栈满,无法入栈!\n");
        return 0;
    }
    else
    {
        stack->stack[stack->top] = x;  //将栈顶元素置为x
        stack->top++;                  //存放个数+1
        return 1;
    }
}
//出栈操作,成功返1,否则返0,将出栈的数据由data带出
int stackPop(Stack *stack, dataType *data)
{
    if (stack->top <= 0)
    {
        printf("栈空,无法出栈!\n");
        return 0;
    }
    else
    {
        stack->top--;                  //存放个数-1
        *data = stack->stack[stack->top]; //出栈的数据赋给data指向的位置
        return 1;
    }
}
//判断是否回文,返回true/false
bool isPalindrome(dataType *array)
{
    Stack stack;
    Stack *p;
    p = &stack;
    stackInitiate(p);                  //创建及初始化堆栈
    int i = 0;
    int len = strlen(array);           //计算字符串长度
    if (len % 2 == 0)                  //如果长度为偶数,肯定不是回文
        return false;
    dataType t;
    for (; i < len / 2; i++)           //将中间字符前面的字符全部依次进栈
        stackPush(p, array[i]);
    i++;                               //遍历时跳过中间字符
    for (; i < len; i++)
    {
        stackPop(p, &t);               //将堆栈里的数据出栈,赋值给t
        if (t != array[i])             //挨个与中间字符后面的数比对
            return false;
    }
    return true;
}

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

main.c 部分

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include "Stack.h"                    //导入头文件
int main()
{
    dataType charArray[50];
    printf("请输入一个字符串:");
    gets_s(charArray);                //从键盘获取一个字符串
    if (isPalindrome(charArray))
        printf("是回文!\n");
    else
        printf("不是回文!\n");
    system("pause");                  //暂停,控制闪退
    return 0;
}

运行结果:


(1)长度为偶数,不是回文


(2)长度为奇数,但不是回文


(3)长度为奇数,且是回文

img



代码编译器:Visual Studio 2017
ok

Last Modified: November 12, 2020
Archives QR Code Tip
QR Code for this page
Tipping QR Code