《算法與數(shù)據(jù)結(jié)構(gòu)(實(shí)踐)》new

PAGEPAGE36遼寧省高等教育自學(xué)考試軟件技術(shù)（應(yīng)用本科）專業(yè)課程設(shè)計(jì)報(bào)告書課程名稱算法與數(shù)據(jù)結(jié)構(gòu)（實(shí)踐）助學(xué)單位信息技術(shù)學(xué)院姓名劉佳旭準(zhǔn)考證號060111300227成績二Ｏ一一年四月實(shí)驗(yàn)1順序表的應(yīng)用實(shí)訓(xùn)目的

1、掌握順序表的定義及操作的C語言實(shí)現(xiàn)方法2、掌握相關(guān)操作的基本思想及其算法。實(shí)驗(yàn)要求1、線性表的基本概念和基本運(yùn)算。2、順序表的存儲結(jié)構(gòu)和查找、插入、刪除等基本運(yùn)算。3、單鏈表的存儲結(jié)構(gòu)以及單鏈表的建立、查找、插入刪除等操作。4、雙向鏈表的存儲結(jié)構(gòu)以及插入、刪除操作。5、靜態(tài)鏈表的存儲結(jié)構(gòu)和基本運(yùn)算。6、利用線性表的基本運(yùn)算解決復(fù)雜問題。實(shí)驗(yàn)步聚1.創(chuàng)建和銷毀順序表存儲結(jié)構(gòu)。創(chuàng)建一個(gè)順序表在順序表的指定位置插入一個(gè)元素；在順序表的指定位置刪除一個(gè)元素；將兩個(gè)有序順序表合并成一個(gè)新的有序順序表-Linearsequenceofstorage,saidtable(structure)andrealizethecreationofachronologicaltable(datafromtheproposed)intheorderoftableelementstoinsertaspecifiedlocationinorderoftableelementstodeleteaspecifiedlocationwillmergetwotablesinanorderlysequenceintoanewtableinanorderlysequence銷毀線性表voidDestroy_SeqList(PSeqListSeqListPoint){/*銷毀順序表，入口參數(shù)：為要銷毀的順序表指針地址，無返回值*/if(SeqListPoint)//SeqListPoint=NULL;return;}設(shè)調(diào)用函數(shù)為主函數(shù)，主函數(shù)對初始化函數(shù)和銷毀函數(shù)的調(diào)用如下：main(){PSeqListSeqListPoint;SeqListPoint=Init_SeqList();……Destroy_SeqList(SeqListPoint);}2.實(shí)現(xiàn)順序表的基本操作，如插入、刪除、查找和遍歷等。具體插入算法描述如下：

InsertList(SeqList*L,inti,DataTypex)

{//在順序表L中第i個(gè)位置之前插入一個(gè)新結(jié)點(diǎn)x

if(i<1||i>L->length+1)

{printf("positionerror");return;}

if(L->length>=ListSize)

{printf("overflow");return;}

for(j=L-length-1;j>=i-1;j--)

L->data[j+1]=L->data[j];

//從最后一個(gè)結(jié)點(diǎn)開始逐一后移

L->data[i-1]=x;//插入新結(jié)點(diǎn)x

L->length++;//實(shí)際表長加1

}從上述的算法以及插入過程圖中可以看出，一般情況下，在第i(1≤i≤n)個(gè)結(jié)點(diǎn)之前插入一個(gè)新結(jié)點(diǎn)時(shí)，需要進(jìn)行n-i+1次移動。而該算法的執(zhí)行時(shí)間花在for循環(huán)的結(jié)點(diǎn)后移上，因此，該算法的時(shí)間復(fù)雜度不僅依賴于表的長度n，而且還與結(jié)點(diǎn)的插入位置i有關(guān)。當(dāng)i=n+1時(shí)，for循環(huán)不執(zhí)行，無需移動結(jié)點(diǎn)，屬于最好情況，其時(shí)間復(fù)雜度為O(1)；當(dāng)i=1，循環(huán)需要執(zhí)行n次，即需要移動表中所有結(jié)點(diǎn)，屬于最壞情況，算法時(shí)間復(fù)雜度為O(n)。由于插入結(jié)點(diǎn)可在表的任何位置上進(jìn)行，因此需要分析討論算法的平均移動次數(shù)。

假設(shè)pi是在第i個(gè)結(jié)點(diǎn)之前插入一個(gè)結(jié)點(diǎn)概率，則在長度為n的線性表中插入一個(gè)結(jié)點(diǎn)時(shí)所需要移動結(jié)點(diǎn)次數(shù)的期望值(平均次數(shù))為:不失一般性，我們假定在線性表的任何位置上插入結(jié)點(diǎn)的機(jī)會是相等的，即是等概率的，則有：

p1=p2=…=pn+1=1/(n+1)

因此，在等概率情況下插入需要移動結(jié)點(diǎn)的平均次數(shù)為：

恰好是表長的一半，當(dāng)表長n較大時(shí)，該算法的效率是相當(dāng)?shù)偷?。因?yàn)镋is(n)是取決于問題規(guī)模n的，它是線性階的，因此算法的平均時(shí)間復(fù)雜度是O(n)。

例如，假定一個(gè)有序表A=(23,31,46,54,58,67,72,88)，表長n=8。當(dāng)向其中插入56時(shí)，此時(shí)的i等于5，因此應(yīng)插入到第i-1個(gè)位置上，從而需要將第i-1個(gè)元素及之后的所有元素都向后移動一位，將第i-1個(gè)元素位置空出來，插入新元素。插入后的有序表為(23,31,46,54,56,58,67,72,88)。按上述移動次數(shù)的計(jì)算公式，可知本插入操作需要移動n-i+1=8-5+1=4次。刪除結(jié)點(diǎn)運(yùn)算的算法如下：

DataTypeDeleteList(SeqList*L,inti)

{//在順序表L中刪除第個(gè)結(jié)點(diǎn)，并返回刪除結(jié)點(diǎn)的值

if(i<1||i>L->length)

{printf("positionerror");

returnError;

}

x=L->data[i];//保存結(jié)點(diǎn)值

for(j=i;j<=L->length;j++)

L->data[j-1]=L->data[j];//結(jié)點(diǎn)前移

L->length--;//表長減1

returnx;

}該算法的時(shí)間復(fù)雜度分析與插入算法類似，刪除一個(gè)結(jié)點(diǎn)也需要移動結(jié)點(diǎn)，移動的次數(shù)取決于表長n和位置i。當(dāng)i=1時(shí)，則前移n-1次，當(dāng)i=n時(shí)不需要移動，因此算法的時(shí)間復(fù)雜度為O(n)；由于算法中刪除第i個(gè)結(jié)點(diǎn)是將從第i+1至第n個(gè)結(jié)點(diǎn)依次向前移動一個(gè)位置，共需要移動n-i個(gè)結(jié)點(diǎn)。同插入類似，假設(shè)在順序表上刪除任何位置上結(jié)點(diǎn)的機(jī)會相等，qi為刪除第i個(gè)結(jié)點(diǎn)的概率，則刪除一個(gè)結(jié)點(diǎn)的平均移動次數(shù)為：

由此可以看出，在順序表上做刪除運(yùn)算，平均移動結(jié)點(diǎn)次數(shù)約為表長的一半，因此，該算法的平均時(shí)間復(fù)雜度為O(n)。7、順序表查找

順序表是指線性表的順序存儲結(jié)構(gòu)。假定在本章的討論中，順序表采用一維數(shù)組來表示，其元素類型為NodeType，它含有關(guān)鍵字key域和其它數(shù)據(jù)域data，key域的類型假定用標(biāo)識符KeyType(int)表示，具體表的類型定義如下：

typedefstruct{

KeyTypekey；

InfoTypedata；

}NodeType；

typedefNodeTypeSeqList[n+1]；

//0號單元用作哨兵

在順序表上的查找方法有多種，這里只介紹最常用的、最主要的兩種方法，即順序查找和二分查找。。

順序查找(SequentialSearch)又稱線性查找，它是一種最簡單和最基本的查找方法。其基本思想是：從表的一端開始，順序掃描線性表，依次把掃描到的記錄關(guān)鍵字與給定的值k相比較；若某個(gè)記錄的關(guān)鍵字等于k，則表明查找成功，返回該記錄所在的下標(biāo)，若直到所有記錄都比較完，仍未找到關(guān)鍵字與k相等的記錄，則表明查找失敗，返回0值。因此，順序查找的算法描述如下：

intSeqSearch(SeqListR,KeyTypek,intn)

{//從順序表R中順序查找記錄關(guān)鍵字為k的記錄，

//查找成功返回其下標(biāo)，否則返回0；R[0]作為哨兵，

//用R[0].key==k作為循環(huán)下界的終結(jié)條件。

R[0].key=k；//設(shè)置哨兵

i=n；//從后向前掃描

while(R[i].key!=k)

i--；

returni；//返回其下標(biāo),若找不到，返回0

}

由于這個(gè)算法省略了對下標(biāo)越界的檢查，查找速度有了很大的提高，其哨兵也可設(shè)在高端，其算法留給讀者自己設(shè)計(jì)。盡管如此，順序查找的速度仍然是比較慢的，查找最多需要比較n+1次。若整個(gè)表R[1..n]已掃描完，還未找到與k相等的記錄，則循環(huán)必定終止于R[0].key==k，返回值為0，表示查找失敗，總共比較了n+1次；若循環(huán)終止于i>0,則說明查找成功，此時(shí)，若i=n，則比較次數(shù)Cn=1；若i=1，則比較次數(shù)C1=n；一般情況下Ci=n-i+1。因此，查找成功時(shí)平均查找長度為：

即順序查找成功時(shí)的平均查找長度約為表長的一半(假定查找某個(gè)記錄是等概率)。如果查找成功和不成功機(jī)會相等，那么順序查找的平均查找長度：

((n+1)/2+(n+1))/2=3(n+1)/4

順序查找的優(yōu)點(diǎn)是簡單的，且對表的結(jié)構(gòu)無任何要求，無論是順序存儲還是鏈?zhǔn)酱鎯?，無論是否有序，都同樣適用，缺點(diǎn)是效率低。順序表的簡單應(yīng)用有序表的合并#include<iostream>usingnamespacestd;int*init(int*x,int&n){cout<<"輸入順序表的大小：";cin>>n;x=(int*)malloc(sizeof(int)*n);cout<<"輸入"<<n<<"個(gè)數(shù)據(jù)："<<endl;for(inti=0;i<n;i++)cin>>x[i];returnx;}int*hebing(int*a,int*b,intna,intnb){int*c=(int*)malloc(sizeof(int)*(na+nb));inti=0,j=0,k=0;while(i<na&&j<nb){if(a[i]<b[j]){c[k]=a[i];i++;}else{c[k]=b[j];j++;}k++;}if(i==na)while(j<nb)c[k++]=b[j++];elsewhile(i<na)c[k++]=a[i++];returnc;}intmain(){int*a,*b,*sum,na,nb;a=init(a,na);b=init(b,nb);sum=hebing(a,b,na,nb);for(inti=0;i<na+nb;i++)cout<<sum[i]<<"";cout<<endl;return0;}二分法檢索又稱折半檢索，二分法檢索的基本思想是設(shè)字典中的元素從小到大有序地存放在數(shù)組中，首先將給定值key與字典中間位置上元素的關(guān)鍵碼比較，如果相等，則檢索成功；否則，若key小，則在字典前半部分中繼續(xù)進(jìn)行二分法檢索，若key大，則在字典后半部分中繼續(xù)進(jìn)行二分法檢索。這樣，經(jīng)過一次比較就縮小一半的檢索區(qū)間，如此進(jìn)行下去，直到檢索成功或檢索失敗。二分法檢索是一種效率較高的檢索方法，要求字典在順序表中按關(guān)鍵碼排序。實(shí)驗(yàn)2鏈表的應(yīng)用實(shí)驗(yàn)?zāi)康?、熟悉C語言的上機(jī)環(huán)境，掌握C語言的基本結(jié)構(gòu)。

2、會定義線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)。

3、熟悉對鏈表的一些基本操作和具體的函數(shù)定義。

4、本章的主要任務(wù)是使用有關(guān)單鏈表的操作來實(shí)現(xiàn)通訊錄信息系統(tǒng)的管理。實(shí)驗(yàn)要求1.創(chuàng)建和銷毀鏈表存儲結(jié)構(gòu)。2.實(shí)現(xiàn)鏈表的基本操作，如插入、刪除、查找和遍歷等。3.鏈表的簡單應(yīng)用，如約瑟夫環(huán)、集合求并、一元多項(xiàng)式相加等。實(shí)驗(yàn)步驟1.創(chuàng)建和銷毀鏈表存儲結(jié)構(gòu)。創(chuàng)建鏈表

一般將鏈表中的每個(gè)數(shù)據(jù)對象稱為節(jié)點(diǎn)（Node）。創(chuàng)建鏈表的基本步驟如下:

第一步，創(chuàng)建第一個(gè)節(jié)點(diǎn)，并將此節(jié)點(diǎn)的內(nèi)存地址保存

第二步，創(chuàng)建第二個(gè)節(jié)點(diǎn)，將第二個(gè)節(jié)點(diǎn)的首地址保存在第一個(gè)節(jié)點(diǎn)的成員變量中。

第三步，以此類推，創(chuàng)建第n個(gè)節(jié)點(diǎn)，并將此節(jié)點(diǎn)的地址存儲到第n-1節(jié)點(diǎn)的成員變量中。銷毀一個(gè)鏈表在鏈表使用完畢后建議銷毀它，因?yàn)殒湵肀旧頃加脙?nèi)存空間。如果一個(gè)系統(tǒng)中使用很多的鏈表，而使用完畢后又不及時(shí)地銷毀它，那么這些垃圾空間積累過多，最終可能導(dǎo)致內(nèi)存的泄漏甚至程序的崩潰。因此應(yīng)當(dāng)養(yǎng)成及時(shí)銷毀不用的鏈表的習(xí)慣。函數(shù)destroyLinkList()的作用是銷毀一個(gè)鏈表list，它包括以下步驟。（1）首先將*list的內(nèi)容賦值給p，這樣p也指向鏈表的第一個(gè)結(jié)點(diǎn)，成為了鏈表的表頭。（2）然后判斷只要p不為空（NULL），就將p指向的下一個(gè)結(jié)點(diǎn)的指針（地址）賦值給q，并應(yīng)用函數(shù)free()釋放掉p所指向的結(jié)點(diǎn)，p再指向下一個(gè)結(jié)點(diǎn)。如此循環(huán)，直到鏈表為空為止。（3）最后將*list的內(nèi)容置為NULL，這樣主函數(shù)中的鏈表list就為空了，防止了list變?yōu)橐爸羔?。而且鏈表在?nèi)存中也被完全地釋放掉了。2.實(shí)現(xiàn)鏈表的基本操作，如插入、刪除、查找和遍歷等。鏈表的插入

鏈表能夠方便地實(shí)現(xiàn)結(jié)點(diǎn)的插入和刪除操作，這也是鏈表結(jié)構(gòu)具有動態(tài)分配存儲空間的體現(xiàn)，也是它優(yōu)于數(shù)組的地方之一。還是舉小朋友排隊(duì)的例子來說明鏈表的插入和刪除是怎樣實(shí)現(xiàn)的。在這個(gè)比喻里面，每一個(gè)小朋友相當(dāng)于一個(gè)結(jié)點(diǎn)，一個(gè)小朋友的手拉著另一個(gè)小朋友的手，相當(dāng)于一個(gè)結(jié)點(diǎn)的指針域指向下一個(gè)結(jié)點(diǎn)。假設(shè)現(xiàn)有一對按大小個(gè)排好隊(duì)的小朋友，又來一個(gè)小朋友需要加入該隊(duì)列。這時(shí)候，就需要從原來隊(duì)列里面的第一個(gè)小朋友開始，按照他們的身高找到新來小朋友應(yīng)該站的位置（前一個(gè)小朋友的身高比他矮，后一個(gè)小朋友的身高比他高）。然后，把這兩個(gè)小朋友的手分開，讓前一個(gè)小朋友的手該拉著新來小朋友的一只手，新來小朋友的另一只手拉著后一個(gè)小朋友的一只手。這樣，新來的小朋友就被插入到這個(gè)隊(duì)伍里面了，并且這個(gè)隊(duì)伍的小朋友還是按照身高順序排列的。特別地，如果新來小朋友最矮，他只需要站在隊(duì)伍的開頭，并且讓他的一只手拉著原來站在對頭的小朋友的手就行了。實(shí)際鏈表的插入操作也就可以類似地實(shí)現(xiàn)。鏈表的刪除在鏈表中刪除一個(gè)節(jié)點(diǎn)，用圖7-4描述如下：[例7-6]創(chuàng)建一個(gè)學(xué)生學(xué)號及姓名的單鏈表，即節(jié)點(diǎn)包括學(xué)生學(xué)號、姓名及指向下一個(gè)節(jié)點(diǎn)的指針，鏈表按學(xué)生的學(xué)號排列。再從鍵盤輸入某一學(xué)生姓名，將其從鏈表中刪除。首先定義鏈表的結(jié)構(gòu)：struct從圖7-4中看到，從鏈表中刪除一個(gè)節(jié)點(diǎn)有三種情況，即刪除鏈表頭節(jié)點(diǎn)、刪除鏈表的中間節(jié)點(diǎn)、刪除鏈表的尾節(jié)點(diǎn)。題目給出的是學(xué)生姓名，則應(yīng)在鏈表中從頭到尾依此查找各節(jié)點(diǎn)，并與各節(jié)點(diǎn)的學(xué)生姓名比較，若相同，則查找成功，否則，找不到節(jié)點(diǎn)。由于刪除的節(jié)點(diǎn)可能在鏈表的頭，會對鏈表的頭指針造成丟失，所以定義刪除節(jié)點(diǎn)的函數(shù)的返回值定義為返回結(jié)構(gòu)體類型的指針。鏈表的遍歷和查找

我們可以用與Length()函數(shù)類似的方法查找鏈表中的某一個(gè)結(jié)點(diǎn)。

//給定鏈表的頭指針和待查結(jié)點(diǎn)數(shù)據(jù)，返回查到的結(jié)點(diǎn)的指針

node*Find(node*head，intdata)

{

node*current=head;

while(current!=NULL)

if(current->data==data)break;

elsecurrent=current->next;

returncurrent;

}

Find()函數(shù)的功能是：輸入鏈表頭結(jié)點(diǎn)head和待查結(jié)點(diǎn)數(shù)據(jù)data，如果某一個(gè)結(jié)點(diǎn)的數(shù)據(jù)與data相等，則返回該結(jié)點(diǎn)的指針；如果查完每一個(gè)結(jié)點(diǎn)也沒有找到數(shù)據(jù)與data相等的結(jié)點(diǎn)，則返回空指針。

需要注意的是：Find函數(shù)也可以寫成下面的形式。

//給定鏈表的頭指針和待查結(jié)點(diǎn)數(shù)據(jù)，返回查到的結(jié)點(diǎn)的指針

node*Find(node*head，intdata)

{

node*current=head;

while(current!=NULL&¤t->data==data)

current=current->next;

returncurrent;

}

但把while的條件"current!=NULL&¤t->data==data"寫成"current->data==data&¤t!=NULL"的形式，則Find函數(shù)可能會出現(xiàn)運(yùn)行錯(cuò)誤。這是因?yàn)椋喝绻湵淼淖詈笠粋€(gè)結(jié)點(diǎn)，仍然不是要找的結(jié)點(diǎn)，則到下一次循環(huán)時(shí)current為NULL，再進(jìn)行條件判斷時(shí)，前者current!=NULL為真，而不再作current->data==data的判斷，循環(huán)便結(jié)束；而后者在作current->data==data判斷時(shí)就會導(dǎo)致程序崩潰。3.鏈表的簡單應(yīng)用，如約瑟夫環(huán)、集合求并、一元多項(xiàng)式相加等。鏈表的約瑟夫環(huán)#include<iostream>usingnamespacestd;intmark[1005];//數(shù)組來做表,方便快速高效intcur;//表的main(){intn,m;//n個(gè)人,數(shù)到第m個(gè)出列scanf("%d%d",&n,&m);//輸入信息intcnt,on=n;cur=1;inti;while(on--)//出列n次{cnt=0;for(;cnt<m;++cur){if(cur==n+1)cur=1;if(mark[cur])continue;++cnt;}mark[cur-1]=1;//標(biāo)記，出隊(duì)printf("%d\n",cur-1);}return0;}實(shí)驗(yàn)3棧和隊(duì)列的應(yīng)用實(shí)驗(yàn)?zāi)康睦斫鈼：完?duì)列的工程原理，掌握棧和隊(duì)列在計(jì)算機(jī)程序設(shè)計(jì)中的應(yīng)用。實(shí)驗(yàn)要求1.創(chuàng)建和銷毀棧和隊(duì)列的存儲結(jié)構(gòu)，要求達(dá)到“熟練掌握”層次。2.實(shí)現(xiàn)棧和隊(duì)列的基本操作，要求達(dá)到“熟練掌握”層次。3.棧和隊(duì)列的簡單應(yīng)用，要求達(dá)到“基本掌握”層次。實(shí)驗(yàn)步驟1.創(chuàng)建和銷毀棧和隊(duì)列的存儲結(jié)構(gòu)。//*HeaderFile#ifndef__STACK_H__#define__STACK_H__structNode;typedefstructNode*PtrToNode;typedefPtrToNodeStack;intIsEmpty(StackS);StackCreateStack(void);voidDisposeStack(StackS);voidMakeEmpty(StackS);voidPush(ElementTypeX,StackS);ElementTypeTop(StackS);voidPop(StackS);#endif////*ImplementationFile//節(jié)點(diǎn)結(jié)構(gòu)structNode{ElementTypeElement;PtrToNodeNext;};////測試堆棧是否為空intIsEmpty(StackS){returnS->Next==NULL;}////創(chuàng)建一個(gè)空棧StackCreateStack(void){StackS;S=(Node*)malloc(sizeof(structNode));//分配一個(gè)節(jié)點(diǎn)的空間給棧Sif(S==NULL)exit(1);//分配失敗S->Next=NULL;MakeEmpty(S);returnS;}////將棧清空voidMakeEmpty(StackS){if(S==NULL)exit(1);else{while(!IsEmpty(S))Pop(S);}}////進(jìn)棧PushvoidPush(ElementTypeX,StackS){PtrToNodeTmpCell;TmpCell=malloc(sizeof(structNode));if(TmpCell==NULL)exit(1);else{TmpCell->Element=X;TmpCell->Next=S->next;S->next=TmpCell;}}//實(shí)驗(yàn)4樹和二叉樹的應(yīng)用實(shí)驗(yàn)?zāi)康模?）熟練掌握樹的基本概念、二叉樹的基本操作及在鏈?zhǔn)酱鎯Y(jié)構(gòu)上的實(shí)現(xiàn)；

（2）重點(diǎn)掌握二叉樹的生成、遍歷及求深度等算法；

（3）掌握二叉樹的線索化及線索二叉樹的遍歷算法；掌握赫夫曼樹的含義及其應(yīng)用；

（4）掌握運(yùn)用遞歸方式描述算法及編寫遞歸C程序的方法，提高算法分析和程序設(shè)計(jì)能力。實(shí)驗(yàn)要求1.創(chuàng)建和銷毀二叉樹的存儲結(jié)構(gòu)。2.實(shí)現(xiàn)二叉樹的基本操作，如查找和遍歷等。3.二叉樹的簡單應(yīng)用，如線索二叉樹、哈夫曼樹和表達(dá)式樹等。4.樹轉(zhuǎn)化為二叉樹的存儲結(jié)構(gòu)的創(chuàng)建和銷毀。5.樹與森林的遍歷算法。6.樹的簡單應(yīng)用，如因特網(wǎng)查詢等。實(shí)驗(yàn)步驟1.創(chuàng)建和銷毀二叉樹的存儲結(jié)構(gòu)。二叉樹的存儲結(jié)構(gòu)有多種，最常用的有兩種：是順序存儲結(jié)構(gòu)和鏈表存儲結(jié)構(gòu)。順序存儲結(jié)構(gòu)二叉樹可以存放在一維數(shù)組之中，這是一種簡單的順序存儲結(jié)構(gòu)。請看如下語句：constintMAXSIZE20

typedefcharElemType;

ElemTypebt[MAXSIZE];其中Bt就是一維數(shù)組（向量），用它來存儲一棵二叉樹，每個(gè)數(shù)組元素存儲樹的一個(gè)結(jié)點(diǎn)的數(shù)據(jù)信息。假設(shè)讓bt[0]閑置，讓bt[1]存放根結(jié)點(diǎn)信息。假設(shè)按照自上而下、自左至右的順序?qū)D6.4(a)的滿二叉樹存入一維數(shù)組bt，可以發(fā)現(xiàn)圖6.4(a)中結(jié)的編號恰好與數(shù)組元素的下標(biāo)號相對應(yīng)，詳見6.5圖。根據(jù)二叉樹性質(zhì)5，在bt數(shù)組中可以方便地由某結(jié)點(diǎn)bt[i]的下標(biāo)i，找到它的雙親結(jié)點(diǎn)bt[i/2]或者它的左、右孩子結(jié)點(diǎn)bt[2i]、bt[2i+1]。例如bt[2]結(jié)點(diǎn)值為B，它的雙親結(jié)點(diǎn)是bt[1]值為A，左孩子結(jié)點(diǎn)是bt[4]值為D，右孩子結(jié)點(diǎn)是bt[5]值為E。鏈?zhǔn)酱鎯Y(jié)構(gòu)用于二叉樹存儲的鏈表結(jié)構(gòu)，常見的有二叉鏈表和三叉鏈表。二叉鏈表的每個(gè)結(jié)點(diǎn)有一個(gè)數(shù)據(jù)域和兩個(gè)指針域，一個(gè)指針指向左孩子，另一個(gè)指針指向右孩子。2.實(shí)現(xiàn)二叉樹的基本操作，如查找和遍歷等。二叉樹的一般操作，實(shí)現(xiàn)了下：主要練習(xí)了二叉樹的非遞歸遍歷，利用棧，和隊(duì)列來完成。代碼#include"stdio.h"#include"malloc.h"#define

MAXSIZE20//二叉樹結(jié)點(diǎn)的結(jié)構(gòu)體表示形式typedefstructnode{char

data;structnode*left,*right;}BTree;//棧的結(jié)構(gòu)體表示形式typedefstructstackelem{BTree*a[MAXSIZE];inttop;}Stack;//隊(duì)列的結(jié)構(gòu)體的表示形式typedefstructqueueelem{BTree*b[MAXSIZE];intfront,rear;}Queue;//前序遍歷，遞歸的方法voidPreorder(BTree*bt){if(NULL!=bt){printf("%c",bt->data);Preorder(bt->left);Preorder(bt->right);}}3.二叉樹的簡單應(yīng)用，如線索二叉樹、哈夫曼樹和表達(dá)式樹等。線索二叉樹：n個(gè)結(jié)點(diǎn)的二叉鏈表中含有n+1個(gè)空指針域。利用二叉鏈表中的空指針域，存放指向結(jié)點(diǎn)在某種遍歷次序下的前趨和后繼結(jié)點(diǎn)的指針（這種附加的指針稱為"線索"）。

這種加上了線索的二叉鏈表稱為線索鏈表，相應(yīng)的二叉樹稱為線索二叉樹(Threaded

BinaryTree)。根據(jù)線索性質(zhì)的不同，線索二叉樹可分為前序線索二叉樹、中序線索二叉樹和后序線索二叉樹三種。

線索鏈表解決了二叉鏈表找左、右孩子困難的問題，出現(xiàn)了無法直接找到該結(jié)點(diǎn)在某種遍歷序列中的前趨和后繼結(jié)點(diǎn)的問題。哈夫曼樹：哈夫曼樹（Huffman）又稱最優(yōu)二叉樹，是一類帶權(quán)路徑長度最短的樹，有著廣泛的應(yīng)用。

在討論哈夫曼樹之前首先需要弄清楚關(guān)于路徑和路徑長度的概念。樹中兩個(gè)結(jié)點(diǎn)之間的路徑由一個(gè)結(jié)點(diǎn)到另一結(jié)點(diǎn)的分支構(gòu)成。兩結(jié)點(diǎn)之間的路徑長度是路徑上分支的數(shù)目。樹的路徑長度是從根結(jié)點(diǎn)到每一個(gè)結(jié)點(diǎn)的路徑長度之和。4.樹轉(zhuǎn)化為二叉樹的存儲結(jié)構(gòu)的創(chuàng)建和銷毀。完全二叉樹結(jié)點(diǎn)編號

在一棵n個(gè)結(jié)點(diǎn)的完全二叉樹中，從樹根起，自上層到下層，每層從左至右，給所有結(jié)點(diǎn)編號，能得到一個(gè)反映整個(gè)二叉樹結(jié)構(gòu)的線性序列。完全二叉樹的順序存儲

將完全二叉樹中所有結(jié)點(diǎn)按編號順序依次存儲在一個(gè)向量bt[0..n]中。

其中：

bt[1．．n]用來存儲結(jié)點(diǎn)

bt[0]不用或用來存儲結(jié)點(diǎn)數(shù)目。一般二叉樹的順序存儲

①將一般二叉樹添上一些"虛結(jié)點(diǎn)"，成為"完全二叉樹"

②為了用結(jié)點(diǎn)在向量中的相對位置來表示結(jié)點(diǎn)之間的邏輯關(guān)系，按完全二叉樹形式給結(jié)點(diǎn)編號

③將結(jié)點(diǎn)按編號存入向量對應(yīng)分量，其中"虛結(jié)點(diǎn)"用"∮"表示5.樹與森林的遍歷算法。前序遍歷樹

步驟：

(1)訪問根結(jié)點(diǎn)；

(2)按從左至右的次序前序遍歷根的各棵子樹。

前序遍歷樹和前序遍歷與該樹相對應(yīng)的二叉樹具有相同的遍歷結(jié)果，即它們的前序遍歷是相同的。后序遍歷樹

步驟：

(1)按從左至右的次序后序遍歷根的各棵子樹；

(2)訪問根結(jié)點(diǎn)。

后序遍歷樹和中序遍歷與該樹相對應(yīng)的二叉樹具有相同的遍歷結(jié)果。森林的遍歷前序遍歷森林

步驟：

(1)訪問森林中第一棵樹的根結(jié)點(diǎn)；

(2)前序遍歷森林中第一棵樹的根結(jié)點(diǎn)的各子樹；

(3)前序遍歷森林中除第一棵樹外其余各樹所構(gòu)成的森林。

前序遍歷森林和前序遍歷與該森林相對應(yīng)的二叉樹具有相同的遍歷結(jié)果。

后序遍歷森林

步驟：

(1)后序遍歷森林中第一棵樹的根結(jié)點(diǎn)的各子樹；

(2)訪問森林中第一棵樹的根結(jié)點(diǎn)；

(3)后序遍歷森林中除第一棵樹外其余各樹所構(gòu)成的森林。

后序遍歷森林和中序遍歷與該樹相對應(yīng)的二叉樹具有相同的遍歷結(jié)果。6.樹的簡單應(yīng)用，如因特網(wǎng)查詢等。哈夫曼編碼(HuffmanEncoding)是最古老，以及最優(yōu)雅的數(shù)據(jù)壓縮方法之一。它是以最小冗余編碼為基礎(chǔ)的，即如果我們知道數(shù)據(jù)中的不同符號在數(shù)據(jù)中的出現(xiàn)頻率，我們就可以對它用一種占用空間最少的編碼方式進(jìn)行編碼，這種方法是，對于最頻繁出現(xiàn)的符號制定最短長度的編碼，而對于較少出現(xiàn)的符號給較長長度的編碼。哈夫曼編碼可以對各種類型的數(shù)據(jù)進(jìn)行壓縮，如應(yīng)用在JPEG圖像的算法很多領(lǐng)域.

在這里我們采用一個(gè)文本文件來演示哈夫曼編碼的.為了說明問題,這個(gè)文本文件是高度簡化,這樣程序會變得相對簡單,比較好理解.

1.文件內(nèi)容只會出現(xiàn)ASCII字符.即字符集里的字符總數(shù)不超過255.

2.用一串兩進(jìn)制數(shù)比如10,110,1110,0來代表文件里字符.每個(gè)字符有一個(gè)獨(dú)立編碼.而且是一種特殊前綴的編碼,即任一個(gè)編碼都不是另外一個(gè)編碼的前綴.

3.統(tǒng)計(jì)文本文件中各個(gè)字符出現(xiàn)頻率,出現(xiàn)頻率最高的字符分配最短的號碼.

實(shí)驗(yàn)5圖的應(yīng)用實(shí)驗(yàn)?zāi)康模?）掌握線性結(jié)構(gòu)、樹形結(jié)構(gòu)和圖形結(jié)構(gòu)等基本數(shù)據(jù)結(jié)構(gòu)及算法的應(yīng)用；（2）掌握分治技術(shù)、貪心技術(shù)、回溯和分支限界等經(jīng)典算法設(shè)計(jì)技術(shù)應(yīng)用；（3）熟練掌握搜索算法和排序算法的應(yīng)用；（4）具備應(yīng)用算法與數(shù)據(jù)結(jié)構(gòu)開發(fā)簡單應(yīng)用軟件的能力。實(shí)驗(yàn)要求（1）圖的鄰接表和鄰接矩陣存儲結(jié)構(gòu)的創(chuàng)建和銷毀，要求達(dá)到“熟練掌握”層次。（2）實(shí)現(xiàn)圖的基本操作，要求達(dá)到“熟練掌握”層次。實(shí)驗(yàn)步驟1.圖的鄰接表和鄰接矩陣存儲結(jié)構(gòu)的創(chuàng)建和銷毀。2．實(shí)現(xiàn)圖的基本操作，如查找和遍歷等。3．圖的應(yīng)用，如最小生成樹、單源最短路徑、拓?fù)渑判虻取＃?）.圖的鄰接表和鄰接矩陣存儲結(jié)構(gòu)的創(chuàng)建和銷毀。////////////////////////////////////////////////////////////////////圖是通過文件建立的//數(shù)據(jù)元素為char類型//存儲結(jié)構(gòu)為鄰接表//文件中第一行為圖的類型//第二行為節(jié)點(diǎn)元素，以#結(jié)束//下邊每一行為邊，和邊的權(quán)值//下邊是文件的示例/*2ABCD#AB3AC4BC2CD4DA1##*///////////////////////////////////////////////////////////////////#include<iostream>#include<fstream>usingnamespacestd;constintMaxNum=20;constintInfinity=-1;typedefcharVexType;typedefintArcType;typedefstructQNode//定義隊(duì)列節(jié)點(diǎn){intdata;QNode*next;}*LQueuePtr;structLQueue//定義隊(duì)列結(jié)構(gòu)體LQueuePtrfront,rear;};oidQueueInit(LQueue&Q)//隊(duì)列初始化{Q.front=newQNode;Q.front->next=0;Q.rear=Q.front;}voidEnqueue(LQueue&Q,inte){LQueuePtrs;s=newQNode;s->data=e;s->next=0;Q.rear->next=s;Q.rear=s;}boolDequeue(LQueue&Q,int&e){LQueuePtrp;if(Q.front==Q.rear)returnfalse;p=Q.front;Q.front=p->next;e=Q.front->data;deletep;returntrue;}pedefstructArcNode//定義邊的結(jié)構(gòu)體{intadjvex;ArcTypeinfo;ArcNode*nextarc;}*ArcPtr;structVexNode//定義節(jié)點(diǎn)的結(jié)構(gòu)體{VexTypedata;ArcPtrfirstarc;};structALGraph//定義圖的結(jié)構(gòu)體{VexNodevexs[MaxNum+1];intkind,vexnum,arcnum;};intLocateVex(ALGraph&G,VexTypev)//在圖中找到某一個(gè)元素{inti;for(i=G.vexnum;i>0&&G.vexs[i].data!=v;i--);returni;}voidCreateGraph(ALGraph&G,charfn[])//創(chuàng)建圖{inti,j;VexTypeu,v;ArcPtrp;ifstreamf;ArcTypew;f.open(fn);//打開文件失敗if(!f){G.vexnum=0;return;}//讀入圖的種類f>>G.kind;//先設(shè)置邊數(shù)為0G.arcnum=0;i=0;while(true)//向節(jié)點(diǎn)數(shù)組中添加節(jié)點(diǎn){f>>u;if('#'==u)break;i++;G.vexs[i].data=u;G.vexs[i].firstarc=0;}G.vexnum=i;while(true)//讀入各條邊{f>>u>>v;if('#'==u||'#'==v)break;i=LocateVex(G,u);if(0==i)continue;j=LocateVex(G,v);if(0==j||j==i)continue;if(1==G.kind||3==G.kind)w=1;elsef>>w;G.arcnum++;p=newArcNode;p->adjvex=j;p->info=w;p->nextarc=G.vexs[i].firstarc;G.vexs[i].firstarc=p;if(G.kind<=2)continue;p=newArcNode;p->adjvex=i;p->info=w;p->nextarc=G.vexs[j].firstarc;G.vexs[j].firstarc=p;}f.close();}voidOutputGraph(ALGraph&G)//輸出圖voidDFS(ALGraph&G,inti,boolvisited[],voidvisit(VexType))//圖的名稱，當(dāng)前節(jié)點(diǎn)位置，標(biāo)記數(shù)組，訪問函數(shù){intj;ArcPtrp;//訪問當(dāng)前節(jié)點(diǎn)visit(G.vexs[i].data);//修改標(biāo)記值visited[i]=true;for(p=G.vexs[i].firstarc;p;p=p->nextarc){j=p->adjvex;if(!visited[j])//對下一個(gè)節(jié)點(diǎn)遞歸DFS(G,j,visited,visit);}}voidDFSTraverse(ALGraph&G,voidvisit(VexType)){inti;boolvisited[MaxNum+1];for(i=1;i<=G.vexnum;i++)//初始化標(biāo)記數(shù)組{visited[i]=false;}for(i=1;i<=G.vexnum;i++){if(!visited[i]){DFS(G,i,visited,visit);}}}voidBFSTraverse(ALGraph&G,voidvisit(VexType)){//訪問節(jié)點(diǎn)visit(G.vexs[v].data);visited[v]=true;//將訪問的節(jié)點(diǎn)入隊(duì)Enqueue(q,v);while(Dequeue(q,u))//出隊(duì)并訪問{for(p=G.vexs[u].firstarc;p;p=p->nextarc){w=p->adjvex;if(!visited[w]){visit(G.vexs[w].data);visited[w]=true;Enqueue(q,w);}}}}}intmain(){ALGraphG;CreateGraph(G,"aaa.txt");cout<<"創(chuàng)建的圖為:";OutputGraph(G);cout<<"深度優(yōu)先遍歷："<<endl;DFSTraverse(G,visit);cout<<endl<<"廣度優(yōu)先遍歷"<<endl;BFSTraverse(G,visit);cout<<endl;return0;}2．實(shí)現(xiàn)圖的基本操作，如查找和遍歷等#include<stdio.h>#include<iostream.h>structgraph{chartnode;charhnode;doublequanzhi;}gr[100];charnode[50]="";doublegraphshu[50][50];intmini(intt,intn)printf("用普里姆算法得出的結(jié)果是:\n");printf("路徑為：");intt2=0;for(k=0;k<n-1;k++){intt1=mini(t2,n);sum=sum+graphshu[t2][t1];for(inti=0;i<n;i++)graphshu[i][t2]=30000;graphshu[t2][t1]=30000;for(i=0;i<n;i++)graphshu[t1][i]=minval(graphshu[t2][i],graphshu[t1][i]);printf("(%c,%c)",node[t2],node[t1]);t2=t1;}printf("\n最小生成樹的總耗費(fèi)為:%f\n",sum);}voidKruscal(intk,intn)value=gr[0].quanzhi;for(i=1;i<k;i++)//tt為最小權(quán)的下標(biāo)if(value>=gr[i].quanzhi){tt=i;value=gr[i].quanzhi;}///////for(i=0;i<n;i++){if(gr[tt].tnode==node[i])ii=i;if(gr[tt].hnode==node[i])jj=i;}if(nod[ii]==nod[jj]){gr[tt].quanzhi=30000;continue;}else{if(nod[ii]>=nod[jj]){for(i=0;i<n;i++)if(nod[i]==nod[ii])nod[i]=nod[jj];}else{for(i=0;i<n;i++)if(nod[i]==nod[jj])nod[i]=nod[ii];{cin>>gr[k].hnode;cin>>gr[k].quanzhi;}}intp,o=1;for(intj=0;j<k;j++)//n為頂點(diǎn)數(shù){for(intt=0;t<o;t++)if(gr[j].tnode!=node[t])p=0;else{p=1;break;}if(p==0){node[n]=gr[j].tnode;n++;o++;}}for(j=0;j<k;j++){for(intt=0;t<o;t++)if(gr[j].hnode!=node[t])p=0;else{p=1;break;}if(p==0){node[n]=gr[j].hnode;n++;o++;}}for(inti=0;i<n;i++)for(intj=0;j<n;j++)graphshu[i][j]=30000;for(i=0;i<k;i++)//構(gòu)造數(shù)組{for(intj=0;j<n;j++)if(gr[i].tnode==node[j]){ii=j;break;}for(j=0;j<n;j++)if(gr[i].hnode==node[j]){jj=j;break;}graphshu[ii][jj]=gr[i].quanzhi;}for(i=0;i<n;i++)for(intj=i;j<n;j++)graphshu[j][i]=graphshu[i][j];//prim(k,n);charoption;intx;for(x=1;x<=4;x++){cout<<"求給定網(wǎng)的最小生成樹"<<endl;cout<<"1.普里姆（Prim）算法"<<endl;cout<<"2.克魯斯卡爾（Kruskal）算法"<<endl;cout<<"3.退出"<<endl;cout<<"請選擇:";cin>>option;switch(option){case'1':Prim(n,k);break;case'2':Kruscal(n,k);break;case'3':return;}}}輸入文件：如果該數(shù)字序列不是度序列，只需在第一行輸出“No！”;如果該數(shù)字序列是一個(gè)度序列，首先在第一行輸出“Yes！”；然后在接下來的若干行里輸出一個(gè)符合該度序列的圖所有邊，每行一條邊。我們默認(rèn)一個(gè)圖的頂點(diǎn)編號為1至T，如果頂點(diǎn)i與j之間有一條邊，我們表示為“ij”。例如圖一就可以表示為：13243435輸入樣例1：532111輸出樣例1：Yes!13243435輸入樣例2：No!說明：若連接結(jié)點(diǎn)之間的邊可以不止一條，這樣的圖稱為多重圖。一個(gè)結(jié)點(diǎn)如果有指向自己的邊，這條邊被稱為自環(huán)。無向簡單圖是指無自環(huán)的非多重圖。3．圖的應(yīng)用，如最小生成樹、單源最短路徑、拓?fù)渑判虻?*已調(diào)試成功前半部分(yes/no)*/#include<stdio.h>#defineNMAX100intmain(){statica[NMAX][NMAX];inttop[NMAX];inttops,i,temp,s=0,s1=0;scanf("%d",&tops);if(tops>NMAX){fprintf(stderr,"toomanyvertax...\n");return-1;}for(i=0;i<tops;++i){scanf("%d",&temp);s+=top[i]=temp;if(temp%2)++s1;}if(s%2||s1%2){printf("No!\n");return1;}printf("Yes!\n");/*waiting...*/return0;}實(shí)驗(yàn)6散列表的應(yīng)用實(shí)驗(yàn)?zāi)康?1)掌握散列查找的基本思想；(2)掌握閉散列表的構(gòu)造方法；(3)掌握線性探測處理沖突的方法；(4)掌握散列技術(shù)的查找性能。實(shí)驗(yàn)要求(1)了解散列表存儲結(jié)構(gòu)的創(chuàng)建和銷毀。(2)了解實(shí)現(xiàn)散列表的基本操作，如插入、刪除和查找等。(3)解決散列沖突方法的應(yīng)用，如開放地址法和鏈地址法等。實(shí)驗(yàn)步驟散列表由固定數(shù)目的散列表元組成。散列表元或是空，或是包含有與某個(gè)關(guān)鍵字相關(guān)聯(lián)的數(shù)據(jù)。為了找到某個(gè)關(guān)鍵字值的數(shù)據(jù)，就要通過散列函數(shù)作用于關(guān)鍵字值來計(jì)算出散列表元數(shù)。對于某一個(gè)給定關(guān)鍵字的值，散列函數(shù)總是產(chǎn)生出相同的散列表元數(shù)。

沖突和重復(fù)

當(dāng)散列表元的數(shù)目少于關(guān)鍵字值的數(shù)目時(shí)，兩個(gè)或者兩個(gè)以上的關(guān)鍵字值就有可能被散列到同一個(gè)散列表元上，這被稱作沖突。當(dāng)發(fā)生沖突的時(shí)候，有兩種選擇，一種是擴(kuò)展散列表元，使它可以含有多個(gè)表項(xiàng)；另一種是不能有多重散列表項(xiàng)。

后種方法不是一個(gè)好的解決方案，這使我們構(gòu)造巨大的散列表以避免沖突。在大多數(shù)情況下，可以讓散列表元包含多個(gè)散列表項(xiàng)，而這些散列表項(xiàng)都是被散列到該散列表元的。

散列表元可以是一個(gè)包含簡單表項(xiàng)的鏈表，空的散列表元含有一個(gè)空的鏈表，散列表元的新表項(xiàng)被附加到該散列表元的表項(xiàng)鏈表的尾部。

FrankAn(WindSor,Ontario,Canada)寫了一個(gè)簡單的算法，代碼如下：#include<iostream>

#include<stdlib.h>usingnamespacestd;enumHashKeyType

{

KEY_STRING,

KEY_INT,

KEY_LONG,

KEY_USER1,

KEY_USER2,

KEY_USER3,

KEY_USER4

};//定義1

structHashEntryBase

{

HashEntryBase*Prev;

HashEntryBase*Next;

HashEntryBase();

virtualHashKeyTypeGetKeyType()const=0;

virtualsize_tHash(size_tbuckets)const=0;

virtualintKeyEquals(constHashEntryBase*entry)const=0;

};//定義2

structHashEntryInt:publicHashEntryBase

{

intKey;

HashEntryInt(constint&k);

HashEntryInt(constHashEntryInt&e);

virtualHashKeyTypeGetKeyType()const;

virtualsize_tHash(size_tbuckets)const;

virtualintKeyEquals(constHashEntryBase*entry)const;

protected:

HashEntryInt();

};

structHashEntryIntDB:publicHashEntryInt

{

intdata;

HashEntryIntDB(constint&k,constint&db):HashEntryInt(k)

{

data=db;

}

};

structHashEntryStr:publicHashEntryBase

{

stringKey;

HashEntryStr(conststring&k);

HashEntryStr(constHashEntryStr&e);

virtualHashKeyTypeGetKeyType()const;

virtualsize_tHash(size_tbuckets)const;

virtualintKeyEquals(constHashEntryBase*entry)const;

protected:

HashEntryStr();

};

structHashEntryStrDB:publicHashEntryStr

{

stringdata;

HashEntryStrDB(conststring&k,conststring&db):HashEntryStr(k)

{

data=db;

}

};//定義3

classHashBucker;//定義4

classHashTableBase

{

public:

HashTableBase(size_tbuckets);

~HashTableBase();

protected:

boolAddEntry(HashEntryBase*newe);

boolDelEntry(constHashEntryBase*dele);

boolIsDupe(constHashEntryBase*dupe);

constHashEntryBase*FindEntry(constHashEntryBase*find);

virtualboolTravCallback(constHashEntryBase*e)const=0;

boolTraverse();

size_tNoOfBuckets;

HashBucker**Table;

};typedefbool(HashTableBase::*HashTravFunc)(constHashEntryBase*e)const;//定義3

classHashBucker

{

public:

HashBucker();

~HashBucker();

boolAddEntry(HashEntryBase*newe);

boolDelEntry(constHashEntryBase*dele);

boolIsDupe(constHashEntryBase*dupe);

constHashEntryBase*FindEntry(constHashEntryBase*find);

boolTraverse(constHashTableBase&table,HashTravFuncfunc);

protected:

HashEntryBase*First;

};//定義5

typedefbool(*HashEnumFuncIntDB)(constint&k,constint&db);

classHashTableIntDB:privateHashTableBase

{

public:

HashTableIntDB(size_tbuckets):HashTableBase(buckets){};

boolInsert(constint&key,constint&db);

boolDelete(constint&dele);

intLookUp(constint&key);

boolEnumerate(HashEnumFuncIntDBfunc);

protected:

virtualboolTravCallback(constHashEntryBase*e)const;

HashEnumFuncIntDBEnumCallBack;

};typedefbool(*HashEnumFuncStrDB)(conststring&k,conststring&db);

classHashTableStrDB:privateHashTableBase

{

public:

HashTableStrDB(size_tbuckets):HashTableBase(buckets){};

boolInsert(conststring&key,conststring&db);

boolDelete(conststring&dele);

stringLookUp(conststring&key);

boolEnumerate(HashEnumFuncStrDBfunc);

protected:

virtualboolTravCallback(constHashEntryBase*e)const;

HashEnumFuncStrDBEnumCallBack;

};

//實(shí)現(xiàn)1

inlineHashEntryBase::HashEntryBase()

{

Prev=NULL;

Next=NULL;

}//實(shí)現(xiàn)2

inlineHashEntryInt::HashEntryInt()

{

}

inlineHashEntryInt::HashEntryInt(constint&k):Key(k)

{

}

inlineHashEntryInt::HashEntryInt(constHashEntryInt&e):Key(e.Key)

{

}

HashKeyTypeHashEntryInt::GetKeyType()const

{

returnKEY_INT;

}

intHashEntryInt::KeyEquals(constHashEntryBase*entry)const

{

if(KEY_INT!=entry->GetKeyType())

printf("mismatchedtypes.\n");

return(Key==((constHashEntryInt*)entry)->Key);

}

size_tHashEntryInt::Hash(size_tbuckets)const

{

returnsize_t(Key%(unsignedlong)buckets);

}

inlineHashEntryStr::HashEntryStr()

{

}

inlineHashEntryStr::HashEntryStr(conststring&k):Key(k)

{

}

inlineHashEntryStr::HashEntryStr(constHashEntryStr&e):Key(e.Key)

{

}

HashKeyTypeHashEntryStr::GetKeyType()const

{

returnKEY_STRING;

}

intHashEntryStr::KeyEquals(constHashEntryBase*entry)const

{

if(KEY_STRING!=entry->GetKeyType())

printf("mismatchedtypes.\n");

return(Key==((constHashEntryStr*)entry)->Key);

}

size_tHashEntryStr::Hash(size_tbuckets)const

實(shí)驗(yàn)7排序的應(yīng)用實(shí)驗(yàn)?zāi)康模?）掌握查找的不同方法，并能用高級語言實(shí)現(xiàn)查找算法。（2）熟練掌握順序表和有序表的順序查找和二分查找方法。（3）掌握排序的不同方法，并能用高級語言實(shí)現(xiàn)排序算法。（4）熟練掌握順序表的選擇排序、冒泡排序和直接插入排序算法的實(shí)現(xiàn)實(shí)驗(yàn)要求(1）深化理解書本上的理論知識，將書本的知識變“活”（為已掌握，為已活用）；(2）理論和實(shí)踐相結(jié)合，學(xué)會將相關(guān)的數(shù)據(jù)結(jié)構(gòu)和算法應(yīng)用于解決實(shí)際問題，培養(yǎng)數(shù)據(jù)結(jié)構(gòu)的應(yīng)用能力和軟件工程所需要的實(shí)踐能力。實(shí)驗(yàn)步驟輸入：一個(gè)包含n個(gè)正整數(shù)的文件，每個(gè)正整數(shù)小于n,n等于10的7次方（一千萬）。并且文件內(nèi)的正整數(shù)沒有重復(fù)和關(guān)聯(lián)數(shù)據(jù)。

輸出:

輸入整數(shù)的升序排列

約束：限制在1M左右內(nèi)存，充足的磁盤空間假設(shè)整數(shù)占32位，1M內(nèi)存可以存儲大概250000個(gè)整數(shù)，第一個(gè)方法就是采用基于磁盤的合并排序算法，第二個(gè)辦法就是將0-9999999切割成40個(gè)區(qū)間，分40次掃描（10000000/250000)，每次讀入250000個(gè)在一個(gè)區(qū)間的整數(shù)，并在內(nèi)存中使用快速排序。書中提出的第三個(gè)解決辦法是采用bitmap（或者稱為bitvector）來表示所有數(shù)據(jù)集合（注意到條件，數(shù)據(jù)沒有重復(fù)），這樣就可以一次性將數(shù)據(jù)讀入內(nèi)存，減少了掃描次數(shù)。算法的偽代碼如下：

階段1：初始化一個(gè)空集合

fori=[0,n)

bit[i]=0;

階段2：讀入數(shù)據(jù)i，并設(shè)置bit[i]=1

foreachiintheinputfile

bit[i]=1;

階段3：輸出排序的結(jié)果

fori=[0,n)

ifbit[i]==1

writeiontheoutputfile算法的時(shí)間復(fù)雜度為O(N)

#include<stdio.h>

#defineWORD32

#defineSHIFT5

#defineMASK0x1F

#defineN10000000

intbitmap[1+N/WORD];

/*

*置位函數(shù)——用"|"操作符,i&MASK相當(dāng)于mod操作

*mmodn運(yùn)算，當(dāng)n=2的X次冪的時(shí)候,mmodn=m&(n-1)

*/

void

set(inti)

{

bitmap[i>>SHIFT]|=(1<<(i&MASK));

}

/*清除位操作，用&~操作符*/

void

clear(inti)

{

bitmap[i>>SHIFT]&=~(1<<(i&MASK));

}

/*測試位操作用&操作符*/

int

test(inti)

{

returnbitmap[i>>SHIFT]&(1<<(i&MASK));

}

intmain()

{

inti=0;

printf("beforesort:\n");

while(scanf("%d",&i)!=EOF){

set(i);

}

printf("aftersort:\n");

for(i=0;i<N;i++){

if(test(i)){

printf("%d\n",i);

}

}

return0;

}======================基于位圖的整數(shù)序列合并算法=====================================搜索引擎檢索時(shí)，常常要將兩個(gè)結(jié)果進(jìn)行組合處理，例如查詢“中國北京”，則需要將包含“中國”和“北京”的文檔編號序列進(jìn)行合并的操作。常用的算法有歸并，先排序后去重等，但這些算法在大數(shù)據(jù)量的情況下，如對包含“中國”的10萬個(gè)文檔編號序列和包含“北京”的8萬個(gè)文檔編號序列進(jìn)行組合時(shí)，效率比較低，無法滿足搜索引擎高速的檢索要求。我們引入了基于二進(jìn)制數(shù)組的算法來解決這個(gè)問題。

基于二進(jìn)制數(shù)組的整數(shù)序列合并算法是一種高速的多個(gè)整數(shù)序列組合的算法。它的基本原理是將各整數(shù)序列保存在一個(gè)二進(jìn)制的數(shù)組當(dāng)中，然后對這些二進(jìn)制數(shù)組進(jìn)行并，或的運(yùn)算。

下面詳細(xì)介紹一下此算法的處理過程。

1．將整數(shù)序列轉(zhuǎn)為二進(jìn)制數(shù)組。

先申請一個(gè)二進(jìn)制數(shù)組，其大小為有可能出現(xiàn)的最大的整數(shù)值，如500萬，如圖所示。（圖1）

假設(shè)有5個(gè)整數(shù)組成的序列{2,3,200,7000,12000}，則我們可以將這個(gè)序列保存在二進(jìn)制數(shù)組當(dāng)中，如圖2所示，第n位如果為1，則表示n存在于這個(gè)序列中：（圖2）

2．對兩個(gè)序列進(jìn)行位運(yùn)算。

如果需要對兩個(gè)整數(shù)序列進(jìn)行并的操作，那么只需要對它們對應(yīng)的二進(jìn)制數(shù)組進(jìn)行“并”的位運(yùn)算；如果需要對兩個(gè)整數(shù)序列進(jìn)行或的操作，那么只需要對它們對應(yīng)的二進(jìn)制數(shù)組進(jìn)行“或”的位運(yùn)算；如果需要對兩個(gè)整數(shù)序列進(jìn)行NOT的操作，那么只需要對它們對應(yīng)的二進(jìn)制數(shù)組先進(jìn)行“并”的位運(yùn)算，再進(jìn)行“異或”的位運(yùn)算。

計(jì)算機(jī)進(jìn)行位運(yùn)算的速度是最快的。在實(shí)際的程序中，我們可以以long類型為基本的位運(yùn)算單位，相同位置的long型數(shù)據(jù)進(jìn)行兩兩位運(yùn)算，以提高速度。

3．將二進(jìn)制數(shù)組轉(zhuǎn)為結(jié)果整數(shù)序列。

位運(yùn)算結(jié)束后，需要將這個(gè)結(jié)果再轉(zhuǎn)為整數(shù)序列。這個(gè)轉(zhuǎn)換后的整數(shù)序列就是我們需要的最終結(jié)果。

下面是一次完整的運(yùn)算過程，我們需要將{2,3,300}和{2,3,200,7000,12000}這兩個(gè)序列進(jìn)行并的操作。如圖3所示。實(shí)驗(yàn)八典型算法的應(yīng)用實(shí)驗(yàn)?zāi)康恼莆枕樞虿檎遥ㄔO(shè)置監(jiān)視哨）、折半查找等典型HYPERLI