学习笔记-数据结构-线性表（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;
}
}

原文地址：https://blog.csdn.net/qq_41755616/article/details/138050814

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！