首页分别用顺序表和单链表作为存储结构，设计高效的算法，实现将线性表(a0,a1,…,an-1).就地逆置，写C语言程序

分别用顺序表和单链表作为存储结构，设计高效的算法，实现将线性表(a0,a1,…,an-1).就地逆置，写C语言程序

时间: 2024-10-07 22:07:46 浏览: 77

对于顺序表（数组），由于数组元素是连续存储的，我们可以通过两个指针i和j从两端开始遍历并交换元素，直到它们相遇。这是一种简单的就地逆置方法，不需要额外的空间复杂度。 ```c #include <stdio.h> void reverseArray(int arr[], int n) { int i = 0, j = n - 1; while (i < j) { // 交换arr[i] 和 arr[j] int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; // 移动指针 i++; j--; } } int main() { int arr[] = {1, 2, 3, 4, 5}; int n = sizeof(arr) / sizeof(arr[0]); printf("Before reverse: "); for (int i = 0; i < n; i++) { printf("%d ", arr[i]); } reverseArray(arr, n); printf("\nAfter reverse: "); for (int i = 0; i < n; i++) { printf("%d ", arr[i]); } return 0; } ``` 对于单链表（动态数组），因为节点之间的位置不是固定的，我们需要遍历整个链表，对每个节点进行翻转，并更新指向下一个节点的指针。这需要临时保存下一个节点的位置，然后更新当前节点的next指针。 ```c typedef struct Node { int data; struct Node* next; } Node; void reverseList(Node** head) { if (*head == NULL || (*head)->next == NULL) { return; // 如果链表为空或只有一个节点，无需反转 } Node* prev = NULL, *curr = *head, *temp = NULL; while (curr != NULL) { // 保存当前节点的下一个节点 temp = curr->next; // 翻转当前节点 curr->next = prev; // 更新指针 prev = curr; curr = temp; } *head = prev; // 新头节点就是原尾节点 } int main() { Node* head = createLinkedList(); // 假设已创建链表 // ...其他链表操作... reverseList(&head); // 打印反转后的链表 printLinkedList(head); return 0; } ```

阅读全文