數(shù)據(jù)結(jié)構(gòu)知識點全面總結(jié)—精華

1、第1章緒論內(nèi)容提要： 數(shù)據(jù)結(jié)構(gòu)研究的內(nèi)容。針對非數(shù)值計算的程序設(shè)計問題，研究計算機的操作對象以及它們之間的關(guān)系和操作。數(shù)據(jù)結(jié)構(gòu)涵蓋的內(nèi)容： 基本概念：數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)對象、數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)類型、抽象數(shù)據(jù)類型。數(shù)據(jù)一一所有能被計算機識別、存儲和處理的符號的集合。數(shù)據(jù)元素一一是數(shù)據(jù)的基本單位，具有完整確定的實際意義。數(shù)據(jù)對象一一具有相同性質(zhì)的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個子集。數(shù)據(jù)結(jié)構(gòu)一一是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合，表示為：Data_Structure=（D,R）數(shù)據(jù)類型一一是一個值的集合和定義在該值上的一組操作的總稱。抽象數(shù)據(jù)類型一一由用戶定義的一個數(shù)學模型與定義在該模型上

2、的一組操作，它由基本的數(shù)據(jù)類型構(gòu)成。 算法的定義及五個特征。算法一一是對特定問題求解步驟的一種描述，它是指令的有限序列，是一系列輸入轉(zhuǎn)換為輸出的計算步驟。算法的基本特性：輸入、輸出、有窮性、確定性、可行性 算法設(shè)計要求。正確性、可讀性、健壯性、效率與低存儲量需求 算法分析。時間復雜度、空間復雜度、穩(wěn)定性學習重點： 數(shù)據(jù)結(jié)構(gòu)的“三要素”：邏輯結(jié)構(gòu)、物理（存儲）結(jié)構(gòu)及在這種結(jié)構(gòu)上所定義的操作（運算）。 用計算語句頻度來估算算法的時間復雜度。第二章線性表內(nèi)容提要： 線性表的邏輯結(jié)構(gòu)定義，對線性表定義的操作。線性表的定義：用數(shù)據(jù)元素的有限序列表示 線性表的存儲結(jié)構(gòu)：順序存儲結(jié)構(gòu)和鏈式存儲結(jié)構(gòu)。順序存儲

3、定義：把邏輯上相鄰的數(shù)據(jù)元素存儲在物理上相鄰的存儲單元中的存儲結(jié)構(gòu)。鏈式存儲結(jié)構(gòu)：其結(jié)點在存儲器中的位置是隨意的，即邏輯上相鄰的數(shù)據(jù)元素在物理上丕二定相鄰。通過指針來實現(xiàn)! 線性表的操作在兩種存儲結(jié)構(gòu)中的實現(xiàn)。數(shù)據(jù)結(jié)構(gòu)的基本運算：修改、插入、刪除、查找、排序1)修改一一通過數(shù)組的下標便可訪問某個特定元素并修改之。核心語句：Vi=x;順序表修改操作的時間效率是0(1)2)插入一一在線性表的第i個位置前插入一個元素實現(xiàn)步驟：將第n至第i位的元素向后移動一個位置；將要插入的元素寫到第i個位置；表長加1。注意：事先應(yīng)判斷：插入位置i是否合法？表是否已滿？應(yīng)當符合條件：1wiWn+1或i=1,n+1核心

4、語句：for(j=n;j>=i;j-)aj+1=aj;ai=x;n+;插入時的平均移動次數(shù)為：n(n+1)/2+(n+1)=n/20(n)3)刪除一一刪除線性表的第i個位置上的元素實現(xiàn)步驟：將第i+1至第n位的元素向前移動一個位置；表長減1。注意：事先需要判斷，刪除位置i是否合法？應(yīng)當符合條件：1wiwn或i=1,n核心語句：for(j=i+1;j<=n;j+)aj-1=aj;n-;順序表刪除一元素的時間效率為：T(n)=(n-1)/2/O(n)順序表插入、刪除算法的平均空間復雜度為O(1)單鏈表：(1)用單鏈表結(jié)構(gòu)來存放26個英文字母組成的線性表(a,b,c,，z),請寫出C語言

5、程序。#include<>#include<>typedefstructnodechardata;structnode*next;node;node*p,*q,*head;d1,c2.d2,則行優(yōu)先存儲時的地址公式為：二維數(shù)組列優(yōu)先存儲的通式為: 稀疏矩陣(含特殊矩陣)的存儲及運算。稀疏矩陣：矩陣中非零元素白個數(shù)較少(一般小于5%)學習重點： 線性表的邏輯結(jié)構(gòu)，指線性表的數(shù)據(jù)元素間存在著線性關(guān)系。在順序存儲結(jié)構(gòu)中，元素存儲的先后位置反映出這種線性關(guān)系,而在鏈式存儲結(jié)構(gòu)中，是靠指針來反映這種關(guān)系的。 順序存儲結(jié)構(gòu)用一維數(shù)組表示，給定下標，可以存取相應(yīng)元素，屬于隨機存取的存

6、儲結(jié)構(gòu)。 鏈表操作中應(yīng)注意不要使鏈意外“斷開”。因此，若在某結(jié)點前插入一個元素，或刪除某元素，必須知道該元素的前驅(qū)結(jié)點的指針。 掌握通過畫出結(jié)點圖來進行鏈表(單鏈表、循環(huán)鏈表等)的生成、插入、刪除、遍歷等操作。 數(shù)組(主要是二維)在以行序/列序為主的存儲中的地址計算方法。 稀疏矩陣的三元組表存儲結(jié)構(gòu)。 稀疏矩陣的十字鏈表存儲方法。補充重點：1 .每個存儲結(jié)點都包含兩部分：數(shù)據(jù)域和指針域(鏈域)2 .在單鏈表中，除了首元結(jié)點外，任一結(jié)點的存儲位置由其直接前驅(qū)結(jié)點的鏈域的值指示。3 .在鏈表中設(shè)置頭結(jié)點有什么好處？頭結(jié)點即在鏈表的首元結(jié)點之前附設(shè)的一個結(jié)點，該結(jié)點的數(shù)據(jù)域可以為空，也可存放表長度等

7、附加信息,其作用是為了對鏈表進行操作時，可以對空表、非空表的情況以及對直元結(jié)點進行統(tǒng)一處理,編程更方便。4 .如何表不空表？(1)無頭結(jié)點時，當頭指針的值為空時表示空表；(2)有頭結(jié)點時，當頭結(jié)點的指針域為空時表示空表。5 .鏈表的數(shù)據(jù)元素有兩個域，不再是簡單數(shù)據(jù)類型，編程時該如何表示？因每個結(jié)點至少有兩個分量，且數(shù)據(jù)類型通常不一致，所以要采用結(jié)構(gòu)數(shù)據(jù)類型。(x)計算變量x的長度(字節(jié)數(shù))；malloc(m)開辟m字節(jié)長度的地址空間，并返回這段空間的首地址；free(p)釋放指針p所指變量的存儲空間，即徹底刪除一個變量。7 .鏈表的運算效率分析：(1)查找因線性鏈表只能順序存取，即在查找時要從

8、頭指針找起，查找的時間復雜度為O(n)。(2)插入和刪除因線性鏈表不需要移動元素，只要修改指針，一般情況下時間復雜度為O(1)。但是，如果要在單鏈表中進行前插或刪除操作，因為要從頭查找前驅(qū)結(jié)點，所耗時間復雜度將是O(n)。例：在n個結(jié)點的單鏈表中要刪除已知結(jié)點*P,需找到它的前驅(qū)結(jié)點的地址，其時間復雜度為O(n)8 .順序存儲和鏈式存儲的區(qū)別和優(yōu)缺點？順序存儲時，邏輯上相鄰的數(shù)據(jù)元素，其物理存放地址也相鄰。順序存儲的優(yōu)點是存儲密度大，存儲空間利用率高；缺點是插入或刪除元素時不方便。鏈式存儲時，相鄰數(shù)據(jù)元素可隨意存放，但所占存儲空間分兩部分，一部分存放結(jié)點值，另一部分存放表示結(jié)點間關(guān)系的指針。鏈

9、式存儲的優(yōu)點是插入或刪除元素時很方便，使用靈活。缺點是存儲密度小，存儲空間利用率低。 順序表適宜于做查找這樣的靜態(tài)操作; 鏈表宜于做插入、刪除這樣的動態(tài)操作。 若線性表的長度變化不大，且其主要操作是查找，則采用順序表； 若線性表的長度變化較大，且其主要操作是插入、刪除操作，則采用鏈表。9 .判斷：“數(shù)組的處理比其它復雜的結(jié)構(gòu)要簡單”，對嗎？答：對的。因為一一數(shù)組中各元素具有統(tǒng)一的類型;數(shù)組元素的下標一般具有固定的上界和下界，即數(shù)組一旦被定義，它的維數(shù)和維界就不再改變。數(shù)組的基本操作比較簡單,除了結(jié)構(gòu)的初始化和銷毀之外，只有存取元素和修改元素值的操作。10 .三元素組表中的每個結(jié)點對應(yīng)于稀疏矩陣

10、的一個非零元素，它包含有三個數(shù)據(jù)項，分別表示該元素的行下標、列下標和元素值。11 .寫出右圖所示稀疏矩陣的壓縮存儲形式。解：介紹3種存儲形式。法1:用線性表表示：(1,2,12),(1,3,9),(3,1,-3),(3,5,14),(4,3,24),(5,2,18),(6,1,15),(6,4,-7)法2:用十字鏈表表示用途：方便稀疏矩陣的加減運算方法：每個非0元素占用5個域法3:用三元組矩陣表示：稀疏矩陣壓縮存儲的缺點：將失去隨機存取功能代碼：1 .用數(shù)組V來存放26個英文字母組成的線性表(a,b,c,，z),寫出在順序結(jié)構(gòu)上生成和顯示該表的C語言程序。charV30;voidbuild()

11、base=(QElemType*)malloc(sizeof(QElemType)*QUEUE_MAXSIZE;base=(QElemType*)malloc(sizeof(QElemType)*QUEUE_MAXSIZE);rear+1)%QUEUE_MAXSIZE;=e;什么要設(shè)計隊列？它有什么獨特用途？離散事件的模擬(模擬事件發(fā)生的先后順序，例如CPU芯片中的指令譯碼隊列)；操作系統(tǒng)中的作業(yè)調(diào)度(一個CPU行多個作業(yè))；簡化程序設(shè)計。3 .什么叫“假溢出”？如何解決？答：在順序隊中，當尾指針已經(jīng)到了數(shù)組的上界，不能再有入隊操作，但其實數(shù)組中還有空位置，這就叫“假溢出”-解決假溢出的途徑采

12、用循環(huán)隊列。4 .在一個循環(huán)隊列中，若約定隊首指針指向隊首元素的前一個位置。那么，從循環(huán)隊列中刪除一個元素時，其操作是先移動隊首位置,后取出元素。5 .線性表、棧、隊的異同點：相同點：邏輯結(jié)構(gòu)相同，都是線性的；都可以用順序存儲或鏈表存儲；棧和隊列是兩種特殊的線性表，即受限的線性表(只是對插入、刪除運算加以限制)。不同點：運算規(guī)則不同：線性表為隨機存??；而棧是只允許在一端進行插入和刪除運算，因而是后進先出表LIFO;隊列是只允許在一端進行插入、另一端進行刪除運算，因而是先進先出表FIFO。用途不同，線性表比較通用；堆棧用于函數(shù)調(diào)用、遞歸和簡化設(shè)計等；隊列用于離散事件模擬、OS乍業(yè)調(diào)度和簡化設(shè)計等

13、。第四章串內(nèi)容提要：串是數(shù)據(jù)元素為字符的線性表，串的定義及操作。串即字符串，是由零個或多個字符組成的有限序列，是數(shù)據(jù)元素為單個字符的特殊線性表。串比較：intstrcmp(char*s1,char*s2);求串長：intstrlen(char*s);串連接：charstrcat(char*to,char*from)子串T定位：charstrchr(char*s,char*c);串的存儲結(jié)構(gòu)，因串是數(shù)據(jù)元素為字符的線性表，所以存在“結(jié)點大小”的問題。模式匹配算法。串有三種機內(nèi)表示方法：模式匹配算法：算法目的：確定主串中所含子串第一次出現(xiàn)的位置(定位)定位問題稱為串的模式匹配，典型函數(shù)為Index

14、(S,T,pos)BF算法的實現(xiàn)一即編寫Index(S,T,pos)函數(shù)BF算法設(shè)計思想：將主串S的第pos個字符和模式T的第1個字符比較，若相等，繼續(xù)逐個比較后續(xù)字符；若不等，從主串S的下一字符(pos+1)起，重新與T第一個字符比較。直到主串S的一個連續(xù)子串字符序列與模式T相等。返回值為S中與T匹配的子序列第一個字符的序號，即匹配成功。否則，匹配失敗，返回值0。IntIndex_BP(SStringS,SStringT,intpos)串和空白串有無區(qū)別？答：有區(qū)別?？沾?NullString)是指長度為零的串；而空白串(BlankString),是指包含一個或多個空白字符(空格鍵)的字符串

15、.2.“空串是任意串的子串；任意串的真子串。”S都是S本身的子串，除S本身外，S的其他子串稱為S第六章樹和二叉樹內(nèi)容提要： 樹是復雜的非線性數(shù)據(jù)結(jié)構(gòu)，樹，二叉樹的遞歸定義，基本概念，術(shù)語。樹：由一個或多個（n>0）結(jié)點組成的有限集合T,有且僅有一個結(jié)點稱為根（root），當n>1時，其余的結(jié)點分為m（nr>0）個互不相交的有限集合T1,T2,，Tm每個集合本身又是棵樹，被稱作這個根的子樹。二叉樹：是n（n>0）個結(jié)點的有限集合，由一個根結(jié)點以及兩棵互不相交的、分別稱為左子樹和右子樹的二叉樹組成。術(shù)語：P88 二叉樹的性質(zhì)，存儲結(jié)構(gòu)。性質(zhì)1:在二叉機勺第i層上至多有2i-

16、1個結(jié)點（i>0）。性質(zhì)2:深度為k的二叉樹至多有2k-1個結(jié)點（k>0）。性質(zhì)3:對于任何一棵二叉樹，若2度的結(jié)點數(shù)有n2個，則葉子數(shù)（n0）必定為n2+1性質(zhì)4:具有n個結(jié)點的完全二叉樹的深度必為性質(zhì)5:對完全二叉樹，若從上至下、從左至右編號，則編號為i的結(jié)點，其左孩子編號必為2i,其右孩子編號為2i+1;其雙親的編號必為i/2（i=1時為根，除外）。二叉樹的存儲結(jié)構(gòu)：一、順序存儲結(jié)構(gòu)按二叉樹的結(jié)點“自上而下、從左至右”編號，用一組連續(xù)的存儲單元存儲。若是完全/滿二叉樹則可以做到唯一復原。不是完全二叉樹：一律轉(zhuǎn)為完全二叉樹！方法很簡單，將各層空缺處統(tǒng)統(tǒng)補上“虛結(jié)點”，其內(nèi)容為空

17、。缺點：浪費空間；插入、刪除不便二、鏈式存儲結(jié)構(gòu)用二叉鏈表即可方便表示。一般從根結(jié)點開始存儲。優(yōu)點：不浪費空間；插入、刪除方便 二叉樹的遍歷。指按照某種次序訪問二叉樹的所有結(jié)點，并且每個結(jié)點僅訪問一次，得到一個線性序列。遍歷規(guī)則二叉樹由根、左子樹、右子樹構(gòu)成，定義為D、L、R若限定先左后右，則有三種實現(xiàn)方案：DLR先序遍歷LDRLRD中序遍歷后序遍歷樹的存儲結(jié)構(gòu)，樹、森林的遍歷及和二叉樹的相互轉(zhuǎn)換?；仡?:二叉樹怎樣還原為樹？要點：逆操作，把所有右孩子變?yōu)樾值?！討?:森林如何轉(zhuǎn)為二叉樹？法一：各森林先各自轉(zhuǎn)為二叉樹；依次連到前一個二叉樹的右子樹上。法二：森林直接變兄弟，再轉(zhuǎn)為二叉樹討論2:二

18、叉樹如何還原為森林？要點：把最右邊的子樹變?yōu)樯?，其余右子樹變?yōu)樾值軜浜蜕值拇鎯Ψ绞剑簶溆腥N常用存儲方式：雙親表示法孩子表示法孩子一兄弟表示法問：樹-二叉樹的“連線一抹線一旋轉(zhuǎn)”如何由計算機自動實現(xiàn)？答：用“左孩子右兄弟”表示法來存儲即可。存儲的過程就是樹轉(zhuǎn)換為二叉樹的過程！樹、森林的遍歷：先根遍歷：訪問根結(jié)點；依次先根遍歷根結(jié)點的每棵子樹。后根遍歷：依次后根遍歷根結(jié)點的每棵子樹；訪問根結(jié)點。討論：樹若采用“先轉(zhuǎn)換，后遍歷”方式，結(jié)果是否一樣？1 .樹的先根遍歷與二叉樹的先序遍歷相同；2 .樹的后根遍歷相當于二叉樹的中序遍歷；3 .樹沒有中序遍歷，因為子樹無左右之分。先序遍歷若森林為空，返

19、回；訪問森林中第一棵樹的根結(jié)點；先根遍歷第一棵樹的根結(jié)點的子樹森林；先根遍歷除去第一棵樹之后剩余的樹構(gòu)成的森林。中序遍歷若森林為空，返回；中根遍歷森林中第一棵樹的根結(jié)點的子樹森林；訪問第一棵樹的根結(jié)點；中根遍歷除去第一棵樹之后剩余的樹構(gòu)成的森林。 二叉樹的應(yīng)用：哈夫曼樹和哈夫曼編碼。Huffman樹：最優(yōu)二叉樹(帶權(quán)路徑長度最短的樹)Huffman編碼：不等長編碼。樹的帶權(quán)路徑長度：(樹中所有葉子結(jié)點的帶權(quán)路徑長度之和)構(gòu)造Huffman樹的基本思想：權(quán)值大的結(jié)點用短路徑，權(quán)值小的結(jié)點用長路徑。構(gòu)造Huffman樹的步驟(即Huffman算法)：(1)由給定的n個權(quán)值w1,w2,，wn構(gòu)成n棵

20、二叉樹的集合F=T1,T2,，Tn(即森林)，其中每棵二叉樹Ti中只有一個帶權(quán)為wi的根結(jié)點，其左右子樹均空。(2)在F中選取兩棵根結(jié)點權(quán)值最小的樹做為左右子樹構(gòu)造一棵新的二叉樹，且讓新二叉樹根結(jié)點的權(quán)值等于其左右子樹的根結(jié)點權(quán)值之和。(3)在F中刪去這兩棵樹，同時將新得到的二叉樹加入F中。(4)重復(2)和(3),直到F只含一棵樹為止。這棵樹便是Huffman樹。具體操作步驟：學習重點：(本章內(nèi)容是本課程的重點) 二叉樹性質(zhì)及證明方法，并能把這種方法推廣到K叉樹。 二叉樹遍歷，遍歷是基礎(chǔ)，由此導出許多實用的算法，如求二叉樹的高度、各結(jié)點的層次數(shù)、度為0、1、2的結(jié)點數(shù)。 由二叉樹遍歷的前序和

21、中序序列或后序和中序序列可以唯一構(gòu)造一棵二叉樹。由前序和后序序列不能唯一確定一棵二叉樹。 完全二叉樹的性質(zhì)。 樹、森林和二叉樹間的相互轉(zhuǎn)換。 哈夫曼樹的定義、構(gòu)造及求哈夫曼編碼。補充：1 .滿二叉樹和完全二叉樹有什么區(qū)別？答：滿二叉樹是葉子一個也不少的樹，而完全二叉樹雖然前k-1層是滿的，但最底層卻允許在右邊缺少連續(xù)若干個結(jié)點。滿二叉樹是完全二叉樹的一個特例。2 .Huffman樹有什么用？最小冗余編碼、信息高效傳輸?shù)谄哒聢D內(nèi)容提要：圖的定義，概念、術(shù)語及基本操作。圖：記為G=（V,E）其中：V是G的頂點集合，是有窮非空集;E是G的邊集合，是有窮集。術(shù)語：見課件圖的存儲結(jié)構(gòu)。1 .鄰接矩陣（數(shù)

22、組）表示法建立一個頂點表和一個鄰接矩陣設(shè)圖A=（V,E）有n個頂點，則圖的鄰接矩陣是一個二維數(shù)組nn。注：在有向圖的鄰接矩陣中，第i行含義：以結(jié)點vi為尾的?。闯龆冗叄?；第i列含義：以結(jié)點vi為頭的?。慈攵冗叄｀徑泳仃嚪▋?yōu)點：容易實現(xiàn)圖的操作，如：求某頂點的度、判斷頂點之間是否有邊（?。┱翼旤c的鄰接點等等。鄰接矩陣法缺點：n個頂點需要n*n個單元存儲邊（?。豢臻g效率為O（n2）。2 .鄰接表（鏈式）表示法對每個頂點vi建立一個單鏈表，把與vi有關(guān)聯(lián)的邊的信息（即度或出度邊）鏈接起來，表中每個結(jié)點都設(shè)為3個域：每個單鏈表還應(yīng)當附設(shè)一個頭結(jié)點（設(shè)為2個域），存vi信息；每個單鏈表的頭結(jié)點另

23、外用順序存儲結(jié)構(gòu)存儲。鄰接表的優(yōu)點：空間效率高；容易尋找頂點的鄰接點；鄰接表的缺點：判斷兩頂點間是否有邊或弧，需搜索兩結(jié)點對應(yīng)的單鏈表，沒有鄰接矩陣方便。圖的遍歷。遍歷定義：從已給的連通圖中某一頂點出發(fā)，沿著一些邊，訪遍圖中所有的頂點，且使每個頂點僅被訪問一次，就叫做圖的遍歷，它是圖的基本運算。圖常用的遍歷：一、深度優(yōu)先搜索；二、廣度優(yōu)先搜索深度優(yōu)先搜索（遍歷）步驟：訪問起始點v;若v的第1個鄰接點沒訪問過，深度遍歷此鄰接點；若當前鄰接點已訪問過，再找v的第2個鄰接點重新遍歷?；舅枷耄阂灰环聵涞南刃虮闅v過程。廣度優(yōu)先搜索（遍歷）步驟：在訪問了起始點v之后，依次訪問v的鄰接點；然后再依次（順序

24、）訪問這些點（下一層）中未被訪問過的鄰接點；直到所有頂點都被訪問過為止。圖的應(yīng)用（最小生成樹，最短路經(jīng)）最小生成樹（MST的性質(zhì)如下：若U集是V的一個非空子集，若（u0,v0）是一條最小權(quán)值的邊，其中u0UI,v0V-U;則：（u0,v0）必在最小生成樹上。求MST最常用的是以下兩種：Kruskal（克魯斯卡爾）算法、Prim（普里姆）算法Kruskal算法特點：將邊歸并，適于求稀疏網(wǎng)的最小生成樹。Prime算法特點：將頂點歸并，與邊數(shù)無關(guān)，適于稠密網(wǎng)。在帶權(quán)有向圖中A點（源點）到達B點（終點）的多條路徑中，尋找一條各邊權(quán)值之和最小的路徑，即最短路徑。兩種常見的最短路徑問題：一、單源最短路徑一

25、用Dijkstra（迪杰斯特拉）算法二、所有頂點間的最短路徑一用Floyd（弗洛伊德）算法一、單源最短路徑（Dijkstra算法）一頂點到其余各頂點（v0fj）目的：設(shè)一有向圖G=（V,E）,已知各邊的權(quán)值，以某指定點v0為源點，求從v0到圖的其余各點的最短路徑。限定各邊上的權(quán)值大于或等于0。二、所有頂點之間的最短路徑可以通過調(diào)用n次Dijkstra算法來完成，還有更簡單的一個算法：Floyd算法（自學）。學習重點：圖是應(yīng)用最廣泛的一種數(shù)據(jù)結(jié)構(gòu)，本章也是這門課程的重點?；靖拍钪?，連通分量，生成樹，鄰接點是重點。 連通圖：在無向圖中,若從頂點v1到頂點v2有路徑，則稱頂點v1與v2是連通的。如

26、果圖中任意一對頂點都是連通的，則稱此圖是連通圖。非連通圖的極大連通子圖叫做連通分量。 生成樹：是一個極小連通子圖，它含有圖中全部n個頂點，但只有n-1條邊。 鄰接點：若（u,v）是E（G）中的一條邊，則稱u與v互為鄰接頂點。 圖是復雜的數(shù)據(jù)結(jié)構(gòu)，也有順序和鏈式兩種存儲結(jié)構(gòu)：數(shù)組表示法（重點是鄰接距陣）和鄰接表。這兩種存儲結(jié)構(gòu)對有向圖和無向圖均適用 圖的遍歷是圖的各種算法的基礎(chǔ)，應(yīng)熟練掌握圖的深度、廣度優(yōu)先遍歷。 連通圖的最小生成樹不是唯一的，但最小生成樹邊上的權(quán)值之和是唯一的。應(yīng)熟練掌握prim和kruscal算法，特別是手工分步模擬生成樹的生成過程。 從單源點到其他頂點，以及各個頂點間的最短

27、路徑問題，掌握熟練手工模擬。補充：1 .問：當有向圖中僅1個頂點的入度為0,其余頂點的入度均為1,此時是何形狀？答：是樹！而且是一棵有向樹！2 .討論：鄰接表與鄰接矩陣有什么異同之處？1 .聯(lián)系：鄰接表中每個鏈表對應(yīng)于鄰接矩陣中的一行，鏈表中結(jié)點個數(shù)等于一行中非零元素的個數(shù)。2 .區(qū)別：對于任一確定的無向圖，鄰接矩陣是唯一的（行列號與頂點編號一致），但鄰接表不唯一（鏈接次序與頂點編號無關(guān)）。3 .用途：鄰接矩陣多用于稠密圖的存儲而鄰接表多用于稀疏圖的存儲4 .若對連通圖進行遍歷，得到的是生成樹若對非連通圖進行遍歷，得到的是生成森林。第八章查找內(nèi)容提要： 查找表是稱為集合的數(shù)據(jù)結(jié)構(gòu)。是元素間約束

28、力最差的數(shù)據(jù)結(jié)構(gòu)：元素間的關(guān)系是元素僅共在同一個集合中。(同一類型的數(shù)據(jù)元素構(gòu)成的集合) 查找表的操作：查找，插入，刪除。 靜態(tài)查找表：順序表，有序表等。針對靜態(tài)查找表的查找算法主要有：順序查找、折半查找、分塊查找一、順序查找(線性查找)技巧：把待查關(guān)鍵字key存入表頭或表尾(俗稱“哨兵”)，這樣可以加快執(zhí)行速度。intSearch_Seq(SSTableST,KeyTypekey)0.key=key;for(i=;1inkey!=key方i1);ASL=eturnj2jlog2(n1)110g2nnj'1nPLspPRf找的過程是怎樣的？給定一個值K,在含有n個記錄的文件中進行搜索，

29、尋找一個關(guān)鍵字值等于K的記錄,如找到則輸出該記錄，否則輸出查找不成功的信息。2 .對查找表常用的操作有哪些？查詢某個“特定的”數(shù)據(jù)元素是否在表中；查詢某個“特定的”數(shù)據(jù)元素的各種屬性；在查找表中插入一元素；從查找表中刪除一元素。3 .哪些查找方法？查找方法取決于表中數(shù)據(jù)的排列方式；4 .如何評估查找方法的優(yōu)劣？用比較次數(shù)的平均值來評估算法的優(yōu)劣。稱為平均查找長度ASL。ASL應(yīng)Pi.Ci5 .使用折半查找算法時，要求被查文件：采用順序存貯結(jié)構(gòu)、記錄按關(guān)鍵字遞增有序6 .將線性表構(gòu)造成二叉排序樹的優(yōu)點： 查找過程與順序結(jié)構(gòu)有序表中的折半查找相似，查找效率高; 中序遍歷此二叉樹，將會得到一個關(guān)鍵字的有序序列(即實現(xiàn)了排序運算)； 如果查找不成功，能夠方便地將被查元素插入到二叉樹的葉子結(jié)點上，而且插入或刪除時只需修改指針而不需移動元素。第九章內(nèi)部排序內(nèi)容提要： 排序的定義，排序可以看作是線性表的一種操作排序：將一組雜亂無章的數(shù)據(jù)按一定的規(guī)律順次排列起來。 排序的分類，穩(wěn)定排序與不穩(wěn)定排序的定義。