1. 为什么顺序表的基础操作值得反复琢磨很多人学数据结构的时候看到顺序表这一章会觉得太简单了——不就是数组吗增删改查谁不会。我刚开始也是这个心态直到有一次帮一个学弟看代码他写了一个顺序表逆序跑出来结果不对我让他把每一步的中间状态打印出来他才发现自己的循环边界写错了导致中间那个元素被覆盖了两次。这件事让我意识到顺序表的基本操作虽然逻辑不复杂但真正动手写的时候边界条件、循环终止条件、元素移动方向这些细节才是拉开水平差距的地方。这篇笔记主要聊两个操作顺序表的逆序和删除特定值。这两个操作看起来都很基础但它们涉及到的思维方式完全不同。逆序考察的是你对双指针交换和循环边界的理解而删除特定值考察的是你对元素移动和原地操作的掌握。更重要的是这两个操作在面试和实际开发中出现的频率非常高很多看起来复杂的算法题拆解到最后就是这两个基本操作的组合。不管你是正在学数据结构的学生还是准备面试的求职者或者是很久没写底层代码想复习一下的开发者这两个操作的细节都值得你花时间彻底搞明白。下面我会从设计思路、代码实现、边界处理、常见错误几个维度把这两个操作掰开揉碎讲清楚。2. 顺序表逆序操作的核心思路与实现细节2.1 逆序操作的本质是什么顺序表的逆序说白了就是把第一个元素和最后一个元素交换第二个元素和倒数第二个元素交换以此类推直到中间位置。这个思路听起来很简单但里面有几个关键问题需要想清楚。第一个问题是交换到什么时候停止。假设顺序表有 n 个元素下标从 0 到 n-1。我们需要交换的对数是 n/2 对整数除法。比如 5 个元素需要交换 2 对中间那个元素不用动6 个元素需要交换 3 对刚好全部交换完。所以循环的条件可以写成i n / 2其中 i 是从 0 开始的左指针。第二个问题是右指针怎么表示。和左指针 i 对应的右指针是n - 1 - i。当 i0 时右指针是 n-1当 i1 时右指针是 n-2。这个对应关系是整个逆序操作的核心。第三个问题是需不需要额外空间。答案是不需要。逆序操作可以通过原地交换完成空间复杂度是 O(1)。这一点很重要因为如果你用一个新的数组来存储逆序结果虽然也能实现但空间复杂度就变成了 O(n)在面试中会被扣分。注意逆序操作的前提是顺序表已经存在且非空。如果顺序表为空或者只有一个元素逆序操作实际上不需要做任何事情代码应该能正确处理这种情况。2.2 双指针交换法的完整实现下面用 C 语言给出一个标准的顺序表逆序实现。假设顺序表的结构定义如下#define MAXSIZE 100 typedef struct { int data[MAXSIZE]; int length; } SeqList;逆序操作的函数实现void ReverseList(SeqList *L) { int i, temp; for (i 0; i L-length / 2; i) { temp L-data[i]; L-data[i] L-data[L-length - 1 - i]; L-data[L-length - 1 - i] temp; } }这段代码虽然短但每一行都值得推敲。L-length / 2利用了整数除法的特性当 length 是奇数时比如 55/22循环执行 i0 和 i1 两次正好交换两对中间的元素不动。当 length 是偶数时比如 66/23循环执行三次全部交换完毕。交换部分用了经典的三变量交换法先把左边的值存到临时变量 temp然后把右边的值赋给左边最后把 temp 里的值赋给右边。这个顺序不能乱如果先写L-data[i] L-data[L-length - 1 - i]那左边的原始值就丢了。如果你用的是 Python实现会更简洁def reverse_list(lst): n len(lst) for i in range(n // 2): lst[i], lst[n - 1 - i] lst[n - 1 - i], lst[i]Python 的元组解包让交换操作变得非常优雅不需要临时变量。但底层逻辑和 C 语言版本完全一样。2.3 逆序操作中容易踩的坑第一个坑是循环边界写成i L-length / 2。多了一个等号当 length 是奇数时中间的元素会自己和自己交换虽然结果看起来是对的但多做了一次无意义的操作当 length 是偶数时会导致数组越界或者重复交换结果就错了。第二个坑是右指针写成L-length - i。这是最常见的下标错误。因为下标是从 0 开始的最后一个元素的下标是 length-1所以右指针应该是length - 1 - i。写成length - i会访问到数组之外的内存在 C 语言里可能不会报错但结果是不可预期的。第三个坑是忘记处理空表。如果 length 为 0L-length / 2也是 0循环不会执行实际上不会出问题。但如果你的代码里有其他依赖 length 的操作比如先判断L-data[0]那就可能出问题。养成先判断空表的习惯。第四个坑是在交换过程中修改了 length。有些人写着写着就把 length 当成了循环变量的一部分去修改这是绝对不允许的。length 是顺序表的属性逆序操作不应该改变它。实操心得写完逆序代码后一定要用奇数和偶数长度的测试用例各跑一遍。我习惯用 [1,2,3,4,5] 和 [1,2,3,4] 这两组数据来验证能覆盖大部分边界情况。3. 删除特定值操作的多种实现方案3.1 删除操作的问题定义删除特定值这个问题具体的描述是给定一个顺序表和一个目标值要求删除顺序表中所有等于目标值的元素并且保持剩余元素的相对顺序不变。这个问题有几个变体需要区分清楚。第一种是删除第一个出现的特定值第二种是删除所有出现的特定值第三种是删除指定位置的值。这篇笔记主要讨论第二种因为它的实现思路最丰富也最能体现算法思维。这个问题的难点在于如果每删除一个元素就把后面的所有元素往前移动一位时间复杂度会达到 O(n²)。我们需要一种更高效的方法在 O(n) 的时间内完成删除操作。3.2 方法一双指针覆盖法双指针覆盖法是解决这类问题最经典的方法。核心思路是用一个指针遍历整个顺序表另一个指针记录下一个有效元素应该放置的位置。int RemoveAll(SeqList *L, int target) { int k 0; // k 是慢指针记录有效元素的位置 int i; // i 是快指针遍历整个顺序表 for (i 0; i L-length; i) { if (L-data[i] ! target) { L-data[k] L-data[i]; k; } } L-length k; // 更新顺序表长度 return k; // 返回新的长度 }这段代码的精妙之处在于快指针 i 负责扫描所有元素慢指针 k 负责记录不等于 target 的元素。当L-data[i] ! target时就把这个元素复制到L-data[k]的位置然后 k 加一。如果L-data[i] target就跳过k 不动。整个过程结束后k 的值就是新顺序表的长度而前 k 个位置存储的就是所有不等于 target 的元素且保持了原来的相对顺序。这个算法的时间复杂度是 O(n)因为只遍历了一遍空间复杂度是 O(1)因为只用了两个额外的变量。注意这个方法会改变顺序表中元素的物理位置但不会改变剩余元素的相对顺序。如果你需要保持原顺序表中被删除元素之后的所有元素位置不变那这个方法不适用需要用下面的方法二。3.3 方法二逐个移动法逐个移动法的思路更直观遍历顺序表一旦发现等于 target 的元素就把后面所有的元素往前移动一位然后 length 减一同时 i 不增加因为移动后当前位置换了一个新元素需要重新检查。int RemoveAllShift(SeqList *L, int target) { int i 0; while (i L-length) { if (L-data[i] target) { int j; for (j i; j L-length - 1; j) { L-data[j] L-data[j 1]; } L-length--; // i 不增加继续检查当前位置的新元素 } else { i; } } return L-length; }这个方法的时间复杂度在最坏情况下是 O(n²)比如顺序表中所有元素都等于 target 时每次删除都要移动大量元素。但它的优点是删除操作是稳定的不会改变其他元素的位置。在实际开发中如果数据量不大或者删除操作不频繁这个方法是可以接受的。但如果数据量很大还是推荐用双指针覆盖法。3.4 方法三尾元素填补法尾元素填补法的思路是当发现等于 target 的元素时直接用顺序表最后一个元素覆盖它然后 length 减一。这个方法的时间复杂度是 O(n)但会打乱元素的相对顺序。int RemoveAllSwap(SeqList *L, int target) { int i 0; while (i L-length) { if (L-data[i] target) { L-data[i] L-data[L-length - 1]; L-length--; } else { i; } } return L-length; }这个方法在有些场景下非常有用比如你只关心剩余元素的集合不关心它们的顺序。但在需要保持顺序的场景下就不能用。3.5 三种方法的对比与选型方法时间复杂度空间复杂度是否保持顺序适用场景双指针覆盖法O(n)O(1)是通用场景推荐首选逐个移动法O(n²)O(1)是数据量小删除操作少尾元素填补法O(n)O(1)否不要求顺序追求效率选型建议如果没有特殊要求优先使用双指针覆盖法。它在时间效率和顺序保持上都表现最好。只有在明确不需要保持顺序且对性能有极致要求时才考虑尾元素填补法。4. 完整实操流程与测试验证4.1 搭建测试环境要验证这两个操作的正确性需要先搭建一个简单的测试环境。我用 C 语言写了一个完整的测试程序包含顺序表的初始化、打印、逆序、删除等操作。#include stdio.h #include stdlib.h #define MAXSIZE 100 typedef struct { int data[MAXSIZE]; int length; } SeqList; // 初始化顺序表 void InitList(SeqList *L, int arr[], int n) { int i; for (i 0; i n i MAXSIZE; i) { L-data[i] arr[i]; } L-length n; } // 打印顺序表 void PrintList(SeqList *L) { int i; printf([); for (i 0; i L-length; i) { printf(%d, L-data[i]); if (i L-length - 1) printf(, ); } printf(]\n); } // 逆序操作 void ReverseList(SeqList *L) { int i, temp; for (i 0; i L-length / 2; i) { temp L-data[i]; L-data[i] L-data[L-length - 1 - i]; L-data[L-length - 1 - i] temp; } } // 删除特定值双指针覆盖法 int RemoveAll(SeqList *L, int target) { int k 0; int i; for (i 0; i L-length; i) { if (L-data[i] ! target) { L-data[k] L-data[i]; k; } } L-length k; return k; } int main() { SeqList L; int arr1[] {1, 2, 3, 4, 5}; int arr2[] {1, 2, 3, 4}; int arr3[] {3, 1, 3, 2, 3, 4, 3}; // 测试奇数长度逆序 InitList(L, arr1, 5); printf(逆序前: ); PrintList(L); ReverseList(L); printf(逆序后: ); PrintList(L); // 测试偶数长度逆序 InitList(L, arr2, 4); printf(逆序前: ); PrintList(L); ReverseList(L); printf(逆序后: ); PrintList(L); // 测试删除特定值 InitList(L, arr3, 7); printf(删除前: ); PrintList(L); int newLen RemoveAll(L, 3); printf(删除后: ); PrintList(L); printf(新长度: %d\n, newLen); return 0; }4.2 测试用例设计与预期结果测试用例的设计要覆盖各种边界情况不能只测最普通的情况。我设计了以下几组测试数据逆序操作的测试用例奇数长度[1,2,3,4,5] → 预期结果 [5,4,3,2,1]偶数长度[1,2,3,4] → 预期结果 [4,3,2,1]单元素[7] → 预期结果 [7]空表[] → 预期结果 []删除操作的测试用例目标值在开头[3,1,2,4] 删除 3 → 预期结果 [1,2,4]目标值在结尾[1,2,4,3] 删除 3 → 预期结果 [1,2,4]目标值在中间[1,3,2,4] 删除 3 → 预期结果 [1,2,4]多个目标值[3,1,3,2,3] 删除 3 → 预期结果 [1,2]全部是目标值[3,3,3] 删除 3 → 预期结果 []没有目标值[1,2,4] 删除 3 → 预期结果 [1,2,4]4.3 实际运行结果记录编译运行上面的测试程序得到以下输出逆序前: [1, 2, 3, 4, 5] 逆序后: [5, 4, 3, 2, 1] 逆序前: [1, 2, 3, 4] 逆序后: [4, 3, 2, 1] 删除前: [3, 1, 3, 2, 3, 4, 3] 删除后: [1, 2, 4] 新长度: 3所有结果都符合预期。逆序操作正确处理了奇数和偶数长度的情况删除操作正确删除了所有的 3并且保持了剩余元素 [1,2,4] 的相对顺序。实操心得测试的时候不要只看最终结果最好在关键步骤打印中间状态。比如在逆序的循环里打印每次交换后的数组在删除的循环里打印 k 和 i 的值。这样一旦结果不对你能快速定位是哪一步出了问题。5. 常见问题与排查技巧实录5.1 逆序操作常见问题速查问题现象可能原因排查方法解决方案结果部分正确部分错误循环边界多写或少写等号打印循环次数和 i 的值检查i length/2是否正确数组越界或程序崩溃右指针下标计算错误打印length-1-i的值确认右指针是length-1-i中间元素被覆盖交换顺序写反单步调试交换过程确保用临时变量暂存空表或单元素报错没有处理边界情况用空表和单元素测试循环条件天然处理但需验证5.2 删除操作常见问题速查问题现象可能原因排查方法解决方案删除后元素顺序乱了用了尾元素填补法检查是否用了 swap 方式改用双指针覆盖法漏删了某些目标值快指针跳过了元素打印每次比较的 i 和值确保 i 每次都递增删除后 length 不对忘记更新 length检查函数末尾添加L-length k删除后出现重复元素慢指针没有正确递增打印 k 的变化确保只在非目标值时 k5.3 独家避坑技巧技巧一用纸笔模拟小数组。当你觉得代码逻辑没问题但结果就是不对的时候拿一张纸画一个 5 个格子的数组手动模拟每一步的变化。这个方法看起来笨但非常有效。我调试逆序操作的时候就是靠手动画图发现右指针写错了。技巧二在循环里加断言。在 C 语言里可以用assert宏来检查关键条件。比如在逆序的循环里加assert(i 0 i L-length)在删除的循环里加assert(k i)。这样一旦条件不满足程序会立即报错而不是产生错误结果。技巧三用 Python 快速验证思路。如果你不确定某个算法的逻辑对不对可以先用 Python 写一个简化版本因为 Python 的列表操作更直观不需要考虑内存和指针。验证思路正确后再翻译成 C 语言。技巧四注意 length 和实际元素个数的区别。在顺序表中length 是逻辑长度表示当前有多少个有效元素。数组的物理容量是 MAXSIZE可能比 length 大。删除操作只需要修改 length不需要清空被删除位置的内存。技巧五删除操作中不要用 for 循环。在逐个移动法中如果用 for 循环遍历删除元素后 i 的自增会导致跳过元素。用 while 循环可以更灵活地控制 i 的变化。双指针覆盖法虽然可以用 for 循环但也要注意 i 和 k 的独立递增。5.4 从面试角度看的加分项如果你是在准备面试这两个操作有几个可以加分的点。第一主动说出时间复杂度。逆序是 O(n)双指针删除也是 O(n)逐个移动删除是 O(n²)。第二主动说出空间复杂度。都是 O(1)原地操作。第三主动提到边界情况。空表、单元素、全部删除、没有删除这些都要考虑到。还有一个加分项是举一反三。比如面试官问你删除特定值你可以顺便提一下如果要求删除有序顺序表中重复的元素怎么做如果要求删除指定区间的元素怎么做。这些变体本质上都是双指针覆盖法的应用。注意面试中写代码不要追求炫技用最清晰、最不容易出错的方式写。双指针覆盖法虽然简洁但如果你对边界不自信可以先写一个暴力版本然后再优化。面试官更看重你的思路和沟通能力而不是代码有多短。6. 从这两个操作延伸出的通用思维6.1 双指针思想的广泛应用逆序操作和删除操作虽然场景不同但都用到了双指针的思想。逆序用的是左右对撞指针一个从前往后一个从后往前删除用的是快慢指针一个负责扫描一个负责记录。双指针思想在算法题中出现的频率极高。比如有序数组的两数之和左右指针从两端向中间逼近链表的中点查找快指针每次走两步慢指针每次走一步数组去重快指针遍历慢指针记录不重复元素的位置滑动窗口左右指针维护一个满足条件的区间掌握了双指针的思维方式很多看起来复杂的问题都能找到 O(n) 的解法。6.2 原地操作的价值这两个操作都是原地操作不需要额外的数组空间。在实际开发中原地操作的价值非常大尤其是在内存受限的场景下比如嵌入式系统、移动端开发、大数据处理。原地操作的核心思想是利用已有空间存储中间结果。在删除操作中我们用顺序表前面的空位来存储保留下来的元素在逆序操作中我们用交换来避免额外空间。这种思维方式在内存优化中非常关键。6.3 边界条件的重要性这两个操作让我深刻体会到边界条件的重要性。空表、单元素、全部满足条件、全部不满足条件这些边界情况在正常数据中很少出现但一旦出现就会导致程序崩溃或结果错误。养成一个习惯写完任何操作后先问自己四个问题。如果数据为空会怎样如果只有一个元素会怎样如果所有元素都满足条件会怎样如果所有元素都不满足条件会怎样这四个问题能帮你覆盖 90% 的边界情况。6.4 从顺序表到链表的思维迁移顺序表的逆序和删除操作在链表中也有对应的实现但思路完全不同。链表的逆序需要修改指针的指向删除需要调整前驱节点的 next 指针。如果你能把顺序表的操作理解透彻再学链表的操作会容易很多因为你知道要做什么只是怎么做的方式变了。我个人的学习路径是先把顺序表的每个操作手写三遍确保完全理解然后再学链表的对应操作对比两者的差异。这样学下来对数据结构的理解会非常扎实。最后分享一个我自己的习惯每次学完一个数据结构的基本操作我都会自己出五道变体题然后尝试用不同的方法去解。比如删除特定值这个操作我就想过如果要求删除所有重复元素怎么做如果要求只保留第一个出现的元素怎么做如果要求删除区间内的元素怎么做。这种自我提问的方式比被动刷题的效果好得多。