程序員考試補課筆記-2

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

發(fā)表于：2023-05-26來源：：點擊數(shù)：標簽：

今天續(xù)著上堂的查找一章，上回已經(jīng)講了順序查找和二分查找，這兩個都是經(jīng)常用到的。還有一種是特別的查找方法就是散列表（這里說明一下，這個查找方法是有幾種不同的名字的，雜湊表和哈希表）。因為這個可能講起來會用很多時間，老師也沒有細詳?shù)慕庹f，只是

今天續(xù)著上堂的查找一章，上回已經(jīng)講了順序查找和二分查找，這兩個都是經(jīng)常用到的。還有一種是特別的查找方法就是散列表（這里說明一下，這個查找方法是有幾種不同的名字的，雜湊表和哈希表）。因為這個可能講起來會用很多時間，老師也沒有細詳?shù)慕庹f，只是舉了一個相對的思想出來，如下：

Rikeyi

a(0)=20

a(1)=30

a(2)=40

a(3)=50addr(Ri)=H(keyi)

Ri=keyi/10-2這個關(guān)系

就是這樣，它對不同的問題當然有不同的關(guān)系，只能只要知道這個思想就好了。教程里的查找也就是這三種了，現(xiàn)在開始講排序了。排序相對查找來說多了很多的方法，我們之前也碰過好幾種排序的方法了，就是前一章的二叉樹排序就是了，還有很早之前講過的冒泡排序，我想很多人都應(yīng)該知道這個經(jīng)典的排序了吧。現(xiàn)在下來要講的是直接插入排序法，這種方法的優(yōu)勢在于已經(jīng)排好序的結(jié)點插入一個新的結(jié)點，有順序的這樣就可以用到上章學(xué)過的折半查找就可以找到該插入的位置了。其實給出一個沒有序的一排數(shù)組，可以把它劃分為兩大部份，一部份是已排好序的結(jié)點，而另一部分則是待插入的結(jié)點，這樣就可以模擬這個算法了，看看第十五天圖一

這里可以清楚看到整個的思路是如何的。下面我們就要用C語言來到描述這個排序算法了，一共有好種種版本，大家一個一個的對比看看，看誰的效率高。

inta[10]={8,7,10,30,5,1,7,10,0,25};

inti,j,k;

for(i=1;in;i++)

{

for(t=e[i],j=i-1;j=0te[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;in;i++)

{

k=a[i];

for(j=i-1;j=0;j--)

if(ka[j])break;

elsea[j+1]=a[j];

a[j+1]=k;

}

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

前一些定義之類的略

p=h-next;h-next=NULL;

while(p)

{

if(p-datah-data)

{

q=p-next;

p-next=h;

h=p;p=q;

}

else

{

q=h;r=q-next;

while(rp-datar-data)

{

q=r;r=r-next;

}

q-next=p;p=p-next;

q-next-next=r;

}