c - 将字符串重复拆分为更小部分的数据结构

Question

我正在尝试编写一个函数，将正则表达式模式与输入字符串重复匹配。该函数应采用模式 1 将其与输入字符串进行匹配，并将其拆分为匹配和非匹配段的部分。模式 2 随后将用于那些不匹配的段，直到使用所有输入模式。返回参数将是所有子字符串的数组。

简单的例子:

针对模式“bc”和“f”输入字符串“abcdefgh”，首先会将其拆分为“a”、“bc”和“defgh”。随后模式“f”将针对“a”和“defgh”部分运行，并将后者拆分为“de”、“f”和“gh”。返回参数 {"a", "bc", "de", "f", "gh"}

(我还会保留一个包含匹配/不匹配信息的关联数组)

但我的问题是:哪种数据结构最适合执行此类任务？以及如何最好地解决这个问题，感觉像是可以递归方式工作的东西。

Answer 1

链表会浮现在脑海中，每次您将正则表达式与特定节点匹配时，您都会删除有问题的节点并在其位置插入 3 个链接节点。

特定的“节点”结构可以像具有 3 个字段的结构一样简单，一个 char* 用于字符串，一个 bool (char 是否匹配以及指向下一个节点的指针。