题目

编写一个算法实现两个有序（非递减有序）顺序表合并成为一个顺序表，假设第一个顺序表存储在A[]中，第二个顺序表存储在B[]中，A[]和B[]的长度为maxSize，maxSize足够大，合并后的结果放在A[]中，不另设新的顺序表存储空间。

分析

实现顺序表A和B的合并过程：从A和B的最好一个元素逐个向前进行比较，将较大的元素先定位在A[]中，直到合并过程结束。

代码

核心代码：

void merge(int A[],int &An,int B[],int Bn){
	for(int i=Bn-1;i>=0;i--){
		for(int j=An-1;j>=0;j--){
			if(B[i]>A[j]){
				int q;
				for(q=An;q>j;q--){
					A[q]=A[q-1];
				}
				A[q+1]=B[i];
				An++;
				break;
			}
		}
	}
}

参考书的代码：

int comb(int A[],int &na,int B[],int nb){// 合并后na发生变化，因此使用引用型
	if(na+nb>maxSize){// 假设maxSize是已经定义好的常量
	return -1; 
	} 
	int i=na,j=nb;
	while(j>0){
		if(i==0||A[i-1]<B[j-1]){
			A[j+i-1]=B[j-1];// 说明B[j-1]是第i+j大的元素 
			j--;
		}else{
			A[j+i-1]=A[i-1];// 说明A[i-1]是第i+j大的元素 
			i--;
		}
	}
	na=na+nb;
	return na;
} 

完整代码：

#include<stdio.h>

#define maxSize 30

/* 题目3. */

void print(int nums[],int n) {
	printf("\n");
	for(int i=0; i<n; i++) {
		printf("%d\t",nums[i]);
	}
	printf("\n");
}


void merge(int A[],int &An,int B[],int Bn) {
	for(int i=Bn-1; i>=0; i--) {
		for(int j=An-1; j>=0; j--) {
			if(B[i]>A[j]) {
				int q;
				for(q=An; q>j; q--) {
					A[q]=A[q-1];
				}
				A[q+1]=B[i];
				An++;
				break;
			}
		}
	}
}

/* 参考书代码 */
int comb(int A[],int &na,int B[],int nb) { // 合并后na发生变化，因此使用引用型
	if(na+nb>maxSize) { // 假设maxSize是已经定义好的常量
		return -1;
	}
	int i=na,j=nb;
	while(j>0) {
		if(i==0||A[i-1]<B[j-1]) {
			A[j+i-1]=B[j-1];// 说明B[j-1]是第i+j大的元素
			j--;
		} else {
			A[j+i-1]=A[i-1];// 说明A[i-1]是第i+j大的元素
			i--;
		}
	}
	na=na+nb;
	return na;
}

int main() {
	int A[maxSize]= {1,3,5,6,9};
	int An=5;
	int B[maxSize]= {2,4,7,8,10,11};
	int Bn=6;

	merge(A,An,B,Bn);
//	comb(A,An,B,Bn);
	print(A,An);

	return 0;
}

运行效果如下：