递归移除所有相邻重复项

引言

涉及从字符串中移除相邻重复项的编程问题非常普遍，而 C 语言为实现有效解决方案提供了绝佳的框架。本文将讨论几种我们将用于使用 C 编程语言递归地从给定字符串中移除所有相邻重复项的方法。每种方法都将被分解、检查并进行性能优化。

方法 1：暴力枚举法

移除 C 语言中相邻重复项的暴力方法采用简单的双循环结构。内层循环将当前字符与之后的所有字符进行比较，以查找相邻的重复项。相比之下，外层循环遍历输入字符串中的每个字符。为了消除重复项，当发现重复项时，使用 `memmove` 函数将字符串的剩余部分向左移动。字符串会相应地变长，内层循环变量会减小，以防止跳过后续的相邻重复项。虽然此方法功能齐全，但其时间复杂度为 O(n^2)，这意味着对于较大的字符串效率较低。这是因为移除过程需要多次遍历字符串，在某些情况下可能会导致性能问题。

代码

输出

代码解释

双循环迭代

removeAdjacentDuplicates 函数使用双循环结构遍历字符串中的每个字符。当由 j 控制的内层循环查找从下一个字符开始的相邻重复项时，由变量 i 控制的外层循环继续从头开始遍历字符串。

重复项移除逻辑

当索引 i 和 j 处的字符在相邻重复项中相等时，使用 memmove 函数将字符串的剩余部分向左移动一位，从而消除重复项。接下来，使用变量 len 递减并反映修改后的字符串长度。

更改循环变量

移除重复项后，内层循环变量 j 会递减 (j--)，以确保所有重复项都得到正确移除。此更改可防止遗漏任何可能接连出现的重复项。

原地修改

重复字符在同一字符串 (str) 中被原地消除。这意味着不会分配新内存；相反，原始字符串会直接被修改。但是，由于移位操作的时间复杂度为 O(n^2)，因此对于较长的字符串，此方法可能不是最有效的。

示例用法

在 main 函数中给出了一个示例字符串 "abbaccddeeff"，并在移除相邻重复项之前和之后分别打印了原始字符串和修改后的字符串。这演示了如何使用 removeAdjacentDuplicates 函数解决该问题。

方法 2：递归方法

为了移除给定字符串中的相邻重复项，递归方法使用一种更复杂有效的方法。递归调用的 {removeAdjacentDuplicatesRecursive} 函数是该技术的核心组成部分。通过重新排列字符串的剩余部分，此函数会移除遍历字符串并查找相邻重复项的任何重复项。递归会一直持续到不再发现相邻重复项为止，从而确保了完整的移除过程。该策略通过递归移除重复项实现了 O(n) 的时间复杂度，这使其比暴力方法更具可扩展性和有效性。

代码

输出

代码解释

递归函数

removeAdjacentDuplicatesRecursive 是此代码中的主要函数，它递归地从提供的字符串中移除相邻的重复字符。当在遍历字符串时发现相邻重复项时，它会移动下一个字符以移除重复项，然后进行递归调用以继续。

字符串遍历

该函数使用循环逐个字符地遍历输入字符串。由于它将每个字符与其相邻字符（即 str[i] 与 str[i + 1]）进行比较，因此循环会一直持续到倒数第二个字符。

移除重复项

当函数找到相邻的重复字符时，它会在嵌套循环（for (j = i; j < len - 1; j++)) 中将后续字符向左移动。这有效地移除了重复项。通过将最后一个字符 (str[len - 1]) 设置为 '\0' 来为修改后的字符串添加 null 终止符。

递归触发

一旦移除了相邻的重复项，该函数就会递归调用自身（removeAdjacentDuplicatesRecursive(str)）以在修改后的字符串中查找和移除重复项。直到不再发现相邻重复项为止，此过程都会重复。

打印结果

在调用 removeAdjacentDuplicatesRecursive 函数之前和之后，分别打印原始字符串和修改后的字符串。main 函数提供了一个示例字符串 ("abbaccddeeff")。这说明了递归移除相邻重复项的有用性。

终止和返回

成功执行 main 函数后，程序通过返回 0 来结束。当修改后的字符串（现在已无相邻重复项）打印到控制台时，用户可以看到递归移除过程的结果。

方法 3：基于栈的方法

一种在 C 语言中递归移除字符串中相邻重复项的有效方法是使用基于栈的方法。此方法使用栈数据结构遍历输入字符串，以跟踪非重复字符。算法在遍历字符串中的每个字符时，将非重复字符压入栈。当发现重复项时，将栈顶元素弹出。在一次遍历字符串的过程中，此过程可以有效地移除相邻的重复项，将修改后的字符串保留在栈中。与暴力方法相比，基于栈的方法在时间复杂度上有了显著的改进，将其提高到 O(n)。这意味着它对于较大的字符串更具可扩展性。此外，null 终止字符数组可确保正确的字符串终止。由于在简单性和整体效率之间取得了平衡，因此基于栈的方法是 C 语言中递归移除相邻重复项的可行解决方案。

代码

输出

代码解释

函数定义

该代码定义了 removeAdjacentDuplicatesStack 函数，该函数采用基于栈的方法来移除字符数组 (str) 中的相邻重复项。通过操作索引（stackIndex）并确保将唯一字符压入栈，该函数会对输入字符串进行原地修改。

基于栈的方法

为了有效地处理相邻重复项，removeAdjacentDuplicatesStack 函数利用了栈。在迭代处理输入字符串中的每个字符时，它将其与栈顶元素（str[stackIndex - 1]）进行比较。如果发现重复项，则通过递减栈索引来有效地移除相邻重复项。如果字符被视为非重复项且不是重复项，则增加栈索引以将字符压入栈。

迭代过程

该函数在遍历整个输入字符串时，逐个评估每个字符。栈有助于跟踪到目前为止尚未重复的字符。由于这种迭代过程，修改后的字符串中的非重复字符的顺序得以保留。

有效的内存使用

与重复移动字符串部分的暴力方法相比，基于栈的方法优化了内存使用。在一次字符串遍历中移除重复项，从而实现了更节省内存的解决方案。通过将 null 终止符 ('\0') 正确放置在修改后的字符串末尾，可以确保正确终止。

main 函数中的示例用法

main 函数中应用了 removeAdjacentDuplicatesStack 函数到一个示例字符串 ("abbaccddeeff")，以演示其用法。创建并显示了原始字符串的一个副本（modifiedString）。在对复制的字符串调用该函数后，将打印修改后的结果，该结果显示了相邻重复项是如何被移除的。

防止修改原始字符串

为了在应用相邻重复项移除之前保护原始字符串，代码会创建原始字符串的副本（modifiedString）。通过确保原始字符串不被更改，此技术使得在不改变原始数据的情况下比较和演示概念成为可能。修改后的字符串反映了移除过程的结果。