列表

发表于 分类于

根据是否修改数据结构，所有操作分为两类方式

  • 静态：仅读取，数据结构的内容和组成不变
  • 动态：需写入，数据结构的局部或整体将改变

与操作方式相对应的，数据元素的存储和组织形式也分为两种

  • 静态：数据空间整体创建和销毁
  • 动态：为各个数据元素动态地分配和回收的物理空间，相邻元素记录彼此的物理地址，在逻辑上形成一个整体，可支持高效的动态操作。

列表是采用动态存储的典型结构，循位置访问，通过节点之间的相互引用找到特定的节点。借助列表设计算法时，应更多地借助逻辑上相邻元素之间的位置索引。

无序列表

循秩访问

模仿向量的循秩访问方式，重载下标操作符，时间复杂度$O(r)$，线性正比于待访问的秩

以均匀分布为例，单次访问的期望复杂度为$\displaystyle\frac {1+2+3+4+…+n} n = (n+1)/2= o(n)$

查找

在节点p(可能为尾节点)的n个真前驱中找到等于e的最后者

1
2
3
4
5
ListNodePosi(T) List<T>::find ( T const& e, int n, ListNodePosi(T) p ) const {
   while ( 0 < n-- ) //（0 <= n <= rank(p) < _size）对于p的最近的n个前驱，从右向左
      if ( e == ( p = p->pred )->data ) return p; //逐个比对，直至命中或范围越界
   return NULL; //p越出左边界意味着区间内不含e，查找失败
} //失败时，返回NULL

插入

插入时间复杂度为$ O(1)$

1
2
3
4
5
ListNodePosi(T) ListNode<T>::insertAsPred ( T const& e ) {
   ListNodePosi(T) x = new ListNode ( e, pred, this ); //创建新节点
   pred->succ = x; pred = x; //设置正向链接
   return x; //返回新节点的位置
}

删除

删除时间复杂度同样为$ O(1)$

1
2
3
4
5
6
template <typename T> T List<T>::remove ( ListNodePosi(T) p ) { //删除合法节点p，返回其数值
   T e = p->data; //备份待删除节点的数值（假定T类型可直接赋值）
   p->pred->succ = p->succ; p->succ->pred = p->pred; //后继、前驱
   delete p; _size--; //释放节点，更新规模
   return e; //返回备份的数值
}

去重

1
2
3
4
5
6
7
8
9
10
template <typename T> int List<T>::deduplicate() { //剔除无序列表中的重复节点
   if ( _size < 2 ) return 0; //平凡列表自然无重复
   int oldSize = _size; //记录原规模
   ListNodePosi(T) p = header; Rank r = 0; //p从首节点开始
   while ( trailer != ( p = p->succ ) ) { //依次直到末节点
      ListNodePosi(T) q = find ( p->data, r, p ); //在p的r个（真）前驱中查找雷同者
      q ? remove ( q ) : r++; //若的确存在，则删除之；否则秩加一
   } //assert: 循环过程中的任意时刻，p的所有前驱互不相同
   return oldSize - _size; //列表规模变化量，即被删除元素总数
}

在最好情况下仅需$O(n)$时间,当所有元素均雷同时，仍然需要执行$O(n)$次迭代，每一步只需要$O(1)$时间。当前节点p始终只有一个前驱，因此find()只需常数时间。

算法最坏情况即为所有元素均彼此互异，当前节点p的前驱数目将随着迭代的推进线性地递增，平均为$O(n)$,算法总体复杂度为$O(n^2)$。

有序列表

唯一化

1
2
3
4
5
6
7
8
9
template <typename T> int List<T>::uniquify() { //成批剔除重复元素，效率更高
   if ( _size < 2 ) return 0; //平凡列表自然无重复
   int oldSize = _size; //记录原规模
   ListNodePosi(T) p = first(); ListNodePosi(T) q; //p为各区段起点，q为其后继
   while ( trailer != ( q = p->succ ) ) //反复考查紧邻的节点对(p, q)
      if ( p->data != q->data ) p = q; //若互异，则转向下一区段
      else remove ( q ); //否则（雷同），删除后者
   return oldSize - _size; //列表规模变化量，即被删除元素总数
}

只需遍历整个列表一趟，整体运行时间为$ O(n)$，线性正比于列表原先的规模。

查找

1
2
3
4
5
6
7
ListNodePosi(T) List<T>::search ( T const& e, int n, ListNodePosi(T) p ) const {
// assert: 0 <= n <= rank(p) < _size
   while ( 0 <= n-- ) //对于p的最近的n个前驱，从右向左逐个比较
      if ( ( ( p = p->pred )->data ) <= e ) break; //直至命中、数值越界或范围越界
// assert: 至此位置p必符合输出语义约定——尽管此前最后一次关键码比较可能没有意义（等效于与-inf比较）
   return p; //返回查找终止的位置
} //失败时，返回区间左边界的前驱（可能是header）——调用者可通过valid()判断成功与否

与无序列表的find()不同，有序列表返回的是不大于e的最后者，而无序列表返回的是等于e的最后者。search多了一次与头哨兵的比较，与查找失败返回NULL语义吻合。两者最好情况下运行时间$O(1)$，最坏情况下为$O(n)$ ；等概率时平均$O(n)$，正比于区间宽度。

为何未能借助有序性提高查找效率，实现不当，还是根本不可能？

按照列表的循位置访问特性，物理存储位置与逻辑次序无关，依据秩的随机访问无法高效实现，而只能根据元素间的引用顺序访问。循位置访问效率较低，故查找效率同样不高。

选择排序

在起泡排序中，每趟扫描交换均需要$O(n)$时间，$O(n)$次比较和$O(n)$次交换，$O(n)$次交换中存在大量无谓的逆向移动，所以整体效率低下。选择排序将序列划分为无序前缀和有序前缀两部分；此外，还要求前缀不大于后缀。每次从前缀中选择最大者，并作为最小元素转移至后缀中。

选择排序适用于向量与列表在内的任何序列结构。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
template <typename T> //列表的选择排序算法：对起始于位置p的n个元素排序
void List<T>::selectionSort ( ListNodePosi(T) p, int n ) { //valid(p) && rank(p) + n <= size
   ListNodePosi(T) head = p->pred; ListNodePosi(T) tail = p;
   for ( int i = 0; i < n; i++ ) tail = tail->succ; //待排序区间为(head, tail)
   while ( 1 < n ) { //在至少还剩两个节点之前，在待排序区间内
      ListNodePosi(T) max = selectMax ( head->succ, n ); //找出最大者（歧义时后者优先）
      insertB ( tail, remove ( max ) ); //将其移至无序区间末尾（作为有序区间新的首元素）
      tail = tail->pred; n--;
   }
}
ListNodePosi(T) List<T>::selectMax ( ListNodePosi(T) p, int n ) {
   ListNodePosi(T) max = p; //最大者暂定为首节点p
   for ( ListNodePosi(T) cur = p; 1 < n; n-- ) //从首节点p出发，将后续节点逐一与max比较
      if ( !lt ( ( cur = cur->succ )->data, max->data ) ) //若当前元素不小于max，则
         max = cur; //更新最大元素位置记录
   return max; //返回最大节点位置
}

insertB ( tail, remove ( max ) ); 涉及节点存储空间的动态释放与申请，所需时间操作比一般操作高出一个数量级，故可改为swap(tail->pres->data,max->data)。

若将!lt ( ( cur = cur->succ )->data, max->data ) 改为lt ( max->data， ( cur = cur->succ )->data ))

采用比较器!lt()或ge()等效于后者优先，如此即可保证重复元素在列表中的次序与其插入次序一致。若改为lt()雷同元素的次序将会完全颠倒，稳定性得不到保证。

性能分析

选择排序由$n$步迭代构成，其运行时间取决于各步迭代中查找及插入操作的效率。insertB()和remove()均只需$O(1)$时间。selectMax()每次必须遍历整个无序前缀，时间线性正比于前缀长度，总计为$O(n^2)$。

但是无论输入序列中各元素相对大小如何，以上$n$次selectMax()调用累计耗时总是$\Theta(n^2)$，最好情况下和最坏情况下复杂度相同。其中元素移动操作远远少于起泡排序，$ \Theta (n^2)$主要来自于元素比较操作。

循环节

任何一个序列A[0,n)都可以分解为若干循环节

任何一个序列A[0,n),都对应于一个有序队列S[0,n)

元素A[k]所属的循环节是：

1
A[k],A[r(k)],A[r(r(k))],...,A[r(...r(k)...)]=A[k]

每个循环节，长度不超过n,循环节之间没有重复元素

选择排序每迭一步，M所属循环节恰好减少一个单位，M脱离原来的循环节，自成一个长度为1的循环节，其余循环节保持不变。

M已经就位，无需交换，这样的情况会出现几次

有多少个循环节就出现多少次，最大值为$O(n)$，期望值为$O(logn)$

插入排序

插入排序算法可简要描述为：

始终将序列视为两个部分，有序的前缀S和无序的后缀U，反复地对将后缀中的首元素取出并转移至前缀中。

插入排序适用于向量与列表在内的任何序列结构。

1
2
3
4
5
6
7
template <typename T> //列表的插入排序算法：对起始于位置p的n个元素排序
void List<T>::insertionSort ( ListNodePosi(T) p, int n ) { //valid(p) && rank(p) + n <= size
   for ( int r = 0; r < n; r++ ) { //逐一为各节点
      insertA ( search ( p->data, r, p ), p->data ); //查找适当的位置并插入
      p = p->succ; remove ( p->pred ); //转向下一节点
   }
}

$n$次迭代，每次$O(r+1)$

性能分析

仅使用$O(1)$辅助空间，属于就地算法

不要求所有数据在算法运行时就完备，属于在线算法

具有输入敏感性

  • 最好情况：完全(或几乎)有序

每次迭代只需$1$次比较，$0$次交换，只需$O(n)$时间

  • 最坏情况：完全或几乎逆序

第k次迭代，需$O(k)$次比较，1次交换，累计$O(n^2)$时间

优化的可能

在有序前缀中的查找定位可以考虑用向量的二分查找，而不是顺序查找。

假定序列中的n个元素的数值为独立均匀的随机分布，则

列表的插入排序算法平均需要$n^2/4=O(n^2)$次元素比较操作

平均意义下的比较操作次数，也就是概率意义下的比较操作期望次数。

比较操作期望次数，应等于各步迭代中比较操作的次数。

search()过程涉及的比较操作次数，应从$0$到$n-1$按照算术级数线性递增，故其总和应为
$$
\sum _{i=1} ^{n-1} (k/2)=\frac {n(n-1)} {4} =O(N^2)
$$

向量的插入排序算法平均需要$n^2/4=O(n^2)$次元素移动操作

向量中插入排序的search()接口可通过二分查找从线性优化至$O(log n)$,但是确定位置后将元素插入已排序的子序列却不得不移动个$O(n)$节点，平均需要$n^2/4=O(n^2)$次元素移动操作。

在$n$次迭代中，平均有多少次无需交换呢？

无需移动的元素期望数目，等于各步迭代中待插入元素无需移动的概率之和。

对于任意$k\in[0,n)$,当前A[k]的$k$个前驱应该也已构成一个有序的子序列A[0,k)。若A[k]无需移动即使得A[0,k]仍为有序子序列，则其充要条件是A[k]在A[0,k]中为最大元素。
$$
\sum _{i=0} ^{n-1} 1/(k+1)=\sum _{i=1} ^{n} (1/k)= \Theta(logn)
$$

序列中元素A[i]和A[j]若满足i<j,且A[i]>A[j]，则称为一个逆序对，若所有逆序对的间距均不超过$k$,则运行时间为$O(kn)$

算法进入到A[k]那步迭代时，该元素在输入序列中的所有前驱都应该业已构成一个有序序列A[0,j)。既然至多$k$个位置与A[j]构成逆序对，故查找过程search() 至多扫描其中k个元素，即可确定合适的插入位置，对应的时间不超过$O(k)$。实际上，每一步都具有以上性质，所以累计运行时间不超过$O(kn)$。
当$k$为常数时，插入排序可在线性时间内完成。

若共有$I$个逆序对，则关键码比较次数不超过$O(I)$

这里定义的每一逆序对，均涉及两个元素，为了便于分析，统一归入后者。因此，所有元素逆序前驱的数目总和应恰好等于$I$。每个元素涉及到的比较操作的数目，应恰好等于逆序前驱的数目。整个算法执行过程中所执行的比较操作总数应恰好等于所有元素的逆序前驱的数目总和。

若共有$I$个逆序对，则运行时间$O(n+I)$

由以上分析，算法过程中消耗于比较操作的时间可由$O(I)$界定，而消耗于移动操作的时间则由$O(n)$界定,二者累计即为$O(n+I)$。既然此处实际的运行时间更多地取决于逆序对的数目，而不仅仅是输入序列的长度，故插入排序亦属于所谓的输入敏感的算法。若将失败比较操作同样归入比较操作的范畴，则还有一个$O(n)$项，在渐进意义下这一因素可忽略。

归并排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
template <typename T> //列表的归并排序算法：对起始于位置p的n个元素排序
void List<T>::mergeSort ( ListNodePosi(T) & p, int n ) { //valid(p) && rank(p) + n <= size
   if ( n < 2 ) return; //若待排序范围已足够小，则直接返回；否则...
   int m = n >> 1; //以中点为界
   ListNodePosi(T) q = p; for ( int i = 0; i < m; i++ ) q = q->succ; //均分列表
   mergeSort ( p, m ); mergeSort ( q, n - m ); //对前、后子列表分别排序
   merge ( p, m, *this, q, n - m ); //归并
} //注意：排序后，p依然指向归并后区间的（新）起点
template <typename T> //有序列表的归并：当前列表中自p起的n个元素，与列表L中自q起的m个元素归并
void List<T>::merge ( ListNodePosi(T) & p, int n, List<T>& L, ListNodePosi(T) q, int m ) {
// assert:  this.valid(p) && rank(p) + n <= size && this.sorted(p, n)
//          L.valid(q) && rank(q) + m <= L._size && L.sorted(q, m)
// 注意：在归并排序之类的场合，有可能 this == L && rank(p) + n = rank(q)
   ListNodePosi(T) pp = p->pred; //借助前驱（可能是header），以便返回前 ...
   while ( 0 < m ) //在q尚未移出区间之前
      if ( ( 0 < n ) && ( p->data <= q->data ) ) //若p仍在区间内且v(p) <= v(q)，则
         { if ( q == ( p = p->succ ) ) break; n--; } //p归入合并的列表，并替换为其直接后继
      else //若p已超出右界或v(q) < v(p)，则
         { insertB ( p, L.remove ( ( q = q->succ )->pred ) ); m--; } //将q转移至p之前
   p = pp->succ; //确定归并后区间的（新）起点
}

为节省每次子列表的划分时间，令$m=min(c,n/2)$，则总体复杂度反而会上升至$O(n^2)$

$T(n)=T(c)+T(n-c)+O(n)$
$T(n)=O(n^2)$

游标实现

在某些特定的语言环境中不支持指针或不支持动态空间分配，此时用线性数组，以游标的形式模拟列表

elem[]:对外可见的数据项

link[]:数据项之间的引用

维护逻辑上互补的列表data和free

data即为数据链表的首元素的秩，通过link索引至下一元素

free即为空闲链表首元素的秩，通过link索引至下一元素

具体实现

初始化

1
2
3
4
5
6
7
8
CursorList ( int c = DEFAULT_CAPACITY ) { //容量为c
      _link = new Rank[_capacity = c]; //游标指针向量
      _elem = new T[_capacity = c]; memset ( _elem, 0, c * sizeof ( T ) ); //数据向量
      _data = -1; _size = 0; //数据链表初始为空
      _free = 0; //空闲链表由所有单元依次串接而成
      for ( Rank i = 0; i < c - 1; i++ ) _link[i] = i + 1;
      _link[c - 1] = -1;
   }

插入元素

1
2
3
4
5
6
Rank insert ( T const& e ) { //插入元素
      assert ( 0 <= _free );
      Rank k = _free; _free = _link[k]; _elem[k] = e;
      _link[k] = _data; _data = k;
      _size++; return k;
   }

删除元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Rank find ( T const& e ) const { //查找
     Rank i = _data; //从数据链表起点出发
     while ( ( 0 <= i ) && ( e != _elem[i] ) ) i = _link[i]; //依次比对
     return i;
  }
Rank remove ( Rank k ) { //删除秩为k的元素
     assert ( 0 <= k ); //此前经查找并确认k合法
     if ( _data == k ) //若[k]为首节点
        _data = _link[k];
     else { //否则
        Rank i = _data; while ( k != _link[i] ) i = _link[i];
        _link[i] = _link[k];
     }
     _link[k] = _free; _free = k; _elem[k] = 0;
     _size--; return k;
  }

先调用find查找删除元素的秩，再调用remove删秩为k的元素。约定初始化或删除后元素均置为0。