回文
回文是指正读反读均相同的字符序列,如“abba”和“abdba”均是回文,但“good”不是回文。试写一个算法判定给定的字符序列是否为回文。(提示:将一半字符入栈。)
所需的知识前提:栈
以下是顺序栈的基本算法
结构表示,初始化,销毁栈,入栈,出栈,得到栈顶元素,判断栈是否为空等算法。
#include<stdio.h>
#include<bits/stdc++.h>
using namespace std;
#include<malloc.h>
#include<string>
typedef int Status;
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define STACK_INIT_SIZE 100
#define STACK_INCREMENT 10
typedef char ElemType;
typedef struct {
ElemType *base;
ElemType *top;
int stacksize;
} SqStack;
void InitStack(SqStack &S)
{
if(!(S.base = (ElemType *)malloc(STACK_INIT_SIZE
* sizeof(ElemType))))
exit(OVERFLOW);
S.top = S.base;
S.stacksize = STACK_INIT_SIZE;
}
void DestroyStack(SqStack &S)
{
free(S.base);
S.base = NULL;
S.top = NULL;
S.stacksize = 0;
}
void Push(SqStack &S, ElemType e)
{
if(S.top - S.base >= S.stacksize) {
S.base = (ElemType *)realloc(S.base, (S.stacksize
+ STACK_INCREMENT) * sizeof(ElemType));
if(!S.base)
exit(OVERFLOW);
S.top = S.base + S.stacksize;
S.stacksize += STACK_INCREMENT;
}
*(S.top)++ = e;
}
Status Pop(SqStack &S, ElemType &e)
{
if(S.top == S.base)
return ERROR;
e = *--S.top;
return OK;
}
Status GetTop(SqStack S, ElemType &e)
{
if(S.top > S.base) {
e = *(S.top - 1);
return OK;
}
else
return ERROR;
}
Status StackEmpty(SqStack S)
{
if(S.top == S.base)
return TRUE;
else
return FALSE;
}
接下来是判断回文的关键算法
参数:传入函数的字符串的首地址和字符串的长度
//思路
将字符串的每个字符一一入st栈
因为栈的特点:后进先出 LIFO(last in first out)
所以字符串的字符全部入栈后,与原来的字符串逆序
因此仅需要将栈中的数据一一出栈与原来次序字符串的字符一一对比:
若出现不相同的状况,即返回不是回文。
若字符串的比较过半(或全部进行完)时,返回是回文。
int Palindrome(char str[], int n)
{
SqStack st;
InitStack(st);
int i;
char ch;
for (i=0;i<n;i++)
Push(st,str[i]);
i=0;
while (!StackEmpty(st))
{ Pop(st,ch);
if (ch!=str[i++])
return 0;
}
return 1;
}
下面是关于回文问题的全部代码(可直接运行)
#include<stdio.h>
#include<bits/stdc++.h>
using namespace std;
#include<malloc.h>
#include<string>
typedef int Status;
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define STACK_INIT_SIZE 100
#define STACK_INCREMENT 10
typedef char ElemType;
typedef struct {
ElemType *base;
ElemType *top;
int stacksize;
} SqStack;
void InitStack(SqStack &S)
{
if(!(S.base = (ElemType *)malloc(STACK_INIT_SIZE
* sizeof(ElemType))))
exit(OVERFLOW);
S.top = S.base;
S.stacksize = STACK_INIT_SIZE;
}
void DestroyStack(SqStack &S)
{
free(S.base);
S.base = NULL;
S.top = NULL;
S.stacksize = 0;
}
void Push(SqStack &S, ElemType e)
{
if(S.top - S.base >= S.stacksize) {
S.base = (ElemType *)realloc(S.base, (S.stacksize
+ STACK_INCREMENT) * sizeof(ElemType));
if(!S.base)
exit(OVERFLOW);
S.top = S.base + S.stacksize;
S.stacksize += STACK_INCREMENT;
}
*(S.top)++ = e;
}
Status Pop(SqStack &S, ElemType &e)
{
if(S.top == S.base)
return ERROR;
e = *--S.top;
return OK;
}
Status GetTop(SqStack S, ElemType &e)
{
if(S.top > S.base) {
e = *(S.top - 1);
return OK;
}
else
return ERROR;
}
Status StackEmpty(SqStack S)
{
if(S.top == S.base)
return TRUE;
else
return FALSE;
}
int Palindrome(char str[], int n)
{
SqStack st;
InitStack(st);
int i;
char ch;
for (i=0;i<n;i++)
Push(st,str[i]);
i=0;
while (!StackEmpty(st))
{ Pop(st,ch);
if (ch!=str[i++])
return 0;
}
return 1;
}
int main()
{
char str[100];
printf("输入一个字符串:");
gets(str);
int len=strlen(str);
;
if(Palindrome(str, len)==1)
printf("是回文\n");
else
printf("不是回文\n");
return 0;
}
运行的例子
![在这里插入图片描述](https://img-blog.csdnimg.cn/20201123142202328.png#pic_center)
![在这里插入图片描述](https://img-blog.csdnimg.cn/20201123142202336.png#pic_center)
![在这里插入图片描述](https://img-blog.csdnimg.cn/20201123142202329.png#pic_center)
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)