将顺序表中的元素就地逆置(即不使用额外的顺序表)。其中,顺序表从1号下标的数组元素开始存放数据;创建顺序表时,以-1表示输入数据结束。 函数接口定义: int reverse(SeqList *L); L:顺序表指针 若L为空表返回0,否则返回顺序表长度。
时间: 2024-10-23 12:05:28 浏览: 25
顺序表的就地逆置
在C语言中,你可以通过双指针技巧实现顺序表的就地逆置,这种方法不需要额外的空间。下面是相应的`reverse`函数实现:
```c
#include <stdio.h>
typedef struct {
int data; // 顺序列表中的数据元素
struct SeqList* next; // 指向下一个元素的指针
} SeqList;
// 初始化顺序表的头结点
SeqList* CreateSeqList() {
SeqList* head = (SeqList*)malloc(sizeof(SeqList));
head->data = -1;
head->next = NULL;
return head;
}
// 反转顺序表
int reverse(SeqList** L) {
if (*L == NULL) { // 空表,直接返回0
return 0;
}
SeqList* prev = NULL; // 预备指针,初始为NULL
SeqList* current = *L; // 当前指针,初始指向头结点
SeqList* next = NULL; // 指向下一个节点
while (current != NULL) { // 当当前指针非空
next = current->next; // 获取下一个节点
current->next = prev; // 将当前节点的next指向前一个节点
prev = current; // 更新前一个节点
current = next; // 更新当前节点
}
*L = prev; // 顺序表头部已反转,更新头结点
return (*L == NULL) ? 0 : 1; // 返回顺序表长度,如果头指针仍为NULL,则为空表
}
// 示例用法
int main() {
SeqList* L = CreateSeqList();
Insert(L, 1); // 添加元素1
Insert(L, 2); // 添加元素2
int length = reverse(&L); // 逆置顺序表
if (length > 0) {
int index = 1;
SeqList* temp = L;
while (temp != NULL) {
printf("Element at position %d: %d\n", index++, temp->data);
temp = temp->next;
}
}
return 0;
}
阅读全文