C中的链表排序

我正在为我的一个类编写一个简单的文件，这是一个简单的链表活动，我需要对链表进行排序。

到目前为止这是我的源代码：

/* * Simple list manipulation exercise. * 1. Create a list of integers. * 2. Print the list. * 3. Sort the list. * 4. Print the list * 5. Free the list nodes. */ #include  #include  struct node { int value ; struct node *next ; } ; extern struct node *mk_node(int v) ; extern void print_list(struct node *head) ; extern struct node *sort_list(struct node *head) ; extern void free_list(struct node *head) ; #define NVALUES (6) int initial_contents[] = { 3, 8, 2, 5, 1, 9 } ; /* * Main driver program. Create the list from the initial_contents, * print it, sort it, print it, free it, and return. */ int main() { struct node *head = NULL ; struct node *curp ; int i ; /* * Put the initial values into the list. This algorithm * will result in the values being inserted in reverse * order of the array. */ for( i = 0 ; i next = head ; head = curp ; } print_list(head) ; head = sort_list(head) ; print_list(head) ; free_list(head) ; return 0 ; } /* * Return a new node with 'v' as the label and a NULL next link. */ struct node *mk_node(int v) { struct node *newp = malloc( sizeof(struct node) ) ; newp->value = v; newp->next = NULL; return newp ; // Place holder } /* * Print the list headed by 'head', one value per line. */ void print_list(struct node *head) { printf("List: "); struct node *ptr = head; while(ptr!=NULL){ printf("%d ", ptr->value); ptr=ptr->next; } putchar('\n'); } /* * Sort the list headed by 'head', returning a pointer to the node * that ends up at the head of the list. */ struct node *sort_list(struct node *head) { struct node *tmpPtr; struct node *tmpNxt; tmpPtr = head; tmpNxt = head->next; int a, tmp; while(tmpNxt != NULL){ a = tmpPtr->value; while(tmpNxt != tmpPtr && tmpNxt->value value = tmpNxt->value; tmpNxt->value = tmp; tmpPtr = tmpPtr->next; } tmpPtr = head; tmpNxt = tmpNxt->next; } return tmpPtr ; // Place holder } /* * Free all the nodes in the list headed by 'head'. */ void free_list(struct node *head) { //struct node *releasep ; //while( head != NULL ){ // releasep = head; // head = head->next ; // // free(releasep->value) ; // free(releasep) ; // } } 

我的排序方法遇到了麻烦。 我甚至一步一步走，我找不到问题。

以下是我的程序输出。

 XXXXXXX@linus:~/350/c_memory_activity$ gcc -o test listsort.c XXXXXXX@linus:~/350/c_memory_activity$ ./test List: 9 1 5 2 8 3 List: 1 9 5 2 8 3 XXXXXXX@linus:~/350/c_memory_activity$ 

PS：原始排序算法在这里： 链接列表插入排序

Answer 1

好吧，这个循环只会去一次（在好的情况下）：

  while(tmpNxt != tmpPtr && tmpNxt->value < a){ tmp = a; tmpPtr->value = tmpNxt->value; tmpNxt->value = tmp; tmpPtr = tmpPtr->next; } 

既然它是作业，只是一个提示：这是tmpNxt，第一次迭代后是tmpPtr？

另一条要看的是那些：

 tmpPtr = head; tmpNxt = tmpNxt->next; 

这两个例子都解释了为什么在你的例子中只替换了前两个元素。

Answer 2

MByD已经指出了这个问题（我为你推荐，MByD），所以我想提出一些建议。

排序是计算机科学史上已经解决过的问题之一。 有一篇优秀的维基百科文章，其中包含大量排序算法的索引和比较。 选择一些，了解它们的工作原理！ 逆向工程（种类）算法是提高自身技能的好方法。

尝试例如冒泡排序，插入排序和快速排序。

干杯!

Answer 3

经过与朋友的一些堆栈追踪后，我想出来了。 inheritance人固定代码：

 struct node *sort_list(struct node *head) { struct node *tmpPtr = head; struct node *tmpNxt = head->next; int tmp; while(tmpNxt != NULL){ while(tmpNxt != tmpPtr){ if(tmpNxt->value < tmpPtr->value){ tmp = tmpPtr->value; tmpPtr->value = tmpNxt->value; tmpNxt->value = tmp; } tmpPtr = tmpPtr->next; } tmpPtr = head; tmpNxt = tmpNxt->next; } return tmpPtr ; // Place holder } 

Answer 4

这是我使用快速排序算法排序的链接列表版本。 检查这是否有帮助..

 #include "stdafx.h" #include "malloc.h" typedef struct node { struct node *next; int val; } node; bool insert_node(struct node **head, int val) { struct node *elem; elem = (struct node *)malloc(sizeof(struct node)); if (!elem) return false; elem->val = val; elem->next = *head; *head = elem; return true; } int get_lval(struct node *head, int l) { while(head && l) { head = head->next; l--; } if (head != NULL) return head->val; else return -1; } void swap(struct node *head, int i, int j) { struct node *tmp = head; int tmpival; int tmpjval; int ti = i; while(tmp && i) { i--; tmp = tmp->next; } tmpival = tmp->val; tmp = head; while(tmp && j) { j--; tmp = tmp->next; } tmpjval = tmp->val; tmp->val = tmpival; tmp = head; i = ti; while(tmp && i) { i--; tmp = tmp->next; } tmp->val = tmpjval; } struct node *Quick_Sort_List(struct node *head, int l, int r) { int i, j; int jval; int pivot; i = l + 1; if (l + 1 < r) { pivot = get_lval(head, l); printf("Pivot = %d\n", pivot); for (j = l + 1; j <= r; j++) { jval = get_lval(head, j); if (jval < pivot && jval != -1) { swap(head, i, j); i++; } } swap(head, i - 1, l); Quick_Sort_List(head, l, i); Quick_Sort_List(head, i, r); } return head; } struct node *Sort_linkedlist(struct node *head) { struct node *tmp = head; // Using Quick sort. int n = 0; while (tmp) { n++; tmp = tmp->next; } printf("n = %d\n", n); head = Quick_Sort_List(head, 0, n); return head; } void print_list(struct node *head) { while(head) { printf("%d->", head->val); head = head->next; } printf("\n"); } int _tmain(int argc, _TCHAR* argv[]) { struct node *head = NULL; struct node *shead = NULL; insert_node(&head, 10); insert_node(&head, 12); insert_node(&head, 9); insert_node(&head, 11); insert_node(&head, 7); insert_node(&head, 1); insert_node(&head, 3); insert_node(&head, 8); insert_node(&head, 5); insert_node(&head, 2); insert_node(&head, 4); insert_node(&head, 6); print_list(head); shead = Sort_linkedlist(head); print_list(shead); return 0; } 

Answer 5

而不是复制其他已知问题的代码，我建议自己创建。 您将学到更多东西，最终可能会减少错误。

也就是说，如果你想知道什么不起作用，那么一旦最小值到达列表的头部，就要跟进一切。 tmpPtr->value将被设置为1，它被分配给a ，最终跳过内部while循环。