數(shù)據(jù)結(jié)構基礎概念

1、第一章 緒論 程序設計的一般過程是“問題想法算法 程序”，其實質(zhì)是數(shù)據(jù)表示和數(shù)據(jù)處理。數(shù)據(jù)結(jié)構是研究非數(shù)值問題中計算機的操作對象以及 它們之間關系和操作的學科。數(shù)據(jù)元素是數(shù)據(jù)的基本單位，在計算機程序中通常作 為一個整體進行考慮和處理。數(shù)據(jù)項是數(shù)據(jù)的最小單位，數(shù)據(jù)元素是討論數(shù)據(jù)結(jié)構 時涉及的最小數(shù)據(jù)單位。從邏輯關系上講， 數(shù)據(jù)結(jié)構主要分為集合， 線性結(jié)構， 樹結(jié)構，圖結(jié)構。數(shù)據(jù)的內(nèi)存結(jié)構主要有順序存儲結(jié)構，鏈接存儲結(jié)構兩種基本方法，不論哪種存儲結(jié)構，都要存儲兩方面 算法具有五個特性分別是有零個或多個輸入，有一個 或多個輸出，有窮性，確定性，可行性。的內(nèi)容: 數(shù)據(jù)元素和數(shù)據(jù)元素之間的關系dzx47

2、ZW DgWmLvg算法的描述方法通常有自然語言，程序設計語言，流 程圖和偽代碼，其中偽代碼被稱為算法語言。在一般情況下，一個算法的時間復雜度是問題規(guī)模的 函數(shù)。順序存儲結(jié)構中數(shù)據(jù)元素之間的邏輯關系是由存儲位 置表示的，鏈接存儲結(jié)構中的數(shù)據(jù)元素之間的邏輯關 系是由指針表示的。 VYry6Ae NGbHYvp可以用抽象數(shù)據(jù)類型定義一個完整的數(shù)據(jù)元素。 算法指的是對特定問題求解步驟的一種描述，是指令 的有限序列。算法分析的目的是分析算法的效率以求改進，算法分 析的兩個主要方面是數(shù)據(jù)復雜性和程序復雜性。時間復雜度要通過算法中基本語句執(zhí)行次數(shù)的數(shù)量級 來確定。邏輯結(jié)構與數(shù)據(jù)元素本身的內(nèi)容和形式無關。順

3、序存儲結(jié)構的特點是用元素在存儲器中的相對位置 來表示數(shù)據(jù)元素之間的邏輯關系，鏈接存儲結(jié)構的特 點是用指示元素存儲地址的指針表示數(shù)據(jù)元素之間的 邏輯關系。 2sRps2T。 DxJQ8Zz。算法在發(fā)生非法操作時可以做出處理的特性稱為健壯 性。常見的算法時間復雜度用大 O 記號表示為：常數(shù)階 （1）,寸數(shù)階O（log2 n），線性階（n）平方階0（n八2）, 指數(shù)階0（2八n）第二章 線性表對順序表和單鏈表的比較要考慮時間性能和空間性能 兩個方面。作為一般規(guī)律，若線性表需頻繁查找卻很 少進行插入和是刪除操作，或其操作和“數(shù)據(jù)元素在 線性表中的位置”密切相關時，宜采用順序表作為存 儲結(jié)構；若線性表需

4、頻繁進行插入和刪除操作，則宜 采用單鏈表作為存儲結(jié)構；當線性表元素個數(shù)變化較 大或者未知時，最好使用單鏈表實現(xiàn)；若用戶事先知 道線性表的大致長度， 使用順序表的空間效率會更高。 GHI21En。 1U2A3fI。對于順序表，在等概率情況下，插入和刪除一個元素 平均需移表長的一半個元素，具體移動元素的個數(shù)與 表長和該元素在表中的位置有關。 HgVZRRP l2bTSD5 單鏈表中設頭結(jié)點的作用是為了方便運算。一個具有n個結(jié)點的單鏈表，在指針p所指結(jié)點后插 入一個新結(jié)點的時間復雜度為 0( 1)；在給定值為x 的結(jié)點后插入一個新結(jié)點的時間復雜度為 0( n)。PW221AI WMkGS26可有一個

5、尾指針唯一確定的鏈表有循環(huán)單鏈表，循環(huán) 雙鏈表，雙鏈表。線性表的順序存儲是一種隨機存取的存儲結(jié)構，線性 表的鏈接存儲結(jié)構是一種順序存取的存儲結(jié)構。 線性表采用鏈接存儲時，其地址連續(xù)與否都可以。 單循環(huán)鏈表的主要優(yōu)點是從表中任一結(jié)點出發(fā)都能掃 描到整個鏈表。鏈表不具有的特點是可隨機訪問任一元素。 若某線性表中最常用的操作是去取第 i 個元素和找第i 個元素的前趨，則采用順序表存儲節(jié)省時間。 若鏈表中最常用的操作在最后一個結(jié)點之后插入一個結(jié)點和刪除一個結(jié)點，則采用帶尾指針的單循環(huán)鏈表 若鏈表最常用的操作是在最后一個結(jié)點之后插入一個 結(jié)點和刪除最后一個結(jié)點，則采用循環(huán)雙鏈表存儲方 法最節(jié)省時間。 v

6、bwaqtC。Rw9JWra存儲方法最節(jié)省時間JNSYgHo f4WNsH對于 n 個元素組成的線性表，建立一個有序單鏈表的 時間復雜度是O(nT).使用雙鏈表存儲線性表，其優(yōu)點是可以更方便數(shù)據(jù)的 插入和刪除。順序表的邏輯順序和存儲順序一致，鏈表的邏輯順序 和存儲順序不一定一致。第三章 棧和隊列 棧是限定僅在表尾進行插入和刪除操作的線性表。棧 中元素除了具有線性關系外， 還具有后進先出的特性。 棧的順序存儲結(jié)構稱為順序棧，順序棧本質(zhì)上是順序 表的簡化。通常把數(shù)組中下標為 0 的一端作為棧底， 同時附設指針 top 指示棧頂元素在數(shù)組中的位置。 hZrDvC2。 7Ow9IPE。實現(xiàn)順序?；静?/p>

7、作的算法的時間復雜度均為 O(1)。 棧的鏈接存儲結(jié)構稱為鏈棧，通常用單鏈表表示，并 且不用附加頭結(jié)點。 鏈棧的插入和刪除操作只需處理棧頂即開始結(jié)點的情 況，其時間復雜度均為 O（1）。 隊列時只允許在一端進行插入操作，而另一端進行刪 除操作的線性表。隊列中的元素除了具有線性關系外， 還具有先進先出特性。 2BadP0x FIEiUde。 順序隊列會出現(xiàn)假溢出問題，解決的辦法是用首尾相 接的順序存儲結(jié)構，稱為循環(huán)隊列。在循環(huán)隊列中， 凡是涉及隊頭及隊尾指針的修改都需要將其求模。MwiC18F SU38JMM在循環(huán)隊列中，隊空的判斷條件是： 隊頭指針=隊尾指 針；再浪費一個存儲單元的情況下，隊滿

8、的判定條件 是（隊尾指針 +1）%數(shù)組長度 =隊頭指針 IZzduNi o mwt8T7H 隊列的鏈接存儲結(jié)構稱為鏈隊列。鏈隊列通常附設頭 結(jié)點，并設置隊頭指針指向頭結(jié)點，隊尾指針指向終 端結(jié)點。鏈隊列基本操作的實現(xiàn)本質(zhì)上也是單鏈表操作的簡 化，插入只考慮在練隊列的尾部進行，刪除只考慮在 鏈隊列的頭部進行， 其時間復雜度均為 0（1） o dCWxsb0 fbBBZnS 棧結(jié)構通常采用的兩種存儲結(jié)構是順序存儲結(jié)構和鏈 接存儲（順序棧和鏈棧），其判定?？盏臈l件分別是棧 頂指針 top=-1 和 top=null ，其判定棧滿的條件分別 是棧頂指針 top 等于數(shù)組的長度和內(nèi)存無可用空間。56HK

9、dRU 9duAG61 ?？勺鳛閷崿F(xiàn)遞歸函數(shù)調(diào)用的一種數(shù)據(jù)結(jié)構。 棧和隊列是兩種特殊的線性表，棧的操作特性是后進 先出，隊列的操作特性是先進先出，棧和隊列的主要 區(qū)別在于對插入和刪除操作限定的位置不同。 CWDUIFmIIdfufa 。 循環(huán)隊列是為了克服假溢出。數(shù)組Q【n】用來表示一個循環(huán)隊列，front為隊頭元 素的前一個位置， rear 為隊尾元素的位置，計算隊列 中元素個數(shù)的計算公式為 (rear-front+n )%nnm sPtIO。T1PYdK5 用循環(huán)鏈表表示的隊列中，出隊即是刪除開始結(jié)點， 這只需修改相應指針；入隊即是在終端結(jié)點的后面插 入一個結(jié)點，這需要從頭指針開始查找終端

10、結(jié)點的地 址。 HYjh0Uq。 BFqCrJX。設計一個判別表達式中左右括號是否配對的算法，采 用棧數(shù)據(jù)結(jié)構最佳。在解決計算機主機與打印機之間速度不匹配問題時通 常設置一個打印緩沖區(qū)，該緩沖區(qū)應該是一個隊列結(jié) 構。棧和隊列的主要區(qū)別在于插入刪除運算的限定不一 樣。在棧滿的情況下不能做進棧操作， 否則將產(chǎn)生“上溢” 對于棧和隊列，無論它們采用順序存儲結(jié)構還是鏈接 存儲結(jié)構，進行插入和刪除操作的時間復雜度都是 O(1)。第四章 字符串和多維數(shù)組字符串是由 0 個或多個字符組成的有限序列。 只包含空格串的稱 為空格串，長度為 0 的稱為空串。字符串的比較是通過組成串的字符之間的比較來進行的， 而字

11、符 見的大小關系是字符編碼之間的大小關系。字符串有順序存儲結(jié)構和鏈接存儲結(jié)構， 在大多數(shù)語言中， 串的 存儲和基本操作的實現(xiàn)都是采用順序存儲給定主串S和模式T,在主串S中尋找模式T的過程稱為模式匹 配。BF算法是一種帶回溯的匹配算法，KMP算法是一種不帶回溯的算法 XjSy9WF YY25shL 數(shù)組是有類型相同的數(shù)據(jù)元素構成的有序集合， 其特點是結(jié)構中 的元素本身可以具有某種結(jié)構，但屬于同一數(shù)據(jù)類型。比如：一 維數(shù)組可以看作一個線性表， 二維數(shù)組可以看作是線性表的線性 表，以此類推，所以數(shù)組是線性表的推廣。NTTwIbs UR1X74M在數(shù)組中通常只有兩種操： 存取和修改， 他們本質(zhì)上只對應

12、一種 操作尋址由于數(shù)組一般不做插入和刪除操作， 因此， 數(shù)組通常采用順序存 儲結(jié)構。采用順序存儲結(jié)構存儲二維數(shù)組需要將二維數(shù)組映射到一維結(jié) 構，常用的映射方法有兩種：按行優(yōu)先和按列優(yōu)先。 矩陣壓縮存儲的基本思想是： 為多個值相同的元素只分配一個存 儲空間；對 0 元素不分配存儲空間。 對稱矩陣壓縮存儲的基本方法是將下三角的元素按行優(yōu)先存儲 到一維數(shù)組SA中，下三角的元素 aij （i>j）在數(shù)組SA中的下標k 與 i 、j 的關系是 k=i* （i+1 ）/2+j-1 . 3wkNLE1 PtKndcH 下三角矩陣的壓縮存儲方法是將下三角中的元素按行存儲非零 元素表示為三元組（行號、列號

13、、非零元素） 。將稀疏矩陣的非 零元素對應的三元組所構成的集合， 按行優(yōu)先的順序排列成一個 線性表，稱為三元組表。 wEppgHMyjoFU18。 三元組表有兩種存儲結(jié)構：順序存儲結(jié)構（三元組順序表）和鏈 接存儲結(jié)構（稱為十字鏈表） 字符串是一種特殊的線性表， 其特殊性體現(xiàn)在數(shù)據(jù)元素的類型是 一個字符。數(shù)組通常只有兩種運算： 存取和修改， 這決定了數(shù)組通常采用順 序存儲結(jié)構來實現(xiàn)存儲。設有兩個串p和q,求q在p中首次出現(xiàn)的位置的運算稱作模式 匹配。將數(shù)組稱為隨機存取結(jié)構是因為對數(shù)組任一元素的存取時間是 相等的數(shù)組是一種線型結(jié)構 數(shù)組是一種定長的線型結(jié)構數(shù)組的基本操作有存取、修改、檢索和排序等，

14、沒有插入和刪除 操作。對特殊矩陣采用壓縮存儲的目的主要是為了減少不必要的存儲 空間。使用三元組存儲稀疏矩陣的元素，有時并不能節(jié)省存儲空間。 稀疏矩陣壓縮存儲后，必會失去隨機存取功能。樹是n (n>=0)個結(jié)點的有限集合。任意一顆非空數(shù)滿足：1. 有且僅有一個特定的稱為根的結(jié)點；2. 當n>1時，除根節(jié)點之外的其余結(jié)點被分成 m( m>0個互不相交的有限集合 T1,T2,Tm, 其中每個集合又是一顆樹，并稱為這個根結(jié)點的字數(shù)。 zZ4BOw7 7phkQoV樹的存儲結(jié)構有雙親表示法、孩子表示法、孩子雙親表示法、孩 子兄弟表示法。二叉樹的遍歷方式： 前序遍歷、中序遍歷、 后序遍歷

15、和層序遍歷、 二叉樹有 5 中形態(tài)。樹是n(n>=0)結(jié)點的有限集合，在一棵非空樹中， 有且僅有一個根結(jié)點，其余的借點分成 m( m>0個互 不相交的集合， 每個集合都是根結(jié)點的子樹。 QI1IW3v。Iwmpwwk 樹中某結(jié)點的個數(shù)稱為該結(jié)點的度，子樹的根結(jié)點稱 為該結(jié)點的孩子，該結(jié)點稱為其子樹根結(jié)點的雙親。 一顆二叉樹的第i (i>=1 )層最多有2A(i-1)個結(jié)點； 一棵樹有n (n>0)個結(jié)點的滿二叉樹共有(n+1) /2個葉子結(jié)點和（ n-1 ）/2 個非終端結(jié)點 o Gob221k UdNDxVN 設二叉樹有n個結(jié)點，則其深度最多是n，最少是【log2n

16、】 +1如果T是由有序樹T轉(zhuǎn)化而來的二叉樹，那么 T中 結(jié)點的前序序列就是T'中結(jié)點的前序序列，T中結(jié)點 的后序序列就是T'中結(jié)點的中序序列。g0hrx4j 。 eQSJmOG在二叉樹的前序遍歷序列中，任意一個結(jié)點均處在其 子女的前面。由樹轉(zhuǎn)換成二叉樹，其根結(jié)點的右子樹總是空的。 對于一棵具有 n 個結(jié)點的樹，其所有結(jié)點的度之和為 n-1.前序遍歷和中序遍歷結(jié)果相同的二叉樹是根結(jié)點無左 孩子的二叉樹。第六章 圖 在無向圖中，對于任意頂點 Vi 和 Vj ，若存在（ Vi，Vj），則稱頂點Vi和Vj互為鄰接點。在有向圖中，對于任意頂點Vi和Vj，若存在弧Vi，Vj，則稱頂點Vj

17、是 Vi 的鄰接點DodsiJ3 N IsuHALoN含有 n 個頂點的無向完全圖共有n*（n-1） /2 條邊； 含有n個頂點的有向完全圖共有n* （n-1 ）條邊。 在無向圖中，頂點 v 的度是指依附于該頂點的邊的個 數(shù)；在有向圖中，頂點 v 的入度是指以該頂點為弧頭的弧的個數(shù)，頂點 v 的出度是指以該頂點為弧尾的弧 的個數(shù)。 eM9LkNm 3oAmku1 在圖中，權通常是指對邊賦予的有意義的數(shù)量值，邊 上帶權的圖稱為網(wǎng)或網(wǎng)圖。在無向圖G=(V,E)中，頂點Vp到Vq之間的路徑是一 個頂點序列Vp=ViO, Vi,Vim=Vq其中，(Vij-1 ,Vij ) E( 1<=j<

18、=m);如果 G是有向圖，則<Vij-1,Vij> E(1v=jv=m).路徑上邊的數(shù)目稱為路徑長度。第一個頂點和最后一個頂點相同的路徑稱為回路Z7eSsOF oq65nHy。在無向圖中，若任意頂點 Vi和Vj (i豐j )之間有路 徑，則稱該圖是連通圖，非連通圖的極大連通子圖稱 為連通分量；在有向圖中，對任意頂點Vi和Vj (i工j )，若從頂點 Vi 到 Vj 和頂點 Vj 到 Vi 均有路徑，則 稱該有向圖為強連通圖，非強連通圖的極大強連通子 圖稱為強連通分量。 LYhVxGc fA6mDcB 連通圖G的生成樹是包含G中全部頂點的一個極小連 通子圖。圖的生成樹可以在遍歷過程中得到。圖的遍歷通常有深度優(yōu)先遍歷和廣度優(yōu)先遍歷兩種方 式。圖的深度優(yōu)先遍歷是以遞歸方式進行的，需用棧 記載遍歷路線；圖的廣度優(yōu)先遍歷是以層次方式進行 的，需用隊列保存已訪問的頂點。 JY97fQt 。 fJv3FWv。 為了在圖的遍歷過程中區(qū)分頂點是否已被訪問，設置 一個訪問標志數(shù)組 visitedn, 其初值為未被訪問標 志“ 0”，如果某個頂點已被訪問，則將該頂點的訪問 標志置為“ 1 YylyoAQ 4dhEKPs圖的存儲結(jié)構有鄰接矩陣，鄰接表