[工學(xué)]數(shù)據(jù)結(jié)構(gòu)第17次課-查找C.ppt

《[工學(xué)]數(shù)據(jù)結(jié)構(gòu)第17次課-查找C.ppt》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、1.上機(jī)實(shí)現(xiàn)順序查找的改進(jìn)算法。2.上機(jī)實(shí)現(xiàn)折半查找的遞歸及非遞歸算法。選做：3.設(shè)計(jì)一個(gè)算法，利用折半查找算法在一個(gè)有序表中插入一個(gè)元素x，并保持表的有序性，上機(jī)實(shí)現(xiàn)。實(shí)驗(yàn)三1針對靜態(tài)查找表的查找算法主要有：8.2靜態(tài)查找表一、順序查找（線性查找）二、折半查找（二分或?qū)Ψ植檎遥┤㈧o態(tài)樹表的查找四、分塊查找（索引順序查找）上節(jié)課內(nèi)容回顧2一、順序查找（Linearsearch，又稱線性查找）順序查找：即用逐一比較的辦法順序查找關(guān)鍵字，這顯然是最直接的辦法。對順序結(jié)構(gòu)如何線性查找？挨個(gè)比較對單鏈表結(jié)構(gòu)如何線性查找？函數(shù)雖未給出，但也很容

2、易編寫；只要知道頭指針head就可以“順藤摸瓜”；對非線性樹結(jié)構(gòu)如何順序查找?可借助各種遍歷操作！優(yōu)點(diǎn)：算法簡單，且對順序結(jié)構(gòu)或鏈表結(jié)構(gòu)均適用。缺點(diǎn)：ASL＝(n+1)/2,ASL太大，時(shí)間效率太低。順序查找的特點(diǎn)：3二、折半查找（又稱二分查找或?qū)Ψ植檎遥┫冉o數(shù)據(jù)排序（例如按升序排好），形成有序表，然后再將key與正中元素相比，若key小，則縮小至右半部內(nèi)查找；再取其中值比較，每次縮小1/2的范圍，直到查找成功或失敗為止。①low=1；high=length；//設(shè)置初始區(qū)間②當(dāng)low>high時(shí)，返回查找失敗信息//表空，查找失?、踠

3、ow≤high，mid=(low+high)/2;//取中點(diǎn)a.若kxelem[mid].key，low=mid+1；轉(zhuǎn)②//查找在右半?yún)^(qū)進(jìn)行c.若kx=elem[mid].key，返回?cái)?shù)據(jù)元素在表中位置//查找成功4四、分塊查找（索引順序查找）這是一種順序查找的另一種改進(jìn)方法。先讓數(shù)據(jù)分塊有序，即分成若干子表，要求每個(gè)子表中的數(shù)值（用關(guān)鍵字更準(zhǔn)確）都比后一塊中數(shù)值?。ǖ颖韮?nèi)部未必有序）。然后將各子表中的最大關(guān)鍵字構(gòu)成一個(gè)索引表，表中還要包含每個(gè)子

4、表的起始地址（即頭指針）。索引表最大關(guān)鍵字起始地址2212138920334244382448605874498653第1塊第2塊第3塊224886例：2248861713特點(diǎn)：塊間有序，塊內(nèi)無序5查找步驟分兩步進(jìn)行：①對索引表使用折半查找法（因?yàn)樗饕硎怯行虮恚?；②確定了待查關(guān)鍵字所在的子表后，在子表內(nèi)采用順序查找法（因?yàn)楦髯颖韮?nèi)部是無序表）；查找效率：ASL=Lb+Lw對索引表查找的ASL對塊內(nèi)查找的ASLS為每塊內(nèi)部的記錄個(gè)數(shù)，n/s即塊的數(shù)目例如當(dāng)n=9，s=3時(shí)，ASLbs=3.5,而折半法為3.1,順序法為56ASL最大最小

5、兩者之間表結(jié)構(gòu)有序表、無序表有序表分塊有序表存儲結(jié)構(gòu)順序存儲結(jié)構(gòu)線性鏈表順序存儲結(jié)構(gòu)順序存儲結(jié)構(gòu)線性鏈表三種靜態(tài)查找方法比較順序查找折半查找分塊查找小結(jié)：7針對動態(tài)查找表的查找算法主要有：8.3動態(tài)查找表一、二叉排序樹（BST）二、平衡二叉樹（AVL樹）三、B-、B+樹81、二叉排序樹的定義回顧----或是一棵空樹；或者是具有如下性質(zhì)的非空二叉樹：（1）左子樹的所有結(jié)點(diǎn)均小于根的值；（2）右子樹的所有結(jié)點(diǎn)均大于根的值；（3）它的左右子樹也分別為二叉排序樹。遞歸定義（4）其中序遍歷序列為一個(gè)遞增序列一.二叉排序樹搜索92、二叉排序樹的插入

6、與刪除將數(shù)據(jù)元素構(gòu)造成二叉排序樹的優(yōu)點(diǎn)：①查找過程與順序結(jié)構(gòu)有序表中的折半查找相似，查找效率高；②如果查找不成功，能夠方便地將被查元素插入到二叉樹的葉子結(jié)點(diǎn)上，而且插入或刪除時(shí)只需修改指針而不需移動元素。注：若數(shù)據(jù)元素的輸入順序不同，則得到的二叉排序樹形態(tài)也不同！——這種既查找又插入的過程稱為動態(tài)查找。二叉排序樹既有類似于折半查找的特性，又采用了鏈表存儲，它是動態(tài)查找表的一種適宜表示。104524531290如果待查找的關(guān)鍵字序列輸入順序?yàn)椋海?4，53，45，45，12，24，90）2453451290查找成功，返回查找成功，返回討論

7、1：二叉排序樹的插入和查找操作則生成二叉排序樹的過程為：例：輸入待查找的關(guān)鍵字序列=（45，24，53，45，12，24，90）則生成的二叉排序樹形態(tài)不同：查找成功返回查找成功返回11bstnodeBSTSEARCH(bstnodet,keytypek){bstnodep;p=t;while(p){if(p.key==k)returnp;if(p.key>k)p=p.lchild;elsep=p.rchild;}returnNULL;}1.二叉排序樹的查找452453122890二叉排序樹的查找&插入算法如何實(shí)現(xiàn)？122.二叉排序樹的結(jié)

8、點(diǎn)插入452453122890a.若原樹為空，返回以新插入結(jié)點(diǎn)為樹根的樹。b.否則，找到要插入的父結(jié)點(diǎn)。c.將新結(jié)點(diǎn)插入確定位置4747>45,向右子樹搜索47<53,向左子樹搜索53左子樹為空，47應(yīng)該插