數(shù)據(jù)結(jié)構(gòu)與常用算法二版

第7章

數(shù)據(jù)結(jié)構(gòu)與常用算法7.1數(shù)據(jù)結(jié)構(gòu)的根本概念7.2線性表及其存儲(chǔ)結(jié)構(gòu)7.3棧和隊(duì)列7.4樹與二叉樹7.5查找算法7.6排序算法7.1數(shù)據(jù)結(jié)構(gòu)的根本概念7.1.1根本術(shù)語(1)數(shù)據(jù)：能被計(jì)算機(jī)識(shí)別、存儲(chǔ)和加工處理的符號(hào)的總稱。計(jì)算機(jī)中可以操作的對(duì)象(2)數(shù)據(jù)元素：數(shù)據(jù)的根本單位。在計(jì)算機(jī)中通常作為整體處理，也稱為記錄(3)數(shù)據(jù)項(xiàng)：數(shù)據(jù)元素的最小單位。一個(gè)數(shù)據(jù)元素由假設(shè)干個(gè)數(shù)據(jù)項(xiàng)組成(4)數(shù)據(jù)對(duì)象：相同性質(zhì)數(shù)據(jù)元素的集合。是數(shù)據(jù)的子集7.1.1根本術(shù)語數(shù)據(jù)對(duì)象、數(shù)據(jù)元素與數(shù)據(jù)項(xiàng)一列整數(shù)｛2，3，5，-3，8，12｝假設(shè)干列整數(shù)一個(gè)學(xué)生：學(xué)號(hào)、姓名、性別、入學(xué)成績。。。一個(gè)學(xué)生表：假設(shè)干條學(xué)生記錄7.1.2數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)：帶結(jié)構(gòu)的數(shù)據(jù)元素的集合。數(shù)據(jù)元素之間相互有關(guān)聯(lián)例如，3214，6587，9345—a1，a2，a3在a1、a2和a3之間存在“次序〞關(guān)系<a1,a2>、<a2、a3>不等于6587,3214,9345—a2,a1,a37.1.2數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)主要研究和討論3個(gè)方面的問題：①數(shù)據(jù)集合中，各種數(shù)據(jù)元素之間所固有的邏輯關(guān)系，即數(shù)據(jù)的邏輯結(jié)構(gòu)；②在對(duì)數(shù)據(jù)進(jìn)行處理時(shí)，各數(shù)據(jù)元素在計(jì)算機(jī)中的存儲(chǔ)關(guān)系，即數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)；③對(duì)各種數(shù)據(jù)結(jié)構(gòu)進(jìn)行的運(yùn)算，其中常用的有檢索、插入、刪除、排序等7.1.2數(shù)據(jù)結(jié)構(gòu)1.數(shù)據(jù)的邏輯結(jié)構(gòu)指反映數(shù)據(jù)元素之間邏輯關(guān)系的數(shù)據(jù)結(jié)構(gòu)。兩個(gè)要素：一是數(shù)據(jù)元素的集合，通常記為D；二是D上的二元關(guān)系，它反映了D中各數(shù)據(jù)元素之間的前驅(qū)與后繼關(guān)系，通常記為R。一個(gè)數(shù)據(jù)結(jié)構(gòu)可以表示成B=(D,R)，其中B表示數(shù)據(jù)結(jié)構(gòu)。通常把數(shù)據(jù)元素之間的這種固有的關(guān)系，簡單地用前驅(qū)與后繼關(guān)系來描述。例如家庭成員的數(shù)據(jù)結(jié)構(gòu)可以表示成B=(D,R)，其中D={父親，兒子，女兒}，R={<父親，兒子>，<父親，女兒>}。7.1.2數(shù)據(jù)結(jié)構(gòu)1.數(shù)據(jù)的邏輯結(jié)構(gòu)通常有下面3種根本結(jié)構(gòu)：①線性結(jié)構(gòu)：結(jié)構(gòu)中數(shù)據(jù)元素之間存在一個(gè)對(duì)一個(gè)的關(guān)系。②樹形結(jié)構(gòu)：結(jié)構(gòu)中數(shù)據(jù)元素之間存在一個(gè)對(duì)多個(gè)的關(guān)系。③圖形結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu)：結(jié)構(gòu)中數(shù)據(jù)元素之間存在多個(gè)對(duì)多個(gè)的關(guān)系。7.1.2數(shù)據(jù)結(jié)構(gòu)2.數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)空間中的存放形式稱為數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)〔也稱物理結(jié)構(gòu)〕。在數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)中，不僅要存放數(shù)據(jù)元素的信息，還需要存放各數(shù)據(jù)元素之間的前驅(qū)和后繼關(guān)系的信息。4種常見的存儲(chǔ)結(jié)構(gòu)：(1)順序存儲(chǔ)結(jié)構(gòu)(2)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)(3)索引存儲(chǔ)結(jié)構(gòu)(4)散列存儲(chǔ)結(jié)構(gòu)7.2線性表及其存儲(chǔ)結(jié)構(gòu)7.2.1線性表的根本概念通常，線性表是由n(n≥0)個(gè)數(shù)據(jù)元素a1,a2,…,an組成的一個(gè)有限序列。①存在唯一的一個(gè)被稱為“第一個(gè)〞的數(shù)據(jù)元素；②存在唯一的一個(gè)被稱為“最后一個(gè)〞的數(shù)據(jù)元素；③除了第一個(gè)之外，表中的每個(gè)數(shù)據(jù)元素均只有一個(gè)前驅(qū)；④除了最后一個(gè)之外，表中的每個(gè)數(shù)據(jù)元素均只有一個(gè)后繼。7.2.1線性表的根本概念線性表的數(shù)據(jù)元素，通常也稱為節(jié)點(diǎn)。數(shù)據(jù)元素在線性表中的位置只取決于它們自己的序號(hào)。線性表中節(jié)點(diǎn)的個(gè)數(shù)n稱為線性表的長度。當(dāng)

n=0時(shí)，稱為空表。7.2.2線性表的順序存儲(chǔ)及其運(yùn)算1.線性表的順序存儲(chǔ)〔順序表〕①線性表中的所有元素所占的存儲(chǔ)空間是連續(xù)的；②線性表中各數(shù)據(jù)元素在存儲(chǔ)空間中是按邏輯順序依次存放的。高級(jí)語言中，常用“一維數(shù)組〞a(1:m)表示這種存儲(chǔ)結(jié)構(gòu)7.2.2線性表的順序存儲(chǔ)及其運(yùn)算2.順序表的根本運(yùn)算(1)順序表的插入〔ai前插入x〕移動(dòng)元素：從最后一個(gè)〔即第n個(gè)〕元素開始，直到第i個(gè)元素之間共n-i+1個(gè)元素依次向后移動(dòng)一個(gè)位置ajaj+1(j:n~i)插入新元素：將新元素x插入到第i個(gè)位置xai更新長度：n+1n當(dāng)n=m時(shí)，不能再插入，否那么會(huì)“上溢〞；所以插入前要檢查是否會(huì)“上溢〞。7.2.2線性表的順序存儲(chǔ)及其運(yùn)算2.順序表的根本運(yùn)算(2)順序表的刪除(刪除ai)移動(dòng)元素：從第i+1個(gè)元素開始，直到第n個(gè)元素之間，共有ni個(gè)元素依次向前移動(dòng)一個(gè)位置。ajaj-1(j:i~n)更新長度：n-1n 當(dāng)n=0時(shí)不能再刪除，

否那么會(huì)“下溢〞；所以刪除前要檢查是否

會(huì)“下溢〞。7.2.2線性表的順序存儲(chǔ)及其運(yùn)算線性表的順序存儲(chǔ)結(jié)構(gòu)的特點(diǎn)具有簡單、存儲(chǔ)密度大、空間利用率高、對(duì)表中任一元素可直接確定其存儲(chǔ)地址〔隨機(jī)存取〕、效率高等優(yōu)點(diǎn)；但是也有明顯的缺乏：在順序表中進(jìn)行插入與刪除等操作時(shí)，需大量移動(dòng)數(shù)據(jù)元素，浪費(fèi)時(shí)間。因此，對(duì)于大的線性表，特別是元素變動(dòng)頻繁的大線性表，不宜采用順序存儲(chǔ)結(jié)構(gòu)，而是采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。7.2.3線性表的鏈?zhǔn)酱鎯?chǔ)及其運(yùn)算1.線性表的鏈?zhǔn)酱鎯?chǔ)通過每個(gè)節(jié)點(diǎn)的指針域?qū)個(gè)節(jié)點(diǎn)按其邏輯順序連接在一起而構(gòu)成的數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)，稱為鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。對(duì)線性鏈表而言，它不要求邏輯上相鄰的元素在物理位置上也相鄰，其存儲(chǔ)單元既可以是連續(xù)的，也可以是不連續(xù)的，甚至可以零散分布在存儲(chǔ)空間中的任何位置上。其中指針域next用于指向該節(jié)點(diǎn)的后繼節(jié)點(diǎn)datanext7.2.3線性表的鏈?zhǔn)酱鎯?chǔ)及其運(yùn)算1.線性表的鏈?zhǔn)酱鎯?chǔ)datanext7.2.3線性表的鏈?zhǔn)酱鎯?chǔ)及其運(yùn)算2.單鏈表的根本運(yùn)算(1)單鏈表的插入(2)單鏈表的刪除ADR(ai-1)ADR(x)ADR(ai-1)①ADR(ai-1).next

ADR(x).next②ADR(x)ADR(ai-1).next①ADR(ai-1).next.next

ADR(ai-1).next②釋放ADR(ai-1).next7.3棧和隊(duì)列7.3.1棧及其根本運(yùn)算1.什么是棧棧是限定在一端進(jìn)行插入和刪除的線性表。在棧中，允許插入和刪除的一端稱為棧頂，用指針

top來表示棧頂?shù)奈恢米⒁?，top的指向而不允許插入和刪除的另一端稱為棧底，用

bottom指向棧底注意，bottom的指向7.3.1棧及其根本運(yùn)算1.什么是棧棧也被稱為“先進(jìn)后出〞表或“后進(jìn)先出〞表。因此，棧具有記憶作用。例如：貨物堆放子彈夾函數(shù)的調(diào)用7.3.1棧及其根本運(yùn)算2.棧的順序存儲(chǔ)及其運(yùn)算在程序設(shè)計(jì)語言中，用一維數(shù)組

S(1:m)作為棧的順序存儲(chǔ)空間，其中m為棧的最大容量。初始狀態(tài)：bottom=1，top=0對(duì)棧的定義的進(jìn)一步理解一個(gè)棧的入棧序列是a,b,c,d,e，那么不可能的出棧序列是〔〕。A．edcba B．decbaC．dceab D．a(chǎn)bcde7.3.1棧及其根本運(yùn)算2.棧的順序存儲(chǔ)及其運(yùn)算(1)入棧運(yùn)算更新棧頂指針：top+1top插入新元素：xStop當(dāng)top=m時(shí)，說明棧空間已滿，不能再進(jìn)行入棧操作。否那么出現(xiàn)“上溢〞錯(cuò)誤。所以入棧之前，要檢查是否會(huì)“上溢〞top-->x7.3.1棧及其根本運(yùn)算2.棧的順序存儲(chǔ)及其運(yùn)算(2)退棧運(yùn)算讀棧頂元素：Stopx更新棧頂指針：top-1top當(dāng)top=0時(shí)，說明棧空，不能再進(jìn)行退棧運(yùn)算。否那么會(huì)出現(xiàn)“下溢〞錯(cuò)誤；所以退棧之前，要檢查是否會(huì)“下溢〞top-->-->x7.3.1棧及其根本運(yùn)算2.棧的順序存儲(chǔ)及其運(yùn)算(3)讀棧頂元素讀數(shù)：Stop

x棧頂指針保持不變當(dāng)

top=0

時(shí)，說明棧空，讀不到棧頂元素；所以讀數(shù)之前，要檢查是否為空棧。7.3.2隊(duì)列及其根本運(yùn)算1.什么是隊(duì)列指允許在一端進(jìn)行插入，而在另一端進(jìn)行刪除的線性表。允許插入的一端稱為隊(duì)尾，通常用一個(gè)稱為隊(duì)尾指針〔rear〕的指針指向隊(duì)尾元素的下一個(gè)位置注意，rear的指向允許刪除的一端稱為隊(duì)首，通常用一個(gè)稱為隊(duì)首指針〔front〕的指針指向隊(duì)首元素的位置注意，front的指向7.3.2隊(duì)列及其根本運(yùn)算1.什么是隊(duì)列隊(duì)列又稱為“先進(jìn)先出〞或“后進(jìn)后出〞的線性表，它表達(dá)了“先來先效勞〞的原那么。例如：排隊(duì)等候現(xiàn)象7.3.2隊(duì)列及其根本運(yùn)算1.什么是隊(duì)列在程序設(shè)計(jì)語言中，用一維數(shù)組

S(1:m)作為隊(duì)列的順序存儲(chǔ)空間，其中

m為隊(duì)列的最大容量初始狀態(tài)：front=rear=17.3.2隊(duì)列及其根本運(yùn)算1.什么是隊(duì)列入隊(duì)運(yùn)算插入新元素：xSrear更新隊(duì)尾指針：rear+1rear當(dāng)rear=m+1時(shí)，說明棧隊(duì)列滿，不能再入隊(duì)。否那么會(huì)出現(xiàn)“上溢〞錯(cuò)誤；所以入隊(duì)之前，要檢查是否會(huì)“上溢〞觀察：此時(shí)隊(duì)首前面可能還有空位置。rear-->x7.3.2隊(duì)列及其根本運(yùn)算1.什么是隊(duì)列出隊(duì)運(yùn)算讀隊(duì)首元素：Sfrontx更新隊(duì)首指針：front+1front當(dāng)front=rear時(shí)，不能再出隊(duì)了。否那么會(huì)出現(xiàn)“下溢〞錯(cuò)誤；所以出隊(duì)之前，要檢查是否會(huì)“下溢〞觀察：出隊(duì)后會(huì)留下空位置，但已不能繼續(xù)使用了——空間的浪費(fèi)！front-->--->x7.3.2隊(duì)列及其根本運(yùn)算2.循環(huán)隊(duì)列及其運(yùn)算將隊(duì)列存儲(chǔ)空間的最后一個(gè)位置繞到第一個(gè)位置，形成邏輯上的環(huán)狀空間，供隊(duì)列循環(huán)使用。當(dāng)隊(duì)尾指針rear=m+1時(shí)，那么置rear=1。當(dāng)隊(duì)首指針front=m+1時(shí)，那么置front=1。7.3.2隊(duì)列及其根本運(yùn)算2.循環(huán)隊(duì)列及其運(yùn)算7.3.2隊(duì)列及其根本運(yùn)算2.循環(huán)隊(duì)列及其運(yùn)算循環(huán)隊(duì)列隊(duì)滿時(shí)，有front=rear；而當(dāng)循環(huán)隊(duì)列空時(shí)，也有front=rear。解決方法：增加一個(gè)標(biāo)志s循環(huán)隊(duì)列初始狀態(tài)：front=rear=1，且s=07.3.2隊(duì)列及其根本運(yùn)算2.循環(huán)隊(duì)列及其運(yùn)算(1)入隊(duì)運(yùn)算插入新元素：xSrear更新隊(duì)尾指針和空否標(biāo)志：rear+1rear，當(dāng)rear=m+1時(shí)置rear=1，且如果此時(shí)s=0，那么置s=1，表示隊(duì)列非空。防止“上溢〞：入隊(duì)之前要檢查，是否s=1且font=rear7.3.2隊(duì)列及其根本運(yùn)算2.循環(huán)隊(duì)列及其運(yùn)算(2)出隊(duì)運(yùn)算讀隊(duì)首元素：Sfrontx更新隊(duì)首指針和空否標(biāo)志：front+1front，當(dāng)front=m+1時(shí)置front=1，且如果此時(shí)front=rear，那么說明隊(duì)空，應(yīng)置s=0。防止“下溢〞：出隊(duì)之前要檢查，是否s=0且font=rear7.4樹與二叉樹7.4.1樹的根本概念1.樹的定義樹是n(n

≥0)個(gè)節(jié)點(diǎn)的有限集T。當(dāng)n=0時(shí)，稱為空樹；當(dāng)n>0時(shí)，該集合滿足如下條件：①有且僅有一個(gè)根節(jié)點(diǎn)；②其余的節(jié)點(diǎn)可分為m(m

≥0)個(gè)互不相交的子集T1,T2,…,Tm，其中每個(gè)子集本身又是一顆樹，并稱其為根的子樹。這是一個(gè)遞歸定義，是表達(dá)“一對(duì)多〞的邏輯關(guān)系7.4.1樹的根本概念2.樹的根本術(shù)語①節(jié)點(diǎn)的度，例如：節(jié)點(diǎn)A的度為3，節(jié)點(diǎn)C的度為1②樹的度，例如：樹的度為3③葉子，例如：節(jié)點(diǎn)E，G，H，J，K，L，M④分支節(jié)點(diǎn)，例如：節(jié)點(diǎn)A，B，C，D，F(xiàn)，I⑤雙親和孩子，例如：節(jié)點(diǎn)A是B、C、D的雙親⑥節(jié)點(diǎn)的層，例如：節(jié)點(diǎn)E、F、G、H、I、J的層均為3⑦樹的深度，例如：圖中樹的深度為4⑧兄弟和堂兄弟⑨祖先和子孫⑩有序樹和無序樹森林度的概念的進(jìn)一步理解9．設(shè)樹T的度為4，其中度為1,2,3,4的結(jié)點(diǎn)數(shù)分別為4,2,1,1。那么T中的葉子結(jié)點(diǎn)數(shù)為〔〕。A．8 B．7 C．6D．5設(shè)樹的節(jié)點(diǎn)總數(shù)為n,度為0〔即葉子〕、1、2、3、4的結(jié)點(diǎn)個(gè)數(shù)分別設(shè)為n0,n1,n2,n3,n4.

那么n=n0+n1+n2+n3+n4=n0+4+2+1+1=n0+8;樹中結(jié)點(diǎn)總數(shù)也可以由樹中分支數(shù)B求得,度為1的結(jié)點(diǎn)就是有1個(gè)分支,度為2的結(jié)點(diǎn)就是有2個(gè)分支,度為3的結(jié)點(diǎn)就是有3個(gè)分支,度為4的結(jié)點(diǎn)就是有4個(gè)分支,度為0的葉子沒有分支,所以B＝1*n1+2*n2+3*n3+4*n4=15.從下向上看,除了根結(jié)點(diǎn),每個(gè)結(jié)點(diǎn)都有一個(gè)分支連著,所以n=B+1=16.所以葉子數(shù)n0為87.4.2二叉樹及其根本性質(zhì)1.二叉樹的定義二叉樹是n(n

≥0)個(gè)節(jié)點(diǎn)的有限集，它或者是空集(n=0)，或者是由一個(gè)根節(jié)點(diǎn)和兩顆互不相交且分別稱為根的左子樹和右子樹的二叉樹組成。在二叉樹中，每一個(gè)節(jié)點(diǎn)的度最大為2。二叉樹和度為2的樹是兩個(gè)不同的概念。一顆野生的二叉樹7.4.2二叉樹及其根本性質(zhì)2.二叉樹的根本性質(zhì)【性質(zhì)1】在二叉樹的第i層至多有2i-1個(gè)節(jié)點(diǎn)(i≥1)?！拘再|(zhì)2】深度為k的二叉樹至多有2k1個(gè)節(jié)點(diǎn)(k≥1)?！拘再|(zhì)3】對(duì)任何一顆二叉樹T，如果其葉子節(jié)點(diǎn)數(shù)為n0，度為2的節(jié)點(diǎn)數(shù)為n2，那么n0=n2+1?！拘再|(zhì)4】具有n(n≥1)個(gè)節(jié)點(diǎn)的完全二叉樹的深度為[logn]+1〔其中[logn]表示取logn的整數(shù)局部〕。7.4.2二叉樹及其根本性質(zhì)2.二叉樹的根本性質(zhì)滿二叉樹完全二叉樹非完全二叉樹完全二叉樹的深入理解10．設(shè)一棵完全二叉樹共有700個(gè)節(jié)點(diǎn)，那么該二叉樹中有_________________個(gè)葉子節(jié)點(diǎn)。7.4.3二叉樹的存儲(chǔ)結(jié)構(gòu)1.順序存儲(chǔ)結(jié)構(gòu)完全二叉樹的順序存儲(chǔ)結(jié)構(gòu)非完全二叉樹的順序存儲(chǔ)結(jié)構(gòu)7.4.3二叉樹的存儲(chǔ)結(jié)構(gòu)2.鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)7.4.4二叉樹的遍歷遍歷一棵二叉樹就是按照某種規(guī)那么去訪問二叉樹的每個(gè)節(jié)點(diǎn)，而且每個(gè)節(jié)點(diǎn)僅被訪問一次。在先左后右的約定下，根據(jù)訪問根節(jié)點(diǎn)的次序，二叉樹的遍歷可以分為:(1)先根遍歷例如：ABDFCE(2)中根遍歷例如：BFDACE(3)后根遍歷例如：FDBECA7.4.4二叉樹的遍歷練習(xí)：先根遍歷序列：

+a*b

cd/ef中根遍歷序列：a+b*c

d

e/f后根遍歷序列：abcd

*+ef/

二叉樹遍歷練習(xí)11．設(shè)一棵二叉樹的中序遍歷結(jié)果為DBEAFC，先序遍歷結(jié)果為ABDECF，那么該二叉樹的后序遍歷結(jié)果為_________________。7.5查找算法7.5查找算法1．定義查找就是根據(jù)給定的值，在一組數(shù)據(jù)中確定一個(gè)其數(shù)值等于給定值的數(shù)據(jù)元素，假設(shè)存在這樣的數(shù)據(jù)元素說明查找是成功的，否那么查找是不成功的。查找某個(gè)數(shù)據(jù)元素取決于數(shù)據(jù)中數(shù)據(jù)元素的組織方式。衡量查找算法好壞的標(biāo)準(zhǔn)是以平均查找比較的次數(shù)來定。7.5查找算法2．查找方法順序查找順序查找方法的平均查找比較次數(shù)為(n+1)/2。折半查找只能用于順序存儲(chǔ)的數(shù)據(jù)元素且各數(shù)據(jù)元素按關(guān)鍵字有序排列的序列。其根本思想是：假設(shè)查找表中的數(shù)據(jù)元素按關(guān)鍵字遞增有序排列，那么首先與“中間位置〞的元素比較，假設(shè)相等那么查找成功；假設(shè)給定值大于“中間位置〞的元素值，那么在后半部繼續(xù)進(jìn)行折半查找；否那么在前半局部進(jìn)行折半查找。當(dāng)在長度為n的表中使用折半查找時(shí)，最壞情況下的查找長度不超過log2n+17.5查找算法2．查找方法如果采用順序查找方法來查找21，需要比較4次；如果采用折半查找方法來查找21，需要比較3次序號(hào)1234567891011數(shù)據(jù)5131921375664758088927.6排序算法7.6排序算法1．選擇排序原始序列8921564885161947第1遍1621564885891947第2遍1619564885892147第3遍1619214885895647第4遍16192147

85895648第5遍1619214748895685第6遍161921474856

89

85第7遍16192147485685

897.6排序算法2．交換排序〔冒泡排序〕原始序列8921564885161947第1遍

218956488516194721568948851619472156488985161947215648858916194721564885168919472156488516198947

結(jié)果

2156488516194789第2遍

2156?4885?16?19?4789

結(jié)果

2148561619478589第3遍

214856?16?19?478589

結(jié)果

2148161947568589第4遍

2148?16?19?47568589

結(jié)果

2116194748568589

7.6排序算法2．交換排序〔冒泡排序〕原始序列8921564885161947第4遍

2148?16?19?47568589

結(jié)果

2116194748568589第5遍

21?16?