数据结构题典008：顺序表的合并（ANSI C）

fduan

于 2011-12-28 01:25:43 发布

阅读量905

点赞数

分类专栏： C/C++ Data Structure 数据结构题典 Algorithm 文章标签：数据结构 c merge 算法

本文链接：https://blog.csdn.net/fduan/article/details/7104643

版权

Algorithm 同时被 3 个专栏收录

60 篇文章

订阅专栏

C/C++

55 篇文章

订阅专栏

Data Structure

37 篇文章

订阅专栏

本文介绍了一种高效地将两个非递减有序的顺序表合并为一个非递减有序顺序表的方法，通过从尾部开始比较和合并，最大程度减少了元素的移动次数。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

题意：设有顺序表La和Lb，二者中元素均为非递减有序，空间足够大。设计算法将Lb中的元素合并到La中，使新的La元素仍非递减有序。

分析：此题与将两个有序顺序表合并到第三个顺序表中的思路类似，只是为了减少移动次数，比较的次序从两线性表的尾部开始，这样每个元素最多只移动一次。

/*
 * merging of two ordered sequences
 *
 * fduan, Dec. 27, 2011.
 */
void merge_array( int a[], int b[], int len, int m, int n )
{
	int * pa = a + m - 1, * pb = b + n - 1, * p = a + m + n - 1;
	assert( len >= m + n );
	while( pa >= a && pb >= b )
		*p-- = ( *pa >= *pb ) ? *pa-- : *pb--;
	
	while( pa >= a )
		*p-- = *pa--;

	while( pb >= b )
		*p-- = *pb--;
}