資料結構
第一章緒論
1、資料結構的定義：按照某種邏輯關係組織起來的資料集、。
2、資料主要分為兩大類：數值型資料和非數值型別資料。數值型資料主要包括整數、實數和複數等；非數值型別資料報括字元、字串、文字、聲音、圖形、影象等。
3、資料結構的邏輯結構是指資料元素的集合以及定義在該集合上的資料元素之間的一種或多種特定關係。
4、資料結構的邏輯結構是根據解決問題的功能目標而建立的；
資料結構的儲存結構是根據解決問題的效能要求而建立的。
5、資料型別是乙個具體相同性質的值的集合以及定義在該集合上的一組操作的總稱。資料型別定義了資料的性質、取值範圍以及對資料所能進行的一組操作。
6、根據資料元素之間邏輯關係的不同特性，可將資料結構分為：集合、線性機構、樹形結構和圖狀結構。
7、乙個非空的線性結構的邏輯特點：1.只有乙個資料元素沒有前驅，稱其為「第乙個」元素；2.
只有乙個資料元素沒有後繼，稱其為「最後乙個」元素；3.除第乙個元素外，其餘資料元素有且只有乙個前驅；4. 除最後乙個元素外，其餘資料元素有且只有乙個後繼。
8、演算法是指為解決乙個問題而採用的方法和步驟；
9、演算法的五個特性：1.有窮性：
演算法必須在有限步驟及有限時間內終止，並計算出結果；2.確定性：演算法的每乙個操作步驟都有確切的含義，即無二義性；3.
演算法的每乙個操作步驟，都是有效的、可行的；4.輸入：乙個演算法有零個或多個輸入，這些輸入取自於某個特定物件的集合；5.
輸出：乙個演算法必須有乙個或多個輸出。演算法的目的是為了求解，通過演算法所求得的「解」即是演算法的輸出。
注意，計算機演算法的輸出不一定就是計算機顯示或列印輸出，乙個演算法得到的結果實際就是演算法的輸出。
第二章線性表
10、線性表是一種最基本而且應用最廣泛的資料結構，其特點是結構中的各資料元素之間存在著一對一的關係，是一種最典型的線性結構。
11、線性表是具有相同特性的資料元素的乙個有限序列。
12、線性表中的資料元素在位置上是有序的，相鄰的元素之間存在著序偶關係。
13、順序表的順序儲存結構是指把線性表中所有資料元素，按照其邏輯順序依次儲存到計算機儲存器中從指定位置開始的一塊連續的儲存空間中，資料元素間的儲存（物理）位置即表示了它的邏輯位置。
14、順序表基本操作的實現：1.初始化操作；2.
求長度操作；3.判空操作；4.清空操作；5.
取元素操作；6.按值查詢操作；7.插入操作；8.
刪除操作。
15、演算法的空間效率是指演算法在計算機上執行時所需儲存空間的大小。
演算法的空間複雜度用大o記法表示為：s（n）=o（f（n））
隨著問題規模n的增大，演算法執行時所需輔助儲存空間的增長率的數量級為f（n）。若演算法執行時所佔的儲存空間與問題規模無關，是個常量，則稱這種演算法為原地工作，其空間複雜度用o（1）表示。
16、順序表的優缺點：
優點：a.實現方法簡單，各種高階語言中都有陣列，容易實現；
b.訪問元素的速度快，因為在順序表中邏輯上相鄰的兩個元素在儲存位置上也必定相鄰，所以只要知道了第乙個元素的位址，其他任何乙個元素的位址都可通過簡單的計算求得，故可實現隨機訪問，即順序表l的第i個元素即為
缺點：a.需占用連續的儲存區，儲存要求高，不能利用小塊儲存區；
b.由於在順序表中邏輯上相鄰的兩個元素在儲存位置上也必定相鄰，所以在進行插入和刪除操作時，需要進行大量的元素移動操作，影響了演算法效率。
17、通常把使用鏈式儲存結構來實現的線性表稱為鍊錶。
18、線性表的鏈式儲存結構是用一組任意的儲存單元來存放線性表中的資料元素，這組儲存單元既可以是連續的，也可以是不連續的，甚至可以零散分布在記憶體中的任意位置上。
19、鍊錶的相關概念：1.首元結點，指煉表中用於儲存線性表的第一各資料元素的結點；2.
頭結點，在鍊錶中為了便於進行插入和刪除等操作，為鍊錶增設乙個輔助結點，稱該輔助結點為鍊錶的頭結點。頭結點在鍊錶中可有可無；3.頭指標，是指向鍊錶中第乙個結點的指標，可以唯一地表示乙個鍊錶；4.
空指標，當鍊表中某個結點的指標域為空時，稱該結點的指標域為空指標。
20、鍊錶的表長是指煉表中存放資料元素的結點數目。
21、鍊錶分為單鏈表、雙向鍊錶和迴圈鍊錶。
22、單鏈表的建立操作：
1.頭插法建立單鏈表：在單鏈表的建立過程中，總是將由讀入元素所生成的結點插入到鍊錶的表首端，即插入時始終將新生成結點作為第1個結點插入。
2.尾插法建立單鏈表：與頭插法正好相反，在單鏈表的建立過程中，其每次都是將所生成的新結點插入到單鏈表尾端，即在插入時始終是新生成結點作為最後乙個結點插入。
23、鍊錶的優缺點：
優點：a.能充分利用記憶體中的小塊儲存區；
b.便於進行插入和刪除操作，在進行插入和刪除操作時不需要進行元素的移動，只需修改相應結點的指標域即可。
缺點：a.與順序表相比，其實現方法較複雜，特別在對雙鏈表進行操作時不僅要考慮向後指向的「鏈」，還需考慮向前指向的「鏈」；
b.無法像順序表那樣實現隨機訪問，在鍊錶中要找某個結點只能從表頭開始向後尋找；
c.在鍊錶的每個結點需要附加儲存關係資訊（指標域），因此當問題規模較小且基本一定時，鍊錶所需儲存空間比順序表多。
第三章棧與佇列
24、棧的定義：棧是一種將插入操作與刪除操作限制在同一段進行的特殊線性表。在這個特殊的線性表中，進行插入與刪除操作的一端稱為棧頂（top），另一端則稱為棧底（bottom）。
也就是說棧的插入操作與刪除操作均在棧頂端進行，其中，插入操作稱為入棧操作（push），刪除操作稱為出棧操作（pop）。不含任何元素的棧稱為空棧。
25、棧具有後進先出或者說為先進後出的特性，故棧又稱為後進先出表或先進後出表。
26、棧的基本操作：初始化、銷毀、判空、清空、入棧、出棧、取棧頂、求棧長及遍歷。
27、經試探可行則行進，不可行則返回重新試探的方法稱為回溯法。
28、乙個概念、函式等物件用自己來定義自己，則稱該物件為遞迴定義的。在程式語言中，乙個演算法直接或間接呼叫自己，則稱該演算法為遞迴演算法。
29、遞迴法則：1.基準情形法則。
遞迴定義中的基準情形即遞迴出口，它本身不再使用遞迴定義，是遞迴的結束條件；2.不斷推進法則。不斷推進法則是指在遞迴求解過程中，每一次遞迴呼叫都必須使求解狀況朝接近基準情形的方向推進。
30、佇列是一種插入操作限制在一端進行而刪除操作限制在另一端進行的特殊線性表。在這個特殊的線性表中進行插入操作的一端成為隊尾，進行刪除操作的一端稱為隊頭。在佇列尾端進行的插入操作稱為入隊操作，而在佇列頭端進行的刪除操作稱為出隊操作。
不含任何元素的佇列稱為空隊。
31、佇列具有先進先出或者說後進後出的重要特性，故佇列又稱為先進先出表或後進後出表。
第四章串
32、串的定義：串是由零個或多個任意字元組成的有限序列，一般記作：s=「s1s2…si…sn」（n≥0）。
其中s是串名，用雙引號括起來的字串行為串值，但引號本身並不屬於串的內容，它的作用是為了避免與變數名或數的常量相混淆。si（1≤i≤n）稱為串的元素，它可以是任意字母、數字或者是其他字元，是構成串的基本單位，i是它在整個串中的序號。n為串的長度，表示串中所包含的字元個數。
例如，串s1=「abcd」，串的元素為乙個字母，其長度為5。而在串s2=「123456」，串的元素為乙個數字，其長度為6。
33、串的靜態順序儲存結構利用的是陣列的靜態分配方式，它是為每個定義的字串分配乙個固定長度的連續儲存區域，將字串中的字元順序地存放在儲存區域的各個單元裡。實質上就是將串定義成字元陣列，利用串名可以直接訪問串值。用這種表示方式，串的儲存空間在編譯時確定，其大小不能改變。
34、串的動態順序儲存結構仍是為每個定義的字串分配乙個連續儲存區域，將字串中的字元順序地存放在這組儲存區域中的各個單元裡，只是這個儲存區域不是在操作前分配的固定長度的區域，而是在操作過程中根據需要動態分配得到的，即在程式執行時為每個產生的串分配一塊實際串長所需的儲存空間，若分配成功，則返回指向該儲存空間起始位址的指標，作為串的基址。
第五章陣列和廣義表
35、陣列是n個相同資料型別的資料元素a0，a1，…，an-1構成的占用一塊位址連續的記憶體單元的有限序列。陣列中任意乙個元素可以用該元素在陣列中的位置來表示，陣列元素的位置通常稱作陣列的下標。
36、在大多數語言中採用以行序為主序的儲存方式，如c語言、c++語言和pascal語言；在fortran等少數語言中採用以列序為主序的儲存方式。
37、常見的特殊矩陣：對稱矩陣、三角矩陣和帶狀矩陣。
對稱矩陣：在乙個n階方陣a中，若元素滿足下述興致：aij=aji（1≤i，j≤n），則稱a為n階對稱矩陣。
三角矩陣：以主對角線劃分，n階三角矩陣有n階上三角矩陣和n階下三角矩陣兩種。n階上三角矩陣的下三角（不包括主對角線）中的元素均為常數c（或0）。
n階下三角矩陣正好相反，它的主對角線上方均為常數c（或0）。
帶狀矩陣：帶狀矩陣是指所有非零元素均集中在以對角線為中心的帶狀區域中的n階方陣。
38、常見的稀疏矩陣儲存方法：三元組順序表和十字鍊錶。
39、三元組順序表：將表示稀疏矩陣非零元素的三元組按行優先或列優先（一般情況下為行優先）的順序排列，並以此儲存在向量中，這種稀疏矩陣的順序儲存結構稱為三元組順序表。
40、在廣義表中，每個結點既可以屬於基本資料型別，也可以屬於廣義表型別。
41、廣義表的定義是乙個遞迴定義，它和線性表之間的不同之處在於：資料元素之間不僅有先後關係，更有元素內部的層次關係。
42、廣義表的長度是指表中資料元素的個數，需要注意的是資料元素可能是原子，也可能是子表；
廣義表的深度是指表中層次關係的最大深度，即所含括弧的重數，需要注意：「原子」深度為0，「空表」的深度為1。
43、廣義表的特性：1.廣義表是乙個多層次的結構。
表中元素可以是子表，子表的元素還可以是子表；2.廣義錶可為其他廣義表所共享。在實際應用中，利用共享特性可以節約儲存空間來；3.
廣義表可以是乙個遞迴的表。遞迴表的深度是無窮值，長度則是有限值。
湖南大學資料結構考試重點
資料結構 複習提綱 一 基礎知識 1 二 應用 5 三 演算法 5 四 題型及樣題 6 第1章緒論 1 什麼是資料結構，分類 2 抽象資料型別的形式定義 3 邏輯結構 物理結構 儲存結構 4 時間複雜度 第2章線性表 5 線性表的定義和術語 6 線性表的儲存結構 順序表鏈式表 線性鍊錶 單鏈表 迴圈...
資料結構複習提綱考試重點
一 基礎知識 第1章緒論 1 什麼是資料結構，分類 2 抽象資料型別的形式定義 3 邏輯結構 物理結構 儲存結構 4 什麼是演算法 5 時間複雜度 第2章線性表 6 線性表的定義和術語 7 線性表的儲存結構 順序錶鏈表 線性鍊錶 單鏈表 迴圈鍊錶 雙向鍊錶 第3章棧和佇列 8 棧 順序棧鏈式棧9 佇...
資料結構重點整理
2幾種資料結構 資料結構定義 具有結構的資料元素的集合 邏輯結構 集合 線性結構 線性表 廣義表 堆疊和佇列 非線性結構 樹 圖 儲存結構 順序儲存結構 鏈式儲存結構 索引結構 雜湊結構等 集合和線性結構 1 1樹形結構 1 n圖形結構 n n 3 線性表順序儲存和鏈結儲存的特點 順序儲存 隨機訪問...