在C语言中如何对链表进行按字母顺序排序？

Question

在C语言中如何对链表进行按字母顺序排序？

4

我试图对这个链表中的名字按字母顺序进行排序，但我不确定应该采取什么样的方法。我创建了一个比较链表中名字并每次更新当前指针的方法。但我一直在出错。有人能建议一种更好的方法来遍历这些名字吗？我是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;
}

- Shamveel Ahammed

检查列表的开头。如果该元素在字典顺序上大于您要插入的单词，请检查下一个元素。重复此过程。如果找到一个在字典顺序上小于您的单词的元素，则在那里插入该单词。 - Ricky Mutschlechner

链表非常适合使用归并排序。请参见http://stackoverflow.com/questions/35614098/implementing-mergesort-on-a-linked-list/35616981#35616981。 - Gene

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- chqrlie · Accepted Answer

你的方法过于复杂：比较函数执行某种排序，插入函数也执行排序。比较函数应该返回一个像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;
}

编辑：下面是一个简化版的指针示例。你会发现需要特殊处理空列表和在开始处插入的情况。

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;
    }
}