第一章緒論
1. 資料結構(data structure)：是指相互之間具有(存在)一定聯絡(關係)的資料元素的集合。
元素之間的相互聯絡(關係)稱為邏輯結構。資料元素之間的邏輯結構有四種基本型別：
① 集合：結構中的資料元素除了「同屬於乙個集合」外，沒有其它關係。
② 線性結構：結構中的資料元素之間存在一對一的關係。
③ 樹型結構：結構中的資料元素之間存在一對多的關係。
④ 圖狀結構或網狀結構：結構中的資料元素之間存在多對多的關係。
2. 演算法(algorithm)：是對特定問題求解方法(步驟)的一種描述，是指令的有限序列，其中每一條指令表示乙個或多個操作。
演算法具有以下五個特性
①有窮性： 乙個演算法必須總是在執行有窮步之後結束，且每一步都在有窮時間內完成。
②確定性：演算法中每一條指令必須有確切的含義。不存在二義性。且演算法只有乙個入口和乙個出口。
③可行性： 乙個演算法是能行的。即演算法描述的操作都可以通過已經實現的基本運算執行有限次來實現。
④ 輸入： 乙個演算法有零個或多個輸入，這些輸入取自於某個特定的物件集合。
⑤ 輸出： 乙個演算法有乙個或多個輸出，這些輸出是同輸入有著某些特定關係的量。
乙個演算法可以用多種方法描述，主要有：使用自然語言描述；使用形式語言描述；使用計算機程式語言描述。
3. 演算法設計的要求
①正確性 ② 可讀性 ③ 健壯性 ④ 通用性
4. 時間複雜度：
表示時間複雜度的階有：
o(1)：常量階；o(n)：線性階；o(log n)：對數階；o(nlog n)：線性對數階
以下六種計算演算法時間的多項式是最常用的。其關係為：
o(1)指數時間的關係為：
o(2n)5. 空間複雜度
一維陣列a[n]： 空間複雜度 o(n)
二維陣列a[n][m]： 空間複雜度 o(n*m)
第二章線性表
1. 線性表(linear list) ：是由n(n≧0)個資料元素(結點)a1，a2， …an組成的有限序列。
該序列中的所有結點具有相同的資料型別。其中資料元素的個數n稱為線性表的長度。當n=0時，稱為空表。
當n>0時，將非空的線性表記作：(a1，a2，…an) a1稱為線性表的第乙個(首)結點，an稱為線性表的最後乙個(尾)結點。a1，a2，…ai-1都是ai(2≦i≦n)的前驅，其中ai-1是ai的直接前驅；ai+1，ai+2，…an都是ai(1≦i ≦n-1)的後繼，其中ai+1是ai的直接後繼。
2. 線性表的邏輯結構和順序結構
線性表中的資料元素ai所代表的具體含義隨具體應用的不同而不同，**性表的定義中，只不過是乙個抽象的表示符號。
設線性表的每個元素需占用l個儲存單元，以所佔的第乙個單元的儲存位址作為資料元素的儲存位置。則線性表中第i+1個資料元素的儲存位置loc(ai+1)和第i個資料元素的儲存位置loc(ai)之間滿足下列關係：loc(ai+1)=loc(ai)+l 線性表的第i個資料元素ai的儲存位置為：
loc(ai)=loc(a1)+(i-1)*l
3. 順序表的特點：
線性表的順序儲存結構的特點是：邏輯關係上相鄰的兩個元素在物理位置上也相鄰，因此可以隨機訪問表中任意元素。弱點：在插入或刪除操作時，需移動大量元素。
4. 線性表的鏈式儲存結構
鏈式儲存 ：用一組任意的儲存單元儲存線性表中的資料元素。用這種方法儲存的線性表簡稱線性鍊錶。
儲存鍊錶中結點的一組任意的儲存單元可以是連續的，也可以是不連續的，甚至是零散分布在記憶體中的任意位置上的。
鍊錶中結點的邏輯順序和物理順序不一定相同。
資料結構知識點
第二章線性表是n個型別相同的資料元素的有限序列，對n 0,除第乙個元素無直接前驅，最後乙個元素無直接後繼外，其餘的每個資料元素只有乙個直接前驅和乙個直接後繼。1 同一性 線性表有同類元素資料組成，每乙個必須屬於同一資料型別。2 有窮性 線性表由有限個資料元素組成，表長就是表中資料元素的個數。3 有序...
資料結構C語言版知識點複習
資料結構複習資料 一 填空題 1.資料結構是一門研究非數值計算的程式設計問題中計算機的操作物件以及它們之間的關係和運算等的學科。2.資料結構被形式地定義為 d,r 其中d是資料元素的有限集合，r是d上的關係有限集合。3.資料結構包括資料的邏輯結構 資料的儲存結構和資料的運算這三個方面的內容。4.資料...
資料結構三章知識點及相應題目
第一章知識點 p3 資料結構從邏輯上劃分為 1 線性結構 2 非線性結構 樹型結構和圖型結構 p4 從儲存結構 物理結構 上劃分 1 順序結構 所有元素存放在一片連續的儲存單元中，邏輯上相鄰的元素存放到計算機記憶體中仍然相鄰 2 鏈式結構 所有元素存放在可以不連續的儲存單元中，但元素之間的關係可以通...