【データ構造-C言語版】--線形テーブルの2つのマージ方法

1234 ワード

線形テーブルLAを拡大し、線形テーブルLBに存在し、線形テーブルLAに存在しないデータ要素を線形テーブルLAに挿入する.時間複雑度:O(ListLength(LA)*ListLength(LB))
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言語版)厳蔚敏呉偉民編著明大学出版社