编写算法实现线性表(顺序存储)逆置并输出:
时间: 2024-10-12 14:14:54 浏览: 3
线性表的逆置是指将线性表中的元素从头到尾进行反转,即原来的第一个元素变成最后一个,第二个元素变成倒数第二个,以此类推。下面是一个简单的算法示例,用于逆置顺序存储的线性表:
```python
def reverse_linear_list(sll):
# 初始化两个指针,一个指向列表头部(front),另一个指向尾部(rear)
front = 0
rear = len(sll) - 1
# 当前指针未超过结束位置
while front < rear:
# 交换当前指针所指的元素
sll[front], sll[rear] = sll[rear], sll[front]
# 指针向中间移动
front += 1
rear -= 1
# 示例:
# 假设有一个顺序存储的整型线性表 [1, 2, 3, 4, 5]
sll = [1, 2, 3, 4, 5]
reverse_linear_list(sll)
# 输出逆置后的线性表:[5, 4, 3, 2, 1]
相关问题
编写算法实现线性表(顺序存储)逆置并输出
对于线性表数据结构可以通过数组、链表、栈、队列等来实现。具体实现方式可以根据不同的需求进行选择。数组实现简单,但是需要预先确定数组大小,在插入和删除时需要移动元素;链表实现方便,不需要预先确定大小,但是访问元素时需要遍历链表;栈和队列通常使用数组实现,栈只在顶部进行插入和删除,队列在队尾进行插入,在队头进行删除。
试分别以顺序表和单链表作存储结构,各编写一个实现线性表就地逆置的算法
顺序表的就地逆置(即不需要额外空间)可以使用两个指针交换的方式来实现,从头和尾开始双向推进。以下是C++的实现:
```cpp
void reverse_seq_list(SeqList& list) {
int start = 0; // 指向第一个元素
int end = list.size() - 1; // 指向最后一个元素
while (start < end) {
std::swap(list[start], list[end]);
start++;
end--;
}
}
```
这里假设`SeqList`是一个自定义的顺序表类型,包含一个`size()`函数获取当前元素个数以及`swap`方法用于交换元素。
对于单链表,由于单链表无法直接访问其前驱节点,我们需要临时创建一个新的链表来实现逆置。以下是C++的链表版本:
```cpp
struct ListNode {
int val;
ListNode* next;
ListNode(int x) : val(x), next(NULL) {}
};
void reverse_link_list(ListNode*& head) {
ListNode* prev = nullptr;
ListNode* curr = head;
ListNode* nextTemp;
while (curr != nullptr) {
nextTemp = curr->next;
curr->next = prev;
prev = curr;
curr = nextTemp;
}
head = prev;
}
```
这个函数接受链表头指针,并通过不断更新`prev`, `curr`和`nextTemp`指向,实现了链表的逆置。