0
我对C非常陌生，但我认为在学习基本数据结构时我会学习它。无论如何，我遇到了一个问题，关于我的代码中出现错误的方式/位置。普通C：二进制堆分段故障/重新分配错误
基本上，我发现了两种不同类型的错误：
- 分割错误（@二进制堆长度2和3）从堆减去时。
- 当我添加到二进制堆足够长，使其长度4（及以上），然后减去长度2（我得到一个无效的二进制堆结构@长度为3时，我也这样做，以及malloc/Realloc错误）。
基本上，我只是想看看我究竟做错了什么来获得这种行为。另外，如果我的代码中有什么是彻头彻尾的appaling，我也想知道。
所以，这里是我的代码：
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: %i\n", size);
}
printf("What is your input?: ");
scanf("%s", user_input);
// Debug
if (debug) {
printf("Current user input is: %s\n", 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 array\n", 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\n\n");
}
printf("\n");
}
free(main_array);
return 0;
}
所以这是代码，这里的测试用例：
- 减去堆@长度= 2 test case 1
- 减去最高最高值堆起始长度= 4且长度= 2的值test case 2
之后，似乎每个其他测试用例都可以正常工作（过去的长度= 4，我可以从二进制堆中加减，而且排序过程效果很好）。谢谢您的帮助:)
1）'而（STRCMP（USER_INPUT，“Q”）！ = 0）{'这使用未初始化的变量'user_input'。 'scanf（“％s”，user_input）;'是一样的。 – BLUEPIXY
您可以重新分配一个函数，但该指针会丢失，因为它不会返回到任何位置，并且可能会继续使用旧的未分配的内存区域。这很可能会导致你的问题。使用调试器来遍历代码。 –
你可能也想在'valgrind'下运行你的代码（很简单，但速度很慢，可能不准确，尤其是在优化时）或AddressSanitizer（需要重建，除非在极端条件下非常快速和准确，并且即使在优化时也可以运行） – o11c