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

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

22

编写方法arrayListNoSTL::reverse,它原地颠倒线性表的元素的顺序（即在数组element中完成操作，不创建新的数组）。颠倒顺序前，线性表的第k个元素是element[k]，颠倒之后，线性表的第k个元素是element[listSize-k-1]。不要利用STL函数的reverse函数。具体实现如下：

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

算法的时间复杂度为O(n)。

23

1）编写方法arrayListNoSTL::leftShift(i)，它将线性表的元素左移i个位置。如果x=[0,1,2,3,4]，那么x.leftShift(2)的结果是x=[2,3,4]。具体实现如下：

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

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

24

在一个循环移动的操作中，线性表的元素根据给定的值，按顺时针方向移动。例如x=[0,1,2,3,4]，循环移动2的结果是x=[2,3,4,0,1]。2）编写方法arrayListNoSTL::circularShift(i)，它将线性表的元素循环移动i个位置。方法应具有线性表长度的线性复杂度。具体实现如下：

 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

调用语句x.half(),可以将x的元素隔一个删除一个。如果x.size是7，x.element[]=[2,13,4,5,17,8,29]，那么x.half()的结果是x.size()是4，x.element[] = [2,4,17,29]。如果x.size()是4，x.element[] = [2,13,4,5],那么x.half()的结果是x.size()是2，x.element[]=[2,4]。如果x为空，那么x.half()的结果也是x为空。1）编写方法arrayListNoSTL::half()。不能利用类arrayListNoSTL的其他方法。复杂度应该为O(listSize)。具体实现如下：

  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

令a和b是类arrayListNoSTL的两个对象。1）编写方法arrayListNoSTL::meld(a,b)，它生成一个新的线性表，从a的第0个元素开始交替地包含a和b的元素。如果一个表的元素取完了，就把另一个表的剩余元素附加到新表中。调用语句c.meld(a,b)使c成为合并后的表。方法应具有两个输入线性表大小的线性复杂度。具体实现如下：

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

令a和b是类arrayListNoSTL的两个对象。假设它们的元素从左到右非递减有序。1）编写方法arrayListNoSTL::merge(a,b)，它生成一个新的有序线性表，包含a和b的所有元素。归并后的线性表是调用对象*this。不要利用STL函数merge。具体实现如下：

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

算法的时间复杂度是O(a.listSize+b.listSize)。

30

1）编写方法arrayListNoSTL::split(a,b)，它生成两个线性表a和b。a包含*this中索引为偶数的元素，b包含其余的元素。具体实现如下：

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

算法的时间复杂度是O(listSize)。

完整的测试例子和程序，可以从我的Github主页下载，仓库名是DataStructureByCPlusCPlus。以上程序可能会有不足之处，欢迎伙伴们指正哦~~。下一节，我们开始介绍链式存储的线性表，链表。

参考资料

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

PS:Github网站搜索wallacedos，https://github.com/wallacedos，请大家关注我哦~~电子版《数据结构、算法与应用C++语言描述第二版》百度网盘下载链接：https://pan.baidu.com/s/1c3I6X1d5BW8upHYBHQTXRA 提取码：ikcv

不定期更新，欢迎关注！微信公众号：地震成像与模拟知乎专栏：江湖百晓生的记事本Github：wallacedos