【データ構造-C言語版】--線形テーブルの2つのマージ方法
1234 ワード
線形テーブルLAを拡大し、線形テーブルLBに存在し、線形テーブルLAに存在しないデータ要素を線形テーブルLAに挿入する.時間複雑度:O(ListLength(LA)*ListLength(LB))
線形テーブルLAおよびLBのデータ要素は、値非減算順に配列されていることが知られており、ここでは、LAおよびLBを新しい線形LCに集約する必要があり、LCのデータ要素は値非減算順に配列されている.時間複雑度:O(ListLength(LA)+ListLength(LB))
参考文献:データ構造(C言語版)厳蔚敏呉偉民編著明大学出版社
viod union(List &La,List Lb){
// Lb La La 。
La_len=ListLength(La); Lb_len=ListLength(Lb);//
for(i=1;i<=Lb_len;i++){
GetElem(Lb,i,e); // Lb i e
if(!LocateElem(La,e,equal)) ListInsert(La,++La_len,e);
//La e ,
}
}//union
線形テーブルLAおよびLBのデータ要素は、値非減算順に配列されていることが知られており、ここでは、LAおよびLBを新しい線形LCに集約する必要があり、LCのデータ要素は値非減算順に配列されている.時間複雑度:O(ListLength(LA)+ListLength(LB))
void MergeList(List La,List Lb,List &Lc){
// La Lb 。
// La Lb Lc,Lc 。
InitList(Lc);
i=j=1;k=0;
La_len=ListLength(La); Lb_len=ListLength(Lb);
while((i<=La_len)&&(j<=Lb_len)) {//La Lb
GetElem(La,i,ai);GetElem(Lb,j,bj);
if(ai<=bj) {ListInsert(Lc,++k,ai);++i;}
else {ListInsert(Lc,++k,bj);++j};
}
while(i<=La_len) {
GetElem(La,++i,ai);ListInsert(Lc,++k,ai);
}
while(i<=Lb_len) {
GetElem(Lb,++j,bj);ListInsert(Lc,++k,bj);
}
参考文献:データ構造(C言語版)厳蔚敏呉偉民編著明大学出版社