线性表的数组描述

//基于公式的类LinearList
template<class T>
class LinearList{
    public:
        LinearList(int MaxListSize = 10);//构造函数
        ~LinearList() {delete [] element;}//析构函数
        bool IsEmpty() const { return length == 0;}
        int Length() const { return length;}
        bool Find(int k, T & x) const;//返回第k个元素至x中
        int Search(const T & x) const;//返回x所在位置
        LinearList<T> & Delete(int k, T & x);//删除第k个元素至x中
        LinearList<T> & Insert(int k ,const T & x);//在第k个元素后插入x
        void Output(ostream & out) const;
    private:
        int length;
        int MaxSize;
        T * element;//一维动态数组
};



update by bob_hu on Apr 17,2012

template<class T>
LinearList<T>::LinearList(int MaxListSize)
{
    MaxSize = MaxListSize;
    element = new T[MaxSize];
    length = 0;
}

template<class T>
bool LinearList<T>::Find(int k, T & x) const
{
    if ( k < 1 || k > length) return false;
    x = element[k-1];
    return true;
}

template<class T>
int LinearList<T>::Search(const T & x) const
{
    for (int i = 0; i < length; i++)
        if ( element[i] == x) return ++i;
    return 0;
}

update by bob_hu on Apr 19,2012

template<class T>
LinearList<T>& LinearList<T>::Delete(int k ,T &x)
{
    if (Find(k,x))
    {
        for (int i = k; i < length;i++)
            element[i-1]= element[i];
        length--;
        return *this;
    }
    else
        //如果不存在第k个元素,则引发异常OutOfBounds
        throw OutOfBounds();
}
template<class T>
LinearList<T> & LinearList<T>::Insert(int k, const T & x)
{
  if (k<0|| k > length) throw OutOfBounds();
  if (length == MaxSize) throw NoMem();
  for(int i = length - 1; i >= k; i--)
    element[i+1] = element[i];
  element[k] = x;
  length++;
  return *this;
}
template<class T>
void LinearList<T>::Output(ostream & out) const
{
  for(int i = 0; i < length; i++)
    out<<element[i]<<" ";
}
template<class T>
ostream& operator<<(ostream & out, const LinearList<T> & x)
{
  x.Output(out);
  return out;
}

update by bob_hu on Apr 20,2012

#include <iostream>
using namespace std;
int main()
{
    LinearList<int> L(5);
    cout<<"Length = "<<L.Length()<<endl;
    cout<<"IsEmpty = "<<L.IsEmpty()<<endl;
    L.Insert(0,2).Insert(1,6);
    cout<<"List is "<<L<<endl;
    cout<<"IsEmpty = "<<L.IsEmpty()<<endl;
    int z;
    L.Find(1,z);
    cout<<"First element is "<< z << endl;
    cout<<"Length = "<<L.Length()<<endl;
    L.Delete(1,z);
    cout<<"Deleted element is "<< z <<endl;
    cout<<"List is "<<L<<endl;
    return 0;
}



update by bob_hu on Apr 21,2012