快速排序功能只适用于最后一个值是最大的

Question

我试图在C中使用快速排序练习。我的程序是一个简单的结构数组，它接受命令行参数（名称1年龄1名称2年龄2 ...等）并以降序输出所述年龄。

只有最后输入的年龄最大才能正常工作。除此之外，我得到没有输出或Seg Fault 11.有没有人有任何想法？

#include <stdio.h> 
#include <stdlib.h> 
#include <string.h> 
#define NameLen 80 
void print_struct(); 

struct people 
{ 
char name [NameLen + 1]; 
int age; 
}; //defining a structure// 

typedef struct people PERSON; 
void quicksort(struct people list[],int,int); 
int main(int argc, const char * argv[]) 

{ 
int i,j; 
j = 0; 
int l = ((argc/2)-1); 


struct people list[l]; //maximum size of array of structs 


    if (argc %2 == 0) //if the number of arguments is an even number 
{ 

printf("Invalid Arguments!\n"); 
printf("Usage : ./hw5 name1 age1 name2 age2 ... "); //print error message and correct program usage 
    exit(0); 
} 

printf("You have entered %d persons(s) into the program \n",(argc/2)); 

for (i=1; i < argc; i+=2) 

{ 
    strcpy(list[j].name, argv[i]); 
    list[j].age = atoi(argv[i+1]); 
    if(list[j].age == 0) 
    { 
     printf("...Invalid age <=0. Try again.\n"); 

     exit(0); 
    } 
    j++; 

} 
    printf("Unsorted Names: \n"); 
    print_struct(&list,argc); 

printf ("Sorted by Age: \n"); 
quicksort(list,0 ,j); 
for(i=0;i<j;i++){ 
    printf("Name : %s| Age : %d\n", list[i].name, list[i].age);}//possible error here? 

//Quicksort Function 

Answer 1

也许问题是j的值。 j是列表的长度吗？或者列表的长度 - 1？

看起来这会是你想要的东西：列表

printf ("Sorted by Age: \n"); 
quicksort(list,0 ,j-1); 
for(i=0;i<j;i++){ 
    printf("Name : %s| Age : %d\n", list[i].name, list[i].age);} 

Answer 2

的 J =长度的快速排序功能是好的。问题是，你调用一个错误：

quicksort(list,0 ,j); 

你传递在first和last的值代表了第一个和最后一个元素的索引。从你如何使用j循环遍历元素可以明显看出，j是元素的数量。这意味着最后一个元素的索引为j-1。

所以你传递的值是last，它是数组末尾的一个元素。当你尝试读/写这个假元素时，你会调用undefined behavior，在你的情况下（幸运的是）会导致段错误。

传入最后一个元素的实际索引（即一个小于大小）并且它成功运行。

quicksort(list,0 ,j - 1); 

Answer 3

你的循环是不正确的：

while(list[i].age<=list[pivot].age&&i<last) 
     i++; 

这是可能的这个循环与i == last，这是坏的结束，因为你试图交换价值，这将是在对阵列的范围。

while(list[j].age>list[pivot].age) 
     j--; 

这里，因为j开始为last，你开始马上与读取阵列之外。

一种可能的解决方法是先向后移动j，然后再测试（do-while样式）。然后，增量i，测试减量j。

do --j; while(list[j].age>list[pivot].age); 
    do ++i; while(list[i].age<=list[pivot].age&&i<j); 

Answer 4

我让代码变得有点简单（将字符数组更改为char，使其更简单）。 我的想法是，当你拨打：

quicksort(list,0 ,j); 

你应该叫的是：

quicksort(list,0 ,j-1); 

因为最后一个参数必须是数组lenght减1，最后一个位置。

我没有赛格故障，运行你的代码，或者我修改了，如果有可能的一个时，仔细检查您所使用的输入字符串。

这里是代码的“我的”代码。

希望它有帮助。

#include <stdio.h> 
#include <stdlib.h> 
#include <string.h> 
#define NameLen 80 
void print_struct(); 

struct people 
{ 
    char name; 
    int age; 
}; //defining a structure// 

typedef struct people PERSON; 
void quicksort(struct people list[],int,int); 

int main(int argc, const char * argv[]) 
{ 
    int i,j; 
    j = 10; 
    struct people list[10]; //maximum size of array of structs 

    for (i=0; i < 10; i++) 
    { 
     list[i].name = 'a'; 
     list[i].age = 10-i; 
    } 

    printf("Unsorted Names: \n"); 
    for(i=0;i<j;i++){ 
     printf("Name : %c| Age : %d\n", list[i].name, list[i].age);}//possible error here? 

    printf ("Sorted by Age: \n"); 
    quicksort(list,0 ,j-1); 
    for(i=0;i<j;i++){ 
     printf("Name : %c| Age : %d\n", list[i].name, list[i].age);}//possible error here? 
} 

void quicksort(struct people list[],int first,int last) 
{ 
    struct people temp; 
    int i,j,pivot; 

    if(first<last){ 
     pivot=first; 
     i=first; 
     j=last; 

     while(i<j) 
     { 
      while(list[i].age<=list[pivot].age&&i<last) 
       i++; 
      while(list[j].age>list[pivot].age) 
       j--; 
      if(i<j){ 
       temp=list[i]; 
       list[i]=list[j]; 
       list[j]=temp; 
      } 
     } 

    temp=list[pivot]; 
    list[pivot]=list[j]; 
    list[j]=temp; 
    quicksort(list,first,j-1); 
    quicksort(list,j+1,last); 
    } 
} 

Answer 5

将所有的意见后，这是生成的代码，这完全编译，但由于两名失踪功能将无法链接：

#include <stdio.h> 
#include <stdlib.h> 
#include <string.h> 

#define NAME_LEN (80) 


struct people 
{ 
    char name [NAME_LEN + 1]; 
    int age; 
}; //defining a structure// 

typedef struct people PERSON; 

// print_struct(ptrToList, numElements) 
void print_struct(PERSON *, int); 

// quicksort(ptrToList, firstOffset, numElements) 
void quicksort(struct people list[],int,int); 


int main(int argc, const char * argv[]) 
{ 
    //int i,j; 
    //j = 0; 
    //int l = ((argc/2)-1); 
    int l = argc/2; 

    struct people list[l]; //maximum size of array of structs 

    if (argc %2 == 0) //if the number of arguments is an even number 
    { 
     //printf("Invalid Arguments!\n"); 
     fprintf(stderr, "Invalid Arguments!\n"); 

     //printf("Usage : ./hw5 name1 age1 name2 age2 ... "); //print error message and correct program usage 
     fprintf(stderr, "Usage : %s name1 age1 name2 age2 ... ", argv[0]); 

     // exit(0); 
     exit(EXIT_FAILURE); 
    } 

    //printf("You have entered %d persons(s) into the program \n",(argc/2)); 
    printf("You have entered %d persons(s) into the program \n", l); 

    //for (int i=1; i < argc; i+=2) 
    for (int i=1, j=0; j < l; i+=2, j++) 
    { 
     //strcpy(list[j].name, argv[i]); 
     memset(list[i].name, '\0', NAME_LEN+1); 
     strncpy(list[j].name, argv[i], NAME_LEN); 
     list[j].age = atoi(argv[i+1]); 

     if(list[j].age == 0) 
     { 
      fprintf(stderr, "...Invalid age <=0. Try again.\n"); 

      //exit(0); 
      exit(EXIT_FAILURE); 
     } 
     //j++; 
    } 

    printf("Unsorted Names: \n"); 
    //print_struct(&list,argc); 
    print_struct(list, l); 

    //printf ("Sorted by Age: \n"); 
    //quicksort(list,0 ,j); 
    quicksort(list, 0, l); 

    printf ("Sorted by Age: \n"); 
    // //for(i=0;i<j;i++) 
    //for(int i=0; i<l; i++) 
    //{ 
    // printf("Name : %s| Age : %d\n", list[i].name, list[i].age); 
    //}//possible error here? 
    //} 
    print_struct(list, l); 
} // end function: main 


//Quicksort Function