合并两个顺序表,并删除重复元素

时间:2021-04-06 19:38:09

设A和B是两个顺序表,其元素按非递减的顺序排列。编写一个将A和B中所有元素组成一个新的从小到大的有序顺序表C的算法,要求删除重复的元素,并返回C表的长度。

解析:这是一个常规题,参考代码如下:
int unions(int A[], int na, int B[], int nb, int C[])
{
	int i = 0,  j = 0, k = 0;
	while (i<na && j<nb)
	{
		if (A[i] <= B[j])
		{
			if (k > 0)
			{
				if (C[k-1] != A[i])
				{
					C[k++] = A[i++];
				}
				else
				{
					++i;
				}
			}
			else	//k==0,C[]的第一个元素位置
			{
				C[k++] = A[i++];
			}
		}
		else	//A[i] > B[j]
		{
			//此处注意k为0时的处理,因为A或B有可能是空表。没有k等于0的判断,C[k-1]会出现溢出
			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++];
		}
	}
	return k;
}
注意:容易忽略对A或者对B内部相同元素的处理,细心处理,避免发生错误。