全套課件-數(shù)據(jù)結(jié)構(gòu)與算法分析

第1章數(shù)據(jù)結(jié)構(gòu)概論1.1什么是數(shù)據(jù)結(jié)構(gòu)1.2基本概念和術(shù)語1.2.1數(shù)據(jù)結(jié)構(gòu)的發(fā)展

1.2.2數(shù)據(jù)結(jié)構(gòu)的基本概念和術(shù)語

1.3抽象數(shù)據(jù)類型和數(shù)據(jù)結(jié)構(gòu)1.4學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的意義1.5算法1.5.1算法及其性質(zhì)1.5.2算法描述的分析

1.1什么是數(shù)據(jù)結(jié)構(gòu)信息中的各個數(shù)據(jù)元素并不是孤立存在的，它們之間存在著一定的結(jié)構(gòu)關(guān)系。一般說來，使用計算機(jī)解決具體問題時，通常需要幾個步驟：分析具體問題得到數(shù)學(xué)模型，設(shè)計解決數(shù)學(xué)模型的算法，編制程序并調(diào)試，最后得到最終答案。在數(shù)據(jù)結(jié)構(gòu)中數(shù)據(jù)之間的關(guān)系主要有兩種，它們分別是線性關(guān)系和非線性關(guān)系，其中非線性關(guān)系又可以分為樹型關(guān)系和圖關(guān)系。數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)是密不可分的兩個方面，在實現(xiàn)算法時，首先應(yīng)解決數(shù)據(jù)的存儲問題。1.1什么是數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)之間既要考慮存儲，又要考慮數(shù)據(jù)單位之間的關(guān)系，在確定了存儲結(jié)構(gòu)后，根據(jù)存儲的結(jié)構(gòu)再來確定相應(yīng)操作的實現(xiàn)方法。簡單說數(shù)據(jù)結(jié)構(gòu)是研究數(shù)據(jù)的存儲、數(shù)據(jù)之間的關(guān)系和對數(shù)據(jù)實現(xiàn)各種操作的一門學(xué)科。1.1什么是數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)的定義可以記作：Data-Structure=（D，R）其中D是數(shù)據(jù)元素的有限集合，R是D上的關(guān)系。一般情況下，“關(guān)系”是指數(shù)據(jù)元素之間存在的邏輯關(guān)系，也稱為數(shù)據(jù)的邏輯結(jié)構(gòu)。數(shù)據(jù)在計算機(jī)內(nèi)的存儲表示（或映象）稱為數(shù)據(jù)的存儲結(jié)構(gòu)或物理結(jié)構(gòu)。1.1什么是數(shù)據(jù)結(jié)構(gòu)邏輯結(jié)構(gòu)體現(xiàn)的是數(shù)據(jù)元素之間的邏輯關(guān)系，換句話說就是從操作對象中抽象出來的數(shù)學(xué)模型，因此又稱為抽象結(jié)構(gòu)，通常習(xí)慣說的數(shù)據(jù)結(jié)構(gòu)一般就是指的邏輯結(jié)構(gòu)。然而討論數(shù)據(jù)結(jié)構(gòu)的目的是為了在計算機(jī)中實現(xiàn)對數(shù)據(jù)的操作，因此還需要研究數(shù)據(jù)的存儲結(jié)構(gòu)。存儲結(jié)構(gòu)是數(shù)據(jù)在計算機(jī)內(nèi)的表示（映象），又稱物理結(jié)構(gòu)。它包括數(shù)據(jù)元素的表示和關(guān)系的表示。1.1什么是數(shù)據(jù)結(jié)構(gòu)由于映象的方法不同，所以同一種的邏輯結(jié)構(gòu)可以映象成兩種不同的存儲結(jié)構(gòu)：順序映象（順序存儲結(jié)構(gòu)）和非順序映象（非順序存儲結(jié)構(gòu)）。順序映象的特點是在順序存儲結(jié)構(gòu)（一般用一維數(shù)組）中體現(xiàn)數(shù)據(jù)之間的關(guān)系；而非順序存儲結(jié)構(gòu)則一般采用指針實現(xiàn)數(shù)據(jù)之間的關(guān)系，包括鏈?zhǔn)酱鎯Y(jié)構(gòu)（鏈表）和散列結(jié)構(gòu)等。數(shù)據(jù)的存儲結(jié)構(gòu)要能夠正確反映數(shù)據(jù)元素之間的邏輯關(guān)系。也就是說數(shù)據(jù)的邏輯結(jié)構(gòu)和數(shù)據(jù)的存儲結(jié)構(gòu)是密不可分的兩個方面，任何一個算法的設(shè)計取決于選定的邏輯結(jié)構(gòu)，而算法的實現(xiàn)則依賴于采用的存儲結(jié)構(gòu)。1.1什么是數(shù)據(jù)結(jié)構(gòu)順序映象（順序存儲結(jié)構(gòu)）是借助元素在存儲器中位置表示數(shù)據(jù)元素之間的邏輯關(guān)系，或邏輯上相鄰的結(jié)點存儲在物理位置上相鄰的存儲單元里，結(jié)點的邏輯關(guān)系由存儲單元的鄰接關(guān)系來體現(xiàn)；而非順序映象（鏈?zhǔn)酱鎯Y(jié)構(gòu)）是借助元素存儲地址的指針表示元素之間的邏輯關(guān)系，或邏輯上相鄰的結(jié)點在物理位置上可相鄰，可不相鄰，邏輯關(guān)系由附加的指針段表示。1.1什么是數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)的非順序存儲結(jié)構(gòu)除包括鏈?zhǔn)酱鎯Y(jié)構(gòu)（簡稱鏈表）以外，還有散列存儲結(jié)構(gòu)、索引存儲結(jié)構(gòu)等。鏈?zhǔn)酱鎯Y(jié)構(gòu)是利用指針直接表示數(shù)據(jù)元素之間的關(guān)系。散列結(jié)構(gòu)的基本思想是根據(jù)結(jié)點的關(guān)鍵字，利用散列函數(shù)直接計算出該結(jié)點的存儲地址。索引存儲結(jié)構(gòu)是指在存儲結(jié)點信息的同時，還建立附加的索引表。索引表的每一項稱為索引項，索引項的一般形式是：（關(guān)鍵字，地址）。關(guān)鍵字：能夠惟一標(biāo)識一個結(jié)點的那些數(shù)據(jù)項集合；索引存儲結(jié)構(gòu)分為稠密索引和稀疏索引，其中稠密索引是指每個結(jié)點在索引表中都有一個索引項的索引表；而稀疏索引是指一組結(jié)點在索引表中對應(yīng)一個索引項的索引表。1.1什么是數(shù)據(jù)結(jié)構(gòu)針對存儲結(jié)構(gòu)，數(shù)據(jù)元素存儲在計算機(jī)中，應(yīng)對每個數(shù)據(jù)元素確定其取值范圍屬性就是數(shù)據(jù)類型。數(shù)據(jù)類型是和數(shù)據(jù)結(jié)構(gòu)密切相關(guān)的一個概念，用以刻畫（程序）操作對象的特征。數(shù)據(jù)類型根據(jù)是否允許分解分為原子類型和結(jié)構(gòu)類型，其中原子類型是指其值不可再分的數(shù)據(jù)類型，例如整型、字符型等；而結(jié)構(gòu)類型是指其值可以再分解為若干成分（分量）的數(shù)據(jù)類型，例如數(shù)組的值由若干分量組成。根據(jù)數(shù)據(jù)的結(jié)構(gòu)（邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)）特性在數(shù)據(jù)的生存期間的變動情況，將數(shù)據(jù)結(jié)構(gòu)分為靜態(tài)結(jié)構(gòu)和動態(tài)結(jié)構(gòu)。靜態(tài)結(jié)構(gòu)是指在數(shù)據(jù)存在期不發(fā)生任何變動，例如高級語言中的靜態(tài)數(shù)組；而動態(tài)結(jié)構(gòu)是指在一定范圍內(nèi)結(jié)構(gòu)的大小可以發(fā)生變動，如使用的堆棧。1.1什么是數(shù)據(jù)結(jié)構(gòu)總之，數(shù)據(jù)結(jié)構(gòu)所要研究的主要內(nèi)容簡單歸納為以下三個方面：⑴研究數(shù)據(jù)元素之間的客觀聯(lián)系（邏輯結(jié)構(gòu)）；⑵研究數(shù)據(jù)在計算機(jī)內(nèi)部的存儲方法（存儲結(jié)構(gòu)）；⑶研究如何在數(shù)據(jù)的各種結(jié)構(gòu)（邏輯的和物理的）上實施有效的操作或處理（算法）。所以數(shù)據(jù)結(jié)構(gòu)是一門抽象地研究數(shù)據(jù)之間的關(guān)系的學(xué)科。1.2基本概念和術(shù)語1.2.1數(shù)據(jù)結(jié)構(gòu)的發(fā)展數(shù)據(jù)結(jié)構(gòu)作為一門獨(dú)立的課程始于1968年，在我國數(shù)據(jù)結(jié)構(gòu)作為一門獨(dú)立課程在80年代初，早期的數(shù)據(jù)結(jié)構(gòu)對課程的范圍沒有明確的規(guī)定，數(shù)據(jù)結(jié)構(gòu)的內(nèi)容幾乎和圖論、樹的理論是相同的，在60到70年代隨著大型程序的出現(xiàn)，軟件也相對獨(dú)立，結(jié)構(gòu)程序設(shè)計逐步成為程序設(shè)計方法學(xué)的主要內(nèi)容，人們已經(jīng)認(rèn)識到程序設(shè)計的實質(zhì)就是對所確定的問題選擇一種好的結(jié)構(gòu)，從而設(shè)計一種好的算法。1.2基本概念和術(shù)語1.2.2數(shù)據(jù)結(jié)構(gòu)的基本概念和術(shù)語

數(shù)據(jù)結(jié)構(gòu)是指數(shù)據(jù)之間的相互形式，即數(shù)據(jù)的組織形式。數(shù)據(jù)結(jié)構(gòu)分為邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)。邏輯結(jié)構(gòu)是指數(shù)據(jù)元素之間的邏輯關(guān)系；存儲結(jié)構(gòu)是指數(shù)據(jù)元素及其關(guān)系在計算機(jī)內(nèi)的表示。數(shù)據(jù)是對客觀事物的符號表示，在計算機(jī)科學(xué)中是指輸入到計算機(jī)中并能夠被計算機(jī)識別、存儲和加工處理的符號的總稱。數(shù)據(jù)由數(shù)據(jù)項組成。數(shù)據(jù)項（數(shù)據(jù)元素）是指具有獨(dú)立含義的最小識別單位（數(shù)據(jù)中不可分割的最小單位）。數(shù)據(jù)項又稱項或字段。1.2基本概念和術(shù)語1.2.2數(shù)據(jù)結(jié)構(gòu)的基本概念和術(shù)語數(shù)據(jù)項有邏輯形式（logicalform）和物理形式（physicalform）兩個方面。用ADT給出的數(shù)據(jù)項的定義是它的邏輯形式，數(shù)據(jù)結(jié)構(gòu)中對數(shù)據(jù)項的實現(xiàn)是它的物理形式。在存儲結(jié)構(gòu)中包括了數(shù)據(jù)元素的表示和數(shù)據(jù)元素之間的關(guān)系表示。數(shù)據(jù)元素存儲在計算機(jī)中，計算機(jī)中表示信息的最小單位是二進(jìn)制數(shù)的一位，稱為位（bit），由若干位組成一個位串表示一個數(shù)據(jù)元素，稱為元素或結(jié)點，也可以描述為結(jié)點是數(shù)據(jù)處理的數(shù)據(jù)單位，它可能是一條記錄或一個數(shù)據(jù)項或組合數(shù)據(jù)項。對應(yīng)結(jié)點定義根據(jù)結(jié)點所處位置的不同可以將表中的結(jié)點分為前趨和后繼結(jié)點，對表中任意結(jié)點，處于該結(jié)點之前的所有結(jié)點稱為該結(jié)點的前趨結(jié)點，處于該結(jié)點之后的所有結(jié)點稱為該結(jié)點的后繼結(jié)點，與之相鄰的前趨結(jié)點稱為直接前趨結(jié)點，與之相鄰的后繼結(jié)點稱為直接后繼結(jié)點；表中的第一個結(jié)點稱為開始結(jié)點，表中最后一個沒有后繼的結(jié)點稱為終端結(jié)點。1.3抽象數(shù)據(jù)類型和數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)類型是指一個值的集合以及在這些值上定義的一組操作的總稱。抽象數(shù)據(jù)類型（AbstractDataType簡稱ADT）是指抽象數(shù)據(jù)組織和與之相關(guān)的操作。每一個操作由它的輸入和輸出定義。抽象數(shù)據(jù)類型的定義取決于它的一組邏輯特性，而與其在計算機(jī)內(nèi)的表示和實現(xiàn)無關(guān)。抽象數(shù)據(jù)類型可以定義為：（D，S，P）其中D表示數(shù)據(jù)對象，S是D上的關(guān)系集，P是對D的基本操作集。1.3抽象數(shù)據(jù)類型和數(shù)據(jù)結(jié)構(gòu)ADT使用偽碼描述為：ADT抽象數(shù)據(jù)類型名{

數(shù)據(jù)對象：<數(shù)據(jù)對象的定義>

數(shù)據(jù)關(guān)系：<數(shù)據(jù)關(guān)系的定義>

基本操作：<基本操作的定義>}ADT抽象數(shù)據(jù)類型名1.4學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的意義算法+數(shù)據(jù)結(jié)構(gòu)=程序。其中數(shù)據(jù)結(jié)構(gòu)是指數(shù)據(jù)邏輯結(jié)構(gòu)和物理結(jié)構(gòu)，算法是對數(shù)據(jù)運(yùn)算的描述。由此可見程序設(shè)計的實質(zhì)是對具體問題選擇一種好的數(shù)據(jù)結(jié)構(gòu)，再設(shè)計一個好的算法，而好的算法通常取決于實際問題的數(shù)據(jù)結(jié)構(gòu)。1.5算法1.5.1算法及其性質(zhì)算法是指解決問題的一種方法或者一個過程。一個問題可以用多種算法來解決，一個給定的算法解決一個特定的問題。數(shù)據(jù)結(jié)構(gòu)與算法之間存在著密切的關(guān)系?？梢哉f不了解施加于數(shù)據(jù)上的算法需求就無法決定數(shù)據(jù)結(jié)構(gòu)；反之算法的結(jié)構(gòu)設(shè)計和選擇又依賴于作為其基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)。即數(shù)據(jù)結(jié)構(gòu)為算法提供了工具。算法是利用這些工具來實施解決問題的最優(yōu)方案。1.5算法1.5.1算法及其性質(zhì)算法就是解決問題的方法。算法是解決某個特定問題的一些指令的集合；由人們組織起來加以準(zhǔn)備加以實施的有限的基本步驟。流程圖是圖形化的算法，程序是用計算機(jī)語言描述的算法。在計算機(jī)領(lǐng)域內(nèi)，一個算法實質(zhì)上是根據(jù)處理問題的需要，在數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)的基礎(chǔ)上施加的一種運(yùn)算。1.5算法1.5.1算法及其性質(zhì)一個完整的算法應(yīng)該滿足以下幾條性質(zhì)：⑴正確性。算法必須完成所期望的功能，得到的結(jié)果必須是正確的。⑵確定性。組成算法的指令必須是清晰的、無二義性。也就是說算法的每一個步驟都必須準(zhǔn)確定義。準(zhǔn)確定義是指所描述的行為必須是對人或機(jī)器而言是可讀的、可執(zhí)行的。每一步必須在有限的時間內(nèi)執(zhí)行完畢，同時必須是我們所力所能及的，能夠依賴于具體的工具來執(zhí)行的工序。⑶有窮性。算法必須在有限的步驟內(nèi)結(jié)束。如果一個算法由無限的步驟組成，該算法不可能有計算機(jī)程序?qū)崿F(xiàn)。⑷有效性。算法的指令必須具有可執(zhí)行性。⑸可終止性。算法必須可以終止，即不能進(jìn)入死循環(huán)。一個算法可以沒有輸入，但是至少應(yīng)該有一個輸出。1.5算法1.5.2算法描述的分析

一、算法設(shè)計要求⑴正確性。算法設(shè)計應(yīng)滿足具體問題的需求。它至少應(yīng)該包括對輸入、輸出及加工過程等的明確的無歧義性的描述?！罢_”涵義通常包含程序無語法錯誤、程序能夠得到正確的結(jié)果、程序?qū)Σ缓戏ǖ臄?shù)據(jù)的輸入應(yīng)有滿足要求的結(jié)果。一般對程序的測試時，以錄入不合法數(shù)據(jù)得到滿足要求的結(jié)果作為衡量程序是否合格的標(biāo)準(zhǔn)。⑵可讀性。算法主要是為了人的閱讀與交流，算法可讀性好有助于人對算法的理解。⑶健壯性。當(dāng)輸入非法的數(shù)據(jù)時，算法能夠適當(dāng)?shù)刈鞒龇磻?yīng)或進(jìn)行處理，不會產(chǎn)生莫名其妙的輸出結(jié)果。⑷效率與低存儲量需求。效率是指算法的執(zhí)行時間，一般對問題的求解方法很多，執(zhí)行時間短的算法效率高。存儲量的需求是指算法執(zhí)行過程所需要的最大的存儲容量，存儲空間越小，則算法越好。1.5算法1.5.2算法描述的分析

二、算法分析算法的分析主要是指判斷算法的優(yōu)劣，判斷一個算法的好壞一般從兩個方面考慮，即從時間角度和從空間角度上衡量算法。一般算法分析從時間角度考慮的比較多。當(dāng)然判斷一個算法的好與壞，不能以時間或空間衡量簡單化，而是根據(jù)實際情況綜合考慮。度量一個程序的執(zhí)行時間通常有兩種方法：⑴事后統(tǒng)計方法。⑵事前分析估算的方法。1.5算法1.5.2算法描述的分析將算法的求解問題的輸入稱為問題的規(guī)模，并用一個整數(shù)n表示。在算法的每個步驟中，可能有若干條語句，而頻度就是指每條語句的執(zhí)行次數(shù)。一個算法的時間復(fù)雜度是指算法的時間耗費(fèi)。簡單說，就是以一條基本語句的執(zhí)行時間為基本單位，該算法所有語句中總的基本語句的執(zhí)行次數(shù)，就是該算法的時間耗費(fèi)，它是該算法所求解的問題規(guī)模n的函數(shù)。當(dāng)問題的規(guī)模n趨向無窮大時，我們把時間復(fù)雜度的數(shù)量階稱為算法的漸進(jìn)時間復(fù)雜度。一般我們把漸進(jìn)時間復(fù)雜度稱為算法的時間復(fù)雜度，記做“O”（Order）。1.5算法1.5.2算法描述的分析算法的時間復(fù)雜度，記做“O”（Order），它有嚴(yán)格的數(shù)學(xué)定義：若T（n）和f（n）是定義在正整數(shù)集合上的兩個函數(shù)，則T（n）＝O（f（n））表示存在正的常數(shù)C和n0，使得當(dāng)n

n0時都滿足0≤T（n）≤C*f（n）?？臻g復(fù)雜度（SpaceComplexity）類似于時間復(fù)雜度，是指該算法所耗費(fèi)的存儲空間，也是問題規(guī)模n的函數(shù)。一般是指漸進(jìn)空間復(fù)雜度。記作：S（n）=O（f（n））其中n是問題的規(guī)模（大小）。第2章線性表2.1線性表類型的定義2.2線性表的順序表示和實現(xiàn)2.3線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)2.3.1單向鏈表

2.3.2單鏈表的基本運(yùn)算

2.3.3循環(huán)鏈表

2.3.4雙鏈表

2.4鏈表應(yīng)用舉例2.5順序表和鏈表的比較2.1線性表類型的定義線性表是n個數(shù)據(jù)元素的有限序列。其一般描述為：A=（a1，a2，……an）其中A稱為線性表的名稱，每個ai（n≥i≥1）稱為線性表的數(shù)據(jù)元素，具體n的值含義則稱為線性表中包含有數(shù)據(jù)元素的個數(shù)，也稱為線性表的長度；當(dāng)n的值等于0時，表示該線性表是空表。每個數(shù)據(jù)元素的含義在不同情況下各不相同，它們可能是一個字母、一個數(shù)字、也可以是一條記錄等。一般情況下，在線性表中每個ai的描述的是一組相同屬性的數(shù)據(jù)。2.1線性表類型的定義線性表的離散定義是：B=<A，R>，其中A包含n個結(jié)點（a1，a2……an），R只包含一個關(guān)系。R={（ai-1，ai）|I=1，2，……n}，線性表中包含的數(shù)據(jù)元素個數(shù)為線性表的長度。一個數(shù)據(jù)元素通常包含多個數(shù)據(jù)項，此時每個數(shù)據(jù)元素稱為記錄，含有大量的記錄的線性表稱為文件。在稍微復(fù)雜的線性表中，一個數(shù)據(jù)元素可以由若干個數(shù)據(jù)項組成。線性表是一個比較靈活的數(shù)據(jù)結(jié)構(gòu)，它的長度根據(jù)需要增長或縮短，也可以對線性表的數(shù)據(jù)元素進(jìn)行不同的操作（如訪問數(shù)據(jù)元素、插入、刪除數(shù)據(jù)元素等）。2.1線性表類型的定義使用抽象數(shù)據(jù)類型ADT定義線性表如下：ADTlist{數(shù)據(jù)對象：D={ai|ai∈元素集合，i=1，2，……n，n≥0}數(shù)據(jù)關(guān)系：R={〈ai-1，ai〉|ai-1，ai∈元素集合，i=1，2，……n}基本操作：{將以上對線性表的操作搬下來，每個函數(shù)注明輸入輸出}}ADTlist2.2線性表的順序表示和實現(xiàn)線性表的存儲結(jié)構(gòu)分為順序存儲和非順序存儲。其中順序存儲也稱為向量存儲或一維數(shù)組存儲。（1）順序表線性表的順序存儲，也稱為向量存儲，又可以說是一維數(shù)組存儲。線性表中結(jié)點存放的物理順序與邏輯順序完全一致，它叫向量存儲（一般指一維數(shù)組存儲），與此同時對應(yīng)A=（a1，a2，．．．a(chǎn)n）線性表而言。實際上，數(shù)據(jù)的存儲邏輯位置由數(shù)組的下標(biāo)決定。所以相鄰的元素之間地址的計算公式為（假設(shè)每個數(shù)據(jù)元素占有c個存儲單元）：LOC（ai+1）=LOC（ai）+c2.2線性表的順序表示和實現(xiàn)（1）順序表對線性表的所有數(shù)據(jù)元素，假設(shè)已知第一個數(shù)據(jù)元素a1的地址為d1，每個結(jié)點占有c個存儲單元，則第i個數(shù)據(jù)元素ai的地址為：di=d1+（i-1）*c線性表的第一個數(shù)據(jù)元素的位置通常稱做起始位置或基地址。線性表的這種機(jī)內(nèi)表示稱做線性表的順序存儲結(jié)構(gòu)或順序映象（Sequentialmapping），使用這種存儲結(jié)構(gòu)存儲的線性表又稱做順序表。其特點是，表中相鄰的元素之間具有相鄰的存儲位置。在使用一維數(shù)組時，數(shù)組的下標(biāo)起始位置根據(jù)給定的問題確定，或者根據(jù)實際的高級語言的規(guī)定確定。2.2線性表的順序表示和實現(xiàn)（1）順序表順序分配的線性表的可以直接使用一維數(shù)組描述為：typearraylist[]；//type的類型根據(jù)實際需要確定//通常用在數(shù)組的元素個數(shù)不是很多且可以對數(shù)組元素“枚舉”的情況下。也可以使用符合類型數(shù)組的動態(tài)進(jìn)行動態(tài)定義。typearrayname[]；該代碼只是對應(yīng)用數(shù)組的聲明，還沒有對該數(shù)組分配空間，因此不能訪問數(shù)組。只有對數(shù)組進(jìn)行初始化并申請內(nèi)存資源后，才能夠?qū)?shù)組中元素進(jìn)行使用和訪問。arrayname=newtype[arraysize]；其作用是給名稱為arrayname的數(shù)組分配arraysize個類型為type大小的空間；其中arraysize表示數(shù)組的長度，它可以是整型的常量和變量；如果arraysize是常量，則分配固定大小的空間，如果是變量，則表示根據(jù)參數(shù)動態(tài)分配數(shù)組的空間。2.2線性表的順序表示和實現(xiàn)（2）順序表基本運(yùn)算的實現(xiàn)線性表的順序存儲的結(jié)構(gòu)，容易實現(xiàn)線性表的某些操作，如隨機(jī)存取第i個數(shù)據(jù)元素等，但是在插入或刪除數(shù)據(jù)元素時則是比較煩瑣，所以順序存儲結(jié)構(gòu)比較適合存取數(shù)據(jù)元素。應(yīng)該注意java的數(shù)組下標(biāo)從0開始。下面考慮線性表順序存儲的插入、刪除和排序的實現(xiàn)方法。順序表的“求表長”和取第i個數(shù)據(jù)元素的時間復(fù)雜度均為O（1），因為可以直接求出線性表的長度，順序存儲下可可以實現(xiàn)隨機(jī)存取，可以直接取得數(shù)據(jù)元素，而不需要移動元素。2.3線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)線性表的順序存儲結(jié)構(gòu)的特點是邏輯關(guān)系上相鄰的兩個元素在物理位置上也相鄰，因此隨機(jī)存取元素時比較簡單，但是這個特點也使得在插入和刪除元素時，造成大量的數(shù)據(jù)元素移動，同時如果使用靜態(tài)分配存儲單元，還要預(yù)先占用連續(xù)的存儲空間，可能造成空間的浪費(fèi)或空間的溢出。如果采用鏈?zhǔn)酱鎯?，就不要求邏輯上相鄰的?shù)據(jù)元素在物理位置上也相鄰，因此它沒有順序存儲結(jié)構(gòu)所具有的弱點，但同時也失去了可隨機(jī)存取的優(yōu)點。2.3線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)2.3.1單向鏈表任意存儲單元存儲線性表的數(shù)據(jù)元素，對于鏈?zhǔn)酱鎯€性表時，其特點形式如圖所示：DATANEXT其中data是數(shù)據(jù)域，存放數(shù)據(jù)元素的值；next是指針域，存放相鄰的下一個結(jié)點的地址，單向鏈表是指結(jié)點中的指針域只有一個的沿著同一個方向表示的鏈?zhǔn)酱鎯Y(jié)構(gòu)。因為結(jié)點是一個獨(dú)立的對象，所以能夠?qū)崿F(xiàn)獨(dú)立的結(jié)點類。2.3線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)2.3.1單向鏈表對于鏈?zhǔn)椒峙渚€性表，整個鏈表的存取必須是從頭指針開始，頭指針指示鏈表中第一個結(jié)點的存儲位置。同時由于最后一個數(shù)據(jù)元素，沒有直接后繼，則線性鏈表中最后一個結(jié)點的指針為“空”（null）。在使用單鏈表結(jié)點時，必須完成三步：首先創(chuàng)建一個新結(jié)點；為該結(jié)點賦一個新值；新結(jié)點的next域賦值個當(dāng)前元素；當(dāng)前結(jié)點的前驅(qū)的next域要指向新插入的結(jié)點。2.3線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)2.3.2單鏈表的基本運(yùn)算①建立鏈表

因為單向鏈表的長度不固定，所以應(yīng)采用動態(tài)建立單向鏈表的方法。動態(tài)地建立單向鏈表的常用方法有如下兩種：尾插入法該方法是將新結(jié)點插到當(dāng)前鏈表的表尾上，為此必須增加一個尾指針tail的開銷，使其始終指向當(dāng)前鏈表的尾結(jié)點；或者增加一個循環(huán)用來查找鏈表的末尾結(jié)點，然后將新結(jié)點插入到鏈表的末尾。此方法的優(yōu)點是，在固定head頭指針后，該指針就不能再變了。不會因為不斷修改頭指針，造成頭指針的丟失。實際上動態(tài)建立鏈表的過程，就是不斷插入新結(jié)點的過程；2.3線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)2.3.2單鏈表的基本運(yùn)算頭插入法如果我們在鏈表的開始結(jié)點之前附加一個結(jié)點，并稱它為頭結(jié)點，那么會帶來以下兩個優(yōu)點：第一，由于開始結(jié)點的位置被存放在頭結(jié)點的指針域中，所以在鏈表的第一個位置上的操作就和在表的其他位置上操作一致，無須進(jìn)行特殊處理；第二，無論鏈表是否為空，其頭指針是指向頭結(jié)點的非空指針（空表中頭結(jié)點的指針域空），因此空表和非空表的處理也就統(tǒng)一了。2.3線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)②查找運(yùn)算按序號查找：在鏈表中，即使知道被訪問結(jié)點的序號i，也不能像順序表中那樣直接按序號i訪問結(jié)點，而只能從鏈表的頭指針出發(fā)，順著鏈域next逐個結(jié)點往下搜索，直至搜索到第i個結(jié)點為止（一般采用計數(shù)器的方式）。鏈表不是隨機(jī)存取結(jié)構(gòu)，只能順序存取。查找之前首先要做到從頭（head）開始，然后再逐個向后查找，查找過程中，每向后移動依次，計數(shù)器增加1，直到找到第i個結(jié)點（查找成功）或找完整個鏈表，沒有第i個結(jié)點（查找失敗）。2.3線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)②查找運(yùn)算按數(shù)值查找

查找結(jié)點有時可以按數(shù)值查找，按值查找是在鏈表中，查找是否有結(jié)點值等于給定值key的結(jié)點，若有的話，則返回首次找到的其值為key的結(jié)點的存儲位置；否則返回null。查找過程從開始結(jié)點出發(fā)，順著鏈域逐個將結(jié)點的值和給定值key作比較，有兩種情況，curr.val=key（查找成功）；curr=null也沒有出現(xiàn)curr.val=key的條件（查找失?。?.3線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)③求鏈表長度求鏈表長度基本同按序號查找，從頭結(jié)點開始順著鏈域掃描，用指針curr指向當(dāng)前掃描到的結(jié)點（原因是頭結(jié)點指針不能變），用len作計數(shù)器，累計當(dāng)前掃描的結(jié)點數(shù)，直至curr=null，返回長度len就可以了。④刪除結(jié)點刪除結(jié)點是將表中的某個結(jié)點從表中刪除，實際上還是利用查找算法，找到滿足條件的將要刪除的結(jié)點后，注意刪除過程中，使用的指針是被刪除結(jié)點的直接前驅(qū)結(jié)點的指針，直接刪除即可。2.3線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)⑤打印鏈表的所有元素

打印鏈表的所有結(jié)點的數(shù)值，與求鏈表的長度的方法基本類同，只是在找到每個結(jié)點的后面，增加一條打印命令，去掉計數(shù)命令，在次方法中需要特別處理的是鏈表為空時的情況。在整個單向鏈表的所有操作中，只要做到單向鏈表的初始化后，剩下比較重要的算法是對鏈表的插入、刪除和查詢操作，只要比較靈活地掌握插入、刪除和查詢?nèi)齻€基本的操作，其它的大部分操作可以利用以上的三種基本操作組合實現(xiàn)。2.3線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)在單鏈表中，因為指針是單一方向，結(jié)點的查找只能從前向后查找，不能反向查找，所以在插入、刪除結(jié)點時，特別是在某個結(jié)點之前插入，或者刪除某個結(jié)點時，需要利用結(jié)點的前趨結(jié)點的指針，所以在查找結(jié)點時，需要保留結(jié)點的直接前趨結(jié)點位置。也因為在單鏈表中，結(jié)點的查找只能從前向后查找，不能反向查找，所以在單向鏈表中，頭結(jié)點的非常重要，不能丟失。2.3線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)2.3.3循環(huán)鏈表

循環(huán)鏈表又稱為循環(huán)線性鏈表，其存儲結(jié)構(gòu)基本同單向鏈表，是在單向鏈表的基礎(chǔ)上加以改進(jìn)形成的，它可以解決單向鏈表中單方向查找的缺點。因為單向鏈表只能沿著一個方向，不能反向查找，并且最后一個結(jié)點的指針域的值是null，為解決單向鏈表的缺點，可以利用末尾結(jié)點的空指針完成前向查找。將單鏈表的末尾結(jié)點的指針域的null變?yōu)橹赶虻谝粋€結(jié)點，邏輯上形成一個環(huán)型，該存儲結(jié)構(gòu)稱之為單向循環(huán)鏈表。相對單鏈表而言，有以下的優(yōu)點：在不增加任何空間的情況下，能夠已知任意結(jié)點的地址，可以找到鏈表中的所有結(jié)點（環(huán)向查找）。當(dāng)然在查找某個結(jié)點的前驅(qū)結(jié)點時，需要增加時間開銷完成，查找的時間復(fù)雜度是O（n）。2.3線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)2.3.3循環(huán)鏈表

循環(huán)線性鏈表中已知鏈表中任何結(jié)點，可以找到鏈表中的所有結(jié)點，我們一般還是習(xí)慣把頭結(jié)點作為已知條件，但是如果已知條件是頭結(jié)點，將在以下的插入或刪除結(jié)點時造成不方便：刪除末尾結(jié)點第一個結(jié)點前插入新結(jié)點在第一種情況下，雖然能夠完成刪除，但是，需要我們從頭結(jié)點開始逐個查找結(jié)點直到找到最后一個結(jié)點的直接前驅(qū)結(jié)點，然后才能夠刪除，整個算法的時間復(fù)雜度是O（n）。在第二種情況下，雖然能夠完成插入，但是，需要我們從頭結(jié)點開始逐個查找結(jié)點直到找到最后一個結(jié)點，然后才能夠插入，因為我們需要修改最后一個結(jié)點的指針域，整個算法的時間復(fù)雜度是O（n）。2.3線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)2.3.3循環(huán)鏈表以上的兩種情況造成無謂的時間開銷，為解決這個問題，我們通常在循環(huán)鏈表以末尾結(jié)點指針為已知條件，這樣以上的兩種情況，都可以直接完成，因為已知末尾結(jié)點可以直接找到頭結(jié)點，此時的時間復(fù)雜度為O（1），這樣在不增加任何開銷的情況下，減少了時間的開銷?？盏难h(huán)線性鏈表根據(jù)定義可以與單向鏈表相同，也可以不相同。判斷循環(huán)鏈表的末尾結(jié)點條件也就不同于單向鏈表，不同之處在于是單向鏈表是判別最后結(jié)點的指針域是否為空，而循環(huán)線性鏈表末尾結(jié)點的判定條件是其指針域的值指向頭結(jié)點。2.3線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)2.3.3循環(huán)鏈表循環(huán)鏈表的插入、刪除運(yùn)算基本同單向鏈表，只是查找時判別條件不同而已；但是這種循環(huán)鏈表實現(xiàn)各種運(yùn)算時的危險之處在于：鏈表沒有明顯的尾端，可能使算法進(jìn)入死循環(huán)，所以判斷條件應(yīng)該用curr.next()!=head替換單向鏈表的curr.next()!=null完成遍歷所有結(jié)點。2.3線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)2.3.4雙鏈表

單循環(huán)鏈表中，雖然從任一已知結(jié)點出發(fā)能找到其直接前趨結(jié)點，但時間耗費(fèi)是O（n）。若希望從表中快速確定一個結(jié)點的直接前趨，可以在單鏈表的每個結(jié)點里再增加一個指向其直接前趨的指針域prior。這樣形成的鏈表中有兩條方向不同的鏈，故稱之為雙（向）鏈表。雙向鏈表的運(yùn)算類似單向鏈表的運(yùn)算，主要包括插入結(jié)點、刪除結(jié)點、查詢結(jié)點等運(yùn)算。2.3線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)2.3.4雙鏈表①雙鏈表的插入結(jié)點

雙向鏈表的插入結(jié)點的實現(xiàn)比較簡單，基本同單向鏈表，只不過在某個結(jié)點前或后插入新的結(jié)點時，只要找到該結(jié)點就可以了。另外在第一個結(jié)點之前插入時同單向鏈表插入結(jié)點，需要單獨(dú)處理。在插入過程中和單向鏈表的主要的不同點是修改的指針的個數(shù)不同。單向鏈表修改兩個指針；雙向鏈表需要修改四個指針。2.3線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)2.3.4雙鏈表①雙鏈表的插入結(jié)點插入結(jié)點應(yīng)分為以下幾個步驟：申請新結(jié)點，同時給新結(jié)點的數(shù)據(jù)域、兩個指針域賦值；將當(dāng)前結(jié)點的next域指向新結(jié)點；將當(dāng)前結(jié)點的直接后繼的前驅(qū)指針指向新結(jié)點。2.3線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)2.3.4雙鏈表②雙向鏈表的刪除結(jié)點

雙向鏈表的刪除結(jié)點的實現(xiàn)基本同單向鏈表，只不過在某個結(jié)點前或后刪除新的結(jié)點時，只要找到該結(jié)點就可以了，不需要保留前驅(qū)結(jié)點。另外在刪除第一個結(jié)點時同單向鏈表刪除頭結(jié)點，需要單獨(dú)處理。在刪除過程中和單向鏈表的主要的不同點是修改的指針的個數(shù)不同。單向鏈表修改一個指針；雙向鏈表需要修改兩個指針。2.3線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)2.3.4雙鏈表②雙向鏈表的刪除結(jié)點

刪除雙向鏈表的結(jié)點步驟有：修改當(dāng)前結(jié)點的next域修改當(dāng)前結(jié)點的后繼結(jié)點前驅(qū)結(jié)點指針③雙向鏈表的查詢結(jié)點

雙向鏈表的查詢結(jié)點的實現(xiàn)基本同單向鏈表，只要按照next的方向找到該結(jié)點就可以了，不需要保留前驅(qū)結(jié)點。如果找到，返回結(jié)點位置，否則返回null。查找結(jié)點的步驟是：從頭結(jié)點開始，直到找到該結(jié)點或是查找失敗。2.4鏈表應(yīng)用舉例例1．鏈?zhǔn)酱鎯ο碌囊辉囗検郊臃ɡ?．Josephus問題例3：使用迭代器編寫一個將鏈接線性表逆序打印的算法。2.5順序表和鏈表的比較線性表的存儲有兩種：順序存儲表和鏈?zhǔn)酱鎯Ρ怼＞唧w存儲方式可根據(jù)具體問題的要求和性質(zhì)來決定。根據(jù)線性表定長與不定長確定：順序存儲結(jié)構(gòu)一般要求數(shù)據(jù)存放的物理和邏輯地址連續(xù)；而鏈?zhǔn)酱鎯Y(jié)構(gòu)數(shù)據(jù)存放地址可連續(xù)可不連續(xù)，在線性表長度沒有確定的情況下，一般采用鏈?zhǔn)酱鎯Y(jié)構(gòu)比較好，反之應(yīng)以順序存儲為主。2.5順序表和鏈表的比較一般選擇存儲結(jié)構(gòu)時可以主要從以下兩個方面考慮：（1）基于空間的考慮順序表的存儲空間是靜態(tài)分配的，在程序執(zhí)行之前一般必須明確規(guī)定它的存儲規(guī)模。若線性表的長度n變化較大，則存儲規(guī)模難于預(yù)先確定（定義太大可能浪費(fèi)空間，定義太小又可能不夠用）。因此，當(dāng)線性表的長度變化較大，難以估計其存儲規(guī)模時，以采用動態(tài)鏈表作為存儲結(jié)構(gòu)為好。反之如果存儲規(guī)模比較小，并且線性表的長度一般固定時，可使用順序存儲。存儲密度=（結(jié)點數(shù)據(jù)本身所占的存儲量）/（結(jié)點結(jié)構(gòu)所占的存儲總量）一般地，存儲密度越大，存儲空間的利用率就越高。順序表的存儲密度為1，而鏈表的存儲密度小于1。由此可知，當(dāng)線性表的長度變化不大，易于事知確定其大小時，為了節(jié)約存儲空間，宜采用順序表作為存儲結(jié)構(gòu)。2.5順序表和鏈表的比較（2）基于時間的考慮順序表是由向量實現(xiàn)的，它是一種隨機(jī)存取結(jié)構(gòu)，對表中任一結(jié)點都可在O（1）時間內(nèi)直接地存取，而鏈表中的結(jié)點，需順序存取，應(yīng)從頭指針起順著鏈指針掃描結(jié)點才能獲得。因此，若對線性表的操作主要是進(jìn)行查找，很少做插入和刪除操作時，采用順序表的存儲結(jié)構(gòu)比較好。反之，如果在線性表中需要做較多的插入和刪除，如果采用順序存取，可能造成大量的數(shù)據(jù)移動，在時間上的開銷較大，而采用鏈?zhǔn)酱鎯r，只需要修改相應(yīng)地指針就可以了。2.5順序表和鏈表的比較如果比較偏重線性表的查找，通常很少對線性表進(jìn)行插入刪除操作時，因為順序存儲結(jié)構(gòu)為隨機(jī)存?。ù嫒∷俣瓤欤?，而鏈?zhǔn)酱鎯Y(jié)構(gòu)為順序存?。ㄏ鄬^慢），此時應(yīng)所以應(yīng)采用順序存儲結(jié)構(gòu)較好。第3章棧和隊列第3章棧和隊列堆棧和隊列是兩種特殊的線性表。堆棧的主要特點是只能在棧頂操作，也就是遵循先進(jìn)后出的運(yùn)算規(guī)則。隊列的主要的特點是只能在一端插入，另一端刪除的一種線性表，也就是遵循先進(jìn)先出的運(yùn)算規(guī)則。3.1棧3.1.1棧定義及基本概念棧（Stack）又稱堆棧，是限制在表的一端進(jìn)行插入和刪除運(yùn)算的線性表。通常稱能夠進(jìn)行插入、刪除運(yùn)算的這一端為棧頂（Top），另一端稱為棧底（Bottom）。當(dāng)表中沒有元素時稱為空棧。習(xí)慣上將每次刪除（也稱為退棧）操作又稱為彈出（POP）操作。刪除的元素總是當(dāng)前棧中“最新”的元素（棧頂元素）。每次插入（稱為進(jìn)棧）操作稱為壓入（PUSH）操作，壓入的元素總是當(dāng)前棧中“最新”的元素。3.1棧3.1.1棧定義及基本概念

在空棧中最先插入的元素總被放在棧的底部，只有所有元素被彈出之后它才能被刪除。當(dāng)棧滿時進(jìn)棧運(yùn)算稱為“上溢”；當(dāng)?？諘r退棧運(yùn)算稱為“下溢”。堆棧的存儲結(jié)構(gòu)有順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)兩種，在順序存儲結(jié)構(gòu)下，可以考慮堆棧的上溢，而在鏈?zhǔn)酱鎯Y(jié)構(gòu)下，不必考慮對雜貨內(nèi)的上溢現(xiàn)象，只需要考慮堆棧的下溢現(xiàn)象。3.1棧3.1.1棧定義及基本概念堆棧上溢是一種出錯狀態(tài)，應(yīng)該設(shè)法避免之；而下溢則可能是正常現(xiàn)象，通常下溢用來作為程序控制轉(zhuǎn)移的條件。堆棧的運(yùn)算規(guī)則是按后進(jìn)先出的原則進(jìn)行的（又稱為后進(jìn)先出），簡稱為LIFO（lastinfirstout）表。就線性表而言，實現(xiàn)棧的方法有很多，我們著重介紹順序棧（arrary-basedstack）和鏈?zhǔn)剑╨inkedstack）棧，它們類似于順序表和鏈?zhǔn)奖怼?.1棧3.1.1棧定義及基本概念棧的基本運(yùn)算一般有以下幾種：①InitStack（S）構(gòu)造一個空棧S。②StackEmpty（S）判?？?，若S為空棧返回TRUE，否則返回FALSE。③StackFull（S）判棧滿，若S為滿棧，則返回TRUE，否則返回FALSE。該運(yùn)算只適用于棧的順序存儲結(jié)構(gòu)。④Push（S，x）進(jìn)棧。若棧S不滿，則將元素x壓入S的棧頂。⑤Pop（S）退棧。若棧S非空，則將S的棧頂元素彈出，并返回該元素。⑥StackTop（S）取堆棧的棧頂元素，不修改棧頂指針。比較重要的運(yùn)算就是入棧和出棧兩種。3.1棧3.1.2順序棧

順序棧的實現(xiàn)從本質(zhì)上講，就是順序線性表實現(xiàn)的簡化。惟一重要的是需要確定應(yīng)該用數(shù)組的哪一端表示棧頂。一種選擇是把數(shù)組的第0個位置作為棧頂。根據(jù)線性表的函數(shù)，所有的插入(insert)和刪除(remove)操作都在第0個位置的元素上進(jìn)行。由于這時每次push(insert)或者pop(remove)操作都需要把當(dāng)前棧中的所有元素在數(shù)組中移動一個位置，因此效率不高。如果棧中有n個元素，則時間代價為O(n)。另一種選擇是當(dāng)棧中有n個元素時把位置n-1作棧頂。也就是說，當(dāng)向棧中壓人元素時，把它們添加到線性表的表尾，成員函數(shù)pop也是刪除表尾元素。在這種情況下，每次push或者pop操作的時間代價僅為O(1)。3.1棧3.1.2順序棧堆棧的運(yùn)算主要考慮堆棧的入棧和出棧算法。其原因是在堆棧的基本運(yùn)算中有六種：判斷堆?？?、堆棧初始化、判斷堆棧滿（僅限于順序存儲的情況下），入棧元素、出棧元素、取棧頂元素等，而入棧時需要考慮的操作步驟是：堆棧初始化，然后判斷堆棧是否為滿，如果不滿，則可以插入元素（入棧）；出棧時，需要考慮的步驟是：判斷堆棧是否為空，如果不空，刪除元素（出棧），出棧之前，保存棧頂元素。也就是說，堆棧的入出棧運(yùn)算包含了其他的六種基本運(yùn)算，取棧頂元素的運(yùn)算，只是不用修改棧頂?shù)闹羔樁选?.1棧3.1.3鏈?zhǔn)綏?/p>

堆棧的鏈?zhǔn)酱鎯?，稱為鏈棧（單向鏈表存儲堆棧）。鏈?zhǔn)綏５幕具\(yùn)算同順序棧，定義也同線性表的鏈表定義，它是對鏈表實現(xiàn)的簡單化（因為它只是對鏈表的頭部操作）。它的元素只能在表頭進(jìn)行插入和刪除。在鏈?zhǔn)酱鎯Y(jié)構(gòu)中，不需要給出表頭結(jié)點，因為其中惟一的已知條件是棧頂指針top，它是指向鏈?zhǔn)綏５牡谝粋€結(jié)點（相當(dāng)于頭結(jié)點）。堆棧的各種運(yùn)算比鏈?zhǔn)酱鎯Φ钠胀ň€性表運(yùn)算實現(xiàn)時要方便得多，主要原因是堆棧的各種運(yùn)算只能在堆棧的一端操作，堆棧是特殊的線性表，我們只要考慮對線性表的一端操作的情況，并且只能在一端插入刪除（棧頂）；而線性表除此之外（不限定一端插入刪除），還需要考慮另外一端結(jié)點以及中間的結(jié)點的插入、刪除、查詢等操作，理解時，我們可以把堆棧的入出堆棧運(yùn)算當(dāng)作線性表的一端進(jìn)行插入刪除的特例即可。注意：堆棧的運(yùn)算一定遵循“先進(jìn)后出”的運(yùn)算規(guī)則。3.1棧3.1.4順序棧和鏈?zhǔn)綏５谋容^

實現(xiàn)鏈?zhǔn)綏：晚樞驐５牟僮鳎际切枰?shù)時間，即時間復(fù)雜度為O（1）。主要兩者從空間和時間兩個方面考慮：初始時，順序堆棧必須說明一個固定的長度，當(dāng)堆棧不夠滿時，造成一些空間的浪費(fèi)，而鏈?zhǔn)蕉褩５拈L度可變則是長度不需要預(yù)先設(shè)定，相對比較節(jié)省空間，但是在每個結(jié)點中，設(shè)置了一個指針域，從而產(chǎn)生了結(jié)構(gòu)開銷。3.1棧3.1.4順序棧和鏈?zhǔn)綏５谋容^當(dāng)需要多個堆棧共享時，順序存儲中可以充分利用順序棧的單向延伸性?？梢允褂靡粋€數(shù)組存儲兩個堆棧，使每個堆棧從各自的端點向中間延伸，這樣浪費(fèi)的空間就會減少。但這種情況只有當(dāng)兩個堆棧的空間需求有相反的需求時，這種方法才有效。也就是說，最好一個堆棧增長，一個堆?？s短。反之，如果兩個堆棧同時增長，則可能比較容易造成堆棧的溢出。如果多個順序堆棧共享空間，則可能需要大量的數(shù)據(jù)移動，造成時間的開銷增大。而鏈?zhǔn)蕉褩Ｓ捎诖鎯Φ牟贿B續(xù)性，一般不存在堆棧滿的問題，所以一般不需要棧的共享。

3.1棧3.1.5棧的應(yīng)用舉例

（一）表達(dá)式的轉(zhuǎn)換

（二）遞歸

（三）漢內(nèi)塔（hanoi）問題

（四）互遞歸

3.2隊列3.2.1隊列定義及基本概念

1、隊列定義隊的操作是在兩端進(jìn)行，其中一端只能進(jìn)行插入，該端稱為隊列的隊尾，而另一端只能進(jìn)行刪除，該端稱為隊列的隊首。一般情況下，入隊操作又稱為隊列的插入，出隊操作又稱為隊列的刪除。隊列的運(yùn)算規(guī)則是FIFO（FirstInFirstOut），或者叫做先進(jìn)先出規(guī)則。隊列的存儲具有順序和鏈?zhǔn)酱鎯煞N。隊列在順序存儲時，經(jīng)常出現(xiàn)“假溢出”現(xiàn)象，解決“假溢出”現(xiàn)象的方法有很多種，但通常采用循環(huán)隊列方式存儲。隊列的主要作用是：用于某種先后順序處理的問題中，如：操作系統(tǒng)的作業(yè)調(diào)度、打印任務(wù)的調(diào)度等。3.2隊列3.2.1隊列定義及基本概念2、隊列的基本運(yùn)算隊列的基本運(yùn)算通常和堆棧的基本運(yùn)算類似，有以下6種：①置空隊；//構(gòu)造一個空隊列。②判對空；//隊空返回真，否則返回假。③判對滿；//隊滿返回真，否則返回假，僅限于順序存儲結(jié)構(gòu)。④入隊；//隊列非滿時，從隊尾插入元素。⑤出隊；//隊列非空時，從隊首刪除元素。⑥取隊首元素；//返回隊首元素，不修改隊首指針。

3.2隊列3.2.2順序隊列

隊列的順序存儲結(jié)構(gòu)稱為順序隊列，順序隊列實際上是運(yùn)算受限的順序表，和順序表一樣，順序隊列也必須用一個向量空間來存放當(dāng)前隊列中的元素。由于隊列的隊頭和隊尾的位置是變化的，因而要設(shè)置兩個指針front和和rear分別指示隊頭元素和隊尾元素在向量空間中的位置，它們的初值在隊列初始化時可以置為0。入隊時將新元素插入rear所指的位置，然后將rear加1。出隊時，刪去front所指的元素，然后將front加1并返回被刪元素。由此可見，當(dāng)頭尾指針相等時隊列為空。在非空隊列里，頭指針始終指向隊頭元素，而尾指針始終指向隊尾元素的下一個位置。3.2隊列3.2.2順序隊列

隊列同堆棧一樣也有上溢和下溢現(xiàn)象。此外隊列中還存在“假溢出”現(xiàn)象。所謂“假溢出”是指在入隊和出隊操作中，頭尾指針不斷增加而不減小或只減小而不增加，致使被刪除元素的空間無法重新利用，最后造成隊列中有空閑空間，但是不能夠插入元素，也不能夠刪除元素的現(xiàn)象。因此，盡管隊列中實際的元素個數(shù)遠(yuǎn)遠(yuǎn)小于向量空間的規(guī)模，但也可能由于尾指針已超越向量空間的上界而不能進(jìn)行入隊或出隊操作。該現(xiàn)象稱為假上溢。解決假上溢現(xiàn)象的方法有很多種，如固定隊首指針，一旦刪除元素，需要移動所有元素后，修改隊尾指針，這樣又可以插入元素了，只有在不能插入元素時，隊列才滿，否則可以一直插入元素，這種方法雖然能夠解決“假溢出”，但需要造成大量的數(shù)據(jù)元素的移動；現(xiàn)在解決“假溢出”比較好的解決方案是使用循環(huán)向量，存儲在循環(huán)向量中的隊列稱為循環(huán)隊列（circularQuene）。3.2隊列3.2.2順序隊列

假設(shè)向量的空間是m，只要在入出隊列時，將隊首和隊尾的指針對m做求模運(yùn)算即可實現(xiàn)隊首和隊為指針的循環(huán)，即隊首和隊尾指針的取值范圍是0到m-1之間。入隊時：rear=（rear+1）%maxsize出隊時：front=（front+1）%mixsize但是入隊和出隊時front和rear的取值不能夠確定隊列的空和滿。因為入隊時，rear指針不斷增加一個，當(dāng)rear指針“追上”front指針時，此時隊列已經(jīng)滿了，此時滿的條件是rear=front；反之，當(dāng)出隊時，front指針不斷增加一個，當(dāng)front指針“追上”rear指針時，此時隊列已經(jīng)空了，此時隊列空的條件是rear=front。由此可見隊空和隊滿的條件是相同的，都是front=rear。3.2隊列3.2.2順序隊列

區(qū)分隊空和隊滿的方法有多種。方法一：我們可以設(shè)置浪費(fèi)一個空間單元，也就是假定rear指向的是剛剛插入元素的位置，front指向剛剛刪除元素的位置。也就是說在入隊時，先不修改rear的值，而是先判斷（rear+1）%maxsize=front，如果成立，表示隊列已滿（此時實際還有front指向的位置空閑），出隊時，只要判斷front=rear，如果成立表示隊已空，否則只要front=（front+1）%maxsize直接刪除元素即可。此種方法存儲的數(shù)據(jù)元素個數(shù)是maxsize-1個，是利用浪費(fèi)一個空間來換取隊空與滿的條件。方法二：設(shè)定一個變量來表示隊列中的元素個數(shù)，利用該變量的值與隊列的最大容量比較，如果該變量的值與最大容量相等，則表示隊滿，如果該變量的只為0，此時表示隊列為空。此方法與第一種方法的不同之處在于，每次入隊、出隊一個元素時，需要修改隊列中的數(shù)據(jù)元素的個數(shù)。3.2隊列3.2.3鏈?zhǔn)疥犃?/p>

定義鏈隊列的存儲結(jié)構(gòu)基本和線性表的定義相同，不過需要在結(jié)構(gòu)中指明的是隊首和隊尾的數(shù)據(jù)類型不再是整型而是指針類型。隊列的各種運(yùn)算比鏈?zhǔn)酱鎯Φ钠胀ň€性表運(yùn)算實現(xiàn)時要方便得多，主要原因是隊列的各種運(yùn)算只能在隊列的兩端操作，隊列是特殊的線性表，我們只要考慮對線性表的兩端操作的情況，并且只能一端插入（隊首），另一端刪除（隊尾）；而線性表除此之外（不限定一端插入、一端刪除），還需要考慮中間的結(jié)點的插入、刪除、查詢等操作，理解時，我們可以把隊列的入出隊運(yùn)算當(dāng)作線性表兩端進(jìn)行插入刪除的特例即可。3.2隊列3.2.3鏈?zhǔn)疥犃?/p>

主要考慮隊列的入隊和出隊算法。其原因是在隊列的基本運(yùn)算中有六種：判斷隊空、隊列初始化、判斷隊列滿（僅限于順序存儲的情況下），入隊元素、出隊元素、取隊首元素等，而入隊時需要操作的步驟是：初始化，然后判斷隊列是否為滿，如果不滿，則可以插入元素（入隊）；出隊時，需要考慮的操作步驟是：判斷隊列是否為空，如果不空，刪除元素（出隊），出隊之前，保存隊首元素。也就是說，隊列的入出隊運(yùn)算包含了其他的六種基本運(yùn)算，取隊首元素的運(yùn)算，只是不用修改隊首的指針而已。3.2隊列3.2.3鏈?zhǔn)疥犃?/p>

以單向循環(huán)隊列為例，只要保留末尾結(jié)點指針（假設(shè)是隊尾指針），主要原因是如果保存隊首和隊尾指針，結(jié)構(gòu)開銷較大，原因是循環(huán)隊列中，已知任意結(jié)點，可以找到所有結(jié)點，所以只要保留一個結(jié)點就可以了。如果已知結(jié)點的指針是頭結(jié)點指針，此時入隊出隊運(yùn)算的時間復(fù)雜度為O（n）（主要時間花費(fèi)在查詢結(jié)點上）；而如果已知結(jié)點的指針是末尾結(jié)點指針，此時不需要查詢結(jié)點，直接進(jìn)行入隊和出隊運(yùn)算，時間復(fù)雜度O（1），各種運(yùn)算實現(xiàn)也比較方便。在出隊算法中，一般只需修改隊頭指針。但當(dāng)原隊中只有一個結(jié)點時，該結(jié)點既是隊頭也是隊尾，故刪去此結(jié)點時亦需修改尾指針，且刪去此結(jié)點后隊列變空。3.2隊列3.2.4隊列的應(yīng)用

（一）合并兩個隊列假設(shè)有兩個隊列，要求將兩個隊列合并到一起，合并時交替使用兩個隊列中的元素，并把剩余的隊列中的元素添加在最后，將產(chǎn)生的新隊列返回。（二）模擬客戶服務(wù)系統(tǒng)

第4章數(shù)組和廣義表4.1多維數(shù)組4.1.1數(shù)組定義

數(shù)組是數(shù)據(jù)結(jié)構(gòu)的基本結(jié)構(gòu)形式，它是一種順序式的結(jié)構(gòu)，數(shù)組是存儲同一類型數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)，使用數(shù)組時需要定義數(shù)組的大小和存儲數(shù)據(jù)的數(shù)據(jù)類型，數(shù)組分為一維數(shù)組和多維數(shù)組。數(shù)組的維數(shù)是由數(shù)組的下標(biāo)的個數(shù)確定的，一個下標(biāo)稱為一維數(shù)組，一個下標(biāo)以上的數(shù)組稱為多維數(shù)組。從這個意義上講，確定了對于數(shù)組的一個下標(biāo)總有一個相應(yīng)的數(shù)值與之對應(yīng)的關(guān)系；或者說數(shù)組是有限個同類型數(shù)據(jù)元素組成的序列。數(shù)組的基本操作包括：initarray（&A）；//初始化數(shù)組destroyarray（&A）；//銷毀數(shù)組assign（&A，e）；//數(shù)組賦值value（A，&e）；//取數(shù)組的某個元素copyarray（M，&T）；//復(fù)制一個數(shù)組printarray（M）；//打印數(shù)組的元素4.1多維數(shù)組4.1.1數(shù)組定義一維數(shù)組一維數(shù)組是指下標(biāo)的個數(shù)只有一個的數(shù)組，有時稱為向量，是最基本的數(shù)據(jù)類型，在java中需要事先聲名，程序才能夠在編譯過程中預(yù)留內(nèi)存空間。聲明的格式一般是：<數(shù)據(jù)類型><變量名稱>[]=new<數(shù)據(jù)類型>[<數(shù)組大小>]；

4.1多維數(shù)組4.1.1數(shù)組定義多維數(shù)組多維數(shù)組是指下標(biāo)的個數(shù)有兩個以上，我們比較常用的是二維數(shù)組（因為三維以上的數(shù)組存儲可以簡化為二維數(shù)組的存儲）。下面以二維數(shù)組為例說明多維數(shù)組。二維數(shù)組的聲明同一維數(shù)組。格式為：<數(shù)據(jù)類型><數(shù)組名稱>[][]=new<數(shù)據(jù)類型>[size1][size2];4.1多維數(shù)組4.1.2數(shù)組的存儲一維數(shù)組的存儲一維數(shù)組的數(shù)據(jù)存儲按照順序存儲，邏輯地址和物理地址都是連續(xù)的。如果已知第一個數(shù)據(jù)元素的地址loc(a1)，則第i個元素的地址loc(ai)為：loc(ai)=loc(a1)+（i-1）*c假設(shè)數(shù)組的下標(biāo)從1開始，只要求出第i個元素之前存放了多少個數(shù)據(jù)元素即可（實際上有i-1個元素），每個元素占有c個存儲單元，再乘以c，就是第i個元素的起始地址。如果下標(biāo)從0開始，則第i個元素之前就有i個元素，此時上面的公式就變?yōu)椋簂oc(ai)=loc(a1)+i*c由此可見，求數(shù)組中數(shù)據(jù)元素的地址，已知條件必須是知道第一個元素的地址，然后主要是找出該元素之前已經(jīng)存儲了多少個數(shù)據(jù)元素。在一維數(shù)組中，只要知道任何一個元素的地址即可求出其它元素的地址，但在多維數(shù)組中，已知條件必須是第一個數(shù)據(jù)元素地址。4.1多維數(shù)組4.1.2數(shù)組的存儲多維數(shù)組以二維數(shù)組的順序存儲為例說明，二維數(shù)組在順序存儲時一般有兩種：行優(yōu)先順序：存儲時先按行從小到大的順序存儲，在每一行中按列號從小到大存儲。列優(yōu)先順序：存儲時先按列從小到大的順序存儲，在每一列中按行號從小到大存儲。以上的兩種存儲順序中，第一個被存放的元素總是第一行第一列的數(shù)據(jù)元素，所以該元素的地址是我們的已知條件。同樣在二維數(shù)組中比較典型的是計算數(shù)據(jù)的存儲位置。4.1多維數(shù)組4.1.2數(shù)組的存儲多維數(shù)組假設(shè)二維數(shù)組是m*n的二維數(shù)組（共有m行，每行有n列）。第一個數(shù)據(jù)元素的地址是loc(a11)，則第i行第j列的數(shù)據(jù)元素的地址的計算公式應(yīng)為（按照行優(yōu)先順序存儲）：loc(aij)=loc(a11)+[（i-1）*n+j-1]*c假設(shè)下標(biāo)從1開始，我們需要計算出i行前面已經(jīng)存儲了i-1行元素，每行有n個元素，共有（i-1）*n個數(shù)據(jù)元素，在第i行元素中，j列之前有j-1個數(shù)據(jù)元素，共有（i-1）*n+j-1個元素，每個元素占有c個存儲單元，只要乘以c就可以了。其中l(wèi)oc(aij)表示第i行第j列數(shù)據(jù)元素的內(nèi)存的起始位置，loc(a11)表示第一個數(shù)據(jù)元素的內(nèi)存位置，c表示每個數(shù)據(jù)元素所占有的內(nèi)存空間的大小，如果下標(biāo)從0開始，只要不用減1即可。4.1多維數(shù)組4.1.2數(shù)組的存儲多維數(shù)組如果按列優(yōu)先順序存儲，則地址的計算為：loc(aij)=loc(a11)+[（j-1）*m+i-1]*c假設(shè)下標(biāo)從1開始，其中l(wèi)oc(aij)表示第i行第j列的數(shù)據(jù)元素的內(nèi)存起始位置，loc(a11)表示第一個數(shù)據(jù)元素的內(nèi)存位置，c表示每個數(shù)據(jù)元素所占有的內(nèi)存空間的大?。恢饕€是計算第i行j列元素之前有多少個數(shù)據(jù)元素。如果下標(biāo)從0開始，只要不用減1即可。按此公式可以推廣到多維數(shù)組的數(shù)據(jù)元素的地址計算（假設(shè)按照行優(yōu)先順序存儲）：m行n列縱標(biāo)為k的三維數(shù)組，假設(shè)第一個元素的地址是loc(a111)，如果按行優(yōu)先順序存儲，i行j列縱標(biāo)為p的數(shù)據(jù)元素的地址為（可以將它分解為二維數(shù)組）：loc(aijp)=loc(a111)+[(i-1)*n*k+(j-1)*k+p-1]*c;如果下標(biāo)從0開始，只要不用減1即可。讀者可以從以上的地址公式中可以找出一定的地址計算規(guī)律：多維數(shù)組中按行優(yōu)先計算公式用一個下標(biāo)乘以后面的最大值。4.1多維數(shù)組4.1.3顯示二維數(shù)組的內(nèi)容一般情況下，只要定義了數(shù)組的存儲順序，數(shù)組的存儲順序就不會改變了，所以對數(shù)組的各種操作后，應(yīng)按照數(shù)組的已定義的存儲順序存儲；也就是說，如果是按行優(yōu)先順序存儲，在對數(shù)組操作后，即使改變了存儲順序，應(yīng)加以改變?nèi)匀话凑招袃?yōu)先順序存儲。

4.2矩陣的壓縮存儲4.2.1矩陣的壓縮存儲所謂矩陣的壓縮存儲，也就是在存儲數(shù)組時，盡量減少存儲空間，但是數(shù)組中的每個元素必須存儲，所以在矩陣存儲中，如果有規(guī)律可尋，只要存儲其中一部分，而另一部分的存儲地址可以通過相應(yīng)的算法將它計算出來，從而占有比較少的存儲空間達(dá)到存儲整個矩陣的目的，稱為矩陣的壓縮存儲。矩陣的壓縮存儲僅是針對特殊矩陣的；而對于沒有規(guī)律可循的二維數(shù)組則不能夠使用壓縮存儲。二維數(shù)組（矩陣）的壓縮存儲一般有三種，它們分別是對稱矩陣、稀疏矩陣和三角矩陣。三種矩陣中以稀疏矩陣比較常見。

4.2矩陣的壓縮存儲4.2.1矩陣的壓縮存儲特殊矩陣若n階矩陣A中的元素滿足以下條件：aij=ajii≥1，j≥1則稱為n階對稱矩陣。對于對稱矩陣，如果不采用壓縮存儲，占有的存儲單元有n2個，因為是對稱矩陣，所以只要存儲對角的數(shù)據(jù)元素和一半的數(shù)據(jù)元素即可，占有的存儲單元有n（n-1）/2個存儲單元中。如果我們以行序為主序存儲其下三角（包括對角線）的元素，其上三角的元素可以推算出來。4.2矩陣的壓縮存儲4.2.1矩陣的壓縮存儲特殊矩陣如果用一維數(shù)組存儲一個對稱矩陣，只要將對稱矩陣存儲在一個最大下標(biāo)為n（n-1）/2的一維數(shù)組S中即可。此時按照行優(yōu)先順序存儲，數(shù)據(jù)元素aij與數(shù)組S的下標(biāo)k的對應(yīng)關(guān)系為：

i(i-1)/2+j-1當(dāng)i≥j時

k=j(j-1)/2+i-1當(dāng)i＜j時4.2矩陣的壓縮存儲4.2.1矩陣的壓縮存儲特殊矩陣對于任意給定的一組下標(biāo)（i，j），均可在S中找到元素aij，反之，對所有元素都能夠確定在S中位置，當(dāng)i＜j時，根據(jù)對稱矩陣的性質(zhì)推算即可。由此可以看出對稱矩陣的存儲可以使用一維數(shù)組S存儲，占用的空間不再是n2，而是n（n-1）/2空間減少了接近一半，實現(xiàn)了二維數(shù)組的壓縮存儲。所謂對角矩陣是指，矩陣的所有非零元素都集中在以主對角線為中心的帶狀區(qū)域中，即除了主對角線上和直接在主對角線上、下方若干條對角線上的元素之外，其余元素皆為零。

4.2矩陣的壓縮存儲4.2.1矩陣的壓縮存儲特殊矩陣也可以按照某個原則（或者以行序為主序，或者以列序為主序，或者按對角線的順序）將對角矩陣B的所有非零元素壓縮存儲到一個一維數(shù)組LTB[1…3n-2]中。這里不妨仍然以行序為主序的原則對B進(jìn)行壓縮存儲，當(dāng)B中任一非零元素bij與LTB[k]之間存在著如下一一對應(yīng)關(guān)系：k=2*i+j-2時，則有bij=LTB[k]。稱LTB[1…3n-2]為對角矩陣B的壓縮存儲。上面討論的幾種特殊矩陣中，非零元素的分布都具有明顯的規(guī)律，因而都可以被壓縮存儲到一個一維數(shù)組中，并能夠確定這些矩陣的每個非零元素在一維數(shù)組中的存儲位置。但是，對于那些非零元素在矩陣中的分布沒有規(guī)律的特殊矩陣(如稀疏矩陣)，則需要尋求其他方法來解決壓縮存儲問題。

4.2矩陣的壓縮存儲4.2.1矩陣的壓縮存儲稀疏矩陣對稀疏矩陣很難下一個確切的定義，它只是一個憑人們的直覺來理解的概念。一般認(rèn)為，一個較大的矩陣中，零元素的個數(shù)相對于整個矩陣元素的總個數(shù)所占比例較大時，該矩陣就是一個稀疏矩陣。例如，有一個6×6階的矩陣A，其36個元素中只有8個非零元素，那么，可以稱矩陣A為稀疏矩陣。稀疏矩陣一般是指矩陣中的大部分元素為零，僅有少量元素非零的矩陣稱為稀疏矩陣；或者說矩陣A（m×n）中有S個非零元素，如果S遠(yuǎn)遠(yuǎn)小于矩陣的元素總數(shù)，稱A為稀疏矩陣。稀疏矩陣的存儲一般只要保存非零元素即可，對于零元素可以不與保存，這樣可以實現(xiàn)稀疏矩陣的壓縮存儲。

4.2矩陣的壓縮存儲4.2.1矩陣的壓縮存儲稀疏矩陣稀疏矩陣的壓縮存儲采用三元組的方法實現(xiàn)。其存儲規(guī)則如下：每一個非零元素占有一行，每行中包含非零元素所在的行號、列號、非零元素的數(shù)值。為完整描述稀疏矩陣，一般在第一行描述矩陣的行數(shù)、列數(shù)和非零元素的個數(shù)。其邏輯描述為：（rowcolvalue）其中row表示行號，col表示列號，value表示非零元素的值。如果每個非零元素按照此種方法存儲，雖然能夠完整地描述非零元素，但如果矩陣中有整行（或整列）中沒有非零元素，此時可能不能夠還原成原來的矩陣，所以為了完整地描述稀疏矩陣，在以上描述的情況下，如果增加一行的內(nèi)容，該行包括矩陣的總的行數(shù)、矩陣的總的列數(shù)，矩陣中非零元素的個數(shù)，就可以還原為原來的矩陣描述了。

4.2矩陣的壓縮存儲4.2.1矩陣的壓縮存儲稀疏矩陣歸納起來，若一個稀疏矩陣有t個非零元素，則需要用t+1行的三元組來表示稀疏矩陣。到底矩陣何時使用三元組存儲呢？一般對m×n的矩陣來說，只要滿足（t+1）*3≤m*n這個條件，使用三元組存儲可以節(jié)省空間，否則更加浪費(fèi)空間，也就沒有必要使用三元組存儲，所以稀疏矩陣中的非零元素的個數(shù)t是能否使用三元組存儲的關(guān)鍵。

4.2矩陣的壓縮存儲4.2.2稀疏矩陣轉(zhuǎn)換為三元組存儲

首先應(yīng)該將稀疏矩陣轉(zhuǎn)換為三元組存儲，然后才利用三元組的存儲，實現(xiàn)對矩陣的各種運(yùn)算。對于矩陣的運(yùn)算一般有矩陣的轉(zhuǎn)置，在轉(zhuǎn)置時值得注意的是：在矩陣的存儲規(guī)則已經(jīng)確定的情況下（如按行優(yōu)先存儲），實現(xiàn)矩陣的運(yùn)算（如轉(zhuǎn)置）時，應(yīng)仍然保留原來的存儲規(guī)則。改進(jìn)的轉(zhuǎn)置方法可以利用對原始的三元組的元素的掃描，直接確定該元素在轉(zhuǎn)置后的三元組中的行，這樣可以將原始三元組中的元素直接放在轉(zhuǎn)置后的三元組中即可。這種方法需要增加兩個一維數(shù)組的結(jié)構(gòu)開銷，稱為快速轉(zhuǎn)置。4.3廣義表4.3.1廣義表的定義廣義表是線性表的擴(kuò)展，具體定義為n（n≥0）個元素的有限集合。其中元素有以下兩種類型：1）一個原子元素（指不可再分的元素）；2）一個可以再分的元素（或稱為一個子表）。如果所有元素都是原子元素，則稱為線性表，如果含有子表則是廣義表。4.3廣義表4.3.1廣義表的定義廣義表的基本操作：initGlist(&L)//創(chuàng)建空的廣義表creatGlist(&L,S)//由S創(chuàng)建廣義表LdestroyGlist(&L)//銷毀廣義表LGlistlength（L）//求廣義表的長度Glistdepth（L）//求廣義表的深度Gethead(L)//求廣義表L的頭Gettail(L)//求廣義表的表尾Insertfirst_Glist(&L,e)//插入元素e作為廣義表L的第一個元素Deletefirst_Glist(&L,&e)//刪除廣義表L的第一個元素，并用e返回其值4.3廣義表4.3.1廣義表的定義廣義表一般記作：LS=（a1，a2，…，an）其中LS是廣義表的名稱，n是廣義表的長度。常見的廣義表為：A=（）B=（（））C=（a,b）D=（A，B，C）E=（a,E）廣義表中含有元素的個數(shù)稱為廣義表的長度，廣義表中含有的括號對數(shù)稱為廣義表的深度。4.3廣義表4.3.1廣義表的定義三個重要結(jié)論：列表的元素可以是子表，而子表的元素還可以是子表…。由此，列表是一個多層次的結(jié)構(gòu)，可以用圖形象地表示。例如圖4-1表示的是列表D。圖中以圓圈表示列表，以方塊表示原子元素。列表可為其它列表所共享。例如在上述例子中，列表A、B和C為D的子表，則在D中可以不必列出子表的值，而是通過子表的名稱來引用。列表可以是一個遞歸的表，即列表也可以是其本身的一個子表。例如列表E就是一個遞歸的表。4.3廣義表4.3.2廣義表的存儲廣義表的存儲方法有很多種，一般采用鏈表存儲。采用鏈表存儲時的結(jié)點存儲的邏輯結(jié)構(gòu)（如圖所示）一般是：其中flag表示標(biāo)志位，當(dāng)flag為0時，該結(jié)點表示原子元素，當(dāng)flag為1時，該結(jié)點表示子表；當(dāng)flag為0時，info表示原子元素的值，當(dāng)flag為1時，info表示指針，指向該子表的第一個結(jié)點；link表示指針，指向廣義表的下一個元素。Flaginfolink第5章樹

5.1樹的概念5.2二叉樹的定義5.3二叉樹的性質(zhì)5.4二叉樹的存儲結(jié)構(gòu)5.5二叉樹的遍歷5.6線索二叉樹5.7樹和二叉樹的轉(zhuǎn)換及樹的存儲結(jié)構(gòu)5.8哈夫曼樹及其應(yīng)用5.1樹的概念5.1.1樹的定義

樹是一種數(shù)據(jù)結(jié)構(gòu)，表示為TREE=（D，R）；其中：D是具有相同特性的數(shù)據(jù)元素的集合；R是元素集合D上的關(guān)系集合，如果D中只含有一個數(shù)據(jù)元素，則R為空集?；蛘哂眠f歸定義為：樹是N（N>0）個結(jié)點的有限集合，其唯一關(guān)系具有下列屬性：集合中存在唯一的一個結(jié)點，稱為樹根，該結(jié)點沒有前驅(qū)；除根結(jié)點外，其余結(jié)點分為M（M≥0）個互不相交的集合，其中每一個集合都是一棵樹，并稱其為根的子樹。

5.1樹的概念5.1.2基本術(shù)語一個結(jié)點的子樹個數(shù)稱為該結(jié)點的度（degree）一棵樹中結(jié)點度的最大值稱為該樹的度度為零的結(jié)點稱為葉子（leaf）或者終端結(jié)點度不為零的結(jié)點稱為分支結(jié)點或者非終端結(jié)點除根結(jié)點之外的分支結(jié)點統(tǒng)稱為內(nèi)部結(jié)點樹中結(jié)點的后繼結(jié)點稱為兒子（child）或者兒子結(jié)點，簡稱兒子

結(jié)點的前驅(qū)結(jié)點稱為兒子的雙親（parents）或者父親結(jié)點，簡稱父親同一個父親的兒子互稱為兄弟（sibling）

5.1樹的概念若樹中存在一個結(jié)點序列k1k2k3…kj，使得ki是ki+1的父親（1≤i＜j），則稱該結(jié)點序列是從k1到kj的一條路徑（path）或者道路路徑的長度等于j-1，它是該路徑所經(jīng)過的邊（即連接兩個結(jié)點的線段）的數(shù)目若樹中結(jié)點k到ks存在一條路徑，則稱k是ks的祖先（Ancestor），ks是k的子孫（Descendant）結(jié)點的層數(shù)（level）是從根開始算起的。設(shè)根結(jié)點的層數(shù)為1，其余結(jié)點的層數(shù)等于其父親結(jié)點的層數(shù)加1樹中結(jié)點的最大層數(shù)稱為樹的高度（Height）或者深度（Depth）

5.1樹的概念若把樹中每個結(jié)點的各子樹看成從左到右有次序的（即不能互換），則稱該樹為有序樹（OrderedTree）；否則稱為無序樹（UnorderedTree）森林（Forest）是m（m≥0）棵互不相交樹的集合樹形結(jié)構(gòu)是非線性結(jié)構(gòu)

祖先與子孫的關(guān)系則是對父子關(guān)系的延伸，其定義了樹中結(jié)點的縱向次序

如果規(guī)定k1和k2是兄弟，且k1在k2的左邊，則k1的任一子孫都在k2的任一子孫的左邊，則定義了樹中結(jié)點的橫向次序

5.2二叉樹的定義二叉樹是由n（n≥0）結(jié)點的有限集合，此集合或者為空，或者由一個根結(jié)點加上兩棵分別稱為左、右子樹的，互不相交的二叉樹組成二叉樹可以為空集，因此根可以有空的左子樹或者右子樹，亦或者左、右子樹皆為空從二叉樹定義中可以看出，二叉樹結(jié)構(gòu)與一般樹結(jié)構(gòu)區(qū)別如下：（1）二叉樹可以為空樹，即不包含任何結(jié)點；一般樹至少應(yīng)有一個結(jié)點。（2）二叉樹區(qū)別于度數(shù)為2的有序樹，在二叉樹中允許某些結(jié)點只有右子樹而沒有左子樹；而有序樹中，一個結(jié)點如果沒有第一子樹就不可能有第二子樹的存在。

5.3二叉樹的性質(zhì)5.3.1二叉樹性質(zhì)性質(zhì)1二叉樹第i（i≥1）層上的結(jié)點數(shù)最多為2i-1

性質(zhì)2高度為k的二叉樹最多有2k-1個結(jié)點

性質(zhì)3對任何二叉樹T，設(shè)n0、n1、n2分別表示度數(shù)為0、1、2的結(jié)點個數(shù)，則n0=n2+1

5.3二叉樹的性質(zhì)性質(zhì)4具有n個結(jié)點的完全二叉樹（包括滿二叉樹）的高度為（或者）性質(zhì)5滿二叉樹原理

非空滿二叉樹的葉結(jié)點數(shù)等于其分支結(jié)點數(shù)加1性質(zhì)6一棵非空二叉樹空子樹的數(shù)目等于其結(jié)點數(shù)目加1

5.3二叉樹的性質(zhì)5.3.2二叉樹的抽象數(shù)據(jù)類型

下列給出一個二叉樹結(jié)點的JAVA接口，稱之為BinNode。BinNode類中存儲了指向Object類的引用。創(chuàng)建二叉樹時，可以根據(jù)需要而采用實際的數(shù)據(jù)類型。成員函數(shù)包括返回元素的值，返回左、右結(jié)點指針，設(shè)置元素的值，以了標(biāo)志該結(jié)點是否為葉結(jié)點。interfaceBinNode{//二叉樹結(jié)點的抽象數(shù)據(jù)類型//返回并設(shè)置元素值publicObjectelement();publicObjectsetElement(Objectv);

5.3二叉樹的性質(zhì)//返回并設(shè)置左孩子publicBinnodeleft();publicBinnodesetLeft(BinNodep);

//返回并設(shè)置右孩子publicBinnoderight();publicBinnodesetRight(BinNodep);

//判斷是否為葉結(jié)點publicbooleanisLeaf();}//interfaceBinNode5.4二叉樹的存儲結(jié)構(gòu)5.4.1二叉樹順序存儲結(jié)構(gòu)

二叉樹的順序存儲結(jié)構(gòu)是把二叉樹的所有結(jié)點按照一定的次序順序存儲到一組包含n個存儲單元的空間中

二叉樹順序存儲的原則是：不管給定的二叉樹是不是完全二叉樹，都看作完全二叉樹，即按完全二叉樹的層次次序（從上到下，從左到右）把各結(jié)點依次存入數(shù)組中

5.4二叉樹的存儲結(jié)構(gòu)在順序存儲結(jié)構(gòu)中，由某結(jié)點的存儲單元地址可以推出其父親、左兒子、右兒子及兄弟的地址，假設(shè)給定結(jié)點的地址為I，則：（1）若I＝1，則該結(jié)點是為根結(jié)點，無父親。（2）若I≠1，則該結(jié)點的父親結(jié)點地址為I／2的整數(shù)部分。（3）若2×I≤n，則該結(jié)點的左兒子結(jié)點地址為2×I，否則該結(jié)點無左兒子。（4）若2×I+1≤n，則該結(jié)點的右兒子結(jié)點地址為2×I+1，否則該結(jié)點無右兒子。（5）若I為奇數(shù)（不為1），則該結(jié)點的左兄弟為I-1。（6）若I為偶數(shù)（不為n），則該結(jié)點的右兄弟為I+1。5.4二叉樹的存儲結(jié)構(gòu)5.4.2二叉樹的鏈接存儲結(jié)構(gòu)

二叉樹的鏈接存儲中每個結(jié)點由數(shù)據(jù)域和指針域兩部分組成

二叉樹每個結(jié)點的指針域有兩個，一個指向左兒子，一個指向右兒子

還需一個鏈表的頭指針指向根結(jié)點

二叉樹的鏈接存儲結(jié)構(gòu)也稱為二叉鏈表

若二叉樹為空，則根結(jié)點為NULL

5.4二叉樹的存儲結(jié)構(gòu)5.4.3二叉樹的實現(xiàn)舉例1．以數(shù)組方式實現(xiàn)二叉樹

先依次序輸入元素值，一一建立二叉樹數(shù)組，