今天繼續是鏈表方式的排序，前天的一題大家有沒有弄懂了。弄不懂不要緊，這是要慢慢來的，急不來。
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.kjueaiud.com/
