線性表(二):豐富功能

在線性表（一）：數(shù)組描述一文中，我們介紹了線性表，并構(gòu)建了 線性表類(lèi)arrayListNoSTL，給出了線性表的最基本的功能實(shí)現(xiàn)。接下來(lái)，我們按照《數(shù)據(jù)結(jié)構(gòu)、算法與應(yīng)用C++語(yǔ)言描述第二版》一書(shū)第五章課后習(xí)題的要求，豐富線性表的功能函數(shù)，并給出新增函數(shù)的測(cè)試代碼。廢話不多說(shuō)，直接開(kāi)撕代碼。重點(diǎn)提示，下文中的標(biāo)號(hào)代表課后習(xí)題的標(biāo)號(hào)。

05

template<class T>
void arrayListNoSTL<T>::trimToSize()
    {
// 使數(shù)組的長(zhǎng)度等于max{listSize,1}
if (arrayLength == listSize)   // 若數(shù)組的長(zhǎng)度arrayLength與線性表的長(zhǎng)度相等，直接返回
      {
return;
       }

if (listSize == 0)          // 若線性表的長(zhǎng)度為0，需要將數(shù)組的長(zhǎng)度調(diào)整為1
       {
delete [] element; // 釋放原數(shù)組空間
           element = new T[1];
          arrayLength = 1;
return;
     }

// 其他情況，arrayLength大于listSize時(shí)，需要改變數(shù)組的長(zhǎng)度
      changeLength1D(element, listSize, listSize);
       arrayLength = listSize;
    }

06

template<class T>
void arrayListNoSTL<T>::setSize(int theSize)
 {
if (theSize < 0 || theSize>this->capacity())  // 若參數(shù)小于0，或者大于數(shù)組的長(zhǎng)度，需要拋異常
      {
// 無(wú)效的參數(shù)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();   // 調(diào)用類(lèi)型T的析構(gòu)函數(shù)，釋放多余的線性表元素
          }
          listSize = theSize;
        }
  }

07

重載操作符[]，使得表達(dá)式x[i]返回對(duì)線性表第i個(gè)元素的引用。若線性表沒(méi)有第i個(gè)元素，則拋出異常illegalIndex。語(yǔ)句x[i]=y和y=x[i]按以往預(yù)期的方式執(zhí)行。測(cè)試你的代碼。

具體實(shí)現(xiàn)如下：

// 重載操作符[]
template <class T>
T& arrayListNoSTL<T>::operator [](int i) const
  {
      checkIndex(i);
return element[i];
   }

08

template <class T>
bool arrayListNoSTL<T>::operator== (const arrayListNoSTL<T>& theList) const
   {
bool ret = false;
if (this->listSize != theList.size())   // 若兩個(gè)線性表的長(zhǎng)度不相等，直接返回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

template<class T> 
bool arrayListNoSTL<T>::operator!= (const arrayListNoSTL<T>& theList) const
    {
return !(*this == theList);
    }

10

template<class T>
bool arrayListNoSTL<T>::operator< (const arrayListNoSTL<T>& theList) const
 {
bool ret = false;
if (this->listSize != theList.size())   // 若兩個(gè)線性表的長(zhǎng)度不相等，直接返回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)
        {   // 線性表的空間不夠，則對(duì)原線性表的空間作擴(kuò)展
         changeLength1D(element, arrayLength, 2 * arrayLength);
          arrayLength *= 2;
       }

this->element[listSize] = theElement;
     listSize++;
    }

template<class T>
void arrayListNoSTL<T>::pop_back()
 {
if (this->listSize == 0)
     {
// 線性表已經(jīng)空了
ostringstream s;
         s << "the list is empty()";
throw exceptionInfo(s.str());
      }

     listSize--;
this->element[listSize].~T();   // 調(diào)用類(lèi)型T的析構(gòu)函數(shù)
  }

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

template<class T> 
void arrayListNoSTL<T>::reserve(const int theCapacity)
 {
if (this->arrayLength>= theCapacity)
     {
return;
       }

     changeLength1D(element, listSize, theCapacity);
        arrayLength = theCapacity;
 }

15

template<class T>
T arrayListNoSTL<T>::setA(int theIndex, const T& theElement)
   {
      checkIndex(theIndex);
      T ret = element[theIndex];
     element[theIndex] = theElement;
return ret;
 }

16

template<class T>
void arrayListNoSTL<T>::clear()
 {
delete [] element;  // 釋放原數(shù)組空間
      T* temp = new T[arrayLength];
       element = temp;
        listSize = 0;
   }

17

template<class T>
void arrayListNoSTL<T>::removeRange(int start, int end)
   {
if (start < 0 || end > listSize)
throw illegalIndex();

if (start >= end) // 直接返回
return;

// 移動(dòng)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

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

參考資料

薩尼.《數(shù)據(jù)結(jié)構(gòu)、算法與應(yīng)用C++語(yǔ)言描述第二版》[M].北京：機(jī)械工業(yè)出版社，2019.

PS:Github網(wǎng)站搜索wallacedos，https://github.com/wallacedos，請(qǐng)大家關(guān)注我哦~~

電子版《數(shù)據(jù)結(jié)構(gòu)、算法與應(yīng)用C++語(yǔ)言描述第二版》百度網(wǎng)盤(pán)下載鏈接：https://pan.baidu.com/s/1c3I6X1d5BW8upHYBHQTXRA 提取碼：ikcv

不定期更新，歡迎關(guān)注！

微信公眾號(hào)：地震成像與模擬

知乎專(zhuān)欄：江湖百曉生的記事本

Github：wallacedos