數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)概念

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

2、言，程序設(shè)計語言，流 程圖和偽代碼，其中偽代碼被稱為算法語言。在一般情況下，一個算法的時間復(fù)雜度是問題規(guī)模的 函數(shù)。順序存儲結(jié)構(gòu)中數(shù)據(jù)元素之間的邏輯關(guān)系是由存儲位 置表示的，存儲結(jié)構(gòu)中的數(shù)據(jù)元素之間的邏輯關(guān)系是 由指針表示的?？梢杂贸橄髷?shù)據(jù)類型定義一個完整的數(shù)據(jù)元素。算法指的是對特定問題求解步驟的一種描述，是指令 的有限序列。算法分析的目的是分析算法的效率以求改良，算法分 析的兩個主要方面是數(shù)據(jù)復(fù)雜性和程序復(fù)雜性。時間復(fù)雜度要通過算法中根本語句執(zhí)行次數(shù)的數(shù)量級 來確定。邏輯結(jié)構(gòu)與數(shù)據(jù)元素本身的容和形式無關(guān) 順序存儲結(jié)構(gòu)的特點是用元素在存儲器中的相對位置 來表示數(shù)據(jù)元素之間的邏輯關(guān)系，存儲結(jié)構(gòu)的

3、特點是 用指示元素存儲地址的指針表示數(shù)據(jù)元素之間的邏輯 關(guān)系。算法在發(fā)生非法操作時可以做出處理的特性稱為健壯 性。常見的算法時間復(fù)雜度用大 O 記號表示為：常數(shù)階O( 1),對數(shù)階O(log2n)，線性階O(n),平方階O(nA2), 指數(shù)階O(2An)第二章 線性表對順序表和單鏈表的比擬要考慮時間性能和空間性能 兩個方面。作為一般規(guī)律，假設(shè)線性表需頻繁查找卻很 少進行插入和是刪除操作，或其操作和“數(shù)據(jù)元素在 線性表中的位置密切相關(guān)時，宜采用順序表作為存 儲結(jié)構(gòu)；假設(shè)線性表需頻繁進行插入和刪除操作，那么宜 采用單鏈表作為存儲結(jié)構(gòu)；當(dāng)線性表元素個數(shù)變化較 大或者未知時，最好使用單鏈表實現(xiàn)；假設(shè)用

4、戶事先知道線性表的大致長度， 使用順序表的空間效率會更高 對于順序表，在等概率情況下，插入和刪除一個元素平均需移表長的一半個元素，具體移動元素的個數(shù)與 表長和該元素在表中的位置有關(guān)。單鏈表中設(shè)頭結(jié)點的作用是為了方便運算。一個具有n個結(jié)點的單鏈表，在指針p所指結(jié)點后插 入一個新結(jié)點的時間復(fù)雜度為 0( 1)；在給定值為x 的結(jié)點后插入一個新結(jié)點的時間復(fù)雜度為 O(n)?？捎幸粋€尾指針唯一確定的鏈表有循環(huán)單鏈表，循環(huán) 雙鏈表，雙鏈表。線性表的順序存儲是一種隨機存取的存儲結(jié)構(gòu)，線性 表的存儲結(jié)構(gòu)是一種順序存取的存儲結(jié)構(gòu)。線性表采用存儲時，其地址連續(xù)與否都可以。單循環(huán)鏈表的主要優(yōu)點是從表中任一結(jié)點出發(fā)

5、都能掃 描到整個鏈表。鏈表不具有的特點是可隨機訪問任一元素 假設(shè)某線性表中最常用的操作是去取第 i 個元素和找第 i 個元素的前趨，那么采用順序表存儲節(jié)省時間。假設(shè)鏈表中最常用的操作在最后一個結(jié)點之后插入一個結(jié)點和刪除一個結(jié)點，那么采用帶尾指針的單循環(huán)鏈表 存儲方法最節(jié)省時間。假設(shè)鏈表最常用的操作是在最后一個結(jié)點之后插入一個 結(jié)點和刪除最后一個結(jié)點，那么采用循環(huán)雙鏈表存儲方 法最節(jié)省時間。對于 n 個元素組成的線性表，建立一個有序單鏈表的 時間復(fù)雜度是O 5人2).使用雙鏈表存儲線性表，其優(yōu)點是可以更方便數(shù)據(jù)的 插入和刪除。順序表的邏輯順序和存儲順序一致，鏈表的邏輯順序 和存儲順序不一定一致

6、第三章 棧和隊列 棧是限定僅在表尾進行插入和刪除操作的線性表。棧 中元素除了具有線性關(guān)系外， 還具有后進先出的特性。棧的順序存儲結(jié)構(gòu)稱為順序棧，順序棧本質(zhì)上是順序 表的簡化。通常把數(shù)組中下標(biāo)為 0 的一端作為棧底， 同時附設(shè)指針 top 指示棧頂元素在數(shù)組中的位置。實現(xiàn)順序棧根本操作的算法的時間復(fù)雜度均為 O(1)棧的存儲結(jié)構(gòu)稱為鏈棧，通常用單鏈表表示，并且不 用附加頭結(jié)點。鏈棧的插入和刪除操作只需處理棧頂即開始結(jié)點的情 況，其時間復(fù)雜度均為 O(1)。隊列時只允許在一端進行插入操作，而另一端進行刪 除操作的線性表。隊列中的元素除了具有線性關(guān)系外， 還具有先進先出特性。順序隊列會出現(xiàn)假溢出問題

7、，解決的方法是用首尾相 接的順序存儲結(jié)構(gòu)，稱為循環(huán)隊列。在循環(huán)隊列中， 但凡涉及隊頭及隊尾指針的修改都需要將其求模。在循環(huán)隊列中，隊空的判斷條件是： 隊頭指針=隊尾指 針；再浪費一個存儲單元的情況下，隊滿的判定條件 是隊尾指針 +1%數(shù)組長度 =隊頭指針隊列的存儲結(jié)構(gòu)稱為鏈隊列。 鏈隊列通常附設(shè)頭結(jié)點， 并設(shè)置隊頭指針指向頭結(jié)點， 隊尾指針指向終端結(jié)點。鏈隊列根本操作的實現(xiàn)本質(zhì)上也是單鏈表操作的簡 化，插入只考慮在練隊列的尾部進行，刪除只考慮在 鏈隊列的頭部進行，其時間復(fù)雜度均為 O1。棧結(jié)構(gòu)通常采用的兩種存儲結(jié)構(gòu)是順序存儲結(jié)構(gòu)和存 儲順序棧和鏈棧，其判定棧空的條件分別是棧頂指 針 top=-

8、1 和 top=null ，其判定棧滿的條件分別是棧頂 指針 top 等于數(shù)組的長度和存無可用空間。?？勺鳛閷崿F(xiàn)遞歸函數(shù)調(diào)用的一種數(shù)據(jù)結(jié)構(gòu)。棧和隊列是兩種特殊的線性表，棧的操作特性是后進 先出，隊列的操作特性是先進先出，棧和隊列的主要 區(qū)別在于對插入和刪除操作限定的位置不同。循環(huán)隊列是為了克服假溢出。數(shù)組Q【n】用來表示一個循環(huán)隊列，front為隊頭元 素的前一個位置， rear 為隊尾元素的位置，計算隊列 中元素個數(shù)的計算公式為( rear-front+n)%n用循環(huán)鏈表表示的隊列中，出隊即是刪除開始結(jié)點，這只需修改相應(yīng)指針；入隊即是在終端結(jié)點的后面插 入一個結(jié)點，這需要從頭指針開始查找終端

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

10、有順序存儲結(jié)構(gòu)和存儲結(jié)構(gòu)， 在大多數(shù)語言中， 串的存儲和根本操作的實現(xiàn)都是采用順序存儲給定主串 S 和模式 T ，在主串 S 中尋找模式 T 的過程稱為模式匹配。BF算法是一種帶回溯的匹配算法， KMP算法是一種不帶回溯的算法數(shù)組是有類型相同的數(shù)據(jù)元素構(gòu)成的有序集合， 其特點是結(jié)構(gòu)中 的元素本身可以具有某種結(jié)構(gòu)，但屬于同一數(shù)據(jù)類型。比方：一 維數(shù)組可以看作一個線性表， 二維數(shù)組可以看作是線性表的線性 表，以此類推，所以數(shù)組是線性表的推廣。在數(shù)組常只有兩種操： 存取和修改， 他們本質(zhì)上只對應(yīng)一種操作 尋址由于數(shù)組一般不做插入和刪除操作， 因此， 數(shù)組通常采用順序存 儲結(jié)構(gòu)。采用順序存儲結(jié)構(gòu)存儲二

11、維數(shù)組需要將二維數(shù)組映射到一維結(jié) 構(gòu)，常用的映射方法有兩種：按行優(yōu)先和按列優(yōu)先。矩陣壓縮存儲的根本思想是： 為多個值相同的元素只分配一個存 儲空間；對 0 元素不分配存儲空間。對稱矩陣壓縮存儲的根本方法是將下三角的元素按行優(yōu)先存儲 到一維數(shù)組 SA 中，下三角的元素 aiji>j 在數(shù)組 SA 中的下標(biāo) k 與 i、j 的關(guān)系是 k=i* i+1/2+j-1.下三角矩陣的壓縮存儲方法是將下三角中的元素按行存儲非零 元素表示為三元組行號、列號、非零元素 。將稀疏矩陣的非零元素對應(yīng)的三元組所構(gòu)成的集合， 按行優(yōu)先的順序排列成一個 線性表，稱為三元組表。三元組表有兩種存儲結(jié)構(gòu)：順序存儲結(jié)構(gòu)三元

12、組順序表和存 儲結(jié)構(gòu)稱為十字鏈表字符串是一種特殊的線性表， 其特殊性表達在數(shù)據(jù)元素的類型是 一個字符。數(shù)組通常只有兩種運算： 存取和修改， 這決定了數(shù)組通常采用順 序存儲結(jié)構(gòu)來實現(xiàn)存儲。設(shè)有兩個串p和q,求q在p中首次出現(xiàn)的位置的運算稱作模式 匹配。將數(shù)組稱為隨機存取結(jié)構(gòu)是因為對數(shù)組任一元素的存取時間是 相等的數(shù)組是一種線型結(jié)構(gòu)數(shù)組是一種定長的線型結(jié)構(gòu) 數(shù)組的根本操作有存取、修改、檢索和排序等，沒有插入和刪除 操作。 對特殊矩陣采用壓縮存儲的目的主要是為了減少不必要的存儲空間。使用三元組存儲稀疏矩陣的元素，有時并不能節(jié)省存儲空間。 稀疏矩陣壓縮存儲后，必會失去隨機存取功能。樹是 n( n>

13、;=0 )個結(jié)點的有限集合。任意一顆非空數(shù)滿足：1.有且僅有一個特定的稱為根的結(jié)點；2當(dāng)n>1時，除根節(jié)點之外的其余結(jié)點被分成m (m>0)個互不相交的有限集合 T1,T2,Tm,其中每個集合又是一顆樹，并稱 為這個根結(jié)點的字數(shù)。樹的存儲結(jié)構(gòu)有雙親表示法、孩子表示法、孩子雙親表示法、孩 子兄弟表示法。二叉樹的遍歷方式：前序遍歷、中序遍歷、后序遍歷和層序遍歷、二叉樹有 5 中形態(tài)。樹是n (n>=0)結(jié)點的有限集合，在一棵非空樹中， 有且僅有一個根結(jié)點，其余的借點分成m (m>0)個互不相交的集合，每個集合都是根結(jié)點的子樹。樹中某結(jié)點的個數(shù)稱為該結(jié)點的度，子樹的根結(jié)點稱

14、為該結(jié)點的孩子，該結(jié)點稱為其子樹根結(jié)點的雙親。一顆二叉樹的第i (i>=1)層最多有2A(i-1)個結(jié)點；一 棵樹有n (n>0)個結(jié)點的滿二叉樹共有(n+1)/2個 葉子結(jié)點和( n-1) /2個非終端結(jié)點。設(shè)二叉樹有n個結(jié)點，那么其深度最多是n，最少是【log2n】+1如果T'是由有序樹T轉(zhuǎn)化而來的二叉樹，那么T中 結(jié)點的前序序列就是T'中結(jié)點的前序序列，T中結(jié)點 的后序序列就是T'中結(jié)點的中序序列。在二叉樹的前序遍歷序列中，任意一個結(jié)點均處在其 子女的前面。由樹轉(zhuǎn)換成二叉樹，其根結(jié)點的右子樹總是空的 對于一棵具有 n 個結(jié)點的樹，其所有結(jié)點的度之和為

15、n-1.前序遍歷和中序遍歷結(jié)果相同的二叉樹是根結(jié)點無左 孩子的二叉樹。第六章 圖在無向圖中，對于任意頂點 Vi 和 Vj ，假設(shè)存在 Vi， Vj,那么稱頂點Vi和Vj互為鄰接點。在有向圖中，對 于任意頂點Vi和Vj，假設(shè)存在弧?Vi, Vj?那么稱頂點 Vj 是 Vi 的鄰接點。含有 n 個頂點的無向完全圖共有 n*n-1 /2 條邊； 含有n個頂點的有向完全圖共有n* n-1條邊。在無向圖中，頂點 v 的度是指依附于該頂點的邊的個 數(shù)；在有向圖中，頂點 v 的入度是指以該頂點為弧頭 的弧的個數(shù)，頂點 v 的出度是指以該頂點為弧尾的弧 的個數(shù)。在圖中，權(quán)通常是指對邊賦予的有意義的數(shù)量值，邊

16、上帶權(quán)的圖稱為網(wǎng)或網(wǎng)圖。在無向圖G=(V,E)中，頂點Vp到Vq之間的路徑是一 個頂點序列Vp=ViO ,Vim=Vq ,其中，(Vij-1 ,Vij) E (1<=jv=m );如果 G 是有向圖，那么<Vij-1,Vij > E(1<=j<=m).路徑上邊的數(shù)目稱為路徑長度。第一個 頂點和最后一個頂點相同的路徑稱為回路。在無向圖中，假設(shè)任意頂點 Vi和Vj (i工j )之間有路 徑，那么稱該圖是連通圖，非連通圖的極通子圖稱為連 通分量；在有向圖中，對任意頂點 Vi和Vj (i工j ), 假設(shè)從頂點 Vi 到 Vj 和頂點 Vj 到 Vi 均有路徑，那么稱該 有

17、向圖為強連通圖，非強連通圖的極大強連通子圖稱 為強連通分量。連通圖G的生成樹是包含G中全部頂點的一個極小連 通子圖。圖的生成樹可以在遍歷過程中得到。圖的遍歷通常有深度優(yōu)先遍歷和廣度優(yōu)先遍歷兩種方 式。圖的深度優(yōu)先遍歷是以遞歸方式進行的，需用棧 記載遍歷路線；圖的廣度優(yōu)先遍歷是以層次方式進行的，需用隊列保存已訪問的頂點 為了在圖的遍歷過程中區(qū)分頂點是否已被訪問，設(shè)置 一個訪問標(biāo)志數(shù)組 visitedn, 其初值為未被訪問標(biāo) 志“ 0，如果某個頂點已被訪問，那么將該頂點的訪問 標(biāo)志置為“ 1圖的存儲結(jié)構(gòu)有鄰接矩陣，鄰接表，十字鏈表，鄰接 多重表等。圖的鄰接矩陣存儲用一個一維數(shù)組存儲圖中頂點的信 息，用一個二維數(shù)組存儲圖中邊的信息鄰接矩陣 ； 圖的鄰接表存儲由邊表和頂點表組成，圖中每個頂點 的所有鄰接點構(gòu)成一個邊表，所有邊表的頭指針和存 儲頂點信息的一維數(shù)組構(gòu)成頂點表。最小生成樹是無向連通網(wǎng)中代價最小的生成樹。最小 生成樹具有MST性質(zhì)，Prim算法和Kruskal算法是兩 個利用MST性質(zhì)構(gòu)造最小生成樹的經(jīng)典算法。Prim算 法的時間復(fù)雜度為 0 5人2，適用于求稠密網(wǎng)的最小 生成樹；Kruskal算法的時間復(fù)雜度為Oelog2