学习笔记-数据结构-线性表（2024-04-21）

两个增序链表的减序合并

假设有两个元素值递增有序的线性表La和Lb，均以带头节点的单链表作为存储结构，编写算法将La表和Lb表合并为一个按元素值递减有序排列的线性表Lc，并要求利用原表（La和Lb表）的节点空间存放表Lc。
算法思想：首先找在表La、Lb中较小的元素，然后利用头插法，来实现Lc表中元素值递减。
变量说明：
La: 指向第一个有序单链表的头节点，该链表中的元素按递增顺序排列。
Lb: 指向第二个有序单链表的头节点，该链表中的元素同样按递增顺序排列。
Lc: 指向结果单链表的头节点，合并后的链表将按元素值递减有序排列。
pa: 在算法执行过程中，pa是一个遍历指针，用于顺序访问La链表中的节点。
pb: 类似于pa，pb是一个遍历指针，用于顺序访问Lb链表中的节点。
pc: 是一个临时指针，用于在合并过程中指向被选中要插入到Lc中的当前节点。

typedef struct Lnode
{
	datatype data;
	struct Lnode * next;
}LinkList,Lnode;
void merge_down(LinkList &La,LinkList &Lb,LinkList &Lc)
{
	Lnode *pa = La;
	Lnode *pb = Lb;
	Lnode *pc;

	// 初始化Lc的头节点
    Lc = (Lnode *)malloc(sizeof(Lnode)); // 分配内存空间给Lc的头节点
	Lc->next=NULL;
	
	// 当La或Lb任一个不为空时执行合并操作
	while( pa || pb )
	{
		if(!pb||(pa->data<=pb->data))
		{
			// 如果Lb为空或La的当前节点值小于等于Lb的当前节点值
			pc=pa;  // 选择La的当前节点
			pa=pa->next; // 移动pa指向La的下一个节点
		}
		else
		{
			// 如果La为空或Lb的当前节点值小于La的当前节点的值
			pc=pb; // 选择Lb的当前节点
			pb=pb->next; // 移动pb指向Lb的下一个节点
		}
		// 将新插入的节点指向反向连接
		pc->next=Lc->next;
		Lc->next=pc;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35