编写顺序表的逆置函数
时间: 2024-09-28 20:04:43 浏览: 16
编写一个逆置顺序表的函数,我们可以使用C语言为例,因为逆置操作的本质是元素的交换,所以不需要额外的空间。下面是简单的示例:
```c
#include <stdio.h>
#define MAX_SIZE 100
// 定义顺序表节点结构体
typedef struct Node {
int data;
struct Node* next;
} Node;
// 函数声明
void reverse(Node** head);
// 主函数演示逆置操作
void print_list(Node* head) {
Node* temp = head;
while (temp != NULL) {
printf("%d ", temp->data);
temp = temp->next;
}
printf("\n");
}
// 逆置顺序表的函数实现
void reverse(Node** head) {
if (*head == NULL || (*head)->next == NULL) {
return; // 如果链表为空或只有一个元素,无需逆置
}
Node* prev = NULL;
Node* current = *head;
Node* next = NULL;
while (current != NULL) {
next = current->next; // 记录当前节点的下一个节点
current->next = prev; // 更新当前节点的next指向前一个节点
prev = current; // 移动prev到当前节点
current = next; // 移动current到下一个节点
}
*head = prev; // 更新头结点为新的第一个元素
}
int main() {
Node* list = (Node*)malloc(sizeof(Node));
list->data = 1;
list->next = (Node*)malloc(sizeof(Node));
list->next->data = 2;
list->next->next = (Node*)malloc(sizeof(Node));
list->next->next->data = 3;
list->next->next->next = (Node*)malloc(sizeof(Node));
list->next->next->next->data = 4;
list->next->next->next->next = (Node*)malloc(sizeof(Node));
list->next->next->next->next->data = 5;
printf("Original List: ");
print_list(list);
reverse(&list); // 调用逆置函数
printf("Reversed List: ");
print_list(list);
free(list);
return 0;
}
```
这段代码首先创建了一个顺序表,然后调用`reverse()`函数逆置它,最后再次打印出逆置后的列表。逆置完成后,原来的列表内容会被改变。