|
|
EDA365欢迎您登录！
您需要 登录 才可以下载或查看，没有帐号？注册
x
假设头指针为La和Lb的单链表分别为线性表LA和LB的存储结构，现要归并La和Lb得到单链表Lc，按照算法MergeList的思想，需设立3个指针pa、pb和pc，其中pa和pb分别指向La表和Lb表中当前待比较插入的结点，而pc指向Lc表中当前最后一个结点，若pa->data≤pb->data，则将pa所指向结点之后，否则将pb所指向结点链接到pc所指结点之后。显然，指针的初始状态为：当LA和LB为非空表时，pa和pb分别指向La和Lb表中第一个结点，否则为空；pc指向空表Lc中的头结点。由于链表的长度为隐含的，则第一个循环执行的条件时pa和pb皆非空，当其中一个为空时，说明有一个表的元素已归并完，则只要将另一个表的剩余段链接在pc所指结点之后即可。由此得到归并两个单链表的算法。
3 o6 f" O2 J- vvoidMergeList_L(LinkList &La,LinkList &Lb,LinkList &Lc,){
% Z* p' f) @' y8 e! L9 `( k//已知单链线性表La和Lb的元素按值非递减排列。) {/ i" B, b+ x4 p& t
//归并La和Lb得到新的单链线性表Lc，Lc的元素也按非递减排列。& p5 q" B' x/ ^" o2 ~
pa=La->next;pb=Lb->next;
7 C( |8 T. N) g F! I4 @5 I8 SLc=pc=La; //用La的头结点作为Lc的头结点: J* h! M7 V( e
while(pa&&pb){6 U1 P- L. K+ C/ q, f' P. ^+ R
if(pa->data<=pb->data){
2 K; Q$ p$ f& i# a* i1 j! O4 K2 V" Rpc->next=pa;pc=pa;pa=pa->next;% j1 o0 r# Q O' c7 |1 ]8 G) L
}
4 N+ E2 e+ M; N8 d% qelse{pc->next=pb;pc=pb;pb=pb->next;}
4 k! u { p7 e/ u7 Q}
: u3 ~6 ^/ J! h3 j3 k5 I' zpc->next=pa?=pa:pb;//插入剩余段0 i% I3 v% ]( c7 }( G6 u+ K
free(Lb); //释放Lb的头结点9 k/ f+ ]# }" i2 k6 r
}//MergeList_L |
|
/1 
发表于 2016-7-13 15:14
收藏
淘帖
支持！
反对！