线性表(二):丰富功能
在线性表（一）：数组描述一文中，我们介绍了线性表，并构建了
线性表类arrayListNoSTL，给出了线性表的最基本的功能实现。接下来，我们按照《数据结构、算法与应用C++语言描述第二版》一书第五章课后习题的要求，丰富线性表的功能函数，并给出新增函数的测试代码。废话不多说，直接开撕代码。重点提示，下文中的标号代表课后习题的标号。
05
编写一个线性表类的方法trimToSize，它使数组的长度等于max{listSize,1}。这个方法的复杂度是多少？同时测试你的代码。具体实现如下：template<class T>
void arrayListNoSTL<T>::trimToSize()
{
// 使数组的长度等于max{listSize,1}
if (arrayLength == listSize) // 若数组的长度arrayLength与线性表的长度相等，直接返回
{
return;
}
if (listSize == 0) // 若线性表的长度为0，需要将数组的长度调整为1
{
delete [] element; // 释放原数组空间
element = new T[1];
arrayLength = 1;
return;
}
// 其他情况，arrayLength大于listSize时，需要改变数组的长度
changeLength1D(element, listSize, listSize);
arrayLength = listSize;
}
06
编写线性表类的方法setSize，它使线性表的大小等于指定的大小。若线性表开始的大小小于指定的大小，则不增加元素。若线性表开始的大小大于指定的大小，则删除多余的元素。这个方法的复杂度是多少？测试你的代码。具体实现如下：template<class T>
void arrayListNoSTL<T>::setSize(int theSize)
{
if (theSize < 0 || theSize>this->capacity()) // 若参数小于0，或者大于数组的长度，需要抛异常
{
// 无效的参数theSize
ostringstream s;
s << "parameter theSize = " << theSize<< "is illegal. It must be in the range of 0 to "<<this->capacity()<<".";
throw illegalParameterValue(s.str());
}
if (listSize <= theSize)
{
return;
}
else
{
for (int i = theSize; i < listSize; i++)
{
element[i].~T(); // 调用类型T的析构函数，释放多余的线性表元素
}
listSize = theSize;
}
}
07
重载操作符[]，使得表达式x[i]返回对线性表第i个元素的引用。若线性表没有第i个元素，则抛出异常illegalIndex。语句x[i]=y和y=x[i]按以往预期的方式执行。测试你的代码。
具体实现如下：
// 重载操作符[]
template <class T>
T& arrayListNoSTL<T>::operator [](int i) const
{
checkIndex(i);
return element[i];
}
08
重载操作符==，使得表达式x==y返回true，当且仅当两个用数组描述的线性表x和y相等（即对所有的i,两个线性表的第i个元素相等）。测试你的代码。具体实现如下：template <class T>
bool arrayListNoSTL<T>::operator== (const arrayListNoSTL<T>& theList) const
{
bool ret = false;
if (this->listSize != theList.size()) // 若两个线性表的长度不相等，直接返回false
{
return ret;
}
ret = true;
for (int i = 0; i < this->listSize; i++)
{
if (this->element[i] != theList[i])
{
ret = false;
return ret;
}
}
return ret;
}
09
重载操作符！=，使得表达式x!=y返回true，当且仅当两个用数组描述的线性表x和y不等。测试你的代码。template<class T>
bool arrayListNoSTL<T>::operator!= (const arrayListNoSTL<T>& theList) const
{
return !(*this == theList);
}
10
重载操作符<，使得表达式x<y返回true，当且仅当用数组描述的线性表x按字典顺序小于用数组描述的线性表y。测试你的代码。具体代码如下：template<class T>
bool arrayListNoSTL<T>::operator< (const arrayListNoSTL<T>& theList) const
{
bool ret = false;
if (this->listSize != theList.size()) // 若两个线性表的长度不相等，直接返回false
{
return ret;
}
ret = true;
for (int i = 0; i < this->listSize; i++)
{
if (this->element[i]>=theList[i])
{
ret = false;
return ret;
}
}
return ret;
}
template<class T>
void arrayListNoSTL<T>::push_back(const T& theElement)
{
// 确定线性表的空间是否够用
if (listSize == arrayLength)
{ // 线性表的空间不够，则对原线性表的空间作扩展
changeLength1D(element, arrayLength, 2 * arrayLength);
arrayLength *= 2;
}
this->element[listSize] = theElement;
listSize++;
}
template<class T>
void arrayListNoSTL<T>::pop_back()
{
if (this->listSize == 0)
{
// 线性表已经空了
ostringstream s;
s << "the list is empty()";
throw exceptionInfo(s.str());
}
listSize--;
this->element[listSize].~T(); // 调用类型T的析构函数
}
template<class T>
void arrayListNoSTL<T>::swap(arrayListNoSTL<T>& theList)
{
int temp = 0;
temp = arrayLength;
arrayLength = theList.arrayLength;
theList.arrayLength = temp;
temp = listSize;
listSize = theList.listSize;
theList.listSize = temp;
T* p = element;
element = theList.element;
theList.element = p;
p = NULL;
}
14
编写线性表类的方法reserve(theCapacity)，它把数组的容量改变为当前容量和theCapacity的较大者。测试你的代码。具体实现如下：template<class T>
void arrayListNoSTL<T>::reserve(const int theCapacity)
{
if (this->arrayLength>= theCapacity)
{
return;
}
changeLength1D(element, listSize, theCapacity);
arrayLength = theCapacity;
}
15
编写线性表类的方法setA(theIndex, theElement)，它用元素theElement替换索引为theIndex的元素。若索引theIndex超出范围，则抛出异常。返回原来索引为theIndex的元素。测试你的代码。具体实现如下：template<class T>
T arrayListNoSTL<T>::setA(int theIndex, const T& theElement)
{
checkIndex(theIndex);
T ret = element[theIndex];
element[theIndex] = theElement;
return ret;
}
16
编写线性表类的方法clear，它使线性表为空。方法的复杂度是多少？测试你的代码。具体代码如下：template<class T>
void arrayListNoSTL<T>::clear()
{
delete [] element; // 释放原数组空间
T* temp = new T[arrayLength];
element = temp;
listSize = 0;
}
17
编写线性表类的方法removeRange，它删除指定索引范围内的所有元素。方法的复杂度是多少？测试你的代码。具体实现如下：template<class T>
void arrayListNoSTL<T>::removeRange(int start, int end)
{
if (start < 0 || end > listSize)
throw illegalIndex();
if (start >= end) // 直接返回
return;
// 移动end之后的元素
copy(element + end, element + listSize, element + start);
// 释放之后的元素
int newSize = listSize - end + start;
for (int i = newSize; i < listSize; i++)
element[i].~T();
listSize = newSize;
}
18
编写线性表类的方法lastIndexOf，它的返回值是指定元素最后出现时的索引。如果这样的元素不存在，则返回-1。方法的复杂度是多少？测试你的代码。具体的代码如下： template<class T>
int arrayListNoSTL<T>::lastIndexOf(const T& theElement) const
{
int theIndex = -1;
for (int i = listSize - 1; i >= 0; i--)
{
if (element[i] == theElement)
{
theIndex = i;
return theIndex;
}
}
return theIndex;
}
完整的测试例子和程序，可以从我的Github主页下载，仓库名是DataStructureByCPlusCPlus。以上程序可能会有不足之处，欢迎伙伴们指正哦~~。下一节，我们接着丰富线性表的功能
参考资料
萨尼.《数据结构、算法与应用C++语言描述第二版》[M].北京：机械工业出版社，2019.
PS:Github网站搜索wallacedos，https://github.com/wallacedos，请大家关注我哦~~
电子版《数据结构、算法与应用C++语言描述第二版》百度网盘下载链接：https://pan.baidu.com/s/1c3I6X1d5BW8upHYBHQTXRA 提取码：ikcv
不定期更新，欢迎关注！
微信公众号：地震成像与模拟
知乎专栏：江湖百晓生的记事本
Github：wallacedos
评论