[请教]Robert Sedgewick那本书里面一个链表插入排序算法

imonyse

这段代码从0-999中抽取N个随机的整数，构造一个带表头节点的链表（第一个for循环），每个数字存放在一个节点里。
然后遍历链表（第二个for循环），按照存放的数字的大小，对节点排序。（例子里应该是从小到大的顺序）

在这里，构造了2个带表头节点的链表，一个是输入（无序），一个是输出（排序之后）。循环的每一次变换，就是从输入链表取出一个节点(删除），然后把它有序的插入输出链表。
觉得我的描述可能有出入的，可以看下面主程序区的原文注释部分。

代码使用下列声明:

1. 
   
2. typedef struct node* link;
   
3. struct node {int item; link next};
   

复制代码

接下来是主代码

1. 
   
2. /* Program 3.II List insertion sort
   
3. * This code generate N random integers between 0 and 999,
   
4. * builds a linked list with one number per node(first for loop),
   
5. * and then rearranges the nodes so that the numbers appear in order
   
6. * when we traverse the list(second for loop).
   
7. * To accomplish the sort, we maintain two lists, an input(unsorted) list
   
8. * and an output(sorted) list. On each iteration of the loop,
   
9. * we remove a node from the input and insert it into position in the output.
   
10. */
    
11. 
    
12. struct node heada, headb;
    
13. link t,u,x,a=&heada,b;
    
14. 
    
15. for (i=0,t=a;i<N;i++)
    
16.         {
    
17.          t->next=malloc(sizeof *t);
    
18.          t=t->next; t->next=NULL;
    
19.          t->item=rand() % 1000;
    
20.         }
    
21. 
    
22. b=&headb; b->next=NULL;
    
23. for (t=a->next;t!=NULL;t=u)
    
24.         {
    
25.          u=t->next;
    
26.          for (x=b;x->next!=NULL;x=x->next)
    
27.                 if (x->next->item > t->item) break;
    
28.          t->next=x->next; x->next=t;
    
29.         }
    

复制代码

问题来了，这里似乎并没有在a指向的链表中作删除操作（a->next貌似还是指向---作了插入操作的节点(t)?）

是我理解错了，还是书上描述错了？我想了一个上午，现在头有点昏了。

//编辑一下，操作不会有问题，貌似不作操作也可以。昏死了，感觉应该把“remove”改成“fetch“比较合适吧？

[ 本帖最后由 imonyse 于 2007-5-8 10:59 编辑 ]

ypxing

原帖由 imonyse 于 2007-5-8 10:56 发表
这段代码从0-999中抽取N个随机的整数，构造一个带表头节点的链表（第一个for循环），每个数字存放在一个节点里。
然后遍历链表（第二个for循环），按照存放的数字的大小，对节点排序。（例子里应该是从小到大的顺 ...

把a中的结点移到b中而已
删除是没有必要的,要不然你也得再分配