题目

设A和B是两个顺序表，其元素按递增的顺序排列。编写一个将A和B中相同元素组成一个新的从大到小的有序顺序表C的算法。

分析

在归并算法的基础上稍加改动，只需要将当前扫描到的相等元素归入C表即可。

代码

核心代码：

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

完整代码：

#include<stdio.h>

#define maxSize 30

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

/* 归并A和B表 */ 
void merge(int A[],int An,int B[],int Bn,int C[],int &Cn) {
	int i=An-1;
	int j=Bn-1;
	int q=0;
	while(i>=0&&j>=0) {
		if(B[j]>A[i]) {
			j--;
		}
		if(B[j]==A[i]) {
			C[q]=A[i];
			i--;
			j--;
			q++;
		}
		if(B[j]<A[i]) {
			i--;
		}
	}
	Cn=q;
}


int main() {
	int A[maxSize]= {1,2,4,6,8,9,10};
	int An=7;
	int B[maxSize]= {2,6,8,10,12,14};
	int Bn=6;
	int C[maxSize];
	int Cn=0;

	merge(A,An,B,Bn,C,Cn);
	print(C,Cn);

	return 0;
}

运行效果如下：