【背景】
回文是指正读反读均相同的字符序列，如“abba”和"abdba"均是回文，但"good"不是回文。试写一个算法判定给定字符序列是否回文。
【源码运行环境】
操作系统：Windows 10
编译环境：Dev C++(基于C99标准）
【思路】
1、利用栈的后进先出特性。
2、让字符串一半进栈。
3、将字符串后半部分与栈中元素出栈顺序依次对比。
3.1 对比出两字符不同，直接返回FALSE。
4、返回TURE。
【源码实现】
#include <stdio.h>
#define SIZE 20
/*
* 结构体：stack
* 作用： 定义一个栈，并封装相应的操作
* Author: WellLee
* Last Modified: 2018-12-13 13:02:20
*/
typedef struct stack{
char *elems;
int top;
int size;
}Stack;
/*
*方法名：InitStack
*作用：初始化栈
*参数：栈指针 s ;
*返回值：void
*Author: WellLee
*Last Modified: 2018-12-13 13:03:33
*/
void InitStack(Stack *s)
{
//s = (Stack *)malloc(sizeof(Stack));
s->elems = (char *)malloc(SIZE * sizeof(char));
s->size = SIZE;
s->top = -1;
}
/*
*方法名：Push
*作用：元素入栈
*参数：栈指针 s ，字符元素 e ;
*返回值：void
*Author: WellLee
*Last Modified: 2018-12-13 13:03:33
*/
void Push(Stack *s, char e)
{
if(s->top+1 == s->size)
{
printf("栈满\n");
return ;
}
s->elems[++s->top] = e;
}
/*
*方法名：Pop
*作用：元素出栈
*参数：栈指针 s , 字符元素指针 e;
*返回值：void
*Author: WellLee
*Last Modified: 2018-12-13 13:03:33
*/
void Pop(Stack *s, char *e)
{
if(s->top == -1)
{
printf("栈空\n");
return ;
}
*e = s->elems[s->top--];
}
/*
*方法名：PopAll
*作用：栈中所有元素出栈并输出
*参数：栈指针 s
*返回值：void
*Author: WellLee
*Last Modified: 2018-12-13 13:03:33
*/
void PopAll(Stack *s)
{
char e;
while(s->top != -1)
{
Pop(s, &e);
printf("%c ",e);
}
printf("\n");
}
/*
*方法名：isPalindrome
*作用：判断字符串是否为回文
*参数：栈指针 s , 字符元素指针 e;
*返回值：0（FALSE） 1(TRUE)
*Author: WellLee
*Last Modified: 2018-12-13 13:03:33
*/
int isPalindrome(char strings[],int length)
{
Stack s;
InitStack(&s);
int mid;
mid = length / 2;
int i;
char e;
for(i = 0; i < mid; i++)
{
Push(&s, strings[i]); // 字符串前半部分压栈操作
}
if(length % 2 != 0)
{
i = mid + 1; // 判断字符串长度是否为奇数，奇数跳过最中间的字符，直接从mid+1开始对比
}
else
{
i = mid;
}
for(; i < length; i++)
{
Pop(&s, &e);
if(strings[i] != e)
{
return 0;
}
}
return 1;
}
int main()
{
char strings[] = {'a','b','c','c','b','a','e'};
int i = isPalindrome(strings,7);
printf("%d \n", i);
return 0;
}
【总结】
在现实需求模型应用中，栈占着自己的一席之地。
【参考文献】
-
《数据结构习题解析与实验指导》.李冬梅,张琪.人民邮电出版社