計(jì)算機(jī)數(shù)據(jù)結(jié)構(gòu)總復(fù)習(xí)講稿習(xí)題ppt

總復(fù)習(xí)第1章應(yīng)用軟件設(shè)計(jì)與開發(fā)技術(shù)第2章算法第3章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算第4章查找與排序技術(shù)第1章應(yīng)用軟件設(shè)計(jì)與開發(fā)軟件工程的概念軟件生命周期軟件開發(fā)的原則和方法測(cè)試的概念和方法調(diào)試的概念和方法軟件工程的概念軟件是計(jì)算機(jī)程序、方法、規(guī)則、相關(guān)文檔以及在計(jì)算機(jī)上運(yùn)行時(shí)所必需的數(shù)據(jù)總和。軟件工程：采用工程的概念、原理、技術(shù)和方法指導(dǎo)軟件的開發(fā)和維護(hù)。主要利用工程學(xué)中的生存周期法和各種結(jié)構(gòu)分析方法和結(jié)構(gòu)設(shè)計(jì)方法。軟件生命周期軟件的生命周期：軟件從被提出、實(shí)現(xiàn)、運(yùn)用直到完成其使命的全過程。定義期開發(fā)期維護(hù)期工作問題的定義、可行性研究、需求分析系統(tǒng)設(shè)計(jì)、詳細(xì)設(shè)計(jì)、編碼及測(cè)試運(yùn)行和維護(hù)任務(wù)明確問題是什么？有解否？確定目標(biāo)系統(tǒng)的功能和信息。確定系統(tǒng)方案、模塊劃分、信息關(guān)系，編寫代碼程序并通過測(cè)試改正、適應(yīng)、完善、預(yù)防結(jié)果和文檔調(diào)研報(bào)告、可行性論證報(bào)告、系統(tǒng)功能模型、信息模型、需求分析報(bào)告軟件結(jié)構(gòu)圖、程序清單及說明、測(cè)試結(jié)果及分析報(bào)告維護(hù)記錄、修改說明書應(yīng)用軟件開發(fā)的原則和方法自上而下的系統(tǒng)結(jié)構(gòu)開發(fā)原則模塊化結(jié)構(gòu)開發(fā)原則設(shè)計(jì)方法：自上而下構(gòu)思，自下而上實(shí)現(xiàn)。設(shè)計(jì)風(fēng)格：保證程序易讀、易調(diào)試、易維護(hù)。測(cè)試的概念和方法測(cè)試的目的和特征；測(cè)試用例的選擇：白箱法、黑箱法等價(jià)類法和邊值分析法調(diào)試的概念和方法調(diào)試的目的：發(fā)現(xiàn)軟件發(fā)生錯(cuò)誤的位置，并改正錯(cuò)誤。調(diào)試策略：試探、回溯、對(duì)分查找、歸納、演繹。第2章算法基本的查找技術(shù)是將關(guān)鍵字與表中數(shù)據(jù)比較來查找，而哈希表技術(shù)是將關(guān)鍵字進(jìn)行某種運(yùn)算，直接找到它在表中的位置。一、哈希表的基本概念二、幾種常用哈希表一、哈希表的基本概念1、直接查找技術(shù)設(shè)表長(zhǎng)度為n，如果存在一個(gè)函數(shù)i=i(k)，對(duì)于表中任一元素的關(guān)鍵字k滿足：

①、1≤i≤n②、對(duì)于任意的k1≠k2，有i(k1)≠i(k2)

則稱此表為直接查找表，其中函數(shù)i=i(k)稱為關(guān)鍵字的映象函數(shù)。直接查找表的運(yùn)算(1)直接查找表的填入①、計(jì)算關(guān)鍵字k的映象函數(shù)i=i(k)。

②、將關(guān)鍵字k及相關(guān)信息填入表的第i項(xiàng)。

INPUTk;i=i(k)

A[i]=關(guān)鍵字為k的信息

RETURN(2)直接查找表的取出①、計(jì)算關(guān)鍵字k的映象函數(shù)i=i(k)。②、若第i項(xiàng)為空，則表中無k，否則取出第i項(xiàng)。

INPUTk;i=i(k)IFA[i]≠NULLTHENOUTPUTA[i]RETURN 直接查找表的特點(diǎn)直接查找表的特點(diǎn)是關(guān)鍵字和其存儲(chǔ)單元是一一對(duì)應(yīng)的，不同的關(guān)鍵字對(duì)應(yīng)不同的存儲(chǔ)單元。

k1≠k2時(shí):i(k1)≠i(k2)

這一點(diǎn)有時(shí)是辦不到的，因?yàn)樗箨P(guān)鍵字的取值范圍是有限的。2、哈希表（1）哈希表的定義設(shè)表長(zhǎng)度為n，如果存在一個(gè)映象函數(shù)i=i(k),對(duì)于表中任一元素的關(guān)鍵字k滿足1≤i≤n，則稱此表為哈希表，并稱i(k)為關(guān)鍵字k的哈希碼。（2）哈希表的關(guān)鍵技術(shù)①、構(gòu)造合適的哈希碼，盡量減少?zèng)_突機(jī)會(huì)；②、當(dāng)發(fā)生沖突時(shí)，要具有處理沖突的機(jī)制。（3）哈希表舉例例：將關(guān)鍵字序列(09,31,26,19,01,13,02,11,27,16,05,21)依次填入長(zhǎng)度為n=12的表中，映象函數(shù)為：i=INT(k/3)+1。序號(hào)123456789101112關(guān)鍵字010205091113161921262731哈希碼的構(gòu)造原則是：

①、使表中各關(guān)鍵字盡可能地均勻分布在哈希表中，減少?zèng)_突的機(jī)會(huì)。

②、哈希碼計(jì)算要簡(jiǎn)單，減少計(jì)算時(shí)間。常用的哈希碼構(gòu)造方法有：

①、截段法：哈希碼為關(guān)鍵字串中的一段。②、分段疊加：分段、疊加、截段。

③、除法：i=mod(k,n),若i=0，取i=n。

④、乘法：i=mod(k×y,n),y=0.618033988747。3、哈希碼的構(gòu)造二、幾種常用哈希表根據(jù)處理沖突的方式不同，構(gòu)成不同的哈希表。

1、線性哈希表（1）線性哈希表的填入①、計(jì)算關(guān)鍵字k的哈希碼i=i(k)。

②、檢查表中第i項(xiàng)內(nèi)容，若第i項(xiàng)空，則將k填入表的第i項(xiàng)；否則令i=mod(i+1,n),轉(zhuǎn)②。

INPUTk;i=i(k) WHILEH(i)≠NULLDO {i=mod(i+1,n);IFi=0THENi=n}

H(i)=k RETURN（2）線性哈希表的取出①、計(jì)算關(guān)鍵字k的哈希碼i=i(k)。②、檢查表的第i項(xiàng)內(nèi)容，若第i項(xiàng)空，則哈希表中無k；若第i項(xiàng)為k，則找到k；若第i項(xiàng)不為k,令i=mod(i+1,n)，轉(zhuǎn)②。

INPUTk;i=i(k) WHILE(H(i)≠NULLANDH(i)≠k)DO {i=mod(i+1,n);IFi=0THENi=n} IFH(i)=NULLTHENi=0 RETURNi

（3）線性哈希表舉例例：將關(guān)鍵字序列(9,31,26,19,1,13,2,11,27,16,5,21)依次填入長(zhǎng)度為n=12的線性哈希表中，哈希碼i=INT(k/3)+1。123456789101112993192631919263119192631191319263112*91319263112*91311**19263112*91311**1926273112*91311**1916**26273112*5*91311**1916**26273112*5*91311**1916**26273121****（4）線性哈希表的特點(diǎn)與改進(jìn)當(dāng)線性哈希表發(fā)生沖突較多時(shí)，表中會(huì)產(chǎn)生“堆聚現(xiàn)象”，即許多關(guān)鍵字被連續(xù)地存儲(chǔ)在一起，另外，處理沖突會(huì)產(chǎn)生新的沖突。當(dāng)i(k)=1時(shí)，線性哈希表就是順序表。線性哈希表的改進(jìn)：①、i=mod(i+p,n)，p和n互質(zhì)。②、n=2r，計(jì)算方便。2、隨機(jī)哈希表處理沖突時(shí)，用加隨機(jī)序列代替固定的加1，一般用于n=2k情況。(i=mod(i0+RN(j),n)，RN(j)為第j個(gè)隨機(jī)數(shù)的值。偽隨機(jī)序列的產(chǎn)生：

R=1 FORj=1TOnDO {R=mod(5×R,4×n);RN(j)=INT(R/4)} RETURN

當(dāng)n=16時(shí)，隨機(jī)序列為：

1,6,15,12,13,2,11,8,9,14,7,4,5,10,3,0（1）隨機(jī)哈希表的填入①、計(jì)算關(guān)鍵字k的哈希碼：i0=i(k)，且令i=i0。②、偽隨機(jī)數(shù)序列初始化：j=1，即j指向第1個(gè)隨機(jī)數(shù)。③、檢查表中第i項(xiàng)內(nèi)容，若第i項(xiàng)空，則將k填入表的第i項(xiàng)，否則，令i=mod(i0+RN(j),n),j=j+1，轉(zhuǎn)③。

INPUTk;i0=i(k);i=i0;j=1 WHILEH(i)≠NULLDO {i=mod(i0+RN(j),n);IFi=0THENi=nj=j+1}

H(i)=k RETURN（2）隨機(jī)哈希表的取出①、計(jì)算關(guān)鍵字k的哈希碼：i0=i(k)，且令i=i0。

②、偽隨機(jī)數(shù)序列初始化：j=1。

③、檢查表的第i項(xiàng)內(nèi)容，若第i項(xiàng)空，則哈希表中無k；若第i項(xiàng)為k，則找到k；若第i項(xiàng)不為k,令i=mod(i0+RN(j),n),j=j+1，轉(zhuǎn)③。INPUTk;i0=i(k);i=i0;j=1WHILE(H(i)≠NULLANDH(i)≠k)DO {i=mod(i0+RN(j),n);IFi=0THENi=nj=j+1}IFH(i)=NULLTHENi=0RETURNi

隨機(jī)哈希表克服了線性哈希表的“堆聚現(xiàn)象”，但處理沖突還會(huì)產(chǎn)生新的沖突。（3）隨機(jī)哈希表的分析隨機(jī)哈希表的平均查找次數(shù)：（4）隨機(jī)哈希表舉例當(dāng)n=16時(shí)，隨機(jī)序列為：1,6,15,12,13,2,11,8,9,14,7,4,5,10,3,0例：將關(guān)鍵字序列(9,31,26,19,1,13,2,11,27,16,5,21)依次填入長(zhǎng)度為n=16的隨機(jī)哈希表中，哈希i=INT(k/3)+1。12345678910111213141516993192631919263119192631191319263112*91319263112*913192611**3112*91316192611**3127**12*5*91316192611**3127**12*5*9131619212611**3127**3、溢出哈希表溢出哈希表包括哈希表和溢出表兩部分，在哈希表的填入過程中，將沖突元素順序填入溢出表，查找發(fā)現(xiàn)沖突時(shí)，在溢出表中順序查找。溢出哈希表在處理沖突時(shí)，不會(huì)產(chǎn)生新的沖突。溢出哈希表的運(yùn)算（1）溢出哈希表的填入①、計(jì)算關(guān)鍵字k的哈希碼：i=i(k)。②、檢查哈希表中第i項(xiàng)內(nèi)容，若第i項(xiàng)空，則將k填入哈希表的第i項(xiàng)，否則，將k順序填入溢出表。（2）溢出哈希表的取出①、計(jì)算關(guān)鍵字k的哈希碼：i=i(k)。②、檢查哈希表的第i項(xiàng)內(nèi)容，若第i項(xiàng)空，則哈希表中無k；若第i項(xiàng)為k，則找到k；若第i項(xiàng)不為k，順序查找溢出表。溢出哈希表舉例例：將關(guān)鍵字序列(9,31,26,19,1,13,2,11,27,16,5,21)依次填入長(zhǎng)度為n=12的溢出哈希表中，哈希碼i=INT(k/3)+1。12345678910111215913161921262731哈希表：溢出表：12345......2114、拉鏈哈希表拉鏈哈希表是一種常用的哈希表，拉鏈哈希表中不登記關(guān)鍵字，而登記指針，關(guān)鍵字登記在表外的結(jié)點(diǎn)中，表外結(jié)點(diǎn)有數(shù)據(jù)域和指針域，以鏈接方式鏈接哈希碼相同的結(jié)點(diǎn)。（順序-索引-鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)）

拉鏈哈希表的優(yōu)點(diǎn)是哈希表只存指針，占用存儲(chǔ)單元較少，可以設(shè)計(jì)得大一些，使沖突少一些。關(guān)鍵字存在表外，可以動(dòng)態(tài)分配空間。（1）拉鏈哈希表舉例例：將關(guān)鍵字序列(9,31,26,19,1,13,2,11,27,16,5,21)依次填入長(zhǎng)度為n=12的拉鏈哈希表中。哈希碼：i=INT(k/3)+1。00121110987654321201050130160190210260270311109（2）拉鏈哈希表的填入①、計(jì)算關(guān)鍵字k的哈希碼：i=i(k)。②、取得一個(gè)新結(jié)點(diǎn)p，將k填入p，③、將p結(jié)點(diǎn)插入頭指針為H(i)的鏈表表頭。

INPUTk i=i(k)

NEW(p);V(p)=k;NEXT(p)=H(i);H(i)=p RETURN（3）拉鏈哈希表的取出①、計(jì)算關(guān)鍵字k的哈希碼：i=i(k)。②、在頭指針為H(i)的鏈表中順序查找k。

INPUTk i=i(k);p=H(i) WHILE(p≠0ANDV(p)≠k)DOp=NEXT(p) RETURNp5、指標(biāo)哈希表指標(biāo)哈希表包括指標(biāo)表和內(nèi)容表兩部分，主要針對(duì)關(guān)鍵字長(zhǎng)度不等的情況。指標(biāo)表是一哈希表，可以是任一形式的哈希表。指標(biāo)表中存放一指針，指針指向?qū)?yīng)關(guān)鍵字在內(nèi)容表中存放的位置。內(nèi)容表是一連續(xù)的存儲(chǔ)空間，用以存放關(guān)鍵字的內(nèi)容，包括內(nèi)容長(zhǎng)度或結(jié)束信息。（順序-索引-順序存儲(chǔ)結(jié)構(gòu)）指標(biāo)表只存放指針，相對(duì)于內(nèi)容來說長(zhǎng)度很短，可以設(shè)計(jì)得空間大些，以減少?zèng)_突的機(jī)會(huì)，因此也可用于關(guān)鍵字長(zhǎng)度相等，但長(zhǎng)度較長(zhǎng)的情況

。

§4.3基本的排序技術(shù)排序：以某種規(guī)律把無序序列整理成非遞增或非遞減的有序序列（本章中以非遞減為例）。一、互換排序二、插入排序三、選擇排序四、其它排序方法簡(jiǎn)介五、各種排序方法的比較一、互換排序

冒泡排序與快速排序?qū)儆诨Q排序，互換類排序是指借助于數(shù)據(jù)元素之間的位置互換進(jìn)行排序。1、冒泡排序從表頭到表尾掃描，若有逆序則進(jìn)行交換，記住最后一次發(fā)生交換的位置，以后的已經(jīng)排好序（至少排好一個(gè)）。從表尾到表頭掃描，若有逆序則進(jìn)行交換，記住最后一次發(fā)生交換的位置，以前的已經(jīng)排好序（至少排好一個(gè)）。以上過程反復(fù)進(jìn)行，直到掃描過程中一次交換都沒有發(fā)生就結(jié)束。冒泡排序舉例排序前19135271263116291121第1遍1351912627162911213111351922627169112131第2遍1513219261691121273112513919261611212731第3遍1259131916112126273112591113191621262731第4遍1259111316192126273112591113161921262731最好情況：比較n-1次；最壞情況：比較n(n-1)/2次；平均情況：O(n2)。冒泡排序算法描述設(shè)無序線性表存儲(chǔ)在P(1:n)中。PROCEDUREBUBSORT(P,1,n)k=1;m=n WHILEk<mDO{j=m-1;m=0//當(dāng)一次交換都沒有時(shí)，有k>m,結(jié)束。

FORi=kTOjDOIFP(i)>P(i+1)THEN{a=P(i);P(i)=P(i+1);P(i+1)=a;m=i}j=k+1;k=n+1//當(dāng)一次交換都沒有時(shí)，有k>m,結(jié)束。

FORi=mTOjBY-1DOIFP(i-1)>P(i)THEN{a=P(i);P(i)=P(i-1);P(i-1)=a;k=i}}RETURN比較一次，相鄰元素交換，消除一個(gè)逆序，時(shí)間復(fù)雜度為O(n2)，空間復(fù)雜度為O(1)。單向冒泡排序排序前19135271263116291121第1遍13519126271629112131第2遍51311926162911212731第3遍51131916291121262731第4遍15131629111921262731第5遍15132911161921262731第6遍15291113161921262731第7遍12591113161921262731第8遍12591113161921262731單向冒泡排序算法描述設(shè)無序線性表存儲(chǔ)在P(1:n)中，單向冒泡排序算法如下：

PROCEDUREBSORT(P,1,n) f=n //f：最后發(fā)生交換的位置

WHILEf>0DO {k=f-1;f=0 FORj=1TOkDO {IFP(j)>P(j+1)THEN {a=P(j);P(j)=P(j+1);P(j+1)=a;f=j} } } RETURN時(shí)間復(fù)雜度為O(n2)，空間復(fù)雜度為O(1)。2、快速排序把無序表分成兩部分，使前一部分的任一元素都不大于后一部分的任一元素，然后不斷分割，直到排序完成。（1）線性表的分割①、設(shè)i,j指向線性表的第一個(gè)和最后一個(gè)元素。②、選取i≤k≤j

，令T=P(k)，然后P(i)移到P(k)。③、重復(fù)以下兩步，直到i=j為止，最后將T移到P(i)。

a、將j逐漸減小，直到P(j)小于T為止，把P(j)移到P(i)。

b、將i逐漸增大，直到P(i)大于T為止，把P(i)移到P(j)。線性表分割舉例設(shè)選取T=488921564885161947ij21568985161947ij47215689851619ij47218985161956ij47211989851656ij47211985168956ij47211916858956ij47211916858956ij4721191648858956ij每分割一次至少排序好一個(gè)元素。設(shè)線性表存在P(1:n)中，把其子表P(m,n)分割成兩部分，分界線為i。（2）線性表分割算法描述PROCEDURESPLIT(P,m,n,i)T=P(k);P(k)=P(m);i=m;j=n//選取P(k),m≤k≤n

WHILEi≠jDO{WHILE(P(j)≥TANDi<j)DOj=j-1IFi<jTHEN {P(i)=P(j);i=i+1 WHILE(P(i)≤TANDi<j)DOi=i+1 IFi<jTHEN{P(j)=P(i);j=j-1}}}P(i)=TRETURNPROCEDUREQKSORT(P,m,n)IFn>mTHEN{SPLIT(P,m,n,i)QKSORT(P,m,i-1)QKSORT(P,i+1,n)}RETURNQKSORT(P,1,n)RETURN（3）快速排序算法的遞歸算法PROCEDUREQKSORT2(P,m,n)SETNULL(S)PUSH(S,m,n,top)WHILEtop≠0DO {POP（S,m,n,top) WHILEn>mDO {SPLIT(P,m,n,i) PUSH(S,i+1,n,top）

n=i-1 }RETURN（4）快速排序的非遞歸算法（5）P(k)的選擇P(k)選最大值時(shí)，快速排序相當(dāng)于冒泡排序，選最小值時(shí)效果一樣，選中的值能使表對(duì)半分效率最高，但計(jì)算麻煩。①、選擇P(m)；②、選擇P(m)，P(n)，P((m+n)/2)中的中值。（6）改進(jìn)

大規(guī)模的線性表用快速排序，當(dāng)分割成小表后用冒泡排序。PROCEDUREQKSORT(P,m,n)IFn-m>kTHEN{SPLIT(P,m,n,i)QKSORT(P,m,i-1)QKSORT(P,i+1,n)}ELSE

BUBSORT(P,m,n)RETURN（7）快速排序性能分析最壞情況：W(n)=n(n-1)/2，和冒泡排序一樣；最好情況：O(n×log2n)，比冒泡排序差；時(shí)間復(fù)雜度：O(n×log2n)，優(yōu)于冒泡排序；空間復(fù)雜度：O(log2n)，遞歸算法，要用堆棧。二、插入排序

插入排序的方法是把數(shù)據(jù)元素插入一個(gè)有序的序列來進(jìn)行排序。1、簡(jiǎn)單(直接)插入排序設(shè)線性表存儲(chǔ)在P(1:n)中，對(duì)2到n之間的每個(gè)j，將P(j)插入到已排序好的子表P(1:j-1)之中。簡(jiǎn)單插入排序舉例原始表8921564885161947j=22189564885161947j=32156894885161947j=42148568985161947j=52148568589161947j=61621485685891947j=71619214856858947j=81619214748568589最好情況：比較n-1次；最壞情況：比較n(n-1)/2次；平均情況：O(n2)。簡(jiǎn)單插入排序算法描述PROCEDUREINSORT(P,n)FORj=2TOnDO{T=P(j);k=j-1WHILE(k>0ANDP(k)>T)DO {P(k+1)=P(k);k=k-1}P(k+1)=T}RETURN簡(jiǎn)單插入排序的效率和冒泡排序的效率一樣。時(shí)間復(fù)雜度為O(n2)，空間復(fù)雜度為O(1)。2、希爾排序?qū)⒕€性表進(jìn)行分割成若干個(gè)子表，然后對(duì)每個(gè)子表進(jìn)行簡(jiǎn)單插入排序，當(dāng)整個(gè)線性表基本有序時(shí)，再最后對(duì)其進(jìn)行一次簡(jiǎn)單插入排序。將線性表分割的方法是將相隔某個(gè)增量h的元素構(gòu)成一個(gè)子表，逐次減小h的值，最后當(dāng)h=1時(shí)，排序完成。h的選擇比較復(fù)雜，常用：hk=n/2k（k=1,2,……,[log2n])。其中n為序列的長(zhǎng)度。希爾排序舉例N=12295634418828311324197h1=6293163441982851324187h2=3443182291963241813857h3=1826344312924191813875結(jié)果PROCEDURESHLSORT(P,n)h=INT(n/2) WHILEh>0DO{FORj=h+1TOnDO{T=P(j);i=j-hWHILE(i>0ANDP(i)>T)DO {P(i+h)=P(i);i=i-h}

P(i+h)=T}h=INT(h/2)}RETURN希爾排序算法描述希爾排序的時(shí)間復(fù)雜度在O(n×log2n)～O(n2)之間，約為O(n1.25)，空間復(fù)雜度為O(1)。三、選擇排序1、簡(jiǎn)單的選擇排序掃描整個(gè)線性表，從中找出最小的元素，將它交換到表的最前面，然后對(duì)剩下的子表采取同樣的方法，直到子表空為止，每次排序好一個(gè)元素。原始表8921564885161947j=21621564885891947j=31619564885892147j=41619214885895647j=51619214785895648j=61619214748895685j=71619214748568985j=81619214748568589比較次數(shù)：n(n-1)/2簡(jiǎn)單選擇排序的算法描述PROCEDURESELESORT(P,n)FORi=1TOn-1DO{k=iFORj=i+1TOnDO IFP(j)<P(k)THENk=jIFk≠iTHEN{d=P(i);P(i)=P(k);P(k)=d}}RETURN時(shí)間復(fù)雜度：O(n2)，空間復(fù)雜度O(1)。（1）堆的定義具有n個(gè)數(shù)據(jù)元素的序列(h1,h2,…,hn)，當(dāng)且僅當(dāng)滿足以下條件時(shí)稱為堆。堆常用完全二叉樹表示。

2、堆排序9153853647302412

①、無序序列建堆；

②、堆頂元素和最后一個(gè)元素交換，最后一個(gè)元素 從堆中刪除；③、剩余元素調(diào)整為堆，回到②，直到排序完畢。（2）堆排序的思路91538536473024129153854730122436（3）調(diào)整建堆設(shè)在完全二叉樹H(1:n)中結(jié)點(diǎn)H(m)的左、右子樹均為堆，將以H(m)為根結(jié)點(diǎn)的子樹調(diào)整建堆。將根結(jié)點(diǎn)和左、右子結(jié)點(diǎn)比較：

①、若大于等于左、右子結(jié)點(diǎn)，已經(jīng)為堆，結(jié)束。

②、否則，把根結(jié)點(diǎn)和左、右子結(jié)點(diǎn)中大的一個(gè) 交換，繼續(xù)調(diào)整建堆。47539185301224369153478530122436調(diào)整建堆算法描述PROCEDURESIFT(H,n,m)T=H(m);i=m;j=2mWHILEj≤nDO {IF(j<nANDH(j)<H(j+1)THENj=j+1 IFT<H(j)THEN{H(i)=H(j);i=j;j=2i} ELSEEXIT }H(i)=TRETURN（4）無序序列建堆在完全二叉樹中，從最后一個(gè)非葉子結(jié)點(diǎn)開始進(jìn)行調(diào)整建堆，直到第一個(gè)結(jié)點(diǎn)為止。最后一個(gè)非葉子結(jié)點(diǎn)的序號(hào)：INT(n/2)k=INT(n/2)FORi=kTO1BY–1DOSIFT(H,n,i)RETURN（5）堆排序

①、無序序列建堆；

②、堆頂元素和最后一個(gè)元素交換，然后將最后一 個(gè)元素從堆中刪除。

③、以堆頂元素為根結(jié)點(diǎn)調(diào)整建堆，回到②，直到 排序完畢。PROCEDUREHEAPSORT(H,n)k=INT(n/2)FORi=kTO1BY–1DOSIFT(H,n,i)FORi=nTO2BY–1DO {t=H(1);H(1)=H(i);H(i)=t;SIFT(H,i-1,1)}RETURN時(shí)間復(fù)雜度：O(n×log2n)，空間復(fù)雜度：O(1)。四、其它排序方法簡(jiǎn)介1、歸并排序把長(zhǎng)度為n的線性表看成是由n個(gè)長(zhǎng)度為1的有序表組成，然后反復(fù)進(jìn)行兩兩歸并，形成有序表。(19)(13)

(05)(27)

(01)(26)

(31)(16)↓↓↓↓(13,19)(05,27)

(01,26)(16,31)↓↓(05,13,19,27)(01,16,26,31)↓(01,05,13,16,19,26,27,31)（1）歸并兩個(gè)有序表設(shè)線性表L(1:n)中的子表L(g:h)已經(jīng)部分有序，即它的兩個(gè)子表L(g:m)L(m+1:h)已經(jīng)有序（其中g(shù)≤m<h），歸并這兩個(gè)子表，使L(g:h)有序。①、開辟與L大小相同的空間A(1:n)；②、i從g到m掃描，j從m+1到h掃描，把兩個(gè)子表中小的一個(gè)移到A中相應(yīng)位置，直到其中一個(gè)子表結(jié)束；③、將剩余元素復(fù)制到A中，然后將排序好的對(duì)應(yīng)段復(fù)制回L中。歸并兩個(gè)有序表算法描述PROCEDUREMERGE(L,g,m,h,A)i=g;j=m+1;k=gWHILE(i≤mANDj≤h)DO{IF(L(i)≤L(j)THEN{A(k)=L(i);i=i+1}ELSE{A(k)=L(j);j=j+1}k=k+1}IFi≤mTHENFORj=iTOmDO{A(k)=L(j);k=k+1}ELSEIFj≤hTHENFORi=jTOhDO{A(k)=L(i);k=k+1}FORi=gTOhDOL(i)=A(i)RETURN（2）歸并排序算法描述PROCEDUREMERGSORT(L,n)定義數(shù)組A(1:n)p=1//元素個(gè)數(shù)WHILE(p<n)DO{k=2p//兩個(gè)歸并之間的步長(zhǎng)

FORj=1TOnBYkDO{g=j;h=j+k-1;m=j+p-1IFh>nTHENh=nIFh>mTHENMERGE(L,g,m,h,A)}p=k}RETURN時(shí)間復(fù)雜度：O(n×log2n)空間復(fù)雜度：O(n)。2、基數(shù)排序設(shè)線性表各元素關(guān)鍵字具有k位有效數(shù)字，從有效數(shù)的最低位直到最高位，對(duì)于每一位有效數(shù)字對(duì)線性表進(jìn)行重新排序。排序前按末位排序連接按首位排序連接19(0)(1)01,31,11,21(2)02(3)13(4)(5)05(6)26,16(7)27(8)(9)19,0901(0)01,02,05,09(1)11,13,16,19(2)21,26,27(3)31(4)(5)(6)(7)(8)(9)01133102051105272109010211261313310516162619021621092726111927210931五、各種排序方法的比較排序方法時(shí)間復(fù)雜度空間復(fù)雜度穩(wěn)定性簡(jiǎn)單性平均最好最壞冒泡排序O(n2)O(n)O(n2)O(1)穩(wěn)定簡(jiǎn)單直接插入O(n2)O(n)O(n2)O(1)穩(wěn)定簡(jiǎn)單直接選擇O(n2)O(n2)O(n2)O(1)不穩(wěn)定簡(jiǎn)單希爾排序O(n1.25)O(1)不穩(wěn)定較復(fù)雜快速排序O(nlog2n)O(nlog2n)O(n2)O(log2n)不穩(wěn)定較復(fù)雜堆排序O(nlog2n)O(nlog2n)O(nlog2n)O(1)不穩(wěn)定較復(fù)雜歸并排序O(nlog2n)O(nlog2n)O(nlog2n)O(n)穩(wěn)定較復(fù)雜排序方法的選擇從以下幾個(gè)方面考慮：①、規(guī)模的大小規(guī)模小采用簡(jiǎn)單的排序，規(guī)模大采用復(fù)雜的排序。②、初始的狀態(tài)基本有序采用冒泡、直接插入排序。③、元素信息量的多少信息量大、采用直接選擇排序，移動(dòng)次數(shù)少。④、空間的要求在空間不允許的情況下，采用附加空間少的排序。⑤、穩(wěn)定性要求

如有穩(wěn)定性要求，采用穩(wěn)定的排序方法?！?.4二叉排序樹及其查找一、二叉排序樹的定義二、二叉排序樹的插入三、二叉排序樹的查找四、二叉排序樹的刪除五、平衡二叉排序樹一、二叉排序樹的定義二叉排序樹是為了兼顧插入和查找運(yùn)算，定義如下：二叉排序樹或者為空，或者具有以下性質(zhì)：①、根結(jié)點(diǎn)的左子樹不空時(shí)，則左子樹上所有結(jié)點(diǎn)值均小于根結(jié)點(diǎn)值；②、根結(jié)點(diǎn)的右子樹不空時(shí)，則右子樹上所有結(jié)點(diǎn)值均不小于根結(jié)點(diǎn)值；③、左、右子樹也是二叉排序樹。53312376190457899二、二叉排序樹的插入給定一個(gè)數(shù)據(jù)元素序列，數(shù)據(jù)元素可以相互比較大小，依次讀入數(shù)據(jù)元素作為新結(jié)點(diǎn)。

①、若二叉樹為空，則新結(jié)點(diǎn)作為二叉樹的根結(jié)點(diǎn)。

②、若二叉樹不空，則新結(jié)點(diǎn)和根結(jié)點(diǎn)比較，

a、若新結(jié)點(diǎn)小于根結(jié)點(diǎn)，將新結(jié)點(diǎn)插入左子樹。

b、若新結(jié)點(diǎn)不小于根結(jié)點(diǎn)，將新結(jié)點(diǎn)插入右子樹。例：(53,61,12,37,90,99,3,78,45)53312376190457899PROCEDUREINBSORT(A,n,BT)BT=0FORk=1TOnDO{NEW(p);V(p)=A(k);L(p)=0;R(p)=0;j=BTIFj=0THENBT=pELSEWHILE(L(j)≠pANDR(j)≠p)DOIFV(p)<V(j)THENIFL(j)≠0THENj=L(j)ELSEL(j)=pELSEIFR(j)≠0THENj=R(j)ELSER(j)=p}RETURN二叉排序樹插入算法描述由無序序列A(1:n)構(gòu)造二叉排序樹。三、二叉排序樹的查找規(guī)則：把關(guān)鍵字和根結(jié)點(diǎn)比較，

①、關(guān)鍵字等于根結(jié)點(diǎn)，則查到結(jié)果，結(jié)束；

②、關(guān)鍵字小于根結(jié)點(diǎn)，到左子樹查找；

③、關(guān)鍵字大于根結(jié)點(diǎn)，到右子樹查找。PROCEDUREBSTSERCH(BT,x,p)p=BTWHILE(p≠0ANDV(p)≠x)DO{IFx<V(p)THENp=L(p)ELSEp=R(p)}RETURNp四、二叉排序樹的刪除從二叉排序樹中刪除含x的結(jié)點(diǎn)。

①、找到含x的結(jié)點(diǎn)p和其父結(jié)點(diǎn)q；

②、若p的左子樹空，則把p的右子樹鏈接到q，若p的右子樹空，則把p的左子樹鏈接到q； 二叉排序樹的刪除（續(xù)1）③、若p的左、右子樹都不空

a、在p的左子樹中沿右鏈找到右指針為0的結(jié)點(diǎn)s（即左子樹中的最大值M）和其父節(jié)點(diǎn)t；

b、最大值M賦給p的值域；

c、s的左子樹鏈接到t的右指針。二叉排序樹的刪除圖解（1）p有雙子樹的情況1：p的左子樹的根沒有右子樹，即根結(jié)點(diǎn)是最大值。二叉排序樹的刪除圖解（2）p有雙子樹的情況2：p的左子樹的根有右子樹。二叉排序樹的刪除算法描述(1)//找到含x的節(jié)點(diǎn)p和其父節(jié)點(diǎn)q。p=BT;q=0WHILE(p≠0ANDV(p)≠x)DO {q=p;p=R(q);IFx<V(q)THENp=L(q)}IFp=0THEN{OUTPUT“找不到x!”;RETURN}//如果p是單支樹。IF(L(p)=0ORR(p)=0)THEN {s=L(p);IFs=0THENs=R(p) IFq=0THENBT=s ELSEIFL(q)=pTHENL(q)=s ELSER(q)=s

DISPOSE(p) }二叉排序樹的刪除算法描述（2）//如果p是雙支樹ELSE{t=p;s=L(p)WHILER(s)≠0THEN {t=s;s=R(s)}

V(p)=V(s)IFt=pTHENL(p)=L(s)ELSER(t)=L(s)

DISPOSE(s)}RETURN五、平衡二叉排序樹二叉排序樹的查找效率與二叉排序樹的形態(tài)有關(guān)，而二叉排序樹的形態(tài)和輸入數(shù)據(jù)的次序有關(guān)。在隨機(jī)情況下，二叉排序樹的平均查找次數(shù)為：1+4×log2n。①②③④⑤⑥⑦①②③④⑤⑥⑦①②③④⑤⑥⑦1、平衡二叉樹的的定義平衡二叉樹或者是空樹，或者是具有下列性質(zhì)的二叉樹：

①、左子樹與右子樹的深度差的絕對(duì)值不大于1。

②、左、右子樹也是平衡二叉樹。平衡二叉樹的存儲(chǔ)結(jié)構(gòu)中，每個(gè)結(jié)點(diǎn)增加一個(gè)平衡因子，其值為該結(jié)點(diǎn)的左子樹和右子樹的深度差。平衡二叉排序樹的查找次數(shù)和log2n同數(shù)量級(jí)。 平衡化之后，樹的深度不變，并且不破壞排序樹的特點(diǎn)。2、平衡化處理在平衡二叉樹中插入新結(jié)點(diǎn)可能使二叉樹失去平衡，設(shè)失去平衡的最小二叉樹的根結(jié)點(diǎn)為p，則失衡情況有如下四種。PAALARPRxPAALCLPRxCRCxPAARCLPLxCRCxxPAALARPL

LL型LR型RR型RL型①、LL平衡化處理PAALARPRx21PAALARPRx00條件：BF(P)=2,BF(A)=1LLRT(P,A)L(P)=R(A)BF(P)=0R(A)=PBF(A)=0RETURN條件：BF(P)=-2,BF(A)=-1 RRRT(P,A) R(P)=L(A) BF(P)=0 L(A)=P BF(A)=0 RETURN②、RR平衡化處理xPAALARPLxPAALARPL-2-100條件：BF(P)=2,BF(A)=-1 LRRT(P,A) C=R(A) L(P)=R(C);R(A)=L(C) R(C)=P;L(C)=A IFBF(C)=1THEN {BF(P)=-1;BF(A)=0} ELSEIFBF(C)=-1THEN {BF(P)=0;BF(A)=1} ELSEIFBF(C)=0THEN {BF(P)=0;BF(A)=0} BF(C)=0;A=C RETURN③、LR平衡化處理PAALCLPRxCRCxPAALCLPRxCRCx2-100,1-1,0④、RL平衡化處理?xiàng)l件：BF(P)=-2,BF(A)=1 RLRT(P,A) C=L(A) R(P)=L(C);L(A)=R(C) L(C)=P;R(C)=A IFBF(C)=1THEN {BF(P)=0;BF(A)=-1} ELSEIFBF(C)=-1THEN {BF(P)=1;BF(A)=0} ELSEIFBF(C)=0THEN {BF(P)=0;BF(A)=0} BF(C)=0;A=C RETURNPAARCLPLxCRCxPAARCLPLxCRCx-2100,1-1,03、平衡二叉排序樹的構(gòu)造步驟：①、把新結(jié)點(diǎn)插入平衡二叉排序樹。②、判斷插入新結(jié)點(diǎn)后是否失去平衡。③、找到失去平衡的最小子樹。④、判斷旋轉(zhuǎn)類型并做相應(yīng)調(diào)整。-1100000000pusTHx把新結(jié)點(diǎn)b插入平衡二叉排序樹（1）構(gòu)造新結(jié)點(diǎn)x，若平衡二叉排序樹為空則新結(jié)點(diǎn)為平衡二叉排序樹的根結(jié)點(diǎn)。BFTIN(TH,b)NEW（x）

V(x)=b;L(x)=0;R(x)=0

BF(x)=0IFTH=0THEN{TH=x;RETURN}-1100000000pusTHx-1100000000pusTHx123456789把新結(jié)點(diǎn)b插入平衡二叉排序樹（2）若二叉排序樹不空：①、找到x的插入位置，即x的父結(jié)點(diǎn)s。②、找到從根結(jié)點(diǎn)到x的路徑上最后一個(gè)平衡因子不為零的結(jié)點(diǎn)p。③、同時(shí)記錄p的父結(jié)點(diǎn)u。

q：當(dāng)前訪問的節(jié)點(diǎn)。p=q=TH;u=s=0WHILEq≠0DO{IFBF(q)≠0THEN{p=q;u=s}s=qIFb<V(q)THENq=L(q)ELSEq=R(q)}IFb<V(s)THENL(s)=xELSER(s)=xpqus1100120125128508修改從p到x的路徑上各結(jié)點(diǎn)的平衡因子IFb<V(p)THEN{q=L(p);d=1}ELSE{q=R(p);d=-1}a=qWHILEq≠xDO{IFb<V(q)THEN{BF(q)=1;q=L(q)}ELSE{BF(q)=-1;q=R(q)}}-1100000000pusTHx-1110000-100pusTHxa判斷以p為根的子樹是否失衡IFBF(p)=0THEN{BF(p)=d;RETURN}IFBF(p)+d=0THEN{BF(p)=0;RETURN}IFd=1THEN{IFBF(a)=1THENLLRT(p,a)ELSEIFBF(a)=-1THENLRRT(p,a)}ELSE{IFBF(a)=-1THENRRRT(p,a)ELSEIFBF(a)=1THENRLRT(p,a)}IFu=0THENTH=aELSE{IFL(u)=pTHENL(u)=aELSER(u)=a}RETURN-1100000000pucTHx123456789a-1100000000uxTH123456789cpa§4.5多層索引樹及其查找link1key1link2key2……link2mkey2mlink2m+1索引是提高數(shù)據(jù)存儲(chǔ)和查找效率的基本方法，如果索引本身很大，查找時(shí)間復(fù)雜度也很大，一般采用多層索引樹。多層索引樹中每個(gè)結(jié)點(diǎn)包含2m個(gè)關(guān)鍵字域和2m+1個(gè)指針域。一、B-樹一棵2m+1階的B-樹或?yàn)榭眨驗(yàn)闈M足以下條件的度為2m+1的樹：①、樹中每個(gè)結(jié)點(diǎn)最多有2m+1棵子樹，且除根結(jié)點(diǎn)和葉子外，每個(gè)結(jié)點(diǎn)至少有m+1棵子樹，而根結(jié)點(diǎn)至少有2棵子樹，除非根結(jié)點(diǎn)又同時(shí)是葉子(平衡樹的概念)；②、所有葉子都在最后一層上；③、除葉子外，對(duì)于度為n+1的結(jié)點(diǎn)，指針為link1～

linkn+1關(guān)鍵字為key1<key2<…<keyn，其中l(wèi)inki所指的子樹中所有結(jié)點(diǎn)的關(guān)鍵字均小于keyi，大于keyi-1；④、所有葉子的指針域?yàn)榭铡?、B-樹的結(jié)點(diǎn)定義N(i)：表示結(jié)點(diǎn)i的關(guān)鍵字個(gè)數(shù)；當(dāng)i結(jié)點(diǎn)不是葉子時(shí)，則i結(jié)點(diǎn)有N(i)+1棵子樹；PRT(i)：指向i結(jié)點(diǎn)的父結(jié)點(diǎn)；KEY(i,j)：表示i結(jié)點(diǎn)的第j個(gè)關(guān)鍵字，1≤j≤2m；LINK(i,j)：表示i結(jié)點(diǎn)的第j個(gè)指針域，1≤j≤2m+1。nprtlink1key1link2key2…linkn+1…key2mlink2m+12、B-樹的查找從根結(jié)點(diǎn)BTH開始，將關(guān)鍵字x和結(jié)點(diǎn)q中的各關(guān)鍵字KEY(q,i)(1≤i≤n)比較，分為以下幾種情況：

①、若x=KEY(q,i)，則查找成功，結(jié)束；②、若x<KEY(q,1)，則沿指針LINK(q,1)向下搜索；③、若x>KEY(q,n)，則沿指針LINK(q,n+1)向下搜索；④、若KEY(q,i)<x<KEY(q,i+1)，則沿指針LINK(q,i+1)向下搜索；以上過程一直進(jìn)行到查找成功或進(jìn)行到葉子而查找失敗為止。B-樹查找算法描述PROCEDUREMBSEARCH(BTH,x,q,k,flag)p=BTH;flag=0WHILE(p≠0ANDflag=0)DO{q=p;k=1