• 源碼

#define ERROR -1
#define OVERMEMORY -2

#include <iostream>

using namespace std;

template<class T>
class List{
    T *elem;    //存儲空間的基址
    int length; //當前順序表長度
    int listsize; //當前分配空間的大小

public:
    List(){
        InitList(1);
    }
    List(int size){
        InitList(size);
    }
    List(const List &l){
        elem = new T[l.listsize];
        length = l.length;
        listsize = l.listsize;
        for (int i = 0; i < l.listsize; i++){
            elem[i] = l.elem[i];
        }
    }//拷貝構(gòu)造函數(shù)

    ~List(){
        delete elem;
    }

    void InitList(int L){
        elem = new T[L];
        if (!elem){
            cout << "Over Memory!" << endl;
            exit(OVERMEMORY);
        }
        length = 0;
        listsize = L;
    }// 初始化鏈表

    void ListInsert(int i,const T &e){
        if (i < 0 || i > length)    return;
        if (length >= listsize)
            resize(listsize*2);
        
        T *p = &elem[i];
        for (T *q = &elem[length]; q > p; q--){
            *q = *(q-1);
        }
        *p = e;
        length++;
    }// 在下標為i的位置插入元素e

    void push_back(const T &e){
        ListInsert(length, e);
    }//在表末添加元素e

    void ListDelete(int i){
        if (i < 0 || i >= length)    return;

        T *end = &elem[length-1];
        for (T *p = &elem[i]; p != end; p++){
            *p = *(p+1);
        }
        length--;

        if (listsize / length >= 4){
            resize(listsize / 2);
        }//如果分配的空間太大，調(diào)整大小

    }//刪除下標為i的元素
    void resize(int size){
        T *newelem = new T[size];
        if (!newelem){
            cout << "Over Memory!" << endl;
            exit(OVERMEMORY);
        }

        int count = 0;
        for (int i = 0; i < size; i++){
            if (i < length){
                newelem[i] = elem[i];
                count++;
            }
            else
                break;
        }
        delete elem;
        elem = newelem;
        listsize = size;
        length = count;
    }// 重新設(shè)置順序表存儲空間大小
    
    int LocateElem(const T &e){
        int i = 0;
        T *p = elem;
        while (i < length && *p != e){
            p++;
            i++;
        }
        if (i == length)
            return -1;
        return i;
    }//獲取元素e的下標，如果有多個則返回下標最小的一個

    void MergeList(List &b){
        List c;

        T *pa = elem;
        T *pb = b.elem;

        c.resize(listsize+b.listsize);
        c.length = length + b.length;

        T *pc = c.elem;
        T *pa_last = &elem[length-1];
        T *pb_last = &b.elem[b.length-1];

        //歸并
        while (pa <= pa_last && pb <= pb_last){
            if (*pa <= *pb){
                *pc = *pa;
                pa++;
                pc++;
            }
            else{
                *pc = *pb;
                pc++;
                pb++;
            }
        }
        while (pa <= pa_last){
            *pc = *pa;
            pc++;
            pa++;
        }//插入La剩余元素
        while (pb <= pb_last){
            *pc = *pb;
            pc++;
            pb++;
        }//插入Lb剩余元素

        *this = c;
    }// 與一個順序表歸并

    void print(){
        for (int i = 0; i < length; i++){
            cout << elem[i];
            if (i != length-1)
                cout << " ";
        }
        cout << endl;
    }

    T& operator[] (int i){
        return elem[i];
    }// 重載[]

    void operator= (const List &l){
        if (listsize)
            delete elem;
        elem = new T[l.listsize];
        length = l.length;
        listsize = l.listsize;
        for (int i = 0; i < l.listsize; i++){
            elem[i] = l.elem[i];
        }
    }// 重載賦值(深拷貝)

};//順序表類, 下標從0開始


int main(){
    List<int> l;
    l.push_back(1);
    l.push_back(2);
    l.push_back(3);
    l.ListInsert(0, 0);
    l.print();

    List<int> a;
    a.push_back(4);
    a.push_back(5);
    a.push_back(6);
    a.ListDelete(1);
    a.print();
    
    a.MergeList(l);
    a.print();
}