算法2.12（归并La，Lb为Lc）

《数据结构》中的算法2.12

algo2_12.h

#include "status.h"



/******************************************************************
            函数声明
******************************************************************/
void MergeList(LinkList *La,LinkList *Lb,LinkList *Lc);

 

algo2_12.c

#include "include.h"
#include "List.h"
#include "algo2_12.h"

void MergeList(LinkList *La,LinkList *Lb,LinkList *Lc)
{//已知单链线性表La和Lb的元素按值非递减排列。

//归并La和Lb得到新的单链线性表Lc，Lc的元素也按非递减排列。

    LinkList pa,pb,pc;
    pa=(*La)->next;//pa指向La第一个元素

    pb=(*Lb)->next;//pb指向Lb第一个元素

    *Lc=pc=*La; //用La的头结点作为Lc的头结点

    while(pa&&pb)
    {
        if(pa->data<=pb->data)
        {
            pc->next=pa;
            pc=pa;
            pa=pa->next;
        }
        else
        {
            pc->next=pb;
            pc=pb;
            pb=pb->next;
        }
    }
    pc->next=pa?pa:pb; //插入剩余段

    free(*Lb); //释放Lb

}



main.c

#include "include.h"
#include "list.h"
#include "algo2_11.h"
#include "algo2_12.h"



Status compare(ElemType c1,ElemType c2)
{//比较两个数是否相等

    if(c1==c2)
        return TRUE;
    else
        return FALSE;
}

void visit(ElemType c)
{
   printf("%d ",c);
}

void main()
{
    LinkList La,Lb,Lc;
    Status result;
    printf("创建单链表La\n");
    printf("一次输入9 7 5 3 1\n");
    CreateList(&La,5);
    printf("创建单链表Lb\n");
    printf("16 14 12 10 8 6 4 2 \n");
    CreateList(&Lb,8);
    
    //-------------------------ListTraverse函数测试------------------------

    printf("输出La中的所有元素。\n");
    result= ListTraverse(La,visit);
    printf("\n");
    printf("输出Lb中的所有元素。\n");
    result= ListTraverse(Lb,visit);
    printf("\n");
    //---------------------------------------------------------------------

    printf("归并La，Lb为Lc\n");
    MergeList(&La,&Lb,&Lc);
    printf("输出Lc中的所有元素。\n");
    result= ListTraverse(Lc,visit);
    printf("\n");

    
}