程序員考試補課筆記-第十五天

　　今天續著上堂的查找一章，上回已經講了順序查找和二分查找，這兩個都是經常用到的。還有一種是特別的查找方法就是散列表（這里說明一下，這個查找方法是有幾種不同的名字的，雜湊表和哈希表）。因為這個可能講起來會用很多時間，老師也沒有細詳的解說，只是舉了一個相對的思想出來，如下：
　　Ri　　 keyi
　a(0)　=　20
　a(1)　=　30
　a(2)　=　40
　a(3)　=　50　　　　addr(Ri)=H(keyi)
　　　　　　　　　　　Ri=keyi/10-2　這個關系

　　就是這樣，它對不同的問題當然有不同的關系，只能只要知道這個思想就好了。教程里的查找也就是這三種了，現在開始講排序了。排序相對查找來說多了很多的方法，我們之前也碰過好幾種排序的方法了，就是前一章的二叉樹排序就是了，還有很早之前講過的冒泡排序，我想很多人都應該知道這個經典的排序了吧?，F在下來要講的是直接插入排序法，這種方法的優勢在于已經排好序的結點插入一個新的結點，有順序的這樣就可以用到上章學過的折半查找就可以找到該插入的位置了。其實給出一個沒有序的一排數組，可以把它劃分為兩大部份，一部份是已排好序的結點，而另一部分則是待插入的結點，這樣就可以模擬這個算法了，看看第十五天圖一
這里可以清楚看到整個的思路是如何的。下面我們就要用C語言來到描述這個排序算法了，一共有好種種版本，大家一個一個的對比看看，看誰的效率高。
　　int a[10]={8,7,10,30,5,1,7,10,0,25};
　　int i,j,k;
　　for(i=1;i<n;i++)
　　{
　　　　for(t=e[i],j=i-1;j>=0 && t<e[j];j--)
　　　　　　e[j+1]=e[j];
　　　　e[j+1]=t;
　　}

另一個

　　for(i=1;i<=9;i++)
　　　　for(j=0;j<=i-1;j++)
　　　　{
　　　　　　if(a[j]>a[i])
　　　　　　{
　　　　　　　　t=a[j];
　　　　　　　　a[j]=a[i];
　　　　　　　　a[i]=t;
　　　　　　}
　　　　}

再另一個

　　for(i=1;i<n;i++)
　　{
　　　　k=a[i];
　　　　for(j=i-1;j>=0;j--)
　　　　　　if(k>a[j]) break;
　　　　　　else a[j+1]=a[j];
　　　　a[j+1]=k;
　　}

　　以前三個程序請大家自己分析，一定要自己動過腦去想。好了，難題終于又是到最后出來了，就是把這個排序的算法變為鏈表形式的，大家有沒有想到呢？我們都急著筆去試了，可是最后還是不行，如果對于至前沒有接觸過這類型的是正常的情況，所有我們都沒有做出來。下面看看老師寫的程序好了：

前一些定義之類的略
　　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;
　　　　}
　　}

　　今天我有些失落，可能是因為做題的事吧，反正整個人都不知道怎么的，不過我還是會堅持，我會繼續加把勁，希望大家可以和我一齊努力吧！

原文轉自：http://www.kjueaiud.com