c - 我怎样才能按字母顺序排列这个链表？

Question

我正在编写一个程序，其中输入了姓名和年龄。然后可以调用这些名字并打印出该人的年龄。如果这个人不在列表中，它会将他们的年龄打印为 -1。如果使用列表中已有的新年龄输入名称，则不会添加新条目。目前看来名称是按我输入它们的顺序排序的。如何仅通过更改函数添加的代码来按字母顺序对它们进行排序？此代码可编译并按预期工作，但非字母列表除外。

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

typedef struct person {
    char *name;
    int age;
    struct person *next;
} Person;

void print(Person *); // prints the entire list
Person *add(Person *, char *, int); // adds a new node to the list
int getAge(Person *, char *); // returns the age of the person or -1 if not found

int main(void) {
    char input1[100];
    int input2;
    Person *myList = NULL;
    printf("Enter a person's name (one word) and age : ");
    scanf("%s %d", input1, &input2);
    while (input2 != 0) {
        myList = add (myList, input1, input2);
        printf("\n\nThe list is now : ");   print(myList);
        printf("Enter a name (one word) and age, enter 'xxx' and 0 to exit : ");
        scanf("%s %d", input1, &input2);
    }
    printf("\n\nThe final list is ");   print(myList);
    printf("\n\nEnter the name of a person to look up their age : ");
    scanf("%s", input1);
    while ( strcmp(input1, "xxx") != 0 ) {
        printf("\t%s is %d years old\n", input1, getAge(myList, input1) );
        printf("Enter a name to look up their age or 'xxx' to exit : ");
        scanf("%s", input1);
    }

    return 0;
}

void print(Person *ptr) {
    while (ptr) { printf("[%s-%d] ", ptr->name, ptr->age); ptr = ptr->next; }
    printf("\n");

    return;
}

//adds person to list if the person does not exist already
Person *add(Person *ptr, char *n, int a) {
    Person *newNode = malloc( sizeof(Person) );
    int duplicate = 1;
    Person *dummy = ptr;
    while (dummy) {
        if(strcmp(dummy->name, n) == 0) {
            printf("Name Already Exists in List! Please retry with other name..\n");
            duplicate=-1;
            break;
        }
        else
            dummy = dummy->next;
    }
    if (duplicate!=-1) {
        newNode->name = malloc( strlen(n) + 1 );
        strcpy(newNode->name, n);
        newNode->age = a;
        newNode->next = ptr;
        return newNode;
    }
    duplicate = 1;
    return ptr;
}

//function to find age of the passed person
int getAge(Person *ptr, char *name) {
    while (ptr) {//while loop to traverse entire linked list elements (All persons one by one)
        if(strcmp(ptr->name, name) == 0) //comparing person name in the list with the search key name
            return ptr->age; //if found, returning the age of that person
        else
            ptr = ptr->next; //if not found, check in next node of linked list
    }

    return -1; // if not found, even after visting all nodes, return -1
}

Answer 1

你可以做一个插入排序。每次添加新记录时，您都会扫描列表以查看它所属的位置并将其插入到那里。这可以与您扫描重复项相结合。

Person *add(Person *head, char *n, int a) {
  char empty[1] = "";
  Person sentinel = {0};
  sentinel.name = empty;
  sentinel.next = head;
  Person *p = &sentinel;
  while (p) {
    int cmp = p->next ? strcmp(n, p->next->name) : -1;
    if (cmp == 0) {
      printf("Name Already Exists in List! Please retry with another name..\n");
      break;
    }
    if (cmp < 0) {
      Person *newNode = malloc( sizeof(Person) );
      newNode->name = malloc( strlen(n) + 1 );
      strcpy(newNode->name, n);
      newNode->age = a;
      newNode->next = p->next;
      p->next = newNode;
      break;
    }
    p = p->next;
  }
  return sentinel.next;  // a possibly-updated copy of head
}

插入排序总是将新元素与下一个 元素(而不是与当前元素)进行比较。这使得处理第一个元素很尴尬，尤其是在列表中。我们通过假装就在列表头部之前的临时“哨兵”来解决这个问题。

还有其他方法。您可以在列表的头部创建新节点，然后将其向下滑动直到就位。如果遇到重复项，则删除新的并修补列表。其他数据结构中的插入排序通常从尾部向头部工作，但这不适用于单链表。