题目一

将两个有序顺序表合并为一个有序顺序表，函数结果返回值为顺序表。

思路

1. 我们可以利用二路归并排序算法中的Merge函数思路，设置两个指针i，j，分别记录在顺序表a和b中的访问位置，再利用直接插入排序算法思想，将比较后的元素值插入顺序表中。时间复杂度为O(n),空间复杂度为O(n)。

代码实现

Array LinearList::Question_07()
{Array arr1,arr2;arr1.length = 5;cout<<"insert 5 nums to arr1:"<<endl;for(int i = 0;i < arr1.length;i ++){cin >> arr1.data[i];}arr2.length = 5;cout<<"insert 5 nums to arr2:"<<endl;for(int i = 0;i < arr2.length;i ++){cin >> arr2.data[i];}int i = 0,j = 0,k = 0;arr.length = arr1.length + arr2.length;while(i < arr1.length || j < arr2.length){if(arr1.data[i] <= arr2.data[j] && i < arr1.length && j < arr2.length){arr.data[k++] = arr1.data[i++];}else if(arr1.data[i] > arr2.data[j] && i < arr1.length && j < arr2.length){arr.data[k++] = arr2.data[j++];}else if(j >= arr1.length-1){arr.data[k++] = arr1.data[i++];}else if(i >= arr2.length-1){arr.data[k++] = arr2.data[j++];}}return arr;
}

效果

题目二

已知一个一维数组A[m+n]中一次存放两个线性表{a1,a2,a3…am}和{b1,b2,b3,…,bn}，编写一个函数，将数组中两个顺序表的位置互换，即将{b1,b2,b3,…,bn}放到{a1,a2,a3…am}之前。

思路

1. 先将数组A[m+n]中的元素逆置，得到{bm,bm-1,…,b1,an,an-1,…,a1}。再分别对两个顺序表进行元素逆置，即可得到{b1,b2,…,bm-1,bm,a1,a2,…,an-1,an},完成题目要求。时间复杂度为O(n)，空间复杂度为O(1)。

代码实现

//逆置函数，将指针位置的数组元素逆置
Array LinearList::Reverse(int left,int right)
{if(arr.length <= 1)return arr;int i = left,j = right-1;int temp = 0;while(i < j){temp = arr.data[i];arr.data[i++] = arr.data[j];arr.data[j--] = temp;temp = 0;}return arr;
}Array LinearList::Question_08()
{Array arr1,arr2;arr1.length = 5;cout<<"insert 5 nums to arr1:"<<endl;for(int i = 0;i < arr1.length;i ++){cin >> arr1.data[i];}arr2.length = 6;cout<<"insert 6 nums to arr2:"<<endl;for(int i = 0;i < arr2.length;i ++){cin >> arr2.data[i];}arr.length = arr1.length + arr2.length;for(int i = 0;i < arr.length;i ++){if(i < arr1.length)arr.data[i] = arr1.data[i];elsearr.data[i] = arr2.data[i-arr1.length];}PrintLinearList();/* 以上代码均为预处理代码，跟算法逻辑无关 */arr = Reverse(0,arr.length);//逆置arr数组PrintLinearList();arr = Reverse(0,arr2.length);//逆置顺序表arr1PrintLinearList();arr = Reverse(arr2.length,arr.length);//逆置顺序表arr2return arr;
}

效果