[408] [数据结构] 顺序表-代码题

01

问题：从顺序表中删除具有最小值的元素（假设唯一）并由函数返回被删元素的值。空出的位置由最后一个元素填补，若顺序表为空，则显示出错信息并退出运行。
答：

boolDeleteMin(SqList&L,ElemType&min){// 从顺序表L中删除具有最小值的元素，并将其值保存在min中if(L.length==0){// 顺序表为空，无法删除returnfalse;// 删除失败}intminIndex=0;// 最小值元素的索引for(inti=1;i<L.length;i++)// 查找最小值元素的索引if(L.data[i]<L.data[minIndex])minIndex=i;min=L.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(SqList&L){// 将顺序表L的所有元素逆置for(inti=0;i<L.length/2;i++){// 只需遍历到中间位置ElemType temp=L.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(SqList&L,ElemType x){// 删除顺序表L中所有值为x的元素intk=0;// k表示当前不为x的元素个数for(inti=0;i<L.length;i++){// 遍历顺序表中的每个元素if(L.data[i]!=x){// 如果当前元素不为xL.data[k]=L.data[i];// 将当前元素赋值给第k个位置k++;// 不为x的元素个数增加1}}L.length=k;// 更新顺序表的长度为不为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(SqList&L,ElemType x){intk=0,i;//记录值不等于x的元素个数for(i=0;i<L.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(SqList&L,ElemType s,ElemType t){// 删除顺序表L中值在s和t之间的元素if(s>=t){// s或t不合理returnfalse;// 删除失败}if(L.length==0){// 顺序表为空returnfalse;// 删除失败}intk=0;// k表示当前不为x的元素个数for(inti=0;i<L.length;i++){// 遍历顺序表中的每个元素if(L.data[i]<s||L.data[i]>t){// 如果当前元素不在[s,t]范围内L.data[k]=L.data[i];// 将当前元素赋值给第k个位置k++;// 不在范围内的元素个数增加1}}L.length=k;// 更新顺序表的长度为不在范围内的元素个数returntrue;// 删除成功}

思路：
本题也是删除元素构建新表，本质上和03题是一样的，上述代码实现用的也是03题的第一种解法，下面也给了类似于03题的第二种解法的解法。

booldesl_s_t(SqList&L,ElemType s,ElemType t){inti,k=0;if(L.length==0||s>=t)returnfalse;//顺序表为空或s、t不合理for(i=0;i<L.length;i++){if(L.data[i]>=s&&L.data[i]<=t){//如果当前元素在[s,t]范围内k++;//记录在范围内的元素个数增加1}else{L.data[i-k]=L.data[i];//当前元素前移k个位置}}}

05

问题：从有序顺序表中删除所有其值重复的元素，使表中所有元素的值均不同。
答：

boolDeleteDuplicates(SqList&L){// 从有序顺序表L中删除所有重复的元素if(L.length==0)returnfalse;// 顺序表为空，无需删除intk=0;// k表示当前不重复元素的个数for(inti=1;i<L.length;i++){// 从第二个元素开始遍历顺序表if(L.data[i]!=L.data[k]){// 如果当前元素与上一个不重复元素不同k++;// 不重复元素个数增加1L.data[k]=L.data[i];// 将当前元素赋值给第k个位置returnture;}}L.length=k+1;// 更新顺序表的长度为不重复元素的个数}

思路：首先题目中说了是有序顺序表，也就是说相同的元素一定是挨着的。那么如果第i个元素和第i-1个元素不同，那么第i个元素也一定和第i个元素之前的所有元素都不相同，那么这个问题我们只需要判断下一个元素和上一个元素是否相同既可，相同就删掉，不同就前移。
扩展：
将有序表改为无序表
答：

boolDeleteDuplicates(SqList&L){// 从无序顺序表L中删除所有重复的元素if(L.length==0)returnfalse;// 顺序表为空，无需删除for(inti=0;i<L.length-1;i++){// 遍历顺序表中的每个元素for(intj=i+1;j<L.length;j++){// 从当前元素的下一个位置开始遍历顺序表if(L.data[i]==L.data[j]){// 如果当前元素与后面的元素相同for(intk=j;k<L.length-1;k++){// 将后面的元素前移一位L.data[k]=L.data[k+1];}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(SqList&L){if(L.length==0)returnfalse;// 假设开一个散列标记数组inthash[MaxSize]={0};intk=0;for(inti=0;i<L.length;i++){if(!hash[L.data[i]]){// 散列表查询是否已存在hash[L.data[i]]=1;L.data[k++]=L.data[i];}}L.length=k;returntrue;}

C++:

boolDeleteDuplicates(SqList&L){// 从无序顺序表L中删除所有重复的元素if(L.length==0)returnfalse;// 顺序表为空，无需删除unordered_set<ElemType>seen;// 哈希表用于存储已见过的元素intk=0;// k表示当前不重复元素的个数for(inti=0;i<L.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.length=k;// 更新顺序表的长度为不重复元素的个数returntrue;// 删除成功}

06

问题：将两个有序顺序表合并为一个新的有序顺序表，使表中所有元素的值均不相同。
答：

boolMergeLists(SqList A,SqList B,SqList C){// 将两个有序顺序表A和B合并为一个新的有序顺序表Cif(A.length+B.length>C.maxSize)returnfalse;//大于顺序表的最大长度inti=0,j=0,k=0;// i、j、k分别表示A、B、C的当前索引while(i<A.length&&j<B.length){//循环，两两比较，小者存入结果表if(A.data[i]<=B.data[j])C.data[k++]=A.data[i++];elseC.data[k++]=B.data[j++];}while(i<A.length)C.data[k++]=A.data[i++];//将A中剩余元素存入结果表while(j<B.length)C.data[k++]=B.data[j++];//将B中剩余元素存入结果表C.length=k;//更新结果表的长度returntrue;//合并成功}

思路：
首先，按顺序不断取下两个顺序表表头较小的结点存入新的顺序表中。然后，看哪个表还有剩余，将剩余部分加到新的顺序表后面既可。

注：本文后续还会持续更新，建议关注收藏