01问题从顺序表中删除具有最小值的元素假设唯一并由函数返回被删元素的值。空出的位置由最后一个元素填补若顺序表为空则显示出错信息并退出运行。答boolDeleteMin(SqListL,ElemTypemin){// 从顺序表L中删除具有最小值的元素并将其值保存在min中if(L.length0){// 顺序表为空无法删除returnfalse;// 删除失败}intminIndex0;// 最小值元素的索引for(inti1;iL.length;i)// 查找最小值元素的索引if(L.data[i]L.data[minIndex])minIndexi;minL.data[minIndex];// 将最小值元素的值保存在min中L.data[minIndex]L.data[L.length-1];// 用最后一个元素填补空出的位置L.length--;// 顺序表长度减少1returntrue;// 删除成功}思路1.删除具有最小值的值并返回其值那么就是遍历整个顺序表我们用minIndex来存储最小值的索引一开始其为1然后依次往后遍历每个元素与L.data[minIndex]进行比较如果这个元素更小就让minIndex等于这个元素的索引遍历完整个顺序表之后minIndex存放的就是整个顺序表中最小元素的索引。然后min就等于L.data[minIndex]。2.空出的位置有最后一个元素填补也就是L.data[L.length-1]。第一步我们就求得了最小元素的索引minIndex所以我们只需要L.data[minIndex]L.data[L.length-1]即可最后需要注意的是我们删除了一个值所以我们需要L.length- -。02问题设计一个高效算法将顺序表 L 的所有元素逆置要求算法的空间复杂度为 O(1)。答voidReverseList(SqListL){// 将顺序表L的所有元素逆置for(inti0;iL.length/2;i){// 只需遍历到中间位置ElemType tempL.data[i];// 临时变量存储当前元素L.data[i]L.data[L.length-1-i];// 将最后一个元素赋值给当前元素L.data[L.length-1-i]temp;// 将临时变量的值赋值给最后一个元素}}思路本题需要注意的是要求算法高效算法空间复杂度为O(1)也就是不利用额外的空间。进行逆置其实就是从中间位置开始从中间位置分成两部分前后两部分距离中间位置距离相同的两个元素对换即可也就是*L.data[i]和L.data[L.length-1-i]*进行对换。03问题对长度为 n 的顺序表 L编写一个时间复杂度为 O(n)、空间复杂度为 O(1)的算法该算法删除顺序表中所有值为 x 的数据元素。答voidDeleteX(SqListL,ElemType x){// 删除顺序表L中所有值为x的元素intk0;// k表示当前不为x的元素个数for(inti0;iL.length;i){// 遍历顺序表中的每个元素if(L.data[i]!x){// 如果当前元素不为xL.data[k]L.data[i];// 将当前元素赋值给第k个位置k;// 不为x的元素个数增加1}}L.lengthk;// 更新顺序表的长度为不为x的元素个数}思路本题两个限制一个是时间复杂度是n一个是空间复杂度是1。任务是删除顺序表中所有值为x的数据元素也就是我们要找到所有数值为x的元素进行删除同时我们还需要将剩余元素构建成一个新的顺序表。这是我们可以通过遍历的方式进行查找数值为x的元素同时遍历的时间复杂度正好为n。然后因为空间复杂度是1所以我们只能使用原本顺序表的空间来构建新的顺序表最好想到的是我们删除一个元素就将后面的元素全部前移但这种方式首先不好编写代码后续也给出了这种实现代码。这时我们可以使用一种更简洁的方法我们定义k表示当前不为x的元素个数然后我们开始遍历是x我们就跳过不管不是x我们就将当前元素赋值给第k个位置同时让k加一。因为是删除操作新的顺序表一定比原来的顺序表小或者相等所以我们可以不用前移而是让需要保留的元素依次覆盖前面的元素从而构建出新的顺序表用k记录顺序表L中等于x的元素个数一边扫描L一边统计k并将不等于x的元素前移k个位置扫描结束后修改L的长度。voiddel_x_2(SqListL,ElemType x){intk0,i;//记录值不等于x的元素个数for(i0;iL.length;i){if(L.data[i]!x){//如果当前元素不等于xL.data[k]L.data[i];//将当前元素赋值给第k个位置k;//记录值不等于x的元素个数增加1}}}04问题从顺序表中删除其值在给定值 s 和 t 之间包含 s 和 t要求 s t的所有元素若 s 或 t 不合理或顺序表为空则显示出错信息并退出运行。答boolDeleteRange(SqListL,ElemType s,ElemType t){// 删除顺序表L中值在s和t之间的元素if(st){// s或t不合理returnfalse;// 删除失败}if(L.length0){// 顺序表为空returnfalse;// 删除失败}intk0;// k表示当前不为x的元素个数for(inti0;iL.length;i){// 遍历顺序表中的每个元素if(L.data[i]s||L.data[i]t){// 如果当前元素不在[s,t]范围内L.data[k]L.data[i];// 将当前元素赋值给第k个位置k;// 不在范围内的元素个数增加1}}L.lengthk;// 更新顺序表的长度为不在范围内的元素个数returntrue;// 删除成功}思路本题也是删除元素构建新表本质上和03题是一样的上述代码实现用的也是03题的第一种解法下面也给了类似于03题的第二种解法的解法。booldesl_s_t(SqListL,ElemType s,ElemType t){inti,k0;if(L.length0||st)returnfalse;//顺序表为空或s、t不合理for(i0;iL.length;i){if(L.data[i]sL.data[i]t){//如果当前元素在[s,t]范围内k;//记录在范围内的元素个数增加1}else{L.data[i-k]L.data[i];//当前元素前移k个位置}}}05问题从有序顺序表中删除所有其值重复的元素使表中所有元素的值均不同。答boolDeleteDuplicates(SqListL){// 从有序顺序表L中删除所有重复的元素if(L.length0)returnfalse;// 顺序表为空无需删除intk0;// k表示当前不重复元素的个数for(inti1;iL.length;i){// 从第二个元素开始遍历顺序表if(L.data[i]!L.data[k]){// 如果当前元素与上一个不重复元素不同k;// 不重复元素个数增加1L.data[k]L.data[i];// 将当前元素赋值给第k个位置returnture;}}L.lengthk1;// 更新顺序表的长度为不重复元素的个数}思路首先题目中说了是有序顺序表也就是说相同的元素一定是挨着的。那么如果第i个元素和第i-1个元素不同那么第i个元素也一定和第i个元素之前的所有元素都不相同那么这个问题我们只需要判断下一个元素和上一个元素是否相同既可相同就删掉不同就前移。扩展将有序表改为无序表答boolDeleteDuplicates(SqListL){// 从无序顺序表L中删除所有重复的元素if(L.length0)returnfalse;// 顺序表为空无需删除for(inti0;iL.length-1;i){// 遍历顺序表中的每个元素for(intji1;jL.length;j){// 从当前元素的下一个位置开始遍历顺序表if(L.data[i]L.data[j]){// 如果当前元素与后面的元素相同for(intkj;kL.length-1;k){// 将后面的元素前移一位L.data[k]L.data[k1];}L.length--;// 顺序表长度减少1j--;// 继续检查当前位置的元素是否有重复}}}returntrue;// 删除成功}思路我们最容易想到的方法就是暴力枚举用外层循环逐个固定一个元素 L.data[i]内层循环从它后面开始找所有和它相等的重复元素找到重复元素后把后面所有元素向前移动一位覆盖掉重复值表长减 1完成删除因为删除后后面元素前移了当前 j 位置会变成新元素所以必须 j-- 重新检查。这种方法的时间复杂度为O(n3)O(n^3)O(n3)我们是否可以找到时间复杂度是O(n)O(n)O(n)呢答案是有的我们可以借助散列表来实现。思路如下开一个散列标记数组用来记录哪些元素已经出现过遍历原顺序表逐个检查当前元素散列表快速判断没出现过 → 保留元素并标记为已出现出现过 → 直接跳过删除用一个下标 k 构建新表把不重复的元素依次覆盖到原数组前面最后修改表长完成去重代码如下// 思路借助哈希思想标记是否出现过boolDeleteDuplicates(SqListL){if(L.length0)returnfalse;// 假设开一个散列标记数组inthash[MaxSize]{0};intk0;for(inti0;iL.length;i){if(!hash[L.data[i]]){// 散列表查询是否已存在hash[L.data[i]]1;L.data[k]L.data[i];}}L.lengthk;returntrue;}C:boolDeleteDuplicates(SqListL){// 从无序顺序表L中删除所有重复的元素if(L.length0)returnfalse;// 顺序表为空无需删除unordered_setElemTypeseen;// 哈希表用于存储已见过的元素intk0;// k表示当前不重复元素的个数for(inti0;iL.length;i){// 遍历顺序表中的每个元素if(seen.find(L.data[i])seen.end()){// 如果当前元素未见过seen.insert(L.data[i]);// 将当前元素添加到哈希表中L.data[k]L.data[i];// 将当前元素赋值给第k个位置k;// 不重复元素个数增加1}}L.lengthk;// 更新顺序表的长度为不重复元素的个数returntrue;// 删除成功}06问题将两个有序顺序表合并为一个新的有序顺序表使表中所有元素的值均不相同。答boolMergeLists(SqList A,SqList B,SqList C){// 将两个有序顺序表A和B合并为一个新的有序顺序表Cif(A.lengthB.lengthC.maxSize)returnfalse;//大于顺序表的最大长度inti0,j0,k0;// i、j、k分别表示A、B、C的当前索引while(iA.lengthjB.length){//循环两两比较小者存入结果表if(A.data[i]B.data[j])C.data[k]A.data[i];elseC.data[k]B.data[j];}while(iA.length)C.data[k]A.data[i];//将A中剩余元素存入结果表while(jB.length)C.data[k]B.data[j];//将B中剩余元素存入结果表C.lengthk;//更新结果表的长度returntrue;//合并成功}思路首先按顺序不断取下两个顺序表表头较小的结点存入新的顺序表中。然后看哪个表还有剩余将剩余部分加到新的顺序表后面既可。注本文后续还会持续更新建议关注收藏