题目

设A和B是两个顺序表，其元素按非递减的顺序排列。编写一个将A和B中所有元素结点组成一个新的从小到大的有序顺序表C的算法，要求所有重复元素只保留一个。

分析

还是在归并算法上进行修改。

代码

核心代码：

/* 归并A和B表 */
/* A[]指的是A顺序表；An指的是A的长度；B[]指的是B表，Bn指的是B的长度；C[]指的是要合并后的表；&Cn指的是C数组的长度，要进行修改 */
void merge(int A[],int An,int B[],int Bn,int C[],int &Cn) {
	int i=0;
	int j=0;
	int q=0;
	while(i<An&&j<Bn) {
		if(A[i]<B[j]) {
			C[q]=A[i];
			i++;
			q++;
		}
		if(A[i]==B[j]) {
			C[q]=A[i];
			q++;
			i++;
			j++;
		}
		if(A[i]>B[j]) {
			C[q]=B[j];
			q++;
			j++;
		}
	}
	while(i<An) { // 处理A表中剩下的元素
		C[q]=A[i];
		q++;
		i++;
	}
	while(j<Bn) { // 处理B表剩下的元素
		C[q]=B[j];
		q++;
		j++;
	}
	Cn=q;
}

参考书上的代码：

int unions(int A[],int na,int B[],int nb,int C[],int &nc) {
	int i=0,j=0,k=0;
	if(na+na>maxSize) {
		return -1;// 数组上溢，返回失败标记
	}
	while(i<na&&j<nb) {
		if(A[i]<=B[j]) {
			if(k>0) {
				// 此处注意堆k为0的处理，因为A和B可能是空表。没有k>0的判断，C[k-1]出现溢出
				if(C[k-1]!=A[i]) { // 这个判断起到过滤相同元素的作用
					C[k++]=A[i++];
				} else {
					i++;
				}
			} else {
				C[k++]=A[i++];
			}
		} else {
			if(k<0) {
				if(C[k-1]!=B[j]) {
					C[k++]=B[j++];

				} else {
					j++;
				}
			} else {
				C[k++]=B[j++];
			}
		}
	}
	while(i<na) {
		if(k>0) {
			if(C[k-1]!=A[i]) {
				C[k++]=A[i++];
			} else {
				i++;
			}
		} else {
			C[k++]=A[i++];
		}
	}
	while(j<nb) {
		if(k>0) {
			if(C[k-1]!=B[j]) {
				C[k++]=B[j++];
			} else {
				j++;
			}
		} else {
			C[k++]=B[j++];
		}
	}
	nc=k;
	return nc;
}

完整代码：

#include<stdio.h>

#define maxSize 30

/* 题目7. */

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

/* 归并A和B表 */
/* A[]指的是A顺序表；An指的是A的长度；B[]指的是B表，Bn指的是B的长度；C[]指的是要合并后的表；&Cn指的是C数组的长度，要进行修改 */
void merge(int A[],int An,int B[],int Bn,int C[],int &Cn) {
	int i=0;
	int j=0;
	int q=0;
	while(i<An&&j<Bn) {
		if(A[i]<B[j]) {
			C[q]=A[i];
			i++;
			q++;
		}
		if(A[i]==B[j]) {
			C[q]=A[i];
			q++;
			i++;
			j++;
		}
		if(A[i]>B[j]) {
			C[q]=B[j];
			q++;
			j++;
		}
	}
	while(i<An) { // 处理A表中剩下的元素
		C[q]=A[i];
		q++;
		i++;
	}
	while(j<Bn) { // 处理B表剩下的元素
		C[q]=B[j];
		q++;
		j++;
	}
	Cn=q;
}


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

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

	return 0;
}

运行效果如下：