气泡在c链表中排序 [英] Bubble sort in c linked list

问题描述

我需要做的是将输入文件读入一个链表中.该文件的一部分是:

I need to do is read in an input file into a linked list. Part of the file is:

NameA，25
名称B，33
名称C，23
名字D，39

NameA, 25
NameB, 33
NameC, 23
NameD, 39

然后我需要按数字排序(冒泡排序)并将其写入另一个文件.

And after i need to sort by the number (bubble sort) and write it to another file.

这是我所拥有的:

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

struct node{
    char name[20];
    int number;
    struct node *next;
    struct node *prev;
}*head;

int main(void) {

    struct node *temp;
    temp = malloc(sizeof(struct node));
    temp->next = NULL;
    head = temp;

    FILE *ifp;
    char fnamer[100] = "";
    char line[128];
//    printf("\n\nPlease Enter the Full Path of the file: \n");
//    scanf("%s",&fnamer);

    ifp = fopen("mintaadatok.txt", "r");
    if (ifp == NULL) {
        printf("\n%s\" File NOT FOUND!", fnamer);
        exit(1);
    }

    int c = 0;

    char buffer[1024];
    memset(buffer, 0, 1024);
    while (c < 15) {
        fgets(buffer, 1024, ifp);
        sscanf(buffer, "%19[^,], %d", temp->name, &temp->number);
        printf("%d %s %d\n", c, temp->name, temp->number);
        temp->next = malloc(sizeof(struct node));
        temp = temp->next;
        temp->next = NULL;
        c++;
    }

    int i,step;
    for (temp = head; temp; temp = temp->next) {
        printf("%s", temp->name);
        printf("%d\n", temp->number);
        for(step=0;step<10-1;++step)
            for(i=0;i<10-step-1;++i)
            {
                temp->next = malloc(sizeof(struct node));
                if(temp->number>temp->next)
                {
                    temp=temp->number;
                    temp->number=temp->next;
                    temp->next=temp;
                }
            }
    }
    printf("In ascending order: ");
}

您能帮我对这些数据进行排序吗?

Can you help me to sort these data?

推荐答案

while(c<10)
{
    fgets(buffer, 1024, ifp);
    sscanf(buffer, "%19[^,], %d", temp->name, &temp->id);
    ...
}

该文件似乎有4个条目，而不是10个.一种更好的读取文件的方法是使用while(fgets(buffer, 1024, ifp)){...}，当没有更多行要读取时，它将停止.这里没有关系，因为一旦退出main就会释放内存，但是在实际的应用程序中，您需要以不同的功能运行代码，并且必须释放内存.

The file appears to have 4 entries, not 10. A better way to read the file is using while(fgets(buffer, 1024, ifp)){...} This will stop when there are no more lines to be read. It doesn't matter here because the memory is freed as soon as you exit main but in a practical application you run the code in different functions and you have to free the memory.

链接列表并不完全正确，因为您要呼叫额外的malloc，因此无法释放此内存.

The linked list is not entirely correct because you are calling an extra malloc, this memory cannot be freed.

使用冒泡排序对链接列表进行排序并非易事.更好的方法是使用realloc将文件读入node数组.然后在数组上使用冒泡排序.或者，您可以将链接列表转换为数组(毫无意义！)

Sorting a linked list using bubble sort is not trivial. A better way is to read the file in to an array of node, using realloc. Then use bubble sort on the array. Alternatively, you can convert the linked-list to an array (pointless!)

否则，要对链接列表使用冒泡排序，可以使两个循环遍历列表，然后比较并更改每个节点的值.

Otherwise, to use bubble sort on linked list you can make two loops to walk the list, then compare and change the values of each node.

下面的示例将条目插入列表的开头(由于对列表进行了排序，所以没有关系)并运行冒泡排序:

The example below inserts the entries at the head of the list (it doesn't matter since the list is being sorted) and runs bubble sort:

struct node 
{
    char name[20];
    int id;
    struct node *next;
}*head;

int main(void) 
{
    FILE *ifp = fopen("mintaadatok.txt", "r");
    if (!ifp)
    {
        printf("file error\n");
        return 0;
    }

    char buffer[1024];
    memset(buffer, 0, 1024);
    while(fgets(buffer, 1024, ifp))
    {
        struct node *temp = malloc(sizeof(struct node));
        temp->next = NULL;

        if(sscanf(buffer, "%19[^,], %d", temp->name, &temp->id) != 2)
        {
            free(temp);
            break;
        }

        if(!head)
        {
            head = temp;
        }
        else
        {
            temp->next = head;
            head = temp;
        }
    }

    //bubble sort here:
    struct node *loop1 = head;
    while(loop1)
    {
        int swapped = 0;
        struct node *loop2 = loop1->next;
        while(loop2)
        {
            if(loop1->id > loop2->id)
            {
                //swap the values for `name` and `id`
                //but don't change the `next` pointers
                char name[20];
                strcpy(name, loop1->name);
                strcpy(loop1->name, loop2->name);
                strcpy(loop2->name, name);

                int id = loop1->id;
                loop1->id = loop2->id;
                loop2->id = id;
                swapped = 1;
            }

            loop2 = loop2->next;
        }

        //if there were no swaps then list is already sorted
        if (!swapped)
            break;

        loop1 = loop1->next;
    }

    //print the list:
    loop1 = head;
    while(loop1)
    {
        printf("%s %d\n", loop1->name, loop1->id);
        loop1 = loop1->next;
    }

    return 0;
}

这篇关于气泡在c链表中排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！