c链表中的冒泡排序

我需要做的是将输入文件读入链表。 部分文件是：

NameA，25
NameB，33
NameC，23
姓名D，39

之后我需要按数字排序（冒泡排序）并将其写入另一个文件。

这是我有的：

#include  #include  #include  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 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;inext = malloc(sizeof(struct node)); if(temp->number>temp->next) { temp=temp->number; temp->number=temp->next; temp->next=temp; } } } printf("In ascending order: "); } 

你能帮我分类这些数据吗？

Answer 1

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

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

链表不完全正确，因为您正在调用额外的malloc ，此内存无法释放。

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

否则，要在链表上使用冒泡排序，您可以制作两个循环来遍历列表，然后比较和更改每个节点的值。

下面的示例将列表插入到列表的开头（由于列表正在排序，因此无关紧要）并运行冒泡排序：

 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; } 

Answer 2

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

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

 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++; } 

因此，最后一个节点将使数据成员具有不确定的值，除了next的数据成员。

我试图回答你的问题如何为单链表编写一个冒泡排序函数 。

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

这个给你。

 #include  #include  #include  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( '\n' ); bubble_sort( &head, cmp_id ); display( &head ); putchar( '\n' ); bubble_sort( &head, cmp_name ); display( &head ); putchar( '\n' ); 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排序，然后按名称排序。

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

Answer 3

对于对链表进行冒泡排序，首先需要一个头指针然后另外两个指针，实现将与冒泡排序相同但略有不同，因为链接列表元素无法通过索引直接访问，您必须使用以下两个指针用于比较值，就像对冒泡排序中的数组一样。

  pptr=head; //for the previou element ptr=head->next;//for the next element if(pptr->value > ptr->value) //comparing the value in linked list 

别忘了增加两个指针。