大學(xué)計(jì)算機(jī)基礎(chǔ) 第6章算法與數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)學(xué)習(xí)資料

本章概要(6學(xué)時)數(shù)據(jù)結(jié)構(gòu)的基本概念算法的基本概念典型的數(shù)據(jù)結(jié)構(gòu)典型算法

程序構(gòu)成：數(shù)據(jù)結(jié)構(gòu)

+算法6.1數(shù)據(jù)結(jié)構(gòu)的基本概念

PrivateSubCommand1_Click()DimRaAsInteger,RAsInteger'變量聲明

DimGAsInteger,BAsIntegerDimXPosAsInteger,YPosAsIntegerForRa=10To1000Step10'循環(huán)開始語句

R=255*Rnd()'賦值語句，將紅色設(shè)為隨機(jī)數(shù)

G=255*Rnd()'將綠色設(shè)為隨機(jī)數(shù)

B=255*Rnd()'將藍(lán)色設(shè)為隨機(jī)數(shù)

XPos=ScaleWidth/2'將x坐標(biāo)設(shè)在窗口中間

YPos=ScaleHeight/2'將y坐標(biāo)設(shè)置在窗口中間

Circle(XPos,YPos),Ra,RGB(R,G,B)'畫圓圈語句

Next'循環(huán)結(jié)束語句EndSub數(shù)據(jù)的組織形式和存儲方式。操作數(shù)據(jù)的步驟和方法

操作：插入、刪除或查找等。學(xué)號姓名性別出生日期班級專業(yè)21119001劉強(qiáng)男1990/02/13211190經(jīng)濟(jì)21119002王曉紅女1992/05/06211190經(jīng)濟(jì)24119901李明男1993/10/25241199會計(jì)24119902張宇男1994/06/14241199會計(jì)1.數(shù)據(jù)結(jié)構(gòu)示例特點(diǎn)：一行(記錄)/學(xué)生，由學(xué)號、姓名等多項(xiàng)構(gòu)成；兩行不完全相同，依學(xué)號由小到大存在前后關(guān)系。6項(xiàng)2.數(shù)據(jù)結(jié)構(gòu)的定義

數(shù)據(jù)結(jié)構(gòu)：具有相同特征、相互關(guān)聯(lián)的數(shù)據(jù)集合。數(shù)據(jù)也稱為數(shù)據(jù)元素或結(jié)點(diǎn)，現(xiàn)實(shí)世界中每個對象都可以抽象成數(shù)據(jù)元素。學(xué)生信息表：數(shù)據(jù)元素由多個數(shù)據(jù)項(xiàng)組成。向量{2，43，68，45，32}家庭成員{祖父、父親、兒子}數(shù)據(jù)元素由一個數(shù)據(jù)項(xiàng)組成，之間有層次上的高低關(guān)系。數(shù)據(jù)元素由一個數(shù)據(jù)項(xiàng)組成，之間有位置上的前后關(guān)系。6項(xiàng)數(shù)據(jù)結(jié)構(gòu)主要研究：1)數(shù)據(jù)邏輯結(jié)構(gòu)：數(shù)據(jù)元素間的固有關(guān)系。2)數(shù)據(jù)存儲(物理)結(jié)構(gòu)：數(shù)據(jù)元素在計(jì)算機(jī)中的存儲方式。3)算法：對數(shù)據(jù)的操作步驟和方法。3.數(shù)據(jù)邏輯結(jié)構(gòu)將元素描述成前后件(前驅(qū)與后繼)關(guān)系?？杀硎緸椋篠=(

D

,R

)。數(shù)據(jù)結(jié)構(gòu)

數(shù)據(jù)元素的集合，如：{一季度，三季度，二季度，四季度}數(shù)據(jù)元素之間前后件關(guān)系的集合(邏輯結(jié)構(gòu))，如：{(一季度，二季度)，(二季度，三季度)，(三季度，四季度)}4種基本邏輯結(jié)構(gòu)1)線性結(jié)構(gòu)：數(shù)據(jù)元素間存在一對一關(guān)系。首結(jié)點(diǎn)無前件，其他結(jié)點(diǎn)都有一個前件。末結(jié)點(diǎn)無后件，其他結(jié)點(diǎn)都只有一個后件。春夏冬秋春夏冬秋2)樹型結(jié)構(gòu)：數(shù)據(jù)元素之間存在一對多關(guān)系；結(jié)點(diǎn)最多有一個前件，可有多個后件；前件與后件之間有層次關(guān)系。3)圖形結(jié)構(gòu)：數(shù)據(jù)元素間存在多對多關(guān)系；結(jié)點(diǎn)可有多個前件和多個后件。4)

集合：一種松散結(jié)構(gòu)，數(shù)據(jù)元素只屬一個集合。根據(jù)數(shù)據(jù)元素間關(guān)系的復(fù)雜程度，數(shù)據(jù)邏輯結(jié)構(gòu)可分為線性結(jié)構(gòu)和非線性結(jié)構(gòu)。也稱線性表，有且只有一個開始和終端結(jié)點(diǎn)，且每個結(jié)點(diǎn)最多只有一個前件和后件。可有多個開始和終端結(jié)點(diǎn)，每個結(jié)點(diǎn)可有多個前件或后件。如：樹型結(jié)構(gòu)和圖型結(jié)構(gòu)。優(yōu)點(diǎn)：結(jié)點(diǎn)占用存儲空間最少。缺點(diǎn)：數(shù)據(jù)元素很多時，可能沒有足夠多的連續(xù)存儲單元，不能充分利用空閑單元，易產(chǎn)生碎片。4.數(shù)據(jù)物理結(jié)構(gòu)數(shù)據(jù)存儲結(jié)構(gòu)不僅要存放各數(shù)據(jù)元素，還要存放數(shù)據(jù)元素之間的前后件關(guān)系信息。1)順序存儲結(jié)構(gòu)：用存儲器中一塊連續(xù)單元存放數(shù)據(jù)，邏輯相鄰結(jié)點(diǎn)，物理位置也鄰接，邏輯關(guān)系由存儲單元的相鄰關(guān)系體現(xiàn)。地址2000H2002H2004H2006H春秋冬數(shù)據(jù)夏零散的空閑存儲單元。2)鏈?zhǔn)酱鎯Y(jié)構(gòu)：結(jié)點(diǎn)由數(shù)據(jù)域和指針域兩部分組成。通過指針反映元素間的邏輯關(guān)系。30011005400E春2000夏秋30011005400E冬存放數(shù)據(jù)元素存放前件或后件的存儲地址優(yōu)點(diǎn)：充分利用空閑存儲單元。缺點(diǎn)：保存結(jié)點(diǎn)指針，占用較多存儲單元。6.2.1算法的定義算法：解決問題采取的方法和步驟。算法定義于數(shù)據(jù)邏輯結(jié)構(gòu)，獨(dú)立于計(jì)算機(jī)；算法是程序的靈魂，依數(shù)據(jù)存儲結(jié)構(gòu)實(shí)現(xiàn)(運(yùn)行)。S1：輸入a、b、c的值；求aX2+bX+c=0解的算法S4：否則，輸出“無解”，結(jié)束。S3：否則，若b2-4ac≥0，則輸出：S2：若a=0，則輸出“非二次方程”Dima,b,cAsSinglea=Text1.Text:b=Text2.Textc=Text3.TextIfa=0Then

'Text4.Text="非二次方程"ElseIf

b^2-4*a*c>=0ThenText4.Text

=

(-b+Sqr(b^2-4*a*c))/(2*a)Text5.Text=(-b-Sqr(b^2-4*a*c))/(2*a)Else

Text5.Text=""Text4.Text="無解"EndIf算法的特征可行性確定性有窮性輸入性輸出性采取的方法和步驟可行，結(jié)果另人滿意。每步結(jié)果必須確定，不能有二義性。由有限步組成，并在有效時間內(nèi)完成。能從外界得到數(shù)據(jù)，不同輸入，可產(chǎn)生不同結(jié)果。要有結(jié)果，并能輸出，有一個或多個輸出。6.2.2算法的描述方法

S1：輸入n

的值；S2：如果n<1，則結(jié)束；S3：設(shè)t和i均為1；S4：t×i

存入t，i值增1；S5：如果i≤n，則轉(zhuǎn)S4；S6：輸出t

并結(jié)束。1)自然語言：人類語言。計(jì)算n!優(yōu)點(diǎn)：描述的算法通俗易懂，容易接受。缺點(diǎn)：描述不嚴(yán)格(如：n為何類型？)，易造成二義性，不易轉(zhuǎn)換成計(jì)算機(jī)語言程序。2)偽代碼語言：介于自然語言和計(jì)算機(jī)程序設(shè)計(jì)語言之間，為描述算法規(guī)定的語言。

Begin(算法開始)inputnifn<1thenreturn1

t1

idot×i

ti+1

iuntili>noutputtEnd(算法結(jié)束)是否優(yōu)點(diǎn)：容易轉(zhuǎn)換成計(jì)算機(jī)語言程序。

優(yōu)點(diǎn)：清晰、直觀、形象地反映控制結(jié)構(gòu)及操作過程。

3)流程圖描述算法：用幾何圖形表示操作，用流線指示算法的執(zhí)行方向。

輸入n的值是輸出t的值否開始結(jié)束n≥11

i1

tt×i

ti+1

ii≤n是否結(jié)束橢圓框：表示算法開始或結(jié)束。平行框：表示輸入或輸出。菱形框：表示條件判斷。矩形框：表示執(zhí)行。缺點(diǎn)：不便描述較復(fù)雜問題。

判斷條件是否執(zhí)行B執(zhí)行A當(dāng)型循環(huán)當(dāng)條件成立A直到型循環(huán)直到條件成立A4)N-S圖描述算法：是另一種流程圖形式，仍然用矩形表示執(zhí)行框。

輸入n的值否是結(jié)束1

t1

ii>nt×i

ti+1

i輸出t的值結(jié)束n≥16.2.3算法的評價(jià)

程序中算法設(shè)計(jì)得優(yōu)與劣，直接影響程序的運(yùn)行效率、穩(wěn)定性和可維護(hù)性。正確性可讀性健壯性執(zhí)行效率執(zhí)行時輸入正確數(shù)據(jù)能夠得到正確結(jié)果易理解、閱讀和實(shí)現(xiàn)，便于程序維護(hù)和完善。執(zhí)行的時間和空間性能對輸入的各種數(shù)據(jù)適當(dāng)提示和處理。如除數(shù)為0，負(fù)數(shù)開偶次方等。

同一問題的多個算法，執(zhí)行時間短，時間效率高；占存儲空間少，空間效率高?！?.2.4算法復(fù)雜度

算法復(fù)雜度是對算法效率的度量，是評價(jià)算法優(yōu)劣的重要依據(jù)。一個算法復(fù)雜度高低體現(xiàn)在運(yùn)行該算法所需要資源的多少。因而，算法復(fù)雜度包含時間復(fù)雜度和空間復(fù)雜度。包括時間資源和空間(即存儲器)資源時間復(fù)雜度指執(zhí)行算法所需時間:

執(zhí)行時間=語句執(zhí)行時間×語句執(zhí)行次數(shù)空間復(fù)雜度指在算法執(zhí)行過程中,所占用附加空間數(shù)量6.3典型數(shù)據(jù)結(jié)構(gòu)6.3.1線性表典型的線性表有棧、隊(duì)列、數(shù)組和串。

一組特征相同數(shù)據(jù)的有限序列：線性表長度：表中數(shù)據(jù)元素個數(shù)n(n≥0)。

空表：不含數(shù)據(jù)元素的線性表(n=0)。

元素序號：非空表中元素的確定位置號。

L={a1,a2,a3,……,an}n{(21119001,劉強(qiáng),男,1990/02/13,211190,經(jīng)濟(jì)),(21119002,王曉紅,女,1992/05/06,211190,經(jīng)濟(jì)),(24119901,李明,男,1993/10/25,241199,會計(jì))}

長度為3{春

,夏

,秋

,冬}

長度為41.線性表的定義順序存儲結(jié)構(gòu)的特點(diǎn)：所有元素占一段連續(xù)的存儲單元。各元素占存儲單元數(shù)相同，且按邏輯順序依次存放，即邏輯與存儲結(jié)構(gòu)一致。2.線性表的順序存儲線性表通常采用順序存儲結(jié)構(gòu)(順序表)或鏈?zhǔn)酱鎯Y(jié)構(gòu)(鏈表)。在L={a1,a2,a3,…,an}中，假設(shè)每個元素占d個單元，首地址Addr(a1)為K，則ai的首地址為:Addr(ai)=Addr(a1)+(i-1)×d=K+(i-1)×d。地址2000H2002H2004H2006H春秋冬數(shù)據(jù)夏{春,夏,秋,冬}，每個元素占2個單元，首地址Addr(春)為2000H，則秋(a3)的首地址為:2000H+(3-1)×2=2004H。隨機(jī)存儲結(jié)構(gòu)：元素首地址可由公式計(jì)算的存儲結(jié)構(gòu)。優(yōu)點(diǎn)：可隨機(jī)讀取元素，節(jié)省存儲空間。缺點(diǎn)：插入和刪除元素要移動大量元素，浪費(fèi)時間，導(dǎo)致時間效率較低，不能充分利用空閑單元。2004H2006H秋冬地址2000H春數(shù)據(jù)每個單鏈表都有頭指針，指向第一個結(jié)點(diǎn)，用于標(biāo)識一個單鏈表。每個結(jié)點(diǎn)只有一個指針域，存放后件結(jié)點(diǎn)的存儲地址，最后結(jié)點(diǎn)指針域?yàn)榭?Null或^)。3.線性表的單鏈表存儲3001^1005400E春2000夏秋30011005400E冬結(jié)點(diǎn)存儲空間可不連續(xù)，邏輯結(jié)構(gòu)與存儲結(jié)構(gòu)互相獨(dú)立，邏輯關(guān)系由指針域確定。Head：2000訪問鏈表：由頭指針找到第1個結(jié)點(diǎn)，再由指針域找其他結(jié)點(diǎn)，直到指針域?yàn)榭铡?/p>

J

S在J,L之間插入接點(diǎn)S

J

U^刪除接點(diǎn)L10

L

U^10202030103010

L10202020優(yōu)點(diǎn)：充分利用存儲單元，便于元素的插入和刪除。缺點(diǎn)：每個結(jié)點(diǎn)都有指針域，占較多存儲單元。優(yōu)點(diǎn)：從任意結(jié)點(diǎn)出發(fā)，均可找到其他結(jié)點(diǎn)；空與非空表統(tǒng)一操作。循環(huán)鏈表中增設(shè)一個表頭結(jié)點(diǎn)，其數(shù)據(jù)域值可任意，指針域指向第一個結(jié)點(diǎn)?？昭h(huán)鏈表只有表頭結(jié)點(diǎn)，自成環(huán)。4.線性表的循環(huán)鏈表存儲將單鏈表最后結(jié)點(diǎn)的指針域指向鏈表的第一個結(jié)點(diǎn)，即首尾相連。注意頭指針和表頭結(jié)點(diǎn)的區(qū)別3001^1005400E春2000夏秋30011005400E冬2000Head：20AB20AB20ABHead:20AB200020AB20AB允許插入和刪除的一端稱棧頂(top)，另一端稱棧底

(bottom)。6.3.2棧

在表的同一端插入和刪除運(yùn)算的線性表。1.棧的定義2.棧的基本運(yùn)算(操作)1)初始化棧：構(gòu)造一個空棧。2)空棧判斷：判斷棧是否空。3)入棧：棧頂插入元素。5)出棧：棧頂刪除元素，入出可交替進(jìn)行。4)讀棧：僅讀棧頂元素，不刪。棧底bottom棧頂top

A1A2A3A3A6A5A4A3A2

A1棧的特點(diǎn)：棧中后進(jìn)先出，或先進(jìn)后出。1)

入棧運(yùn)算算法：3.棧的順序存儲及運(yùn)算棧的順序存儲，低地址端為棧底，位置固定不變。用變量top表示棧頂位置，n表示棧中最多能容納元素的個數(shù)。S1：若top=n，則棧滿，結(jié)束入棧。S2：top+1

top。S3：新元素入棧頂位置(top)。棧底bottomn=5topA6A2

A1

A1A2A3A4A5top入棧失敗(上溢錯誤)

。1)

出棧運(yùn)算算法：S1：若top=0，則棧空，結(jié)束出棧。S3：top–1

top。S2：棧頂元素賦給變量

(出棧)。棧底bottomn=5topA3A2

A1出棧失敗(下溢錯誤)

。2.隊(duì)列的基本運(yùn)算6.3.3隊(duì)列一端插入、另一端刪除的線性表。插入的一端稱隊(duì)尾，刪除的一端稱隊(duì)頭。也稱先進(jìn)先出或后進(jìn)后出線性表。A2A1A3A4A51.定義1)初始化隊(duì)列：創(chuàng)建一個空隊(duì)列。2)空隊(duì)列判斷：判斷隊(duì)列是否為空。3)入隊(duì)運(yùn)算：隊(duì)尾插入元素。4)出隊(duì)運(yùn)算：隊(duì)頭刪除元素。5)讀元素：讀隊(duì)頭元素賦給一個變量。X：A16)隊(duì)列長度：求隊(duì)列中元素個數(shù)。長度：401234S1：若rear=n-1，則隊(duì)已滿，結(jié)束。

n=5用變量front指向隊(duì)列中第一個元素前位置，用rear指向隊(duì)列中最后元素位置。

n為隊(duì)列中容納元素?cái)?shù)。3.隊(duì)列順序存儲及其常用運(yùn)算1)初始化隊(duì)列：建空隊(duì)列，front=rear=-1。A2A3A4A5A1FrontRear2)入隊(duì)運(yùn)算(操作)A6S2：rear+1

rear。

S3：新元素放在隊(duì)尾位置(rear)。

01234入隊(duì)失敗(上溢錯誤)

。012343)

退隊(duì)運(yùn)算S1：若front=rear，則隊(duì)空,退隊(duì)失敗(下溢錯誤),結(jié)束退隊(duì)。S2：front+1

front。S3：取front所指元素。A2A3A4A5A1FrontRear隊(duì)中有空位，但不能插入新元素。出現(xiàn)假溢出入隊(duì)時尾指針追頭，出隊(duì)時頭指針追趕尾。front=rear時，隊(duì)可能空或滿，要增加變量(Flag)

標(biāo)識列滿或空。6.3.4循環(huán)隊(duì)列×將隊(duì)列存儲空間視為首尾相連的環(huán)狀，即形成邏輯上環(huán)形空間。0213401234FrontRearFrontRear1.循環(huán)隊(duì)列的定義2.循環(huán)隊(duì)列的常用運(yùn)算(操作)A5A1A2A3A4Flag=0，隊(duì)列空

RearRearRearFlag=1，隊(duì)列滿

Flag=0Flag=1S3：元素放在隊(duì)尾(rear)，1

flag。S2：若rear+1=n，則0

rear；否則rear+1

rear。1)初始化：創(chuàng)建空隊(duì)列，并設(shè)置Front=0，

Rear=0，F(xiàn)lag=0。02134FrontRearFlag=02)入隊(duì)運(yùn)算(操作)S1：若front=rear且flag=1，則隊(duì)滿，并結(jié)束入隊(duì)。A5A1A2A3A4A6Flag=1入隊(duì)失敗(上溢錯誤)RearRearRear出隊(duì)后再進(jìn)。S3：0

flag，元素出隊(duì)。S2：若(front+1)=n，則0

front

；否則front+1

front。02134FrontRearFlag=03)出隊(duì)運(yùn)算(操作)S1：若front=rear且flag=0，則隊(duì)空，結(jié)束出隊(duì)。A1A2A3A4Flag=1出隊(duì)失敗(下溢錯誤)Rear6.3.5

樹樹是n(n≥0)個結(jié)點(diǎn)組成的有限集合。當(dāng)n=0時，稱為空樹；否則，有且僅有一個根結(jié)點(diǎn)。一棵樹由根及若干子樹構(gòu)成，每棵子樹又是由更小的子樹構(gòu)成。上端結(jié)點(diǎn)是前件，下端結(jié)點(diǎn)是后件(子結(jié)點(diǎn))。根結(jié)點(diǎn)沒有前件，其他結(jié)點(diǎn)只有一個前件。葉結(jié)點(diǎn)：沒有后件的結(jié)點(diǎn)。結(jié)點(diǎn)的度：結(jié)點(diǎn)擁有后件的個數(shù)。E結(jié)點(diǎn)的度為3。D結(jié)點(diǎn)的度為0。樹的度：樹中所有結(jié)點(diǎn)的最大度。樹的度為4。第一層第二層第三層第四層樹的深度：樹中結(jié)點(diǎn)的最大層次數(shù)，也稱高度。樹的高度為4。存儲結(jié)構(gòu)上，每個結(jié)點(diǎn)都是一個存儲記錄，用鏈接指針實(shí)現(xiàn)記錄之間的聯(lián)系。吉林大學(xué)8306831683018310法學(xué)院8401841084218306物理學(xué)院8801881088218310經(jīng)濟(jì)學(xué)院8601861086218316理化所960196108301教師99019910…8601管理人員99519961…8621學(xué)生99319936…8610指針實(shí)現(xiàn)樹結(jié)構(gòu)存儲，需要大量指針域，結(jié)點(diǎn)的指針域需要動態(tài)分配或按樹的度進(jìn)行設(shè)置。6.3.6二叉樹特點(diǎn)：非空二叉樹有且只有一個根結(jié)點(diǎn)；結(jié)點(diǎn)最多有兩棵子樹,且分左右。ATXCZYBP每個結(jié)點(diǎn)最多有兩個后件(即樹的度為2)。1.二叉樹及其特點(diǎn)

5種基本形態(tài)

空只有根只有左左右均有只有右2.二叉樹基本性質(zhì)

1.性質(zhì)1：第i層最多有2i-1個結(jié)點(diǎn)(i≥1)。ATXCEMBPSDNFRYQ第1層≤21-1=1個結(jié)點(diǎn)第2層≤22-1=2個結(jié)點(diǎn)第3層≤23-1=4個結(jié)點(diǎn)第4層≤24-1=8個結(jié)點(diǎn)2.性質(zhì)2：深度為k的二叉樹，最多2k-1個結(jié)點(diǎn)(k≥1)。結(jié)點(diǎn)總數(shù)：1

+2

+4

+8

≤24-13.性質(zhì)3：二叉樹度為0的結(jié)點(diǎn)比度為2的結(jié)點(diǎn)多1個。度為2的結(jié)點(diǎn)：7個度為0的結(jié)點(diǎn)：8個度為2的結(jié)點(diǎn)：7-2度為0的結(jié)點(diǎn)：8-2×MFERCBATXSDYPNQ3.滿二叉樹是2k-1個結(jié)點(diǎn)、深度為k的二叉樹。每一層結(jié)點(diǎn)數(shù)都達(dá)到最大值，葉結(jié)點(diǎn)都在最底同一層。非滿二叉樹葉結(jié)點(diǎn)4.完全二叉樹及其性質(zhì)深度為k的二叉樹,若第1至k-1層是滿二叉樹，第k層都滿放最左邊,則稱完全二叉樹。√×注：滿二叉樹是完全二叉樹，反之未必成立。性質(zhì)4：n個結(jié)點(diǎn)的完全二叉樹的深度為

log2n」+1。

log212」+1=3+1ATXCRBPSEGFY性質(zhì)5：n個結(jié)點(diǎn)的完全二叉樹,結(jié)點(diǎn)從上到下，從左到右編號1、2、…、n，對編號為k的結(jié)點(diǎn)有：ATXCRBPSEQFY123456710119812k=1為根結(jié)點(diǎn)。k>1，k結(jié)點(diǎn)的父結(jié)點(diǎn)編號為int(k/2)。2k<=n，k結(jié)點(diǎn)的左子結(jié)點(diǎn)為2k，否則無左子結(jié)點(diǎn)。2k+1<=n，k結(jié)點(diǎn)的右子結(jié)點(diǎn)為2k+1,否則無右子結(jié)點(diǎn)。2×7＞12，無左子樹2×6+1＞12，無右子樹5.二叉樹的順序存儲完全二叉樹按編號順序存儲容易計(jì)算出結(jié)點(diǎn)的父、子結(jié)點(diǎn)。ATXCRBPSEQFY123456710119812ATXSBCPYERFQ123456710119812根，左子2×1=2—T，右子2×1+1=3—X父int(2/2)=1—A，左子2×2=4—S，右子2×2+1=5—B父int(5/2)=2—T，左子2×5=10—R，右子2×5+1=11—F普通二叉樹可整理成完全二叉樹后編號，再順序存儲。ATXCPSEQY123456710119812ATXCZYBP深度為4ABT∧TX∧B∧∧C∧P∧∧Y∧∧Z左指針域數(shù)據(jù)域

右指針域6.二叉樹的鏈?zhǔn)酱鎯Y(jié)點(diǎn)由數(shù)據(jù)域和左、右兩個指針域組成。有許多空指針。7.二叉樹遍歷按照某種順序，訪問二叉樹中結(jié)點(diǎn)的過程，訪問每個結(jié)點(diǎn)一次，且僅一次。根據(jù)訪問根的次序，分先序、中序和后序遍歷。ATXCZYBP1)先序遍歷

訪問根結(jié)點(diǎn)先序遍歷左子樹先序遍歷右子樹遍歷結(jié)果：AT無左子樹，故遍歷右子樹BZXCPYATXCZYBP2)中序遍歷中序遍歷左子樹訪問根結(jié)點(diǎn)中序遍歷右子樹遍歷結(jié)果：AT無左子樹，故遍歷子根BZXCPYATXCZYBP2)后序遍歷后序遍歷左子樹后序遍歷右子樹訪問根結(jié)點(diǎn)遍歷結(jié)果：AT無左子樹，故遍歷右子樹BZXCPY6.4典型算法6.4.1查找是在數(shù)據(jù)集合中查找數(shù)據(jù)元素的過程，又稱檢索。若存在，則查找成功；否則，查找失敗。

1.

順序查找：適于線性表。從第一個元素開始，用給定值與表中各元素依次比較。若相等，則查找成功，結(jié)束。若直到最后都沒找到，則查找失敗。(88，15，23，80，63，8，86，46，71，101)71比較9次，查找成功！90比較10次，查找失敗！1)

鏈?zhǔn)酱鎯Γ?)順序存儲，但元素?zé)o序。2.二分查找要求對順序存儲且元素升序或降序排列的有序表查找，又稱折半查找。基本思想：設(shè)表升序排列。給定值與中間元素比較，若相等，則查找成功，結(jié)束；若小于中間元素，則對前半再折半查找；若大于中間元素，則對后半再折半查找。直到查找成功或范圍為0個元素(查找失敗)。(8，15，23，63，65，71，80，86，91，99)12345678910查找元素序號區(qū)間為[L…R]，中間位置為mid=

(L+R)/2」。即首尾序號相加除2取整數(shù)。如：[1…10]中間位置5，[6…10]中間位置8。71中間位置為5。中間位置為8，71<86，應(yīng)該在前半中查找。中間位置為6，相等，比較3次查找成功。71>65，應(yīng)該在后半中查找。6060<65，應(yīng)該在前半中查找。中間位置為2，60>15，應(yīng)該在后半中查找。中間位置為3，