分段错误:11,当我测试书中的堆排序代码时 'Introduction to Algorithms'
Segmentation fault: 11, when I test heapsort code from book 'Introduction to Algorithms'
我用C执行书'Introduction of Algorithms'中heapsort的伪代码,出现错误:Segmentation fault: 11,内存溢出有什么问题吗?
#define LEFT(i) 2*i;
#define RIGHT(i) 2*i+1;
#define PARENT(i) i/2;
/************************************************/
/*heap_sort -- stable
*In order to easily determine the relationship of index between parent node and child nodes,
*available index of arr starts from 1.
*/
/************************************************/
/*
Available index of arr starts from 1.
Length represents the last element's index.
Heap_size is biggest range in arr.
*/
typedef struct {
int heap_size;
int length;
int *arr;
} heap;
/*
Node i's left_child tree and right_child tree are all max heap.
This function put node i's value into proper position in oder to keep a max heap.
*/
void max_heapify(heap h, int i) {
int *arr = h.arr;
int left = LEFT(i);
int right = RIGHT(i);
int largest = i;
if (arr[left] > arr[i] && left <= h.heap_size)
largest = left;
if (arr[right] > arr[largest] && right <= h.heap_size)
largest = right;
if (largest != i) {
exchange(h.arr + i, h.arr + largest);
max_heapify(h, largest);
}
return;
}
/*
Build a max heap.
*/
void build_max_heap(heap h) {
h.heap_size = h.length;
for (int i = h.length / 2; i > 0; i--) //leaf nodes need not to call max_heapify
max_heapify(h, i);
return;
}
void heap_sort(heap h) {
build_max_heap(h);
int *arr = h.arr;
for (int i = h.length; i > 1; i--) {
exchange(arr + 1, arr + i);
h.heap_size--;
max_heapify(h, 1);
}
return;
}
int main() {
int arr[] = {1,4,9,0,2,1,6,2};
int num = sizeof(arr) / sizeof(int);
heap h = {0, num - 1, arr};
heap_sort(h);
for (int i = 1; i < num; i++) {
printf("%d,", arr[i]);
}
return 0;
}
最大堆是一棵二叉树,其中一个节点的值大于其左右子节点的值。
在您的 max_heapify()
函数中,首先您需要检查 left
或 right
是否仍在边界内 - 即它们是 <= h.heap_size
,并且仅当它们是在绑定中,那么您需要评估 arr[left]
或 arr[right]
的值。但是,你正在做相反的事情。因此,当尝试超出范围时尝试访问 arr[left]
或 arr[right]
时,您的程序会崩溃。这可以通过更改 if
语句中的条件顺序来解决,如下所示。
void max_heapify(heap h, int i) {
int *arr = h.arr;
int left = LEFT(i);
int right = RIGHT(i);
int largest = i;
/* ISSUE: You are evaluating first, checking bounds second */
/* if (arr[left] > arr[i] && left <= h.heap_size) */
/* Right way: Check bounds first, evaluate second */
if (left <= h.heap_size && arr[left] > arr[i]) /* Right */
largest = left;
/* ISSUE: You are evaluating first, checking bounds second */
/* if (arr[right] > arr[largest] && right <= h.heap_size) */
/* Right way: Check bounds first, evaluate second */
if (right <= h.heap_size && arr[right] > arr[largest])
largest = right;
if (largest != i) {
exchange(h.arr + i, h.arr + largest);
max_heapify(h, largest);
}
return;
}
以上更改应该可以解决您的程序崩溃问题。
但是您的代码中还有一个问题 - 与您的程序崩溃无关,但会给出错误的结果。您还需要在 heap_sort()
函数中设置 h.heap_size = h.length
。这是因为,由于您要传递堆 h
,按值设置 build_max_heap()
函数中的 h.heap_size = h.length;
不会影响 heap_sort()
中 h.heap_size
的值功能。您需要在 heap_sort()
函数中再次明确地执行此操作。
void heap_sort(heap h)
{
build_max_heap(h);
int *arr = h.arr;
h.heap_size = h.length; /* This statement REQUIRED here */
for (int i = h.length; i > 1; i--)
{
exchange(arr + 1, arr + i);
h.heap_size = h.heap_size - 1;
max_heapify(h, 1);
}
return;
}
我用C执行书'Introduction of Algorithms'中heapsort的伪代码,出现错误:Segmentation fault: 11,内存溢出有什么问题吗?
#define LEFT(i) 2*i;
#define RIGHT(i) 2*i+1;
#define PARENT(i) i/2;
/************************************************/
/*heap_sort -- stable
*In order to easily determine the relationship of index between parent node and child nodes,
*available index of arr starts from 1.
*/
/************************************************/
/*
Available index of arr starts from 1.
Length represents the last element's index.
Heap_size is biggest range in arr.
*/
typedef struct {
int heap_size;
int length;
int *arr;
} heap;
/*
Node i's left_child tree and right_child tree are all max heap.
This function put node i's value into proper position in oder to keep a max heap.
*/
void max_heapify(heap h, int i) {
int *arr = h.arr;
int left = LEFT(i);
int right = RIGHT(i);
int largest = i;
if (arr[left] > arr[i] && left <= h.heap_size)
largest = left;
if (arr[right] > arr[largest] && right <= h.heap_size)
largest = right;
if (largest != i) {
exchange(h.arr + i, h.arr + largest);
max_heapify(h, largest);
}
return;
}
/*
Build a max heap.
*/
void build_max_heap(heap h) {
h.heap_size = h.length;
for (int i = h.length / 2; i > 0; i--) //leaf nodes need not to call max_heapify
max_heapify(h, i);
return;
}
void heap_sort(heap h) {
build_max_heap(h);
int *arr = h.arr;
for (int i = h.length; i > 1; i--) {
exchange(arr + 1, arr + i);
h.heap_size--;
max_heapify(h, 1);
}
return;
}
int main() {
int arr[] = {1,4,9,0,2,1,6,2};
int num = sizeof(arr) / sizeof(int);
heap h = {0, num - 1, arr};
heap_sort(h);
for (int i = 1; i < num; i++) {
printf("%d,", arr[i]);
}
return 0;
}
最大堆是一棵二叉树,其中一个节点的值大于其左右子节点的值。
在您的 max_heapify()
函数中,首先您需要检查 left
或 right
是否仍在边界内 - 即它们是 <= h.heap_size
,并且仅当它们是在绑定中,那么您需要评估 arr[left]
或 arr[right]
的值。但是,你正在做相反的事情。因此,当尝试超出范围时尝试访问 arr[left]
或 arr[right]
时,您的程序会崩溃。这可以通过更改 if
语句中的条件顺序来解决,如下所示。
void max_heapify(heap h, int i) {
int *arr = h.arr;
int left = LEFT(i);
int right = RIGHT(i);
int largest = i;
/* ISSUE: You are evaluating first, checking bounds second */
/* if (arr[left] > arr[i] && left <= h.heap_size) */
/* Right way: Check bounds first, evaluate second */
if (left <= h.heap_size && arr[left] > arr[i]) /* Right */
largest = left;
/* ISSUE: You are evaluating first, checking bounds second */
/* if (arr[right] > arr[largest] && right <= h.heap_size) */
/* Right way: Check bounds first, evaluate second */
if (right <= h.heap_size && arr[right] > arr[largest])
largest = right;
if (largest != i) {
exchange(h.arr + i, h.arr + largest);
max_heapify(h, largest);
}
return;
}
以上更改应该可以解决您的程序崩溃问题。
但是您的代码中还有一个问题 - 与您的程序崩溃无关,但会给出错误的结果。您还需要在 heap_sort()
函数中设置 h.heap_size = h.length
。这是因为,由于您要传递堆 h
,按值设置 build_max_heap()
函数中的 h.heap_size = h.length;
不会影响 heap_sort()
中 h.heap_size
的值功能。您需要在 heap_sort()
函数中再次明确地执行此操作。
void heap_sort(heap h)
{
build_max_heap(h);
int *arr = h.arr;
h.heap_size = h.length; /* This statement REQUIRED here */
for (int i = h.length; i > 1; i--)
{
exchange(arr + 1, arr + i);
h.heap_size = h.heap_size - 1;
max_heapify(h, 1);
}
return;
}