第二章第二节综合应用

逆置算法：
算法思想：扫描顺序表L的前半部分元素，对于元素L.data[i] (o<=i

2.设计一个高效算法，将顺序表L的所有元素逆置，要求算法的空间复杂度为 O(1)。
本题代码如下：

void Reverse(SqList &L){
	for(int i =0;i  
8.已知在一维数组A[m+n]中依次存放两个线性表(a1,a2,a3,…,am)和(b1,b2,b3,…,bn)。试编写一个函数，将数组中两个顺序表的位置互换，即将(b1,b2,b3,…,bn)放在(a1,a2,a3,…,am)的前面。
 本题代码如下：
 
void Reverse(ElemType A[],int left,int right,int arraySize){
	if(left arraySize){
		return;
	}
	int mid =(right -left)/2;
	for(int i =0;i <=mid-left;i++){
		ElemType temp =L.data[i +left];
		L.data[i +left] =L.data[right -i];
		L.data[right -i] =temp;
	}
} 
void Exchange(ElemType A[],int m,int n,int arraySize){
	Reverse(A,0,m +n -1,arraySize);
	Reverse(A,0,n -1,arraySize);
	Reverse(A,n,m +n -1,arraySize);
}
 
10.【2010统考真题】设将n(n>1)个整数存放到一维数组R中。设计一个在时间和空间两方面都尽可能高效的算法。将R中保存的序列循环左移p(0 1)给出算法的基本设计思想。
 2)根据设计思想，采用C或C++或Java语言描述算法，关键之处给出注释。
 3)说明你所设计算法的时间复杂度和空间复杂度。
 
void Reverse(int R[],int from,int to){
	for(int i =0;i <(to -from +1)/2;i++){
		int temp =R.data[i +from];
		R.data[i +from] =R.data[to -i];
		R.data[to -i] =temp;
	}
} 
void Exchange(int R[],int n,int p){
	Reverse(R,0,p -1);
	Reverse(R,p,n -1);
	Reverse(R,0,n -1);
}
 
3)上述算法中三个Reverse函数的时间复杂度分别为O(p/2)、0((n-p)/2)和O(n/2)，故所设计的算法的时间复杂度为 O(n)，空间复杂度为 0(1)。