LinkList Read( ); //按顺序依次读入元素,生成一个带头结点的单链表,表中元素值排列顺序与输入顺序一致,若输入-1,则创建链表结束(链表中不包含-1)。此处要求元素值按非递减顺序录入 LinkList Merge( LinkList L1, LinkList L2 ); //合并L1与L2。已知L1与L2中的元素非递减排列,要求合并后的单链表中元素也按值非递减排列。
时间: 2024-02-25 19:54:27 浏览: 97
好的,根据你的补充,我来给出完整的代码实现:
```c++
#include <stdio.h>
#include <stdlib.h>
typedef int ElemType;
typedef struct Node {
ElemType data;
struct Node *next;
} LNode, *LinkList;
LinkList Read() {
LinkList head = (LinkList) malloc(sizeof(LNode));
head->next = NULL;
LNode *tail = head;
int num;
while (scanf("%d", &num) == 1 && num != -1) {
LNode *p = (LNode*)malloc(sizeof(LNode));
p->data = num;
p->next = NULL;
tail->next = p;
tail = p;
}
return head;
}
LinkList Merge(LinkList L1, LinkList L2) {
LinkList head = (LinkList) malloc(sizeof(LNode));
head->next = NULL;
LNode *tail = head;
LNode *p1 = L1->next, *p2 = L2->next;
while (p1 && p2) {
if (p1->data <= p2->data) {
tail->next = p1;
tail = p1;
p1 = p1->next;
} else {
tail->next = p2;
tail = p2;
p2 = p2->next;
}
}
if (p1) {
tail->next = p1;
}
if (p2) {
tail->next = p2;
}
return head;
}
int main() {
LinkList L1, L2, L;
L1 = Read();
L2 = Read();
L = Merge(L1, L2);
LNode *p = L->next;
while (p) {
printf("%d ", p->data);
p = p->next;
}
return 0;
}
```
这个程序中,我们首先定义了一个单链表结构体 `LNode`,包含了节点的值和下一个节点的指针。然后,我们实现了两个函数:`Read` 和 `Merge`。
`Read` 函数按顺序依次读入元素,生成一个带头结点的单链表,表中元素值排列顺序与输入顺序一致,若输入 `-1`,则创建链表结束(链表中不包含 `-1`)。具体地,我们首先为头结点分配内存空间,然后使用一个尾指针 `tail` 指向链表的最后一个节点,逐个读入元素,为每个元素创建新节点,并把新节点插入到链表的尾部。
`Merge` 函数合并 `L1` 与 `L2`。已知 `L1` 与 `L2` 中的元素非递减排列,要求合并后的单链表中元素也按值非递减排列。具体地,我们创建一个新的链表 `head`,并使用一个尾指针 `tail` 指向链表的最后一个节点。然后,我们使用两个指针 `p1` 和 `p2` 分别指向 `L1` 和 `L2` 中的第一个节点,依次比较两个指针所指向的节点的值,将较小的节点插入到 `head` 的尾部,并将对应指针向后移动。直到其中一个指针为空,我们将另一个指针剩余的节点依次插入到 `head` 的尾部。最后,我们返回 `head`。
在 `main` 函数中,我们首先调用 `Read` 函数分别读入两个链表 `L1` 和 `L2`。然后,我们调用 `Merge` 函数将两个链表合并,并使用一个指针 `p` 遍历合并后的链表,并输出每个节点的值。
希望这段代码能够帮助到你,如果你还有其他问题,可以随时问我。
阅读全文