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:

姓名A，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("

Please Enter the Full Path of the file: 
");
//    scanf("%s",&fnamer);

    ifp = fopen("mintaadatok.txt", "r");
    if (ifp == NULL) {
        printf("
%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
", 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
", 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?

推荐答案

我们初学者应该互相帮助.:)

We beginners should help each other.:)

我没有查看你所有的代码.然而，这显然是不正确的，例如由于此循环中节点的分配顺序不正确

I did not look through all your code. However it is obviously incorrect for example due to the incorrect order of allocations of nodes in this loop

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

所以最后一个节点将具有除数据成员next之外的不确定值的数据成员.

So the last node will have data members with indeterminate values except the data member next.

我正在尝试回答您的问题如何为单向链表编写冒泡排序函数.

I am trying to answer your question how to write a bubble sort function for a singly-linked list.

为单向链表编写冒泡排序函数对于你我这样的初学者来说并不是一件容易的事.例如，您需要为列表的节点正确编写交换函数.

To write a bubble sort function for a singly-linked list is not an easy task for such beginners as you and me. For example you need to write correctly a swap function for nodes of the list.

给你.

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

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

int push_back( struct node **head, const char *name, int id )
{
    struct node *tmp = malloc( sizeof( struct node ) );
    int success = tmp != NULL;

    if ( success )
    {
        while ( *head != NULL ) head = &( *head )->next;

        strcpy( tmp->name, name );
        tmp->id = id;
        tmp->next = NULL;

        *head = tmp;
    }

    return success;
}

void display( struct node **head )
{
    for ( struct node *current = *head; current != NULL; current = current->next )
    {
        printf( "{ %s, %d } ", current->name, current->id );
    }
}

void swap( struct node **current )
{
    struct node *tmp = ( *current )->next->next;
    ( *current )->next->next = *current;
    *current = ( *current )->next;
    ( *current )->next->next = tmp;
}


void bubble_sort( struct node **head, int cmp( const void *, const void * ) )
{
    if ( *head != NULL )
    {
        for ( struct node *last = NULL, *swapped = NULL; ( *head )->next != last; last = swapped )
        {
            swapped = ( *head )->next;

            for ( struct node **first = head; ( *first )->next != last; first = &( *first )->next )
            {
                if ( cmp( ( *first )->next, *first ) < 0 )
                {
                    swap( first );
                    swapped = ( *first )->next;
                }
            }
        }
    }
}

int cmp_id( const void *a, const void *b )
{
    const struct node *left  = a;
    const struct node *right = b;

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

int cmp_name( const void *a, const void *b )
{
    const struct node *left  = a;
    const struct node *right = b;

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

int main(void) 
{
    struct node *head = NULL;

    push_back( &head, "NameA", 25 );
    push_back( &head, "NameB", 33 );
    push_back( &head, "NameC", 23 );
    push_back( &head, "NameD", 39 );    

    display( &head );
    putchar( '
' );

    bubble_sort( &head, cmp_id );

    display( &head );
    putchar( '
' );

    bubble_sort( &head, cmp_name );

    display( &head );
    putchar( '
' );

    return 0;
}

程序输出为

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

在演示程序中，列表首先按 ID 排序，然后按名称排序.

In the demonstrative program at first the list is sorted by IDs and then by names.

因此，您现在需要的只是根据使用过的文件中的数据正确构建列表.

Thus all you need now is to build correctly the list from data in the used file.

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