带头结点的单链表归并操作

  • 2017-09-18 15:20:45
  • 1,029 次阅读
  • 稿源:天马行空

单链表是链表中比较重要的形式之一,它不仅支持动态分配,而且插入与删除元素不需要移动元素的位置,只需改变指针的指示的位置就能完成结点的插入与删除操作。而单链表的归并操作相对比较难一点点,首先是指针比较多,比较搞脑汁,其次是没有图例或者是动画演示,真的很难搞清楚程序是怎么执行的。下面是C程序写的单链表归并操作与图例演示:
(1)单链表归并图片展示:
①三个单链表的初始状态如下图:

linkList
②一个循环的单链表执行状态如下图:

linkListTwo
③最终执行状态如下图:

linkListThree(2)C语言的单链表归并程序如下所示:
void mergeList(LNode *La,LNode *Lb,LNode *&Lc)
{

LNode *pa=La->next;//pa用来跟踪La的最小值结点
LNode *pb=Lb->next;//pb用来跟踪Lb的最小值结点
LNode *rc; //rc始终指向Lc的终端结点
Lc=La; //用La的头结点作为Lc的头结点
Lc->next=NULL; //从La链表中取下头结点作为新链表的头
free(Lb); //Lb的头结点已无用,则释放掉
rc=Lc; //rc指向Lc,此时头结点也是终端结点

while(pa!=NULL&&pb!NULL)//当pa与pb都不空时,选取pa与pb所指结点中的较小者插入Lc的尾部
{

if(pa->data<=pb->data)
{
rc->next=pa;pa=pa->next;
rc=rc->next;
}
else
{
rc->next=pb;pb=pb->next;
rc=rc->next;
}

}
rc->next=NULL;
/*以下两个if语句将还有剩余结点的链表链接到Lc的尾部*/
if(pa!=NULL) rc->next=pa;
if(pb!=NULL) rc->next=pb;

}

喜欢 0

文章评论 (0)

表情

大眼 可爱 大笑 坏笑 害羞 发怒 折磨 快哭了 大哭 白眼 晕 流汗 困 腼腆 惊讶 憨笑 色 得意 骷髅 囧 睡觉 眨眼 亲亲 疑问 闭嘴 难过 淡定 抗议 鄙视 猪头