1、第一章 數據結構與算法1.1 算法1、算法是指解題方案的準確而完整的描述。換句話說，算法是對特定問題求解步驟的一種描述。I=1 ，變量I賦值為1S=0 ，變量S賦值為0DO WHILE I<=100 ，循環結構，當I小于100時循環S=S+I ，對I的值累加求和I=I+1 ，變量I的值沒循環一次增加1LOOP ，循環結構，遇到loop返回DO處重新循環 MSGBOX S ，輸出求和變量S的值算法規定了解決某類問題所需的操作語句以及執行順序，使其能通過有限的指令語句，在一定時間內解決問題。算法是一個操作序列、有限長度，目的是解決某類問題。*：算法不等于程序，也不等于計算方法。程序的編制不可

2、能優于算法的設計。2、算法的基本特征（1）可行性。針對實際問題而設計的算法，執行后能夠得到滿意的結果。（2）確定性。每一條指令的含義明確，無二義性。并且在任何條件下，算法只有唯一的一條執行路徑，即相同的輸入只能得出相同的輸出。（3）有窮性。算法必須在有限的時間內完成。有兩重含義，一是算法中的操作步驟為有限個，二是每個步驟都能在有限時間內完成。（4）擁有足夠的情報。指的是有足夠的輸入和輸出。*：綜上所述，所謂算法，是一組嚴謹地定義運算順序的規則，并且每一個規則都是有效的，且是明確的，此順序將在有限的次數下終止。3、算法的基本要素一個算法通常由兩種基本要素組成：一是對數據對象的運算和操作；二是算法

3、的控制結構。(1）算法中對數據的運算和操作每個算法實際上市按解題要求從環境能進行的所有操作中選擇合適的操作所組成的一組指令序列。因此，計算機算法就是計算機能處理的操作所組成的指令序列。在一般的計算機系統中，基本的運算和操作有以下四類：算術運算：主要包括加、減、乘、除等運算；邏輯運算：主要包括與(AND)、或(OR)、非(NOT)等運算；關系運算：主要包括大于、小于、等于、不等于等運算數據傳輸：主要包括賦值、輸入、輸出等操作。(2)算法的控制結構順序、選擇和循環。4、算法的基本方法（計算機解題的過程實際上是在實施某種算法）（1）列舉法（列舉所有解決方案） 根據提出的問題，列舉所有可能的情況，并用

4、問題中給定的條件檢驗哪些是需要的，哪些是不需要的。（2）歸納法（特殊->一般）適合于列舉量為無限的情況 通過列舉少量的特殊情況，經過分析，最后找出一般的關系。（3）遞推法 （已知->未知） 從已知的初始條件出發，逐次推出所要求的各中間結果和最后結果。（4）遞歸法（逐層分解） 將一個復雜的問題歸結為若干個較簡單的問題，然后將這些較簡單的每一個問題再歸結為更簡單的問題（5）減半遞推法 “減半”是指將問題的規模減半，而問題的性質不變，所謂“遞推”是指重復“減半”的過程。（6）回溯法 復雜應用，找出解決問題的線索，然后沿著這個線索逐步多次“探”、“試”。5、算法復雜度主要包括時間復雜度和空

5、間復雜度。 算法的復雜度是衡量算法好壞的量度。（1）算法時間復雜度是指執行算法所需要的計算工作量，可以用執行算法的過程中所需基本運算的執行次數來度量。影響計算機工作量的主要因素：第一：基本運算次數； 第二：問題規模。下面的方法不能用來度量算法的時間復雜度：第一：算法程序的長度或算法程序中的語句（指令）條數；第二：算法程序所執行的語句條數；第三：算法程序執行的具體時間（2）算法空間復雜度是指執行這個算法所需要的內存空間。 一個算法所用的內存空間包括： 1）算法程序所占用的存儲空間；2）輸入的初始數據所占的存儲空間；3）算法執行過程中的額外空間。6、考題練習：1）下列敘述正確的是（） （A）算法就

6、是程序（B）算法強調的是利用技巧提高程序執行效率（C）設計算法時只需考慮結果的可靠性（D）以上三種說法都不對2）下面敘述正確的是（） （A）算法的執行效率與數據的存儲結構無關（B）算法的空間復雜度是指算法程序中指令（或語句）的條數（C）算法的有窮性是指算法必須能在執行有限個步驟之后終止（D）以上三種描述都不對3）下列敘述中正確的是（） （A）一個算法的空間復雜度大，則其時間復雜度也必定大（B）一個算法空間復雜度大，則其時間復雜度必定小（C）一個算法的時間復雜度大，則其時間復雜度必定小（D）以上三種說法都不對4）算法的空間復雜度是指（ ）（A）算法程序中變量的個數（B）算法程序中的指令條數（C）

7、算法程序中各控制變量所占的額外空間（D）算法執行過程中所需要的存儲空間1.2 數據結構的基本概念1、基本概念：1）數據：在計算機科學中是指所有能輸入到計算機中并被計算機程序處理的符號的總稱。2）數據元素：數據的基本單位，在計算機程序中通常作為一個整體進行考慮和處理。3）數據結構：是指相互有關聯的數據元素的集合。 線性表 棧 線性結構 隊列 數據的邏輯結構 樹形結構 非線性結構 圖形結構 順序存儲 數據的存儲結構 鏈式存儲 數據的運算：檢索、排序、插入、刪除、修改2、邏輯結構：數據元素之間的邏輯關系，從邏輯關系上描述數據，它與數據的存儲無關，是獨立于計算機的。3、存儲（物理）結構：是指數據元素及

8、其關系在計算機內存中的表示，即數據的邏輯結構在計算機存儲空間中的存放形式。注意：對于同一個邏輯結構來說，采用不同的存儲結構，其數據處理的效率是不同的。因此，在數據處理時，選擇合適的存儲結構很重要。各數據元素在計算機存儲空間中的位置關系與它們的邏輯關系不一定相同。由于數據元素在計算機存儲空間中的位置關系可能與邏輯關系不同，因此，為了表示存放在計算機存儲空間中的各數據元素之間的邏輯關系（即前后間關系）在數據結構中，不僅要存放各數據元素的本身，而且還需要存放各數據元素之間的前后件關系的信息。4、邏輯結構與物理結構的關系：（1）一種邏輯結構可以用不同的物理結構來實現（2）邏輯結構決定了算法的設計（3）

9、物理結構決定了算法的實現數據結構的圖形表示：表示數據結構的常用方法：二元關系表和圖形表示。例：一年四季的數據結構可以表示成：用圖形表示為：春夏秋冬1） 數據元素：用中間標有元素值的方框來表示，稱為數據結點，簡稱為結點。2） 元素之間的前后關系：用一條有向線段從前件結點指向后件結點（有時可以省略箭頭）例如：家庭成員數據結構可以表示稱為：父親女兒兒子在數據結構中，沒有前件的結點稱為根結點，沒有后件的結點稱為終端結點（也稱為葉子結點）其它的稱為內部結點。5、線性結構與非線性結構數據結構的分類：根據數據結構中各數據元素之間的前后關系的復雜度，一般將數據結構分成兩大類：線性結構和非線性結構。注意：線性結

10、構與非線性結構是在數據的邏輯結構概念下的一種劃分方法，與數據的存儲結構無關。前面說過，一種數據的邏輯結構根據需要可以表示成多種存儲結構，但只要數據的邏輯結構是屬于線性結構，則該邏輯結構的任意一種存儲結構也都屬于線性結構。6、線性結構的定義：如果一個非空的數據結構滿足下列兩個條件：（1） 有且只有一個根結點（每有前件的結點稱為根結點）（2） 每個結點最多有一個前件，也最多有一個后件。則稱該數據結構為線性結構，線性結構又稱為線性表。（3） 線性結構的操作。 在一個線性結構中插入或刪除任何一個結點后還應是線性結構。1.3 線性表及其順序存儲結構1、線性表就是線性結構。線性表由一組數據元素構成，數據元

11、素的位置只取決于自己的序號，元素之間的相對位置是線性的。線性表是由n(n0)個數據元素組成的一個有限序列，表中的每一個數據元素，除了第一個外，有且只有一個前件，除了最后一個外，有且只有一個后件2、線性表的順序存儲結構也稱為順序表。3、線性表的順序存儲結構具有兩個基本特點：（1）線性表中所有元素所占的存儲空間是連續的；（2）線性表中各數據元素在存儲空間中是按邏輯順序依次存放的，其前后兩個元素在存儲空間中是緊鄰的，且前件元素一定存儲在后件元素的前面。4、線性表的長度：是指線性表中數據元素的個數，當N=0時，稱為空表。5、通常定義一個一維數組來表示線性表的順序存儲空間，用一維數組來存放線性表時，該一

12、維數組的長度不要定義為太短，也不要定義為太長。6、順序表（線性表的順序結構）的插入運算：在一般情況下，要在第i（1in）個元素之前插入一個新元素時，首先要從最后一個（即第n個）元素開始，直到第i個元素之間共n-i+1個元素依次向后移動一個位置，移動結束后，第i個位置就被空出，然后將新元素插入到第i項。插入結束后，線性表的長度就增加了1。7、順序表的刪除運算：在一般情況下，要刪除第i（1in）個元素時，則要從第i+1個元素開始，直到第n個元素之間共n-i個元素依次向前移動一個位置。刪除結束后，線性表的長度就減小了1。*：進行順性表的刪除運算時也需要移動元素，在等概率情況下，平均需要移動（n-1）

13、/2個元素。插入、刪除運算不方便。例題：選擇正確表示線性表(A1,A2,A3,A4)的順序結構是（ ）A1A4A2A3A1A2A3A4A1A2A3A4綜上所述：線性表的順序存儲結構對于經常需要變動的大線性表就不合適了，因為插入和刪除的效率比較低。線性表的順序存儲的缺點第一、在插入和刪除時需要移動元素（除棧和隊列之外）第二、上溢（或下溢） 1.4 棧1、棧的定義：展示一種特殊的線性表，即限定在一端進行插入與刪除的線性表。2、棧頂、棧底的定義：在棧中，允許插入與刪除的一端稱為棧頂，不允許插入與刪除的另一端稱為棧底。棧頂元素總是最后被插入的元素，棧底元素總是最先被插入的元素。3、棧的操作原則：是按照

14、“先進后出”或“后進先出”的原則組織數據的。4、棧的基本運算：1）插入元素稱為入棧運算；2）刪除元素稱為退棧運算；3）讀棧頂元素是將棧頂元素賦給一個指定的變量，此時指針無變化。5、棧具有記憶功能。6、注意：1）在順序存儲結構下，棧的插入與刪除運算都不需要移動表中其他數據元素；2）在棧中，棧頂指針動態反映了棧中元素的變化情況。7、在順序結構下的讀棧頂元素是指將棧頂元素賦值給一個指定的變量。（讀不是刪除，刪除一定要先讀。在只讀的情況下，原來是多少，讀后還是多少）8、讀棧頂元素過程中應注意的問題：1）讀棧頂元素不刪除棧頂元素，只是將它的值賦給一個變量。因此在這個運算中棧頂指針不會改變；2）當棧頂指針

15、為0時，說明棧為空，讀不到棧頂元素。1.5隊列及其運算1、隊列的定義：隊列是指允許在一端（隊尾）進入插入，而在另一端（隊頭）進行刪除的線性表。2、允許插入的一端叫隊尾。尾指針（Rear）指向隊尾元素。允許刪除的一端叫對頭。頭指針（front）指向排頭元素的前一個位置（隊頭）。3、數據操作方法：隊列是“先進先出”或“后進后出”的線性表。4、隊列運算包括：1）入隊運算：從隊尾插入一個元素；2）退隊運算：從隊頭刪除一個元素。5、在順序存儲結構下，隊列的插入與刪除運算都不需要移動表中其他數據元素。6、循環隊列及其運算：所謂循環隊列，就是將隊列存儲空間的最后一個位置繞到第一個位置，形成邏輯上的環狀空間，

16、供隊列循環使用。在循環隊列中，用隊尾指針rear指向隊列中的隊尾元素，用排頭指針front指向排頭元素的前一個位置，因此，從頭指針front指向的后一個位置直到隊尾指針rear指向的位置之間，所有的元素均為隊列中的元素。7、確定循環隊列中元素個數的方法如下：設循環隊列的容量為M，如果rear>front，則循環隊列中的元素個數為rear-front；如果rear<front，則循環隊列中的元素個數為M+(rear-front)；8、循環隊列的運算有兩個：1）入隊運算：是在循環隊列的隊尾加入一個新元素，也就是rear+1；2）退隊運算：是在先能換隊列的排頭位置退出一個元素并賦給指定的

17、變量，也就是front+1。1.6 線性鏈表對于大的線性表或者變動頻繁的線性表不宜用順序存儲，應該用鏈式存儲。1、鏈式存儲方式的特點：（1）在鏈式存儲結構中，存儲數據結構的存儲空間可以是不連續的。（2）各結點的存儲順序與數據元素之間的邏輯關系可以不一致。2、線性鏈表：線性表的鏈式存儲結構稱為線性鏈表，是一種物理存儲單元上非連續、非順序的存儲結構，數據元素的邏輯順序是通過鏈表中的指針鏈接來實現的。3、線性表順序存儲的缺點：（1）插入或刪除的運算效率很低。在順序存儲的線性表中，插入或刪除數據元素時需要移動大量的數據元素；（2）線性表的順序存儲結構下，線性表的存儲空間不便于擴充；（3）線性表的順序存

18、儲結構不便于對存儲空間的動態分配。注意：線性鏈表是線性表的鏈式存儲結構；帶鏈的棧是棧的鏈式存儲結構；帶鏈的隊列是隊列的鏈式存儲結構。4、線性鏈表的存儲結點的定義：為了適應線性鏈表的鏈式存儲結構，計算機存儲空間被劃分為一個一個小塊，每個小塊占若干個字節，通常稱這些小塊為存儲結點。存儲結點=數據域+指針域頭指針：在線性鏈表中，頭指針（head）很關鍵，不的丟失。最后一個結點的指針域：線性鏈表的最后一個結點的指針域為空（用NULL或0來表示）5、在鏈式存儲方式中，每個結點由兩部分組成：一部分用于存放數據元素的值，稱為數據域；另一部分用于存放指針，稱為指針域，用于指向該結點的前一個或后一個結點（即前件

19、或后件），如下圖所示：線性鏈表分為單鏈表、雙向鏈表和循環鏈表三種類型。在單鏈表中，每一個結點只有一個指針域，由這個指針只能找到其后件結點，而不能找到其前件結點。因此，在某些應用中，對于線性鏈表中的每個結點設置兩個指針，一個稱為左指針，指向其前件結點；另一個稱為右指針，指向其后件結點，這種鏈表稱為雙向鏈表，如下圖所示：3、線性鏈表的基本運算（1）在線性鏈表中包含指定元素的結點之前插入一個新元素。*：在線性鏈表中插入元素時，不需要移動數據元素，只需要修改相關結點指針即可，也不會出現“上溢當為一個線性表分配順序存儲結構后，如果出現線性表的存儲空間已滿，但還需要插入新的元素時，就會發生“上溢”現象。”

20、現象。（2）在線性鏈表中刪除包含指定元素的結點。*：在線性鏈表中刪除元素時，也不需要移動數據元素，只需要修改相關結點指針即可。（3）將兩個線性鏈表按要求合并成一個線性鏈表。（4）將一個線性鏈表按要求進行分解。（5）逆轉線性鏈表。（6）復制線性鏈表。（7）線性鏈表的排序。（8）線性鏈表的查找。*：線性鏈表不能隨機存取在鏈表中，即使知道被訪問結點的序號i，也不能像順序表中那樣直接按序號i訪問結點，而只能從鏈表的頭指針出發，順著鏈域逐個結點往下搜索，直至搜索到第i個結點為止。因此，鏈表不是隨機存儲結構。4、循環鏈表及其基本運算在線性鏈表中，其插入與刪除的運算雖然比較方便，但還存在一個問題，在運算過程

21、中對于空表和對第一個結點的處理必須單獨考慮，使空表與非空表的運算不統一。為了克服線性鏈表的這個缺點，可以采用另一種鏈接方式，即循環鏈表。與前面所討論的線性鏈表相比，循環鏈表具有以下兩個特點：1）在鏈表中增加了一個表頭結點，其數據域為任意或者根據需要來設置，指針域指向線性表的第一個元素的結點，而循環鏈表的頭指針指向表頭結點；2）循環鏈表中最后一個結點的指針域不是空，而是指向表頭結點。即在循環鏈表中，所有結點的指針構成了一個環狀鏈。下圖a是一個非空的循環鏈表，圖b是一個空的循環鏈表：循環鏈表的優點主要體現在兩個方面：一是在循環鏈表中，只要指出表中任何一個結點的位置，就可以從它出發訪問到表中其他所有

22、的結點，而線性單鏈表做不到這一點；二是由于在循環鏈表中設置了一個表頭結點，在任何情況下，循環鏈表中至少有一個結點存在，從而使空表與非空表的運算統一。*：循環鏈表是在單鏈表的基礎上增加了一個表頭結點，其插入和刪除運算與單鏈表相同。但它可以從任一結點出發來訪問表中其他所有結點，并實現空表與非空表的運算的統一。1.6 樹與二叉樹1、樹的基本概念樹是一種簡單的非線性結構。在樹這種數據結構中，所有數據元素之間的關系具有明顯的層次特性。在樹結構中，每一個結點只有一個前件，稱為父結點。沒有前件的結點只有一個，稱為樹的根結點，簡稱樹的根。每一個結點可以有多個后件，稱為該結點的子結點。沒有后件的結點稱為葉子結點

23、。在樹結構中，一個結點所擁有的后件的個數稱為該結點的度，所有結點中最大的度稱為樹的度。樹的最大層次稱為樹的深度。結點的定義：數據元素+若干指向子樹的分支。結點的度得定義：子樹的個數，即擁有的后件個數稱為該結點的度。樹的度得定義：樹中所有結點的度的最大值。葉子結點的定義：度為零的結點，即沒有后件的結點。分支結點的定義：度大于非零的結點。結點的層次（深度）的定義：假設根結點的層次為1，第I層得結點的子樹根結點的層次為I+1。樹的深度的定義：樹中葉子結點所在的最大層次。2、二叉樹及其基本性質（1）什么是二叉樹二叉樹是一種很有用的非線性結構，它具有以下兩個特點：1）非空二叉樹只有一個根結點；2）每一個

24、結點最多有兩棵子樹，且分別稱為該結點的左子樹與右子樹。*：根據二叉樹的概念可知，二叉樹的度可以為零（葉結點）、1（只有一棵子樹）或2（有2棵子樹）。（2）二叉樹的基本性質性質1 在二叉樹的第k層上，最多有 個結點。性質2 深度為m的二叉樹最多有個 個結點。性質3 在任意一棵二叉樹中，度數為0的結點（即葉子結點）總比度為2的結點多一個。性質4 具有n個結點的二叉樹，其深度至少為 ，其中 表示取 的整數部分。3、滿二叉樹與完全二叉樹滿二叉樹：除最后一層外，每一層上的所有結點都有兩個子結點。完全二叉樹：除最后一層外，每一層上的結點數均達到最大值；在最后一層上只缺少右邊的若干結點。*：根據完全二叉樹的

25、定義可得出：度為1的結點的個數為0或1。下圖a表示的是滿二叉樹，下圖b表示的是完全二叉樹：完全二叉樹還具有如下兩個特性：性質5 具有n個結點的完全二叉樹深度為 。性質6 設完全二叉樹共有n個結點，如果從根結點開始，按層序（每一層從左到右）用自然數1，2，n給結點進行編號，則對于編號為k（k=1，2，n）的結點有以下結論：若k=1，則該結點為根結點，它沒有父結點；若k>1，則該結點的父結點的編號為INT(k/2)。若2kn，則編號為k的左子結點編號為2k；否則該結點無左子結點（顯然也沒有右子結點）。若2k+1n，則編號為k的右子結點編號為2k+1；否則該結點無右子結點。4、二叉樹的存儲結構在計算機中，二叉樹通常采用鏈式存儲結構。與線性鏈表類似，用于存儲二叉樹中各元素的存儲結點也由兩部分組成：數據域和指針域。但在二叉樹中，由于每一個元素可以有兩個后件（即兩個子結點），因此，用于存儲二叉樹的存儲結點的