设有一线性表e=(e1 , e2 , … , en-1 , en),其逆线性表定义为e'=( en , en-1 , … , e2 , e1),请设计一个算法,将线性表逆置,要求逆线性表仍占用原线性表的空间,并且用顺序表和单链表两种方法来表示,写出不同的处理函数。使用C语言
时间: 2024-10-12 17:16:11 浏览: 27
chapter2习题 .ppt
在C语言中,我们可以分别使用顺序表(数组)和单链表的数据结构来实现线性表的逆置。以下是两种方法的具体处理函数:
**顺序表 (数组) 实现:**
```c
#include <stdio.h>
void reverseArray(int arr[], int n) {
int start = 0;
int end = n - 1;
while (start < end) {
// 交换起始位置和结束位置的元素
int temp = arr[start];
arr[start] = arr[end];
arr[end] = temp;
// 移动边界
start++;
end--;
}
}
// 主函数演示
int main() {
int arr[] = {1, 2, 3, 4, 5};
int n = sizeof(arr) / sizeof(arr[0]);
printf("Original array: ");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
reverseArray(arr, n);
printf("\nReversed array: ");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
return 0;
}
```
**单链表实现:**
由于单链表的特点,我们需要临时指针来帮助交换节点,这里假设`ListNode`是一个链表节点结构体,包含`data`和`next`两个成员。
```c
typedef struct ListNode {
int data;
struct ListNode* next;
} ListNode;
void reverseLinkedList(ListNode** head) {
if (*head == NULL || (*head)->next == NULL) {
return;
}
ListNode* prev = NULL;
ListNode* curr = *head;
ListNode* nextTemp = NULL;
while (curr != NULL) {
nextTemp = curr->next; // 记录当前节点的下一个节点
curr->next = prev; // 将当前节点指向prev
prev = curr; // 更新prev为curr
curr = nextTemp; // 进入下一轮循环
}
*head = prev; // 最终让头指针指向新的头节点
}
// 主函数演示
struct ListNode* createList() { /* 创建单链表函数 */ }
void printList(ListNode* head) { /* 打印链表函数 */ }
int main() {
ListNode* list = createList(); // 创建一个链表
printf("Original linked list: ");
printList(list);
reverseLinkedList(&list); // 反转链表
printf("\nReversed linked list: ");
printList(list);
return 0;
}
```
以上就是顺序表和单链表两种数据结构下逆置线性表的C语言实现。注意,对于链表,我们在操作过程中并没有创建额外的空间,而是直接改变了原有链表节点的连接关系。
阅读全文