数据结构与算法——线性表（数组描述）

前言

表ADT常用的描述方法有两种：数组描述和链式描述，在STL中分别有容器vector和list与之对应。本文重点讨论线性表的数组描述，通过利用C++语言从零开始实现数组描述的线性表，对其进行学习（所使用的函数名和签名与STL代码相同）。线性表也称有序表，其每一个实例均为元素的一个有序集合。元素被看做原子，其本身的结构与线性表的结构无关。线性表除了先后关系的有序性之外，不再有其他关系。表ADT

线性表（数组描述）C++实现

1、抽象类linearList

template<class T> class linearList { public: virtual ~linearList() {}; virtual bool empty() const = 0; // 判断是否为空 virtual int size() const = 0; //返回线性表的元素个数 virtual T& get(int theIndex) const = 0; // 返回索引为theIndex的元素 virtual int indexOf(const T& theElement) const = 0; // 返回元素theElement第一次出现的索引 virtual void erase(int theIndex) = 0; // 删除索引为theIndex的元素 virtual void insert(int theIndex, const T& theElement) = 0; // 吧theElement插入到线性表中所因为theIndex的位置上 virtual void output(ostream& out) const = 0; //把线性表插入输出流 };

注：抽象类不能实例化，但是数组表和链表均继承自抽象类linearList。

2、数组类

2.1 数组动态调整实现 创建一个数组类，以实现抽象数据类型linearList，必须选择element的类型和数组长度。模板类可以解决第一个问题，动态数组解决第二个问题。 改变一个数组长度的代码实现：

template<class T> void changeLength1D(T*& a, int oldLength, int newLength) { if (newLength < 0) throw illegalParameterValue("new length must be >= 0"); T* temp = new T[newLength]; // new array int number = min(oldLength, newLength); // number to copy copy(a, a + number, temp); delete[] a; // deallocate old memory a = temp; }

2.2 数组类arrayList实现 arrayList是linearList的派生类，必须实现linearList中的所有方法，还可包含抽象类中没有的方法：capacity给出element的长度、checkIndex确定一个元素在0~listSize-1内的索引。

template<class T> class arrayList : public linearList<T> { public: // 构造函数、复制函数、析构函数 arrayList(int initialCapacity = 10); arrayList(const arrayList<T>&); ~arrayList() { delete[] element; } // ADT 方法 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 insert(int theIndex, const T& theElement); void output(ostream& out) const; // 其他方法 int capacity() const { return arrayLength; } protected: void checkIndex(int theIndex) const; // theIndex无效则抛出异常 T* element; // 存储线性表元素的一维数组 int arrayLength; //一维数组的容量 int listSize; // 线性表元素个数 };

arrayList类方法的实现代码：

template<class T> arrayList<T>::arrayList(int initialCapacity) {// Constructor. if (initialCapacity < 1) { ostringstream s; s << "Initial capacity = " << initialCapacity << " Must be > 0"; throw illegalParameterValue(s.str()); } arrayLength = initialCapacity; element = new T[arrayLength]; listSize = 0; } template<class T> arrayList<T>::arrayList(const arrayList<T>& theList) {// Copy constructor. arrayLength = theList.arrayLength; listSize = theList.listSize; element = new T[arrayLength]; copy(theList.element, theList.element + listSize, element); } template<class T> void arrayList<T>::checkIndex(int theIndex) const {// Verify that theIndex is between 0 and listSize - 1. if (theIndex < 0 || theIndex >= listSize) { ostringstream s; s << "index = " << theIndex << " size = " << listSize; throw illegalIndex(s.str()); } } template<class T> T& arrayList<T>::get(int theIndex) const {// Return element whose index is theIndex. // Throw illegalIndex exception if no such element. checkIndex(theIndex); return element[theIndex]; } template<class T> int arrayList<T>::indexOf(const T& theElement) const {// Return index of first occurrence of theElement. // Return -1 if theElement not in list. // search for theElement int theIndex = (int)(find(element, element + listSize, theElement) - element); // check if theElement was found if (theIndex == listSize) // not found return -1; else return theIndex; } template<class T> void arrayList<T>::erase(int theIndex) {// Delete the element whose index is theIndex. // Throw illegalIndex exception if no such element. checkIndex(theIndex); // valid index, shift elements with higher index copy(element + theIndex + 1, element + listSize, element + theIndex); element[--listSize].~T(); // invoke destructor } template<class T> void arrayList<T>::insert(int theIndex, const T & theElement) {// Insert theElement so that its index is theIndex. if (theIndex < 0 || theIndex > listSize) {// invalid index ostringstream s; s << "index = " << theIndex << " size = " << listSize; throw illegalIndex(s.str()); } // valid index, make sure we have space if (listSize == arrayLength) {// no space, double capacity changeLength1D(element, arrayLength, 2 * arrayLength); arrayLength *= 2; } // shift elements right one position copy_backward(element + theIndex, element + listSize, element + listSize + 1); element[theIndex] = theElement; listSize++; } template<class T> void arrayList<T>::output(ostream & out) const {// Put the list into the stream out. copy(element, element + listSize, ostream_iterator<T>(cout, " ")); } // overload << template <class T> ostream& operator<<(ostream & out, const arrayList<T> & x) { x.output(out); return out; }

3、总结

上述实现了最基本的arrayList类，可以为其添加迭代器以适用于STL的迭代器算法，这个迭代器被定义为类arrayList的公有成员。vector描述：STL的vector没有一个构造函数与arrayList的构造函数等价，也没有名为get, indexOf, output等方法，可以定义一个vectorList类，用vector描述线性表，其方法签名和操作与linearList相同。