Ç通用堆排序 [英] c generic heapsort
问题描述
好了,所以我需要建立在C通用堆排序,这是我迄今为止
(我可能会丢失在code一些闭幕括号,但他们只是迷路了,当我搬到这里我的code)
Okay so I need to create a 'generic' heapsort in c and this is what I have so far (I might be missing some closing brackets in code but they just got lost when I moved my code here)
void srtheap(void *, size_t, size_t, int (*)(const void *, const void *));
void heapify(void *, size_t, size_t, size_t, int (*)(const void *, const void *));
void srtheap(void *base, size_t nelem, size_t size, int (*compar)(const void *, const void *)) {
void *p1, *p2;
void *last = base + (size*(nelem-1));
for (size_t curpos = nelem-1; curpos>0; curpos-2){
p1 = base + ((curpos-1)/2)*size;
if(compar(last, (last-size)) >= 0){
if(compar(last, p1) > 0){
swap(last, p1, size);
heapify(base, nelem, curpos, size, compar);
}
}
else { //LEFT>RIGHT
if(compar(last-size, p1) > 0){
swap(last-size, p1, size);
heapify(base, nelem, curpos-1, size, compar);
}
//otherwise, parent is greater than LEFT & RIGHT,
//or parent has swapped with child, iteration done, repeat through loop
} //end else, children have been compared to parent
//end check for two children, only left child if this loop is skipped
last = last-(2*size);
}
/*
**Now heapify and sort array
*/
while(nelem > 0){
last = base + (size*(nelem-1));
swap(base, last, size);
nelem=nelem-1;
heapify(base, nelem, 0, size, compar); //pass in array, #elements, starting pos, compare
}
}
void heapify(void *root, size_t numel, size_t pos, size_t sz, int (*compar)(const void *, const void *)){
void *rc, *lc, *p1;
while(pos < numel){
rc = root+((pos+1)*2)*sz; //right child
lc = root+(((pos+1)*2)-1)*sz; //left child
p1 = root+(pos*sz); //parent
if((pos+1)*2 < numel){ //check if current element has RIGHT
if (compar(rc, lc)>=0){
if(compar(rc, p1)>0) {
swap(rc, p1, sz);
pos=(pos+1)*2; //move to RIGHT, heapify
}
else {
pos = numel; //PARENT>LEFT&RIGHT, array is heapified for now
}
} //end RIGHT>LEFT
else { //LEFT>RIGHT
if(compar(lc, p1) >0 ) {
swap(lc, rc, sz);
pos=((pos+1)*2)-1; // move to LEFT, heapify
}
else {
pos = numel; //PARENT>LEFT&RIGHT, array is heapified for now
} //end inner if, else
}//end LEFT,RIGHT comparison
}//end check for RIGHT
else if (((pos+1)*2)-1 < numel){ //else, check if element has LEFT
if(compar(lc, p1)>0){
swap(lc, p1, sz);
pos=((pos+1)*2)-1; //move to LEFT, continue heapify
}
else {
pos = numel; //PARENT>LEFT, array is heapified for now
}
}//end check for LEFT
else { //current element has no children, array is heapified for now
pos = numel;
}
}
}
另外我有包括比较功能的主文件。
本质上,阵列的基址,元件的数目,每个元件的尺寸,并比较函数传递到我的堆排序的功能。
In addition I have a main file that includes a compare function. Essentially, the base address of the array, number of elements, size of each element, and the compare function are passed into my heapsort functions.
当我跑我得到一个分段错误的计划,我想办法,我试图访问未分配给我的记忆。
所以我想我不知道有没有人看到我的非法访问内存地址或可能指向我一个调试器,我可以用它来弄清楚什么问题?
When I run the program I am getting a segmentation fault which I assume means I am trying to access memory that is not allocated to me. So I guess I'm wondering does anybody see any problems where I am accessing illegal memory addresses or could point me to a debugger that I can use to figure it out?
谢谢!
推荐答案
调试器经常在内存中诊断错误的来源是有用的。我们知道,当你从一个调试器中运行你的code会发生什么。
Debuggers are often useful in diagnosing sources of memory errors. Let us know what happens when you run your code from a debugger.
这篇关于Ç通用堆排序的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!