顺序存储的函数实现

/******************************************************************************
* 文件：LinearListSqu.h
* 功能：线性表顺序存储
* 说明：动态分配顺序存储结构的线性表类定义
        及类成员函数包括数据插入、删除、查找等函数的实现
* 时间：2011-4-3
Author: Lzy
*******************************************************************************/
#include <iostream.h>
#include "LinearList.h"

/********************************************************************
* 类名: 类模板LinearListSqu
* 功能: 动态分配顺序存储结构的线性表类
* 说明：线性表的长度可变
/********************************************************************/
template<class T>
class LinearListSqu : public LinearList<T>            //从LinearList派生

{
public:
    LinearListSqu(int MaxListSize = 10);
    virtual ~LinearListSqu() {if(element) delete[]element;}
    virtual bool IsEmpty() const {return length ==0;}
    virtual int Length() const {return length;}
    virtual bool Find(int k, T &x) const;            //返回第K个元素到x中，在具体类中完成

    virtual bool Delete(int k, T &x);                //删除第K个元素并将它返回至x

    virtual bool Insert(int k, const T &x);            //在第K个元素之后插入x

    virtual void Output(ostream &out) const;        //输出


protected:
    long length;            //线性表长度

    long MaxSize;            //表最大长度

    T *element;                //动态数组

};

/********************************************************************
* 所属类名: LinearListSqu
* 成员名称：LinearListSqu
* 函数功能：初始化线性表
* 说    明：
/********************************************************************/
template<class T>
LinearListSqu<T>::LinearListSqu(int MaxListSize)
{                                //线性表初始化

    MaxSize = MaxListSize;
    element = new T[MaxSize];
    length = 0;
}

/********************************************************************
* 所属类名: LinearListSqu
* 成员名称：Find
* 函数功能：查找元素
* 说    明：把第K个元素取至X中，如果不存大返回假，否则返回真
/********************************************************************/
template<class T>
bool LinearListSqu<T>::Find(int k, T &x) const
{
    if(k < 1 || k > length)
        return false;
    x = element[k - 1];
    return true;
}

/********************************************************************
* 所属类名: LinearListSqu
* 成员名称：Output
* 函数功能：输出表中所有元素至&out
* 说    明：
/********************************************************************/
template<class T>
void LinearListSqu<T>::Output(ostream &out) const
{
    for(int i = 0; i < length; i++)
        out<<element[i]<<" ";            //把表输送至输出流

}

/********************************************************************
* 所属类名: LinearListSqu
* 成员名称：<<
* 函数功能：<<重载
* 说    明：
/********************************************************************/
template<class T>
ostream& operator<<(ostream& out, const LinearListSqu<T>& x)
{
    x.Output(out);
    return out;
}

/********************************************************************
* 所属类名: LinearListSqu
* 成员名称：Insert
* 函数功能：插入数据元素
* 说    明：在第K元素之后插入X
/********************************************************************/
template<class T>
bool LinearListSqu<T>::Insert(int k, const T &x)
{
    if(k < 0 || k > length)                    //判断插入位置是否合法

        throw OutOfBounds();
    if(MaxSize == length)
        throw NoMem();

    for(int i = length - 1; i >= k; i--)
        element[i+1] = element[i];            //元素后移

    element[k] = x;                            //数据插入

    length++;                                //线性表长度加1

    return true;
}

/********************************************************************
* 所属类名: LinearListSqu
* 成员名称：Delete
* 函数功能：删除数据
* 说    明：把第K个元素放入x中然后删除该元素
            如果不存在，则收发异常OutOfBounds
/********************************************************************/
template<class T>
bool LinearListSqu<T>::Delete(int k, T &x)
{
    if(Find(k, x))                        //找到第K个元素，放入X中

    {
        for(int i = k; i < length; i++)
            element[i-1] = element[i];        //删除元素

        length--;
        return true;
    }
    else
        throw OutOfBounds();
}

/******************************************************************************
* 文件：
* 功能：测试程序
* 说明：测试线性表函数的操作
* 时间：2011-4-3
Author: Lzy
*******************************************************************************/
#include <iostream.h>
#include "LinearListSqu.h"

void main()
{try{

    LinearListSqu<int>L(5);                //初始化线性表

    cout<<"Length="<<L.Length()<<endl;
    cout<<"IsEmpty="<<L.IsEmpty()<<endl;

    bool ok = L.Insert(0,2);            //插入元素

    if(ok)
        cout<<"ok"<<endl;
    L.Insert(1,6);    L.Insert(2,8);
    cout<<"List is "<<L<<endl;

    int z;
    L.Find(1, z);                        //查找元素

    cout<<"第一个元素是："<<z<<endl;

    cout<<"Length="<<L.Length()<<endl;

    L.Delete(1, z);                        //删除元素

    cout<<"删除元素："<<z<<endl;

    cout<<"List is "<<L<<endl;
    cout<<"Length="<<L.Length()<<endl;
}

    catch(...)
    {
        cerr<<"错误"<<endl;
    }

}