如何在 C 中对具有多个元素的双向链表进行排序？

Question

我需要对一个包含多个元素的双向链表进行排序，我的结构如下：

typedef struct node {
   int code;
   char name[40];
   char job[40];
   int salary;
   struct nodo *next;
   struct nodo *prev;
} node;

详细来说，我必须创建一个函数来接收 *Head 并按元素的 salary 对元素进行排序（从低到高），例如

node1->salary = 1000;
node2->salary = 500;
node3->salary = 1500;

该函数必须排序，因此顺序设置为 node2、node1、node3。到目前为止，这是我尝试过的：

void sort(node *head) 
{ 
    int swapped, i; 
    node *ptr1; 
    node *lptr = NULL; 

    if (top == NULL) 
        return; 

    do
    { 
        swapped = 0; 
        ptr1 = head; 

        while (head->next != lptr) 
        { 
            if (ptr1->salary > ptr1->next->salary) 
            {  
                // This part actually only changes the positions of the salary
                // I need to change the position of all the elements
                node *temp;
                temp->salary= ptr1->salary;
                ptr1->salary= ptr1->next->salary;
                ptr1->next->salary= temp->salary;
                swapped = 1; 
            } 
            ptr1 = ptr1->next; 
        } 
        lptr = ptr1; 
    } 
    while (swapped); 
}

Answer 1

这里是一个例子，升序和降序排序

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

typedef struct node {
   int code;
   char name[40];
   char job[40];
   int salary;
   struct node *next;
   struct node *prev;
} node;

void swapNodes(node *a, node *b) {
  node tmp = *a;
  a->code = b->code;
  strcpy(a->name, b->name);
  strcpy(a->job, b->job);
  a->salary = b->salary;
  b->code = tmp.code;
  strcpy(b->name, tmp.name);
  strcpy(b->job, tmp.job);
  b->salary = tmp.salary;
}

//////////////////////////////////////////////////////////////////////////////////////
// \brief  Sort the linked list in ascending or descending order
// \param  head        The head node of the list
//
// \param  isReversed  Whether to sort in asc or desc, false for asc and true for desc
//////////////////////////////////////////////////////////////////////////////////////
void sort(node *head, bool isReversed) {
  // store the current and the previous nodes
  node *currentNode, *previousNode;
  // store if there still a difference in the list means that we have some nodes not sorted
  bool difference;
  loopAgain:
    // looping again and assuming no more difference
    difference = false;
    currentNode = previousNode = head;
    // loop over the list
    while(currentNode != NULL) {
      currentNode = currentNode->next;
      // check for salary if the current salary is less than the previous and in ascending mode
      // then swap the nodes and the opposite in descending mode
      if(currentNode != NULL && (isReversed ? previousNode->salary < currentNode->salary :
          previousNode->salary > currentNode->salary)) {
        swapNodes(previousNode, currentNode);
        difference = true;
      }
      previousNode = currentNode;
    }
  // go to loop again since there still maybe no sorted nodes yet
  if(difference) {
    goto loopAgain;
  }
}

int main() {
  node n1 = {0, "a", "-", 3500, NULL, NULL},
    n2 = {0, "b", "-", 500, NULL, &n1},
    n3 = {0, "c", "-", 1500, NULL, &n2};
  n1.next = &n2;
  n2.next = &n3;
  printf("Before sort:\n%s)%d\n%s)%d\n%s)%d\n", n1.name, n1.salary, n2.name, n2.salary, n3.name, n3.salary);
  sort(&n1, false);
  printf("After ascending sort:\n%s)%d\n%s)%d\n%s)%d\n", n1.name, n1.salary, n2.name, n2.salary, n3.name, n3.salary);
  sort(&n1, true);
  printf("After descending sort:\n%s)%d\n%s)%d\n%s)%d", n1.name, n1.salary, n2.name, n2.salary, n3.name, n3.salary);
  return 0;
}

输出

Before sort:
a)3500
b)500
c)1500
After ascending sort:
b)500
c)1500
a)3500
After descending sort:
a)3500
c)1500
b)500

Answer 2

初学者有错字

typedef struct node {
   int code;
   char name[40];
   char job[40];
   int salary;
   struct nodo *next;
          ^^^^
   struct nodo *prev;
          ^^^^
} node;

应该有

typedef struct node {
   int code;
   char name[40];
   char job[40];
   int salary;
   struct node *next;
          ^^^^
   struct node *prev;
          ^^^^ 
} node;

其次，如果你想对列表进行排序，那么你应该对其节点的顺序进行排序，而不是交换节点数据成员的值。例如，在 main 中可以声明一个指向某个节点的指针。如果您将通过交换节点数据成员的值来对列表进行排序，那么指针将无效，因为指向节点的数据成员已更改。

第三，除了指针next和prev之外的所有数据成员应该放在一个单独的结构中。在这种情况下，函数声明看起来会简单得多，因为您不需要将多个初始值设定项传递给函数，而只需传递一个结构类型的对象。

例如

typedef struct Person
{
    int  code;
    char name[N];
    char job[N];
    int  salary;
} Person;

typedef struct Node 
{
    Person person;  
    struct Node *prev;
    struct Node *next;
} Node;

最后，如果您处理双向链表，那么您应该可以将新节点添加到列表的开头和结尾。这意味着您应该保留两个指针：一个指向列表的第一个节点，另一个指向列表的最后一个节点。这样做的结果是您应该再声明一个结构来描述列表，例如

typedef struct List
{
    Node *head;
    Node *tail;
} List;

现在一切准备就绪，是时候展示如何将冒泡排序方法应用于这样的列表了。

这是一个演示程序。

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

enum { N = 40 };

typedef struct Person
{
    int  code;
    char name[N];
    char job[N];
    int  salary;
} Person;

typedef struct Node 
{
    Person person;  
    struct Node *prev;
    struct Node *next;
} Node;

typedef struct List
{
    Node *head;
    Node *tail;
} List;

int push_back( List *list, const Person *person )
{
    Node *new_node = malloc( sizeof( Node ) );
    int success = new_node != NULL;

    if ( success )
    {
        new_node->person = *person;
        new_node->prev   = list->tail;
        new_node->next   = NULL;

        if ( list->tail == NULL )
        {
            list->head = list->tail = new_node; 
        }
        else
        {
            list->tail = list->tail->next = new_node;
        }
    }

    return success;
}

void display( const List *list )
{
    for ( Node *current = list->head; current != NULL; current = current->next )
    {
        printf( "code = %d, name = %s, job = %s, salary = %d\n",
                current->person.code, current->person.name, 
                current->person.job, current->person.salary );
    }
}

void swap( Node **current )  
{  
    Node *tmp = *current;  

    *current = ( *current )->next;  

    tmp->next = ( *current )->next;
    ( *current )->next = tmp;

    ( *current )->prev = tmp->prev;
    tmp->prev = *current;

    if ( tmp->next != NULL )
    {
        tmp->next->prev = tmp;
    }
}

void clear( List *list )
{
    while ( list->head != NULL )
    {
        Node *current = list->head;
        list->head = list->head->next;
        free( current );
    }

    list->tail = list->head;
}

void sort( List *list, int cmp( const void *, const void * ) )
{
    if ( list->head != NULL )
    {
        int first_iteration = 1;

        for ( Node **first = &list->head, *sorted = NULL, *last = NULL;
              ( *first )->next != last;
              last = sorted )
        {
            Node **current = first;
            sorted = ( *first )->next;

            for ( ; ( *current )->next != last; current = &( *current )->next )
            {
                if ( cmp( &( *current )->person, &( *current )->next->person ) > 0 )
                {
                    swap( current );
                    sorted = ( *current )->next;
                }
            }

            if ( first_iteration )
            {
                list->tail = *current;
                first_iteration = 0;
            }               
        }             
    }         
}

int cmp_by_salary( const void *a, const void *b )
{
    const Person *left  = a;
    const Person *right = b;

    return ( right->salary < left->salary ) - ( left->salary < right->salary );
}

int cmp_by_code( const void *a, const void *b )
{
    const Person *left  = a;
    const Person *right = b;

    return ( right->code < left->code ) - ( left->code < right->code );
}

int cmp_by_name( const void *a, const void *b )
{
    const Person *left  = a;
    const Person *right = b;

    return strcmp( left->name, right->name );
}

int main(void) 
{
    List list = { .head = NULL, .tail = NULL };

    Person person[] =
    {
        { .code = 1, .name = "RaCo", .job = "programmer", .salary = 1000 },
        { .code = 2, .name = "Another RaCo", .job = "programmer", .salary = 500 },
        { .code = 3, .name = "One more RaCo", .job = "programmer", .salary = 1500 },
    };
    const size_t n = sizeof( person ) / sizeof( *person );

    puts( "Original list:" );
    for ( size_t i = 0; i < n; i++ )
    {
        push_back( &list, person + i );
    }

    display( &list );
    putchar( '\n' );

    sort( &list, cmp_by_salary );

    puts( "list sorted by salary:" );
    display( &list );
    putchar( '\n' );

    sort( &list, cmp_by_name );

    puts( "list sorted by name:" );
    display( &list );
    putchar( '\n' );

    sort( &list, cmp_by_code );

    puts( "list sorted by code:" );
    display( &list );
    putchar( '\n' );

    printf( "Debug output. The pointer tail points to %s\n", list.tail->person.name );

    clear( &list );

    return 0;
}

程序输出为

Original list:
code = 1, name = RaCo, job = programmer, salary = 1000
code = 2, name = Another RaCo, job = programmer, salary = 500
code = 3, name = One more RaCo, job = programmer, salary = 1500

list sorted by salary:
code = 2, name = Another RaCo, job = programmer, salary = 500
code = 1, name = RaCo, job = programmer, salary = 1000
code = 3, name = One more RaCo, job = programmer, salary = 1500

list sorted by name:
code = 2, name = Another RaCo, job = programmer, salary = 500
code = 3, name = One more RaCo, job = programmer, salary = 1500
code = 1, name = RaCo, job = programmer, salary = 1000

list sorted by code:
code = 1, name = RaCo, job = programmer, salary = 1000
code = 2, name = Another RaCo, job = programmer, salary = 500
code = 3, name = One more RaCo, job = programmer, salary = 1500

Debug output. The pointer tail points to One more RaCo

如您所见，使用同一个函数 sort 您可以按结构 Person 的任何数据成员对列表进行排序。每次必须更改排序条件时，您无需编写新的排序函数。

如果你需要对列表进行排序，例如按数据成员薪水降序排列，那么只需在比较函数return语句中交换变量

int cmp_by_salary( const void *a, const void *b )
{
    const Person *left  = a;
    const Person *right = b;

    return ( right->salary < left->salary ) - ( left->salary < right->salary );
}

喜欢

int cmp_by_salary_desc( const void *a, const void *b )
{
    const Person *left  = a;
    const Person *right = b;

    return ( left->salary < right->salary ) - ( right->salary < left->salary );
}

并调用函数 sort as

sort( &list, cmp_by_salary_desc );

如何在 C 中对具有多个元素的双向链表进行排序？

How to sort doubly linked list with multiple elements in C?

c

sorting

linked-list

bubble-sort

doubly-linked-list