1、第一章 概述一、概念： 1學科：數據結構是一門研究非數值計算的程序設計問題中計算機的操作對象 以及它們之間的關系和操作等等。2概念：由某一數據對象及該對象中所有數據成員之間的關系組成。具體來說， 數據結構包含三個方面的內容， 即數據的邏輯結構， 數據的存儲結構和對數據所 施加的運算。3這三個方面的關系為：1) 數據的邏輯結構獨立于計算機，是數據本身所固有的。2) 存儲結構也稱為物理結構，是邏輯結構在計算機存儲器中的映像，必須 依賴于計算機。3) 運算是指所施加的一組操作總稱。運算的定義直接依賴于邏輯結構，但 運算的實現必依賴于存貯結構。4數據( data) :信息的載體，指能夠輸入到計算機中，

2、并被計算機識別和處理 的符號的集合。例如：數字、字母、漢字、圖形、圖像、聲音都稱為數據。 5數據元素( data elemen)t ：數據元素是組成數據的根本單位。 數據元素是一個數據整體中相對獨立的單位。 但它還可以分割成假設干個具有不同屬性的項字段，故不是組成數據的最小單位。6 邏輯結構：從解決問題的需要出發，為實現必要的功能所建立的數據結構， 它屬于用戶的視圖，是面向對象的。7.物理結構：指數據該如何在計算機中存放，是數據邏輯結構的物理存儲方式， 是屬于具體實現的視圖，是面向計算機的。8 邏輯結構與存儲結構二者關系：物理結構是邏輯結構的存儲映象。任何一個算法的設計取決于選定的數據邏輯結構

3、，而算法的實現依賴于采用的存儲結構。9從邏輯結構劃分數據結構：線性結構和非線性結構樹、圖10. 線性結構：1元素之間為一對一的線性關系2第一個元素無直接前驅3最后一個元素無直接后繼4其余元素都有一個直接前驅和直接后繼。11. 非線性結構1元素之間為一對多或多對多的非線性關系2每個元素有多個直接前驅或多個直接后繼12 順序存儲：數據元素存儲方法：所有元素存放在一片連續的存貯單元中。 數據元素之間關系表示：邏輯上有相鄰關系的元素存放到計算機內存仍然相鄰, 即存儲位置表達了數據元素之間的關系。01且L01aL弘弘a3a3a<a$L* last5L > 1 ast066 MAXSIZE-l

4、MAXSIZE-lL. dataL->data(a)413鏈式存貯數據元素存儲方法：元素可以存放在不連續的存貯單元中。數據元素之間關系表示：邏輯上相鄰的元素存放到計算機內存后不一定是相鄰 的，因此元素之間的關系通過地址確定。bcateatmat14.算法：一個有窮的指令集，這些指令為解決某一特定任務規定了一個運算序 列。特性：輸入有0個或多個輸入輸出有一個或多個輸出處理結果 確定性每步定義都是確切、無歧義的 有窮性算法應在執行有窮步后結束 可行性每一條運算應可通過已經實現的根本運算執行有限次來實現 算法的含義與程序十分相似，但二者是有區別的。一個程序不一定滿足有窮性死 循環，另外，程序中

5、的指令必須是機器可執行的， 而算法中的指令那么無此限制。 一個算法假設用計算機語言來書寫，那么它就可以是一個程序。15算法的分析與度量：1算法的性能標準： 正確性：正確執行的功能和性能要求。 可使用性：算法能夠很方便的使用。 可讀性：便于理解、測試和修改算法。 效率：計算機資源的消耗，包括存儲和運行時間。 健壯性：檢錯、報錯及糾錯的功能。2算法的事前估計：空間復雜度和時間復雜度3算法的后期測試：在算法中的某些部位插裝時間函數time ，測定算法完成某一功能所花費的時間。16時間復雜度：一個算法執行所消耗的時間，從理論上是不能算出來的，必須 上機運行測試才能知道。 但我們不可能也沒有必要對每個算

6、法都上機測試， 只需 知道哪個算法花費的時間多， 哪個算法花費的時間少就可以了。 并且一個算法花 費的時間與算法中語句的執行次數成正比例， 哪個算法中語句執行次數多， 它花 費時間就多。一個算法中的語句執行次數稱為語句頻度或時間頻度。記作T(n)=0(f(n):表示算法中根本運算次數 T(n)是問題規模n的某個函數f(n)1)求以下算法段的語句頻度 for(i=1; i<=n; i+)for(j =1; j <=i ; j+) x=x+1;n(n 1)時間頻度T(n)=1+2+3+n=2T (n)與n2數量級相同，因此它的時間復雜度為O(n2)。2)例分析以下算法段的時間頻度及時間

7、復雜度for (i=1;i<=n ;i+ )for (j=1;j<=i;j+)for ( k=1;k<=j;k+)x=i+j-k;分析算法®1律可知時間頻度謳Tfn)=l 一( 1 +2)+( 1+2+3 比.+(1+2-3+ +n)-V (l + 2-p3d-.+Jt)丄6以7TS -2 L2Jn上由于有1/6 ST (n)/iP£l故時間復雜度為$制弓)第二章 線性表1 .線性表的定義：線性表(linear list)是n (n?0)個數據元素al, a2,an 組成的有限序列。其中n稱為數據元素的個數或線性表的長度，當n=0時稱為空表，n>0時

8、稱為非 空表。通常將非空的線性表記為(a1, a2,an),其中的數據元素ai (K i < n)是一 個抽象的符號， 其具體含義在不同情況下是不同的， 即它的數據類型可以根據具 體情況而定。2. 線性表中數據元素的關系： 元素之間為一對一的線性關系。有且僅有一個開始結點 (表頭結點 )a1 ，它沒有直接前驅，只有一個直接后繼 ; 有且僅有一個終端結點(表尾結點)an,它沒有直接后繼，只有一個直接前驅； 其它結點都有一個直接前驅和直接后繼；3. 線性表的順序存儲結構 ,也稱為順序表。 在內存中開辟一片連續存儲空間， 但該連續存儲空間的大小要大于或等于順序表 的長度。然后讓線性表中第一個元

9、素存放在連續存儲空間第一個位置， 第二個元素緊跟著第一個之后，其余依此類推。4假設線性表中元素為(al, a2,.,an)設第一個元素al的內存地址為L0C(a1)，每個元素在計算機內占 那么第i個元素ai的地址為L0C(ai)=L0C(a1)+(i-1) x d骨口. 序號內容骨口. 序號內容001a11a12a22a23a33a3i-1ai-1i-1ai-1iaiixi+1ai+1i+1ainannan-1anmaxsize-1maxsize-1d個存儲單元(其中 1 < i < n)。5.插入元素void ListI nsert_sq(Sqlist &L,i nt i

10、, i nt e) int *p,*q;if(i<1|i>L.le ngth +1) return;q=&L.elemi-1;插入位置for(p=&L.elemL.length -1;p>=q;-p ) *(p+1)=*p;*q=e;+L .len gth ; return;序號內容序號內容001ai1a12a?2a23a33a3i-1a-1i-1ai-1iaiai+1i+1a+1i+1ai+2nn-1an11maxsize-1maxsize-16刪除元素 void ListDel_sq(Sqlist &L,int i, int &e)if(i

11、<1|i>L.length) return; e=L.elemi-1;for(int j=i;j<Length ;j+)L.elemj-1=L.elemj;-L.length ;7線性表的鏈式存儲結構，也稱為鏈表。存儲方式：存儲單元可以不連續， 元素的存放順序及位置都可以以任意順序進行， 原來相鄰的元素存放到計算機內存后不一定相鄰。元素關系：為了從一個元素找下一個元素增加一個存儲下一個元素地址的指針。特點：不能像順序表一樣隨機訪問，而只能按順序訪問。 常用的鏈表有單鏈表、循環鏈表和雙向鏈表、多重鏈表等。8定義的鏈表時，假設只含有一個指向直接后繼的指針域，稱這樣的鏈表為單鏈 表

12、或線性鏈表。Datanext中data域用來存放結點本身信息，類型由具體問題而定，設定為elemtype類型, 表示某一種具體的類型。next域用來存放下一個元素地址。9.head丨I 叵(a)不帶頭結點的單鏈表he a_»lai I -I>la21 4 > (b)帶頭結點的單鏈表環帶頭結點和帝頭結點的單儲表頭指針W150|11(：qi eK. jfH.1201304O150160rc180a；180roNULL11035140130dara 域 next 域巧 I -I_7磯| V_仙 | 斗川 | T"«15單狂表比邏輯表示刪除結點的指針修改10單

13、鏈表上的插入運算p_uTi-B(b-rn可 建立新的數據結點。 找到插入位置前的結點 改變指針指向。插入結點時的指針修改11 單鏈表上的刪除運算找到刪除結點前一個結點(這 就要求有兩個指針)改變指針指向釋放結點空間刪除結點的拒針修改12棧(stack)是限制線性表中元素的插入和刪除只能在線性表的同一端進行的一出棧進棧棧頂棧底(queue)。允許種特殊線性表。允許插入和刪除的一端，為變化的一端，稱為棧頂(Top)，另一端為固定的一端，稱為棧底(Bottom)。13第1個進棧的元素在棧底 最后一個進棧的元素在棧頂 第1個出棧的元素為棧頂元素 最后一個出棧的元素為棧底元素棧是一種后進先出(Last

14、In First Out)的線性表，簡 稱為LIFO表。根據棧的定義可知，最先放入棧中元素在棧底，最后 放入的元素在棧頂，而刪除元素剛好相反，最后放入 的元素最先刪除，最先放入的元素最后刪除。13僅允許在一端進行插入，另一端進行刪除的線性表，稱為隊列 插入的一端稱為隊尾rear,允許刪除的一端稱為隊頭frort。隊列是一種先進先出First In First Out的特殊線性表，或稱FIFO表。 假設隊列中沒有任何元素，那么稱為空隊列，否那么稱為非空隊列。出隊引 幻v入隊-1I隊頭隊尾14 表尾稱作隊尾，表頭稱為隊頭； al為隊頭元素，an為隊尾元素； 在表尾插入元素操作，稱為入隊操作； 在表

15、頭刪除元素的操作，稱為出隊操作； 元素按a1,a2, a3, . an順序入隊， 第1個入隊的元素為al 最后一個入隊的元素是an 第1個出隊的元素為al 最后一個出隊的元素是an 隊列具有先進先出的特點，所以又稱為先進先出表FIFO 表15順序隊列常常會出現“假溢出現象。雖然隊列中還有一定的存儲空間，但 因為front指針與rear指針均向同一個方向移動，導致該隊列不能再進行入隊操 作。為了防止"假溢出，可以這樣規定，一旦rear指針(或front指針)指向了存儲空間的末尾位置，如果此時再進行入隊(或出隊)操作，那么將相應的指針平移到數組的起始位置， 即是將隊列假想為一個循環的環狀

16、空間，我們稱之 為循環隊列。出隊時應先判-隊是否空？ 隊空條件：q.rear = q.front不空，那么出隊。進隊時應先判隊是否滿？隊滿條件：(q.rear + 1) % maxsize) = q.fro nt不滿，那么進隊。16字符串是一種特殊的線性表，表中的元素類型剛好都是字符型的串(string)是由零個或多個字符組成的有限序列，記作s= “a1a2an其中s 為串的名字，用成對的雙引號括起來的字符序列為串的值，但兩邊的雙引 號不算串值，不包含在串中。ai(1 < i < n)可以是字母、數字或其它字符。n為串中字符的個數，稱為串的長度。空串：不含任何字符的串稱為空串，它的

17、長度n=0,記為s= “。空白串：含有一個空格的串，稱為空白串，它的長度n=1，記為s= “ 或s=“ ?。子串、主串：假設一個串是另一個串中連續的一段，那么這個串稱為另一個串的 子串，而另一個串相對于該串稱為主串。除串本身以外的子串都稱為真子串。例如，串 s1= “abcdefg，s2= “fabcdefghxyz，貝U si 為 s2 的子串，s2 相對于 si為主串。17一維數組：可以看成是一個線性表，它在計算機內是存放在一塊連續的存儲 單元中，適合于隨機查找。18.二維數組中的每一個元素 最多可有二個直接前驅和兩個直接后繼(邊界除 外)，故是一種典型的非線性結構。行優先順序 (m 個)

18、 ：也稱為低下標優先或左邊下標優先于右邊下標。(aOO a01 a02 a0n-1)(a10 ail a12 a1n-1)(aiOail ai2 aij-1 aijaij+1 a-1)(am-10 am-11 am-112 amln-1)列優先順序( n 個) ：也稱為高低標優先或右邊下標優先于左邊下標。(aOO a10 a20 am)(a01 all a21-am (a0j a1j a2j-畫ai+1j -am-1j) (aOd aln-1 a2nJ amln-1)第三章 樹1 僅有一個沒有前趨的結點稱為根結點。除根結點外其它結點都有且僅有一個 直接前驅，但可以有 O 個或多個直接后繼，這樣

19、的邏輯結構稱之為樹。樹是由n (n>0個結點組成的有限集合。假設n=0,稱為空樹；假設n>0,貝有一個特定的稱為根(root)的結點。它只有直接后繼，但沒有直接前驅。 除根結點以外的其它結點可以劃分為m (m>0)個互不相交的有限集合TO, T1,，Tm-1，每個集合Ti (i=0,1,m-1)又是一棵樹，稱為根的 子樹，每棵子樹的根結點有且僅有一個直接前驅， 但可以有 0個或多個直 接后繼。由此可知，樹的定義是一個遞歸的定義， 即樹的定義中又用到了樹的概念。 樹形表示法:廣義表:嵌套集合表示法:雙親、孩子一對關系中的直接前驅、直接后繼。祖先、子孫一對關系集合中的前驅、后繼。

20、兄弟具有相同直接前驅的數據兀素。堂兄弟具有相同前驅的數據元素。結點深度根結點的深度為1假設某結點深度為i,那么其子結點深度為i+1樹的深度空樹深度為0;非空樹深度等于子樹深度的最大值加1。結點的度結點擁有的子樹數。|葉子結點度為0的結點。分支結點度不為0的結點。樹的度樹內所有結點的度的最大值。有序樹、無序樹左右結點是否等價森林m棵互不相交的樹的集合。m=0:空集；m=1 :樹3.棵二叉樹是一個結點的有限集合，該集合或者為空，或者是由一個根結點 加上兩棵分別稱為左子樹和右子樹的、互不相交的二叉樹組成。二的豆種不口話態4.性質1假設二叉樹的層次從0開始，那么在二叉樹的第i層最多有2i個結點(i 0

21、)性質 2 深度(高度)為 k 的二叉樹最多包含的結點數為 2k-1( k>0) 性質 3 對任何一棵二叉樹 , 如果其葉結點有 n0 個, 度為 2 的非葉結點有 n2 個,那么有 no= n2 + 1定義1滿二叉樹(Full Bin ary Tree):深度為k,共有2k-1個結點。定義 2 完全二叉樹 (Complete Binary Tree)假設設二叉樹的深度為k，除第k層外，其它各層(0 k-1)的結點數都到達 最大個數,即 k-1 層是滿二叉樹,第 k 層從右向左連續缺假設干結點,這就是完 全二叉樹。性質 4 具有 n 個結點的完全二叉樹的深度為 int(log2n)+1。

22、性質5有n個結點的完全二叉樹，結點從0順序標號：假設 i>0， i 的雙親結點是 (i-1)/2。假設2i+1<n，i的左孩子是2i+1;否那么i無左孩子。假設2i+2<n，i的右孩子是2i+2;否貝U i無右孩子。 假設i為偶數,且i != 0 ,貝U其左兄弟為i-1,假設i為奇數,且i != n-1 ,那么 其右兄弟為 i+1 。5樹轉換成二叉樹1) 在相鄰兄弟之間連線。2) 指抹掉雙親與除左孩子外其它孩子之間的連線。3) 只需將樹作適當的旋轉。6森林轉換成二叉樹使第 n 棵樹接入到第 n-1 棵的右邊并成為它的右子樹，第 n-1 棵二叉樹接入到 第n-2棵的右邊并成為它

23、的右子樹，第2棵二叉樹接入到第1棵的右邊并成 為它的右子樹，直到最后剩下一棵二叉樹為止。7“遍歷是任何類型均有的操作，對線性結構而言，只有一條搜索路徑(因為每個結點均只有一個后繼 )，故不需要另加討論。二叉樹是非線性結構， 每個結點有兩個后繼， 那么存在如何遍歷即按什么樣的搜索 路徑進行遍歷的問題。“訪問指對結點施行某種操作，含義可以很廣，如輸出結點信息、修改結點的 數據值等。遍歷是樹結構插入、刪除、修改、查找和排序運算的前提，是二叉樹一切運算的 根底和核心。8樹的遍歷就是按某種次序訪問樹中的結點，要求每個結點訪問一次且僅訪問 一次。設訪問根結點記作V遍歷根的左子樹記作L遍歷根的右子樹記作R那

24、么可能的遍歷次序有6種先左后右：前序VLR中序LVR后序LRV先右后左：VRLRVLRLV9. 先(根)序的遍歷：假設二叉樹為空樹，那么空操作；否那么,(1) 訪問根結點；(2) 先序遍歷左子樹；(3) 先序遍歷右子樹。遍歷結果：-+ a * b - c d / e f10. 中(根)序遍歷：假設二叉樹為空樹，那么空操作；否那么,(1) 中序遍歷左子樹；(2) 訪問根結點；(3) 中序遍歷右子樹。遍歷結果：a + b*c-d-e/f11. 后(根)序遍歷假設二叉樹為空樹，那么空操作；否那么,(1) 后序遍歷左子樹；(2) 后序遍歷右子樹；(3) 訪問根結點。遍歷結果：abcd-* + ef/-

25、12. 二叉樹的順序存儲27一般二叉樹 的順序農示憲仝二又樹的】幀序表示13. 二叉樹的鏈式存儲rootrootroot二叉樹二叉鏈表三叉鏈表14.二叉鏈表的靜態存儲結構A-11-""1B023C1-1D145E3-1-1F3'1-1 |data parent leftChild rightChild15.二叉樹的建立：A B C D E G F 16.由二叉樹的前序序列和中序序列可唯一地確定一棵二叉樹例先根序列 ABHFDECKG 和中根序列 HBDFAEKCG ,構造二叉樹:(AEHFDECKG Hr;DFA-KCG1先序序列：abcdefg中序序列：cbdae

26、gf2中序序列：DBAEKCF 后序序列：DBKEFCA3一棵二叉樹的中序遍歷結果為DBHEAFICG后序遍歷結果為 DHEBIFGC,畫出該二叉樹及寫出其前序遍歷結果。17. 在一棵樹中，從一個結點往下可以到達的孩子或子孫結點之間的通路，稱為 路徑。路徑長度：路徑中經過的分支數目。假設規定根結點的層數為1,那么從根結點到第L層結點的路徑長度為L-1 0樹的路徑長度：等于從樹的根結點到樹中各個結點的路徑長度之和。18. 結點的權：假設將樹中結點賦給一個有著某種含義的數值，那么這個數值稱為該 結點的權。結點的帶權路徑長度：從根結點到該結點之間的路徑長度與該結點的權的乘積。 樹的帶權路徑長度：樹中

27、所有葉子結點的帶權路徑長度之和。19. 哈夫曼樹是帶權路徑長度到達最小的擴充二叉樹。通過分析權值確定的4個葉子組成的樹情況，我們知道哈夫曼樹中權值分配具有 如下特點：權值越大的結點離根結點越近；權值越小的結點離根結點越遠。20. 如何構造哈夫曼樹思路：讓權值小的結點盡量做為子樹的葉子。構造包含n個葉子結點的哈夫曼樹(1) 設n個權值分別為 w1,w2,wn；(2) 將w1,w2,wn看成是有n棵樹的森林(每棵樹僅有一個結點)；3在森林中選出兩個根結點的權值最小的樹合并，作為一棵新樹的左、右子 樹，且新樹的根結點權值為其左、右子樹根結點權值之和；4從森林中刪除組合成新樹的兩棵樹，并將新樹參加森林

28、；5重復34步，直到森林中只剩一棵樹為止，該樹即為我們所求的哈夫 曼樹。權值 W= 3, 6, 2, 11, 8 對給定的一組權值：7，18，3, 32, 5, 26，12，8，試構造相應的哈夫曼樹, 并求出其帶權路徑長度 wpl是多少？第四章 圖1圖是：由一個非空有限集合的頂點集V ；一個有限邊集 E 構成的數據結構。圖是由頂點集合(vertex)及頂點間的關系集合組成的一種數據結構.邊是頂點的無序對或有序對。 表達的數據之間的邏輯關系是多對多。2. 具有n個頂點，n(n-1)/2條邊的圖，稱為完全無向圖。具有n個頂點，n(n-1)條 弧的有向圖，稱為完全有向圖。完全無向圖和完全有向圖都稱為

29、完全圖。如果 (u, v) 是 E(G) 中的一條邊，那么稱 u 與 v 互為鄰接頂點。 頂點的度是與它相關聯的邊的條數，記作 TD(v)。在有向圖中 , 頂點的度等于該頂點的入度與出度之和：頂點 v 的入度是以 v 為 終點的有向邊的條數，記作ID(v)。頂點v的出度是以v為始點的有向邊的條 數, 記作 OD(v)3. 圖的鄰接矩陣存儲：記錄各個頂點信息的頂點表，表示各個頂點之間關系的 鄰接矩陣。養<k/A1/BJ/D4/E0A00100101B110001i2C26001013D30010014E41100005F5011100無向圖鄰接矩陣是對稱矩陣。矩陣中1的個數的一半為圖中邊的

30、數目；頂點V的度等于二維數組對應行列中 1的個數；判斷兩頂點V、u是否為鄰接點，只需判二維數組對應分量是否為1；圖占用存儲空間只與它的頂點數有關，與邊數無關。Tim邊集a/A1/B3/D4/EaA001010iB1001002C2000013D3001004"e'41"'1b"o'"0矩陣不一定是對稱的。第i行中1的個數為頂點i的出度； 第i列中1的個數為頂點i的入度； 矩陣中1的個數為圖中弧的數目；很容易判斷頂點i和頂點j是否有弧相連。4 鄰接表存儲54 3 2104 3 2 1 0FEcwA1u二In-AI卜IJ>1*1

31、hA1hF>A1J11A有向圖的十字鏈表存儲匱點偵麼擁何托豺竦daDfinis IIIrS-nnt持計域LldlTHbEUhTXUL&hl i nkdmk5從已給的連通圖中某一頂點出發，沿著一 些邊訪遍圖中所有的頂點， 且使每 個頂點僅被訪問一次，就叫做圖的遍歷 ( Graph Traversal )。深度優先搜索DFS (Depth First Search)：連通圖的深度優先搜索遍歷：從圖 中某個頂點 V0 出發，訪問此頂點，然后 依次從 V0 的各個未被訪問的鄰接 點出發深度優先搜索 遍歷圖，直至圖中所有和 V0 有路徑相通的頂點都被訪 問到。廣度優先搜索BFS (Breadth First Search)從圖中的某個頂點 V0出發，并在 訪問此頂點之后依次訪問 V0 的所有未被訪問過的鄰接點；之后按這些頂點 被訪問的先后次序依次訪問它們的鄰接點，直至圖中所有和 V0 有路徑相通 的頂點都被訪問到。圖中可能存在