1003: 顺序表（3）

题目描述

请在上题SortList类的基础上添加成员函数Merge，实现两个有序表的合并。部分代码已经给出，请勿改动。注意：合并算法效率要求为O(m+n)，不能借助排序算法实现。
//有序表类
template
class SortList{
public:
SortList(){length=0;}
~SortList(){}
void Insert(T x); //有序表的插入，使序列仍有序
void DispList(); //输出表
/成员函数Merge实现两个有序表的合并，使序列仍有序，
将A表和B表合并到当前类中，要求：A表，B表的元素保持不变/
void Merge(SortList &A,SortList &B);
private:
T data[MaxSize]; //存储元素
int length; //顺序表实际长度
};
//构造有序表A：函数声明
template
void CreateSort(SortList &A);
int main(){

SortList A,B,C;
//生成一个有序表A
CreateSort(A);
//生成一个有序表B
CreateSort(B);
try{
C.Merge(A,B);//合并A,B表为C表
}
catch(const char wrong){
cout << wrong; //如失败提示失败信息
}
A.DispList();
B.DispList();
C.DispList(); //显示合并后的结果
return 0;
}

//构造有序表A：函数定义
template
void CreateSort(SortList &A){
int i,n;
T x;
cin>>n;
for (i=1;i<=n;i++){
cin>>x;
try{
A.Insert(x);
}
catch(char wrong){
cout< }
}
}

输入

数据输入格式：第一个为所创建表的元素个数，之后是各个元素值，例如，下例输入，两个表的元素个数分别为5，6。
5 4 24 2 42 3
6 78 36 34 24 64 43

输出

样例输入

5 4 24 2 42 3
6 78 36 34 24 64 43

样例输出

The length:5
The elements:
2 3 4 24 42
The length:6
The elements:
24 34 36 43 64 78
The length:11
The elements:
2 3 4 24 24 34 36 42 43 64 78

提示

来源

提交

import java.util.Scanner;
class SqList {
    Object[] listElem;
    int curLen;
    String type;
    public SqList(int maxSize,String type) {
        curLen = 0;
        listElem = new Object[maxSize];
        this.type = type;
    }
    public int length() {
        return curLen;
    }
    public void insert(Object x) throws Exception {
        if (curLen == listElem.length)
            throw new Exception("顺序表已满");
        int i;
        for(i = 0;i<curLen;i++){
            if(type.equals("int")){
                if((int)listElem[i]>(int)x)break;
            }else{
                if((char)listElem[i]>(char)x)break;
            }
        }
        for (int j = curLen; j > i; j--)
            listElem[j] = listElem[j - 1];
        listElem[i] = x; // 插入 x
        curLen++; // 表长加1
    }
    public void merge(SqList A,SqList B) throws Exception {
        listElem = new Object[A.length()+B.length()];
        int ai = 0, bi = 0;
        while (ai < A.curLen && bi < B.curLen) {
            if ((int)A.listElem[ai] < (int)B.listElem[bi]) {
                listElem[curLen++] = A.listElem[ai++];
            } else {
                listElem[curLen++] = B.listElem[bi++];
            }
        }
        while (ai < A.curLen) listElem[curLen++] = A.listElem[ai++];
        while (bi < B.curLen) listElem[curLen++] = B.listElem[bi++];
    }
    public void display() {
        System.out.println("The length:"+length());
        System.out.println("The elements:");
        for (int j = 0; j < curLen; j++) {
            System.out.print(listElem[j]+ " ");
        }
        System.out.println();
    }
}
public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        SqList A,B,C ;
        int l = sc.nextInt();
        A = new SqList(l,"int");
        for (int i = 0; i < l; i++) {
            try {
                A.insert(sc.nextInt());
            } catch (Exception e) {
                e.printStackTrace();
            }
        }
        l = sc.nextInt();
        B = new SqList(l,"int");
        for (int i = 0; i < l; i++) {
            try {
                B.insert(sc.nextInt());
            } catch (Exception e) {
                e.printStackTrace();
            }
        }
        C = new SqList(0,"int");
        C.merge(A,B);
        A.display();
        B.display();
        C.display();
    }
}