请用C语言回答1.将两个递增有序的顺序表A,B进行合并,合并后仍然有序,并求中位数。 2.给定一个升序排列的顺序表,请删除重复出现的元素,使每个元素只出现一次,并输出新的顺序表的信息。注:删除元素后顺序表保持升序
时间: 2024-10-07 22:02:56 浏览: 50
1. 合并两个递增有序的顺序表A和B,可以使用双指针法。首先创建一个新的空表C作为结果。然后设置两个指针i和j分别指向A和B的头部。比较两个指针所指的元素,将较小的那个添加到结果表C,并移动对应的指针。当其中一个列表遍历完后,直接将另一个列表剩余的部分复制到结果表C的剩余位置。最后,对结果表C进行遍历即可得到排序后的顺序表。
```c
typedef struct Node {
int data;
struct Node* next;
} Node;
void merge(Node** A, Node** B) {
Node* C = NULL;
Node* tail = NULL;
while (*A && *B) {
if ((*A)->data <= (*B)->data) {
if (C == NULL) {
C = *A;
tail = C;
} else {
tail->next = *A;
tail = tail->next;
}
(*A)++;
} else {
if (C == NULL) {
C = *B;
tail = C;
} else {
tail->next = *B;
tail = tail->next;
}
(*B)++;
}
}
// 如果有一个列表还有剩余元素,直接添加到结果表尾部
while (*A) {
tail->next = *A;
tail = tail->next;
(*A)++;
}
while (*B) {
tail->next = *B;
tail = tail->next;
(*B)++;
}
}
double findMedianSortedList(Node* list) {
int length = 0;
Node* slow = list, *fast = list;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
length++;
}
if (length % 2 != 0) {
return (double)(slow->data);
} else {
return (double)(slow->data + fast->data) / 2.0;
}
}
```
2. 删除升序顺序表中的重复元素,可以先创建一个新的空表D,然后遍历原表。对于每个元素,如果它比当前表头大或为空,则将其添加到新表D;若相等则跳过。遍历完成后,新表D即为去重后的顺序表。
```c
void removeDuplicates(Node** A) {
Node* D = NULL;
Node* D_tail = NULL;
for (Node* temp = *A; temp != NULL; temp = temp->next) {
if (D_tail && D_tail->data < temp->data) {
D_tail->next = temp;
D_tail = D_tail->next;
} else if (D == NULL || temp->data > D_tail->data) {
if (D != NULL) {
D_tail->next = temp;
} else {
D = temp;
}
D_tail = temp;
}
}
*A = D;
}
```
阅读全文