数据结构回文判断程序实现
时间: 2024-11-11 17:13:59 浏览: 24
数据结构回文判断.doc
数据结构回文判断程序通常是指检查一个序列(如字符串、数字数组等)是否从前往后读和从后往前读都一样,即它是一个回文。以下是几种常见算法的实现:
1. **双指针法**(对于字符串):创建两个指针,一个指向开始位置,另一个指向结束位置。然后依次比较两个指针所指的字符,如果相等则向中间移动,直到两个指针相遇或交叉。如果在整个过程中所有字符都匹配,则该序列是回文。
```python
def is_palindrome(s):
left, right = 0, len(s) - 1
while left < right:
if s[left] != s[right]:
return False
left += 1
right -= 1
return True
```
2. **栈**(对于任意序列):将序列的一半压入栈中,然后遍历另一半并与栈顶元素逐个对比。如果都相等则是回文,如果不等则不是。
```python
def is_palindrome(lst):
stack = lst[:len(lst)//2]
for i in range(len(lst)//2, len(lst)):
if stack.pop() != lst[i]:
return False
return not stack
```
3. **递归**(对于字符串):如果字符串的第一个和最后一个字符相同,并且剩下的子串也是回文,那么原串就是回文。
```python
def is_palindrome_rec(s):
if len(s) <= 1:
return True
return s[0] == s[-1] and is_palindrome_rec(s[1:-1])
```
阅读全文