严蔚敏数据结构 严蔚敏版数据结构31页算法2 12 为什么La的头结点不用释放(见图)?
下面讨论如何将两个有序链表合并为一个有序链表。 假设头指针为La和Lb的单链表分别为线性表LA和LB的存储结构,现要归并为La和Lb得到单链表Lc,按照2.1节(P20)中算法MergeList的思想,需设立3个指针pa、pb和pc,其中pa和pb分别指向La表和Lb表中当前待比较插入的结点,而pc指向Lc表中当前最后一个结点,若pa->data ≤ pb->data,则将pa所指结点链接到pc所指结点之后,否则将pb所指结点链接到pc所指结点之后。
显然,指针的初始状态为:当LA和LB为非空表时,pa和pb分别指向La和Lb表中的第一个结点,否则为空;pc指向空表Lc的头结点。 由于链表的长度为隐含的,则第一个循环执行的条件是pa和pb皆非空,当其中一个为空时,说明有一个表的元素已归并完,则只要将另外一个表的剩余表链接到pc所指结点之后即可,由此得到归并两个单链表的算法: void MergerList L(LinkList &La,LinkList &Lb,LinkList &Lc){//已知单链线性表La和Lb的元素按值非递减排列//归并La和Lb得到新的单链线性表Lc,Lc的元素也按照值非递减排列pa = La->next;pb = Lb->next;Lc = pc = La;// 用La的头结点作为Lc的头结点,pc始终指向Lc当前最后一个结点while(pa && pb){if(pa->data <= pb->data){pc->next = pa;pc = pa; // 等价于 pc = pc->nextpa = pa->next; }else{pc->next = pb;pc = pb; // 等价于 pc = pc->nextpb = pb->next;}}pc->next = pa?pa:pb;// 插入剩余段,?:是三目运算符free(Lb);// 释放Lb的头结点}// MergeList L
