关于数组和顺序表

这里首先给出一个抽象数据类型的数组的模板

#include

const int DefaultSize = 100;

template class Array
{
    public:
        Array(int Size = DefaultSize);                          //构造函数
        Array(const Array & x);                          //赋值构造函数
        ~Array(){delete [] elements;}                           //析构函数
        Array & operator = (const Array & A);     //数组复制  
                                                    还有那个const是什么意思？有什么用？
        Type & operator [] (int);                               //下标（符号重载）
        Type * operator * () const {return elements}          //指针转换
                                                            这里的const又是什么意思？
        int Length() const {return ArraySize;}
        void ReSize(int sz);                                    //修改数组长度
    private:
        Type * elements;                                    //给出首地址指针的动态数组
        int ArraySize;
        void getArray();                                        //动态分配数组储存空间
}

template void Array :: getArray()
{
    elements = new Type[ArraySize];
    if(elements == 0)
    {
        cerr<<"Memory Allocation Error"<        ArraySize = 0;
        return;
    }
}

template Array :: Array(int sz)
{
    if(sz <= 0)
    {
        cerr<<"Invalid Array Size"<        ArraySize = 0;
        return;
    }
}

template Array :: Array(const Array & x)
{
    int n = x.ArraySize;               //arraysize不是私有吗？为什么可以这样直接引用？
    ArraySize = n;
    elements = new Type[n];

    if(elements == 0)
    {
        cerr<<"Memory Allocation Error"<        ArraySize = 0;
        return;
    }

    Type * srcptr = x.elements;                                 //源数组地址首地址
    Type * destptr = elements;                                  //目的数组首地址
    while(n--)
        * destptr++ = * srcptr;                                         //传送
}


template Type & Array :: operator [](int i)
{
    if(i < 0 || i > Array - 1)
    {cerr<<"Index out of range"<    return elements[i];
}

template void Array :: ReSize(int sz)
{
    if(sz < 0)
        cerr<<"Invalid Array Size"<    if(sz != ArraySize)
    {
        Type * newarray = new Type[sz];
        if(newarray == 0)
        {cerr<<"Memory Allocation Error"<        int n = (sz <= ArraySize) ? sz : ArraySize;
        Type * srcptr = elements;
        Type * destptr = newarray;
        while(n--)
            * destptr++ = * srcptr++;
        delete [] elements;                                         //删除老数组
        elements = newarray;                                        //复制新数组
        ArraySize = sz;
    }
}


下面再看一个顺序表类的定义个实现的模板：
template class SeqList
{
    public:
        SeqList(int MaxSize = defaultSize);
        ~SeqList(){delete [] data;}
        int Length() const {return last + 1;}
        int Find(Type & x) const;
        int IsIn(Type & x);
        int Insert(Type & x, int i);
        int Remove(Type & x);
        int Next(Type & x);
        int Prior(Type & x);
        int IsEmpty(){return last == -1}
        int IsFull(){return last == MaxSize - 1}
        Type Get(int i){return i < 0 || i > last ? NULL : data[i]}
    private:
        Type * data;
        int MaxSize;
        int Last;
};

template SeqList :: SeqList(int sz)
{
    if(sz > 0)
    {
        MaxSize = sz;
        last = -1;
        data = new Type[MaxSize];
    }
}

template int SeqList :: Find(Type & x) const
{
    int i = 0;
    while(i <= last && data[i] != x)
        i++;
    if(i > last)
        return -1;
    else return i;
}

template int SeqList :: IsIn(Type & x)
{
    int i = 0;
    found = 0;
    while(i <= last && !found)
        if(data[i] != x)
            i++;
        else found = 1;
    return found;
}

template int SeqList :: Insert(Type & x, int i)
{
    if(i < 0 || i > last + 1 || last == MaxSize - 1)
        return 0;
    else
    {
        last++;
        for(int j = last; j > i; j--)
            data[j] = data[j - 1];
        data[i] = x;
        return 1;
    }
}

template int SeqList :: Remove(Type & x)
{
    int i = Find(x);
    if(i >= 0)
    {
        last--;
        for(int j = i; j <= last; j++)
            data[j] = data[j + 1];
        return 1;
    }
}

template int SeqList :: Next(Type & x)
{
    int i = Find(x);
    if(i >= 0 && i < last)
        return i +１;
    else return -1;
}

template int SeqList :: Prior(Type & x)
{
    int i = Find(x);
    if(i > 0 && i <= last)
        return i - 1;
    else return -1;
}



接下来是比较处理两个顺序表的简单函数：
template void Union(SeqList & LA, SeqList & LB)           //合并顺序表LA和LB，重复元素只留一个
{
    int n = LA.Length();
    int m = LB.Length();
    for(int i = 0; i < m; i++)                                                     //从LB中找出元素，和LA中的对比，LA中有的话就忽略，没有就加载LA后面
    {
        Type x = LB.Get(i);
        int k = LA.Find(x);
        if(k == -1)
        {
            LA.Insert(n + 1, x);
            n++;
        }
    }
}



template void Intersection(SeqList & LA, SeqList & LB)     //找出顺序表LA和LB的共有元素
{
    int n = LA.Length();
    int m = LB.Length();
    int i = 0;
    while(i < n)                                                        //从LA中逐个取出元素，并在LB中查找这个元素，不存在的话就在LA中删除该元素
    {
        Type x = LA.Get(i);
        int k = LB.Find(x);
        if(k == -1)
        {
            LA.remove(x);
            n--;
        }
        else
            i++;
    }
}