节点
typedef struct Node {
int data;
// 指向下个节点的指针
struct Node *next;
} Node;
操作
初始化
graph LR;
h(head) --> n((NULL))
Node* InitHead() {
NodeList head = (NodeList)malloc(sizeof(Node));
head->next = NULL;
return head;
}
创建
void InsertNode(Node* head, int data) {
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->data = data;
newNode->next = NULL;
Node* temp = head;
while(temp->next) {
temp = temp->next;
}
temp->next = newNode;
}
显示
void PrintNode(Node* head) {
Node* p = head->next;
while(p) {
printf("%d ", p->data);
p = p->next;
}
}
有序表合并
#include <stdio.h>
#include <stdlib.h>
typedef struct Lnode {
int data;
struct Lnode *next;
} Lnode, *Linklist;
// 初始化
Linklist InitHeadNode(Linklist &head) {
head = (Linklist)malloc(sizeof(Lnode));
head->next = NULL;
return head;
}
// 后插法建立链表
Linklist CreateNodeList(Linklist &head, int n) {
head->next = NULL;
Linklist p;
Linklist r = head;
for (int i = 0; i < n; i++) {
p = (Linklist)malloc(sizeof(Lnode));
scanf("%d", &p->data);
p->next = NULL;
r->next = p;
r = p;
}
return head;
}
void MergeNode(Linklist &head1, Linklist &head2, Linklist &head3) {
Linklist p1, p2, p3;
p1 = head1->next;
p2 = head2->next;
head3 = head1;
p3 = head3;
// 两个表均为到末尾, 则依次摘取
while (p1 && p2) {
// 摘取第一条链上的点
if (p1->data <= p2->data) {
// 将这个节点与head3连接上
p3->next = p1;
// p3指向p1, 为下一次连接做准备
p3 = p1;
p1 = p1->next;
} else {
// 将这个节点与head3连接上
p3->next = p2;
// p3指向p1, 为下一次连接做准备
p3 = p2;
p2 = p2->next;
}
}
// 将非空表的剩余部分与head3相连
p3->next = p1 ? p1 : p2;
free(head2);
}
void PrintNodeList(Linklist &head) {
Linklist p = head->next;
while (p) {
printf("%d ", p->data);
p = p->next;
}
}
int main() {
Linklist head1, head2, head3;
head1 = InitHeadNode(head1);
head2 = InitHeadNode(head2);
head3 = InitHeadNode(head3);
int n;
scanf("%d", &n);
head1 = CreateNodeList(head1, n);
scanf("%d", &n);
head2 = CreateNodeList(head2, n);
MergeNode(head1, head2, head3);
PrintNodeList(head3);
}