大一下相關(guān)課程課件數(shù)據(jù)結(jié)構(gòu)

第9章查找李巖信息與電子學(xué)院-雷達與對抗技術(shù)研究所

1查找表：由同一類型的數(shù)據(jù)元素（或記錄）構(gòu)成的集合。查找表的基本操作查詢某個“特定的”數(shù)據(jù)元素是否在表中檢索某個“特定的”數(shù)據(jù)元素的各種屬性插入一個數(shù)據(jù)元素刪除某個數(shù)據(jù)元素靜態(tài)查找表：只作查詢和檢索操作的查找表。動態(tài)查找表：在查找過程中同時作插入或刪除操作的查找表。第9章查找2記錄：由若干數(shù)據(jù)項構(gòu)成的數(shù)據(jù)元素。關(guān)鍵字：能標識一個數(shù)據(jù)元素（或記錄）的數(shù)據(jù)項。主關(guān)鍵字：能唯一地標識一個記錄的關(guān)鍵字。次關(guān)鍵字：用以識別若干記錄的關(guān)鍵字。學(xué)號姓名專業(yè)年齡

20030001王洪計算機1720030002李文計算機1820030003謝軍計算機1820030004張輝信息工程2020030005李文信息工程193第9章查找查找：根據(jù)給定的某個值，在查找表中確定一個其關(guān)鍵字等于給定值的記錄或數(shù)據(jù)元素，若表中存在這樣的記錄，則稱查找成功，查找結(jié)果為該記錄在查找表中的位置；否則稱為查找不成功，查找結(jié)果為0或NULL。學(xué)號姓名專業(yè)年齡

20030001王洪計算機1720030002李文計算機1820030003謝軍計算機1820030004張輝信息工程2020030005李文信息工程194第9章查找查找方法評價：平均查找長度平均查找長度ASL(AverageSearchLength)：為確定記錄在表中的位置，需和給定值進行比較的關(guān)鍵字的個數(shù)的期望值叫查找算法的平均查找長度。用于度量查找算法的效率查找算法的基本操作：比較設(shè)查找成功的概率為1(Pi=1)

平均查找長度：ASL=PiCi

Ci：查找第i個記錄所需的比較次數(shù)

Pi：查找第i個記錄的概率5第9章查找關(guān)鍵字類型定義

typedeffloatKeyType;//實型

typedefintKeyType;//整型

typedefchar*KeyType;//字符串型數(shù)據(jù)元素類型定義

typedefstruct{KeyTypekey;//關(guān)鍵字域

……//其他域

}ElemType;

key

6第9章查找對數(shù)值型關(guān)鍵字

#defineEQ(a,b)((a)==(b))#defineLT(a,b)((a)<(b))#defineLQ(a,b)((a)<=(b))對字符串型關(guān)鍵字

#defineEQ(a,b)(!strcmp((a),(b)))#defineLT(a,b)(strcmp((a),(b))<0)#defineLQ(a,b)(strcmp((a),(b))<=0)7第9章查找靜態(tài)查找 在指定的表中查找某一個“特定”的數(shù)據(jù)元素是否存在，檢索某一個“特定”數(shù)據(jù)元素的各種屬性。動態(tài)查找 在查找的過程中同時插入表中不存在的數(shù)據(jù)元素，或者從查找表中刪除已存在的某個數(shù)據(jù)元素。8第9章查找靜態(tài)查找 順序表的查找：順序查找 有序表的查找：折半查找 索引順序表的查找：分塊查找99.1靜態(tài)查找表查找表用線性表表示L1=(45,61,12,3,37,24,90,53,98,78）用順序表表示靜態(tài)查找表用線性鏈表表示靜態(tài)查找表查找方法：順序查找109.1靜態(tài)查找表——順序表的查找順序表類型定義

typedefstruct{ElemType*elem;//0號單元留空

intlength;}SSTable;與線性表順序存儲結(jié)構(gòu)比較一下

012345678910m-1

456112

3372490539878ST.elemSSTableST;119.1靜態(tài)查找表——順序表的查找intSearch_Seq(SSTableST,KeyTypekey){//在順序表ST中順序查找其關(guān)鍵字等于key的數(shù)據(jù)元素。若找到，則函數(shù)值為該元素在表中的位置，否則為0。

ST.elem[0].key=key;//“哨兵”for(i=ST.length;!EQ(key,ST.elem[i].Key;--i)；

returni;//若表中不存在待查元素,i=0}//Search_Seq

012345678910m-1

456112

3372490539878ST.elemkey免去查找過程中每一步都要檢測整個表是否查找完畢129.1靜態(tài)查找表——順序表的查找例1：在下表中查找key=8的結(jié)點。8012n-3n-2n-1nST.elemkey………………100100713iiiiiii查找不成功，i=08012n-3n-2n-1nST.elemkey例2：在下表中查找key=8的結(jié)點?！?00100813iii查找成功，i=n-2139.1靜態(tài)查找表——順序表的查找特點無排序要求；存儲結(jié)構(gòu)：順序、鏈式；平均查找長度：ASLSS=(n+1)/2149.1靜態(tài)查找表——順序表的查找查找表：用有序表表示查找方法：折半查找（二分查找）查找過程：先確定待查記錄所在的范圍（區(qū)間），然后逐步縮小范圍直到找到或找不到該記錄為止。 例：有原始查找表{45,61,12,3,37,24,90,53,98,78}

為進行折半查找，需要先進行排序：

L=(3,12,24,37,45,53,61,78,90,98)159.1靜態(tài)查找表——有序表的查找例：查找Key=24的記錄。

12345678910

3122437455361789098lowmid

high

123456789103122437455361789098lowmid

high

24＜45

24＞12

123456789103122437455361789098Low

highmid169.1靜態(tài)查找表——有序表的查找intSearch_Bin(SSTableST,KeyTypekey){//在有序表ST中折半查找法查找其關(guān)鍵字等于key的數(shù)據(jù)元素。若找到，則返回該元素在表中的位置，否則為0。

low=1;high=ST.length;while(low<=high){mid=(low+high)/2;ifEQ(key,ST.elem[mid].key)returnmid;elseifLT(key,ST.elem[mid].key)high=mid-1;elselow=mid+1;}return0;//表中不存在待查元素}//Search_Bin179.1靜態(tài)查找表——有序表的查找該查找過程可用一個二叉樹來描述123456789103,12,24,37,45,53,61,78,90,98

52136947108樹中每個結(jié)點表示表中一個記錄，結(jié)點中的值為該記錄在表中的位置，結(jié)點的層數(shù)為查找該結(jié)點所對應(yīng)的關(guān)鍵字所需的次數(shù)，通常稱這個描述查找過程的二叉樹為判定樹。189.1靜態(tài)查找表——有序表的查找例1：在下表中查找key=9的結(jié)點。此時ST.elem[mid].key＝10>key，因此令high＝mid－1low=1high=7mid=4012key4891011131934567elemhigh=3mid=2low=1此時ST.elem[mid].key＝8<key，因此令low＝mid＋1low=3mid=3此時ST.elem[mid].key＝9=key，查找成功，返回mid值high=3199.1靜態(tài)查找表——有序表的查找例2：在下表中查找key=5的結(jié)點。012key4891011131934567elem此時ST.elem[mid].key＝10>key，因此令high＝mid－1high=7mid=4low=1low=1high=3mid=2此時ST.elem[mid].key＝8>key，因此令high＝mid－1low=1mid=1此時ST.elem[mid].key＝4<key，因此令low=mid＋1high=1high=1low=2mid=1此時low>high查找不成功209.1靜態(tài)查找表——有序表的查找折半查找的特點要求元素按關(guān)鍵字有序。存儲結(jié)構(gòu)：順序。平均查找長度ASLbs=log2(n+1)-1219.1靜態(tài)查找表——有序表的查找查找表的組織：分塊索引，除表本身以外，尚需建立一個“索引表”。該查找表是“分塊有序”的。查找方法：查找索引表；在數(shù)據(jù)塊內(nèi)順序查找12345678910111213141516171822121389203342443824486058745786532248861713索引表229.1靜態(tài)查找表——索引順序表的查找起始地址最大關(guān)鍵字查找38查找方法比較ASL最大最小兩者之間表結(jié)構(gòu)有序表、無序表有序表分塊有序表存儲結(jié)構(gòu)順序存儲結(jié)構(gòu)線性鏈表順序存儲結(jié)構(gòu)順序存儲結(jié)構(gòu)線性鏈表順序查找折半查找分塊查找239.1靜態(tài)查找表動態(tài)查找

二叉排序樹：或者是一棵空樹；或者是具有下列性質(zhì)的二叉樹：若左子樹不空，則左子樹上所有結(jié)點的值均小于根結(jié)點的值；若右子樹不空，則右子樹上所有結(jié)點的值均大于根結(jié)點的值；根結(jié)點的左、右子樹也分別為二叉排序樹。249.2動態(tài)查找表例：在二叉排序樹中查找關(guān)鍵字為24的記錄。

45

12

3

37

53

90

24

7898

61259.2動態(tài)查找表例：在二叉排序樹中查找關(guān)鍵字為60的記錄。

45

12

3

37

53

90

24

7898

61269.2動態(tài)查找表二叉排序樹的存儲typedefstructBiTNode{TElemTypedata;structBiTNode*lchild,*rchild;}BiTNode,*BTree;typedefstruct{KeyTypekey;…}TElemType;Lchilddatarchild

key

…279.2動態(tài)查找表二叉排序樹的查找——非遞歸算法BiTreeSearchBST(BiTreeT,KeyTypekey){/*二叉排序樹用二叉鏈表存儲。在根指針T所指二叉排序樹中查找關(guān)鍵字等于key的記錄，若查找成功，則返回該記錄結(jié)點的指針，否則返回空指針*/

p=T;while(p&&!EQ(key,p->data.key)){if(LT(key,p>data.key))p=p->lchild;elsep=p->rchild;}return(p);}//SearchBST289.2動態(tài)查找表二叉排序樹的查找（算法9.5a）——遞歸算法BiTreeSearchBST(BiTreeT,KeyTypekey){//將二叉鏈表作為二叉排序樹的存儲結(jié)構(gòu)

if((!T)||EQ(key,T->data.key))return(T);elseif(LT(key,T->data.key))return(SearchBST(T->lchild,key));elsereturn(SearchBST(T->rchild,key));}//SearchBST299.2動態(tài)查找表二叉排序樹的特點：是一種動態(tài)樹表，樹的結(jié)構(gòu)通常不是一次生成的，而是在查找過程中，當樹中不存在關(guān)鍵字等于給定值的結(jié)點時再進行插入。新插入結(jié)點的特點：一定是一個新添加的葉子結(jié)點，并且是查找不成功時查找路徑上訪問的最后一個結(jié)點的左孩子或右孩子結(jié)點。插入新結(jié)點的時機：當查找不成功時。309.2動態(tài)查找表插入算法：執(zhí)行查找算法，找出被插入結(jié)點的雙親結(jié)點；判斷被插入結(jié)點是其雙親結(jié)點的左孩子結(jié)點還是右孩子結(jié)點，將被插入結(jié)點作為葉子結(jié)點插入；若二叉樹為空，則首先單獨生成根結(jié)點。319.2動態(tài)查找表StatusSearchBST(BiTreeT,KeyTypekey,BiTreef,BiTree&p){//在根指針為T的二叉排序樹中查找關(guān)鍵字等于key的元素，若查找成功，則p指向該結(jié)點，并返回TRUE，否則指針p指向查找路徑的最末結(jié)點，并返回FALSE。f指向T的雙親，初始調(diào)用時為NULL。if(!T){p=f;returnFALSE;}elseif(EQ(key,T->data.key)){p=T;returnTRUE;}elseif(LT(key,T->data.key))returnSearchBST(T->lchild,key,T,p);elsereturnSearchBST(T->rchild,key,T,p);}//SearchBST算法9.5b329.2動態(tài)查找表StatusInsertBST(BiTree&T,TElemTypee){

/*當二叉排序樹T中不存在關(guān)鍵字等于e.key的數(shù)據(jù)元素時，插入e并返回TURE，否則返回FALSE*/if(!SearchBST(T,e.key,NULL,p)){//查找不成功

s=(BiTree)malloc(sizeof(BiTNode));s->data=e;s->lchild=s->rchild=NULL;if(!p)T=s;//T為空，被插結(jié)點為根結(jié)點

elseif(LT(e.key,p->data.key))p->lchild=s; elsep->rchild=s;returnTRUE;}elsereturnFALSE;//查找成功}//InsertBST算法9.6339.2動態(tài)查找表例1：插入值為280的結(jié)點。12225030011099Tf：NULL12225030011099fTkey=28012225030011099fTkey=280f12225030011099T:NULLkey=280p12225030011099280349.2動態(tài)查找表例2：在一棵空樹中，查找如下的關(guān)鍵字序列459024125345241253452445245345φ{(diào)45，24，53，45，12，24，90}生成的二叉排序樹如下：對二叉排序樹進行中序遍歷可以得到有序序列359.2動態(tài)查找表二叉排序樹刪除操作刪除原則：保持二叉排序樹的特性。設(shè)：二叉排序樹上指向被刪結(jié)點的指針為p，指向其雙親結(jié)點的指針為f。

F

PPRPLfp369.2動態(tài)查找表二叉排序樹的刪除操作要刪除二叉排序樹中的p結(jié)點，分三種情況：p為葉子結(jié)點p只有左子樹或右子樹p左、右子樹均非空379.2動態(tài)查找表二叉排序樹的刪除操作要刪除二叉排序樹中的p結(jié)點，分三種情況：p為葉子結(jié)點，只需修改

p雙親

f的指針： f->lchild=NULL或f->rchild=NULLpf

F

P刪除前f

F刪除后389.2動態(tài)查找表二叉排序樹的刪除操作p只有左子樹，用p的左孩子代替p(1)(2)FQPLP中序遍歷：QFPLPFQPL中序遍歷：QFPL(2)FPPLQ中序遍歷：PLPFQFPLQ中序遍歷：PLFQ(1)399.2動態(tài)查找表二叉排序樹的刪除操作p只有右子樹，用p的右孩子代替p(3)(4)中序遍歷：PPRFQFPRQ中序遍歷：PRFQ(3)FPPRQ中序遍歷：QFPPRFQPR中序遍歷：QFPR(4)FQPRP409.2動態(tài)查找表二叉排序樹的刪除操作p左、右子樹均非空沿

p左子樹的根

C的右子樹分支找到

S，S的右子樹為空，將

S的左子樹成為

S的雙親Q的右子樹，用

S取代

p(5)FPCPRCLQQLSSL中序遍歷：CLC…QLQSL

S

PPRFFSCPRCLQQLSL中序遍歷：CLC…QLQSL

SPRF(5)419.2動態(tài)查找表二叉排序樹的刪除操作p左、右子樹均非空若

C無右子樹，用

C取代

p(6)FPCPRCL中序遍歷：CLCP

PRFFCPRCL中序遍歷：CLC

PR

F(6)429.2動態(tài)查找表二叉排序樹的刪除操作要刪除二叉排序樹中的p結(jié)點，分三種情況：p為葉子結(jié)點，只需修改

p雙親

f的指針：f->lchild=NULLf->rchild=NULLp只有左子樹或右子樹p只有左子樹，用p的左孩子代替p(1)(2)p只有右子樹，用p的右孩子代替p(3)(4)p左、右子樹均非空沿

p左子樹的根

C的右子樹分支找到

S，S的右子樹為空，將

S的左子樹成為

S的雙親Q的右子樹，用

S取代

p(5)若

C無右子樹，用

C取代

p(6)439.2動態(tài)查找表voidDelete(BiTree&p){//從二叉排序樹中刪除結(jié)點p，并重接它的左或右子樹

if(!p->rchild)//右子樹為空，則只需重接左子樹{q=p;p=p->lchild;free(q);}

elseif(!p->lchild)//左子為空，則只重接右子樹{q=p;p=p->rchild;free(q);}

else

//左右子樹均不空{(diào)q=p;s=p->lchild;while(s->rchild)//定位p左子樹的最右結(jié)點{q=s;s=s->rchild;}p->data=s->data;//s取代p

if(q!=p)q->rchild=s->lchild;//重接右子樹

elseq->lchild=s->lchild;//重接左子樹

free(s);}}//Delete算法9.8449.2動態(tài)查找表二叉排序樹的刪除操作例805012060110150557053刪除508060120110150557053刪除60805512011015053701052581376刪除1085257136刪除78525613459.2動態(tài)查找表性能分析查找表：{3,12,24,37,45,53,61,78,90,98}

45

12

3

37

53

90

24

78

98

61ASL=(1+2+3+4+5+6+7+8+9+10)/10=5.5ASL=(1+22+34+43)/10=2.94512337539024789861單支樹469.2動態(tài)查找表二叉排序樹的特點之一（缺陷）：沒有對樹的深度進行控制。在構(gòu)造二叉排序樹的過程中進行“平衡化”處理，成為平衡二叉樹（AVL樹）。平衡二叉樹：左子樹和右子樹的深度之差的絕對值不超過計劃。479.2動態(tài)查找表二叉排序樹的特點含有n個結(jié)點的二叉排序樹不唯一，與結(jié)點插入的順序有直接關(guān)系。當查找失敗后，在葉結(jié)點插入。刪除某個結(jié)點后，二叉排序樹要重組。沒有對樹的深度進行控制。二叉排序樹的適用范圍

用于組織規(guī)模較小的、內(nèi)存中可以容納的數(shù)據(jù)。對于數(shù)據(jù)量較大必須存放在外存中的數(shù)據(jù)，則無法快速處理。489.2動態(tài)查找表散列法（哈希法）基本思想：在記錄的存儲地址和它的關(guān)鍵字之間建立一個確定的對應(yīng)關(guān)系；這樣，不經(jīng)過比較，一次存取就能得到所查元素的查找方法。即：通過簡單計算直接得到數(shù)據(jù)的地址。哈希(Hash)函數(shù)是一個映象，即：將關(guān)鍵字的集合映射到某個地址集合上，它的設(shè)置很靈活，只要這個地址集合的大小不超出允許范圍即可。哈希函數(shù)可寫成：addr(ai)=H(ki) ai是表中的一個元素 addr(ai)是ai的存儲地址 ki是ai的關(guān)鍵字。關(guān)鍵字集合存儲地址集合hash499.3哈希表散列法（哈希法）由于哈希函數(shù)是一個壓縮映象，因此，在一般情況下，很容易產(chǎn)生“沖突”現(xiàn)象，即：key1key2，而f(key1)=f(key2)。很難找到一個不產(chǎn)生沖突的哈希函數(shù)。一般情況下，只能選擇恰當?shù)墓：瘮?shù)，使沖突盡可能少地產(chǎn)生。

1235152年份人數(shù)

1949195019511999200020002100220044004420例某地區(qū)的人口統(tǒng)計表H(年度）=年度-1948509.3哈希表散列法（哈希法）例30個地區(qū)的各民族人口統(tǒng)計表編號地區(qū)總?cè)丝跐h族回族…...1北京2上?！?..…...以編號作關(guān)鍵字，構(gòu)造哈希函數(shù)：H(key)=keyH(1)=1H(2)=2以地區(qū)作關(guān)鍵字，取地區(qū)名稱第一個拼音字母的序號作哈希函數(shù)：H(Beijing)=2H(Shanghai)=19H(Shenyang)=19519.3哈希表散列法（哈希法）哈希表——應(yīng)用哈希函數(shù)，由記錄的關(guān)鍵字確定記錄在表中的地址，并將記錄放入此地址，這樣構(gòu)成的表叫哈希表。哈希查找——又叫散列查找，利用哈希函數(shù)進行查找的過程叫哈希查找。529.3哈希表散列法（哈希法）在構(gòu)造這種特殊的“查找表”時，除了需要選擇一個“好”（盡可能少產(chǎn)生沖突）的哈希函數(shù)之外，還需要找到一種“處理沖突”的方法?！疤幚頉_突”的實際含義是：為產(chǎn)生沖突的地址尋找下一個哈希地址。常用的解決沖突的方法：開放地址法、鏈地址法、再哈希法、建立一個公共溢出區(qū)。5