程序员考试补课笔记-第十六天.docxVIP

程序员考试补课笔记-第十六天 p=h-next;h-next=NULL;　　while(p)　　{　　　　if(p-datadata)　　　　{　　　　　　q=p-next;　　　　　　p-next=h;　　　　　　h=p;p=q;　　　　}　　　　else　　　　{　　　　　　q=h;r=q-next;　　　　　　while(r r=r-next;　　　　　　}　　　　　　q-next=p;p=p-next;　　　　　　q-next-next=r;　　　　}　　}　　根据这条程序的思路让我们来想想整个的过程，这个程序分了两部份，一局部就是假如当前待排序的结点值是小于头的结点值就直接把它插到第一个里，由于假如比照头的那个已经小于它了，所以后面的都不要比拟了。假如待插入排序的结点值不是小于当前头结点的话，那么就应当要找到适宜的位置才可以插入该结点了，我们来看q和r指针是用来做什么来的，它指向头指针h和r指向q指针的一下个结点，由于我们知道单向链表的缺点是不能知道它前面的结点是什么，所以一断开就可能会导至链表失败。我们的目的就是用q来保存它的前一个结点。在while循环里就是有两种可能，一种是r为空，这里r为空时就是说明白这个链表已经比到最终一个了，所以直接把待插入的结点插在后面就行了。至于p-datar-data是要等p-data比r-data小时就说明已经找到该插入的位置里，我们就可以连续往下进展插入的步骤。while里面的是假如这两个条件都是真的时候说明还没有找到，那么就让两个双链指针往后移一个连续比拟，等找到符合了就可以插入了。假如还是比拟模糊的话大家不要紧，再看看下面这条程序：struct node *li_sort(struct node *h){　　struct node *t,*s,*u,*v;　　s=h-next;　　h-next=NULL;　　while(s!=NULL)　　{　　　　for(t=s,v=h;v!=NULL u=v,v=v-next);　　　　　　s=s-next;　　　　if(v==h) h=t;　　　　else u-next=t;　　　　t-next=v;　　}}　　我们可以看出这个程序很像上面的，但它更简化了，把整个推断都在一个for语句里了。我们渐渐来分析一下这个程序，信任只有去想的话大家应当都会明白的了。S=h-next 和h-next=NULL这两句都是同上一样，把他们分开成已排序部份和待排序部份。跟着主要的是要看看for语句里的，由于全部推断条件都在这里了。这里t是临时变量代s的，s的角色就是当前要插入的那个结点，v和u指针都和上面一程序的q和r是一样的，都是用来补缺单向链表的缺点。这里的条件也是一样，和上面程序的分别就是它整合了两种状况的可能性在，跟着下面的程序又作了一个条件来分别这是插入头的还是中间的。好了，还是一句要自己的脑根去想，这里第十六天图一里有整个的过程。