构造两个长度均为5的有序线性表LA和LB,将有序表LA和LB合并为一个有序线性表LC 其中LC表中允许存在相同的元素。C语言源代码
时间: 2024-11-29 18:37:23 浏览: 1
数据结构实验报告1-线性表-两个有序表的归并-实验内容及要求.docx
在C语言中,合并两个长度均为5的有序线性表可以使用迭代或者递归的方式。这里给出一个简单的迭代方法来合并它们:
```c
#include <stdio.h>
#include <stdlib.h> // 包含malloc函数,用于动态内存分配
// 定义结构体表示线性表的一个节点
typedef struct Node {
int value; // 节点的值
struct Node* next; // 指向下一个节点的指针
} Node;
// 合并两个有序链表
Node* mergeSortedLists(Node* LA, Node* LB) {
// 创建一个新的链表LC作为结果
Node* LC = NULL; // 结果头指针
Node* temp = NULL; // 助手指针
// 当两个链表都不为空时
while (LA != NULL && LB != NULL) {
// 如果LA的当前元素小于等于LB的当前元素
if (LA->value <= LB->value) {
// 把LA的当前元素添加到LC
if (LC == NULL) {
LC = temp = LA;
} else {
temp->next = LA;
temp = temp->next;
}
LA = LA->next;
} else {
// 把LB的当前元素添加到LC
if (LC == NULL) {
LC = temp = LB;
} else {
temp->next = LB;
temp = temp->next;
}
LB = LB->next;
}
}
// 如果LA还有剩余元素,把他们直接添加到LC
while (LA != NULL) {
temp->next = LA;
temp = temp->next;
LA = LA->next;
}
// 如果LB还有剩余元素,把他们添加到LC的尾部
while (LB != NULL) {
temp->next = LB;
temp = temp->next;
LB = LB->next;
}
return LC;
}
// 打印链表
void printList(Node* node) {
while (node != NULL) {
printf("%d ", node->value);
node = node->next;
}
printf("\n");
}
int main() {
// 假设已经初始化好LA和LB两个有序链表
Node LA_data[] = {1, 3, 5, 7, 9};
Node LA_head = createLinkedList(LA_data, 5); // 创建LA链表头部
Node LB_data[] = {2, 4, 6, 8, 10};
Node LB_head = createLinkedList(LB_data, 5); // 创建LB链表头部
// 合并两个链表
Node* LC_head = mergeSortedLists(LA_head, LB_head);
// 打印LC
printf("合并后的有序链表LC:\n");
printList(LC_head);
return 0;
}
// 助手函数,用于创建单链表
Node* createLinkedList(int data[], int size) {
Node* head = NULL;
for (int i = 0; i < size; ++i) {
Node* newNode = (Node*) malloc(sizeof(Node));
newNode->value = data[i];
newNode->next = NULL;
if (head == NULL) {
head = newNode;
} else {
Node* current = head;
while (current->next != NULL) {
current = current->next;
}
current->next = newNode;
}
}
return head;
}
```
这段代码首先定义了一个`mergeSortedLists`函数,它接收两个链表的头指针作为输入,然后按照顺序合并这两个链表。`printList`函数则用于打印链表的内容。
在`main`函数中,假设LA和LB已分别初始化为给定的有序数据,然后调用`mergeSortedLists`函数得到合并后的链表LC,最后打印出LC的内容。
阅读全文