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

今天继续是链表方式的排序，前天的一题大家有没有弄懂了。弄不懂不要紧，这是要慢慢来的，急不来。
p=h->next;h->next=NULL;
　　while(p)
　　{
　　　　if(p->data<h->data)
　　　　{
　　　　　　q=p->next;
　　　　　　p->next=h;
　　　　　　h=p;p=q;
　　　　}
　　　　else
　　　　{
　　　　　　q=h;r=q->next;
　　　　　　while(r && p->data > r->data)
　　　　　　{
　　　　　　　　q=r;r=r->next;
　　　　　　}
　　　　　　q->next=p;p=p->next;
　　　　　　q->next->next=r;
　　　　}
　　}
　　按照这条程序的思路让我们来想想整个的过程，这个程序分了两部份，一部分就是如果当前待排序的结点值是小于头的结点值就直接把它插到第一个里，因为如果对比头的那个已经小于它了，所以后面的都不要比较了。如果待插入排序的结点值不是小于当前头结点的话，那么就应该要找到合适的位置才可以插入该结点了，我们来看q和r指针是用来做什么来的，它指向头指针h和r指向q指针的一下个结点，因为我们知道单向链表的缺点是不能知道它前面的结点是什么，所以一断开就可能会导至链表失败。我们的目的就是用q来保存它的前一个结点。在while循环里就是有两种可能，一种是r为空，这里r为空时就是说明了这个链表已经比到最后一个了，所以直接把待插入的结点插在后面就行了。至于p->data>r->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 && v->data < t->data; 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是一样的，都是用来补缺单向链表的缺点。这里的条件也是一样，和上面程序的分别就是它整合了两种情况的可能性在，跟着下面的程序又作了一个条件来分别这是插入头的还是中间的。好了，还是一句要自己的脑根去想，这里第十六天图一里有整个的过程。
　　说完了单向链表的当然就是要讲讲双向链表了，因为双向链表可以往前移的关系，所以程序也比较好办，不过麻烦的就是它的插入和删除操作，也当再一次练习链表操作的机会吧。大家先自己想想，再试着写出程序来，有了上面单向链表的基础应该也很容易可以跟着思路编出。大家把编好的程序发到http://zhgpa.vicp.net/bbs 程序员考试那版里，看看大家的方法有何不同一齐讨论。大家先不要看我下面的程序：
一些定义略
while(p)
{
　　for(q=p->pre,r=p;q && p->data < q->data; q=q->pre);
　　p=p->next;
　　r->pre->next=p;
　　if (p) p->pre=r->pre;
　　if(q)
　　{
　　　　p->next=q->next;
　　　　if(q->next) q->next->pre=p;
　　　　p->pre=q;
　　　　q->next=p;
　　}
　　else
　　{
　　　　r->next=h;
　　　　r->pre=NULL;
　　　　h->pre=r;
　　}
}
　　好了，大家的程序又是如何呢？希望大家多多讨论。这几天虽然学的内容不算多，但是就从中吸受到很多经验，现在链表的操作又更一步的前进了。懂得了分析程序的一些方法，编程这条路看起来真的很漫长，我在这条路里我什么都不懂，可是我会坚持。

原文转自：http://www.ltesting.net