顺序表题目2

//7.有序的顺序表合并
bool mergeTwoLists(StaticSqList &a,StaticSqList &b,StaticSqList &c){
	//防止溢出 
	if(a.length+b.length > MAXSIZE)return false;
	int i=0,j=0,k=0;
	while(i<a.length && j<b.length){
		//注意是小于等于 
		if(a.data[i]<=b.data[j]){
			c.data[k++] = a.data[i++];
		}else{
			c.data[k++] = b.data[j++];
		}
	}
	while(i<a.length){
		c.data[k++] = a.data[i++];
	}
	while(j<b.length){
		c.data[k++] = b.data[j++];
	}
	c.length = k; 
	return true;
}

//8.一维数组中的两个线性表互换
void reverse(int s[],int left,int right,int ssize){
	if(left>=right || right>=ssize)return false;
	int mid = (left+right)/2;
	int temp;
	for(int i=0;i<=mid-left;i++){
		temp = s[left+i];
		s[left+i] = s[right-i];
		s[right-i] = temp;
	}
} 

void Exchange(int a[],int m,int n,int asize){
	reverse(a,0,m+n-1,asize);
	reverse(a,0,n-1,asize);
	reverse(a,n,m+n-1,asize);
}

//9.(有序)查找数值为x的元素，找到了就与后继元素交换，没找到就插入元素
bool findx(StaticSqList &L,int x){
	int mid = (L.length-1)/2;
	int left = 0;
	int right = L.length-1
	//这里是小于等于 
	while(left <= right){
		if(L.data[mid]==x) break;
		else if(x>L.data[mid])
		left = mid+1;
		else
		right = mid-1;
	}
	//缺失条件，万一没有后继元素交换干嘛？ 
	if(L.data[mid]==x && mid != L.length-1){
		int temp = L.data[mid];
		L.data[mid] = L.data[mid+1];
		L.data[mid+1] = temp;
	}
	//这里条件全错 
	if(left > right){
		for(int i=L.length-1;i>right;i--){
			L.data[i+1] = L.data[i];
		}
		L.data[right+1] = x;
	}
	
} 

//10.一维数组R循环左移P位
//逆转数组 
void reverse2(int s[],int from,int to){
	for(int i=0;i<=(from-to)/2;i++){
		int temp = s[from+i];
		s[from+i] = s[to-i];
		s[to-i] = temp;
	}
}
//输入 
void move_p(int a[],int p,int n){
	reverse2(a,0,n-1);
	reverse2(a,0,p-1);
	reverse2(a,p,n-1); 
}

//11.寻找两个等长有序序列的中位数
int findMidNum(StaticSqList &a,StaticSqList &b,StaticSqList &c){
	//先归并俩个顺序表
	int i=0,j=0,k=0;
	while(i<a.length && j<b.length){
		if(a.data[i]<=b.data[i]){
			c.data[k++] = a.data[i++];
		}else{
			c.data[k++] = b.data[j++];
		}
	} 
	while(i<a.length){
		c.data[k++] = a.data[i++];
	}
	while(j<b.length){
		c.data[k++] = b.data[j++];
	}
	//对C中的元素取中位数 
	return c.data[(a.length+b.length)/2-1];
}

//12.寻找主元素
//思路1： 开辟新的空间来存放数组 
//思路2：如下，设置一个c存放元素，遍历一遍所有元素，取count=1，如果重复就加加，不重复就减减，count<=0就换一个新的元素 
int findMainNum(int a[],int n){
	int c,count = 1;
	c = a[0];
	for(int i=1;i<n;i++){
		if(c == a[i]){
			count++;
		}else{ 
		if(count > 0){
			count--;
		}else{
			c = a[i];
			count = 1;
		}
	  } 
	} 
	//统计次数 
	if(count > 0){
		for(int i=0,count = 0;i<n;i++){
			if(a[i] == c){
				count++;
			}
		}
	}
	if(count>n/2)return c;
	else return -1;
	
} 

//13.最小正整数
int min_Num(int a[],int n){
	int i,b[n]={0};
	for(i=0;i<n;i++){
		b[a[i]-1] = 1;
	}
	for(i=0;i<n;i++){
		if(b[i]==0)break;
	}
	return i+1;
}