当前位置: 动力学知识库 > 问答 > 编程问答 >

c - Abort trap: 6 on Mac when trying to run program with quicksort

问题描述:

So, I'm trying to run the following C program, and all I get when I run it is an error that says:

Abort trap: 6

Any ideas why? This only happens when I run the quicksort algorithm. I think it has something to do with the recursion, but it should work fine, so I don't know what's going on.

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#define MAX_DIM 30

int partition(char**, int, int);

void quickSort(char**, int, int);

int main()

{

char **array;

array = (char**) malloc(6*sizeof(char*));

for(int i = 0; i < 6; i++)

{

array[i] = (char*) malloc(MAX_DIM*sizeof(char));

}

strcpy(array[0], "ok");

strcpy(array[1], "bye");

strcpy(array[2], "then");

strcpy(array[3], "yeah");

strcpy(array[4], "lets");

strcpy(array[5], "go");

quickSort(array, 0, 5);

for(int i = 0; i < 6; i++)

{

printf("%s\n", array[i]);

}

return 0;

}

void quickSort(char **a, int l, int r)

{

int j;

if( l < r )

{

j = partition( a, l, r);

quickSort( a, l, j-1);

quickSort( a, j+1, r);

}

}

int partition(char **a, int l, int r) {

int i, j;

char pivot[MAX_DIM], t[MAX_DIM];

strcpy(pivot, a[l]);

i = l; j = r+1;

while(1)

{

do ++i; while( strcmp(a[i], pivot) <= 0 && i <= r );

do --j; while( strcmp(a[j],pivot) > 0);

if( i >= j ) break;

strcpy(t, a[i]); strcpy(a[i], a[j]); strcpy(a[j], t);

}

strcpy(t, a[l]); strcpy(a[l], a[j]); strcpy(a[j], t);

return j;

}

网友答案:

Logic Bug

(a && b) != (b && a)

in general, for C/C++. They are equal if and only if the evaluations of a and b are independent of each other.

In the specifications, there exists a short-circuit optimization so that if a is false, b will never be evaluated. Hence, the logical-and operation is not commutative, if expressions a and b are not independent of each other.

Your code is a perfect example of lack of independence between your expressions - ordering does matter.

Change:

do ++i; while( strcmp(a[i], pivot) <= 0 && i <= r );

To:

do ++i; while( i <= r && strcmp(a[i], pivot) <= 0 );

Output:

bye
go
lets
ok
then
yeah
分享给朋友:
您可能感兴趣的文章:
随机阅读: