当前位置：首页 > news >正文

【数据结构与算法】判定给定的字符向量是否为回文算法

news 2025/9/16 22:09:01

题目：

Qestion: 试写一个算法判定给定的字符向量是否为回文。

回文解释: 回文是指正读反读均相同的字符序列，如“abba”和“abdba”均是回文，但“good”不是回文。

主要思路：

因为数据要求不是很严格并且是一个比较简单的题，因此偷懒采用了用线性表来表示栈，用的是数组来存储字符串，定义了一个结构体Strack，里面含有栈顶指针top和栈内元素个数cnt。
创建一个字符数组char c [max]，用scanf将用户输入的字符串传入该char数组。
统计用户输入字符串的长度，结束标志位char c [i] = '\0'，得出该字符串的总长度。
*将用户输入的字符串一半入栈（需要分字符个数位为奇还是为偶两种情况）。
*栈内元素依次与从char c [max] 中间字符的下一位（这里也要分奇偶）开始比较判读该字符串是否为回文字符串。

数据结构与定义：

#define max 20struct Stack
{int cnt; // 统计栈中共有几个元素int top; // 指向栈顶元素的指针
};
Stack A; //字符串的栈
char stack[max];//数组实现的栈的存储结构
char c[max];//用于存放用户输入的字符串

主要操作函数：

//置空栈，默认若栈中没有元素则栈顶指针指向char数组第一位
void InitStack(Stack &S)
{S.top = 0;
}//计算用户输入字符串的长度
int StringLength(char a[])
{int length = 0;for (int i = 0; i < max; i++){if (a[i] != '\0') // 当遇到`\0`时循环结束{length++;}elsebreak;}return length;
}//将用户输入的字符串一半存入栈中，其中char a[]为用于存放用户输入的字符串数组
//S为栈结构体包括栈顶指针和栈内元素个数，length为字符串的长度，char stack为
//用数组实现的栈，用于存储入栈的元素
void PushStringInStack(char a[], Stack &S, int length, char stack[])
{if (length % 2 == 0) //若字符的个数为偶数，则将其一半入栈{for (int i = 0; i < length / 2; i++){stack[S.top] = a[i]; // 将a[i]压入栈中S.top = i + 1; //栈顶指针上移S.cnt++; //栈内元素个数加一}}else // 若字符的个数为奇数，则将其总数减一的一半个数的字符入栈{for (int i = 0; i < (length - 1) / 2; i++){stack[S.top] = a[i]; // 同上S.top = i + 1;S.cnt++;}}
}//判断用户输入的字符是否为回文串
bool IsPalindrome(char stack[], Stack S, char a[], int length)
{int j;if (length % 2 == 0)j = length / 2;elsej = (length / 2) + 1;for (int i = (S.top - 1); i > 0; i--){if (stack[i] == a[j]){j = j + 1;}elsereturn false;}return true;
}

图解：

初始化链表

判断是否为回文字符串

完整代码

#include <stdio.h>
#include <string.h>
#define max 20
struct Stack
{int cnt; int top; 
};bool IsPalindrome(char stack[], Stack S, char a[], int length)
{int j;//j 也可以用S.cnt替代，这只是另一种表示方法，结果是一样的if (length % 2 == 0)j = length / 2;elsej = (length / 2) + 1;for (int i = (S.top - 1); i > 0; i--){if (stack[i] == a[j]){j = j + 1;}elsereturn false;}return true;
}int StringLength(char a[])
{int length = 0;for (int i = 0; i < max; i++){if (a[i] != '\0'){length++;}elsebreak;}return length;
}void InitStack(Stack &S)
{S.top = 0;
}void PushStringInStack(char a[], Stack &S, int length, char stack[])
{if (length % 2 == 0){for (int i = 0; i < length / 2; i++){stack[i] = a[i];S.top = i + 1;S.cnt++;}}else{for (int i = 0; i < (length - 1) / 2; i++){stack[i] = a[i];S.top = i + 1;S.cnt++;}}
}int main()
{Stack A;char stack[max];InitStack(A);char c[max];scanf("%s", c);int length = StringLength(c);PushStringInStack(c, A, length, stack);if (IsPalindrome(stack, A, c, length))printf("true");elseprintf("false");return 0;
}