顺序表A和B的合并与排序

March 12, 2020 数据结构 访问: 30 次

用顺序表A和B表示的两个线性表,元素的个数分别是m和n, 若表中数据都是从小到大顺序排列的,且这(m+n)个数据中没有重复的。

设计一个算法将此两个线性表合并成一个,仍是数据由小到大排列的线性表,存储到另一个顺序表C中。

void meger1(SqList *&A, SqList *&B, SqList *&C){
    int i=0,j=0,k=0; //i扫描A,j扫描B
    while(i< A->length && j< B->length)
    {
        if (A->data[i] < B->data[j])
        {
            C->data[k] = A->data[i];
            i++; k++;
        } 
        else
        {
            C->data[k] = B->data[j];
            j++; k++;
        }
    }

    while(i< A->length){ //若A未扫描完,则将A剩余的元素加到C中
        C->data[k] =A->data[i];
        i++; k++;
    }

    while(j< B->length){ //若B未扫描完,则将B剩余的元素加到C中
        C->data[k] = B->data[j];
        j++; k++;
    }
    C->length=k;
}

时间复杂度:O(m+n)

如果顺序表B的大小为(m+n)个单元,是否可不利用顺序表C而将合成的线性表存放于顺序表B中? 试设计算法。

void meger2(SqList *&A, SqList *&B){
    int i=0,j=0,k;
    while(i< A->length){
        if (A->data[i] > B->data[B->length-1]) //若A->data[i]大于B中所有元素
        { 
            B->data[B->length]=A->data[i];  //将A->data[i]插入到B末尾
            B->length++; i++;
        }
        else if(A->data[i] < B->data[j]){
                for(k=B->length-1; k>=j; k--)
                {
                    B->data[k+1] = B->data[k]; //将元素B->data[j]及之后的元素依次后移
                }
                B->data[j]=A->data[i]; //在位置j处插入
                B->length++; //顺序表长度加1
                i++; j++;
        }
        else {
            j++;
        }
    }
}

时间复杂度:O(m*n)

添加新评论