2.2.3 顺序表其它算法举例

例2-5　试设计一个算法，用尽可能少的辅助空间将顺序表中前 m 个元素和后 n 个元素进行互换，即将线性表( ,,…,,,,…, ) 改变成( ,,…,, ,,…, )。

算法 算法2.10
　　void invert( ElemType &R[], int s, int t )
　{
　　// 本算法将数组 R 中下标自 s 到 t 的元素逆置，即将
　　// （Rs,Rs+1,…,Rt-1,Rt）改变为（Rt,Rt-1,…,Rs+1,Rs）
　　for ( k=s; k<=(s+t)/2; k++ )
　　{
　　　w = R[k];
　　　R[k] = R[t-k+s];
　　　R[t-k+s] = w;
　　} // for
　} // invert

算法 算法2.11
　　void exchange ( SqList &A,int m )
　{
　　// 本算法实现顺序表中前 m 个元素和后 n 个元素的互换
　　if ( m > 0 && m < A.length ){
　　　n = A.length - m;
　　　invert( A.elem, 0, m+n-1 );
　　　invert( A.elem, 0, n-1 );
　　　invert( A.elem, n, m+n-1 );
　　}
　} // exchange

   　解题分析：
　　此题的难点在于要求用尽可能少的辅助空间。如果没有这个限制，可以另设一个和已知顺序表空间大小相同的顺序表，然后进行元素复制即可。
　
　　此题的一种比较简单的算法是，从表中第 m+1 个元素起依次插入到元素 之前。则首先需将该元素 (k=1，2，…，n)暂存在一个辅助变量中，然后将它之前的 m 个元素( ,,…, )依次后移一个位置。显然，由于对每一个 都需要移动 m 个元素，因此算法的时间复杂度为 O (m×n)。动画

　　也可采用另一种算法为，对顺序表进行三次"逆置"，第一次是对整个顺序表进行逆置，之后分别对前 n 个和后 m 个元素进行逆置。动画
　
　　由于逆置顺序表可以利"交换"相应元素进行，其时间复杂度为线性级别，则三次调用逆置算法完成的操作的时间复杂度仍然是线性级别的，即为
　　O (m+n)。