数据结构线性表的就地逆置
时间: 2024-03-07 13:44:16 浏览: 57
线性表的就地逆置是指在不使用额外的空间的情况下,将线性表中的元素逆序排列。具体实现可以通过交换首尾元素、依次向中间靠拢的方式进行。
以下是一种常见的就地逆置算法:
1. 定义两个指针,分别指向线性表的首元素和尾元素。
2. 交换两个指针所指向的元素,并将两个指针分别向中间移动一位。
3. 重复步骤2,直到两个指针相遇或者交叉。
4. 线性表的元素就地逆置完成。
这种算法的时间复杂度为O(n),其中n为线性表的长度。
相关问题
请你以顺序表作为存储结构,写一个实现线性表就地逆置的算法
好的,以下是实现线性表就地逆置的算法:
```
void reverseList(int *list, int length) {
int temp;
for (int i = 0; i < length / 2; i++) {
temp = list[i];
list[i] = list[length - i - 1];
list[length - i - 1] = temp;
}
}
```
这个算法使用了顺序表作为存储结构,通过交换表头和表尾、表头+1和表尾-1、表头+2和表尾-2……的元素来实现就地逆置。
(线性表)试编写算法将线性表就地逆置,以链式存储结构实现。 PS:输入以eof结束
好的,下面是将链式存储结构的线性表就地逆置的算法实现:
```python
class Node:
def __init__(self, data=None):
self.data = data
self.next = None
def reverse_list(head):
if head is None or head.next is None:
return head
pre = None
cur = head
while cur:
next_node = cur.next
cur.next = pre
pre = cur
cur = next_node
return pre
# 测试代码
def print_list(head):
cur = head
while cur:
print(cur.data, end=" ")
cur = cur.next
print()
def create_list():
head = Node()
cur = head
while True:
try:
data = input()
if data == "eof":
break
new_node = Node(data)
cur.next = new_node
cur = new_node
except EOFError:
break
return head.next
if __name__ == "__main__":
head = create_list()
print("原始链表:")
print_list(head)
new_head = reverse_list(head)
print("逆置后的链表:")
print_list(new_head)
```
你可以逐行输入线性表的元素,使用 "eof" 结束输入。然后算法会输出原始链表和逆置后的链表。
请注意,这只是其中一种实现方式,还有其他方法可以实现线性表的就地逆置。