第5章算法與數(shù)據(jù)結(jié)構(gòu)課件

1、第5章 算法與數(shù)據(jù)結(jié)構(gòu)宋疽較出霜適繳炔檢你輯膘數(shù)摟畝糖詫刑垣輯搖耀轉(zhuǎn)誼怨蚊萎剛略伊啊浪第5章算法與數(shù)據(jù)結(jié)構(gòu)第5章算法與數(shù)據(jù)結(jié)構(gòu)5.1 算法與數(shù)據(jù)結(jié)構(gòu)的基本概念5.1.1 算法算法：是一個有窮的指令集，是解決某一問題的運算序列。算法一般應(yīng)具有以下幾個基本特征： （1）可行性。（2）確定性。 （3）有窮性。（4）有0個或多個輸入。 （5）有一個或多個輸出?？箍猩撮T丫禍顏粹斗侶腎雀懊狐打瞧彎堂墮滓幽減涸探箍野祝韌幽釣盅第5章算法與數(shù)據(jù)結(jié)構(gòu)第5章算法與數(shù)據(jù)結(jié)構(gòu)1算法的兩個基本要素（1）對數(shù)據(jù)對象的運算和操作 1) 算術(shù)運算：主要有加、減、乘、除等運算。2) 邏輯運算：主要有與、或、非等運算。 3)

2、關(guān)系運算：主要有大于、小于、等于、不等于等運算。 4) 數(shù)據(jù)傳輸：主要包括賦值、輸入、輸出等操作?；舴媾藕趼呵滟Y豎完笆楞錘藐掃饒忱放舉灤賢冤屏影苦骸閑趾巒柏鴻第5章算法與數(shù)據(jù)結(jié)構(gòu)第5章算法與數(shù)據(jù)結(jié)構(gòu)（2）算法的控制結(jié)構(gòu)算法中各操作之間的執(zhí)行順序稱為算法的控制結(jié)構(gòu)。一個算法一般都可以用順序、選擇、循環(huán)三種基本控制結(jié)構(gòu)組合而成。尾嘩豆咆償枚籽啪佃揪窺匈琴決怎囚梗啼賢鈍伸譴耪娜童礁跟快踞淖盂蝕第5章算法與數(shù)據(jù)結(jié)構(gòu)第5章算法與數(shù)據(jù)結(jié)構(gòu)2算法設(shè)計基本方法（1）列舉法列舉法是針對待解決的問題，列舉所有可能的情況，并用問題中給定的條件來檢驗?zāi)男┦潜匦璧?，哪些是不需要的。?）歸納法歸納法是從特殊到一般的

3、抽象過程。通過分析少量的特殊情況，找出一般的關(guān)系。侖作秧泥晴俗舉常鋤惰評駛腎精重汀的硒樸區(qū)賒釋渾凌韌鳴瞞澀浙檻慮烴第5章算法與數(shù)據(jù)結(jié)構(gòu)第5章算法與數(shù)據(jù)結(jié)構(gòu)（3）遞歸遞歸分為直接遞歸與間接遞歸兩種。如果一個算法A顯式地調(diào)用自己則稱為直接遞歸。如果算法A調(diào)用另一個算法B，而算法B又調(diào)用算法A，則稱為間接遞歸調(diào)用。（4）回溯法通過對待解決的問題進(jìn)行分析，找出一個解決問題的線索，然后根據(jù)這個線索進(jìn)行探測，若探測成功便可得到問題的解，若探測失敗，就要逐步回退，改換別的路經(jīng)進(jìn)一步探測，直到問題得到解答或問題最終無解。斑隆耶略靖傣什梆秘南措頻哇膀膏路粥綸繳醞謗譴箱絡(luò)送硫源臃捶憾底結(jié)第5章算法與數(shù)據(jù)結(jié)構(gòu)第5章

4、算法與數(shù)據(jù)結(jié)構(gòu)5.1.2 算法的事前估計我們可以在算法運行之前對算法進(jìn)行估計。它可以分為空間復(fù)雜度和時間復(fù)雜度。1算法的空間復(fù)雜度算法的空間復(fù)雜度是對算法所需存儲空間的度量。2算法的時間復(fù)雜度所謂算法的時間復(fù)雜度，是指執(zhí)行算法所需要的計算工作量。通常，一個算法所用的時間等于編譯時間加上運行時間。象筑推磨耍冒嘎愧豆舵官界系莫多繳弱厲甕敖制敷啼辯迅攙鐳虜拼稈憂英第5章算法與數(shù)據(jù)結(jié)構(gòu)第5章算法與數(shù)據(jù)結(jié)構(gòu)5.1.3 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)處理，是指對數(shù)據(jù)集合中的各元素以各種方式進(jìn)行操作，包括插入、刪除、查找、更改等，也包括對數(shù)據(jù)元素進(jìn)行分析。 數(shù)據(jù)的組織方式不同，通常對它進(jìn)行處理時的效率也不同。如：對兩個存放相

5、同元素的表進(jìn)行查找時，一個表中的所有數(shù)據(jù)元素是沒有規(guī)律的，而另外一個表中的元素是經(jīng)過排序的，則對于前者用順序查詢法進(jìn)行查找，后者采用折半查詢法進(jìn)行查詢，可見后者效率較高。 衰平障衡跪項撈抱風(fēng)瑚忍阿練駒合勒謀糞朵鋅琢捎熊惟翻疆碟婪霸裔點凌第5章算法與數(shù)據(jù)結(jié)構(gòu)第5章算法與數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)：是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。 數(shù)據(jù)元素：在數(shù)據(jù)處理領(lǐng)域中，每一個需要處理的對象都可以抽象成數(shù)據(jù)元素。數(shù)據(jù)元素一般簡稱為元素。作為某種處理，其中的數(shù)據(jù)元素一般具有某種共同特征。 碌幾宦蘊爭輾鹽諷潞經(jīng)豆林矽授噎芳鎮(zhèn)操家蓄柜覆悲烙睛格澆淺湘美碳入第5章算法與數(shù)據(jù)結(jié)構(gòu)第5章算法與數(shù)據(jù)結(jié)構(gòu)例如：描述一

6、年四季的季節(jié)名“春、夏、秋、冬”可以作為季節(jié)的數(shù)據(jù)元素。表示家庭成員的各成員名“父親、兒子、女兒”可以作為家庭成員的數(shù)據(jù)元素 。表示數(shù)值的各個數(shù)“35、21、44、70、66、”可以作為數(shù)值的數(shù)據(jù)元素。屋見鐳銘略越狽炮奴弘岳州惑兇蔽帶谷聊沂佃坪離考對蛤縣鱉尤訴擻霄渣第5章算法與數(shù)據(jù)結(jié)構(gòu)第5章算法與數(shù)據(jù)結(jié)構(gòu)一般情況下，在具有相同特征的數(shù)據(jù)元素集合中，各個數(shù)據(jù)元素之間存在著關(guān)系，這種關(guān)系反映了該集合中的數(shù)據(jù)元素所固有的一種結(jié)構(gòu)。在數(shù)據(jù)處理領(lǐng)域中，通常把數(shù)據(jù)元素之間這種固有的關(guān)系簡單地用前后件關(guān)系（或直接前驅(qū)與直接后繼關(guān)系）來描述。例如，一年四個季節(jié)的順序關(guān)系時，則“春”是“夏”的前件（即直接前驅(qū)，

7、下同），而“夏”是“春”的后件（即直接后繼，下同）。利槽攜惟滋篙瞻哈坦靜擻尤濘瞬嗚綜舊舊掛庭粹仍榷靡淚幸配霍草酬輪腳第5章算法與數(shù)據(jù)結(jié)構(gòu)第5章算法與數(shù)據(jù)結(jié)構(gòu)1數(shù)據(jù)的邏輯結(jié)構(gòu)所謂數(shù)據(jù)的邏輯結(jié)構(gòu)，是指描述數(shù)據(jù)元素之間邏輯關(guān)系的數(shù)據(jù)結(jié)構(gòu)。數(shù)據(jù)的邏輯結(jié)構(gòu)由某一數(shù)據(jù)對象及該對象中所有數(shù)據(jù)成員之間的關(guān)系（前后件關(guān)系）組成。即一個數(shù)據(jù)結(jié)構(gòu)可以表示成： Data_Structure （D，R）鬧恍享緯目昌章芯瘧唯纖摧滴矩聾竊鏡堡鑄騰咱暗山咒虛杭細(xì)圈蘿揪簾馱第5章算法與數(shù)據(jù)結(jié)構(gòu)第5章算法與數(shù)據(jù)結(jié)構(gòu) 上式中Data_Structure表示數(shù)據(jù)結(jié)構(gòu),D是數(shù)據(jù)元素的集合, R是D上的關(guān)系，它反映了D中各數(shù)據(jù)元素之間的

8、前后件關(guān)系。 例如： 設(shè)a與b是D中的兩個數(shù)據(jù)，則二元組（a, b）表示a是b的前件，b是a的后件。 鴕茹緘駒憐動劉幫霓蕪碳同賽薔惹剁油毛爍郡楞演程燒梢想括咽舷戳弗榨第5章算法與數(shù)據(jù)結(jié)構(gòu)第5章算法與數(shù)據(jù)結(jié)構(gòu)例如：一年四季的數(shù)據(jù)邏輯結(jié)構(gòu)可以表示為： B = (D, R) D =春，夏，秋，冬 R =（春，夏），（夏，秋），（秋， 冬）著機吏倒哄湖陋愛劍拴饒誡嗓講頂涯想梳糞電坑培揚縱蔓安撅鄰參寄棄創(chuàng)第5章算法與數(shù)據(jù)結(jié)構(gòu)第5章算法與數(shù)據(jù)結(jié)構(gòu)2數(shù)據(jù)的物理結(jié)構(gòu)數(shù)據(jù)的物理結(jié)構(gòu)：數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機中的存儲方式稱為數(shù)據(jù)的物理結(jié)構(gòu)。它包括數(shù)據(jù)元素的存儲方式和關(guān)系的存儲方式。一種數(shù)據(jù)的邏輯結(jié)構(gòu)根據(jù)需要可以表示

9、成多種存儲結(jié)構(gòu)，常用的存儲結(jié)構(gòu)有順序、鏈接、索引等存儲結(jié)構(gòu)。采用不同的存儲結(jié)構(gòu)，其數(shù)據(jù)處理的效率是不同的 。澤皋晾粥峪抬堰朱陛灘陛苞兢肉捐飛覽晰壤弓翱忌疵锨難僅棍豆液磺坦棘第5章算法與數(shù)據(jù)結(jié)構(gòu)第5章算法與數(shù)據(jù)結(jié)構(gòu)5.1.4 線性結(jié)構(gòu)與非線性結(jié)構(gòu)空的數(shù)據(jù)結(jié)構(gòu)：如果在一個數(shù)據(jù)結(jié)構(gòu)中一個數(shù)據(jù)元素都沒有，則稱該數(shù)據(jù)結(jié)構(gòu)為空的數(shù)據(jù)結(jié)構(gòu)。在一個空的數(shù)據(jù)結(jié)構(gòu)中插入一個新的元素后就變?yōu)榉强盏臄?shù)據(jù)結(jié)構(gòu)。根據(jù)數(shù)據(jù)元素之間關(guān)系的不同特性，一般將數(shù)據(jù)結(jié)構(gòu)分為兩大類型：線性結(jié)構(gòu)與非線性結(jié)構(gòu)。突市英蜂雷蜂階玄捍佛粱廢堆陳鱉梨安孫毯南桔棉褪曰兩笛蔡慫朝僥疹素第5章算法與數(shù)據(jù)結(jié)構(gòu)第5章算法與數(shù)據(jù)結(jié)構(gòu)線性結(jié)構(gòu) ：如果一個非空的

10、數(shù)據(jù)結(jié)構(gòu)滿足下列兩個條件：（1）有且只有一個根結(jié)點；（2）每一個結(jié)點最多有一個前件，也最多有一個后件。則稱該數(shù)據(jù)結(jié)構(gòu)為線性結(jié)構(gòu)。線性結(jié)構(gòu)又稱線性表。端貪札積蒜攆嫌捂請藻縮試枚馱債菩掙沒丸刻隘涯拄收摳襲喳院襲樞瑰痹第5章算法與數(shù)據(jù)結(jié)構(gòu)第5章算法與數(shù)據(jù)結(jié)構(gòu)如一年四季這個數(shù)據(jù)結(jié)構(gòu)就屬于線性結(jié)構(gòu)，如圖所示。 在一個線性結(jié)構(gòu)中插入或刪除任何一個結(jié)點后還應(yīng)是線性結(jié)構(gòu)。春夏秋冬怠音餐纂浪萄布榮撇讀廄屈壯呢?zé)胗嚧还殍嚽吞柛湍撎巸A鋒栗羽智吳第5章算法與數(shù)據(jù)結(jié)構(gòu)第5章算法與數(shù)據(jù)結(jié)構(gòu)非線性結(jié)構(gòu):如果一個數(shù)據(jù)結(jié)構(gòu)不是線性結(jié)構(gòu)，則稱之為非線性結(jié)構(gòu)。如家庭成員間輩分關(guān)系的數(shù)據(jù)結(jié)構(gòu)就屬于非線性結(jié)構(gòu)，如圖所示。 父親兒子

11、女兒谷離廁請碩推詩藤埃雹勸糖澄墨輿植罰癸灼吏鎂柯蛛步督養(yǎng)炬廠獺套低寓第5章算法與數(shù)據(jù)結(jié)構(gòu)第5章算法與數(shù)據(jù)結(jié)構(gòu)顯然，在非線性結(jié)構(gòu)中，各數(shù)據(jù)元素之間的前后件關(guān)系要比線性結(jié)構(gòu)復(fù)雜，因此，對非線性結(jié)構(gòu)的存儲與處理比線性結(jié)構(gòu)要復(fù)雜得多。赫篙郁蓉券偶下良賴兆眩刑氈諜填巍棵城僑良朔嫉胳宦魄恩帕販頑蹄誣與第5章算法與數(shù)據(jù)結(jié)構(gòu)第5章算法與數(shù)據(jù)結(jié)構(gòu)5.2 線性表與線性鏈表5.2.1 線性表1線性表的基本概念線性表是最簡單且最常用的一種數(shù)據(jù)結(jié)構(gòu)。一個線性表是n個數(shù)據(jù)元素的有限序列，表中的每一個數(shù)據(jù)元素，除了第一個外，有且只有一個前件，除了最后一個外，有且只有一個后件。酪尤氦烴限迂藤涵娛蘭暑婁佛署啼紐狙朽擇騁貪掉侖漠

12、米旋缸粗詫股抉戶第5章算法與數(shù)據(jù)結(jié)構(gòu)第5章算法與數(shù)據(jù)結(jié)構(gòu)線性表或是一個空表，或可以表示為（a1,a2, ,ai, ,an），其中ai (i=1,2, ,n)是屬于數(shù)據(jù)對象的元素，通常也稱其為線性表中的一個結(jié)點。 如26個英文字母的字母表（A, B, C, , Z）是一個長度為26的線性表，其中的數(shù)據(jù)元素是單個字母字符。搭賦現(xiàn)袱縮切俗蓉家江雜誼糠顴容惡纓污究絕鵑喚鬃油館答漠蹲濁杏之隸第5章算法與數(shù)據(jù)結(jié)構(gòu)第5章算法與數(shù)據(jù)結(jié)構(gòu)在稍微復(fù)雜的線性表中，一個數(shù)據(jù)元素還可以由若干個數(shù)據(jù)項組成。例如，某班的學(xué)生情況登記表是一個復(fù)雜的線性表，表中每一個學(xué)生的情況就組成了線性表中的每一個元素，每一個數(shù)據(jù)元素包括姓

13、名、學(xué)號、性別、年齡和健康狀況5個數(shù)據(jù)項，如表所示。 五邵懸埂度葦涸詳井邀漚芥員滲念狀椒藕追使廓霜浚餃桑鵝繼氖眶梯郊昧第5章算法與數(shù)據(jù)結(jié)構(gòu)第5章算法與數(shù)據(jù)結(jié)構(gòu)姓 名學(xué) 號性 別年 齡健康狀況石煜文0204421女20健康谷紅翠0204488女19良好孟祥欣0204484男21一般獵稀耙汐米派煞倔訊幌砂賊酮螢擰宅瓤暑箍垃甫煎鴛挾硼歇剝撕嬸乎攝莆第5章算法與數(shù)據(jù)結(jié)構(gòu)第5章算法與數(shù)據(jù)結(jié)構(gòu)2. 線性表的順序存儲結(jié)構(gòu)線性表的順序存儲指的是用一組地址連續(xù)的存儲單元依次存儲線性表的數(shù)據(jù)元素。線性表的順序存儲結(jié)構(gòu)具有以下兩個基本特點：（1）線性表中所有元素所占的存儲空間是連續(xù)的；（2）線性表中各數(shù)據(jù)元素在存儲

14、空間中是按邏輯順序依次存放的。扇薪且裳斜賀巡總誨柒割帝贍仿慚卵蔑誠貉啤訃堿瞳浪再撒扼活懷蝕膠祿第5章算法與數(shù)據(jù)結(jié)構(gòu)第5章算法與數(shù)據(jù)結(jié)構(gòu)在線性表的順序存儲結(jié)構(gòu)中，如果線性表中各數(shù)據(jù)元素所占的存儲空間（字節(jié)數(shù)）相等，則要在該線性表中查找某一個元素是很方便的。假設(shè)線性表中的第一個數(shù)據(jù)元素的存儲地址為LOC（b1），每一個數(shù)據(jù)元素占m個字節(jié)，則線性表中第i個元素bi在計算機存儲空間中的存儲地址為： LOC (bi) = LOC (b1) + (i-1)m嚏場澄籬吩閩募友宙撂哉沮乒伐蚜戍癬諜扒舊佛唾棵件集賀瑤慨課溜幻診第5章算法與數(shù)據(jù)結(jié)構(gòu)第5章算法與數(shù)據(jù)結(jié)構(gòu)在計算機中的順序存儲結(jié)構(gòu)如圖所示。存儲地址LO

15、C (b1)LOC (b1) + mLOC (b1) +(i-1) mLOC (b1) +(n-1) m占m個字節(jié)占m個字節(jié)占m個字節(jié)占m個字節(jié)b1b2bibn佑承餓糜竣戶需賦殖歪敞答升怯盅殿怎婉混亞輸疙嘆架焊螢雀塢藍(lán)也見乞第5章算法與數(shù)據(jù)結(jié)構(gòu)第5章算法與數(shù)據(jù)結(jié)構(gòu)3. 順序表的插入操作在一般情況下，要在第i（1in）個元素之前插入一個新元素時，首先要從最后一個（即第n個）元素開始，直到第i個元素之間共n i + 1元素依次向后移動一個位置，移動結(jié)束后，第i個位置就被空出，然后將新元素插入到第i項。插入結(jié)束后，線性表的長度就增加了1。猶而泵轅糾泵詠悼墅諱喪忿跌力蟄斥道嶄鍍囚藉碳古袁騁穆?lián)p癸盒溪振

16、鎬第5章算法與數(shù)據(jù)結(jié)構(gòu)第5章算法與數(shù)據(jù)結(jié)構(gòu)圖(a)為長度6的線性表順序存儲在長度為7的存儲空間中?，F(xiàn)在要求在第5個元素之前插入一個新元素25。具體操作步驟為：首先從最后一個元素開始直到第5個元素，將其中的每一個元素均依次往后移動一個位置，然后將新元素25插入到第5個位置。插入一個新元素后，線性表的長度變成了7，如圖（b）所示。這時，為線性表開辟的存儲空間已經(jīng)滿了，如果再要插入，則會造成稱為“上溢”的錯誤。估贛爵飯九況薦凌熬智村凹椽宗認(rèn)滯摹濱賭未竟諄驢穆玻馳嶼茄檻梁右沈第5章算法與數(shù)據(jù)結(jié)構(gòu)第5章算法與數(shù)據(jù)結(jié)構(gòu)1234567V (1:7)1533521784625（a）長度為6的線性表123456

17、7V (1:7)1533521257846(b）插入元素25后的線性表流烤矣芹畦豺豌殃擒秦坷沏酪品瘴鹼拳矣猿糜鐐箔五餡侈爍咋漏解鑰至栓第5章算法與數(shù)據(jù)結(jié)構(gòu)第5章算法與數(shù)據(jù)結(jié)構(gòu)4. 順序表的刪除操作在一般情況下，要刪除第i（1in）個元素時，則要從第i + 1個元素開始，直到第n個元素之間共n i個元素依次向前移動一個位置。刪除結(jié)束后，線性表的長度就減小了1。戀嘿呀遺單跌菏粥望都夕釉贖范話譬淆擻帽侮屑歹栽婿投渠放慌姐乍竄除第5章算法與數(shù)據(jù)結(jié)構(gòu)第5章算法與數(shù)據(jù)結(jié)構(gòu) 圖（a）為一個長度為6的線性表順序存儲在長度為7的存儲空間中?，F(xiàn)在要求刪除線性表中的第3個元素（即刪除元素5）。具體操作步驟為：從第4

18、個元素開始直到最后一個元素，將其中的每一個元素均依次往前移動一個位置。此時，線性表的長度變成了5，如圖（b）所示。婁導(dǎo)腿分改瞇政色趾莽侵云司擱光時腑禮酪犢雹響躁亮籌答擔(dān)曠墊壬干叫第5章算法與數(shù)據(jù)結(jié)構(gòu)第5章算法與數(shù)據(jù)結(jié)構(gòu)1234567V (1:7a）長度為6的線性表1234567V (1:7)1533217846（b）刪除元素5后的線性表嘆豁崎躺窗閉溪閩玉似瓊北鴕踢藻促思池泌謂掂忘纂搐衡坡網(wǎng)增畫償播哪第5章算法與數(shù)據(jù)結(jié)構(gòu)第5章算法與數(shù)據(jù)結(jié)構(gòu)5.2.2 線性鏈表線性表的順序存儲結(jié)構(gòu)具有簡單、操作方便等優(yōu)點。但在做插入或刪除操作時，需要移動大量的元素。因此，對于大的線性表，

19、特別是元素變動頻繁的大線性表不宜采用順序存儲結(jié)構(gòu)，而是通常采用鏈?zhǔn)酱鎯Y(jié)構(gòu)。在鏈?zhǔn)酱鎯Y(jié)構(gòu)中，存儲數(shù)據(jù)結(jié)構(gòu)的存儲空間可以不連續(xù)，各數(shù)據(jù)結(jié)點的存儲順序與數(shù)據(jù)元素之間的邏輯關(guān)系可以不一致。鏈?zhǔn)酱鎯Ψ绞郊瓤捎糜诒硎揪€性結(jié)構(gòu)，也可用于表示非線性結(jié)構(gòu)。彩游濱攔撐瑚腸孵苦藍(lán)剁溢堪悸佩龔堵哉州奧航毫漱訊詹贍杉婦騙瘩千吐第5章算法與數(shù)據(jù)結(jié)構(gòu)第5章算法與數(shù)據(jù)結(jié)構(gòu)假設(shè)數(shù)據(jù)結(jié)構(gòu)中的每一個數(shù)據(jù)結(jié)點對應(yīng)于一個存儲單元，這種存儲單元稱為存儲結(jié)點，簡稱結(jié)點。在鏈?zhǔn)酱鎯Ψ绞街?，要求每個結(jié)點由兩部分組成：一部分用于存放數(shù)據(jù)元素值，稱為數(shù)據(jù)域；另一部分用于存放指針，稱為指針域。其中指針用于指向該結(jié)點的前一個或后一個結(jié)點，從而可以

20、表示數(shù)據(jù)元素之間的邏輯關(guān)系。黨武帝砧圣燭靡撐建懶瞅硫蒂鉆暖未砌吠公晨劊特攪靴變男誓漢熙圃色剮第5章算法與數(shù)據(jù)結(jié)構(gòu)第5章算法與數(shù)據(jù)結(jié)構(gòu)我們把線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)稱為線性鏈表。線性鏈表中存儲結(jié)點的結(jié)構(gòu)如圖所示: 存儲地址 i數(shù)據(jù)域指針域V (i)NEXT (i)葷恢節(jié)檔專闖惡澎矽享曬挪慎湯龐誰蝕蛔焙躺平淖花歹鵑廂餃櫻釜漲禹頌第5章算法與數(shù)據(jù)結(jié)構(gòu)第5章算法與數(shù)據(jù)結(jié)構(gòu)在線性鏈表中，用一個專門的指針H（稱為頭指針）指向線性鏈表中第一個數(shù)據(jù)元素的結(jié)點（即存放線性表中第一個數(shù)據(jù)元素的存儲結(jié)點的序號）。從頭指針開始，沿著線性鏈表各結(jié)點的指針可以掃描到鏈表中的所有結(jié)點。線性表中最后一個元素沒有后件，因此，線性鏈

21、表中最后一個節(jié)點的指針域為空（用、NULL或0表示），表示鏈表終止。當(dāng)頭指針H = NULL（或0）時稱為空表?？鷹壩伖鹿客招钭逦⌒纺z巋澆盆去方瘧角盎曼吩歡訪顴仰伺都然祁恩第5章算法與數(shù)據(jù)結(jié)構(gòu)第5章算法與數(shù)據(jù)結(jié)構(gòu)在某些應(yīng)用中，對線性鏈表中的每個結(jié)點設(shè)置兩個指針，一個稱為左指針，用以指向其直接前驅(qū)；另一個稱為右指針，用以指向其直接后繼。這樣的線性鏈表稱為雙向鏈表。 型題腺敗彌甕棚碴樁妄掏珍倦蹈痞巡滌躲炎霖近嗆檔牙癸磺潮噶毗浸瑪踩第5章算法與數(shù)據(jù)結(jié)構(gòu)第5章算法與數(shù)據(jù)結(jié)構(gòu)5.2.3 對線性鏈表的基本操作1. 在線性鏈表中查找指定的元素在非空線性鏈表中尋找包含指定元素值x的前一個結(jié)點n的操作過程為

22、：從頭指針指向的結(jié)點開始向后沿指針進(jìn)行掃描，直到后面已經(jīng)沒有結(jié)點或下一個結(jié)點的數(shù)據(jù)域為x為止。套健寺漲攤涉愚騙偵頒紊貸柬娥故嫡影普羽黍郁鎖盼賣賴鞭溫始媚蓑俯逗第5章算法與數(shù)據(jù)結(jié)構(gòu)第5章算法與數(shù)據(jù)結(jié)構(gòu)因此，由這種方法找到的結(jié)點n有兩種可能：當(dāng)線性鏈表中存在包含元素x的結(jié)點時，則找到的n為首次發(fā)現(xiàn)的包含元素x的前一個結(jié)點序號；當(dāng)線性鏈表中不存在包含元素x的結(jié)點時，則找到的n為線性鏈表中的最后一個結(jié)點序號。報唁礎(chǔ)躬彈洋捅溜競立刻性墓誠峨熟躺鈾涉先柱內(nèi)抨平逐鎳十藝患葛早章第5章算法與數(shù)據(jù)結(jié)構(gòu)第5章算法與數(shù)據(jù)結(jié)構(gòu)2. 線性鏈表的插入線性鏈表的插入操作是指在線性鏈表中的指定位置上插入一個新的元素。為了要在

23、線性鏈表中插入一個新元素，首先要為該元素申請一個新結(jié)點，以存儲該元素的值。然后將存放新元素值的結(jié)點鏈接到線性鏈表中指定的位置。芒督稽汾謾彼殖板剃趴繪抵評堵砒枚隘囪雀秉術(shù)賃橙權(quán)晃誕汾茬易往酗癡第5章算法與數(shù)據(jù)結(jié)構(gòu)第5章算法與數(shù)據(jù)結(jié)構(gòu)3. 線性鏈表的刪除線性鏈表的刪除是指在線性鏈表中刪除包含指定元素的結(jié)點。為了在線性鏈表中刪除包含指定元素的結(jié)點，首先要在線性鏈表中找到這個結(jié)點，然后將要刪除結(jié)點釋放，以便于以后再次利用。念領(lǐng)殘此巫逝枷鉚桐償下捌襯嗓末俄畜島阻伴鋸扣鍺聊躥鎬韋委肖題咬者第5章算法與數(shù)據(jù)結(jié)構(gòu)第5章算法與數(shù)據(jù)結(jié)構(gòu)4. 循環(huán)鏈表及其基本操作循環(huán)鏈表的結(jié)構(gòu)與前面所討論的線性鏈表相比，具有以下兩

24、個特點：（1）在循環(huán)鏈表中增加了一個表頭結(jié)點，表頭結(jié)點的數(shù)據(jù)域可以是任意值，也可以根據(jù)需要來設(shè)置，指針域指向線性表的第一個元素的結(jié)點。循環(huán)鏈表的頭指針指向表頭結(jié)點。禮迫敬而辰拴制慮蘸蒸鈾標(biāo)待蠻晨躍五輔矗磅潞商距菲羌嗚鄲銷噓寄痛宴第5章算法與數(shù)據(jù)結(jié)構(gòu)第5章算法與數(shù)據(jù)結(jié)構(gòu)（2）循環(huán)鏈表中最后一個結(jié)點的指針域不為空，而是指向表頭結(jié)點。從而在循環(huán)鏈表中，所有結(jié)點的指針構(gòu)成了一個環(huán)?？媒芳彽満む徯亓氏Ь鞈{封展嚎梯陡留猖靳賦嘴僵砂刀掘?qū)嫿k法份擊袋汾第5章算法與數(shù)據(jù)結(jié)構(gòu)第5章算法與數(shù)據(jù)結(jié)構(gòu)5.3 棧和隊列5.3.1 棧1. 什么是棧棧實際上是一種特殊的線性表。在這種特殊的線性表中，插入與刪除操作都只在線性表

25、的一端進(jìn)行。因此，棧是指被限定僅在一端進(jìn)行插入與刪除操作的線性表。冶輻納答野袖專碴單逐慚榔塔嗅始常叔固壯眺五相雇唱切惜奧屏伍掛扇分第5章算法與數(shù)據(jù)結(jié)構(gòu)第5章算法與數(shù)據(jù)結(jié)構(gòu)在棧中，允許插入與刪除的一端稱為棧頂，而不允許插入和刪除的另一端稱為棧底。棧是按照“后進(jìn)先出”的原則組織數(shù)據(jù)的，因此，棧也被稱為“后進(jìn)先出”的線性表。在程序設(shè)計語言中，一般用一維數(shù)組作為隊列的順序存儲空間。酬哺億哮漸忱體兜魚串茫敖遏舜直渙哦人鯉裹舔望壞嗓齲慎雞撥舞雛載織第5章算法與數(shù)據(jù)結(jié)構(gòu)第5章算法與數(shù)據(jù)結(jié)構(gòu)通常用指針top來指示棧頂?shù)奈恢?，用指針bottom指向棧底。向棧中插入一個元素稱為進(jìn)棧操作，從棧中刪除一個元素稱為出棧

26、操作。棧頂指針top動態(tài)反映了棧中元素的變化情況。圖是棧的示意圖。五銜村嘯顱淋滬柄哼腮拍蔽對宿位鉑災(zāi)岡蠟澤缸簾墑毋銅談注讓司賈碑徊第5章算法與數(shù)據(jù)結(jié)構(gòu)第5章算法與數(shù)據(jù)結(jié)構(gòu)棧頂 top 棧底 bottom 進(jìn)棧 出棧 bnb2b1辰彎鹽弄捂帖鎮(zhèn)憶宵攢祈刁誅耀牙穴還晨胎腋勤梅嫁令淪惜慣裙娥巍扇呵第5章算法與數(shù)據(jù)結(jié)構(gòu)第5章算法與數(shù)據(jù)結(jié)構(gòu)2. 對棧的操作對棧的基本操作有兩種：進(jìn)棧和出棧。（1）進(jìn)棧操作進(jìn)棧操作是指在棧頂位置插入一個新元素。其過程是：先將棧頂指針加一，然后將新元素放到棧頂指針指向的位置。當(dāng)棧頂指針已經(jīng)指向存儲空間的最后一個位置時，說明?？臻g已滿，不能再進(jìn)棧，這種情況稱為?！吧弦纭卞e誤。暫

27、訴我版催柄薦墻浚啥畦眼娠厄獲殺僵竭族纏扦終蛇指禾榮悉爺膝冰井賂第5章算法與數(shù)據(jù)結(jié)構(gòu)第5章算法與數(shù)據(jù)結(jié)構(gòu)（2）出棧操作出棧操作是指取出棧頂元素。其過程是：先將棧頂指針指向的元素賦給一個指定的變量，然后將棧頂指針減1。當(dāng)棧頂指針為0時，說明?？眨荒茉俪鰲?，這種情況稱為?！跋乱纭卞e誤。癟榷趨杰帚裳匣坐喻阮?？截曘y同剖其砰插柿迭騷坷拘播彩泡住戮啄逼玉第5章算法與數(shù)據(jù)結(jié)構(gòu)第5章算法與數(shù)據(jù)結(jié)構(gòu)5.3.2 隊列1. 什么是隊列隊列是指只允許在一端進(jìn)行插入、而在另一端進(jìn)行刪除的線性表。允許插入的一端稱為隊尾，通常用一個稱為尾指針（rear）的指針指向隊尾元素；允許刪除的一端稱為隊頭，通常也用一個隊頭指針（f

28、ront）指向隊頭元素的前一個位置。隊列是按照“先進(jìn)先出”的原則組織數(shù)據(jù)的，因此隊列又稱為“后進(jìn)后出”的線性表。 黨乍蔚債汗撕攬怎新逾箔曾桃兼禿誨抽粘考皖戴坊皺拳咯輕挪稀虎痙圓例第5章算法與數(shù)據(jù)結(jié)構(gòu)第5章算法與數(shù)據(jù)結(jié)構(gòu)在隊列中，隊尾指針rear與隊頭指針front共同反映了隊列元素中元素動態(tài)變化的情況。下圖是隊列的示意圖。出隊abcde進(jìn)隊frontrear蛀奮夸囊去錢折座員睫粟各佐閱昭曾某箭劈梧鉛參絨策泵煎宴劑喂仕協(xié)仟第5章算法與數(shù)據(jù)結(jié)構(gòu)第5章算法與數(shù)據(jù)結(jié)構(gòu)向隊列的隊尾插入一個元素稱為進(jìn)隊操作，從隊列的隊頭刪除一個元素稱為出隊操作。由上圖可知：在隊列的末尾插入一個元素（進(jìn)隊操作）只涉及隊尾指

29、針rear的變化，而要刪除隊列中的隊頭元素（出隊操作）只涉及隊頭指針front的變化。遞涉件龍吝槽配伎曳局煩崇育辜冀宜曼菌熬兢悅槐酸肖綻親希曾企銥委澀第5章算法與數(shù)據(jù)結(jié)構(gòu)第5章算法與數(shù)據(jù)結(jié)構(gòu)2. 循環(huán)隊列及其操作循環(huán)隊列是一種將順序隊列臆造為一個環(huán)狀的空間的方法，通過把存儲隊列元素的表在邏輯上看成一個環(huán)，將隊列存儲空間的第一個位置作為隊列最后一個位置的下一個位置，供隊列循環(huán)使用。 雄墩韭徽揖娠遇泊凍燼突適踩喇隴洪捅喀鷗守保燙咖陛休噸休墾珍鳴織籌第5章算法與數(shù)據(jù)結(jié)構(gòu)第5章算法與數(shù)據(jù)結(jié)構(gòu)循環(huán)隊列的初始狀態(tài)為空，即rear = front = m，如圖所示。A (1: n)n21A.rear A.f

30、ront 斌翠擰索噴浙譴猖胯筋魚蜘向錯武嬸陣?yán)现敬熘秾毸庹嫔衅承拐灵l鍺玉鵝第5章算法與數(shù)據(jù)結(jié)構(gòu)第5章算法與數(shù)據(jù)結(jié)構(gòu)在循環(huán)隊列中，用隊尾指針rear指向隊列中的隊尾元素，用隊頭指針front指向隊頭元素的前一個位置，因此，從隊頭指針front指向的后一個位置直到隊尾指針rear指向的位置之間所有的元素均為隊列中的元素。處吳現(xiàn)哀視肄屬卡漳陡渡策炸棄舊垣卜哲輾炸孟嘔闌摔閏托索舍磚武爪說第5章算法與數(shù)據(jù)結(jié)構(gòu)第5章算法與數(shù)據(jù)結(jié)構(gòu)循環(huán)隊列主要有兩種基本操作：進(jìn)隊操作與出隊操作。每進(jìn)行一次進(jìn)隊操作，隊尾指針加一。當(dāng)隊尾指針rear = n + 1時，則置rear = 1。每進(jìn)行一次出隊操作，隊頭指針就加一。

31、當(dāng)隊頭指針front = n + 1時，則置front = 1。 孺僑砧奪倆梧與恨坑叫飼廉雀深露城峽樞撕瞅苔操迭諧勛繼筒糯妓銹純傅第5章算法與數(shù)據(jù)結(jié)構(gòu)第5章算法與數(shù)據(jù)結(jié)構(gòu)為了能區(qū)分隊列滿還是隊列空，通常還需增加一個標(biāo)志s，s值的定義如下：由此可以得出隊列空與隊列滿的條件如下：隊列空的條件為s = 0；隊列滿的條件為s = 1且front = rear。懊誘底脂鐐憲斤蹤率桌在速纖痙屢團(tuán)佯頃撤補凍骯況椅鹵灌津計撕梧鎬師第5章算法與數(shù)據(jù)結(jié)構(gòu)第5章算法與數(shù)據(jù)結(jié)構(gòu)5.4 樹與二叉樹5.4.1 樹的基本概念樹是一種重要的非線性結(jié)構(gòu)。在這種數(shù)據(jù)結(jié)構(gòu)中，所有數(shù)據(jù)元素之間的關(guān)系具有明顯的層次特性，并以分支關(guān)系定

32、義了層次結(jié)構(gòu)。下圖是一棵樹的例子。 頹舷溝糯句楓僑隔求蝦撣丙挪稠悶鄙檸琵茨茍嗓慧壽瀉攙忱掌贊撅枝靛忘第5章算法與數(shù)據(jù)結(jié)構(gòu)第5章算法與數(shù)據(jù)結(jié)構(gòu)AEDCBIHGFQNJRKM髓奮傭洗燒色穩(wěn)基款唾箋默攙然辣傣伎睜辣攫大四塢愈濘式賺墅駭脾認(rèn)賢第5章算法與數(shù)據(jù)結(jié)構(gòu)第5章算法與數(shù)據(jù)結(jié)構(gòu)現(xiàn)實世界中有很多可以用樹來表示的例子。例如圖中的樹表示了高校中院系之間的關(guān)系。 沈陽工業(yè)大學(xué)信息學(xué)院外語學(xué)院理學(xué)院經(jīng)濟學(xué)院軟件教研室控制教研室英語教研室德語教研室數(shù)學(xué)教研室物理教研室宏觀經(jīng)濟教研室微觀經(jīng)濟教研室駱興履糯邁蒙艾竟總推攆園數(shù)世嚷官車閘濁茂錳舀啥窄司冰紋洲休舷統(tǒng)泉第5章算法與數(shù)據(jù)結(jié)構(gòu)第5章算法與數(shù)據(jù)結(jié)構(gòu)樹中每一個結(jié)

33、點只有一個直接前驅(qū)，稱作父結(jié)點。沒有直接前驅(qū)的結(jié)點只有一個，稱作樹的根結(jié)點，簡稱為樹的根。例如，在上圖中，結(jié)點沈陽工業(yè)大學(xué)是樹的根結(jié)點。每一個結(jié)點可以有多個直接后繼，它們都稱為該結(jié)點的子女。沒有直接后繼的結(jié)點稱為葉子結(jié)點（如：圖中的結(jié)點理學(xué)院、數(shù)學(xué)教研室等）。術(shù)眷妨徽紛預(yù)震攀毖杉技厭漢咐升良詣梨耶樟蓖偽螟帖戳麓瓶文邊坯碟源第5章算法與數(shù)據(jù)結(jié)構(gòu)第5章算法與數(shù)據(jù)結(jié)構(gòu)除樹根以外的其它結(jié)點被劃分為多個互不相交的有限集合，每個集合又是一棵樹，被稱為根的子樹。結(jié)點所擁有的子樹的棵樹被稱為該結(jié)點的度。如上圖中沈陽工業(yè)大學(xué)根節(jié)點 的度是4，理學(xué)院的度是2，樹中所有結(jié)點的度的最大值稱為樹的度。例如，圖中所示的樹

34、的度為4。鈍凡嶺啟羌厚培縛品附牡陀駐舜娶輔圃膀鴕趴獻(xiàn)曬讒衙碌爵挖鎖虞鈣綽恢第5章算法與數(shù)據(jù)結(jié)構(gòu)第5章算法與數(shù)據(jù)結(jié)構(gòu)用樹來表示算術(shù)表達(dá)式的原則如下：（1）算術(shù)表達(dá)式中的每一個運算符對應(yīng)于樹中的一個結(jié)點。（2）運算符的任一運算對象皆為該運算符結(jié)點的子樹。（3）運算對象中的單個變量均為葉子結(jié)點。巢箕世扦條涅峭忙婦團(tuán)士晉舀轉(zhuǎn)輯溉戶敷娠汰煽佛蟲狡董馮嬸早牙底教討第5章算法與數(shù)據(jù)結(jié)構(gòu)第5章算法與數(shù)據(jù)結(jié)構(gòu)下圖是用樹結(jié)構(gòu)對表達(dá)式a + b/(c-d) - (x, y, z)*e 的表示。注意：表示一個表達(dá)式的表達(dá)式樹可能并不唯一。拴梢毀撩榮屠迪椰拓詹杖锨渡奔誰媳融丁稠湊添罰底攘芒諺囊曬環(huán)抉騙釋第5章算法與數(shù)據(jù)

35、結(jié)構(gòu)第5章算法與數(shù)據(jù)結(jié)構(gòu)-+/a-bdc*ea+b/(c-d)b/(c-d)c-d(x, y, z)(x, y, z)*exyz兄桃金兵屢鉚歸鶴嗅嗅唬獅遵甜涼子點缸藥拜遵畫畢把詛斌燼逢攢派床么第5章算法與數(shù)據(jù)結(jié)構(gòu)第5章算法與數(shù)據(jù)結(jié)構(gòu)5.4.2 二叉樹及其基本性質(zhì)1. 什么是二叉樹二叉樹是另一種樹型結(jié)構(gòu)，當(dāng)然二叉樹也是一種非線性結(jié)構(gòu)。它的特點是：（1）非空二叉樹只有一個根結(jié)點；（2）每一個結(jié)點最多有兩棵子樹，順序不能顛倒，分別稱為該結(jié)點的左子樹與右子樹。況仔凄體睡唐鴕蔽映逸脯拱派實拋烹括萎耐志步副宏迸圈坯揀贅薯礙靶藩第5章算法與數(shù)據(jù)結(jié)構(gòu)第5章算法與數(shù)據(jù)結(jié)構(gòu)可見在二叉樹中，不存在度大于2的結(jié)點，從

36、而所有子樹也均為二叉樹。另外，在二叉樹中，一個結(jié)點可以只有左子樹而沒有右子樹，也可以只有右子樹而沒有左子樹。當(dāng)一個結(jié)點既沒有左子樹也沒有右子樹時，該結(jié)點即是葉子結(jié)點。 慎總熙智乖器馭漁炕韌辟掄澄騾罵賈椽怕忻茹抄碎戶節(jié)蘸彎愉玻律腔籃漲第5章算法與數(shù)據(jù)結(jié)構(gòu)第5章算法與數(shù)據(jù)結(jié)構(gòu)下圖是一棵深度為3的二叉樹。ACEBF哈蓄撓眨述曠遭虎凋未池似幣閱俠活泛嘔貉稱間秉槳寸嫡嫡逆捷計曉芍估第5章算法與數(shù)據(jù)結(jié)構(gòu)第5章算法與數(shù)據(jù)結(jié)構(gòu)2. 二叉樹的基本性質(zhì)性質(zhì)1 在二叉樹的第i層上，最多有 （i1）個結(jié)點。性質(zhì)2 深度為m的二叉樹最多有 -1個結(jié)點。性質(zhì)3 在任意一棵二叉樹中，度為0的結(jié)點（即葉子結(jié)點）總是比度為2的

37、結(jié)點多一個。性質(zhì)4 具有n個結(jié)點的二叉樹，其深度至少為log2n+1，其中l(wèi)og2n表示取log2n的整數(shù)部分。2i-12m燒剔二蛙蚊用配豺蠟付峰妓蒸最酮舞勉疥濾鉗行檄飲池謹(jǐn)仆健吊垢袒綁贓第5章算法與數(shù)據(jù)結(jié)構(gòu)第5章算法與數(shù)據(jù)結(jié)構(gòu)3. 滿二叉樹與完全二叉樹滿二叉樹與完全二叉樹是兩種特殊形態(tài)的二叉樹。（1）滿二叉樹滿二叉樹是一棵深度為m且有 -1個結(jié)點的二叉樹。該二叉樹每一層上的所有結(jié)點數(shù)都達(dá)到最大值。 2m痊語考葵僻棱粘屈嚇澎偶勞剖諾徒跌痊沛徹袱內(nèi)曰仁證舒蜜僵到唐葫筒腹第5章算法與數(shù)據(jù)結(jié)構(gòu)第5章算法與數(shù)據(jù)結(jié)構(gòu)(a) 深度為2的滿二叉樹(b) 深度為3的滿二叉樹ABCDEFGABC嬌酬頒墊臆暢駐蛤

38、揍鹼任紫始補光辛炯去馱蜜郝綴茬驢涵披喳旭咀村鼠冒第5章算法與數(shù)據(jù)結(jié)構(gòu)第5章算法與數(shù)據(jù)結(jié)構(gòu)（2）完全二叉樹完全二叉樹除最后一層外，每一層上的結(jié)點數(shù)均達(dá)到最大值；在最后一層上只缺少右邊的若干結(jié)點 ，稱之為完全二叉樹 。醞愁蜀右沸擊凱噎瞇啤幸刃狀貶贅煥擂粳江儈尹令械兆女路紗屢邑咽殉砒第5章算法與數(shù)據(jù)結(jié)構(gòu)第5章算法與數(shù)據(jù)結(jié)構(gòu)ACDFEB由滿二叉樹與完全二叉樹的特點可以看出，滿二叉樹也是完全二叉樹，而完全二叉樹一般不是滿二叉樹。根膩午俠佃碉抽碎凰娥膝壇耕鴻圾洲列閏壇噓經(jīng)打槽吉纓蹬貶當(dāng)箍攆芒背第5章算法與數(shù)據(jù)結(jié)構(gòu)第5章算法與數(shù)據(jù)結(jié)構(gòu)5.4.3 二叉樹的存儲結(jié)構(gòu)在計算機中，二叉樹通常采用鏈?zhǔn)酱鎯Y(jié)構(gòu)。用于存

39、儲二叉樹中各元素的存儲結(jié)點由兩部分組成：數(shù)據(jù)域與指針域。但在二叉樹中，由于每一個元素可以有兩個子結(jié)點，因此，用于存儲二叉樹的存儲結(jié)點的指針域有兩個：一個用于指向該結(jié)點的左子結(jié)點，稱左指針域；另一個用于指向該結(jié)點的右子結(jié)點，稱為右指針域。 銜孔額博贍眠震地石葉獻(xiàn)如臼膳塔煥櫥滄鎬乍唉瓦竿鼓幅盜俄賴逸鎬糞壘第5章算法與數(shù)據(jù)結(jié)構(gòu)第5章算法與數(shù)據(jù)結(jié)構(gòu)由于二叉樹的存儲結(jié)構(gòu)中每一個存儲結(jié)點有兩個指針域，因此，二叉樹的鏈?zhǔn)酱鎯Y(jié)構(gòu)也稱為二叉樹鏈表。 鈔啤顯均胳稿漾契飯鋒銀坊鳥套牡涌瑟痞臃禽譴德青虧辰鑷綿習(xí)旨螟殃窿第5章算法與數(shù)據(jù)結(jié)構(gòu)第5章算法與數(shù)據(jù)結(jié)構(gòu)5.4.4 二叉樹的遍歷二叉樹的遍歷：是指不重復(fù)地訪問二叉

40、樹中的所有結(jié)點。在遍歷二叉樹的過程中，一般先遍歷左子樹，然后再遍歷右子樹。在先左后右的原則下，根據(jù)訪問根結(jié)點的次序，二叉樹的遍歷可以分為三種：前序遍歷、中序遍歷、后序遍歷。 怎蟲肯胞試掇巷孫藐么他漾記遲瓦響委玲擒咆頰壺漠楷絨摟壞機箔嚨科浮第5章算法與數(shù)據(jù)結(jié)構(gòu)第5章算法與數(shù)據(jù)結(jié)構(gòu)1. 前序遍歷所謂前序遍歷是指首先訪問根結(jié)點，然后遍歷左子樹，最后遍歷右子樹；并且，在遍歷左、右子樹時，仍然先訪問根結(jié)點，然后遍歷左子樹，最后遍歷右子樹。蚊虞俊吼輥原迢漣秉癌稿腦椅墑分扶礁動烘拓口涯集汞撕丈楷悉芽削寬蛇第5章算法與數(shù)據(jù)結(jié)構(gòu)第5章算法與數(shù)據(jù)結(jié)構(gòu)下面是二叉樹中序遍歷的簡單描述：若二叉樹為空，則結(jié)束返回。否則：

41、（1）中序遍歷左子樹；（2）訪問根結(jié)點；（3）中序遍歷右子樹。烴咸圖約骨藤迎光刮枉乳牡廬鑒偵缸職絲娟狼巨服萊典暢縮蹭冰米柏做絞第5章算法與數(shù)據(jù)結(jié)構(gòu)第5章算法與數(shù)據(jù)結(jié)構(gòu)2. 中序遍歷所謂中序遍歷是指首先遍歷左子樹，然后訪問根結(jié)點，最后遍歷右子樹；并且，在遍歷左、右子樹時，仍然先遍歷左子樹，然后訪問根結(jié)點，最后遍歷右子樹。 帆涉脈剿怖泣茄細(xì)漬瘍純母存殃晤狼兼薪魄翰畏唁定軍翔瞧迪簡悄蠕艙碩第5章算法與數(shù)據(jù)結(jié)構(gòu)第5章算法與數(shù)據(jù)結(jié)構(gòu)下面是二叉樹中序遍歷的簡單描述：若二叉樹為空，則結(jié)束返回。否則：（1）中序遍歷左子樹；（2）訪問根結(jié)點；（3）中序遍歷右子樹。援署濤素捷丑渺長狂住梗豁礫灘嫌創(chuàng)期孝佬航場餐渴儈

42、回醬凄尊茵籬蝸須第5章算法與數(shù)據(jù)結(jié)構(gòu)第5章算法與數(shù)據(jù)結(jié)構(gòu)3. 后序遍歷所謂后序遍歷是指首先遍歷左子樹，然后遍歷右子樹，最后訪問根結(jié)點，并且，在遍歷左、右子樹時，仍然先遍歷左子樹，然后遍歷右子樹，最后訪問根結(jié)點。 捧襟爪潤輕輾朱例器映個審撒嫡澄咆泛障蔥戲炙若丸乍潦葛融芹核酣馭汐第5章算法與數(shù)據(jù)結(jié)構(gòu)第5章算法與數(shù)據(jù)結(jié)構(gòu)下面是二叉樹后序遍歷的簡單描述：若二叉樹為空，則結(jié)束返回。否則：（1）后序遍歷左子樹；（2）后序遍歷右子樹；（3）訪問根結(jié)點。道貶銀謠締硅葷瘩拽遞衡自絲罐廣減市頹譚趕票鐵款叫角籌債閹咎紫碩腥第5章算法與數(shù)據(jù)結(jié)構(gòu)第5章算法與數(shù)據(jù)結(jié)構(gòu)5.5 查找和排序技術(shù)5.5.1 查找技術(shù)1. 順序查

43、找順序查找的基本方法是：從線性表的第一個元素開始，逐個將線性表中的元素與被查元素進(jìn)行比較，若相等則表示找到（即查找成功）；若線性表中所有的元素都與被查元素進(jìn)行了比較但都不相等，則表示線性表中沒有要找的元素（即查找失敗）。彥提蠟鄧光乒尼瞞墟撰娥療描攤靈峙翼呂半熒拽痛空竭闖曾幽褒豢憤嚨蓖第5章算法與數(shù)據(jù)結(jié)構(gòu)第5章算法與數(shù)據(jù)結(jié)構(gòu)雖然順序查找的效率不高，但在下列兩種情況下只能采用順序查找：（1）如果線性表為無序表，則只能用順序查找。（2）采用鏈?zhǔn)酱鎯Y(jié)構(gòu)的有序線性表，只能采用順序查找。捅庫斧櫻陽穿捶傍坤倍遙耐型扁欠盛補碌掇痢儉楚瑚姚己骨偵蠕鎖隅吵臨第5章算法與數(shù)據(jù)結(jié)構(gòu)第5章算法與數(shù)據(jù)結(jié)構(gòu)2. 折半查找

44、折半查找只適用于順序存儲的有序表，也就是說，線性表中的元素已經(jīng)按值非遞減排列。假設(shè)有序線性表的長度為m，被查元素值為x，則折半查找的方法如下：釜癟詳翔牽札招隔賽靠追掣涉哦吳摘廖偉英灰夢婿榆媳烴氮鞋賽瓣袱乖尊第5章算法與數(shù)據(jù)結(jié)構(gòu)第5章算法與數(shù)據(jù)結(jié)構(gòu)將x與線性表的中間項的元素值進(jìn)行比較，若中間項的值等于x，則查找成功，結(jié)束返回；若x小于中間項的值，則在線性表的前半部分用相同的方法進(jìn)行查找；若x大于中間項的值，則在線性表的后半部分用相同的方法進(jìn)行查找。這個過程一直進(jìn)行到查找成功或線性表中沒有這個元素為止。稠潘庭百筍嚴(yán)漣勁置拈祁瘓異旦細(xì)基明笑晨吝籽利猾篷萊攙鋇膠哦區(qū)憎鮮第5章算法與數(shù)據(jù)結(jié)構(gòu)第5章算法與

45、數(shù)據(jù)結(jié)構(gòu)5.5.2 排序技術(shù)1. 插入排序所謂插入排序，是指將無序序列中的各元素依次插入到已經(jīng)有序的線性表中。（1）簡單插入排序簡單插入排序的基本思想是：將一個新元素插入到已經(jīng)排好序的有序序列中，從而元素的個數(shù)增一，并成為新的有序序列。啟把驕哲責(zé)息覽拌夯速菲曰竊篷我桅望殼矗莫荷殖攬殉疙售鉤喊揍針熄優(yōu)第5章算法與數(shù)據(jù)結(jié)構(gòu)第5章算法與數(shù)據(jù)結(jié)構(gòu)在簡單插入排序過程中，由于每一次比較后最多去掉一個逆序，因此，這種排序方法的效率在最壞情況下，需要n(n-1)/2次比較。（2）希爾排序希爾排序的基本思想是：將整個初始序列分割成若干個子序列，對每個子序列分別進(jìn)行簡單插入排序，最后再對全體元素進(jìn)行一次簡單插入排

46、序。由此可見，希爾排序也是一種插入排序方法。蟲核遮啥獻(xiàn)界齡腋湯滲耶性潭僚充疾拋瘁才嘿妒燕倚凸裔呈龍霹珍外飯鄲第5章算法與數(shù)據(jù)結(jié)構(gòu)第5章算法與數(shù)據(jù)結(jié)構(gòu)2交換排序所謂交換排序是指借助數(shù)據(jù)元素之間的互相交換進(jìn)行排序的一種方法。冒泡排序法與快速排序法都屬于交換類的排序方法。（1）冒泡排序冒泡排序的過程簡單，它的基本思想是通過對相鄰元素進(jìn)行比較，并根據(jù)比較的結(jié)果交換位置，從而逐步由任意序列變?yōu)橛行蛐蛄?。函否勸肪償吻劃舜陌那若拓卑瘟收麗緘棱簡抒藐九翻申壩發(fā)毋撩蕾惺鯉恃第5章算法與數(shù)據(jù)結(jié)構(gòu)第5章算法與數(shù)據(jù)結(jié)構(gòu)具體過程是：首先，將第一個元素和第二元素進(jìn)行比較，若為逆序，則交換之。接下來對第二個元素和第三個元素進(jìn)行同樣的操作，并依次類推，直到倒數(shù)第二個元素和最后一個元素為止。其結(jié)果是將最大的元素交換到了整個序列的尾部。這個過程叫做第一趟冒泡排序。而第二趟冒泡排序是在除去這個最大元素的子序列中從第一個元素起重復(fù)上述過程，直到整個序列變?yōu)橛行驗橹?。排序過程中，小元素好比水中氣泡逐漸上浮，而大元素好比大石頭逐