第一章數(shù)據(jù)結(jié)構(gòu)與算法全國計算機(jī)二級考試之公共根底知識1本章主要內(nèi)容算法概述數(shù)據(jù)結(jié)構(gòu)線性表及其順序存儲結(jié)構(gòu)棧和隊(duì)列線性鏈表樹與二叉樹查找技術(shù)排序技術(shù)21.1算法算法的定義算法的設(shè)計算法的表示算法的評價3算法和程序程序設(shè)計是利用計算機(jī)解決問題的全過程程序設(shè)計的過程：分析抽象模型求解命令編程調(diào)試程序?qū)嶋H問題問題模型求解算法編制程序問題實(shí)現(xiàn)問題分析算法設(shè)計編程設(shè)計測試執(zhí)行4計算機(jī)求解問題的步驟確定并理解問題；尋找解決問題的方法與步驟，并將其表示成算法(Algorithm)；使用某種程序設(shè)計語言描述該算法(編程),并進(jìn)行調(diào)試；運(yùn)行程序，獲得問題的解答；進(jìn)行評估，改進(jìn)算法和程序算法5算法和程序程序設(shè)計的第一步是問題分析問題分析問題一：統(tǒng)計一個班級的學(xué)生考試成績，并選出優(yōu)秀學(xué)生多少科目的成績？優(yōu)秀的定義〔總分？平均分？第一名？前五名？〕數(shù)據(jù)如何錄入？如何輸出？這是初學(xué)者認(rèn)為最簡單而在實(shí)際工程中最難的工作。在軟件工程中被稱作“需求分析〞6算法和程序算法設(shè)計算法的概念要使計算機(jī)完成某一問題的解題任務(wù)，首先必須針對該問題設(shè)計一個解題步驟，然后再據(jù)此編寫程序。這里所說的解題步驟就是“算法〞。算法與程序不同，它是問題求解規(guī)那么的一種過程描述。在算法中要精確定義一系列規(guī)那么，這些規(guī)那么指定了相應(yīng)的操作順序，以便在有限的步驟內(nèi)得到所求問題的解答。7算法定義算法－解決問題的方法和步驟例：有三個硬幣，其中一個是偽造的，另兩個是真的，偽幣與真幣重量略有不同?，F(xiàn)在提供一座天平，如何找出偽幣呢？分析：方法明確而有序按提供的條件進(jìn)行操作任何人均可仿照進(jìn)行(共享智能)算法開始C是偽幣B是偽幣A是偽幣A＝B？A＝C？是否否是8算法和程序算法無處不再例1：Word如何在文檔中查找用戶指定的詞語？例2：EXCEL中如何將表格內(nèi)容排序？例3：如何把彩色圖片轉(zhuǎn)換為灰度(黑白)圖片？例4：如何在硬盤中找到用戶指定的文件？例5：媒體播放器如何把MP3文件轉(zhuǎn)換成動聽的音樂？例6：搜索引擎如何找到用戶需要的網(wǎng)頁？算法9算法的通用性算法所解決的是一類問題而不是一個特定的問題，例如排序(sort)：包括表格內(nèi)容的排序，文件夾中文件的排序等排序方式也可以按數(shù)字、文字或日期等排序查找(search)：可以在文檔中查找某個單詞或在硬盤中查找某個文件，也可在Web上查找某個網(wǎng)頁等等開發(fā)計算機(jī)應(yīng)用的核心是：根據(jù)實(shí)際問題給出解題的算法，然后再將該算法在計算機(jī)上實(shí)現(xiàn)(即開發(fā)成為軟件)算法10實(shí)現(xiàn)算法考慮的問題實(shí)現(xiàn)算法考慮的問題：如何確定算法－算法設(shè)計如何表示算法－算法表示如何使算法更有效－算法的復(fù)雜性設(shè)計算法的實(shí)現(xiàn)貫穿在整個計算機(jī)求解問題的過程當(dāng)中算法11算法的特點(diǎn)算法的根本特征可行性：運(yùn)算必須在計算機(jī)能力范圍內(nèi)可以運(yùn)行確定性：運(yùn)算操作必須清楚明確，無二義性有窮性：算法必須在有限步后終止擁有足夠情報〔數(shù)據(jù)〕：即計算數(shù)據(jù)必須完備其他：輸入：有0~多個輸入，包括外界輸入和初始化輸出：至少有一個輸出算法12算法的特點(diǎn)練習(xí)算法的有窮性是指A〕算法程序的運(yùn)行時間是有限的B〕算法程序所處理的數(shù)據(jù)量是有限的C〕算法程序的長度是有限的D〕算法只能被有限的用戶使用以下表達(dá)中正確的選項(xiàng)是A〕算法就是程序B〕設(shè)計算法時只需要考慮數(shù)據(jù)結(jié)構(gòu)的設(shè)計C〕設(shè)計算法時只需要考慮結(jié)果的可靠性D〕以上三種說法都不對算法答案：AD13算法設(shè)計根本方法算法的設(shè)計原那么由粗到細(xì)由抽象到具體逐步求精14算法設(shè)計根本方法常用算法的設(shè)計方法列舉法〔窮舉法、枚舉法〕例：判斷素數(shù)歸納法例：Fibonacci數(shù)列1，1，2，3，5，8，13，...歸納結(jié)果:Fn=Fn-1+Fn-2(n≥3)遞推法是歸納法最常使用的一種例：求級數(shù)和遞歸法回溯法15算法的表示算法表示方法：文字說明法，缺點(diǎn)：容易產(chǎn)生歧義，很難“精確〞地進(jìn)行表達(dá)表達(dá)冗長，很難清楚地表達(dá)算法的邏輯流程流程圖流程圖由符號和箭頭構(gòu)成，描述了算法所執(zhí)行操作的順序及執(zhí)行操作的條件流程圖比文字描述簡明，但當(dāng)算法比較復(fù)雜時，理解困難，容易產(chǎn)生錯誤偽代碼〔一種介于自然語言和程序設(shè)計語言之間的文字和符號表達(dá)工具〕16算法設(shè)計算法設(shè)計舉例：－對包含n個整數(shù)元素的數(shù)組A進(jìn)行升序排序。直接選擇算法：文字表示從所有整數(shù)中選取最小的，交換到第一個數(shù)位置上；從剩下未排整數(shù)中選出最小的，交換到已排好序列的最后一個數(shù)后面；反復(fù)執(zhí)行②，直到所有整數(shù)都放到已排好的序列中。17算法的表示舉例偽代碼法：

將原始數(shù)據(jù)放在數(shù)組A中；FORi=1Ton{確定A[i]到A[n]中最小整數(shù)的位置，設(shè)為j；交換A[i]和[j]；i=i+1}原始數(shù)據(jù)放在數(shù)組A中；令i=1確定A[i]到A[n]中最小整數(shù)的位置,設(shè)為jA[i]和A[j]交換位置i=i+1i=n?結(jié)束開始流程圖法18算法評價算法評價指判斷算法的好壞正確性指給定有效輸入后，經(jīng)過有限時間的計算，產(chǎn)生正確的輸出結(jié)果簡單性算法是否容易理解，是否容易驗(yàn)證其正確性，程序是否容易調(diào)試簡單的算法效率不一定高，要在保證一定效率的前提下力求算法簡單19算法評價占用的計算機(jī)資源－算法的復(fù)雜度時間復(fù)雜度－指程序運(yùn)行消耗的時間空間復(fù)雜度－指程序運(yùn)行時所占存儲空間的大小理解度、調(diào)試和測試的方便度等20算法復(fù)雜度算法的時間復(fù)雜度算法的時間復(fù)雜度：程序運(yùn)行消耗的時間衡量方法：執(zhí)行算法所需要的計算工作量工作量計算方法：執(zhí)行算法的過程中所需根本運(yùn)算的執(zhí)行次數(shù)根本運(yùn)算是算法中的主要運(yùn)算例：矩陣相乘時，乘法是根本運(yùn)算，加法忽略不計查找運(yùn)算，以比較為根本運(yùn)算21算法復(fù)雜度算法的時間復(fù)雜度工作量計算方法分類：平均性態(tài)分析：指根本運(yùn)算次數(shù)的加權(quán)平均值最壞情況復(fù)雜性指根本運(yùn)算的最大次數(shù)22選擇排序算法的時間復(fù)雜性設(shè)參加排序的整數(shù)有n個比較操作的次數(shù)：在第i趟排序中選出最小整數(shù)時，需做n-i次比較操作，因此，總的比較操作次數(shù)為：n(n-1)/2=(n2-n)/2交換操作的次數(shù)：最好情況(原始數(shù)據(jù)已經(jīng)排序)時，交換次數(shù)為0最壞情況(原始數(shù)據(jù)逆序排列)時，每趟均要執(zhí)行交換操作(3次傳送)，總的交換次數(shù)取最大值為：3(n-1)所以，直接選擇排序的時間復(fù)雜性為O(n2)設(shè)置i的初值為1，循環(huán)執(zhí)行以下操作，直到i=n:{確定A[i]到A[n]中最小的整數(shù)元素的位置，設(shè)為j；交換A[i]和[j]；i=i+1}23算法復(fù)雜度算法的空間復(fù)雜度指執(zhí)行算法所需內(nèi)存空間大小算法程序所占空間原始數(shù)據(jù)所占空間額外空間：包括運(yùn)算時占用工作單元和特殊數(shù)據(jù)結(jié)構(gòu)存儲時的附加空間注意：時間和空間復(fù)雜度經(jīng)常是矛盾的，需要根據(jù)具體情況找到平衡點(diǎn)24算法復(fù)雜度練習(xí)以下表達(dá)中正確的選項(xiàng)是A〕一個算法的空間復(fù)雜度大，那么其時間復(fù)雜度也必定大B〕一個算法的空間復(fù)雜度大，那么其時間復(fù)雜度必定小C〕一個算法的時間復(fù)雜度大，那么其空間復(fù)雜度必定小D〕上述三種說法都不對以下表達(dá)中正確的選項(xiàng)是A〕算法的效率只與問題的規(guī)模有關(guān)，而與數(shù)據(jù)的存儲結(jié)構(gòu)無關(guān)B〕算法的時間復(fù)雜度是指執(zhí)行算法所需要的計算工作量C〕數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲結(jié)構(gòu)是一一對應(yīng)的D〕算法的時間復(fù)雜度與空間復(fù)雜度一定相關(guān)答案：DB251.2數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的存儲結(jié)構(gòu)數(shù)據(jù)的運(yùn)算26數(shù)據(jù)結(jié)構(gòu)的概念算法(程序)由2個局部組成：進(jìn)行的操作所涉及的操作對象(數(shù)據(jù))算法操作對象操作步驟與條件程序說明所要處理的數(shù)據(jù)的名字和類型描述所要執(zhí)行的算法說明語句命令語句27數(shù)據(jù)結(jié)構(gòu)的概念數(shù)據(jù)結(jié)構(gòu)研究如何在計算機(jī)中表示被處理的對象及對象之間的關(guān)系，即如何組織數(shù)據(jù)。例如：選擇排序中，未排序整數(shù)和已排序整數(shù)如何表示？排序算法中，排序的對象假設(shè)不是整數(shù)而是姓名如何表示？是文件夾中的文件名又如何表示？是表格中的“行〞又如何表示？Windows操作系統(tǒng)中菜單如何表示？對話框如何表示？窗口如何表示？計算機(jī)下棋時，棋盤和棋局如何表示？28數(shù)據(jù)結(jié)構(gòu)的概念數(shù)據(jù)結(jié)構(gòu)是相互有關(guān)聯(lián)的數(shù)據(jù)元素的集合例：研究季節(jié)時：“春、夏、秋、冬〞是相互關(guān)聯(lián)的數(shù)據(jù)元素數(shù)據(jù)元素的的前后件關(guān)系指數(shù)據(jù)元素的前后順序關(guān)系例：春夏關(guān)系：春是夏的前件，夏是春的后件前后件關(guān)系是數(shù)據(jù)元素之間的根本關(guān)系數(shù)據(jù)結(jié)構(gòu)29數(shù)據(jù)結(jié)構(gòu)的概念精心設(shè)計的數(shù)據(jù)結(jié)構(gòu)可使算法獲得更高的時間效率或空間效率研究數(shù)據(jù)結(jié)構(gòu)一般包括三個方面的內(nèi)容：數(shù)據(jù)的邏輯結(jié)構(gòu)：數(shù)據(jù)間關(guān)系的描述數(shù)據(jù)的存儲結(jié)構(gòu)：邏輯結(jié)構(gòu)在存儲器上的實(shí)現(xiàn)在數(shù)據(jù)上定義的運(yùn)算數(shù)據(jù)結(jié)構(gòu)30數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)指數(shù)據(jù)集合中各數(shù)據(jù)元素之間所固有的邏輯關(guān)系數(shù)據(jù)結(jié)構(gòu)包含的信息：數(shù)據(jù)元素本身的信息〔用D表示〕各數(shù)據(jù)元素之間的前后件關(guān)系〔用R表示〕數(shù)據(jù)的邏輯結(jié)構(gòu)的表示：B=〔D,R〕例：季節(jié)數(shù)據(jù)結(jié)構(gòu)：D=｛春、夏、秋、冬｝R=｛(春、夏),(夏、秋),(秋、冬)｝數(shù)據(jù)結(jié)構(gòu)31數(shù)據(jù)的邏輯結(jié)構(gòu)常見數(shù)據(jù)邏輯結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)HDSLYA線性結(jié)構(gòu)例：四季網(wǎng)狀結(jié)構(gòu)例：課程,學(xué)生樹形結(jié)構(gòu)例：組織結(jié)構(gòu)結(jié)點(diǎn)根結(jié)點(diǎn)(無前件)32數(shù)據(jù)的存儲結(jié)構(gòu)數(shù)據(jù)的存儲結(jié)構(gòu)是其邏輯結(jié)構(gòu)在計算機(jī)存儲器上的實(shí)現(xiàn)包含內(nèi)容：數(shù)據(jù)元素自身值數(shù)據(jù)元素之間關(guān)系例：數(shù)組結(jié)構(gòu)，序號反映前后件關(guān)系與邏輯結(jié)構(gòu)的關(guān)系邏輯結(jié)構(gòu)不一定與存儲結(jié)構(gòu)一致例：父子關(guān)系中兒、女中必有一人無法緊接父親存放同一種邏輯結(jié)構(gòu)的數(shù)據(jù)可以采用不同的存儲結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)33數(shù)據(jù)的存儲結(jié)構(gòu)常見存儲結(jié)構(gòu)：順序：把邏輯上相鄰的結(jié)點(diǎn)存儲在物理位置相鄰的存儲單元里，結(jié)點(diǎn)間的邏輯關(guān)系由存儲單元的鄰接關(guān)系來表達(dá)例：數(shù)組鏈接：不要求邏輯上相鄰的結(jié)點(diǎn)在物理位置上亦相鄰，結(jié)點(diǎn)間的邏輯關(guān)系是由附加的指針字段表示的索引：除建立存儲結(jié)點(diǎn)信息外，還建立附加的索引表來標(biāo)識結(jié)點(diǎn)的地址數(shù)據(jù)結(jié)構(gòu)34數(shù)據(jù)的存儲結(jié)構(gòu)存儲結(jié)構(gòu)分類：線性結(jié)構(gòu)〔非空的數(shù)據(jù)結(jié)構(gòu)〕特點(diǎn)：有且只有一個根結(jié)點(diǎn)每一個結(jié)點(diǎn)最多有一個前件，也最多有一個后件常見的線性結(jié)構(gòu)：線性表、棧、隊(duì)列和線性鏈表等非線性結(jié)構(gòu)：不滿足線性結(jié)構(gòu)條件的數(shù)據(jù)結(jié)構(gòu)常見非線性結(jié)構(gòu)：樹、二叉樹和圖等數(shù)據(jù)結(jié)構(gòu)35數(shù)據(jù)的運(yùn)算數(shù)據(jù)的運(yùn)算定義：定義在數(shù)據(jù)結(jié)構(gòu)上的一組運(yùn)算(操作)及其實(shí)現(xiàn)方法常用運(yùn)算：檢索、插入、刪除、更新、排序等。數(shù)據(jù)結(jié)構(gòu)36數(shù)據(jù)結(jié)構(gòu)練習(xí)以下表達(dá)中正確的選項(xiàng)是〔〕A〕算法的效率只與問題的規(guī)模有關(guān)，而與數(shù)據(jù)的存儲結(jié)構(gòu)無關(guān)B〕算法的時間復(fù)雜度是指執(zhí)行算法所需要的計算工作量C〕數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲結(jié)構(gòu)是一一對應(yīng)的D〕算法的時間復(fù)雜度與空間復(fù)雜度一定相關(guān)以下表達(dá)中正確的選項(xiàng)是〔〕A〕數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲結(jié)構(gòu)必定是一一對應(yīng)的B〕由于計算機(jī)存儲空間是向量式的存儲結(jié)構(gòu)，因此，數(shù)據(jù)的存儲結(jié)構(gòu)一定是線性結(jié)構(gòu)C〕程序設(shè)計語言中的數(shù)組一般是順序存儲結(jié)構(gòu)，因此，利用數(shù)組只能處理線性結(jié)構(gòu)D〕以上三種說法都不對答案：BD371.3線性表及順序存儲結(jié)構(gòu)線性表根本概念線性表的存儲結(jié)構(gòu)線性表的的運(yùn)算38線性表根本概念線性表線性表是最簡單、最常用的數(shù)據(jù)結(jié)構(gòu)是假設(shè)干個相同類型的數(shù)據(jù)元素組成的一個有限序列其中每個數(shù)據(jù)元素可由多個數(shù)據(jù)項(xiàng)組成。表中有且僅有一個開始元素〔根結(jié)點(diǎn)〕和一個結(jié)束元素〔終端結(jié)點(diǎn)〕，且所有元素都最多只有一個直接前趨〔前件〕和一個直接后繼〔后件〕例：考生成績登記表(table)39線性表實(shí)例：考生成績登記表34681張雷64834682王寧68234683周光明58834684李霞霞61534685錢欣608………………34700趙剛658準(zhǔn)考證號姓名總分表中的每一行是1個數(shù)據(jù)元素每個數(shù)據(jù)元素包含3個數(shù)據(jù)項(xiàng)：準(zhǔn)考證號、姓名、總分開始元素結(jié)束元素前件后件數(shù)據(jù)元素已經(jīng)排了序的線性表稱為有序線性表，簡稱有序表40線性表的運(yùn)算(操作)增加1個新的數(shù)據(jù)元素刪除1個指定數(shù)據(jù)元素查找指定的數(shù)據(jù)元素最高分考生最低分考生將表中的數(shù)據(jù)元素排序?qū)Ρ碇械臄?shù)據(jù)進(jìn)行計算計算平均分···34681張雷64834682王寧68234683周光明58834684李霞霞61534685錢欣608………………34700趙剛658準(zhǔn)考證號姓名總分41線性表存儲結(jié)構(gòu)順序存儲結(jié)構(gòu)：借助數(shù)據(jù)元素在存儲器中的相對位置來表示數(shù)據(jù)元素之間的邏輯關(guān)系鏈接表存儲結(jié)構(gòu)：利用地址指針來表示元素之間的邏輯關(guān)系a1a2低地址高地址a2是a1的后繼元素a1p1a2a2是a1的后繼元素42假設(shè)下面的有序表中姓名已按拼音排序例：有序表的實(shí)現(xiàn)方法之1使用數(shù)組實(shí)現(xiàn)，在內(nèi)存中順序存放元素：如果要在表中加一個姓名:馬明，結(jié)果為：程紅李軍劉林劉建平王曉林張小明010016022028034040046

程紅李軍劉林劉建平王曉林張小明010016022028034040046馬明分析：尋找指定的數(shù)據(jù)元素很容易插入元素或刪除元素很不方便程紅李軍劉林劉建平王曉林張小明內(nèi)存地址43有序表的實(shí)現(xiàn)方法之2使用鏈接表(linkedlist)實(shí)現(xiàn)：數(shù)據(jù)元素在內(nèi)存中可不按順序存放，它們之間的順序用“指針〞來表示指針實(shí)際上就是后繼數(shù)據(jù)元素的地址演示2種實(shí)現(xiàn)方法的比照：數(shù)組實(shí)現(xiàn)的空間開銷少；存取指定元素的速度比較塊鏈表實(shí)現(xiàn)時插入/刪除指定元素的速度快，表的長度不受限制第n個考生準(zhǔn)考證號、姓名、…∧第1個考生準(zhǔn)考證號、姓名、…Link第2個考生準(zhǔn)考證號、姓名、…Link第3個考生準(zhǔn)考證號、姓名、…Link441.4棧和隊(duì)列棧及根本運(yùn)算棧的存儲及運(yùn)算隊(duì)列及根本運(yùn)算45棧的根本概念棧及其根本運(yùn)算棧是一種特殊的線性表?xiàng)Ｏ薅ㄖ荒茉谝欢诉M(jìn)行插入與刪除運(yùn)算在棧中，允許插入與刪除的一端稱為棧頂，不允許插入與刪除的另一端稱為棧底棧頂元素總是最后被插入的元素，棧底元素總是最先被插入的元素。即棧是按照“先進(jìn)后出〞或“后進(jìn)先出〞的原那么組織數(shù)據(jù)的棧具有記憶作用46棧的根本概念棧的根本運(yùn)算入棧：指在棧頂插入一個元素退棧：指取出棧頂元素并賦值給一個變量讀棧頂元素：將棧頂元素賦值給指定變量47隊(duì)列的根本概念隊(duì)列及其根本運(yùn)算隊(duì)列是指允許在一端〔隊(duì)尾〕進(jìn)入插入，而在另一端〔隊(duì)頭〕進(jìn)行刪除的線性表。尾指針〔Rear〕指向隊(duì)尾元素，頭指針〔front〕指向排頭元素的前一個位置〔隊(duì)頭〕。隊(duì)列是“先進(jìn)先出〞或“后進(jìn)后出〞的線性表隊(duì)列的運(yùn)算：入隊(duì)：從隊(duì)尾插入一個數(shù)據(jù)退隊(duì)：從隊(duì)頭刪除一個數(shù)據(jù)48隊(duì)列的根本概念隊(duì)列及其根本運(yùn)算循環(huán)隊(duì)列及其運(yùn)算：所謂循環(huán)隊(duì)列，就是將隊(duì)列存儲空間的最后一個位置繞到第一個位置，形成邏輯上的環(huán)狀空間，供隊(duì)列循環(huán)使用。注意：循環(huán)隊(duì)列中元素的個數(shù)=rear-front。49棧與隊(duì)列練習(xí)按“先進(jìn)后出〞原那么組織數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)是______數(shù)據(jù)結(jié)構(gòu)分為線性結(jié)構(gòu)和非線性結(jié)構(gòu)，帶鏈的隊(duì)列屬于線性結(jié)構(gòu)下面對隊(duì)列的表達(dá)正確的選項(xiàng)是A)隊(duì)列屬于非線性表B)隊(duì)列按“先進(jìn)后出〞原那么組織數(shù)據(jù)C)隊(duì)列在隊(duì)尾刪除數(shù)據(jù)D)隊(duì)列按“先進(jìn)先出〞原那么組織數(shù)據(jù)設(shè)某循環(huán)對列的容量為50，頭指針front=5〔指向?qū)︻^元素的前一位置〕，尾指針rear=29〔指向隊(duì)尾元素〕，那么該循環(huán)隊(duì)列中共有_____個元素線性表的存儲結(jié)構(gòu)主要分為順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)。隊(duì)列是一種特殊的線性表，循環(huán)隊(duì)列是隊(duì)列的___存儲結(jié)構(gòu)答案：棧D24順序501.5線性鏈表線性鏈表根本概念線性鏈表的根本運(yùn)算51線性鏈表根本概念線性鏈表是用鏈接方式存儲的線性表線性鏈表特點(diǎn)：每個結(jié)點(diǎn)數(shù)據(jù)包括兩局部：存儲的數(shù)據(jù)〔數(shù)據(jù)域〕和下一結(jié)點(diǎn)的地址〔指針域〕鏈表結(jié)尾地址為NULL〔空指針〕頭指針：存放鏈表第一個結(jié)點(diǎn)地址的指針變量。頭指針是操作訪問整個鏈表的關(guān)鍵52線性鏈表王平90&張歡80&李林85&丁一79NULL......head鏈表特點(diǎn)：數(shù)據(jù)域：姓名，分?jǐn)?shù)指針域：“王平〞結(jié)尾存放“張歡〞地址......鏈表結(jié)尾地址為NULL〔空指針〕利用頭指針head順序操作訪問整個鏈表53線性鏈表根本概念雙向鏈表：指針域有兩個指針：一個指向下一結(jié)點(diǎn)，一個指向前一結(jié)點(diǎn)循環(huán)鏈表：鏈表結(jié)尾地址不為NULL〔空指針〕，而是存放第一個結(jié)點(diǎn)地址〔表頭地址〕王平90&張歡80&李林85&丁一79&......head54線性鏈表根本概念線性鏈表的運(yùn)算：線性鏈表的插入............p1p2p055線性鏈表根本概念線性鏈表的運(yùn)算：線性鏈表的刪除............p1p2561.6樹與二叉樹樹的根本概念二叉樹及根本性質(zhì)二叉樹的存儲結(jié)構(gòu)二叉樹的遍歷57樹的根本概念樹的根本概念樹是一種簡單的非線性結(jié)構(gòu)。沒有前件的結(jié)點(diǎn)只有一個，稱為樹的根結(jié)點(diǎn)，簡稱樹的根。沒有后件的結(jié)點(diǎn)稱為葉子結(jié)點(diǎn)ABCDEF根結(jié)點(diǎn)葉子結(jié)點(diǎn)父結(jié)點(diǎn)葉子結(jié)點(diǎn)父結(jié)點(diǎn)58樹的根本概念樹的根本概念樹結(jié)構(gòu)中，一個結(jié)點(diǎn)所擁有的后件的個數(shù)稱為該結(jié)點(diǎn)的度，所有結(jié)點(diǎn)中最大的度稱為樹的度。樹的最大層次稱為樹的深度下例：結(jié)點(diǎn)A的度為2，D的度為1，樹的深度為4ABCDEFXYZ59樹與二叉樹二叉樹及其根本性質(zhì)二叉樹是很有用的非線性結(jié)構(gòu)二叉樹特點(diǎn)：非空二叉樹只有一個根結(jié)點(diǎn)每一個結(jié)點(diǎn)最多有兩棵子樹，且分別稱為該結(jié)點(diǎn)的左子樹與右子樹二叉樹的度可以為0〔葉結(jié)點(diǎn)〕、

1〔只有一棵子樹〕

2〔有2棵子樹〕

ABCDEFXYZ60樹與二叉樹二叉樹根本性質(zhì)二叉樹的第k層上，最多有個結(jié)點(diǎn)深度為m的二叉樹最多有2m個結(jié)點(diǎn)。任意一棵二叉樹中，度數(shù)為0的結(jié)點(diǎn)〔即葉子結(jié)點(diǎn)〕總比度為2的結(jié)點(diǎn)多一個。具有n個結(jié)點(diǎn)的二叉樹，其深度至少為[log2n]+1，其中[log2n]表示取[log2n]的整數(shù)局部。61樹與二叉樹滿二叉樹除最后一層外，每一層上的所有結(jié)點(diǎn)都有兩個子結(jié)點(diǎn)完全二叉樹：除最后一層外，每一層上的結(jié)點(diǎn)數(shù)均到達(dá)最大值；在最后一層上只缺少右邊的假設(shè)干結(jié)點(diǎn)62樹與二叉樹練習(xí)某二叉樹中有n個度為2的結(jié)點(diǎn),那么該二叉樹中的葉子結(jié)點(diǎn)數(shù)為______。A)n+1B)n-1C)2nD)n/2一顆二叉樹中共有70個葉子結(jié)點(diǎn)與80個度為1的結(jié)點(diǎn)，那么該二叉樹中的總結(jié)點(diǎn)數(shù)為______。A〕219B〕221C〕229D〕231深度為5的滿二叉樹有個葉子結(jié)點(diǎn)答案：AA1663樹與二叉樹二叉樹的遍歷二叉樹的遍歷是指不重復(fù)地訪問二叉樹中的所有結(jié)