使用指针算术删除子阵列

Question

我需要在C中使用指针算术来删除子阵列的函数C。功能应返回删除元素的数量。不允许辅助阵列。

#include <stdio.h>
int remove_subarray(int * first_start, int * first_end,const int * second_start,const int * second_end) {
  int size_of_second = second_end-second_start;
  int *subarray_start, *last = first_end - 1;
  const int *pok = second_start,*second_start_copy = second_start;
  int number_of_the_same = 0;
  while (first_start != first_end) {
    if ( * first_start == * second_start) {
      if (number_of_the_same == 0)
       subarray_start = first_start;
      first_start++;
      second_start++;
      number_of_the_same++;
      if (number_of_the_same == size_of_second) {
        first_start = subarray_start;
        while (1) {
          if ( *first_start == *last)
            break;
          subarray_start = first_start;
          subarray_start += size_of_second;
          *first_start = *subarray_start;
          first_start++;
        }
        break;
      }
    } else {
      number_of_the_same = 0;
      first_start++;
      second_start = second_start_copy;
    }
  }
  return size_of_second;
}
int main() {
  // This gives correct result
  int niz1[14] = {1, 2, 3, 4, 5, 6, 7, 0, 1, 2, 3, 4, 5, -1},i;
  int niz2[4] = {2, 3, 4, 5};
  int k1 = remove_subarray(niz1, niz1 + 14, niz2, niz2 + 4);
  for (i = 0; i < 14 - k1; ++i)
    printf("%i ", niz1[i]);
  printf("\n");
  // This gives wrong result
  int niz3[10] = {1, 1, 2, 3, 5, 6, 1, 2, 4, 10};
  int niz4[3] = {1, 2, 3};
  int k2 = remove_subarray(niz3, niz3 + 10, niz4, niz4 + 3);
  for (i = 0; i < 10 - k2; i++) printf("%d ", niz3[i]);
  return 0;
}

我的算法如下：

• 如果元素匹配，则将位置保存到指针 start
• 如果number_of_the_same（elements）等于第二个数组中的元素数量（n）（n）中的元素数量，则意味着
• 如果找到子阵列，则发现子阵列，i将所有元素设置为等于

在我尝试使用两组数组（ niz1和niz2 ）的主函数中向它们转发它们的元素，并且对于第一组，它的工作正常。但是，对于第二组数组（ niz3和niz4 ），它不正确。

您能帮我修复我的代码吗？

Answer 1

提供的代码很难阅读，因此也很难测试。至少对我来说。可能是作者可以使用更有意义的名称。

我认为原始代码中的错误是，在找到sub_array的第一个数字之后，如果搜索失败，则程序 不得推进数组的指针，因为当前值指向成为序列的真实开始，而前一个只是假阳性。在第二个提供的集合中，请参见Pair 1,1，

我将在一个示例中提供2个可能会有所帮助的选项。

a tl; dr部分现在处于结尾，示例

该方法在示例中的

想法是

• 您有一个数组，如果它包含某个sub_array，则需要使用sub_array做某事。像其他语言中的谓词函数。
• 这些参数是开放式片段，例如c ++ stl中的迭代器：第一个参数指向第一个元素，第二个参数点超过数组的末尾，
• 两个函数都在代码中
  • remove_subarray（）将整个sub_array移至数组末尾
  • mark_subarray（） int_max

  替换所有sub_array值

使事物更容易：很少有助手函数

int show_array（const int*，const int*，const char*）;

此功能具有5行：只需写下带有可选标题的数组，例如此处

    char buffer[80] = {0};
    sprintf(buffer, "%d elements moved. Resulting array:", res);
    show_array(array, array + sz_arr, buffer);

或此处的

    show_array(array, array + sz_arr, "Base array:");

样本输出：

3 elements moved. Resulting array:    [  1  2  4  10  5  6  1  1  2  3  ]

或

              Base array:    [  1  1  2  3  5  6  1  2  4  10  ]

<代码> int*find_sub_array（const int*，const int*，const int*，const int*）;

返回null如果在数组中找不到sub_array或sub_array。

这种类型的事物很容易由状态机A fsm 表达。在这里，我们需要一组2种国家的简约集：

• 一个在找到sub_array
• One的可能启动之前，以搜索sub_array的其余部分

可能的实现

int* find_sub_array(
    const int* arr_start, const int* arr_end,
    const int* sa_start, const int* sa_end)
{  
    char st    = 0;
    int* pA    = (int*)arr_start;
    int* pSA   = (int*)sa_start;
    int* sa_ix = 0;  // address of the sub_array in array
    while (1)
    {
        switch (st)
        {
            case 0:
                if (*pA == *pSA)
                {
                    st    = 1;
                    sa_ix = pA;         // found 1st
                    pSA += 1, pA += 1;  // both pointers up
                    break;
                }
                pA += 1;  // array pointer only
                break;
            case 1:
            default:
            {
                if (*pA != *pSA)
                {
                    pSA = (int*)sa_start;  // reset
                    st  = 0;               // back to search
                    break;
                }
                else
                    pSA += 1, pA += 1;  // both goup
                if (pSA == sa_end) return sa_ix;
                break;
            }
        };  // end switch()
        if (pA >= arr_end) return NULL;
    }
    return NULL;
}

remove> remove_subarray（）

使用这些功能，可以写remove_subarray（）以紧凑的方式

int remove_subarray(
    int* first_start, int* first_end,
    const int* second_start, const int* second_end)
{
    int* pos = find_sub_array(
        first_start, first_end, second_start, second_end);
    if (pos == NULL) return 0;
    int sz_sub_arr = (int)(second_end - second_start);
    for (int ix = 0; ix < sz_sub_arr; ix += 1)
        *pos++ = INT_MAX;  // set all elements to INT_MAX
    return sz_sub_arr;
}

测试多个版本

以上版本更改sub_array值。示例代码中的另一个将sub_array移至末尾。无论如何，这只是一个例子。

void test_with(
    int array[], int, int sub_arr[], int sz_sub_arr,
    int (*)(int*, int*, const int*, const int*));

这个接受了应用于参数的函数的名称，例如 c ++ 或 java in_each（） 。它在这样的示例中使用：

    printf("\nUsing 1st provided set\n");
    int niz3[10] = {1, 1, 2, 3, 5, 6, 1, 2, 4, 10};
    int niz4[3]  = {1, 2, 3};
    test_with(niz3, 10, niz4, 3, remove_subarray);

    int niz1[14] = {1, 2, 3, 4, 5, 6, 7,
                    0, 1, 2, 3, 4, 5, -1};
    int niz2[4]  = {2, 3, 4, 5};
    printf( "\
\nUsing 2nd provided set + function to set sub_array elements to "
        "INT_MAX\n\n");
    test_with(
        niz1, sizeof(niz1) / sizeof(niz1[0]), niz2,
        sizeof(niz2) / sizeof(niz2[0]), mark_subarray);

示例代码

total of 4 basic tests

Test 1 of 4:
              Base array:    [  1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  ]
               Sub_array:    [  1  2  3  ]
3 elements moved. Resulting array:    [  14  15  16  4  5  6  7  8  9  10  11  12  13  1  2  3  ]

Test 2 of 4:
              Base array:    [  1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  ]
               Sub_array:    [  1  2  4  ]
0 elements moved. Resulting array:    [  1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  ]

Test 3 of 4:
              Base array:    [  1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  ]
               Sub_array:    [  14  15  16  ]
[nothing to move: subarray found already at the end]
0 elements moved. Resulting array:    [  1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  ]

Test 4 of 4:
              Base array:    [  1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  ]
               Sub_array:    [  13  14  15  ]
3 elements moved. Resulting array:    [  1  2  3  4  5  6  7  8  9  10  11  12  16  13  14  15  ]

Using 1st provided set
              Base array:    [  1  1  2  3  5  6  1  2  4  10  ]
               Sub_array:    [  1  2  3  ]
3 elements moved. Resulting array:    [  1  2  4  10  5  6  1  1  2  3  ]

Using 2nd provided set + function to set sub_array elements to INT_MAX

              Base array:    [  1  2  3  4  5  6  7  0  1  2  3  4  5  -1  ]
               Sub_array:    [  2  3  4  5  ]
4 elements moved. Resulting array:    [  1  2147483647  2147483647  2147483647  2147483647  6  7  0  1  2  3  4  5  -1  ]

示例代码

#include <limits.h>
#include <stdio.h>

int* find_sub_array(
    const int*, const int*, const int*, const int*);
int  mark_subarray(int*, int*, const int*, const int*);
int  remove_subarray(int*, int*, const int*, const int*);
int  set_array(int*, size_t);
int  shift_array(int*, int*, int);
int  show_array(const int*, const int*, const char*);
void test_with(
    int array[], int, int sub_arr[], int sz_sub_arr,
    int (*)(int*, int*, const int*, const int*));

int main(void)
{
    int array[16]    = {0};
    int sz_arr       = sizeof(array) / sizeof(array[0]);
    int sub_arr[][3] = {
        {1, 2, 3}, {1, 2, 4}, {14, 15, 16}, {13, 14, 15}};
    const int sz_sub_arr =
        sizeof(sub_arr[0]) / sizeof(sub_arr[0][0]);
    const n_of_tests = sizeof(sub_arr) / sizeof(sub_arr[0]);

    printf("total of %d basic tests\n", n_of_tests);

    for (int tst = 0; tst < n_of_tests; tst += 1)
    {
        printf("\nTest %d of %d:\n", 1 + tst, n_of_tests);
        set_array(array, sz_arr);
        test_with(
            array, sz_arr, sub_arr[tst], sz_sub_arr,
            remove_subarray);
    }

    printf("\nUsing 1st provided set\n");
    int niz3[10] = {1, 1, 2, 3, 5, 6, 1, 2, 4, 10};
    int niz4[3]  = {1, 2, 3};
    test_with(niz3, 10, niz4, 3, remove_subarray);

    int niz1[14] = {1, 2, 3, 4, 5, 6, 7,
                    0, 1, 2, 3, 4, 5, -1};
    int niz2[4]  = {2, 3, 4, 5};
    printf(
        "\
\nUsing 2nd provided set + function to set sub_array elements to "
        "INT_MAX\n\n");
    test_with(
        niz1, sizeof(niz1) / sizeof(niz1[0]), niz2,
        sizeof(niz2) / sizeof(niz2[0]), mark_subarray);

    return 0;
}

int* find_sub_array(
    const int* arr_start, const int* arr_end,
    const int* sa_start, const int* sa_end)
{
    char st    = 0;
    int* pA    = (int*)arr_start;
    int* pSA   = (int*)sa_start;
    int* sa_ix = 0;  // address of the sub_array in array
    while (1)
    {
        switch (st)
        {
            case 0:
                if (*pA == *pSA)
                {
                    st    = 1;
                    sa_ix = pA;         // found 1st
                    pSA += 1, pA += 1;  // both pointers up
                    break;
                }
                pA += 1;  // array pointer only
                break;
            case 1:
            default:
            {
                if (*pA != *pSA)
                {
                    pSA = (int*)sa_start;  // reset
                    st  = 0;               // back to search
                    break;
                }
                else
                    pSA += 1, pA += 1;  // both goup
                if (pSA == sa_end) return sa_ix;
                break;
            }
        };  // end switch()
        if (pA >= arr_end) return NULL;
    }
    return NULL;
}

int mark_subarray(
    int* first_start, int* first_end,
    const int* second_start, const int* second_end)
{
    int* pos = find_sub_array(
        first_start, first_end, second_start, second_end);
    if (pos == NULL) return 0;
    int sz_sub_arr = (int)(second_end - second_start);
    for (int ix = 0; ix < sz_sub_arr; ix += 1)
        *pos++ = INT_MAX;  // set all elements to INT_MAX
    return sz_sub_arr;
}

int remove_subarray(
    int* first_start, int* first_end,
    const int* second_start, const int* second_end)
{
    int* pos = find_sub_array(
        first_start, first_end, second_start, second_end);
    if (pos == NULL) return 0;
    int sz_sub_arr = (int)(second_end - second_start);
    if ((first_end - pos - sz_sub_arr) == 0)
    {  // sub_array found but already at the end
        fprintf(
            stderr,
            "[nothing to move: subarray found already at "
            "the end]\n");
        return 0;
    }
    return shift_array(pos, first_end - 1, sz_sub_arr);
}

int set_array(int* v, size_t len)
{  // set the array from 1 to len
    for (int i = 0; i < len; v[i] = 1 + i, i += 1)
        ;
    return 0;
};

int shift_array(int* src, int* last, int len)
{  // shift sub_array to the end od the array
    int* l = src + len - 1;
    int* r = last;
    for (int x = 0; x < len; x += 1, --r, --l)
    {
        int temp = *r;
        *r       = *l;
        *l       = temp;
    }
    return (int)len;
}

int show_array(
    const int* vct, const int* past_end, const char* msg)
{
    if (msg != NULL) printf("%25s", msg);
    printf("    [");
    for (const int* p = vct; p != past_end; p += 1)
        printf("  %d", *p);
    printf("  ]\n");
    return 0;
}

void test_with(
    int array[], int sz_arr, int sub_arr[], int sz_sub_arr,
    int (*f)(int*, int*, const int*, const int*))
{
    show_array(array, array + sz_arr, "Base array:");
    show_array(
        sub_arr, sub_arr + sz_sub_arr, " Sub_array:");

    int res = (*f)(
        array, array + sz_arr, sub_arr,
        sub_arr + sz_sub_arr);

    char buffer[80] = {0};
    sprintf(
        buffer, "%d elements moved. Resulting array:", res);
    show_array(array, array + sz_arr, buffer);
    return;
}

tl; dr

第二个示例仅适用于原始测试用例的代码，find_array（）

示例2

#include <limits.h>
#include <stdio.h>

int* find_sub_array(
    const int*, const int*, const int*, const int*);
int  remove_subarray(int*, int*, const int*, const int*);
int  show_array(const int*, const int*, const char*);

int main(void)
{
    int niz1[14] = {1, 2, 3, 4, 5, 6, 7,
                    0, 1, 2, 3, 4, 5, -1};
    int niz2[4]  = {2, 3, 4, 5};
    printf("\nUsing 1st provided set\n");
    show_array(
        niz1, niz1 + sizeof(niz1) / sizeof(niz1[0]),
        "Base array:");
    show_array(
        niz2, niz2 + sizeof(niz2) / sizeof(niz2[0]),
        " Sub_array:");

    int res = remove_subarray(
        niz1, niz1 + sizeof(niz1) / sizeof(niz1[0]), 
        niz2, niz2 + sizeof(niz2) / sizeof(niz2[0]));

    char buffer[80] = {0};
    sprintf(
        buffer, "%d elements moved. Resulting array:", res);
    show_array(
        niz1, niz1 + sizeof(niz1) / sizeof(niz1[0]),
        "Resulting array:");

    printf("\nUsing 2nd provided set\n");
    int niz3[10] = {1, 1, 2, 3, 5, 6, 1, 2, 4, 10};
    int niz4[3]  = {1, 2, 3};
    show_array(niz3,niz3 + sizeof(niz3) / sizeof(niz3[0]),
        "Base array:");
    show_array(
        niz4,niz4 + sizeof(niz4) / sizeof(niz4[0]),
        " Sub_array:");

    res = remove_subarray(
       niz3,niz3 + sizeof(niz3) / sizeof(niz3[0]),
        niz4,niz4 + sizeof(niz4) / sizeof(niz4[0]));

    sprintf(
        buffer, "%d elements moved. Resulting array:", res);
    show_array(
        niz3, niz3 + sizeof(niz3) / sizeof(niz3[0]),
        "Resulting array:");

    return 0;
}

int* find_sub_array(
    const int* arr_start, const int* arr_end,
    const int* sa_start, const int* sa_end)
{
    char st    = 0;
    int* pA    = (int*)arr_start;
    int* pSA   = (int*)sa_start;
    int* sa_ix = 0;  // address of the sub_array in array
    while (1)
    {
        switch (st)
        {
            case 0:
                if (*pA == *pSA)
                {
                    st    = 1;
                    sa_ix = pA;         // found 1st
                    pSA += 1, pA += 1;  // both pointers up
                    break;
                }
                pA += 1;  // array pointer only
                break;
            case 1:
            default:
            {
                if (*pA != *pSA)
                {
                    pSA = (int*)sa_start;  // reset
                    st  = 0;               // back to search
                    break;
                }
                else
                    pSA += 1, pA += 1;  // both goup
                if (pSA == sa_end) return sa_ix;
                break;
            }
        };  // end switch()
        if (pA >= arr_end) return NULL;
    }
    return NULL;
}

int remove_subarray(
    int* first_start, int* first_end,
    const int* second_start, const int* second_end)
{
    int* pos = find_sub_array(
        first_start, first_end, second_start, second_end);
    if (pos == NULL) return 0;
    int sz_sub_arr = (int)(second_end - second_start);
    for (int ix = 0; ix < sz_sub_arr; ix += 1)
        *pos++ = INT_MAX;  // set all elements to INT_MAX
    return sz_sub_arr;
}

int show_array(
    const int* vct, const int* past_end, const char* msg)
{
    if (msg != NULL) printf("%25s", msg);
    printf("    [");
    for (const int* p = vct; p != past_end; p += 1)
        printf("  %d", *p);
    printf("  ]\n");
    return 0;
}

输出

Using 1st provided set
              Base array:    [  1  2  3  4  5  6  7  0  1  2  3  4  5  -1  ]
               Sub_array:    [  2  3  4  5  ]
         Resulting array:    [  1  2147483647  2147483647  2147483647  2147483647  6  7  0  1  2  3  4  5  -1  ]

Using 2nd provided set
              Base array:    [  1  1  2  3  5  6  1  2  4  10  ]
               Sub_array:    [  1  2  3  ]
         Resulting array:    [  1  2147483647  2147483647  2147483647  5  6  1  2  4  10  ]

Answer 2

您的算法有一个小错误，它仅比较子阵列的第一项与数组，如果匹配，则假定这是子阵列的开始，而无需看到以下项目。

标题文件

#include <stdio.h>

删除子数组的功能

int remove_sub(int *arr_start, int *arr_end, int *sub_start, int *sub_end)
{
    const int arr_len = arr_end - arr_start;
    const int sub_len = sub_end - sub_start;

    if (sub_len > arr_len)
        return 0;

    int *a_ptr = arr_start;
    int *s_ptr = sub_start;

    while (a_ptr != arr_end)
    {
        int count = 0;
        int *ptr = a_ptr;
        while (*ptr == *s_ptr && s_ptr != sub_end && ptr != arr_end)
        {
            ptr++;
            s_ptr++;
            count++;
        }
        if (count == sub_len)
        {
            int *start = a_ptr;
            int *end = arr_end;
            int *temp = a_ptr;

            for (int i = 0; i < sub_len; i++)
            {
                while (start != end)
                {
                    *a_ptr = *(++start);
                    a_ptr++;
                }
                a_ptr = temp;
                start = a_ptr;
                end--;
                arr_end--;
            }
        }
        s_ptr = sub_start;
        a_ptr++;
    }

    int *ptr = arr_start;
    while (ptr != arr_end)
    {
        printf("%d ", *ptr);
        ptr++;
    }

    return arr_end - arr_start;
}

主函数

int main()
{
    int arr[] = {1, 2, 3, 4, 5, 6, 7, 0, 1, 2, 3, 4, 5, -1};
    int sub[] = {2, 3, 4, 5};

    int size_arr = sizeof(arr) / sizeof(arr[0]);
    int size_sub = sizeof(sub) / sizeof(sub[0]);

    int size = remove_sub(arr, arr + size_arr, sub, sub + size_sub);
    printf("size: %d\n", size);

    return 0;
}

注意：指针算术也计数** （arr + i）

Answer 3

您可能需要利用内存功能（memcmp，memcpy），该功能可以加快代码并创建更优雅的解决方案。我不确定“使用指针算术”是否暗示不允许arr_start [i]。如果是这种情况，则应用 *（x+i）代替x [i]的每个引用，从而有效地用等效的指针算术代替索引。

int remove_sub(int *arr_start, int *arr_end, int *sub_start, int *sub_end)
{
    const int arr_len = arr_end - arr_start;
    const int sub_len = sub_end - sub_start;

    if (sub_len < 1 || sub_len > arr_len)
        return 0;

    // Search in arr position 0 .. (arr_len - sub_len)
    for (int i=0 ; i<arr_len-sub_len ; i++ ) {
        int *curr_arr = arr_start + i ;

        // Move to next element, if match not found
        if ( memcmp(curr_arr, sub_start, sub_len*sizeof(*sub_start) )
            continue ;

        // Match found: remove it and return
        int arr_tail = arr_len - i - sub_len ;
        memmove(curr_arr, curr_arr+sub_len, arr_tail*sizeof(*arr_start)) ;
        return sub_len ;
     }
     // No match found at all, return 0, no change to array.
     return 0 ;
} ;

免责声明：我没有编译/测试。可能有错别字。