c语言 - 快速排序算法给出分段错误错误

Question

我正在尝试创建一个程序，该程序获取具有 5 个元素的向量并根据它们的距离对它们进行排序("距离"的含义是这里的重点之外)。

但是每次执行它时，它都会给我"分段错误">错误：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct 
{
char ID[8];
char Content[4];
int distance;
} DATA;

void sort(DATA *z, int l){
DATA p; //pivot
DATA t;
int aux=(l-1); //pivot's position
int i,j;
p.distance=z[l-1].distance;

if(l==1){return;}
for(i=0; i<l; i++){
if((z[i].distance)<(p.distance)){
continue;
}

if((z[i].distance)>(p.distance)){
t=z[i];
for(j=i; j<aux; j++){
z[j]=z[j+1];
}
z[aux]=t;
aux--;
}
}

sort(z,aux-1);
sort(&z[aux+1],l-aux);
}
int main(){
DATA *z;
int l=5;
int i;
z=(DATA*)malloc(5*sizeof(DATA));
z[0].distance=5;
z[1].distance=1;
z[2].distance=4;
z[3].distance=3;
z[4].distance=2;
sort(z,l);
for(i=0; i<5; i++){
printf("%dn",z[i].distance);
}
free(z);
}

我看不出问题可能在哪里。如果可以的话，请帮忙。

Answer 1

您正在递归地调用排序，而不检查第二个参数的值是什么。 使用 gdb 执行代码会产生以下输出：

Program received signal SIGSEGV, Segmentation fault.
0x0000000000400661 in sort (z=0x602010, l=-513) at main.c:21
21  p.distance=z[l-1].distance;
(gdb) bt
#0  0x0000000000400661 in sort (z=0x602010, l=-513) at main.c:21
#1  0x000000000040077c in sort (z=0x602010, l=-511) at main.c:51
#2  0x000000000040077c in sort (z=0x602010, l=-509) at main.c:51
#3  0x000000000040077c in sort (z=0x602010, l=-507) at main.c:51
#4  0x000000000040077c in sort (z=0x602010, l=-505) at main.c:51
#5  0x000000000040077c in sort (z=0x602010, l=-503) at main.c:51
#6  0x000000000040077c in sort (z=0x602010, l=-501) at main.c:51
#7  0x000000000040077c in sort (z=0x602010, l=-499) at main.c:51
#8  0x000000000040077c in sort (z=0x602010, l=-497) at main.c:51
#9  0x000000000040077c in sort (z=0x602010, l=-495) at main.c:51
#10 0x000000000040077c in sort (z=0x602010, l=-493) at main.c:51
#11 0x000000000040077c in sort (z=0x602010, l=-491) at main.c:51
#12 0x000000000040077c in sort (z=0x602010, l=-489) at main.c:51
#13 0x000000000040077c in sort (z=0x602010, l=-487) at main.c:51
#14 0x000000000040077c in sort (z=0x602010, l=-485) at main.c:51
#15 0x000000000040077c in sort (z=0x602010, l=-483) at main.c:51
#16 0x000000000040077c in sort (z=0x602010, l=-481) at main.c:51
#17 0x000000000040077c in sort (z=0x602010, l=-479) at main.c:51
#18 0x000000000040077c in sort (z=0x602010, l=-477) at main.c:51
#19 0x000000000040077c in sort (z=0x602010, l=-475) at main.c:51
#20 0x000000000040077c in sort (z=0x602010, l=-473) at main.c:51
#21 0x000000000040077c in sort (z=0x602010, l=-471) at main.c:51
#22 0x000000000040077c in sort (z=0x602010, l=-469) at main.c:51

您可以使用调试符号编译代码，如下所示gcc -g main.c然后使用 gdb 执行它gdb a.out加载后只需键入 run 即可运行它，您将看到分段错误。键入 bt 作为回溯跟踪。

Answer 2

此行看起来很可疑

sort(&z[aux+1],l-aux);

l 是长度，aux+1 是新的基索引，所以新的长度应该是 l - aux -1

但是，正如其他人所说，您需要调试/放入诊断 printfs。很难调试像离子屏这样的功能。

Answer 3

正如一些评论所指出的，您可以使用 gdb 来查找分段错误的位置。我在你的原始代码上做了，发现它在行处中断

p.distance=z[l-1].distance;  // statement 1

正如 Malcolm 所指出的，发生这种情况是因为您在递归调用排序函数时没有正确传入数组的长度。正确的递归调用应该是(记住c数组是从零开始的)

sort(z,aux); // left half of the array , excluding the pivot
sort(&z[aux+1],l-aux-1); // right half of the array.

此外，理想情况下，语句 1 应该放在您检查 之后，

if(l <= 1){return;}

请注意，我如何将比较从 l == 1 更改为 l <= 1，因为您还必须检查 l = 0 的情况。即使在这些更改之后，你遍历数组的循环也有一些问题，我试图在保持原始代码结构的同时尽可能地修复这些问题。这是代码

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct 
{
char ID[8];
char Content[4];
int distance;
} DATA;

void sort(DATA *z, int l){
DATA p; //pivot
DATA t;
int aux=(l-1); //pivot's position
int i,j;


if(l <= 1){return;}
p.distance=z[l-1].distance;
for(i=0; i<l; i++){
if(i >= aux)
break; // to avoid going over the right of pivot unnecessarily
if((z[i].distance)<(p.distance)){
continue;
}

if((z[i].distance)>(p.distance)){
t=z[i];
for(j=i; j<aux; j++){
z[j]=z[j+1];
}
z[aux]=t;
aux--;
i--; // You have changed the array and brought in a new element , 
//and you should consider it too for comparison with pivot. 
}
}

sort(z,aux); // left half of the array , excluding the pivot
sort(&z[aux+1],l-aux-1); // right half of the array.
}
int main(){
DATA *z;
int l=5;
int i;
z=(DATA*)malloc(5*sizeof(DATA));
z[0].distance=5;
z[1].distance=1;
z[2].distance=4;
z[3].distance=3;
z[4].distance=2;
sort(z,l);
for(i=0; i<5; i++){
printf("%dn",z[i].distance);
}
free(z);
}

但我建议你考虑以不同的方式编写遍历循环，因为现在它在太多元素周围移动，实际上是 O(n^2)。而 使用快速排序所需的行为是 O(n) 。我建议在一本好书中查找算法，例如CLRS算法书。