顺序表的实现与分析

template <typename T>
class LinearList
{
public:
    LinearList();
    ~LinearList();

    virtual int Size() const = 0;   //返回线性表所能够存储的最大长度
    virtual int Length() const = 0; //当前线性表的长度

    virtual int Search(T &x) const = 0;
    virtual int Locate(int i) const = 0;

    virtual bool getData(int i,T &x) const = 0;
    virtual void setData(int i,T &x) = 0;

    virtual bool Insert(int i,T &x) = 0;
    virtual bool Remove(int i,T &x) = 0;

    virtual bool IsFull() const = 0;
    virtual bool IsEmpty() const = 0;

    virtual void input() = 0;
    virtual void output() const = 0;

    virtual void Sort() = 0;
    virtual LinearList<T> operator=(LinearList<T> &L) = 0;  //支持线性表的复制
};

正文　

--顺序表的实现

对于顺序表，其特点有如下公式：

Loc(i) = Loc(j) + (i-j) * sizeof(T)

类定义如下：

//注：	对于某些不知含义的C++关键词的含义以及用法，
//		请参考系列博客：http://blog.csdn.net/column/details/zjf666.html
const int defaultSize = 10;

template <class T>
class SeqList : public LinearList<T>
{
public:
    SeqList(int sz = defaultSize);
    SeqList(SeqList<T> &L);
    ~SeqList()
    {
        delete []data;
    }

    int Size() const
    {
        return maxSize;
    }
    int Length() const
    {
        return last + 1;
    }

    int Search(T &x)　const;
    int Locate(int i) const;

    bool getData(int i,T &x)
    {
        if (i > 0 && i <= last+1)
        {
            x = data[i-1];
            return true;
        }
        else
        {
            return false;
        }
    }
    void setData(int i,T &x)
    {
        if (i > 0 && i <= last+1)
        {
            data[i-1] = x;
        }
    }

    bool Insert(int i,T &x);
    bool Remove(int i,T &x);

    bool IsFull() const
    {
        return last == maxSize-1;
    }
    bool isEmpty() const
    {
        return last == -1;
    }

    void input();
    void output();

    void Sort();

    SeqList<T> operator=(SeqList<T> &L);

protected:
    T *data;                    //数组
    int maxSize;                //最大可容纳量
    int last;                   //当前已存元素的最后一个位置

    void reSize(int newSize);   //改变data数组的空间大小
};

--各个操作的实现与分析：

1) 构造函数与复制构造函数

template <typename T>
SeqList<T>::SeqList(int sz)     //构造顺序表
{
    if (sz > 0)
    {
        maxSize = sz;
        last = -1;              //表的实际长度置空
        data = http://www.mamicode.com/new T[sz];>
 
2) 私有操作：扩充顺序表的的存储数组空间大小
template <typename T>
void SeqList<T>::reSize(int newSize)
{
    if (newSize <= 0)   //无效的数组长度
    {
        cerr << "invalid size!" << endl;
        exit(1);
    }

    if (newSize != maxSize)
    {
        T *newArr = new T[newSize]; //重新分配新的数组
        checkNew(newArr);

        int times = last + 1;       //获得原数组长度
        T *srcPtr = data;
        T *destPtr = newArr;

        while (times --)            //将原数组内容复制到新的数组
        {
            *destPtr ++ = *srcPtr ++;
        }

        delete []data;              //不要忘记释放原data内存！
        data = http://www.mamicode.com/newArr;>
 
3) 搜索和定位操作
template <typename T>
int SeqList<T>::Search(T &x) const
{
    for (int i = 0; i <= last ; ++i)
    {
        if (data[i] == x)
        {
            return i + 1;   //表项序号恰比它在数组中的实际存放的位置序号少1
        }
    }
    return 0;
}

template <typename T>
int SeqList<T>::Locate(int i) const
{
    if (i >= 1 && i <= last)
        return i;
    return 0;
}

 
4) 顺序表的插入与删除操作
template <typename T>
bool SeqList<T>::Insert(int i,T &x)
{
    if (last + 1 == maxSize)    //表满
        return false;
    if (i < 0 || i > last + 1)  //表项参数错误
        return false;

    for (int index = last; index >= i; -- index)    //依次后移，空出i号位置
    {
        data[index] = data[index - 1];
    }
    data[i] = x;
    ++ last;            //表长+1[勿忘]

    return true;
}

template <typename T>
bool SeqList<T>::Remove(int i,T &x)
{
    if (last == -1)                 //表空
        return false;
    if (i < 1 || i > last + 1)      //表项参数错误
        return false;

    x = data[i - 1];
    for (int index = i; index <= last ; ++index)
    {
        data[index - 1] = data[index];  //循环前移，将i-1位置填充
    }
    -- last;    //修改表长

    return true;
}

 
5) 输入输出操作
template <class T>
void SeqList<T>::input()
{
    while (1)
    {
        cin >> last;    //输入数组最后一个元素所在位置
        if (last <= maxSize - 1)
            break;
        cout << "The value of last is error,please try again!" << endl;
    }

    for (int i = 0; i <= last; ++i)
    {
        cout << i + 1 << ": ";
        cin >> data[i];
    }
}

template <class T>
void SeqList<T>::output() const
{
    for (int i = 0; i <= last; ++i)
    {
        cout << "#" << i + 1 << ": " << data[i] << endl;
    }
}

 
6) 赋值操作
template <class T>
SeqList<T> &SeqList<T>::operator=(const SeqList<T> &L)
{
    if (maxSize < L.Length())
    {
        reSize(L.Length() * 2);
    }

    maxSize = L.Length() * 2;
    last = L.Length() - 1;

    T value;
    for (int i = 1;i <= last + 1; ++i)
    {
        L.getData(i,value);
        data[i - 1] = value;
    }

    return * this;
}

	--顺序表的性能分析
	顺序表的所有操作的实现中，最复杂、最耗时的就是搜索、插入和删除运算的实现。搜索的时间代价主要看重搜索所采用的方法，是采用顺序搜索，还是二叉搜索等，而顺序表的插入和删除的时间代价主要是看循环内的数据移动次数。