《数据结构·编程题解》线性表:归并单链表(顺序表)

题目

求并集A=AUB
已知线性表LA和LB重点数据元素按,现要求将LA和LB归并未一个新的线性表LC,且LC中的数据元素仍按值非递减有序排列,例如,设LA={3,5,8,11},LB=(2,6,8,9,11,15,20),则LC=(2,3,5,6,8,8,9,11,11,15,20)。

参考课本算法2.2和2.7

解析

归并单链表(顺序表)的算法,将两个顺序表合并至一个顺序表中,并且需要满足合并前后顺序表都是有序排列的。总体上看,解决办法有两种,一种用数组下标实现,另外一种使用指针实现,原理是调用单链表顺序存储结构中封装的函数来实现。

源代码

这里只列出核心部分源码,详细源码回复可见下载地址。

算法2.2
void MergeSqList_1(SqList La, SqList Lb, SqList *Lc)    //调用顺序表函数进行合并 
{
    int La_len, Lb_len; 
    int i, j, k;
    LElemType_Sq ai, bj;
    
    i = j = 1;
    k = 0;
    
    InitList_Sq(Lc);                    //初始化LC    
    La_len = ListLength_Sq(La);            //获取LA、LB长度 
    Lb_len = ListLength_Sq(Lb);     

    while(i<=La_len && j<=Lb_len)        //LA及LB均未扫描完 
    {
        GetElem_Sq(La, i, &ai);
         GetElem_Sq(Lb, j, &bj);
         
         if(ai<=bj)
         {
             ListInsert_Sq(Lc, ++k, ai);
             i++;
         }
         else
         {
            ListInsert_Sq(Lc, ++k, bj);
            j++;
        }
    } 
    
    while(i<=La_len)                    //表LB 还未扫描完 
    {
        GetElem_Sq(La, i++, &ai);
        ListInsert_Sq(Lc, ++k, ai);
    }
   
    while(j<=Lb_len)                    //表LB 还未扫描完
    {
        GetElem_Sq(Lb, j++, &bj);
        ListInsert_Sq(Lc, ++k, bj);
    }
}
算法2.7
void MergeSqList_1(SqList La, SqList Lb, SqList *Lc)    //调用顺序表函数进行合并 
{
    int La_len, Lb_len; 
    int i, j, k;
    LElemType_Sq ai, bj;
    
    i = j = 1;
    k = 0;
    
    InitList_Sq(Lc);                    //初始化LC    
    La_len = ListLength_Sq(La);            //获取LA、LB长度 
    Lb_len = ListLength_Sq(Lb);     

    while(i<=La_len && j<=Lb_len)        //La及LB均未扫描完 
    {
        GetElem_Sq(La, i, &ai);
         GetElem_Sq(Lb, j, &bj);
         
         if(ai<=bj)
         {
             ListInsert_Sq(Lc, ++k, ai);
             i++;
         }
         else
         {
            ListInsert_Sq(Lc, ++k, bj);
            j++;
        }
    } 
    
    while(i<=La_len)                    //表LA还未扫描完 
    {
        GetElem_Sq(La, i++, &ai);
        ListInsert_Sq(Lc, ++k, ai);
    }
   
    while(j<=Lb_len)                    //表LB还未扫描完
    {
        GetElem_Sq(Lb, j++, &bj);
        ListInsert_Sq(Lc, ++k, bj);
    }
}

结果

1.jpg

Last modification:March 18th, 2018 at 05:38 pm
If you think my article is useful to you, please feel free to appreciate

Leave a Comment