3、有两个递增有序的整数顺序表A、B,设计一个算法将他们中全部元素放到顺序表C中,要求C中元素是递减有序的,并进行测试。
时间: 2023-05-24 13:01:13 浏览: 46
可以实现一个合并排序算法,具体步骤如下:
1. 定义三个指针,分别指向A、B、C的最后一个元素。
2. 比较指针所指向的元素,将较大的元素放到C的最后一个位置,并将指针向前移动一位。
3. 重复步骤2,直到A、B中的一个指针移动到第一个元素。
4. 将另一个顺序表中剩余的元素复制到C中的前面。
下面是具体的实现代码:
void mergeSortedList(int A[], int B[], int C[], int nA, int nB)
{
int *pa = A + nA - 1, *pb = B + nB - 1, *pc = C + nA + nB - 1;
while (pa >= A && pb >= B)
{
if (*pa > *pb)
*pc-- = *pa--;
else
*pc-- = *pb--;
}
while (pa >= A) *pc-- = *pa--;
while (pb >= B) *pc-- = *pb--;
}
可以通过以下方式进行测试:
int main()
{
int A[5] = {1, 3, 5, 7, 9};
int B[5] = {2, 4, 6, 8, 10};
int C[10] = {0};
mergeSortedList(A, B, C, 5, 5);
for (int i = 0; i < 10; i++)
printf("%d ", C[i]);
return 0;
}
输出结果为: 10 9 8 7 6 5 4 3 2 1
注意:此算法的时间复杂度为O(n),其中n为待排序序列的长度。
相关推荐
![cpp](https://img-home.csdnimg.cn/images/20210720083646.png)
![text/x-c](https://img-home.csdnimg.cn/images/20210720083646.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)