0

我在机器上运行双音排序顺序代码。它对于最多 16 个元素的数组大小运行良好，但是一旦我将大小增加到 32，它在执行时会出现以下错误：

“警告：进程 654 终止：分段错误 (11)。”

有人可以帮我怎么回事吗？当大小增加到32时它会占用很多内存这是为什么会出现这个问题吗？

我想将其测试为并行版本。所以，我需要一些相当长的数组大小进行比较..

以下是我的代码：

void merge_up(int *arr, int n)
{
int step=n/2,i,j,k,temp;

while (step > 0)
        {

                for (i=0; i < n; i+=step*2)
                {
                        for (j=i,k=0;k < step;j++,k++)
                        {
                                        if (arr[j] > arr[j+step])
                                        { // swap
                                                temp = arr[j];
                                                arr[j]=arr[j+step];
                                                arr[j+step]=temp;
                                        }
                        }
                }
                step /= 2;
        }
}

void merge_down(int *arr, int n)
{

        int step=n/2,i,j,k,temp;
                while (step > 0)
                {
                        for (i=0; i < n; i+=step*2)
                        {
                                for (j=i,k=0;k < step;j++,k++)
                                {       if (arr[j] < arr[j+step])
                                        {       // swap
                                                temp = arr[j];
                                                arr[j]=arr[j+step];
                                                arr[j+step]=temp;
                                        }
                                }
                        }
                        step /= 2;
                }
}

int main(int argc, char **argv)
{

int n, i, s;
n = 32;

int arr[32] = {234, 233, 22, 1, 22, 8, 1, 89, 5, 34, 21, 9, 222, 2, 1, 999, 21, 12, 23, 32, 21, 111, 45, 23, 211, 21, 232, 45, 22, 11, 9876, 22, 2, 3, 555, 333};

printArray(arr,n);

// do merges
for (s=2; s <= n; s*=2)
{
        for (i=0; i < n;)
        {
                merge_up((arr+i),s);
                merge_down((arr+i+s),s);
                i += s*2;
        }
}

printArray(arr,n);

}// END 

void printArray(int *arr, int n)
{

        int i;
        printf("[%d",arr[0]);

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

2 回答 2

1

我认为你忽略了类似的东西

warning: excess elements in array initializer

您的 arr 已针对 32 个元素进行了初始化，并且您正试图将元素推到其限制之上。

于 2013-05-19T13:31:38.887 回答
1

您正在越界访问数组。

使用大小 16 时也存在问题。它只是没有显示，因为即使使用大小 16，您也在创建大小为 32 的数组。

非法访问在这里完成：

arr[j] > arr[j+step]

因为j+step对于数组来说太大了。在你的 main 添加一个 print ，你很容易看到会发生什么：

// do merges
for (s=2; s <= n; s*=2)
{
        for (i=0; i < n;) 
        {   
                printf("s: %d, n : %d, i: %d\n", s, n, i); 
                merge_up((arr+i),s);
                merge_down((arr+i+s),s);
                i += s*2;
        }   
}



s: 2, n : 32, i: 0
s: 2, n : 32, i: 4
s: 2, n : 32, i: 8
s: 2, n : 32, i: 12
s: 2, n : 32, i: 16
s: 2, n : 32, i: 20
s: 2, n : 32, i: 24
s: 2, n : 32, i: 28
s: 4, n : 32, i: 0
s: 4, n : 32, i: 8
s: 4, n : 32, i: 16
s: 4, n : 32, i: 24
s: 8, n : 32, i: 0
s: 8, n : 32, i: 16
s: 16, n : 32, i: 0
s: 32, n : 32, i: 0
s: 1857424340, n : 1857424324, i: -580085849
Segmentation fault: 11

在某些时候，n、s和i变成一个随机（大）数。这是因为当您越界访问数组时，您正在更改与这些变量关联的内存。

函数的局部变量是按照声明的顺序在堆栈上创建的。你有

int n, i, s;
int arr[32];

在你的堆栈上，这看起来像这样

stack grows here
 a[0]
 .
 .
 .
 a[31]
 s
 i
 n 
 return address
bottom of the stack frame

这意味着如果您访问a[32]或向上，您将访问变量n、s和i。

奇怪的是，如果您将变量声明更改为

int arr[32];
int n, i, s;

堆栈将如下所示

stack grows here
 s
 i
 n 
 a[0]
 .
 .
 .
 a[31]
 return address
bottom of the stack frame

并且程序可以工作，因为堆栈上的变量不再位于数组之后，但是您在程序退出时会出现段错误，因为您正在更改返回地址（地址告诉 cpu 程序终止后下一条指令是什么）。

最后，问题出在这里：

merge_up((arr+i),s);
merge_down((arr+i+s),s);

在某个点i+s是 32，并且您merge_down使用指针作为参数调用，该指针指向arr + 32，它已经指向越界。我建议你改变这个

于 2013-05-19T15:28:10.560 回答