I need to make a function for removing subarray using pointer arithmetic in C. Function should return number of removed elements. Auxiliary arrays are not allowed.

#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;
}

My algorithm is the following:

• if elements match, save position to pointer start
• if number_of_the_same (elements) is equal to number of elements in second array (n) that means subarray is found
• if subarray is found, I set all elements to be equal to the elements that are n positions forward them

In the main function I tried with two set of arrays (niz1 and niz2) and for the first set it worked correct. However it didn't work correct for second set of arrays (niz3 and niz4).

Could you help me to fix my code?

CodePudding user response：

There is a little mistake in your algorithm, It only compares the first item of the subarray to the array and if it matches it assumes that this is the starting of the subarray without seeing the following items.

header files

#include <stdio.h>

function to remove sub array

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;
}

main function

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;
}

Note: Pointer Arithmetic also counts *(arr i)

CodePudding user response：

You might want to take advantage of memory function (memcmp, memcpy), which can speed up the code, and create more elegant solution. I'm not sure if "using pointer arithmetic" implied that arr_start[i] is not allowed. If this is the case, then every reference to X[i] should be replaced with *(X i), effectively replacing indexing with the equivalent pointer arithmetic.

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 ;
} ;

Disclaimer: I did not compile/test. Possible that there are typos.