C快速将字符数组排序为字母顺序
C quick sort character array into alphabetical order
我对 C 还很陌生，把它当作练习来做。代码在遇到运行时错误 Abort trap: 6 之前编译并运行。我已经在第二次递归调用会议 i < last_line 越界的第二次调用中跟踪到计数器 j 的错误。我看不到代码中的错误。快速排序不是我特别熟悉的方法；谁能帮我找出错误？
我输入的名单是：
James
Janet
James
Rosie
Dave
这是我的代码：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
void quicksort(char **array, int first_line, int last_line) ;
int main(int argc, char* argv[])
{
int i = 0 ;
int j = 0 ;
int line_count = 0 ;
int line_number = 20 ;
char *lines[20] ;
//char temp[BUFSIZ] ;
FILE *foutptr ;
FILE *finptr ;
finptr = fopen("names.txt", "r") ;
if(finptr == NULL)
{
perror("ERROR: input file pointer") ;
return 1 ;
}
foutptr = fopen("sorted.txt", "w") ;
if(foutptr == NULL)
{
perror("ERROR: output file pointer") ;
return 1 ;
}
lines[i] = malloc(BUFSIZ) ;
while(fgets(lines[i],BUFSIZ,finptr) && i < line_number)
{
printf("Element %d is the name %s.\n", i, lines[i]) ;
i++ ;
lines[i] = malloc(BUFSIZ) ;
}
printf("TEST %s.\n", *(lines+1)) ;
line_count = i ;
i = 0 ;
char **all_lines = lines ;
quicksort(all_lines, 0, line_count-1) ;
for(j = 0 ; j < line_count ; j++)
{
fprintf(foutptr, "%s", lines[j]) ;
}
return 0 ;
}
void quicksort(char **array, int first_line, int last_line)
{
int i = 0, j = 0, x = 0, pivot = (first_line + last_line)/2 ;
char temp[100] ;
i = first_line ;
j = last_line ;
if(last_line - first_line < 1)
{
return ;
}
printf("first_line = %d so i = %d. last line = %d so j = %d. The pivot is %d \n", first_line, i, last_line, j, pivot) ;
while(i <= j)
{
/* While array[i] proceeds the pivot alphabetically and is less than array[j] move through the array. This deals with first mismatching letter of first string is less than the second
in ASCII character numbers i.e. if earlier in the alphabet as ASCII chartcters earlier in the alphabet have a lower numerical id */
while(strcmp(array[i], array[pivot]) < 0 && i < last_line)
{
printf("No swapping In while 1, comparing %s and %s with strcmp = %d. \n", array[i], array[pivot], strcmp(array[i], array[pivot])) ;
printf("%d. \n", i) ;
i++ ;
}
/* While array[j] follows the pivot alphabetically and is greater than array[i] move through the array. This deals with the first mismatching letter of first string compared to the second is greater in number id i.e. the ASCII character code is bigger in the first so it is latter in the alphabet */
while(strcmp(array[j], array[pivot]) > 0 && j > first_line)
{
printf("No swapping In while 2, comparing %s and %s with strcmp = %d. \n", array[j], array[pivot], strcmp(array[j], array[pivot])) ;
printf("%d. \n", j) ;
j-- ;
}
// Swap if the conditions above are not met
if(i <= j)
{
printf("%s\n","SWAPPING") ;
printf("Array[%d] = %s, Array[%d] = %s", i, array[i], j, array[j]) ;
strcpy(temp,array[i]) ;
strcpy(array[i], array[j]) ;
strcpy(array[j],temp) ;
printf("Array[%d] = %s, Array[%d] = %s", i, array[i], j, array[j]) ;
i++ ;
j-- ;
}
}
if(first_line < j)
{
printf("Recursive call 1: Lower bound = %d, Upper bound = %d\n", first_line, j) ;
for(x = 0 ; x < last_line + 1 ; x++)
{
printf("Array[%d]: %s \n", x, array[x]) ;
}
quicksort(array, first_line, j) ;
}
x = 0 ;
if(i < last_line)
{
printf("Recursive call 2: Lower bound = %d, Upper bound = %d\n", i, last_line) ;
for(x = 0 ; x < last_line + 1 ; x++)
{
printf("Array[%d]: %s \n", x, array[x]) ;
}
quicksort(array, i, last_line) ;
}
x = 0 ;
return ;
}
正如评论中所述，我在您的代码中看不到任何内容可以解释您声称观察到的越界索引问题，而且我自己也没有用您的代码和数据观察到它。事实上，您提供的代码似乎无法提供您描述的行为的可能性。如果您确实观察到这样的问题，那么我倾向于猜测它与您实际使用的代码和您提供的代码之间的一些差异有关。
另一方面，正如我在评论中首先提到的那样，您的代码存在错误。构建一个较长的输入相对容易，但它会错误地排序（我在第一次尝试时就这样做了，没有特别考虑您的实现细节）。我看到的问题是，在分区期间，您使用 array[pivot] 来引用枢轴元素，从而假设枢轴元素保持在其初始位置。对于某些输入的某些分区，该假设 将 被违反，结果可能是数组未正确排序。
另请注意，我强烈建议您直接对数组元素（指针）执行交换，而不是交换指针指向的 char 数组的内容。这不仅效率更高，而且可以更轻松地解决枢轴元素的问题。如果您不能依赖指向所有指向相同大小分配的指针，它实际上是唯一的选择。
下面的代码包含了上面的答案和评论中给出的建议。此代码似乎可以正常工作，但仍不清楚为什么最初收到 Abort trap 6 运行 时间错误。
最终代码：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
void quicksort(char **array, int first_line, int last_line) ;
int main(int argc, char* argv[])
{
int i = 0 ;
int j = 0 ;
int line_count = 0 ;
int line_number = 20 ;
char *lines[100] ;
FILE *foutptr ;
FILE *finptr ;
finptr = fopen("names.txt", "r") ;
if(finptr == NULL)
{
perror("ERROR: input file pointer") ;
return 1 ;
}
foutptr = fopen("sorted.txt", "w") ;
if(foutptr == NULL)
{
perror("ERROR: output file pointer") ;
return 1 ;
}
lines[i] = malloc(BUFSIZ) ;
while(fgets(lines[i],BUFSIZ,finptr) && i < line_number)
{
printf("Element %d is the name %s.\n", i, lines[i]) ;
i++ ;
lines[i] = malloc(BUFSIZ) ;
}
printf("TEST %s.\n", *(lines+1)) ;
line_count = i ;
i = 0 ;
char **all_lines = lines ;
quicksort(all_lines, 0, line_count-1) ;
for(j = 0 ; j < line_count ; j++)
{
fprintf(foutptr, "%s", lines[j]) ;
}
return 0 ;
}
void quicksort(char **array, int first_line, int last_line)
{
int i = 0, j = 0, x = 0i, p = (first_line + last_line)/2 ;
printf("%s \n", array[p]) ;
char pivot[BUFSIZ] ;
char *temp_ptr ;
strcpy(pivot,array[p]) ;
i = first_line ;
j = last_line ;
if(last_line - first_line < 1)
{
return ;
}
printf("first_line = %d so i = %d. last line = %d so j = %d. The pivot is array[%d] \n", first_line, i, last_line, j, p) ;
while(i <= j)
{
/* While array[i] proceeds the pivot alphabetically and is less than array[j] move through the array. This deals with first
mismatching letter of first string is less than the second in ASCII character numbers i.e. if earlier in the alphabet as ASCII
chartcters earlier in the alphabet have a lower numerical id */
while(strcmp(array[i], pivot) < 0 && i < last_line)
{
printf("No swapping In while 1, comparing %s and %s with strcmp = %d. \n", array[i], pivot, strcmp(array[i], pivot)) ;
printf("%d. \n", i) ;
i++ ;
}
/* While array[j] follows the pivot alphabetically and is
greater than array[i] move through the array. This deals with the
first mismatching letter of first string compared to the second
is greater in number id i.e. the ASCII character code is
bigger in the first so it is latter in the alphabet */
while(strcmp(array[j], pivot) > 0 && j > first_line)
{
printf("No swapping In while 2, comparing %s and %s with strcmp = %d. \n", array[j], pivot, strcmp(array[j], pivot)) ;
printf("%d. \n", j) ;
j-- ;
}
// Swap if the conditions above are not met
if(i <= j)
{
printf("%s\n","SWAPPING") ;
printf("Array[%d] = %s, Array[%d] = %s", i, array[i], j,array[j]) ;
temp_ptr = array[i] ; //Here we copy pointers which is eaier to do than copy the array contents and is more efficent.
array[i] = array[j] ;
array[j] = temp_ptr ;
//strcpy(temp,array[i]) ; // This is much less efficent as it copies the contents of the aray not the pointers.
//strcpy(array[i], array[j]) ;
//strcpy(array[j],temp) ;
printf("Array[%d] = %s, Array[%d] = %s", i, array[i], j,array[j]) ;
i++ ;
j-- ;
}
}
if(first_line < j)
{
printf("Recursive call 1: Lower bound = %d, Upper bound = %d\n", first_line, j) ;
for(x = 0 ; x < last_line + 1 ; x++)
{
printf("Array[%d]: %s \n", x, array[x]) ;
}
quicksort(array, first_line, j) ;
}
x = 0 ;
if(i < last_line)
{
printf("Recursive call 2: Lower bound = %d, Upper bound = %d\n", i, last_line) ;
for(x = 0 ; x < last_line + 1 ; x++)
{
printf("Array[%d]: %s \n", x, array[x]) ;
}
quicksort(array, i, last_line) ;
}
x = 0 ;
return ;
}
我对 C 还很陌生，把它当作练习来做。代码在遇到运行时错误 Abort trap: 6 之前编译并运行。我已经在第二次递归调用会议 i < last_line 越界的第二次调用中跟踪到计数器 j 的错误。我看不到代码中的错误。快速排序不是我特别熟悉的方法；谁能帮我找出错误？
我输入的名单是：
James
Janet
James
Rosie
Dave
这是我的代码：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
void quicksort(char **array, int first_line, int last_line) ;
int main(int argc, char* argv[])
{
int i = 0 ;
int j = 0 ;
int line_count = 0 ;
int line_number = 20 ;
char *lines[20] ;
//char temp[BUFSIZ] ;
FILE *foutptr ;
FILE *finptr ;
finptr = fopen("names.txt", "r") ;
if(finptr == NULL)
{
perror("ERROR: input file pointer") ;
return 1 ;
}
foutptr = fopen("sorted.txt", "w") ;
if(foutptr == NULL)
{
perror("ERROR: output file pointer") ;
return 1 ;
}
lines[i] = malloc(BUFSIZ) ;
while(fgets(lines[i],BUFSIZ,finptr) && i < line_number)
{
printf("Element %d is the name %s.\n", i, lines[i]) ;
i++ ;
lines[i] = malloc(BUFSIZ) ;
}
printf("TEST %s.\n", *(lines+1)) ;
line_count = i ;
i = 0 ;
char **all_lines = lines ;
quicksort(all_lines, 0, line_count-1) ;
for(j = 0 ; j < line_count ; j++)
{
fprintf(foutptr, "%s", lines[j]) ;
}
return 0 ;
}
void quicksort(char **array, int first_line, int last_line)
{
int i = 0, j = 0, x = 0, pivot = (first_line + last_line)/2 ;
char temp[100] ;
i = first_line ;
j = last_line ;
if(last_line - first_line < 1)
{
return ;
}
printf("first_line = %d so i = %d. last line = %d so j = %d. The pivot is %d \n", first_line, i, last_line, j, pivot) ;
while(i <= j)
{
/* While array[i] proceeds the pivot alphabetically and is less than array[j] move through the array. This deals with first mismatching letter of first string is less than the second
in ASCII character numbers i.e. if earlier in the alphabet as ASCII chartcters earlier in the alphabet have a lower numerical id */
while(strcmp(array[i], array[pivot]) < 0 && i < last_line)
{
printf("No swapping In while 1, comparing %s and %s with strcmp = %d. \n", array[i], array[pivot], strcmp(array[i], array[pivot])) ;
printf("%d. \n", i) ;
i++ ;
}
/* While array[j] follows the pivot alphabetically and is greater than array[i] move through the array. This deals with the first mismatching letter of first string compared to the second is greater in number id i.e. the ASCII character code is bigger in the first so it is latter in the alphabet */
while(strcmp(array[j], array[pivot]) > 0 && j > first_line)
{
printf("No swapping In while 2, comparing %s and %s with strcmp = %d. \n", array[j], array[pivot], strcmp(array[j], array[pivot])) ;
printf("%d. \n", j) ;
j-- ;
}
// Swap if the conditions above are not met
if(i <= j)
{
printf("%s\n","SWAPPING") ;
printf("Array[%d] = %s, Array[%d] = %s", i, array[i], j, array[j]) ;
strcpy(temp,array[i]) ;
strcpy(array[i], array[j]) ;
strcpy(array[j],temp) ;
printf("Array[%d] = %s, Array[%d] = %s", i, array[i], j, array[j]) ;
i++ ;
j-- ;
}
}
if(first_line < j)
{
printf("Recursive call 1: Lower bound = %d, Upper bound = %d\n", first_line, j) ;
for(x = 0 ; x < last_line + 1 ; x++)
{
printf("Array[%d]: %s \n", x, array[x]) ;
}
quicksort(array, first_line, j) ;
}
x = 0 ;
if(i < last_line)
{
printf("Recursive call 2: Lower bound = %d, Upper bound = %d\n", i, last_line) ;
for(x = 0 ; x < last_line + 1 ; x++)
{
printf("Array[%d]: %s \n", x, array[x]) ;
}
quicksort(array, i, last_line) ;
}
x = 0 ;
return ;
}
正如评论中所述，我在您的代码中看不到任何内容可以解释您声称观察到的越界索引问题，而且我自己也没有用您的代码和数据观察到它。事实上，您提供的代码似乎无法提供您描述的行为的可能性。如果您确实观察到这样的问题，那么我倾向于猜测它与您实际使用的代码和您提供的代码之间的一些差异有关。
另一方面，正如我在评论中首先提到的那样，您的代码存在错误。构建一个较长的输入相对容易，但它会错误地排序（我在第一次尝试时就这样做了，没有特别考虑您的实现细节）。我看到的问题是，在分区期间，您使用 array[pivot] 来引用枢轴元素，从而假设枢轴元素保持在其初始位置。对于某些输入的某些分区，该假设 将 被违反，结果可能是数组未正确排序。
另请注意，我强烈建议您直接对数组元素（指针）执行交换，而不是交换指针指向的 char 数组的内容。这不仅效率更高，而且可以更轻松地解决枢轴元素的问题。如果您不能依赖指向所有指向相同大小分配的指针，它实际上是唯一的选择。
下面的代码包含了上面的答案和评论中给出的建议。此代码似乎可以正常工作，但仍不清楚为什么最初收到 Abort trap 6 运行 时间错误。
最终代码：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
void quicksort(char **array, int first_line, int last_line) ;
int main(int argc, char* argv[])
{
int i = 0 ;
int j = 0 ;
int line_count = 0 ;
int line_number = 20 ;
char *lines[100] ;
FILE *foutptr ;
FILE *finptr ;
finptr = fopen("names.txt", "r") ;
if(finptr == NULL)
{
perror("ERROR: input file pointer") ;
return 1 ;
}
foutptr = fopen("sorted.txt", "w") ;
if(foutptr == NULL)
{
perror("ERROR: output file pointer") ;
return 1 ;
}
lines[i] = malloc(BUFSIZ) ;
while(fgets(lines[i],BUFSIZ,finptr) && i < line_number)
{
printf("Element %d is the name %s.\n", i, lines[i]) ;
i++ ;
lines[i] = malloc(BUFSIZ) ;
}
printf("TEST %s.\n", *(lines+1)) ;
line_count = i ;
i = 0 ;
char **all_lines = lines ;
quicksort(all_lines, 0, line_count-1) ;
for(j = 0 ; j < line_count ; j++)
{
fprintf(foutptr, "%s", lines[j]) ;
}
return 0 ;
}
void quicksort(char **array, int first_line, int last_line)
{
int i = 0, j = 0, x = 0i, p = (first_line + last_line)/2 ;
printf("%s \n", array[p]) ;
char pivot[BUFSIZ] ;
char *temp_ptr ;
strcpy(pivot,array[p]) ;
i = first_line ;
j = last_line ;
if(last_line - first_line < 1)
{
return ;
}
printf("first_line = %d so i = %d. last line = %d so j = %d. The pivot is array[%d] \n", first_line, i, last_line, j, p) ;
while(i <= j)
{
/* While array[i] proceeds the pivot alphabetically and is less than array[j] move through the array. This deals with first
mismatching letter of first string is less than the second in ASCII character numbers i.e. if earlier in the alphabet as ASCII
chartcters earlier in the alphabet have a lower numerical id */
while(strcmp(array[i], pivot) < 0 && i < last_line)
{
printf("No swapping In while 1, comparing %s and %s with strcmp = %d. \n", array[i], pivot, strcmp(array[i], pivot)) ;
printf("%d. \n", i) ;
i++ ;
}
/* While array[j] follows the pivot alphabetically and is
greater than array[i] move through the array. This deals with the
first mismatching letter of first string compared to the second
is greater in number id i.e. the ASCII character code is
bigger in the first so it is latter in the alphabet */
while(strcmp(array[j], pivot) > 0 && j > first_line)
{
printf("No swapping In while 2, comparing %s and %s with strcmp = %d. \n", array[j], pivot, strcmp(array[j], pivot)) ;
printf("%d. \n", j) ;
j-- ;
}
// Swap if the conditions above are not met
if(i <= j)
{
printf("%s\n","SWAPPING") ;
printf("Array[%d] = %s, Array[%d] = %s", i, array[i], j,array[j]) ;
temp_ptr = array[i] ; //Here we copy pointers which is eaier to do than copy the array contents and is more efficent.
array[i] = array[j] ;
array[j] = temp_ptr ;
//strcpy(temp,array[i]) ; // This is much less efficent as it copies the contents of the aray not the pointers.
//strcpy(array[i], array[j]) ;
//strcpy(array[j],temp) ;
printf("Array[%d] = %s, Array[%d] = %s", i, array[i], j,array[j]) ;
i++ ;
j-- ;
}
}
if(first_line < j)
{
printf("Recursive call 1: Lower bound = %d, Upper bound = %d\n", first_line, j) ;
for(x = 0 ; x < last_line + 1 ; x++)
{
printf("Array[%d]: %s \n", x, array[x]) ;
}
quicksort(array, first_line, j) ;
}
x = 0 ;
if(i < last_line)
{
printf("Recursive call 2: Lower bound = %d, Upper bound = %d\n", i, last_line) ;
for(x = 0 ; x < last_line + 1 ; x++)
{
printf("Array[%d]: %s \n", x, array[x]) ;
}
quicksort(array, i, last_line) ;
}
x = 0 ;
return ;
}