数据结构顺序线性表的例题算法2.2——C语言完整实现

兔子不吃窝边草

        已知线性表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,9,11,11,15,20）
               
                        动态数组的插入ListInsert(),加入了判断是否满的情况，因此不用担心溢出的问题。
               

#include<stdio.h>
#include<stdlib.h>
#define ListInitsize 20//初始分配内存数 
#define OVERFLOW -2 //异常状态 
#define ADD 10        //分配内存增量 
typedef struct
{
        int *data;//顺序线性表动态数组名 
        int length;//线性表长度 
        int Listsize;//线性表当前分配的内存数量； 
}List;
int InitList(List *L)//线性表初始化 
{
        L->data =malloc(ListInitsize*sizeof(int));//分配内存 
        if(!L->data)
                exit(OVERFLOW);//分配内存失败，则退出。 
        L->length = 0;
        L->Listsize = ListInitsize;// 线性表内存为初始化内存数。 
        return 1;
}
int GetElem(List *L,int i,int *e)//获取线性表第i个元素 
{
        
        if(i<1||i>L->length)//若i不在范围内，则退出。 
        return 0;
        *e = L->data[i-1]; 
        return 1;        
}
int ListInsert(List *L,int i,int e)//插入e至第i个元素位置，需要将i个元素至最后一个元素向后移动一个位置 
{
        int *p=malloc(sizeof(int));
        int *q=malloc(sizeof(int));
        int *newbase; //新分配的动态数组名 
        if(i<1||i>L->length+1)//若插入位置在最后一个元素的后一个元素之后也要退出 
                return 0;
        if(L->length>=L->Listsize)//判定分配内存空间是否满或溢出了。 
        {
                newbase = realloc(L->data,(L->Listsize+ADD)*sizeof(int));//若满或溢出就重新分配内存 ，将原来的内存空间增加ADD个单位 
                if(!newbase)
                exit(OVERFLOW);//分配内存失败，则异常退出。 
                L->data = newbase;//新的内存首地址为newbase，将它赋值给data。 
                L->Listsize += ADD;//性表当前分配的内存为原来的增加ADD。 
        }
        q= &L->data[i-1];        //将q指向第i个元素。 
        for(p=&L->data[L->length-1];p>=q;p--)        //p初始化指向数组最后一个元素，依次递减至指向第i个元素。 
                *(p+1) = *p;//依次将最后一个元素到第i个元素的值，赋给最后一个元素的后一个元素到 i+1个元素。
                                        //相当于i到最后一个元素整体后移一位。         
        *q =e;                        //将e插入第i的位置。 
        L->length++;        //线性表的长度增加1。 
        return 1;
}
int ListDelete(List *L,int i,int *e)//删除线性表的一个元素，本题用不到。 
{
        int *p=malloc(sizeof(int));
        int *q=malloc(sizeof(int));
        if(i<1||i>L->length)
        return 0;
        p = &L->data[i-1];//指向第i个元素的指针。 
        *e = *p;                        //将其值保存在*e中。 
        q = L->data+L->length-1;//指向最后一个元素的指针。 
        for(++p;p<=q;p++)
                *(p-1) = *p;//将第i+1个元素到最后一个元素向前移动一个位置。 
        L->length--;
        return 1;
}
int ListLength(List L)//获取线性表长度 
{
        return L.length;
}

void MergeList(List La,List Lb,List *Lc)//将La与Lb中的元素按从小到大的顺序插入到Lc中，从大到小也行，改一下比较符就行。 
{
        int i=1,j=1,k=0;                                //i,j,k分别为在表la,lb,lc的位置，即第几个元素，i，j初始化为第一个元素。k初始化为第一个元素之前的位置，后面自增用前缀。
        int La_len,Lb_len,ai,bj;
        InitList(Lc);        
        La_len = ListLength(La);
        Lb_len = ListLength(Lb);
        while(i<=La_len&&j<=Lb_len)        //依次从La和Lb中读取较小的元素插入到 Lc中。 
        {
                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)                //当Lb的元素都插入完了，剩下的La的元素依次读取并插入到Lc中。
        {
                GetElem(&La,i++,&ai);//注意结束上面的循环后，若是Lb的元素插入完，i指向的元素还没有插入到Lc中，因此i自增是后缀。 
                ListInsert(Lc,++k,ai);
        }
        while(j<=Lb_len)                //这是La插入完的情况，这两个只会执行一个因为有一个是插入完的。
        {
                GetElem(&Lb,j++,&bj);
                ListInsert(Lc,++k,bj);
        }
}
int main()
{
        int i,e;
        List La,Lb,Lc;
        InitList(&La);
        InitList(&Lb);
        printf("创建链表La\n"); 
        for(i=0;i<4;i++)
        {
                scanf("%d",&e);
                ListInsert(&La,i+1,e);
        }
        printf("创建链表Lb\n");
        for(i=0;i<7;i++)
        {
                scanf("%d",&e);
                ListInsert(&Lb,i+1,e);        
        }                //如题创建线性表La，Lb。 
        printf("数量：%d\n",ListLength(La)+ListLength(Lb));//新的线性表Lc的元素数量，这里是做一个验证，La与Lb的元素数量和与下面打印的数量应该相同。 
        MergeList(La,Lb,&Lc);
        for(i=1;i<=Lc.length;i++)
        {
                GetElem(&Lc,i,&e);
                printf("%d ",e); 
        }//依次打印新的线性表的元素。 
        return 0;
}