普通 C:二进制堆分段错误/重新分配错误

Question

我对 C 语言很陌生，但我认为我会在学习基本数据结构时学习它。无论如何，我在代码中出现错误的方式/位置时遇到了问题。

基本上，我遇到两种不同类型的错误：

1. 从堆中减去时的分段错误(@ 二进制堆长度 2 和 3(。
当我添加到二进制堆以使其长度达到
2. 4(及以上(然后减去长度 2 时，Malloc/Realloc 错误(当我这样做时，我也得到一个无效的二进制堆结构 @ 长度 3(。

基本上，我只是想看看我到底做错了什么来获得这种行为。另外，如果我的代码中有任何彻头彻尾的apping，我也想知道。

所以，这是我的代码：

void printArray(int array[], int size) {
printf("[");
for (int i = 0; i < size; i++) {
if (i == (size - 1)) {
printf("%d", array[i]);
} else {
printf("%d, ", array[i]);
}
}
printf("]n");
}
int getLeftChild(int h_array[], int p_index, int size) {
/* Summary: Obtains the `left child` of Parent at given parent index (p_index)
* 
* Input: `h_array` - The binary heap
*        `p_index` - The index of the parent that we are currently looking at
*        `size` - The size of the binary heap.
*
* Return: `0` if the index given points out of bounds of the array. Returns the child of parent at p_index if not
*/ 
int child = 0;
if (p_index * 2 + 1 < size) {
child = h_array[p_index * 2 + 1];
}
return child;
}
int getRightChild(int h_array[], int p_index, int size) {
/* Summary: Obtains the `right child` of Parent at given parent index (p_index)
* 
* Input: `h_array` - The binary heap
*        `p_index` - The index of the parent that we are currently looking at
*        `size` - The size of the binary heap.
*
* Return: `0` if the index given points out of bounds of the array. Returns the child of parent at p_index if not
*/ 
int child = 0;
if ((p_index * 2 + 2) < size) {
child = h_array[p_index * 2 + 2];
}
return child;
}
void heapSort(int h_array[], int size, int min_max) {
/* Summary: Performs a heap sort on a binary heap array; parents with 2 children maximum.
*          This could be used to implement a priority queue, as the node with the highest (or lowest)
*          priority will be at the root of the list.
* Input: `h_array` - the heap array to sort
*        `size` - The size of the heap array
*        `min_max` - an input that will tell whether or not we want to return a 'maxed', or a 'min'd' binary heap.
*                      maxed will have highest priority at the root, and min'd will have the lowest priority at the root
* 
* Returns: Does not return. Performs all sorting operations on input array.
**/
int parent, leftChild, rightChild, p_holder, i = 0;
while (i < (size / 2)) {
parent = h_array[i];
leftChild = getLeftChild(h_array, i, size);
rightChild = getRightChild(h_array, i, size);
if (min_max == 0 ) {
while (parent < leftChild || parent < rightChild) {
p_holder = parent;
if (parent < leftChild) {
h_array[i] = leftChild;
h_array[(i * 2) + 1] = p_holder;
} else if (parent < rightChild) {
h_array[i] = rightChild;
h_array[(i * 2) + 2] = p_holder;
}
i = 0;
parent = h_array[i];
leftChild = getLeftChild(h_array, i, size);
rightChild = getRightChild(h_array, i, size);
}
i++;
} else {
while ((leftChild != 0 && parent > leftChild) || (rightChild != 0 &&parent > rightChild)) {
p_holder = parent;
if ((leftChild != 0) && parent > leftChild) {
h_array[i] = leftChild;
h_array[(i * 2) + 1] = p_holder;
} else if ((rightChild != 0) && parent > rightChild) {
h_array[i] = rightChild;
h_array[(i * 2) + 2] = p_holder;
}
i = 0;
parent = h_array[i];
leftChild = getLeftChild(h_array, i, size);
rightChild = getRightChild(h_array, i, size);
}
i++;
}
}
}
void heapAdd(int h_array[], int *a_size, int value, int *min_max_ptr) {
/* Summary: Adds a value to the binary heap
* Input: `h_array` - The binary heap array
*        `a_size` - The size of the array. A pointer to `size` located in main().
*        `value` - The value that is to be inserted in the array
* Returns: Void function. Performs all operations on inputted array.
*/
*a_size += 1;
int * a_copy = h_array;
h_array = realloc(h_array, *a_size * sizeof(int));
memcpy(h_array, a_copy, (*a_size - 2) * sizeof(int));
h_array[*a_size - 1] = value;
heapSort(h_array, *a_size, *min_max_ptr);
}
void heapSub(int h_array[], int *a_size, int *min_max_ptr) {
/* Summary: Subtracts the root value from the binary heap
* Input: `h_array` - The binary heap array
*        `a_size` - The size of the array. A pointer to `size` located in main().
* Returns: Void function. Performs all operations on inputted array.
*/
h_array[0] = h_array[*a_size - 1];
int * a_copy = h_array;
h_array = realloc(h_array, *a_size - 1 * sizeof(int));
memcpy(h_array, a_copy, (*a_size - 1) * sizeof(int));
*a_size -= 1; // Put here in order to not do any stupid calculations in the calls.
heapSort(h_array, *a_size, *min_max_ptr);
}
int main(void) {
char * user_input;
int user_value;
int debug = 0;
// min_max = 0 to produce a max-heap, min_max = 1 to produce a min-heap
int min_max = 0;
int *min_max_ptr = &min_max;
int size = 0;
int *size_ptr = &size;
// Binary Heap array, initialized here
int * main_array = malloc(size * sizeof(int));
// Start building binary heap with the following loop.
while (strcmp(user_input, "q") != 0) {
printf("Current Heap:n");
printArray(main_array, size);
// Debug
if (debug) {
printf("Current Heap Size: %in", size);
}
printf("What is your input?: ");
scanf("%s", user_input);
// Debug
if (debug) {
printf("Current user input is: %sn", user_input);
}
if (strcmp(user_input, "add") == 0) {
printf("What # will you be adding to the heap?: ");
scanf("%i", &user_value);
heapAdd(main_array, size_ptr, user_value, min_max_ptr);
} else if (strcmp(user_input, "sub") == 0) {
printf("Subtracting %i from arrayn", main_array[0]);
heapSub(main_array, size_ptr, min_max_ptr);
} else if (strcmp(user_input, "debug") == 0) {
printf("Do you want to toggle debug mode(y/n): ");
scanf("%s", user_input);
if (strcmp(user_input, "y") == 0) {
debug = (debug == 0) ? 1 : 0;
printf("Debug is: %i", debug);
} else {
continue;
}
} else {
printf("Incorrect Input, please read the instructions morenn");
}
printf("n");
}
free(main_array);
return 0;
}

这就是代码，下面是测试用例：

1. 从堆中减去最大值 @ 长度 = 2 个测试用例 1
2. 从堆中减去最大值，从 @ 长度 = 4 开始，到长度 = 2 测试用例 2

在那之后，似乎其他所有测试用例都工作正常(过去的长度 = 4，我可以很好地从二进制堆中添加和减去，并且排序过程效果很好(。感谢您的帮助:)

Answer 1

我能够通过对代码进行以下更改来解决问题：

void heapAdd(int h_array[], int *a_size, int value, int *min_max_ptr) {
/* Summary: Adds a value to the binary heap
* Input: `h_array` - The binary heap array
*        `a_size` - The size of the array. A pointer to `size` located in main().
*        `value` - The value that is to be inserted in the array
* Returns: Void function. Performs all operations on inputted array.
*/
*a_size += 1;
h_array[*a_size - 1] = value;
heapSort(h_array, *a_size, *min_max_ptr);
}
void heapSub(int h_array[], int *a_size, int *min_max_ptr) {
/* Summary: Subtracts the root value from the binary heap
* Input: `h_array` - The binary heap array
*        `a_size` - The size of the array. A pointer to `size` located in main().
* Returns: Void function. Performs all operations on inputted array.
*/
h_array[0] = h_array[*a_size - 1];
h_array[*a_size - 1] = 0;
*a_size -= 1; // Put here in order to not do any stupid calculations in the calls.
heapSort(h_array, *a_size, *min_max_ptr);
}
int main(void) {
char * user_input;
int user_value;
int debug = 0;
// min_max = 0 to produce a max-heap, min_max = 1 to produce a min-heap
int min_max = 0;
int *min_max_ptr = &min_max;
int size = 0;
int *size_ptr = &size;
int alloc_size = 1000;
int * main_array = malloc(alloc_size * sizeof(int));
do {
if (alloc_size - size < 2) {
printf("Reallocating the main_array size");
alloc_size += 1000;
main_array = realloc(main_array, alloc_size * sizeof(int));
if (main_array == NULL) {
printf("realloc addition failed, exiting");
exit(1);
}
} else if (alloc_size - size > 1002) {
alloc_size -= 1000;
main_array = realloc(main_array, alloc_size * sizeof(int));
if (main_array == NULL) {
printf("Realloc subtraction failed, exiting");
exit(1);
}
}
printf("Current Heap:n");
printArray(main_array, size);
// Debug
if (debug) {
printf("Current Heap Size: %in", size);
}
printf("What is your input?: ");
scanf("%s", user_input);
// Debug
if (debug) {
printf("Current user input is: %sn", user_input);
}
if (strcmp(user_input, "add") == 0) {
printf("What # will you be adding to the heap?: ");
scanf("%i", &user_value);
heapAdd(main_array, size_ptr, user_value, min_max_ptr);
} else if (strcmp(user_input, "sub") == 0) {
if (size == 0) {
printf("Can't subtract any more from the heap.n");
continue;
} else {
printf("Subtracting %i from arrayn", main_array[0]);
heapSub(main_array, size_ptr, min_max_ptr);
}
} else if (strcmp(user_input, "debug") == 0) {
printf("Do you want to toggle debug mode(y/n): ");
scanf("%s", user_input);
if (strcmp(user_input, "y") == 0) {
debug = (debug == 0) ? 1 : 0;
printf("Debug is: %i", debug);
} else {
continue;
}
} else {
printf("Incorrect Input, please read the instructions more fullynn");
}
printf("n");
} while (strcmp(user_input, "q") != 0);
free(main_array);
return 0;
}