线性表(三):丰富功能

在线性表（二）：丰富功能一文中，我们按《数据结构、算法与应用C++语言描述第二版》第五章课后习题的要求丰富了线性表类arrayListNoSTL的功能。今天，我们完成剩余部分。下一篇，给大家介绍链式存储的线性表，即链表。废话不多说，直接开撕代码。重点提示，下文中的标号代表课后习题的编号。

22

   template<class T>
void arrayListNoSTL<T>::reverse()
 {
for (int i = 0; i < (listSize / 2); i++)
      {
          swapElement(element + i, element + listSize - i - 1);
       }
  }

23

    template<class T>
void arrayListNoSTL<T>::leftShift(int i)
   {
if (i <0 || i>listSize)
      {
// 无效的参数i
ostringstream s;
          s << "parameter i = " <<i<< "is illegal. It must be in the range of 0 to " << listSize<< ".";
throw illegalParameterValue(s.str());
      }

int newSize = 0;
if (i<= listSize)
      {
          newSize = listSize - i;
            copy(element + i, element + listSize, element);
        }

// 剩余元素作析构
for (int i = newSize; i < listSize; i++)
          element[i].~T();

      listSize = newSize;
    }

24

 template<class T>
void arrayListNoSTL<T>::circularShift(int i)
   {
if (i<0 || i>listSize)
       {
// 无效的参数i
ostringstream s;
          s << "parameter i = " << i << "is illegal. It must be in the range of 0 to " << listSize << ".";
throw illegalParameterValue(s.str());
       }

     T* s = new T[i];    // 创建辅助数组s
for (int k = 0; k < i; k++)
        {
          s[k] = element[k];
     }

for (int k = 0; k < (listSize - i); k++)
        {
          element[k] = element[k + i];
       }

for (int k = (listSize - i); k < listSize; k++)
        {
          element[k] = s[k - listSize + i];
      }
delete[]s;
        s = NULL;
   }

25

  template<class T>
void arrayListNoSTL<T>::half()
    {
int newListSize = (listSize + 1) / 2;
for (int i = 0; i < newListSize; i++)
     {
          element[i] = element[2 * i];
        }

for (int i = newListSize; i < listSize; i++)
       {
          element[i].~T();
       }

     listSize = newListSize;
    }

28

template<class T>
void arrayListNoSTL<T>::meld(const arrayListNoSTL<T>& a, const arrayListNoSTL<T>& b)
  {
delete[]element;
int aListSize = a.listSize;
int bListSize = b.listSize;

int newListSize = aListSize + bListSize;

// 确定线性表的空间是否够用
if (newListSize> arrayLength)
        {
          arrayLength = newListSize;
     }

     listSize = newListSize;
        element = new T[arrayLength];

if (aListSize == bListSize)
       {
for (int i = 0; i < aListSize; i++)
          {
              element[2*i] = a.element[i];
                element[2 * i + 1] = b.element[i];
           }
      }
else if (aListSize > bListSize)
     {
for (int i = 0; i < bListSize; i++)
          {
              element[2 * i] = a.element[i];
              element[2 * i + 1] = b.element[i];
           }
          copy(a.element+bListSize, a.element+aListSize, element+(2 * bListSize));
        }
else if (aListSize < bListSize)
     {
for (int i = 0; i < aListSize; i++)
          {
              element[2 * i] = a.element[i];
              element[2 * i + 1] = b.element[i];
           }
          copy(b.element + aListSize, b.element + bListSize, element + (2 * aListSize));
      }
else
      {
// 触发未定义的异常
ostringstream s;
            s <<"the program has triggered an undefined exception...";
throw undefinedException(s.str());
      }
  }

29

    template<class T>
void arrayListNoSTL<T>::merge(const arrayListNoSTL<T>& a, const arrayListNoSTL<T>& b)
   {
int ca = 0;                       // 线性表a的游标
int cb = 0;                       // 线性表b的游标
int ct = 0;                       // 当前线性表的游标

// 释放当前线性表，并为当前线性表重新申请内存空间
delete[] element;
       arrayLength = a.listSize + b.listSize;
     element = new T[arrayLength];

// 由a到b作归并
while ((ca < a.listSize) && (cb < b.listSize))
if (a.element[ca] <= b.element[cb])
               element[ct++] = a.element[ca++];
else
               element[ct++] = b.element[cb++];

// 处理剩余元素
      copy(a.element + ca, a.element + a.listSize, element + ct);
        ct += a.listSize - ca;
     copy(b.element + cb, b.element + b.listSize, element + ct);
        ct += b.listSize - cb;

        listSize = ct;
 }

30

   template<class T>
void arrayListNoSTL<T>::split(arrayListNoSTL<T>& a, arrayListNoSTL<T>& b)
 {
int aListSize = (listSize + 1) / 2;
int bListSize = listSize - aListSize;
delete[]a.element;
delete[]b.element;

int aArrayLength = aListSize > a.arrayLength ? aListSize : a.arrayLength;
int bArrayLength = bListSize > b.arrayLength ? bListSize : b.arrayLength;

      a.element = new T[aArrayLength];
        b.element = new T[bArrayLength];
        a.arrayLength = aArrayLength;
      b.arrayLength = bArrayLength;
      a.listSize = aListSize;
        b.listSize = bListSize;

for (int i = 0; i < aListSize; i++)
       {
          a.element[i] = element[2 * i];
      }

for (int i = 0; i < bListSize; i++)
     {
          b.element[i] = element[2 * i + 1];
       }
  }

参考资料