线性表——数组描述

抽象数据类型（abstract date tpye， ADT）

1.抽象数据类型linearList

C++支持两种类——抽象类和具体类。一个抽象类包含没有实现的代码的成员函数。这样的成员函数成为“虚函数(pure virtual function）”.

具体类是没有虚函数的类。只有虚函数才可以实例化（只能对具体类建立实例或对象）。但是可以建立抽象类的对象指针。

一个线性表的抽象类：

template<class T>

class linearList

{

    public:

        virtual ~linearList() {

        };

        //线性表为空，返回true 

        virtual bool empty() const  = 0;

        //返回线性表的元素个数 

        virtual int size() const = 0;

        //返回索引为theIndex的元素 

        virtual T& get(int theIndex) const = 0;

        //返回元素theElement第一次出现的索引 

        virtual int indexof(const T& theElement) const = 0;

        //删除索引为theIndex的元素 

        virtual void erase(int theIndex) = 0;

        //将元素theElement插入索引为theIndex的位置 

        virtual void insert(int theIndex, const T& theElement) = 0;

        //线性表插入输出流out 

        virtual void output(ostream& out) const = 0;

};

一个抽象类的派生类，只有实现了基类的所有纯虚函数才是具体类，否则依然是抽象类不能实例化。

抽象类linearList的派生类arrayList（具体类） ：

template<class T>

class arrayList : public linearList<T>

{

    protected:

        T* element; //存储线性元素的一维数组 

        int arrayLength;    //一维数组的容量 

        int listSize;   //线性表的元素个数 

        //索引theIndex无效，则抛出异常 

        void checkIndex(int theIndex) const;

    public:

        //构造函数，复制函数和析构函数

        arrayList(int initialCapacity = 10);

        arrayList(const arrayList<T>&);

        ~arrayList()

        {

            delete [] element;

        }

        //DAT方法

        bool empty() const

        {

            return listSize == 0;

        } 

        int size() const

        {

            return listSize;    

        }

        T& get(int theIndex) const;

        int indexof(const T& theElement) const;

        void erase(int theIndex);

        void insetr(int theIndex, const T& theElement);

        void output(ostream& out) const;

        //其他方法

        int capacity() const

        {

            return arrayLength;

        }

};

类的具体实现：

template<class T>

arrayList<T>::arrayList(int initialCapacity)

{

    if(initialCapacity < 1)

    {

        ostringstream s;

        s << "初始容量 = " << initialCapacity << "必须大于零";   

        //throw illegalParameterValue(s.str());

    }

        arrayLength = initialCapacity;

        element = new T[arrayLength];

        listSize = 0;   

}

template<class T>

arrayList<T>::arrayList(const arrayList<T>& theList)

{

    arrayLength = theList.arrayLength;

    listSize = theList.listSize;

    element = new T[arrayLength];

    copy(theList.elemet, theList.element + listSize, element);

}

template<class T>

T& arrayList<T>::get(int theIndex) const

{

    checkIndex(theIndex);

    return element(theIndex); 

} 

template<class T>

int arrayList<T>::indexof(const T& theElement) const

{

    int theIndex = (int) (find(element, element + listSize, theElement) – element);

    if(theIndex == listSize)

    {

        return -1;

    }

    else

    {

        return theIndex;

    }

}

template<class T>

void arrayList<T>::erase(int theIndex)

{

    //如果引索不存在，则抛出异常 

    checkIndex(theIndex);

    //引索存在，向前移动引索大于theIndex的元素

    copy(element + theIndex + 1, element + listSize, element + theIndex);

    element[–listSize].~T();  //调用析构函数 

}

template<class T>

void arrayList<T>::insetr(int theIndex, const T& theElement) 

{

    if(theIndex < 0 || theIndex > listSize)

    {

        ostringstream s;

        s << "索引 = " << theIndex << "索引大小 = " << listSize;

        throw illeaglIndex(s.str());    

    }

    //有效引索，确定数组是否已满

    if(listSize == arrayLength) //数组长度空间已满，数组长度倍增 

    {

        changeLength1D(element, arrayLength, 2 * arrayLength) ;

        arrayLength *= 2;

    } 

    //把元素向右移动一个位置

    copy_backward(element + theIndex, element + listSize,

                  element + theIndex + 1); 

    element[theIndex] = theElement;

    listSize++;

} 

template<class T>

void arrayList<T>::output(ostream& out) const

{

    copy(element, element + listSize, ostream_iterator<T>(cout, " "));

}

template<class T>

void arrayList<T>::checkIndex(int theIndex) const

{

    //确定索引theIndex在 0 到 listSize 之间

    if(theIndex < 0 || theIndex >= listSize)

    {

        ostringstream s;

        s << "索引 = " << theIndex << "索引大小 = " << listSize;

        throw illeaglIndex(s.str());    

    }

}

//改变一个一维数组长度

template<class T>

void changeLength1D(T*& a, int oldLength, int newLength)

{

    if(newLength < 0)

        cout<< "错误" <<endl; 

    T* temp = new T[newLength]; //新数组

    int number = min(oldLength, newLength);

    copy(a, a + number, temp);

    delete [] a;

    a = temp; 

}

库定义了三种类：istringstream、ostringstream和stringstream，分别用来进行流的输入、输出和输入输出操作。

————————————————

原文链接：https://blog.csdn.net/peng_shakalaka/java/article/details/60598806