我需要在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个位置的元素
在main函数中，我尝试了两组数组(niz1和niz2)，对于第一组，它工作正确。然而，对于第二组数组(niz3和niz4)，它不能正确工作。
你能帮我修改我的代码吗?
提供的代码很难阅读，因此也很难测试。至少对我来说是这样。也许作者可以用更有意义的名字。
我认为原始代码中的错误是，在找到sub_array的第一个数字后，如果搜索失败，程序必须不向前移动数组的指针，因为指向的当前值可能是序列的真正开始，而前面的值只是一个假阳性。参见第二个提供集
中的1,1对我将举一个有两个选项的例子，可能会有所帮助。
TL;DR部分现在以一个更短的示例结束了
示例中的方法
意思是
- 你有一个数组，如果它包含一个特定的sub_array，你需要对sub_array做一些事情。类似于其他语言中的谓词函数。
- 参数是开放的段，就像
C++ STL中的迭代器一样:第一个参数指向第一个元素，第二个参数指向数组的末尾 - 两个函数在代码中
remove_subarray()，将整个sub_array移动到数组的末尾mark_subarray()将所有sub_array值替换为INT_MAX
让事情变得更简单:一些帮助函数
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的地址。
这种类型的东西很容易用状态机FSM来表示。这里我们需要一个包含两个状态的极简集合:
- one before find sub_array
- 一个用于搜索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_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中的for_each()。它在示例中使用如下:
printf("nUsing 1st provided setn");
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_MAXnn");
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 testsn", 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 setn");
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_MAXnn");
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;博士
第二个例子只有原始测试用例和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 setn");
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 setn");
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 ]
你的算法有一个小错误，它只比较子数组的第一项和数组，如果匹配，它假设这是子数组的开始，而不看到下面的项。
头文件
#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: %dn", size);
return 0;
}
注意:指针算术也计数*(arr + i)
您可能希望利用内存函数(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 ;
} ;
声明:我没有编译/测试。可能有错别字