算法2.7 归并La和Lb

《数据结构》算法2.7的实现

algo2_7.h

#include "status.h"



/******************************************************************
            函数声明
******************************************************************/
SqList MergeList_Sq(SqList La,SqList Lb);

algo2_7.c

#include "include.h"
#include "List.h"
#include "algo2_7.h"

SqList MergeList_Sq(SqList La,SqList Lb)
{//初始条件：已知La和Lb中的元素非递减排列

//操作结果：归并La和Lb到Lc，Lc的元素也是非递减排列

    SqList Lc;
    ElemType *pa,*pb,*pc;
    ElemType *pa_last,*pb_last;
    pa=La.elem; //pa pb指向顺序表的基址

    pb=Lb.elem;
    Lc.listsize=Lc.length=La.length+Lb.length;
    pc=Lc.elem=(ElemType *)malloc(Lc.listsize*sizeof(ElemType));
    if(!Lc.elem)
        exit(OVERFLOW);
    pa_last=La.elem + La.length-1;//取得La Lb最后元素的指针

    pb_last=Lb.elem + Lb.length-1;
    while(pa<=pa_last&&pb<=pb_last) //归并

    {
        if(*pa<=*pb)
            *pc++=*pa++;
        else
            *pc++=*pb++;
    }
    while(pa<=pa_last) //插入剩余的La元素

        *pc++=*pa++;
    while(pb<=pb_last) //插入剩余的Lb元素

        *pc++=*pb++;
    return Lc;
}

main.c

/******************************************************************
                       主函数
******************************************************************/
#include "include.h"
#include "List.h"
#include "Algo2_7.h"


Status visit(ElemType *e)
{
    printf("%d ",*e);
    printf("\n");
    return OK;
}

void main()
{
    SqList La,Lb,Lc;
    int i;
    int result;//函数的返回状态值

    //------------------初始化La和Lb-----------------------

    printf("初始化顺序表\n");
    La=InitList();
    Lb=InitList();
    printf("初始化后的结果：\n");
    printf("La.elem=%u La.length=%d La.listsize=%d\n\n",La.elem,La.length,La.listsize);
    printf("Lb.elem=%u Lb.length=%d Lb.listsize=%d\n\n",Lb.elem,Lb.length,Lb.listsize);
    //-----------------------------------------------------

    //------------------初始化La---------------------------

    printf("在表La头依次插入11 8 5 3 \n");
    result=ListInsert(&La,1,11);
    result=ListInsert(&La,1,8);
    result=ListInsert(&La,1,5);
    result=ListInsert(&La,1,3);
    printf("La.elem=%u La.length=%d La.listsize=%d\n\n",La.elem,La.length,La.listsize);
    printf("插入的内容为：\n");
    for(i=1;i<=La.length;i++)
        printf("%d ",*(La.elem+i-1));
    //-----------------------------------------------------

    //------------------初始化Lb---------------------------

    printf("\n在表Lb头依次插入20 15 11 9 8 6 2\n");
    result=ListInsert(&Lb,1,20);
    result=ListInsert(&Lb,1,15);
    result=ListInsert(&Lb,1,11);
    result=ListInsert(&Lb,1,9);
    result=ListInsert(&Lb,1,8);
    result=ListInsert(&Lb,1,6);
    result=ListInsert(&Lb,1,2);
    printf("Lb.elem=%u Lb.length=%d Lb.listsize=%d\n\n",Lb.elem,Lb.length,Lb.listsize);
    printf("插入的内容为：\n");
    for(i=1;i<=Lb.length;i++)
        printf("%d ",*(Lb.elem+i-1));

    //--------------算法2.2测试---合并顺序表---------------

    Lc=MergeList_Sq(La,Lb);
    printf("\nLc合并后的内容：\n");
    result=ListTraverse(Lc,visit);
    //-----------------------------------------------------


}


其他文件list.c list.h不变