实现两个有序顺序表的合并算法 将顺序表1(值为{1,3,5,7,9,15,21})和顺序表2(值为{2,4,6,8,10,18})合并为一个顺序表3(值为{1,2,3,4,5,6,7,8,9,10,15,18,21})
时间: 2024-10-14 12:12:28 浏览: 0
为了合并两个已排序的顺序表(也称为数组),我们可以采用双指针的方法。这里是一个简单的C语言实现:
```c
#include <stdio.h>
#include <stdlib.h>
// 顺序表结构体
typedef struct {
int *data;
size_t size;
size_t capacity;
} SeqList;
// 合并两个有序顺序表
SeqList* merge_sorted_lists(SeqList *list1, SeqList *list2) {
SeqList *merged_list = create_seq_list(list1->capacity + list2->capacity);
// 指向两个列表的当前索引
size_t idx1 = 0, idx2 = 0;
while (idx1 < list1->size && idx2 < list2->size) {
if (list1->data[idx1] <= list2->data[idx2]) {
merged_list->data[idx1 + idx2] = list1->data[idx1];
idx1++;
} else {
merged_list->data[idx1 + idx2] = list2->data[idx2];
idx2++;
}
}
// 将剩余元素追加到结果列表中
while (idx1 < list1->size) {
merged_list->data[idx1 + idx2] = list1->data[idx1];
idx1++;
}
while (idx2 < list2->size) {
merged_list->data[idx1 + idx2] = list2->data[idx2];
idx2++;
}
merged_list->size = idx1 + idx2;
return merged_list;
}
// 创建顺序表
SeqList* create_seq_list(size_t capacity) {
SeqList *list = (SeqList*) malloc(sizeof(SeqList));
list->data = (int*) malloc(capacity * sizeof(int));
list->size = 0;
list->capacity = capacity;
return list;
}
// 打印顺序表
void print_seq_list(SeqList *list) {
for (size_t i = 0; i < list->size; i++) {
printf("%d ", list->data[i]);
}
printf("\n");
}
int main() {
// 创建并填充两个有序顺序表
SeqList list1 = { .data = {1, 3, 5, 7, 9, 15, 21}, .size = 7, .capacity = 7 };
SeqList list2 = { .data = {2, 4, 6, 8, 10, 18}, .size = 6, .capacity = 6 };
// 合并两个顺序表
SeqList *merged_list = merge_sorted_lists(&list1, &list2);
// 打印合并后的顺序表
print_seq_list(merged_list);
// 清理内存
free(merged_list->data);
free(merged_list);
return 0;
}
```
这个程序首先创建一个新的顺序表 `merged_list`,然后遍历两个输入列表,比较当前元素并将其较小的一个放入 `merged_list`。最后,如果其中一个列表还有剩余元素,则将剩余部分追加到 `merged_list`。