Cのリンクリストのアルファベット順ソート？

Question

このリンクされたリストの名前をアルファベット順にソートしようとしていますが、どのアプローチを取るのが適切かはわかりません。リストの名前を比較し、毎回現在のポインタを更新するメソッドを作成しました。私は間違いを続けている。誰もが名前を並べ替えるより良い方法を提案できますか？私はCの新人です。私はこれを実装するより良い方法を見つけるのに苦労しています。どんな助けも大いに感謝されるでしょう。

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

#define HOW_MANY 7 

char *names[HOW_MANY] = { "Ben", "Chris", "RDJ", "Mark", "Scarlet", "Samuel", "Tom" }; 
int ages[HOW_MANY] = { 22, 24, 50, 26, 18, 32, 24 }; 

/* declare your struct for a person here */ 
struct person { 
    char *name; 
    int age; 
    struct person *next; 
}; 

static struct person *compare_people(struct person *headptr, struct person *headptr) { 
    int didSwap = 1, limit = HOW_MANY - 1; 
    struct person *temp; 
    struct person *previous = headptr; 
    struct person *new = headptr -> next; 

    while (didSwap) { 
     didSwap = 0; 
     for (int i = 0; i < limit; i++) { 
      if (strcmp(previous->name, new->name) > 0) { 
       temp = previous; 
       previous = new; 
       new = temp; 
       didSwap = 1; 
      } 
     } 
     limit--; 
    } 
    return temp; 
} 

static struct person *insert_sorted(struct person *headptr, char *name, int age) { 
    struct person *ptr; 
    // Allocate heap space for a record 
    ptr = malloc(sizeof(struct person)); 
    if (ptr == NULL) 
     abort(); 
    // Assign to structure fields 
    ptr->name = name; 
    ptr->age = age; 
    ptr->next = NULL; 

    if (headptr == NULL) { 
     ptr->next = headptr; 
     headptr = ptr; 
    } else { 
     struct person *currptr = headptr; 

     while (currptr != NULL) { 
      currptr = compare_people(headptr, headptr); 
     } 
     headptr = currptr; 
    } 
    return headptr; 
} 

int main(int argc, char **argv) { 
    // initialise the pointer to be empty 
    struct person *headptr = NULL; 

    // To insert all the info in the array 
    for (int i = 0; i < HOW_MANY ; i++) { 
     headptr = insert_sorted(headptr, names[i], ages[i]); 
    } 

    struct person *current = headptr; 
    while (current != NULL) { 
     printf("The person's name is %s and the age is %d.\n", current->name, current->age); 
     current = current->next; 
    } 
    return 0; 
} 

Answer 1

あなたのアプローチは複雑すぎます：比較機能は何らかのソートと挿入機能も実行します。比較関数は、strcmp()のように0または正の値を持つintを返す必要があります。また、insert_sortedは、新しいpersonを簡単な反復メソッドを使用して適切な位置にリストに挿入する必要があります。

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

#define HOW_MANY 7 

char *names[HOW_MANY] = { "Ben", "Chris", "RDJ", "Mark", "Scarlet", "Samuel", "Tom" }; 
int ages[HOW_MANY] = { 22, 24, 50, 26, 18, 32, 24 }; 

/* declare your struct for a person here */ 
struct person { 
    char *name; 
    int age; 
    struct person *next; 
}; 

static int compare_people(const struct person *a, const struct person *b) { 
    return strcmp(a->name, b->name); 
} 

static struct person *insert_sorted(struct person *headptr, char *name, int age) { 
    // Allocate heap space for a record 
    struct person *ptr = malloc(sizeof(struct person)); 
    if (ptr == NULL) { 
     abort(); 
    } 

    // Assign to structure fields 
    ptr->name = name; 
    ptr->age = age; 
    ptr->next = NULL; 

    struct person **pp = &headptr; 
    while (*pp != NULL && compare_people(ptr, *pp) >= 0) { 
     pp = &(*pp)->next; 
    } 
    ptr->next = *pp; 
    *pp = ptr; 

    return headptr; 
} 

int main(int argc, char **argv) { 
    // initialise the list to be empty 
    struct person *headptr = NULL; 

    // To insert all the info in the array 
    for (int i = 0; i < HOW_MANY; i++) { 
     headptr = insert_sorted(headptr, names[i], ages[i]); 
    } 

    struct person *current = headptr; 
    while (current != NULL) { 
     printf("The person's name is %s and the age is %d.\n", current->name, current->age); 
     current = current->next; 
    } 
    return 0; 
} 

EDIT：以下は、単純なポインタと代替バージョンです。ここ

は簡単なバージョンです。私は空のリストと挿入の最初の特別なケースを作る必要があることがわかります。

static struct person *insert_sorted(struct person *headptr, char *name, int age) { 
    // Allocate heap space for a record 
    struct person *ptr = malloc(sizeof(struct person)); 
    if (ptr == NULL) { 
     abort(); 
    } 
    ptr->name = name; 
    ptr->age = age; 
    ptr->next = NULL; 

    if (headptr == NULL || compare_people(ptr, headptr) < 0) { 
     ptr->next = headptr; 
     return ptr; 
    } else { 
     struct person *cur = headptr; 
     while (cur->next != NULL && compare_people(ptr, cur->next) >= 0) { 
      cur = cur->next; 
     } 
     ptr->next = cur->next; 
     cur->next = ptr; 
     return headptr; 
    } 
}