2014-02-12 87 views
-1

我只是在C堆陣列。但運行時,它給我分段錯誤(核心轉儲)...我不知道我在哪裏試圖訪問未分配的內存!分段故障,而heapifying

#include<stdio.h> 

int n; 

int left(i) 
{ 
    return (2*i); 
} 

int right(i) 
{ 
    return (2*i + 1); 
} 


void min_heap(int a[],int i) 
{ 
    int l=left(i); 
    int r=right(i); 
    int min; 

    if((l<=n)&&(a[l]<=a[i])&&(a[l]<=a[r])) 
    { 
     min=a[l]; 
     a[i]=a[i]+a[l]; 
     a[l]=a[i]-a[l]; 
     a[i]=a[i]-a[l]; 
    } 
    else if((r<=n)&&(a[r]<=a[i])&&(a[r]<=a[l])) 
    { 
     min=a[r]; 
     a[i]=a[i]+a[r]; 
     a[r]=a[i]-a[r]; 
     a[i]=a[i]-a[r]; 
    } 

    min_heap(a,min); 
} 



int main() 
{ 
    printf("The no is : "); 
    scanf("%d",&n); 
    int i,a[n+1]; 

    for(i=1;i<=n;i++) 
    { 
     scanf("%d",&a[i]); 
    } 

    for(i=n/2;i>=1;i--) 
    { 
     min_heap(a,i); 
    } 

    for(i=1;i<=n;i++) 
    { 
     printf("%d",a[i]); 
    } 

    return 0; 
} 
+2

不適用於任何關於! – haccks

+1

我不清楚'if'和'else'塊中的計算應該做什麼;它看起來不像一個簡單的交換。你檢查'l <= n',但是如果'l == n',那麼'r> n',當你訪問'a [r]'時你會遇到問題。如果你的數組的大小是10('n == 10'),並且數組中的值是1000000以上,那麼你使用'min = a [l];'或'min = a [r];'表示你將在一個應該比實際大得多的數組上進行遞歸。有一個全局變量'n'是俗套的;將它作爲參數傳遞給函數。 –

+0

@JonathanLeffler:那些交換(但不是直截了當的)。我建議將它們改爲使用臨時的舊式掉期。特別是因爲'min'已經在那裏作爲臨時的了。 –

回答

0

撥打min_heap(a,i)i == n/2

在這種情況下,內部min_heap()調用right()實際上將返回:

(2 * (n/2) + 1) 

n甚至將導致的n+1右索引和訪問a[r](與r == n+1)是超過端你分配的數組。

我不確定這是否是您的段錯誤的原因;我猜可能還有其他問題。

你可能只需要用調試器執行一次運行。

0

以下是由Jon Bentley編寫的More Programming Pearls的一些代碼,作爲C語言文件中的註釋編寫。完整的代碼與你無關;它是通用接口,如bsearch()qsort()的接口,但是這寫在awk

/* 
** See Appendix 2 of Jon Bentley "More Programming Pearls". 
** See also Column 14 of Jon Bentley "Programming Pearls, 2nd Edn". 
** Note that MPP algorithms are in terms of an array indexed from 1. 
** C, of course, indexes arrays from zero. 
** 
** 1-based identities. 
** root   = 1 
** value(i)  = x(i) 
** leftchild(i) = 2*i 
** rightchild(i) = 2*i+1 
** parent(i)  = i/2 
** null(i)  = (i < 1) or (i > n) 
** 
** 0-based identities. 
** root   = 0 
** value(i)  = x(i) 
** leftchild(i) = 2*(i+1)-1 = 2*i+1 
** rightchild(i) = 2*(i+1)+1-1 = leftchild(i)+1 
** parent(i)  = (i+1)/2-1 
** null(i)  = (i < 0) or (i >= n) # NB: i < 0 irrelevant for unsigned numbers 
*/ 

/* 
** function swap(i, j t) { 
**  # x[i] :=: x[j] 
**  t = x[i] 
**  x[i] = x[j] 
**  x[j] = t 
** } 
** 
** function siftup(l, u, i, p) { 
**  # pre maxheap(l, u-1) 
**  # post maxheap(l, u) 
**  i = u 
**  while (1) { 
**   # maxheap(l, u) except between i and its parent 
**   if (i <= l) break 
**   p = int(i/2)  # p = parent(i) 
**   if (x[p] >= x[i]) break 
**   swap(p, i) 
**   i = p 
**  } 
** } 
** 
** function siftdown(l, u, i, c) { 
**  # pre maxheap(l+1, u) 
**  # post maxheap(l,u) 
**  i = l 
**  while (1) { 
**   # maxheap(l, u) except between i and its children 
**   c = 2*i   # c = leftchild(i) 
**   if (c > u) break; 
**   if (c + 1 <= u && x[c+1] > x[c]) c++ 
**   if (x[i] >= x[c]) break 
**   swap(c, i) 
**   i = c 
**  } 
** } 
** 
** function hsort( i) { 
**  # post sorted(1, n) 
**  for (i = int(n/2); i >= 1; i--) 
**   siftdown(i, n) 
**  for (i = n; i >= 2; i--) { 
**   swap(1, i) 
**   siftdown(1, i-1) 
**  } 
** } 
*/ 

在代碼中,被排序的數組是x,索引從1N