^{<blockquote id="7zlo3"></blockquote>}

正文內(nèi)容

數(shù)據(jù)結(jié)構(gòu)之查找課件(編輯修改稿)

2025-09-14 09:41 本頁面

　

【文章內(nèi)容簡介】 return (search (bright,k))。 } } 非遞歸算法 btree treesearch (BSTree *b, int k) { BSTree *p。 p=b。 while(p!=NULL)。 { if (pdata==k) return (p)。 else if (kpdata) p=pleft。 else p=pright。 } return (NULL)。 } 二叉排序樹查找分析 ?樹型查找最壞情況時，需要的查找時間取決于樹的高度，當(dāng)二叉排序樹接近滿二叉樹時，其高度為 log2n，最壞情況下查找時間為 O(log n)，與二分查找是同樣數(shù)量級的；當(dāng)二叉排序樹為只有一個端結(jié)點(diǎn)的所謂“退化樹”時，其高度等于 n，最壞情況下查找時間為 O(n)，與順序查找屬于同一數(shù)量級。 ?為了保證樹型查找有較高的查找速度，我們希望該二叉樹接近滿二叉樹，也就是希望二叉樹的每一個結(jié)點(diǎn)的左、右子樹高度盡量接近平衡，即使按任意次序不斷地插入結(jié)點(diǎn)，也不要使此樹成為退化樹。圖兩個二叉排序樹 45 24 53 12 37 100 12 45 24 100 53 37 在二叉排序樹上插入結(jié)點(diǎn) 基本思想插入結(jié)點(diǎn)的非遞歸算法 Void insertbst(BSTree *tptr,*s) /*tptr指向根 {…… /*s 指向要插入的結(jié)點(diǎn) slchild=srchild=null。 If (tptr==null) { tptr=s。 return。 } else { p=tptr。 While(p!=null) { if (pkey==skey) return。 /*無需插入 q=p。 /*q記錄 p的父親 if (skey pkey) /*尋找要插入的位置 p=plchild。 else p=prchild。 } If ( skeyqkey) /*至此 ,q指向的是 qlchild=s。 /*要插入結(jié)點(diǎn) s的父 else qrchild=s。 /*結(jié)點(diǎn) } } 在二叉排序樹上刪除結(jié)點(diǎn) 在二叉排序樹中刪除一個結(jié)點(diǎn)后，要使剩余的結(jié)點(diǎn)仍為二叉排序樹。設(shè)被刪除的結(jié)點(diǎn)為 P, 且 P為 F的左兒子（若為右兒子時，道理相同）。 1. P無兒子刪除 P, 修改有關(guān)指針 flchild=null 2. P只有一個兒子設(shè) P只有左兒子 Pl(或右兒子 Pr), 只要令 Pl （或 Pr ）成為 F的左兒子即可。 Flchild=plchild 或 Flchild=prchild 3. P有兩個兒子時，有兩種方法。設(shè) P的前驅(qū)為 S. （ 1）令 P的左子樹成為 F的左子樹， P的右子樹成為 S的右子樹。 Flchild=plchild。 r=prchild。 /*r為臨時變量 S=flchild。 While(srchild != null) s=srchild。 S=r。 /*使 P的右子樹成為 S的右子樹 ?（ 2）使 P的前驅(qū) S代替 P,然后刪除 S. 若 S有左兒子，則用 S的左兒子代替 S的位置。設(shè) Q為 S的父親。 q=p。 S=plchild。 While(srchild != null) { q=s。 S=srchild。 /*找 P左子樹最右下方的結(jié)點(diǎn) S } Pkey=skey。 If (q!=p) qrchild=slchild。 Else qlchild=slchild。 /*當(dāng) Q=P時， S即為 P的左兒子，此時把 S的左兒子作為 P的左兒子平衡樹 ?平衡樹 (Balanced tree)也稱為 AVL樹，是由阿德爾森 — 維爾斯基和蘭迪斯 (Adelsonvelskii and landis)于 1962年首先提出的。 ?這是一種附加了一定限制條件的二叉樹。我們定義二叉樹中每一結(jié)點(diǎn)的左子樹高度減右子樹高度為該結(jié)點(diǎn)的平衡因子（ Balance factor），所謂平衡樹，是指一個二叉樹其任一結(jié)點(diǎn)的平衡因子值只能是 +1， 0或 1，即任一結(jié)點(diǎn)的左、右子樹高度之差不超過 1。 ?如圖，圖中數(shù)字為該結(jié)點(diǎn)的平衡因子。平衡樹 ?平衡二叉樹 1 1 1 1 0 0 0 1 2 0 0 1 0 ?不平衡二叉樹 ?假設(shè)給平衡樹某個結(jié)點(diǎn)的左子樹插入一個新結(jié)點(diǎn)，且此新結(jié)點(diǎn)使左子樹的高度加 1，我們可能會遇到以下三種情況： (1) 如果原來其左子樹高度 hl與右子樹高度 hr相等，即原來此結(jié)點(diǎn)的平衡因子等于 0,插入新結(jié)點(diǎn)后將

點(diǎn)擊復(fù)制文檔內(nèi)容

環(huán)評公示相關(guān)推薦

工學(xué)數(shù)據(jù)結(jié)構(gòu)ppt課件-資料下載頁

【總結(jié)】?實驗安排時間：8-15周單周：周四5、6節(jié)雙周：周二5、6節(jié)地點(diǎn)：1、2班軟4193、4班軟420第3章棧和隊列棧和隊列是兩種常用的線性結(jié)構(gòu)【學(xué)習(xí)目標(biāo)】1.掌握棧和隊列這兩種抽

2025-10-25 20:39

數(shù)據(jù)結(jié)構(gòu)數(shù)組ppt課件-資料下載頁

【總結(jié)】數(shù)據(jù)結(jié)構(gòu)數(shù)組數(shù)組的定義數(shù)組是我們最熟悉的數(shù)據(jù)類型，在早期的高級語言中，數(shù)組是唯一可供使用的數(shù)據(jù)類型。由于數(shù)組中各元素具有統(tǒng)一的類型，并且數(shù)組元素的下標(biāo)一般具有固定的上界和下界，因此，數(shù)組的處理比其它復(fù)雜的結(jié)構(gòu)更為簡單數(shù)組的定義多維數(shù)組是向量的推廣。例如，二維數(shù)組：a00a01………a0n

2026-04-21 18:12

[工學(xué)]數(shù)據(jù)結(jié)構(gòu)第17次課-查找c-資料下載頁

【總結(jié)】數(shù)據(jù)結(jié)構(gòu)計算機(jī)與信息學(xué)院姜敏第1頁1.上機(jī)實現(xiàn)順序查找的改進(jìn)算法。。選做：，利用折半查找算法在一個有序表中插入一個元素x，并保持表的有序性，上機(jī)實現(xiàn)。實驗三數(shù)據(jù)結(jié)構(gòu)計算機(jī)與信息學(xué)院姜敏第2頁

2026-01-10 11:23

數(shù)據(jù)結(jié)構(gòu)排序ppt課件-資料下載頁

【總結(jié)】數(shù)據(jù)結(jié)構(gòu)——WithC/C++主講教師：石振鋒主講教師：石振鋒哈爾濱工業(yè)大學(xué)數(shù)學(xué)系哈爾濱工業(yè)大學(xué)數(shù)學(xué)系2022年6月1數(shù)學(xué)系計算數(shù)學(xué)教研室數(shù)據(jù)結(jié)構(gòu)Ch02數(shù)據(jù)結(jié)構(gòu)課程的內(nèi)容數(shù)學(xué)系計算數(shù)學(xué)教研室數(shù)據(jù)結(jié)構(gòu)Ch02概述插入排序交換排序選擇排序歸并排序基

2026-04-21 18:12

數(shù)據(jù)結(jié)構(gòu)排序ppt課件-資料下載頁

【總結(jié)】第十章排序內(nèi)容提要?本課主題：排序的概念、插入排序，冒泡排序、快速排序，選擇排序，堆排序，歸并排序，其它排序方法?教學(xué)目的：掌握排序的基本概念，掌握插入排序、冒泡排序、快速排序，選擇排序，堆排序，歸并排序算法，了解其它排序方法?教學(xué)重點(diǎn)：插入排序、冒泡排序、快速排序，選擇排序，堆排序，歸并排序?教學(xué)難點(diǎn)：快速

2025-10-25 22:18

gis數(shù)據(jù)結(jié)構(gòu)ppt課件-資料下載頁

【總結(jié)】第二章GIS數(shù)據(jù)結(jié)構(gòu)?第一節(jié)地理空間及其表達(dá)?第二節(jié)地理空間數(shù)據(jù)及其特征?第三節(jié)空間數(shù)據(jù)結(jié)構(gòu)的類型?第四節(jié)空間數(shù)據(jù)結(jié)構(gòu)的建立第一節(jié)地理空間及其表達(dá)一、地理空間的概念“地理空間”(geo-spatial)一般包括地理空間定位框架及其所連接的空間對象；地理空間定位框架即大地測量控制，由平

2026-01-05 03:24

動態(tài)數(shù)據(jù)結(jié)構(gòu)ppt課件-資料下載頁

【總結(jié)】1第七章動態(tài)數(shù)據(jù)結(jié)構(gòu)2教學(xué)目標(biāo)?動態(tài)數(shù)據(jù)結(jié)構(gòu)的概念?動態(tài)申請和釋放內(nèi)存的方法?鏈表的建立?鏈表結(jié)點(diǎn)的插入和刪除算法3從靜態(tài)數(shù)據(jù)結(jié)構(gòu)到動態(tài)數(shù)據(jù)結(jié)構(gòu)動態(tài)內(nèi)存分配鏈表本章小結(jié)4從靜態(tài)數(shù)據(jù)結(jié)構(gòu)到動態(tài)數(shù)據(jù)結(jié)構(gòu)靜態(tài)數(shù)據(jù)結(jié)構(gòu)的特點(diǎn)是由系統(tǒng)分配固定大小的存儲空間，以后在

2026-04-27 12:08

數(shù)據(jù)結(jié)構(gòu)串ppt課件-資料下載頁

【總結(jié)】串的類型定義串的表示和實現(xiàn)串的模式匹配算法串(String)是零個或多個字符組成的有限序列。一般記作S=“a1a2a3…an”，其中S是串名，雙引號括起來的字符序列是串值；ai(1≤i≤n)可以是字母、數(shù)字或其它字符；串中所包含的字符個數(shù)稱為該串的長度。長度為零的串稱為空串(EmptyString)，它不包含任何字

2025-10-25 22:18

數(shù)據(jù)結(jié)構(gòu)排序ppt課件-資料下載頁

【總結(jié)】第9章排序插入排序交換排序選擇排序歸并排序習(xí)題?排序是針對記錄的集合{R1,R2,…,Rn}，其相應(yīng)的關(guān)鍵字序列為{K1,K2,…,Kn}，重組記錄之間的關(guān)系，使記錄的排列次序滿足相應(yīng)的關(guān)鍵字的遞增或遞減關(guān)系。記錄的集合也稱為待排序序列。若待排序序列完全存放在內(nèi)存中，

2025-10-25 22:17

數(shù)據(jù)結(jié)構(gòu)概論ppt課件-資料下載頁

【總結(jié)】數(shù)數(shù)據(jù)據(jù)結(jié)結(jié)構(gòu)構(gòu)蔣洪波蔣洪波華中科技大學(xué)電信系華中科技大學(xué)電信系()12數(shù)據(jù)結(jié)構(gòu)課程的地位數(shù)據(jù)結(jié)構(gòu)課程的地位——針對非數(shù)值計算的程序設(shè)計問題，研究計算機(jī)的操作對象以及它們之間的關(guān)系和操作。——是介于數(shù)學(xué)、計算機(jī)硬件和計算機(jī)軟件三者之間的一門核心課程。關(guān)系對象關(guān)系操作數(shù)學(xué)軟件硬件對象

2026-04-21 18:12

矢量數(shù)據(jù)結(jié)構(gòu)ppt課件-資料下載頁

【總結(jié)】WWW.SDJTU.地理信息系統(tǒng)基礎(chǔ)GeographicalInformationSystem2矢量數(shù)據(jù)模型3序?矢量數(shù)據(jù)模型定義：用歐幾里得（Euclid）幾何學(xué)中的點(diǎn)、線、面及其組合體來表示實體空間分布，通過記錄空間對象的坐標(biāo)及空間關(guān)系來表達(dá)空間對象的位置的數(shù)據(jù)結(jié)構(gòu)。4矢量數(shù)據(jù)模型?§

2026-04-25 07:44

數(shù)據(jù)結(jié)構(gòu)課件隊列ppt課件-資料下載頁

【總結(jié)】?棧?棧的應(yīng)用?隊列?隊列的應(yīng)用隊列抽象數(shù)據(jù)類型隊列的定義隊列(Queue)也是一種運(yùn)算受限的線性表。它只允許在表的一端進(jìn)行插入，而在另一端進(jìn)行刪除。允許刪除的一端稱為隊頭(front)，允許插入的一端稱為隊尾(rear)。（a0,a1,...,ai-1,ai,ai+1,…,a

2026-04-20 02:57

數(shù)據(jù)結(jié)構(gòu)講義ppt課件-資料下載頁

【總結(jié)】西安交通大學(xué)自動化系本科生課程數(shù)據(jù)結(jié)構(gòu)與算法DataStructureandAlgorithms西安交通大學(xué)自動化系杜友田2數(shù)據(jù)結(jié)構(gòu)課程簡介【課程內(nèi)容】?數(shù)據(jù)的各種邏輯結(jié)構(gòu)和物理結(jié)構(gòu)（存儲結(jié)構(gòu)），以及它們之間的相應(yīng)關(guān)系?并對每種結(jié)構(gòu)定義相適應(yīng)的各種運(yùn)算?設(shè)計出相應(yīng)的算法

2026-01-10 08:06

數(shù)據(jù)結(jié)構(gòu)之查找課件(編輯修改稿)

工學(xué)數(shù)據(jù)結(jié)構(gòu)ppt課件-資料下載頁

數(shù)據(jù)結(jié)構(gòu)數(shù)組ppt課件-資料下載頁

[工學(xué)]數(shù)據(jù)結(jié)構(gòu)第17次課-查找c-資料下載頁

數(shù)據(jù)結(jié)構(gòu)排序ppt課件-資料下載頁

數(shù)據(jù)結(jié)構(gòu)排序ppt課件-資料下載頁

gis數(shù)據(jù)結(jié)構(gòu)ppt課件-資料下載頁

動態(tài)數(shù)據(jù)結(jié)構(gòu)ppt課件-資料下載頁

數(shù)據(jù)結(jié)構(gòu)串ppt課件-資料下載頁

數(shù)據(jù)結(jié)構(gòu)排序ppt課件-資料下載頁

數(shù)據(jù)結(jié)構(gòu)概論ppt課件-資料下載頁

矢量數(shù)據(jù)結(jié)構(gòu)ppt課件-資料下載頁

數(shù)據(jù)結(jié)構(gòu)課件隊列ppt課件-資料下載頁

數(shù)據(jù)結(jié)構(gòu)講義ppt課件-資料下載頁

數(shù)據(jù)結(jié)構(gòu)軟ppt課件-資料下載頁

數(shù)據(jù)結(jié)構(gòu)串ppt課件-資料下載頁

數(shù)據(jù)結(jié)構(gòu)之查找課件-wenkub

數(shù)據(jù)結(jié)構(gòu)之查找課件(已修改)

數(shù)據(jù)結(jié)構(gòu)之查找課件(編輯修改稿)

數(shù)據(jù)結(jié)構(gòu)之查找課件-wenkub.com

數(shù)據(jù)結(jié)構(gòu)之查找課件(已改無錯字)