數(shù)據(jù)結(jié)構(gòu)-查找ds_chap-文庫(kù)吧
2025-04-22 21:08 本頁(yè)面
【正文】 元素的集合。各個(gè)數(shù)據(jù)元素均含有類(lèi)型相同，可唯一標(biāo)識(shí)數(shù)據(jù)元素的關(guān)鍵字。 ?數(shù)據(jù)關(guān)系 R： 數(shù)據(jù)元素同屬一個(gè)集合。 ?基本操作 P： InitDSTable(amp。DT)； 操作結(jié)果：構(gòu)造 — 個(gè)空的動(dòng)態(tài)查找表 DT。 DestroyDSTable(amp。DT)； 初始條件：動(dòng)態(tài)查找表 DT 存在。 操作結(jié)果：銷(xiāo)毀動(dòng)態(tài)查找表 DT。 SearchDSTable(DT， key)； 初始條件：動(dòng)態(tài)查找表 DT存在， key為和關(guān)鍵字類(lèi)型相同的給定值。 操作結(jié)果：若 DT中存在關(guān)鍵字等于 key的數(shù)據(jù)元素，則函數(shù)值為該元素值或在表中位置，否則為 “ 空 ” 。 南昌航空大學(xué)計(jì)算機(jī)學(xué)院 /軟件學(xué)院 第 8章 查找 動(dòng)態(tài)查找表 ?抽象數(shù)據(jù)類(lèi)型 動(dòng)態(tài)查找表 的定義 InsertDSTable(amp。DT， e)； 初始條件：動(dòng)態(tài)查找表 DT存在， e為待插入數(shù)據(jù)元素。 操作結(jié)果：若 DT中不存在其關(guān)鍵字等于 ，則插入e到 DT。 DeleteDSTable(amp。DT， key)； 初始條件：動(dòng)態(tài)查找表 DT存在， key為和關(guān)鍵字類(lèi)型相同的給定值。 操作結(jié)果：若 DT中存在其關(guān)鍵字等于 key的數(shù)據(jù)元素，則刪除。 TraverseDSTable(DT， Visit())； 初始條件：動(dòng)態(tài)查找表 DT存在， Visit是對(duì)結(jié)點(diǎn)操作的應(yīng)用函數(shù)。 操作結(jié)果：按某種次序?qū)?DT的每個(gè)結(jié)點(diǎn)調(diào)用函數(shù) Visit()一次且至多一次。一旦 visit()敗，則操作失敗。 } ADT DynamicSearchTable 南昌航空大學(xué)計(jì)算機(jī)學(xué)院 /軟件學(xué)院 第 8章 查找 動(dòng)態(tài)查找表 ?存儲(chǔ)結(jié)構(gòu) ?二叉鏈表 ?主要內(nèi)容 ?二叉排序樹(shù) ?二叉排序樹(shù)的定義 ?二叉排序樹(shù)的查找過(guò)程 ?二叉排序樹(shù)的插入 ?二叉排序樹(shù)的建立 ?二叉排序樹(shù)的刪除 ?二叉排序樹(shù)的查找分析 ?平衡的二叉排序樹(shù)的定義 lchild data …… rchild key 南昌航空大學(xué)計(jì)算機(jī)學(xué)院 /軟件學(xué)院 第 8章 查找 動(dòng)態(tài)查找表 —— 二叉排序樹(shù) ?二叉排序樹(shù)的定義：一種特殊結(jié)構(gòu)的二叉樹(shù)，或者是一棵空樹(shù)，或者是具有如下性質(zhì)的二叉樹(shù)： ?若它的左子樹(shù)非空，則左子樹(shù)上所有結(jié)點(diǎn)的值均小于根結(jié)點(diǎn)的值； ?若它的右子樹(shù)非空，則右子樹(shù)上所有結(jié)點(diǎn)的值均大于根結(jié)點(diǎn)的值； ?它的左右子樹(shù)也分別為二叉排序樹(shù)。 ?中序遍歷二叉排序樹(shù) ?遞增有序序列 35 15 45 50 40 25 10 20 30 南昌航空大學(xué)計(jì)算機(jī)學(xué)院 /軟件學(xué)院 第 8章 查找 動(dòng)態(tài)查找表 —— 二叉排序樹(shù) ?二叉排序樹(shù)的查找 —— 與次優(yōu)二叉樹(shù)類(lèi)似 ?當(dāng)二叉排序樹(shù)不空時(shí)，首先將給定值和根結(jié)點(diǎn)的關(guān)鍵字比較，若相等，則查找成功，否則將依據(jù)給定值和根結(jié)點(diǎn)的關(guān)鍵字之間的大小關(guān)系，分別在左子樹(shù)或右子樹(shù)上繼續(xù)進(jìn)行查找。 35 15 45 50 40 25 10 20 30 搜索 45 搜索成功 搜索 28 搜索失敗 南昌航空大學(xué)計(jì)算機(jī)學(xué)院 /軟件學(xué)院 第 8章 查找 動(dòng)態(tài)查找表 —— 二叉排序樹(shù) ?二叉排序樹(shù)查找的遞歸算法 ?BiTree SearchBST (BiTree T， KeyType key){ //在根指針 T所指二叉排序樹(shù)中遞歸地查找某關(guān)鍵字等于 key的數(shù)據(jù)元素 //若查找成功，則返回指向該數(shù)據(jù)元素結(jié)點(diǎn)的指針，否則返回空指針 if( (!T)||EQ(key， T)) return (T)； //查找結(jié)束 else if LT(key， T) return(SearchBST(Tlchild， key))； //在左子樹(shù)中繼續(xù)查找 else return(SearchBST(T rchild， key))； //在右子樹(shù)中繼續(xù)查找 }//SearchBST 南昌航空大學(xué)計(jì)算機(jī)學(xué)院 /軟件學(xué)院 第 8章 查找 動(dòng)態(tài)查找表 —— 二叉排序樹(shù) ?二叉排序樹(shù)查找的 非 遞歸算法 ?BiTree NSearchBST (BiTree T， KeyType key){ //在根指針 T所指二叉排序樹(shù)中非遞歸地查找某關(guān)鍵字等于 key的數(shù)據(jù)元素 //若查找成功，則返回指向該數(shù)據(jù)元素結(jié)點(diǎn)的指針，否則返回空指針 p = T。 //指針 p指向根結(jié)點(diǎn)，搜索從根結(jié)點(diǎn)開(kāi)始 while ( p != NULL amp。amp。 p != key ) { if (key p key ) p = p lchild。 else p = p rchild。 } return ( p)。 }//NSearchBST 南昌航空大學(xué)計(jì)算機(jī)學(xué)院 /軟件學(xué)院 第 8章 查找 動(dòng)態(tài)查找表 —— 二叉排序樹(shù) ?二叉排序樹(shù)的插入 ?二叉排序樹(shù)的查找的特點(diǎn) ?動(dòng)態(tài)樹(shù)表查找 ?樹(shù)的結(jié)構(gòu)通常不是一次生成的，而是在查找過(guò)程中，當(dāng)樹(shù)中不存在關(guān)鍵字等于給定值的結(jié)點(diǎn)時(shí)再進(jìn)行插入。 ?新插入的結(jié)點(diǎn)一定是一個(gè)新添加的葉子結(jié)點(diǎn)，并且是查找不成功時(shí)查找路徑上訪(fǎng)問(wèn)的最后一個(gè)
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1