03-将两个有序的线性表合并为一个有序的线性表

1.1.1　将两个有序的线性表合并为一个有序的线性表

问题描述

顺序表A和顺序表B的元素都是非递减排列的，利用顺序表的基本运算，将它们合并成一个顺序表C，要求C也是非递减排列的。例如，若 A=(8,17,17,25,29)，B=(3,9,21,21,26,57)，则C=(3,8,9,17,17,21,21,25,26,29,57)。

【分析】

顺序表C是一个空表，首先取出顺序表A和B中的元素，并将这两个顺序表中的元素进行比较。如果A中的元素m₁大于B中的元素n₁，则将B中的元素n₁插入C中，继续取出B中下一个元素n₂并与A中元素m₁比较；如果A中的元素m₁小于或等于B中的元素n₁，则将A中的元素m₁插入C中，继续取出A中的下一个元素m₂与B中的元素n₁比较。依次比较，直到一个表中元素比较完毕，将另一个表中的剩余元素插入C中。

第1章\实例1-01.c

/********************************************
*实例说明：合并两个有序的线性表为一个有序的线性表
*********************************************/
#include<stdio.h>                /*包含输入/输出头文件*/
#define ListSize 200
typedef int DataType;            /*元素类型定义为整型*/
#include"SeqList.h"              /*包含顺序表的基本运算*/
void MergeList(SeqList A,SeqList B,SeqList *C);
/*合并顺序表A和B中元素的函数声明*/
void main()
{
    int i,flag;
    DataType a[]={8,17,17,25,29};
    DataType b[]={3,9,21,21,26,57};
    DataType e;
    SeqList A,B,C;                
    InitList(&A);                 
    InitList(&B);                 
    InitList(&C);                 
    for(i=1;i<=sizeof(a)/sizeof(a[0]);i++)/*将数组a中的元素插入顺序表A中*/
    {
        if(InsertList(&A,i,a[i-1])==0)
        {
            printf("位置不合法");
            return;
        }
    }
    for(i=1;i<=sizeof(b)/sizeof(b[0]);i++)/*将数组b中的元素插入顺序表B中*/
    {
        if(InsertList(&B,i,b[i-1])==0)
        {
            printf("位置不合法");
            return;
        }
    }
    printf("顺序表A中的元素：\n"); /*输出顺序表A中的每个元素*/
    for(i=1;i<=A.length;i++)     
    {
        flag=GetElem(A,i,&e);    /*返回顺序表A中的每个元素到e中*/
        if(flag==1)
            printf("%4d",e);
    }
    printf("\n");
    printf("顺序表B中的元素：\n"); /*输出顺序表B中的每个元素*/
    for(i=1;i<=B.length;i++)
    {
        flag=GetElem(B,i,&e);
        if(flag==1)
            printf("%4d",e);    
    }
    printf("\n");
    printf("将顺序表A和B中的元素合并得到C：\n");
    MergeList(A,B,&C);           /*将顺序表A和B中的元素合并*/
    for(i=1;i<=C.length;i++)    /*显示合并后顺序表C中的所有元素*/
    {
        flag=GetElem(C,i,&e);
        if(flag==1)
            printf("%4d",e);    
    }
    printf("\n");
}
void MergeList(SeqList A,SeqList B,SeqList *C)
/*合并顺序表A和B的元素到顺序表C中，并保持元素非递减排序*/
{
    int i,j,k;
    DataType e1,e2;
    i=1;j=1;k=1;
    while(i<=A.length&&j<=B.length)
    {
        GetElem(A,i,&e1);                
        GetElem(B,j,&e2);                
        if(e1<=e2)                       
        {
            InsertList(C,k,e1);          /*将较小的一个元素插入顺序表C中*/
            i++;                         /*往后移动一个位置，准备比较下一个元素*/
            k++;
        }
        else
        {
            InsertList(C,k,e2);         
            j++;                        
            k++;
        }
    }
    while(i<=A.length)                   /*如果顺序表A中元素还有剩余，顺序表B中已经没有元素*/
    {
        GetElem(A,i,&e1);
        InsertList(C,k,e1);             
        i++;
        k++;
    }
    while(j<=B.length)                  /*如果顺序表B中元素还有剩余，顺序表A中已经没有元素*/
    {
        GetElem(B,j,&e2);
        InsertList(C,k,e2);            
        j++;
        k++;
    }
    C->length=A.length+B.length;        /* 顺序表C的长度等于顺序表A和顺序表B的长度的和*/
}

运行结果如图1.4所示。

图1.4　运行结果 如何调用顺序表的头文件？ 在程序中，需要调用头文件SeqList.h时，因为其中包含数据类型DataType和表示顺序表长度的宏名ListSize，所以在包含命令#include"SeqList.h"前首先需要给宏名赋值，并进行类型定义，其语句次序如下。

#define ListSize 200
typedef int DataType;
#include"SeqList.h"