这种排序方法如何工作？(How does this sorting method work?)

我正在从“The C Book”学习C语言。我认为这是一本好书，我理解它的大部分内容，比如指针。但我无法理解使用链表结构排序的一个例子。

如果我在纸上画它，我会继续得到第二个对象的指针如果被切换则不会调整到第一个。也许我正在以错误的方式思考结构中的这些指针。有人可以非常简短地解释这个交换，可能就像我在5,99和1的代码中所做的那样。我想了解这种带链表的排序，因为它似乎对后来非常有用。

这是代码：#include #include

struct list_ele{ int data; struct list_ele *pointer; }ar[3]; struct list_ele * sortfun( struct list_ele *list ); int main(){ struct list_ele *lp; ar[0].data = 5; ar[0].pointer = &ar[1]; ar[1].data = 99; ar[1].pointer = &ar[2]; ar[2].data = 1; ar[2].pointer = 0;/* mark end of list */ /* sort list */ lp = sortfun(ar); /* follow pointers */ while(lp){ printf("contents %d\n", lp->data); lp = lp->pointer; } exit(EXIT_SUCCESS); } struct list_ele * sortfun( struct list_ele *list ) { int exchange; struct list_ele *nextp, *thisp, dummy; /* * Algorithm is this: * Repeatedly scan list. * If two list items are out of order, * link them in the other way round. * Stop if a full pass is made and no * exchanges are required. * The whole business is confused by * working one element behind the * first one of interest. * This is because of the simple mechanics of * linking and unlinking elements. */ dummy.pointer = list; do{ exchange = 0; thisp = &dummy; while( (nextp = thisp->pointer) && nextp->pointer) { if(nextp->data > nextp->pointer->data){ /* exchange */ exchange = 1; thisp->pointer = nextp->pointer; nextp->pointer = this->pointer->pointer; thisp->pointer = nextp; } thisp = thisp->pointer; } }while(exchange); return(dummy.pointer); }

I'm learning C from "The C Book". I think it's a good book and I understand most of it, like pointers. But I can't get my head around 1 example of sorting with linked list structures.

If I draw it on paper, I keep getting that the pointers of the second object aren't adjusted to the first if they are switched. Maybe I'm thinking in a wrong way about these pointers in the structures. Can somebody explain this exchange very short, maybe by example like I made in the code with 5, 99 and 1. I'd like to understand this kind of sorting with linked list because it seems pretty useful for later.

This is the code: #include #include

struct list_ele{ int data; struct list_ele *pointer; }ar[3]; struct list_ele * sortfun( struct list_ele *list ); int main(){ struct list_ele *lp; ar[0].data = 5; ar[0].pointer = &ar[1]; ar[1].data = 99; ar[1].pointer = &ar[2]; ar[2].data = 1; ar[2].pointer = 0;/* mark end of list */ /* sort list */ lp = sortfun(ar); /* follow pointers */ while(lp){ printf("contents %d\n", lp->data); lp = lp->pointer; } exit(EXIT_SUCCESS); } struct list_ele * sortfun( struct list_ele *list ) { int exchange; struct list_ele *nextp, *thisp, dummy; /* * Algorithm is this: * Repeatedly scan list. * If two list items are out of order, * link them in the other way round. * Stop if a full pass is made and no * exchanges are required. * The whole business is confused by * working one element behind the * first one of interest. * This is because of the simple mechanics of * linking and unlinking elements. */ dummy.pointer = list; do{ exchange = 0; thisp = &dummy; while( (nextp = thisp->pointer) && nextp->pointer) { if(nextp->data > nextp->pointer->data){ /* exchange */ exchange = 1; thisp->pointer = nextp->pointer; nextp->pointer = this->pointer->pointer; thisp->pointer = nextp; } thisp = thisp->pointer; } }while(exchange); return(dummy.pointer); }

最满意答案

这是泡沫排序。它通过不按顺序交换项目来工作，重复直到没有更多的项目乱序。如果没有那么多项目会很有帮助，否则需要一些其他方法。技巧部分可能是这样的：

thisp->pointer = nextp->pointer; nextp->pointer = this->pointer->pointer; thisp->pointer = nextp;

这意味着交换链表中两个元素的顺序。

This is bubble sort. It works by exchanging items out of order, repeating until there is no more items out of order. It is helpful if there is not so much items, otherwise some other methods are required. The tricki part is probably this:

thisp->pointer = nextp->pointer; nextp->pointer = this->pointer->pointer; thisp->pointer = nextp;

that is meant to swap the order of two element in the linked list.

更多推荐