c - 用数组中的另一个数据序列替换一个数据序列

Question

我需要用数组中的其他数据序列替换一些数据序列，例如在这个示例中(我为替换函数想象的签名):

seq_replace(
    int *array, size_t size0,      // The array to modify         + its size
    int *to_replace, size_t size1, // The sequence to be replaced + its size
    int *to_place, size_t size2);  // The sequence to be placed   + its size

int array[] = {0, 6, 3, 0, 6, 2};
seq_replace(
    &array, 6,
    (const int[]){0, 6}, 2,
    (const int[]){9}, 1);

并且会获得我的数组，其值为{9, 3, 9, 2}。

我认为链表更适合这种类型的任务，但我在整个项目中都使用数组，并且在容器类型之间进行转换会花费时间。

无论如何，我不知道有什么算法可以做这种事情，而且我也没有在互联网上找到任何有趣的东西。因此，我求助于此站点以获取有关如何执行此任务的建议。

Answer 1

这是在已知 array 足够大以进行任何替换的情况下工作的代码。该函数返回 array 的新逻辑大小。 //p += size2; 注释指令可以递归替换 to_place 的结果(就像窥孔优化器的情况一样)。例如在 {0,6,6} 中用 {0} 替换 {0,6} 得到 {0}。

有一个 main() 来测试各种情况。

#include <stdio.h>
#include <string.h>

void show_array(const int *array, size_t size0)
{
 int i;
  for(i = 0; i < size0; i++)
    printf("%3d", array[i]);
  puts("");
}

int seq_replace(int *array, size_t size0,            // The array to modify         + its size
                const int *to_replace, size_t size1, // The sequence to be replaced + its size
                const int *to_place, size_t size2)   // The sequence to be placed   + its size
{
  int *p = array, *end = array + size0;

  while(p < end)
    {
      if (p + size1 <= end && memcmp(p, to_replace, size1 * sizeof(*p)) == 0)
        {
          memmove(p + size2, p + size1, (end - p - size1) * sizeof(*p));
          memcpy(p, to_place, size2 * sizeof(*p));
          // p += size2; // uncomment to avoid replacements in to_place itself
          size0 = size0 - size1 + size2;
          end = array + size0;
        }
      else
        {
          p++;
        }
    }
  return size0; // return logical new size
}

#define N_ELEM(p) (sizeof(p) / sizeof(*(p)))

// array is physically large enough
int array[1000] = {0, 6, 6, 0, 6, 2, 0, 6, 0, 6};
int size0 = 10; // its logical length
int to_replace[] = {0, 6};
int to_place[] = {0}; // try {9, 8}, {9, 8, 7}, {9} and even {}

int main()
{

  printf("initial array; length: %d\n", size0);
  show_array(array, size0);

  size0 = seq_replace(array, size0,
                      to_replace, N_ELEM(to_replace),
                      to_place, N_ELEM(to_place));

  printf("final array, new length: %d\n", size0);
  show_array(array, size0);
}