c - 按字母顺序排序 c 中的列表

Question

您好，我正在编写一个管理学生列表的程序，我正在使用一个列表，每个元素的描述如下:

struct student
{
    char lastname[50];
    char name[50];
    char date_of_birth[50];
    char height[50];
    struct student *next;
};

struct student *root=0; //this is the root node

这是我向列表中添加元素的方式:

void add_element(struct student **root, char lastname[50], char name[50], char date_of_birth[50], char height[50])
{
    if(*root == 0)
    {
        *root = malloc(sizeof(struct student));
         strcpy((*root)->lastname,lastname);
         strcpy( (*root)->name,name);
         strcpy( (*root)->date_of_birth,date_of_birth);
         strcpy( (*root)->height,height);

        (*root)->next = 0;
    }
    else
    {
        add_element(&(*root)->next,lastname,name,date_of_birth,height);
    }
} 

我还写了 2 个函数，一个是从文件中读取，另一个是写入文件，文件包含所有学生，一切正常，但我需要一个函数来按姓氏的字母顺序对所有元素进行排序，我试着写一个，但它不起作用，它一直在崩溃。

我尝试了很多东西，但都没有用，这是一次尝试，但没有用:-(

请帮帮我

void sort(struct student *head)
{
    struct student **current;
    struct student *tmp;

    for(current = &head ; *current !=NULL ; current = (*current)->next)
    {
        if((*current)->next == NULL)
        {
            break;
        }
        switch(strcmp((*current)->lastname,(*current)->next->lastname))
        {
            case 0:
            {
                printf("user not valid");
                break;
            }

            case 1:
            {
                tmp = *current;
                *current = (*current)->next;
                (*current)->next = tmp;
                break;
            }
        }
    }
}

Answer 1

在包含评论中的评论以更正建议的源代码之后，排序链表的算法缺少一些步骤。至少，要对链表进行排序，必须有两个循环。 struct student **current 访问权限的选择对于两个嵌套循环来说会很复杂。

这是使用优化的 qsort() 函数的另一个强大的排序函数。

第 1 步 - 在显示函数之前，要对列表进行排序，应修改 root 指针。

First method, used for the add_element() by sending the address of the pointer.

void sort(struct student **root)
{
...
}

Second method, to return the modified root.

struct student *sort(struct student *root)
{
...
    return (root);
}

第 2 步 - 使用 qsort() 快速排序函数的函数 sort()。

该方法分配一个临时指针数组，以便对固定大小的元素进行排序。

1. 第一个循环需要知道要排序的指针的个数(如果小于2，则不需要排序)；
2. 分配struct student *数组后，对链表的每一项使用循环填充数组；
3. 使用自定义比较函数node_compare()调用qsort()函数(见下一步)；
4. 通过强制 struct student *next 的值(第一个是 *root，最后一个指向 NULL)，用排序后的指针恢复链表.
5. 释放struct student *的临时数组；

就这些。

//
void sort(struct student **root)
{
    struct student *tmp;
    struct student **array;
    int i,icount;

    // number of nodes to be sorted
    for(tmp = *root,icount = 0;tmp!=NULL;tmp = tmp->next,icount++);
    if (icount<2) {
        // no sort needed
        return;
    }

    // allocate an array of pointers
    array = (struct student **)malloc(icount*sizeof(struct student *));
    // push linked-list into array of pointers
    for(tmp = *root,icount = 0;tmp!=NULL;tmp = tmp->next,icount++) {
        array[icount]=tmp;
    }

    // quicksort using node_compare() customized function
    qsort(array, icount, sizeof(struct student *), node_compare);

    // pop linked-list from array of pointers
    *root = array[0];
    (*root)->next = NULL;
    for(tmp = *root,i = 1;i<icount;i++) {
        tmp->next = array[i];
        array[i]->next = NULL;
        tmp = tmp->next;
    }
    // free the allocated array of pointer
    free(array);
}
//

第 3 步 - qsort() 所需的比较函数 node_compare()。

The function shall return a signed comparison as strcmp() does.

int node_compare(const void * a, const void * b)
{
    // restore node pointers
    struct student *node_a = *((struct student **)a);
    struct student *node_b = *((struct student **)b);

    if (node_b==NULL) return (-1); // force 'node_a'
    if (node_a==NULL) return (+1); // force 'node_b'
    // use the strcmp() function
    return (strcmp(node_a->lastname,node_b->lastname));
}

增强 - 因为 add_element() 使用的是不符合长链表的递归调用，所以这是一个非常简单的非递归算法。

If the recursive algorithm limits the size to few-centuries of elements, the proposed one has been tested with 100,000 elements (40Mb linked-list), generated randomly and sorted.

void add_element(struct student **root, char lastname[50], char name[50], char date_of_birth[50], char height[50])
{
    struct student **current;

    for(current = root; *current !=NULL ; current = &((*current)->next));
    *current = (struct student *)malloc(sizeof(struct student));
    strcpy((*current)->lastname,lastname);
    strcpy( (*current)->name,name);
    strcpy( (*current)->date_of_birth,date_of_birth);
    strcpy( (*current)->height,height);

    (*current)->next = NULL;
}