計(jì)算機(jī)科學(xué)導(dǎo)論-基于計(jì)算思維的思想與方法（第4版） 課件【ch07】問題求解的算法基礎(chǔ)

計(jì)算機(jī)科學(xué)導(dǎo)論基于計(jì)算思維的思想與方法問題求解的算法基礎(chǔ)第七章新工科建設(shè)之路·計(jì)算機(jī)類系列教材01算法——問題求解的核心算法——問題求解的核心01一、算法的基本概念算法研究史上最著名的古老算法是用于求兩個(gè)整數(shù)的最大公約數(shù)的歐幾里得(Euclid)算法。這個(gè)算法最早出現(xiàn)在大約公元前350——300年由古希臘數(shù)學(xué)家歐幾里得寫成的《Elements》(《幾何原本》)中，它被人們公認(rèn)為是算法史上的第一個(gè)算法，歐幾里得算法的原理是重復(fù)應(yīng)用等式1.算法的起源算法——問題求解的核心01一、算法的基本概念算法是求解問題的方法和步驟，并具有完整的規(guī)則。把算法歸納為以下5個(gè)顯著特征。(1)確定性；(2)有效性；(3)有窮性；(4)有零個(gè)或多個(gè)輸入；(5)有一個(gè)或多個(gè)輸出。2.算法的特征算法——問題求解的核心01二、算法的設(shè)計(jì)要求1.正確性(Correctness)正確性是指對一切合法的輸入，都能在有限次的計(jì)算后產(chǎn)生正確的結(jié)果。算法的正確是評價(jià)一個(gè)算法優(yōu)劣的重要指標(biāo)，一旦完成對算法的描述，必須證明它是正確的。2.可讀性(Readality)可讀性是指算法可供人們閱讀的容易程度。一個(gè)好的算法應(yīng)便于閱讀、理解、編碼、修改等。從書寫角度來說，結(jié)構(gòu)上要直觀、清晰、美觀，并在必要的地方加上注釋說明。算法——問題求解的核心01二、算法的設(shè)計(jì)要求3.健壯性(Robustness)健壯性是指一個(gè)算法對不合理輸入數(shù)據(jù)的反應(yīng)能力和處理能力。程序設(shè)計(jì)時(shí)要充分考慮異常情況。健壯性體現(xiàn)了思維的縝密性，如果沒有對算法進(jìn)行仔細(xì)認(rèn)真的考察，特別是極端數(shù)據(jù)、特殊數(shù)據(jù)的處理，就很可能使算法失去準(zhǔn)確性。4.算法的運(yùn)行效率算法的運(yùn)行效率是指在程序執(zhí)行時(shí)，所需耗用的時(shí)間和所占用的內(nèi)存空間。耗用的時(shí)間和占用的空間越少，則算法的運(yùn)行效率越高。算法的運(yùn)行效率是評價(jià)算法好壞的重要指標(biāo)。算法——問題求解的核心01三、算法的復(fù)雜性1.時(shí)間復(fù)雜度(TimeComplexity)算法的時(shí)間復(fù)雜度是指度量時(shí)間的復(fù)雜性，即算法的時(shí)間效率的指標(biāo)。換言之，時(shí)間復(fù)雜度是與求解問題的規(guī)模、算法輸入數(shù)據(jù)相關(guān)的函數(shù)，該函數(shù)表示算法運(yùn)行所花費(fèi)的時(shí)間。為了簡化問題，通常用算法運(yùn)行某段代碼的次數(shù)來代替準(zhǔn)確的執(zhí)行時(shí)間，記為T(n)。T即Time的首字母，T(n)中的n表示問題規(guī)模的大小，一般指待處理的數(shù)據(jù)量的大小。算法——問題求解的核心01三、算法的復(fù)雜性2.空間復(fù)雜度(SpaceComplexity)算法的空間復(fù)雜度是指算法運(yùn)行的存儲(chǔ)空間，是實(shí)現(xiàn)算法所需的內(nèi)存空間的大小。空間復(fù)雜度也是與求解問題規(guī)模、算法輸入數(shù)據(jù)相關(guān)的函數(shù)，記為S(n)?？臻g復(fù)雜度的分析方法與時(shí)間復(fù)雜度的分析是類似的，往往希望算法有常數(shù)數(shù)量級(jí)或多項(xiàng)式數(shù)量級(jí)的空間復(fù)雜度。算法——問題求解的核心01四、算法的描述方法1.用自然語言描述算法自然語言是人們?nèi)粘Ｋ褂玫恼Z言，如漢語、英語、日語等。用自然語言描述算法是最原始方法，也是最直觀、通俗易懂、為人們所熟悉的方法。算法——問題求解的核心01四、算法的描述方法2.用圖形描述算法由于用自然語言描述算法的邏輯結(jié)構(gòu)不是太好，對于稍復(fù)雜的算法問題很容易出錯(cuò)，因此常用圖形描述算法。目前，用來描述算法的圖形有3種：流程圖(FlowChart)、N-S圖和PAD圖，

它們各有其優(yōu)點(diǎn)，人們更多地習(xí)慣用流程圖描述算法，并特別適合初學(xué)者。算法——問題求解的核心01四、算法的描述方法3.用偽代碼描述算法偽代碼是一種介于自然語言與高級(jí)語言之間描述方法，常用偽代碼符號(hào)如表7-1所示。算法——問題求解的核心01四、算法的描述方法4.用程序設(shè)計(jì)語言描述算法無論是用自然語言或偽代碼，還是用流程圖所描述的算法，都不能被機(jī)器識(shí)別，最后必須將它們轉(zhuǎn)換成程序設(shè)計(jì)語言。因此，用程序設(shè)計(jì)語言來描述算法是最直接有效的方法。存在以下不足：(1)要求設(shè)計(jì)者必須熟練掌握程序設(shè)計(jì)語言和編程技巧；(2)要求描述計(jì)算步驟的細(xì)節(jié)，從而忽視了算法的本質(zhì)；

(3)程序設(shè)計(jì)語言基于串行，算法的邏輯流程難以遵循，邏輯較復(fù)雜時(shí)問題越顯嚴(yán)重。02數(shù)值數(shù)據(jù)求解——算法策略數(shù)值數(shù)據(jù)求解——算法策略02窮舉算法(ExhaustiveAttackAlgorithm)，也稱為枚舉算法(EnumerateAlgorithm)或稱為強(qiáng)力算法(Brute-forceAlgorithm)，是針對要解決的問題，列舉所有可能的情況，逐個(gè)判斷哪些條件符合問題所要求的約束條件，從而得到問題的解。一、窮舉算法數(shù)值數(shù)據(jù)求解——算法策略021.算法思想(1)確定范圍：按照問題要求確定問題解的大致范圍一一列舉，遍歷所有可能的組合值。(2)條件約束：判斷題解是否符合正解條件，避免解題結(jié)果錯(cuò)誤。(3)循環(huán)運(yùn)算：使可能解的范圍降至最小，以便提高解題效益。一、窮舉算法數(shù)值數(shù)據(jù)求解——算法策略022.算法特點(diǎn)(1)算法優(yōu)點(diǎn)：思路簡單，問題的答案是一個(gè)有窮的集合，可以一一列舉出來。(2)算法缺點(diǎn)：運(yùn)算量比較大，解題效率不高。(3)算法應(yīng)用：適用于決策類最優(yōu)化問題。一、窮舉算法數(shù)值數(shù)據(jù)求解——算法策略02回溯算法(Back-TrackingAlgorithm)是窮舉法和試探法的結(jié)合，它將要解決的問題的所有解空間(SolutionSpace)分為若干節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)有若干可供選擇的后續(xù)節(jié)點(diǎn)，然后按某種順序逐一窮舉和試驗(yàn)。若不滿足條件，返回到上一層節(jié)點(diǎn)，恢復(fù)剛才的參數(shù)，再試探其他分支。二、回溯算法數(shù)值數(shù)據(jù)求解——算法策略02二、回溯算法1.算法思想回溯法是一種解決問題的方法，而不是一種特殊算法?；厮菟惴ㄒ话惆凑找韵虏襟E求解：(1)定義：針對所給問題，定義問題的解空間，至少包含問題的一個(gè)最優(yōu)解；(2)確定：根據(jù)定義，確定易于搜索的解空間結(jié)構(gòu)，使得能用回溯方法搜索整個(gè)解空間；(3)搜索：以深度優(yōu)先的方式搜索解空間，并且在搜索過程中用剪枝函數(shù)避免無效搜索。數(shù)值數(shù)據(jù)求解——算法策略02二、回溯算法2.算法特點(diǎn)回溯算法本質(zhì)上是一種窮舉法，但它是比窮舉“聰明”的搜索技術(shù)，有“通用解題法”之稱。當(dāng)一個(gè)問題沒有顯而易見的解法時(shí)，可以嘗試使用回溯法求解。不過，該算法耗時(shí)多，效率低。由于回溯算法是對解空間的深度優(yōu)先探索，所以在一般情況下可用遞歸函數(shù)來實(shí)現(xiàn)回溯算法。數(shù)值數(shù)據(jù)求解——算法策略02三、遞推算法遞推算法(RecurrenceAlgorithm)是根據(jù)問題本身的已知條件，利用特定關(guān)系得出中間推論，直至得到結(jié)果的算法。遞推算法本質(zhì)上屬于歸納法，即根據(jù)簡單、特殊實(shí)例，總結(jié)一般性結(jié)論。遞推算法分為順推和反推(逆推)兩種。順推是指從已知條件出發(fā)，逐步推算出求解結(jié)果；反推是指從已知結(jié)果出發(fā)，用迭代表達(dá)式逐步推出問題的開始條件(初始值)，它是順推的逆過程。數(shù)值數(shù)據(jù)求解——算法策略02三、遞推算法1.算法思想遞推方法是假設(shè)問題在某一步某個(gè)條件下成立，下一步可根據(jù)這一步所得到的關(guān)系進(jìn)行推導(dǎo)，把一個(gè)復(fù)雜、龐大的計(jì)算過程轉(zhuǎn)化為簡單過程的多次重復(fù)運(yùn)算。遞推算法一般按以下步驟進(jìn)行。(1)確定問題數(shù)據(jù)之間的特定關(guān)系，并將這種關(guān)系規(guī)律歸納成簡捷的遞推關(guān)系式

；(2)確定由已知的基礎(chǔ)數(shù)據(jù)可以遞推出后面的數(shù)據(jù)，而且盡量簡化變量，以減少變量暫用空間。數(shù)值數(shù)據(jù)求解——算法策略02三、遞推算法2.算法特點(diǎn)每相鄰兩項(xiàng)之間的變化有一定規(guī)律性，通過后項(xiàng)與前項(xiàng)之間的關(guān)系，從初始條件入手，一步步地按遞推關(guān)系進(jìn)行遞推，直到求出最終結(jié)果。(1)算法優(yōu)點(diǎn)：思路簡單，無論是程序編寫還是程序調(diào)試，都很方便，而且程序運(yùn)行效率高。(2)算法缺點(diǎn)：運(yùn)算的過程值較多，耗用空間大。適合大、小規(guī)模之間的關(guān)系。(3)算法應(yīng)用：適用于已知本身?xiàng)l件，利用特定關(guān)系得出中間推論，直至得到最終結(jié)果。數(shù)值數(shù)據(jù)求解——算法策略02四、迭代算法迭代算法(IterativeAlgorithm)就是在數(shù)的序列中建立起后項(xiàng)與前項(xiàng)之間的關(guān)系，通過從一個(gè)初始值出發(fā)，不斷用變量的舊值遞推新值的過程。迭代算法包括求精確解和近似解的算法。1.迭代算法思想所謂迭代，就是為了逼近所需目標(biāo)或結(jié)果而重復(fù)反饋，每次迭代的結(jié)果作為下次迭代的初始值。迭代與遞推的區(qū)別源于問題的性質(zhì)，在實(shí)際問題中可能遇到以下兩種情況。(1)可以表示成數(shù)學(xué)上明確的遞推公式。(2)無法直接寫出顯式遞推公式：只能通過“迭代”，并且可分為精確迭代和近似迭代。數(shù)值數(shù)據(jù)求解——算法策略02四、迭代算法2.算法特點(diǎn)(1)算法優(yōu)點(diǎn)：對一組指令進(jìn)行重復(fù)執(zhí)行，每次執(zhí)行時(shí)都從變量的原值中推出它的一個(gè)新值。(2)算法缺點(diǎn)：如果方程無解，算法的近似根序列不會(huì)收斂，迭代過程失?。蝗绻匠屉m然有解但迭代公式選擇不當(dāng)，或迭代的初始近似根選擇不合理，也會(huì)導(dǎo)致迭代失敗。(3)算法應(yīng)用：是遞推算法的反推形式，適用于方程求根，方程組求解，矩陣求特征值等。數(shù)值數(shù)據(jù)求解——算法策略02五、遞歸算法遞歸算法(RecursiveAlgorithm)是指在定義算法的過程中，用自身的簡單情況來定義自身，直接或間接地調(diào)用自身的一種算法。一個(gè)直接或間接地調(diào)用自身的過程稱為遞歸過程(RecursiveProcedure)，一個(gè)使用函數(shù)自身給出定義的函數(shù)稱為遞歸函數(shù)(RecursiveFunction)。1.算法思想遞歸是一種強(qiáng)有力的數(shù)學(xué)工具，它可使問題的描述和求解變得簡潔和清晰，它有兩種形式。(1)直接遞歸(2)間接遞歸數(shù)值數(shù)據(jù)求解——算法策略02五、遞歸算法2.算法特點(diǎn)本質(zhì)上，遞歸和遞推都是同一種解決問題的思路，都是把問題進(jìn)行分解，但遞推是由小到大的推導(dǎo)，而遞歸則是由大到小的推導(dǎo)。(1)算法優(yōu)點(diǎn)：程序代碼簡潔、清晰，可讀性好。(2)算法缺點(diǎn)：如果遞歸層次太深(太多)，會(huì)導(dǎo)致堆棧溢出，而且遞歸算法運(yùn)行效率較低。(3)算法應(yīng)用：適用于當(dāng)問題本身或所涉及的數(shù)據(jù)結(jié)構(gòu)是遞歸定義的情況，可與分治法結(jié)合。數(shù)值數(shù)據(jù)求解——算法策略02六、分治算法分治算法(DivideandConquerAlgorithm)是將一個(gè)難以直接解決的大問題，劃分成一些規(guī)模較小子問題，以便各個(gè)擊破。因此，分治算法是一種“分而治之”的算法思想策略。1.算法思想由分治算法產(chǎn)生的子問題往往是原問題的較小模式，最終使子問題縮小到容易直接求解，自然導(dǎo)致遞歸過程的產(chǎn)生，也為使用遞歸技術(shù)提供了方便。分治算法一般按照以下步驟求解：(1)分解(2)求解(3)合并數(shù)值數(shù)據(jù)求解——算法策略02六、分治算法2.算法特點(diǎn)“分而治之”策略是很多高效算法的思想基礎(chǔ)，由分治法產(chǎn)生的子問題往往是原問題的較小或最小模式，這既導(dǎo)致了遞歸過程的產(chǎn)生，也為使用遞歸技術(shù)提供了方便，最終使子問題縮小到很容易直接求出其解。分治算法與遞歸算法像一對孿生兄弟經(jīng)常同時(shí)應(yīng)用在算法設(shè)計(jì)中，并由此產(chǎn)生許多高效算法，如漢諾塔問題、折半查找、快速排序等，都是分治策略運(yùn)用的典型實(shí)例。數(shù)值數(shù)據(jù)求解——算法策略02七、貪心算法貪心算法(GreedyAlgorithm)是把一一個(gè)復(fù)雜問題分解為一系列較為簡單的局部最優(yōu)選擇，每一步選擇都是對當(dāng)前解的一個(gè)擴(kuò)展，直到獲得問題的完整解。貪心算法的典型應(yīng)用是求解最優(yōu)問題(OptimizationProblem)，即在滿足一定約束條件下，使得目標(biāo)函數(shù)的值達(dá)到最大或最小。數(shù)值數(shù)據(jù)求解——算法策略02七、貪心算法1.算法思想貪心算法的指導(dǎo)思想是將待求的問題分解成若干子問題進(jìn)行分步求解，并且每一步總是做出當(dāng)前最好的選擇，即得到局部最優(yōu)解，然后將各個(gè)子問題的局部最優(yōu)解組合成原問題的一個(gè)解。由此可見，貪心算法體現(xiàn)了“快刀斬亂麻”的思想，以當(dāng)前和局部利益最大化為導(dǎo)向的求解策略。2.算法特點(diǎn)貪心算法是最接近人類日常思維的一種問題求解方法，例如“背包問題”“田忌賽馬”等都是典型實(shí)例。數(shù)值數(shù)據(jù)求解——算法策略02八、動(dòng)態(tài)規(guī)劃1.算法思想為了解決某一多階段決策過程的優(yōu)化問題，而依次做出n個(gè)決策D1，D2，.，Dn；如果這個(gè)決策序列是最優(yōu)的，不論前面決策是怎樣的，以后的最優(yōu)決策取決于由前面決策所確定的當(dāng)前狀態(tài)。動(dòng)態(tài)規(guī)劃一般按照以下步驟求解。(1)劃分(2)推導(dǎo)(3)記錄數(shù)值數(shù)據(jù)求解——算法策略02八、動(dòng)態(tài)規(guī)劃2.算法特點(diǎn)(1)算法優(yōu)點(diǎn)：能夠得到全局最優(yōu)解，可以得到一族最優(yōu)解，由于動(dòng)態(tài)規(guī)劃方法反映了動(dòng)態(tài)過程演變的聯(lián)系和特征，在計(jì)算時(shí)可以利用實(shí)際知識(shí)和經(jīng)驗(yàn)提高求解效率。(2)算法缺點(diǎn)：一是沒有統(tǒng)一的標(biāo)準(zhǔn)模型；二是數(shù)值方法求解時(shí)需要額外的內(nèi)存空間。(3)算法應(yīng)用：動(dòng)態(tài)規(guī)劃方法是解決復(fù)雜問題的思維方法，在經(jīng)濟(jì)管理、生產(chǎn)調(diào)度、工程技術(shù)和最優(yōu)控制值等方面得到廣泛應(yīng)用，用動(dòng)態(tài)規(guī)劃方法求解比用其它方法求解更為方便、有效。03非數(shù)值數(shù)據(jù)處理——數(shù)據(jù)結(jié)構(gòu)非數(shù)值數(shù)據(jù)處理——數(shù)據(jù)結(jié)構(gòu)03一、線性表結(jié)構(gòu)線性表(LinearTable)是由有限個(gè)相同的數(shù)據(jù)元素所構(gòu)成的序列，通常記為a1，a2，...an。除了第一個(gè)元素只有直接后繼、最后一個(gè)元素只有直接前驅(qū)，其余數(shù)據(jù)元素都有一個(gè)直接前驅(qū)和一個(gè)直接后繼。學(xué)生檔案表是一個(gè)典型的線性表。1.線性表的定義非數(shù)值數(shù)據(jù)處理——數(shù)據(jù)結(jié)構(gòu)03一、線性表結(jié)構(gòu)將一個(gè)線性表存儲(chǔ)到計(jì)算機(jī)中可以采用多種不同的方法來實(shí)現(xiàn)，通常采用的方法有順序存儲(chǔ)結(jié)構(gòu)(也稱為靜態(tài)存儲(chǔ)結(jié)構(gòu))和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)(也稱為動(dòng)態(tài)存儲(chǔ)結(jié)構(gòu))。2.線性表的實(shí)現(xiàn)非數(shù)值數(shù)據(jù)處理——數(shù)據(jù)結(jié)構(gòu)03一、線性表結(jié)構(gòu)線性表是最簡單、最常用的一種數(shù)據(jù)結(jié)構(gòu)，通常用于對大量數(shù)據(jù)元素進(jìn)行隨機(jī)存取的情況，例如，程序設(shè)計(jì)中使用的數(shù)組和字符串，由學(xué)生學(xué)籍信息構(gòu)成的檔案表項(xiàng)，用計(jì)算機(jī)進(jìn)行學(xué)籍管理時(shí)對數(shù)據(jù)表項(xiàng)實(shí)現(xiàn)添加、刪除、修改、查找、存儲(chǔ)等操作，都是線性表的典型應(yīng)用。若對線性表的這些基本操作加以一定的限制，則形成特殊結(jié)構(gòu)的線性表，即棧結(jié)構(gòu)和隊(duì)列結(jié)構(gòu)。3.線性表的應(yīng)用非數(shù)值數(shù)據(jù)處理——數(shù)據(jù)結(jié)構(gòu)03二、棧結(jié)構(gòu)1.棧結(jié)構(gòu)的定義棧(Stack)或堆棧是限制線性表中元素的插入和刪除只能在線性表的同一端進(jìn)行的一種特殊線性表，是一種“先進(jìn)后出”的數(shù)據(jù)結(jié)構(gòu)，首先存入棧中的元素在棧底(Bottom)，最后存入棧中的元素在棧項(xiàng)(Top)，，它是允許插入或刪除的端口，沒有元素的堆棧稱為空棧。棧結(jié)構(gòu)形如子彈夾，其數(shù)據(jù)動(dòng)態(tài)如圖7-12所示。非數(shù)值數(shù)據(jù)處理——數(shù)據(jù)結(jié)構(gòu)03二、棧結(jié)構(gòu)2.棧結(jié)構(gòu)的實(shí)現(xiàn)棧結(jié)構(gòu)的具體實(shí)現(xiàn)取決于棧的存儲(chǔ)結(jié)構(gòu)，存儲(chǔ)結(jié)構(gòu)不同，其相應(yīng)的算法描述方法也不同。存儲(chǔ)結(jié)構(gòu)通常分為順序存儲(chǔ)和鏈接存儲(chǔ)兩種形式。3.棧結(jié)構(gòu)的應(yīng)用在程序設(shè)計(jì)中通常用于數(shù)據(jù)逆序處理的各種場合，如對數(shù)據(jù)進(jìn)行首尾元素互換的排序操作、函數(shù)嵌套調(diào)用時(shí)返回地址的存放、編譯過程中的語法分析等。在程序設(shè)計(jì)中，函數(shù)嵌套調(diào)用和遞歸調(diào)用的實(shí)現(xiàn)都包含棧的應(yīng)用。非數(shù)值數(shù)據(jù)處理——數(shù)據(jù)結(jié)構(gòu)03三、隊(duì)列結(jié)構(gòu)隊(duì)列結(jié)構(gòu)也是一種運(yùn)算受限的線性表，其限制是僅允許在表的一端進(jìn)行插入，而在表的另一端進(jìn)行刪除。這種邏輯結(jié)構(gòu)被稱為隊(duì)列(Queue)，只允許插入的一端被稱為隊(duì)尾(Rear)，只允許刪除的一端被稱為隊(duì)首(Front)。1.隊(duì)列結(jié)構(gòu)的定義非數(shù)值數(shù)據(jù)處理——數(shù)據(jù)結(jié)構(gòu)03三、隊(duì)列結(jié)構(gòu)隊(duì)列結(jié)構(gòu)可以采用順序存儲(chǔ)結(jié)構(gòu)來實(shí)現(xiàn)，也可以采用鏈表存儲(chǔ)結(jié)構(gòu)來實(shí)現(xiàn)。順序存儲(chǔ)結(jié)構(gòu)：一般情況下，使用一維數(shù)組作為隊(duì)列的順序存儲(chǔ)空間；再設(shè)兩個(gè)指示器：一個(gè)指向隊(duì)頭元素位置的指示器front，另一個(gè)指向隊(duì)尾元素位置的指示器rear。鏈表存儲(chǔ)結(jié)構(gòu)：在一個(gè)鏈表隊(duì)列中需要設(shè)定兩個(gè)指針(頭指針和尾指針)，分別指向隊(duì)列的頭部和尾部。2.隊(duì)列結(jié)構(gòu)的實(shí)現(xiàn)非數(shù)值數(shù)據(jù)處理——數(shù)據(jù)結(jié)構(gòu)03三、隊(duì)列結(jié)構(gòu)隊(duì)列結(jié)構(gòu)可用于應(yīng)用系統(tǒng)中的事件規(guī)劃，典型的實(shí)例是CPU資源的競爭問題，如在操作系統(tǒng)中用來解決主機(jī)與外部設(shè)備之間速度不匹配或多個(gè)用戶引起的資源競爭問題。3.隊(duì)列結(jié)構(gòu)的應(yīng)用非數(shù)值數(shù)據(jù)處理——數(shù)據(jù)結(jié)構(gòu)03四、樹結(jié)構(gòu)1.樹結(jié)構(gòu)的定義樹結(jié)構(gòu)(TreeStructure)是一種非常重要的非線性數(shù)據(jù)結(jié)構(gòu)，該結(jié)構(gòu)因節(jié)點(diǎn)之間存在的分支、層次關(guān)系非常類似一顆倒立的樹而得名。(Subtree)。樹的定義是遞歸的，深刻地反映了樹的固有特性，即一棵非空樹是由若干子樹構(gòu)成的，而子樹又可由若干更小的子樹構(gòu)成。非數(shù)值數(shù)據(jù)處理——數(shù)據(jù)結(jié)構(gòu)03四、樹結(jié)構(gòu)2.二叉樹和哈夫曼樹二叉樹是指每個(gè)節(jié)點(diǎn)的度至多為2的有序樹，如圖7-15所示。哈夫曼樹又稱為最優(yōu)二叉樹，是指對于一組帶有確定權(quán)值的葉節(jié)點(diǎn)構(gòu)造出具有最小帶權(quán)路徑長度(最精簡、最高效描述)的二叉樹。非數(shù)值數(shù)據(jù)處理——數(shù)據(jù)結(jié)構(gòu)03四、樹結(jié)構(gòu)3.二叉樹的實(shí)現(xiàn)二叉樹的實(shí)現(xiàn)可以采用順序存儲(chǔ)結(jié)構(gòu)，也可以采用鏈表存儲(chǔ)結(jié)構(gòu)，但主要采用鏈表存儲(chǔ)結(jié)構(gòu)。順序存儲(chǔ)結(jié)構(gòu)：完全二叉樹采用自上而下，每層自左向右的順序存儲(chǔ)；非完全二叉樹也按完全二叉樹的形式來存儲(chǔ)，不過需要增加空節(jié)點(diǎn)。鏈表存儲(chǔ)結(jié)構(gòu)：用順序存儲(chǔ)結(jié)構(gòu)存放一般的二叉樹比較浪費(fèi)存儲(chǔ)空間，所以通常采用鏈表的方式存儲(chǔ)。非數(shù)值數(shù)據(jù)處理——數(shù)據(jù)結(jié)構(gòu)03四、樹結(jié)構(gòu)4.二叉樹的遍歷遍歷(Traversal)是指沿著某條搜索路線依次對樹中每個(gè)節(jié)點(diǎn)僅做一次訪問。二叉樹遍歷的實(shí)質(zhì)是將非線性結(jié)構(gòu)的數(shù)據(jù)線性化的過程，并先遍歷左子樹，再遍歷右子樹。5.樹結(jié)構(gòu)的應(yīng)用樹結(jié)構(gòu)在計(jì)算機(jī)領(lǐng)域中具有廣泛應(yīng)用。例如，在編譯系統(tǒng)中，用樹來表示源程序的語法結(jié)構(gòu)；在人工智能系統(tǒng)中，用樹來描述數(shù)據(jù)模型；在文件系統(tǒng)中，用樹來描述目錄結(jié)構(gòu)；在數(shù)據(jù)庫中，用樹結(jié)構(gòu)來組織信息和大型列表的搜索。04數(shù)據(jù)元素操作——查找和排序數(shù)據(jù)元素操作——查找和排序04一、查找算法1.順序查找(SequentialSearch)順序查找，又稱為線性查找，是一種最簡單的查找算法，既適用于線性表的順序存儲(chǔ)結(jié)構(gòu)，也適用于線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。(1)順序查找算法思想：順序查找是從線性表的一段開始，順序掃描該線性表。(2)順序查找算法分析：對n個(gè)元素進(jìn)行順序查找，若查找成功，則所需比較關(guān)鍵字的次數(shù)最少為1，即R[n]