互换顺序表中的两个子表位置

本文主要是介绍互换顺序表中的两个子表位置，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题型一：假设一个表长为n的顺序表L中有两个分别为长度s子表S和长度为r子表R，S，R不相交。设计算法，实现S和R在L中的位置互换，并且互换后S和R的元素均为正序排列。

思想：先整个表进行逆转，然后对前面的子表进行逆转，最后对后面一个子表进行逆转。（例如：可以将两个子表看成12345abcde，对前面进行逆转后为edbca54321，再对后面进行逆转为abcde54321，最后对整进行逆转为abcde12345）

代码：

void reverse(Sqlist &L,int s,int e){if(e>L.length) return;//反转顺序表的氛围为s到ewhile(s<e){//对称位置做交换 swap(L.data[s],L.data[e]);s++;e--;}
} 
bool exchage(Sqlist &L,int s,int n){//if(L.length != n){//	return false;//}reverse(L,0,n-1);//逆转整个表 reverse1(L,0,s-1);//逆转前s个元素 reverse1(L,s,n-1);//逆转后n-s个元素 return true;}
void swap(ElemType &a,ElemType &b){int temp;temp=a;a=b;b=temp
}

时间复杂度O(n)；空间复杂度O（1）

题型二：假设一个表长为n的顺序表L中有两个分别为长度s子表S和长度为r子表R，S，R不相交。设计算法，实现S和R在L中的位置互换，并且互换后S和R的元素均为逆序排列。

思想：将两个子表看成一个表，对表中的元素进行交换。首先是1与n交换，然后对2和n-1进行交换，以此类推，直到不能交换为止。

void reverse(Sqlist &L){int i=0;j=L.length-1;//开始时，i为顺序表的第一个元素 ，j为顺序表的最后一个元素 while(i<j){ElemType t = L.data[i];L.data[i] = L.data[j];L.data[j] = t;i++;j--;}} 

时间复杂度O(n)；空间复杂度O（1）

这篇关于互换顺序表中的两个子表位置的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---