在C语言中使用结构体对链表进行排序

Question

我曾经在一个用于排序已插入链表的书籍程序中尝试使用所学过的冒泡排序方法。我尝试交换了两个节点，但这也导致了nextptr被交换。我开始写一个名为authsort的新函数，它不引用书籍结构中的成员。为使此排序工作，我需要改变什么？

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

struct book
{
    char author[30];
    char title[50];
    char hold2[50];
    char titleins[50];
    char genre[15];
    int rating;
    int comma;
    int titleshift;
    int number;
};
struct listnode
{
    struct book data;
    struct listnode *nextptr;
};
    typedef struct listnode LISTNODE;
    typedef LISTNODE *LISTNODEPTR;



    void insert(LISTNODEPTR *sptr, struct listnode data);
    void authsort(LISTNODEPTR sptr, struct listnode data);
    void freenodes(LISTNODEPTR currentptr);
    int add_2 (count, i, j, index, tag);
    void print_list(LISTNODEPTR, struct listnode book);
    int main ()
    {
        LISTNODEPTR startptr = NULL;
        struct listnode listnode;
        struct book book;
        int choice = 0;
        char item;
        int count = 0;
        int index = 0;
        int j = 0;
        char * pch2;
        char string[40];
        char string2[40];
        char * pch;
        int i = 0;
        while( choice != 2)
        {
        printf("What Would You Like To Do?\n");
        printf("1.Add Books\n2.exit\n3:sort by author\n");
        scanf("%d", &choice);
        getchar();




    switch(choice)
    {
        case 1:
                printf("Enter your book title:");
                gets(listnode.data.title);
                for(i=0;i<100;i++)
                {
                    listnode.data.title[i] = tolower(listnode.data.title[i]);
                }
                printf("Enter the author:");
                if(listnode.data.title[0] == 't')
                    {
                        if(listnode.data.title[1] == 'h')
                        {
                            if(listnode.data.title[2] == 'e')
                            {
                                if(listnode.data.title[3] == ' ')
                                {
                                    book.titleshift = 4;
                                    pch = strtok(listnode.data.title, " ");
                                    strcpy(string, pch);
                                    pch2 = strtok(NULL, "");
                                    book.comma = strlen(pch2);
                                    strcpy(string2, pch2);
                                    strncat(string2, string, 20);
                                    strncpy(listnode.data.title, string2, 50);

                                }
                            }
                        }
                    }
                if(listnode.data.title[0] == 'a')
                {
                    if(listnode.data.title[1] == ' ')
                    {
                        book.titleshift = 2;
                        pch = strtok(listnode.data.title, " ");
                        strcpy(string, pch);
                        pch2 = strtok(NULL, "");
                        book.comma = strlen(pch2);
                        strcpy(string2, pch2);
                        strncat(string2, string, 20);
                        strncpy(listnode.data.title, string2, 50);
                    }
                }
                gets(listnode.data.author);
                for(i=0;i<100;i++)
                {
                    listnode.data.author[i] = tolower(listnode.data.author[i]);
                }
                printf("Enter the genre:");
                gets(listnode.data.genre);

                for(i=0;i<100;i++)
                {
                    listnode.data.genre[i] = tolower(listnode.data.genre[i]);
                }
                printf("Enter the quality:");
                scanf("%d", &listnode.data.rating);
                printf("Enter the number of pages:");
                scanf("%d", &listnode.data.number); // after scanning in from user, we insert and print the list
                insert(&startptr, listnode);
                print_list(startptr, listnode);
                break;
        case 2:
        freenodes(startptr);
        break;
        case 3:
        authsort(startptr, listnode);
        print_list(startptr, listnode);
        break;
    }
        }
    return 0;
}


/*********************************FUNCTION*********************************/
void print_list(LISTNODEPTR currentptr, struct listnode book)
{

    if (!currentptr)
        printf("List is empty.\n\n");
    else
     {
        printf("your list:\n");
         while (currentptr)

         {
             if(currentptr->data.comma > 1)
                {

             printf("%-15s %-20s %-15s %-15d %-15d\n", currentptr->data.author, currentptr->data.title, currentptr->data.genre, currentptr->data.rating, currentptr->data.number);
            currentptr = currentptr -> nextptr; // this will continue printing as long as there in a nextptr, or book

                }

                else if(currentptr->data.comma == 0)
                {
                    printf("%-15s %-20s %-15s %-15d %-15d\n", currentptr->data.author, currentptr->data.title, currentptr->data.genre, currentptr->data.rating, currentptr->data.number);
                    currentptr = currentptr -> nextptr; // this will continue printing as long as there in a nextptr, or book

                }
         }

        if(!currentptr)
        {
            printf("end of list\n\n");

        }
     }
}

/*********************FUNCTION******************/
void insert(LISTNODEPTR *sptr, struct listnode data)
{
     LISTNODEPTR newptr, previousptr, currentptr;
     newptr = malloc(sizeof(LISTNODE));
     int i = 0;

        if (newptr)
        {



            strcpy(newptr -> data.title,data.data.title);

            //if(book.titleshift == 0)
            //{

            //strcpy(newptr -> title,book.title);
            //}
            // here the books are being copied into the current node
            strcpy(newptr -> data.author, data.data.author);
            strcpy(newptr -> data.genre, data.data.genre);
            newptr -> data.rating= data.data.rating;
            newptr -> data.number= data.data.number;
            newptr -> nextptr = NULL;
            previousptr = NULL;
            currentptr = *sptr;

     while (currentptr != NULL && strcmp(data.data.title, currentptr -> data.title)>0)
                            // this compares the titles to insert by author
     {
        previousptr = currentptr;
        currentptr = currentptr -> nextptr;
     }
        if (previousptr == NULL)
        {
        newptr -> nextptr = *sptr;
        *sptr = newptr;
        }
        else
        {
            previousptr -> nextptr = newptr;
            newptr -> nextptr = currentptr;
        }
            }
            else
            {
                printf("Not inserted.\n");
            }
}

/*******************************FUNCTION***********************************/

/**************************FUNCTION*********************/
void freenodes(LISTNODEPTR currentptr)
{
 LISTNODEPTR tempptr;
 while(currentptr!=NULL)
 {
  tempptr=currentptr->nextptr;
  free(currentptr);
  currentptr=tempptr;
 }
}

void authsort(LISTNODEPTR sptr, struct listnode data)
{
    LISTNODEPTR nextptr;
    LISTNODEPTR previousptr;
    LISTNODEPTR currentptr;
    LISTNODEPTR tempptr;
    LISTNODEPTR trail;
        int count = 0;
        int j = 0;
        while(sptr != NULL)
        {
            count++;
            sptr = sptr -> nextptr;
        }
        for(j=0;j<count;j++)
        {

        currentptr = sptr;
        while(currentptr->nextptr != NULL)
        {


            if(strcmp(currentptr ->data.author, currentptr->nextptr.data.author)>0)
            {
                tempptr = currentptr ->nextptr;
                currentptr ->nextptr = currentptr ->nextptr->nextptr;
                currentptr ->nextptr = currentptr;


                if(currentptr == sptr)
                  sptr = trail = tempptr;
                else
                  trail->nextptr = tempptr;
                currentptr = tempptr;
              }

              trail = currentptr;
              currentptr = currentptr->nextptr;
        }

        }



}

- Sergei Levashov

---

大多数书籍中学习的冒泡排序不适用于链表，它是针对数组设计的。如果你想在链表上进行排序，代码会非常不同。我建议你看一下递归合并排序在链表上的实现，这样做相当简单。 - Mox

请通过此链接 http://geeksquiz.com/c-program-bubble-sort-linked-list/ 进行查看，这将对您有所帮助。 - aakansha

@Mox：为什么冒泡排序在链表上不起作用？你只能交换相邻节点，这很容易实现。（我不是说它是一种好的排序方法，但它可以用于链表。） - M Oehm

@aa1992 谢谢，我觉得我的代码现在用那个方法可以工作了。 - Sergei Levashov

@Mox：如果你愿意，甚至可以交换指针。它们总是相邻的，因此 a->next == b。 - M Oehm

Answer 1

看，你的最终目标应该是拥有一个已排序的链表。现在你正在尝试对两个节点进行排序，但你甚至可以交换它们的数据！

这不涉及指针重定位，使你的程序更容易分析和理解。我希望这能提示你找到正确的解决方案！

祝编码愉快 :)

- Venkatesh Suvarna

Answer 2

你的代码存在一些问题：

• 在确定长度后，sptr 变成了 NULL。从这里开始，你不能再对代码做任何有意义的操作，因为你已经丢失了头指针。
• 如果你想交换节点本身而不仅仅是数据，你可能需要更新头指针。目前，你只是传递了头指针，但如果调用代码必须反映对头指针所做的更改，则应传递指向头指针的指针。
• 当你交换指针时，还必须更新指向当前节点的指针，它可以是 sptr 或前一个节点的 nextptr 成员。
• 你使用了太多的临时变量。例如，trail 从未被使用过，你的函数的第二个参数也没有被使用过。

让我们解决这些问题。首先，我们不会使用 acount。相反，我们会跟踪是否需要在一次遍历中更改任何节点。如果不需要，那么我们就完成了，因为列表已经排序好了。否则，我们进行另一次遍历。

跟踪前一个节点的问题有一种优雅的解决方案，涉及将头指针作为参数传递给指针的问题：使用指向当前节点指针的指针进行迭代，这会增加一级间接性：迭代指针 curr 现在指向指向当前节点（原始头指针从调用函数中传递或者一个nextptr成员）的指针。

这个解决方案不把头指针作为一个特例。它导致代码更短，但也会产生大量嘈杂的(*curr)语法。

以下是一个可运行的实现，它交换节点而不是有效载荷：

void authorsort(struct listnode **sptr)
{
    int done = 0;

    while (!done) {
        struct listnode **curr = sptr;

        done = 1;
        while ((*curr)->nextptr != NULL) {
            if (strcmp((*curr)->data.author, 
                (*curr)->next->data.author) > 0) {
                struct listnode *temp = (*curr)->nextptr;

                (*curr)->nextptr = temp->nextptr;
                temp->nextptr = *curr;
                *curr = temp;

                done = 0;
            }

            curr = &(*curr)->nextptr;
        }
    }
}

交换有效载荷更容易，但如果您从外部拥有对这些节点的指针（例如，如果书集将书作为指针引用），则交换节点是必要的。

- M Oehm