[数据结构与算法]数据结构之线性表—数组描述

定义

线性表（linear list）：零个或多个数据元素的有限序列。

线性表也称有序表（ordered list），它的每一个实例都是元素的一个有序集合。每一个实例的形式为（$e_0$, $e_1$, …, $e_n{?}_1$），其中n是有穷自然数，是线性表的长度或大小，$e_i$是线性表的元素，i是元素$e_i$的索引。

元素本身的结构与线性表的结构无关，在较复杂的线性表中，一个数据元素可以由若干个数据项组成。

当n = 0时，线性表称为空表；当n > 0时，$e_0$是线性表的第0个元素或首元素，$e_n{?}_1$是线性表的最后一个元素。可以认为$e_i{?}_1$先于$e_i$，$e_i$先于$e_i{+}_1$，称$e_i{?}_1$是$e_i$的直接前驱元素，称$e_i{+}_1$是$e_i$的直接后继元素。除了这种先后关系之外，线性表不再有其他关系。

?

抽象数据类型（ADT）linearList

ADT linearList
{
   Data
   	有限个元素的有序集合
   Operation
   	empty(): 若表空，则返回true，否则返回false
   	size(): 返回线性表的大小（即元素个数）
   	get(index): 返回线性表中索引为index的元素
       indexOf(x): 返回线性表中第一次出现的x的索引。若x不存在，则返回-1
       erase(index): 删除索引为index的元素，索引大于index的元素其索引减1
       insert(index, x): 把x插入线性表中索引为index的位置上，索引大于等于index的元素其索引加1
       output(): 从左到右输出表元素
}

?

抽象类 linearList

对上面的抽象数据类型ADT linearList，除了用上面的非形式语言方法来描述，我们还可以用抽象类来描述。

template<class T>
class linearList
{
public:
	virtual ~linearList() {};

	virtual bool empty() const = 0;  // 当且仅当线性表为空时返回true

	virtual int size() const = 0; // 返回线性表的元素个数

	virtual T& get(int theIndex) const = 0; // 返回索引为theElement的元素

	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; // 把线性表插入输出流out
};

?

数组描述的线性表

在数组描述中，用数组来存储线性表的元素。假定使用一个一维数组element来存储线性表的元素，arrayLength表示数组长度或容量。数组的每一个位置都可以存储线性表的一个元素，我们需要一个映射，使线性表的一个元素对应数组的一个位置。

?

要创建一个数组类，以实现抽象数据类型linearList，必须首先选择数组element的类型和数组长度。使用模板类可以很好地解决第一个问题，使用动态数组可以很好地解决第二个问题，首先按照用户估计的长度创建数组，然后在数组空间不足的情况下，动态地增加数组长度。

?

变长一维数组

一维数组a，线性表元存储在a[0:n-1]中。要增加或减少这个数组的长度，首先要建立一个具有新长度的数组，然后把数组a的元素复制到这个新数组，最后改变数组a的值，使它能够引用新数组。

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];				// 新数组
	int number = min(oldLength, newLength); // 需要复制的元素个数
	copy(a, a + oldLength, temp);
	delete[] a;						// 释放老数组的内存空间
	a = temp;
}

创建一个长度为m的数组所需的时间为O(1)。

当数组满而需要加大数组长度时，数组长度常常是要加倍的，这个过程称为数组倍增（array doubling）。数组倍增的时间，从渐进意义上考量，不会大于元素插入的总时间。

?

类 arrayList

我们定义一个C++抽象类linearList的派生类arrayList，它利用映射公式：location(i) = i实现ADT linearList，arrayList是一个具体类，所以它必须实现抽象类linearList的所有方法。不仅如此，它还包含基类linearList没有声明的方法，例如，capacity和checkIndex。

类arrayList的定义

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; }        // 返回数组element当前的长度
protected:
	void checkIndex(int theIndex) const;  // 若索引theIndex无效，则抛出异常
	T* element;			// 存储线性表元素的一维数组
	int arraylength;	// 一维数组的容量
	int listSize;		// 线性表的元素个数
};

?

类arrayList的构造函数

template<class T>
arrayList<T>::arrayList(int initialCapacity)
{// 构造函数
	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)
{// 复制构造函数
	arrayLength = theList.arraylength;
	listSize = theList.listSize;
	element = new T[arraylength];
	copy(theList.element, theList.element + listSize, element);
}

?

类arrayList—checkIndex、get、indexOf函数的实现

template<class T>
void arrayList<T>::checkIndex(int theIndex) const 
{// 确定索引theIndex在0和listSize - 1之间
	if (theIndex < 0 || theIndex >= listSize)
	{
		ostringstream s;
		s << "index = " << theIndex << " size = " << listSize;
		throw illegalParameterValue(s.str());
	}
}

template<class T>
T& arrayList<T>::get(int theIndex) const
{// 返回索引为theIndex的元素
	// 若此元素不存在，则抛出异常
	checkIndex(theIndex);
	return element[theIndex];
}

template<class T>
int arrayList<T>::indexOf(const T& theElement) const
{// 返回元素theElement第一次出现时的索引
	// 若该元素不存在，则返回-1

	// 查找元素 theElement
	int theIndex = (int)(find(element, element + listSize, theElement) - element);

	// 确定元素theElement是否找到
	return (theIndex == listSize) ? -1 : theIndex;
}

?

删除一个元素

为了从线性表中删除索引为theIndex的元素，首先要确定线性表包含这个元素，然后删除这个元素。若没有这个元素，则抛出类型为illegalIndex的异常。

template<class T>
void arrayList<T>::erase(int theIndex)
{//删除索引为theIndex的元素，若该元素不存在，则抛出异常
	checkIndex(theIndex);
	
	// 有效索引，移动其索引大于theIndex的元素
	copy(element + theIndex + 1, element + listSize, element + theIndex);

	element[--listSize].~T(); // 调用析构函数(显示调用析构）
}

?

插入一个元素

要在表中索引为theIndex的位置上插入一个新元素，首先把索引从theIndex到listSize-1的元素向右移动一个位置，然后将新元素插入索引为theIndex的位置，最后将变量listSize的值加1，copy_backward函数时从最右端开始移动元素的。

template<class T>
void arrayList<T>::insert(int theIndex, const T& theElement)
{// 在索引theIndex处插入元素theElement
	checkIndex(theIndex);
	
	if (listSize == arrayLength)
	{// 若数组空间已满，数组长度倍增
		changeLength1D(element, arrayLength, 2 * arrayLength);
		arrayLength *= 2;
	}
	// 把元素向右移动一个位置
	copy_backward(element + theIndex, element + listSize, element + listSize + 1);

	element[theIndex] = theElement;
	listSize++;
}