线性表(二):丰富功能-技术圈

在线性表（一）：数组描述一文中，我们介绍了线性表，并构建了线性表类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;
    }

算法的平均复杂度是O（n）。

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;
        }
  }

算法的平均复杂度是O（n）。

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;
  }

11编写线性表类的函数push_back，它把元素theElement插到线性表的右端。不要利用insert方法。方法的时间复杂度是多少？测试你的代码。具体的代码实现如下：

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++;
    }

算法的时间复杂度为O（1）。12编写线性表类的方法pop_back，它把线性表右端的元素删除。不要利用insert方法。方法的时间复杂度是多少？测试你的代码。具体代码如下：

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的析构函数
  }

算法的时间复杂度为O（1）。13编写线性表方法swap(theList)，它交换线性表的元素*this和theList。方法的时间复杂度是多少？测试你的代码。具体的代码如下：

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;
   }

算法的时间复杂度是O（1）。

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;
   }

方法的时间复杂度是O（1）。

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;
    }

算法的时间复杂度为O（n）。

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;
  }

算法的时间复杂度是O（n）。

完整的测试例子和程序，可以从我的Github主页下载，仓库名是DataStructureByCPlusCPlus。以上程序可能会有不足之处，欢迎伙伴们指正哦~~。下一节，我们接着丰富线性表的功能

参考资料

萨尼.《数据结构、算法与应用C++语言描述第二版》[M].北京：机械工业出版社，2019.

PS:Github网站搜索wallacedos，https://github.com/wallacedos，请大家关注我哦~~

电子版《数据结构、算法与应用C++语言描述第二版》百度网盘下载链接：https://pan.baidu.com/s/1c3I6X1d5BW8upHYBHQTXRA 提取码：ikcv

不定期更新，欢迎关注！

微信公众号：地震成像与模拟

知乎专栏：江湖百晓生的记事本

Github：wallacedos