第一章緒論
程式設計的一般過程是「問題——想法——演算法——程式」，其實質是資料表示和資料處理。
資料結構是研究非數值問題中計算機的操作物件以及它們之間關係和操作的學科。
資料元素是資料的基本單位，在電腦程式中通常作為乙個整體進行考慮和處理。
資料項是資料的最小單位，資料元素是討論資料結構時涉及的最小資料單位。
從邏輯關係上講，資料結構主要分為集合，線性結構，樹結構，圖結構。
資料的記憶體結構主要有順序儲存結構，鏈結儲存結構兩種基本方法，不論哪種儲存結構，都要儲存兩方面的內容:資料元素和資料元素之間的關係。
演算法具有五個特性分別是有零個或多個輸入，有乙個或多個輸出，有窮性，確定性，可行性。
演算法的描述方法通常有自然語言，程式語言，流程圖和偽**，其中偽**被稱為演算法語言。
在一般情況下，乙個演算法的時間複雜度是問題規模的函式。
順序儲存結構中資料元素之間的邏輯關係是由儲存位置表示的，鏈結儲存結構中的資料元素之間的邏輯關係是由指標表示的。
可以用抽象資料型別定義乙個完整的資料元素。
演算法指的是對特定問題求解步驟的一種描述，是指令的有限序列。
演算法分析的目的是分析演算法的效率以求改進，演算法分析的兩個主要方面是資料複雜性和程式複雜性。
時間複雜度要通過演算法中基本語句執行次數的數量級來確定。
邏輯結構與資料元素本身的內容和形式無關。
順序儲存結構的特點是用元素在儲存器中的相對位置來表示資料元素之間的邏輯關係，鏈結儲存結構的特點是用指示元素儲存位址的指標表示資料元素之間的邏輯關係。
演算法在發生非法操作時可以做出處理的特性稱為健壯性。
常見的演算法時間複雜度用大o記號表示為：常數階
o（1），對數階o(log2n)，線性階o（n），平方階o(n^2)，指數階o(2^n)
第二章線性表
對順序表和單鏈表的比較要考慮時間效能和空間效能兩個方面。作為一般規律，若線性表需頻繁查詢卻很少進行插入和是刪除操作，或其操作和「資料元素**性表中的位置」密切相關時，宜採用順序表作為儲存結構；若線性表需頻繁進行插入和刪除操作，則宜採用單鏈表作為儲存結構；當線性表元素個數變化較大或者未知時，最好使用單鏈表實現；若使用者事先知道線性表的大致長度，使用順序表的空間效率會更高。
對於順序表，在等概率情況下，插入和刪除乙個元素平均需移表長的一半個元素，具體移動元素的個數與表長和該元素在表中的位置有關。
單鏈表中設頭結點的作用是為了方便運算。
乙個具有n個結點的單鏈表，在指標p所指結點後插入乙個新結點的時間複雜度為o（1）；在給定值為x的結點後插入乙個新結點的時間複雜度為o（n）。
可有乙個尾指標唯一確定的鍊錶有迴圈單鏈表，迴圈雙鏈表，雙鏈表。
線性表的順序儲存是一種隨機訪問的儲存結構，線性表的鏈結儲存結構是一種順序訪問的儲存結構。
線性表採用鏈結儲存時，其位址連續與否都可以。
單迴圈鍊錶的主要優點是從表中任一結點出發都能掃瞄到整個鍊錶。
鍊錶不具有的特點是可隨機訪問任一元素。
若某線性表中最常用的操作是去取第i個元素和找第i個元素的前趨，則採用順序表儲存節省時間。
若煉表中最常用的操作在最後乙個結點之後插入乙個結點和刪除乙個結點，則採用帶尾指標的單迴圈鍊錶儲存方法最節省時間。
若鍊錶最常用的操作是在最後乙個結點之後插入乙個結點和刪除最後乙個結點，則採用迴圈雙鏈表儲存方法最節省時間。
對於n個元素組成的線性表，建立乙個有序單鏈表的時間複雜度是o（n^2）.
使用雙鏈表儲存線性表，其優點是可以更方便資料的插入和刪除。
順序表的邏輯順序和儲存順序一致，鍊錶的邏輯順序和儲存順序不一定一致。
第三章棧和佇列
棧是限定僅在表尾進行插入和刪除操作的線性表。棧中元素除了具有線性關係外，還具有後進先出的特性。
棧的順序儲存結構稱為順序棧，順序棧本質上是順序表的簡化。通常把陣列中下標為0的一端作為棧底，同時附設指標top指示棧頂元素在陣列中的位置。
實現順序棧基本操作的演算法的時間複雜度均為o(1)。
棧的鏈結儲存結構稱為鏈棧，通常用單鏈表表示，並且不用附加頭結點。
鏈棧的插入和刪除操作只需處理棧頂即開始結點的情況，其時間複雜度均為o（1）。
佇列時只允許在一端進行插入操作，而另一端進行刪除操作的線性表。佇列中的元素除了具有線性關係外，還具有先進先出特性。
順序佇列會出現假溢位問題，解決的辦法是用首尾相接的順序儲存結構，稱為迴圈佇列。在迴圈佇列中，凡是涉及隊頭及隊尾指標的修改都需要將其求模。
在迴圈佇列中，隊空的判斷條件是：隊頭指標=隊尾指標；再浪費乙個儲存單元的情況下，隊滿的判定條件是（隊尾指標+1）%陣列長度=隊頭指標
佇列的鏈結儲存結構稱為鏈佇列。鏈佇列通常附設頭結點，並設定隊頭指標指向頭結點，隊尾指標指向終端結點。
鏈佇列基本操作的實現本質上也是單鏈表操作的簡化，插入只考慮在練佇列的尾部進行，刪除只考慮在鏈佇列的頭部進行，其時間複雜度均為o(1)。
棧結構通常採用的兩種儲存結構是順序儲存結構和鏈結儲存（順序棧和鏈棧），其判定棧空的條件分別是棧頂指標top=-1和top=null，其判定棧滿的條件分別是棧頂指標top等於陣列的長度和記憶體無可用空間。
棧可作為實現遞迴函式呼叫的一種資料結構。
棧和佇列是兩種特殊的線性表，棧的操作特性是後進先出，佇列的操作特性是先進先出，棧和佇列的主要區別在於對插入和刪除操作限定的位置不同。
迴圈佇列是為了克服假溢位。
陣列q【n】用來表示乙個迴圈佇列，front為隊頭元素的前乙個位置，rear為隊尾元素的位置，計算佇列中元素個數的計算公式為（rear-front+n）%n
用迴圈鍊錶表示的佇列中，出隊即是刪除開始結點，這只需修改相應指標；入隊即是在終端結點的後面插入乙個結點，這需要從頭指標開始查詢終端結點的位址。
設計乙個判別表示式中左右括號是否配對的演算法，採用棧資料結構最佳。
在解決計算機主機與印表機之間速度不匹配問題時通常設定乙個列印緩衝區，該緩衝區應該是乙個佇列結構。
棧和佇列的主要區別在於插入刪除運算的限定不一樣。
在棧滿的情況下不能做進棧操作，否則將產生「上溢」。
對於棧和佇列，無論它們採用順序儲存結構還是鏈結儲存結構，進行插入和刪除操作的時間複雜度都是o(1)。
第四章字串和多維陣列
字串是由0個或多個字元組成的有限序列。只包含空格串的稱為空格串，長度為0的稱為空串。
字串的比較是通過組成串的字元之間的比較來進行的，而字元見的大小關係是字元編碼之間的大小關係。
字串有順序儲存結構和鏈結儲存結構，在大多數語言中，串的儲存和基本操作的實現都是採用順序儲存
給定主串s和模式t，在主串s中尋找模式t的過程稱為模式匹配。bf演算法是一種帶回溯的匹配演算法，kmp演算法是一種不帶回溯的演算法
陣列是有型別相同的資料元素構成的有序集合，其特點是結構中的元素本身可以具有某種結構，但屬於同一資料型別。比如：一維陣列可以看作乙個線性表，二維陣列可以看作是線性表的線性表，以此類推，所以陣列是線性表的推廣。
在陣列中通常只有兩種操：訪問和修改，他們本質上只對應一種操作——定址
由於陣列一般不做插入和刪除操作，因此，陣列通常採用順序儲存結構。
採用順序儲存結構儲存二維陣列需要將二維陣列對映到一維結構，常用的對映方法有兩種：按行優先和按列優先。
矩陣壓縮儲存的基本思想是：為多個值相同的元素只分配乙個儲存空間；對0元素不分配儲存空間。
對稱矩陣壓縮儲存的基本方法是將下三角的元素按行優先儲存到一維陣列sa中，下三角的元素aij(i>j)在陣列sa中的下標k與i、j的關係是k=i*（i+1）/2+j-1.
下三角矩陣的壓縮儲存方法是將下三角中的元素按行儲存非零元素表示為三元組（行號、列號、非零元素）。將稀疏矩陣的非零元素對應的三元組所構成的集合，按行優先的順序排列成乙個線性表，稱為三元組表。
三元組表有兩種儲存結構：順序儲存結構（三元組順序表）和鏈結儲存結構（稱為十字鍊錶）
字串是一種特殊的線性表，其特殊性體現在資料元素的型別是乙個字元。
陣列通常只有兩種運算：訪問和修改，這決定了陣列通常採用順序儲存結構來實現儲存。
設有兩個串p和q，求q在p中首次出現的位置的運算稱作模式匹配。
將陣列稱為隨機訪問結構是因為對陣列任一元素的訪問時間是相等的
陣列是一種線型結構
陣列是一種定長的線型結構
陣列的基本操作有訪問、修改、檢索和排序等，沒有插入和刪除操作。
對特殊矩陣採用壓縮儲存的目的主要是為了減少不必要的儲存空間。
使用三元組儲存稀疏矩陣的元素，有時並不能節省儲存空間。
稀疏矩陣壓縮儲存後，必會失去隨機訪問功能。
樹是n（n>=0）個結點的有限集合。任意一顆非空數滿足：
1.有且僅有乙個特定的稱為根的結點；
2.當n>1時，除根節點之外的其餘結點被分成m（m>0）個互不相交的有限集合t1,t2,......,tm,其中每個集合又是一顆樹，並稱為這個根結點的字數。
樹的儲存結構有雙親表示法、孩子表示法、孩子雙親表示法、孩子兄弟表示法。
二叉樹的遍歷方式：前序遍歷、中序遍歷、後序遍歷和層序遍歷、
二叉樹有5中形態。
樹是n（n>=0）結點的有限集合，在一棵非空樹中，有且僅有乙個根結點，其餘的借點分成m（m>0）個互不相交的集合，每個集合都是根結點的子樹。
樹中某結點的個數稱為該結點的度，子樹的根結點稱為該結點的孩子，該結點稱為其子樹根結點的雙親。
一顆二叉樹的第i（i>=1）層最多有2^(i-1)個結點；一棵樹有n（n>0）個結點的滿二叉樹共有（n+1）/2個葉子結點和（n-1）/2個非終端結點。
設二叉樹有n個結點，則其深度最多是n，最少是【log2n】+1
如果t』是由有序樹t轉化而來的二叉樹，那麼t中結點的前序序列就是t』中結點的前序序列，t中結點的後序序列就是t』中結點的中序序列。
在二叉樹的前序遍歷序列中，任意乙個結點均處在其子女的前面。
由樹轉換成二叉樹，其根結點的右子樹總是空的。
對於一棵具有n個結點的樹，其所有結點的度之和為n-1.
前序遍歷和中序遍歷結果相同的二叉樹是根結點無左孩子的二叉樹。
第六章圖
在無向圖中，對於任意頂點vi和vj，若存在（vi，vj），則稱頂點vi和vj互為鄰接點。在有向圖中，對於任意頂點vi和vj，若存在弧《vi，vj》，則稱頂點vj是vi的鄰接點。
含有n個頂點的無向完全圖共有n*（n-1）/2條邊；含有n個頂點的有向完全圖共有n*（n-1）條邊。
資料結構概念
資料結構是資訊的組織方式。對於相同的演算法，用不同的資料結構表示其中的抽象資料型別會造成不同的執行效率。這就有必要研究各種抽象資料型別用不同的資料結構表示的效率差異，以及其適用場合。何謂資料結構 資料結構是在整個電腦科學與技術領域上廣泛被使用的術語。它用來反映乙個資料的內部構成，即乙個資料由那些成分...
資料結構概念
線性表的特徵 1 有且僅有乙個開始結點 表頭結點 a1，它沒有直接前驅，只有乙個直接後繼 2 有且僅有乙個終端結點 表尾結點 an，它沒有直接後繼，只有乙個直接前驅 3 其它結點都有乙個直接前驅和直接後繼 4 元素之間為一對一的線性關係。在順序儲存結構中為 o 1 在鏈式儲存結構中為 o n 棧 先...
資料結構基礎試題
資料結構試卷 a卷 考試時間 分鐘閉卷 班級學號姓名成績 一 單項選擇 每空2分，共30分 1.資料結構是一門研究非數值計算的程式設計問題中,資料元素的 資料資訊在計算機中的 以及一組相關的運算等的課程。a 操作物件 計算方法 邏輯結構 資料映象 a 儲存結構 關係運算演算法 2.線性表的邏輯順序與...