回文是指正读和反读均相同的字符序列,如”abba”和”abdba”均是回文,但”good”不是回文,试用c语言写一算法利用栈判定给定的字符序列是否为回文。(提示:将一半字符入栈)
时间: 2023-10-30 10:05:35 浏览: 39
```c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_SIZE 100
//定义栈结构体
typedef struct Stack{
char data[MAX_SIZE];
int top;
}Stack;
//初始化栈
void initStack(Stack *s){
s->top = -1;
}
//判断栈是否为空
int isEmpty(Stack *s){
return s->top == -1;
}
//判断栈是否已满
int isFull(Stack *s){
return s->top == MAX_SIZE-1;
}
//入栈
void push(Stack *s, char ch){
if(isFull(s)){
printf("The stack is full!\n");
return;
}
s->data[++s->top] = ch;
}
//出栈
char pop(Stack *s){
if(isEmpty(s)){
printf("The stack is empty!\n");
return '\0';
}
return s->data[s->top--];
}
//判断字符串是否为回文
int isPalindrome(char *str){
int len = strlen(str);
Stack s;
initStack(&s);
int i;
for(i = 0; i < len/2; i++){
push(&s, str[i]); //前一半字符入栈
}
if(len % 2 == 1) i++; //如果字符串长度为奇数,中间字符不入栈
while(str[i] != '\0'){
if(str[i] != pop(&s)) return 0; //与栈中字符比较,不相等则不是回文
i++;
}
return 1;
}
int main(){
char str[MAX_SIZE];
printf("Please input a string: ");
scanf("%s", str);
if(isPalindrome(str)){
printf("%s is a palindrome.\n", str);
}
else{
printf("%s is not a palindrome.\n", str);
}
return 0;
}
```