无法在C中按升序对链表进行排序

Question

我正在尝试使用代码块编辑器在 C 上制作图书馆管理系统程序。

到目前为止，我已经成功地使程序打印了图书馆书籍的名称和作者姓名，但是当它询问我是否要按升序排列并按 'y' 时，它再次打印相同的列表而不按升序排列（我正在尝试使用冒泡排序算法进行排序）。

请相应修改代码并附上详细说明。

原文：

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

struct Node {
    char name[50];
    char author[50];
    struct Node* next;
};
struct Node* head; // Global Variable
void Insert(char q[50], char r[50]);
void Print();
void bsort();

int main()
{
    int n,i; //Local Variables
    char x[50],y[50]; // Local Variables
    char d;
    head=NULL; //Initially head is null
    printf("How many books you want to enter?: ");
    scanf("%d",&n);
    for (i=1; i<=n; i++) // Loop iterate the number of times we have books in quantity.
    {
        printf("Enter a Book name: ");
        fflush(stdin); // To clear buffer memory
        gets(x); // Same as scanf
        printf("Author: ");
        gets(y);
        Insert(x,y);

    }
    Print();
    printf("Do you want to sort the data in ascending order?(y/n): ");
    scanf("%c",&d);
    printf("Your pressed %c",d);
    if (d=='y')
    {
        bsort();
        Print();
    }
    else
        printf("alright!");

    return 0;
}

void Insert(char q[50], char r[50]) //Adding items at the end of linked list
{
    struct Node* temp = (struct Node*)malloc(sizeof(struct Node));
    temp->next=NULL; // Since we are adding a node to the end, we are linking it to NULL.
    strcpy(temp->name,q); // copying the contents of "q" to "temp->name"
    strcpy(temp->author,r); // same
    if(head==NULL)
    {
        head=temp;
    }
    else
    {
        struct Node* temp1 = head;
        while(temp1->next!=NULL)
            temp1=temp1->next;
        temp1->next=temp;
    }
}
void Print() //Traversing
{
    printf("\n");
    printf("The Library data is as follows: \n");
    struct Node* temp=head;
    printf("\n");
    while(temp!=NULL)
    {
        printf("%25s",temp->name);
        printf("%25s",temp->author);
        temp=temp->next;
        printf("\n");
    }
}

void bsort() //Bubble Sort Algorithm to arrange Library data in Ascending Order
{
    int count=1,k=1;
    char temp3[50];
    struct Node* i=head;
    struct Node* j;
    j=i->next;
    while(i!=NULL)
    {
        i=i->next;
        count++;
    }
    {
        for (k=1; k=count-1; k++)
        {
            for (i=head; i<=NULL-k; i=i->next)
            {
                if(i->name>j->name)
                {
                    strcpy(temp3,i->name);
                    strcpy(i->name,j->name);
                    strcpy(j->name,temp3);
                }
                j=j->next;
            }
        }
    }
}

第一次编辑：

void bsort() //Bubble Sort Algorithm to arrange Library data in Ascending Order
{
    int count=1,k=1;
    char temp3[50];
    struct Node* i=head;
    struct Node* j;
    j=i->next;
    while(i!=NULL)
    {
        i=i->next;
        count++;
    }

    for (k=1; k=count-1; k++)
    {
        for (i=head; i<=count-k; i=i->next)
        {
            if (strcmp(i->name,j->name)>0)
            {
                strcpy(temp3,i->name);
                strcpy(i->name,j->name);
                strcpy(j->name,temp3);
            }
            j=j->next;
        }
    }
}

第二次编辑：

void bsort() //Bubble Sort Algorithm to arrange Library data in Ascending Order
{
    int count=1,k=1;
    char temp3[50];
    struct Node* i=head;
    struct Node* j;
    j=i->next;
    while(i!=NULL)
    {
        i=i->next;
        count++;
    }

    for (k=1; k<=count-1; k++)
    {
        for (i=head; i<=count-k; i=i->next)
        {
            if (strcmp(i->name,j->name)>0)
            {
                strcpy(temp3,i->name);
                strcpy(i->name,j->name);
                strcpy(j->name,temp3);
            }
            j=j->next;
        }
    }
}

第三次编辑

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

struct Node {
    char name[50];
    char author[50];
    struct Node* next;
};
struct Node* head; // Global Variable
void Insert(char q[50], char r[50]);
void Print();
void bsort_print();
int main()
{   int n,i; //Local Variables
    char x[50],y[50]; // Local Variables
    char d;
    head=NULL; //Initially head is null
    printf("How many books you want to enter?: ");
    scanf("%d",&n);
    for (i=1; i<=n; i++) // Loop iterate the number of times we have books in quantity.
    {
        printf("Enter a Book name: ");
        fflush(stdin); // To clear buffer memory
        gets(x); // Same as scanf
        printf("Author: ");
        gets(y);
        Insert(x,y);

    }
    Print();
    printf("Do you want to sort the data in ascending order?(y/n): ");
    scanf("%c",&d);
    printf("Your pressed %c",d);
    if (d=='y')
    {
        bsort_print();
    }
    else
        printf("alright!");

    return 0;
}

void Insert(char q[50], char r[50]) //Adding items at the end of linked list
{
    struct Node* temp = (struct Node*)malloc(sizeof(struct Node));
    temp->next=NULL; // Since we are adding a node to the end, we are linking it to NULL.
    strcpy(temp->name,q); // copying the contents of "q" to "temp->name"
    strcpy(temp->author,r); // same
    if(head==NULL)
    {
        head=temp;
    }
    else {
        struct Node* temp1 = head;
        while(temp1->next!=NULL)
            temp1=temp1->next;
        temp1->next=temp;
    }
}
void Print() //Traversing
{
    printf("\n");
    printf("The Library data is as follows: \n");
    struct Node* temp=head;
    printf("\n");
    while(temp!=NULL)
    {
        printf("%25s",temp->name);
        printf("%25s",temp->author);
        temp=temp->next;
        printf("\n");
    }
}
void bsort_print() //Bubble Sort Algorithm to arrange Library data in Ascending Order
{
    int count=1,k=1;
    char temp3[50];
    struct Node* i=head;
    struct Node* j;
    struct Node* current=i;
    j=i->next;
    while(i!=NULL)
    {
        i=i->next;
        count++;
    }

    for (k=1; k<=count-1; k++)
    {
        for (count=1; count<count-k; count++)
        {
            if (strcmp(i->name,j->name)>0)
            {
                strcpy(temp3,i->name);
                strcpy(i->name,j->name);
                strcpy(j->name,temp3);
            }
            j=j->next;
        }
    }
    printf("\n");
    printf("The Library data is as follows: \n");
    printf("\n");
    while(current!=NULL)
    {
        printf("%25s",current->name);
        printf("%25s",current->author);
        current=current->next;
        printf("\n");
    }
}

Answer 1

冒泡排序的实现有问题

您的冒泡排序实施存在一些问题：

我认为你的意思是 i <= count-k 而不是 i<=NULL-k 因为 NULL == 0 所以语句 i<=NULL-k 等同于 i<=-k 和 i > k.
使用 strcmp 而不是 i->name>j->name 因为你比较的是数组的地址而不是名称。
您忘记在您的结构中交换作者。

更好的实现

其余代码需要更改的地方

每次你有一个数组使用 #define MAX_STRING_LENGTH 50 而不是重复 50 ，它更具可读性，如果你需要更改它，你可以这样做而不必搜索每个出现在代码中。
void Insert(char q[50], char r[50]); 你不需要在函数的参数中指定数组的维数，你可以只 void Insert(char *p, char *r); 它指的是指向字符的通用指针。
与其将用户输入保存在两个数组中，然后将它们复制到节点中的数组，不如使用 malloc 函数分配新数组然后仅处理对它的引用更有效进入节点。这允许您不使用 O(n) 的 strcpy 并减慢很多代码。
用typedef struct node {<ARGS>} Node;定义一个新的变量类型，这样你就可以写Node*而不是struct Node*这样更具可读性。

气候复杂性

这是冒泡排序CC与站点lizard.ws:

的分析结果

// Imports
//---------------------------------------------
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
//---------------------------------------------
// Definitions
//---------------------------------------------
#define MAX_STRING_LENGTH 50
//---------------------------------------------
// Type definitions to make the code more readable
//---------------------------------------------
typedef struct node {
    char *name;
    char *author;
    struct node * next;
} Node;
//---------------------------------------------
// Global Variable
//---------------------------------------------
Node* head = NULL;
//---------------------------------------------
// Function protoypes
//---------------------------------------------
void insert(char *q, char *r);
void print_the_list();
void bsort();
//---------------------------------------------
// Main Function :
// Ask the user to insert some books then
// print the list of books
// normally or sorted by book name
//---------------------------------------------
int main() {
    head = NULL; //Initially head is null

    char *book_name, *book_author;

    int n; // Number of book that the user want to enter
    printf("How many books you want to enter?: \n");
    scanf("%d", &n);

    for (int i = 1; i <= n; i++){ // Loop iterate the number of times we have books in quantity.
        // To clear buffer memory
        fflush(stdin);

        // get the name
        printf("Enter a Book name: \n");
        // allocate the memory for the name of the new book
        book_name = (char*) malloc(MAX_STRING_LENGTH*sizeof(char));
        gets(book_name); // Same as scanf

        // get the author
        printf("Author: \n ");
        // allocate the memory for the author of the new book
        book_author = (char*) malloc(MAX_STRING_LENGTH*sizeof(char));
        gets(book_author);

        // add it to the list
        insert(book_name, book_author);

    }

    print_the_list();
    char d;
    printf("Do you want to sort the data in ascending order?(y/n): \n\t");
    scanf("%c", & d);
    if (d == 'y') {
        printf("Soprting the list!");
        bsort();
    } else
        printf("alright!");

    print_the_list();
    return 0;
}
//---------------------------------------------
// insert(name of the book, authro of the book):
// O(n_of_element_in_the_list)
// append the new book the global list
//---------------------------------------------
void insert(char* name, char* author){ //Adding items at the end of linked list
    // create and initialize the new node
    Node* new_node = (Node* ) malloc(sizeof(Node));
    new_node->author = author;
    new_node->name   = name;
    new_node->next   = NULL; // Since we are adding a node to the end, we are linking it to NULL.

    // if the list is empty then add the node as the head of the list
    if (head == NULL) {
        head = new_node;
    }
    else {
        Node * temp = head;
        // Traverse the list till the end
        while (temp->next != NULL)
            temp = temp->next;
        // add the new node as the successor of the last node
        temp->next = new_node;
    }
}

//---------------------------------------------
// print_the_list():
// O(n_of_element_in_the_list)
// print the whole content of the global list
//---------------------------------------------
void print_the_list(){
    printf("\nThe Library data is as follows: \n\n");
    Node* temp = head;
    while (temp != NULL) {
        printf("%s\n%s\n\n", temp->name,temp->author);
        temp = temp->next;
    }
}

//---------------------------------------------
// sort():
// O(n_of_element_in_the_list^2)
// sort the whole list by name in Ascending Order
//---------------------------------------------
void bsort(){ //Bubble Sort Algorithm to arrange Library data in Ascending Order
    char *swap_ptr_name, *swap_ptr_author;
    // for each node of the list
    for (Node* current_minimum = head; current_minimum != NULL; current_minimum = current_minimum->next) {
        // for each node after the current_minimum
        for (Node* current_node = current_minimum->next; current_node != NULL;  current_node = current_node->next) {
            // if the current_node is less than the current_minimum swap them
            if (strcmp(current_node->name,current_minimum->name) < 0) {
                // Save the name and author of the current_minimum
                swap_ptr_name   = current_minimum->name;
                swap_ptr_author = current_minimum->author;

                // Place the current node as the minimum
                current_minimum->name   = current_node->name;
                current_minimum->author = current_node->author;

                // Place the old minimum in the place of the current_node
                current_node->name   = swap_ptr_name;
                current_node->author = swap_ptr_author;
            }
        }
    }
}

补充说明

代码格式化

我建议您阅读一些代码风格指南 (GNU,Google)，因为在 C 语言中，如果您不够精确，代码很快就会变得不可读。

开始我认为最好的办法是习惯使用：

#define 定义
typedef 定义新的变量类型，这样你就不必每次都编写结构
评论很多代码。

编辑

抱歉，我实现的算法不是冒泡排序

实际的冒泡排序实现是这样的：

//---------------------------------------------
// sort():
// O(n_of_element_in_the_list^2)
// sort the whole list by name in Ascending Order
//---------------------------------------------
void bsort(){ //Bubble Sort Algorithm to arrange Library data in Ascending Order

    // If he list is empty then is already sorted
    if(head == NULL)
        return;

    // Temp pointers to swap two nodes.
    char *swap_ptr_name, *swap_ptr_author;
    // Variable that keep track if at least one swap was made in the for.
    int swapped;


    Node* next_node;
    do{
        // Reset the flag
        swapped = 0;
        // for each node in the list except the last one
        for (Node* current_node = head; current_node->next != NULL;  current_node = current_node->next) {
            // Set the next node 
            next_node = current_node->next;
            // if the current_node is bigger than the next_node swap them
            if (strcmp(current_node->name,next_node->name) > 0) {
                // Save the name and author of the current_minimum
                swap_ptr_name   = next_node->name;
                swap_ptr_author = next_node->author;

                // Place the current node as the minimum
                next_node->name   = current_node->name;
                next_node->author = current_node->author;

                // Place the old minimum in the place of the current_node
                current_node->name   = swap_ptr_name;
                current_node->author = swap_ptr_author;

                // We swapped two nodes so the flag is setted
                swapped = 1;
            }
        }
    }while(swapped == 1);
}

补充说明 Pt.2

有一种方法可以在没有交换指针的情况下交换变量，但它的可读性较差。 XOR Swap

在这种情况下，它看起来像这样。

// X := X XOR Y
current_node->name   ^= next_node->name;
current_node->author ^= next_node->author;

// Y := Y XOR X
next_node->name   ^= current_node->name;
next_node->author ^= current_node->author;

// X := X XOR Y
current_node->name   ^= next_node->name;
current_node->author ^= next_node->author;

无法在C中按升序对链表进行排序

Unable to sort linked list in ascending order in C

c

sorting

linked-list

bubble-sort