自考~數(shù)據(jù)結(jié)構(gòu)筆記體會(超級詳細(xì)可做專業(yè)考試條)

1、.自考數(shù)據(jù)結(jié)構(gòu)筆記(詳盡版)感謝熱心自考人：liuii322筆記特點筆記特點：圖例豐富，超級詳細(xì)，幾乎涵蓋本課程所有要求掌握的知識點，。。。用于復(fù)習(xí)和做小條概論學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的意義...................................................................................................................................

2、...................................5概論算法的描述和分析(一).................................................................................................................................................................5線性表鏈?zhǔn)酱鎯Y(jié)構(gòu)

3、單鏈表的運(yùn)算（一）............................................................................................................................14三棧和隊列棧棧的定義及基本運(yùn)算......................................................................

4、...............................................................22三棧和隊列隊列隊列的定義及基本運(yùn)算..............................................................................................................................25三棧和隊列隊列順序隊

5、列..........................................................................................................................................................25棧和隊列隊列鏈隊列......................................................

6、..............................................................................................................26三棧和隊列棧和隊列的應(yīng)用實例棧的應(yīng)用實例（一）.....................................................................................

7、.............27四—串的基本概念（一）........................................................................................................................................................................30圖圖的概念（一）................

8、...............................................................................................................................................................63圖圖的存儲結(jié)構(gòu)鄰接矩陣表示法.............................................

9、...............................................................................................67圖圖的遍歷深度優(yōu)先遍歷（一）.............................................................................................................

10、...............................72圖圖的遍歷廣度優(yōu)先遍歷（一）..........................................................................................................................................75圖生成樹和最小生成樹生成樹....................

11、.............................................................................................................................77圖生成樹和最小生成樹最小生成樹（一）...........................................................................

12、...............................................79圖最短路徑（一）...................................................................................................................................................................

13、..........82圖拓?fù)渑判颍ㄒ唬?............................................................................................................................................................................84排序排序基本概念（一）..............

14、.................................................................................................................................................86排序插入排序直接插入排序（一）..........................................................

15、..............................................................................87排序插入排序直接插入排序（二）.............................................................................................................................

16、...........88排序插入排序希爾排序...............................................................................................................................................................89排序交換排序冒泡排序（一）.......................

17、..........................................................................................................................90排序交換排序快速排序（一）...................................................................................

18、............................................................92排序選擇排序堆排序（一）..................................................................................................................................................

19、....96排序歸并排序（一）...........................................................................................................................................................................98排序分配排序基數(shù)排序......................

20、.......................................................................................................................................101排序各種內(nèi)部排序方法的比較和選擇（一）...............................................................

21、...........................................................102查找查找的基本概念.....................................................................................................................................................

22、....................103查找線性表的查找順序查找.............................................................................................................................................................104查找線性表的查找二分查找（一）..........

23、............................................................................................................................105查找線性表的查找分塊查找.................................................................................

24、...................................................................107查找樹上的查找二叉排序樹（一）......................................................................................................................................1

25、09查找樹上的查找Ｂ－樹.............................................................................................................................................................114查找散列技術(shù)散列表的概念....................................

26、................................................................................................................121查找散列技術(shù)散列函數(shù)的構(gòu)造方法..........................................................................................

27、............................................122文件文件的基本概念（一）............................................................................................................................................................123文件

28、順序文件.......................................................................................................................................................................................125文件索引文件（一）.....................

29、....................................................................................................................................................126文件索引順序文件ISAM文件（一）....................................................

30、.................................................................................127文件索引順序文件VSAM文件（一）.......................................................................................................................

31、...........130文件散列文件.......................................................................................................................................................................................131文件多關(guān)鍵字文件多重表文件.

32、..............................................................................................................................................132.2非數(shù)值問題求解非數(shù)值問題求解瑞士計算機(jī)科學(xué)家沃思教授曾提出：算法數(shù)據(jù)結(jié)構(gòu)=程序數(shù)據(jù)結(jié)構(gòu)是數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)，算法是對數(shù)據(jù)運(yùn)算的描述概論概論算

33、法的描述和分析算法的描述和分析(一)數(shù)據(jù)的運(yùn)算通過算法(Algithm)描述1算法算法：非形式地說，算法是任意一個良定義的計算過程。它以一個或多個值作為輸入，并產(chǎn)生一個或多個值作為輸出。（1）一個算法可以被認(rèn)為是用來解決一個計算問題的工具。（2）一個算法是一系列將輸入轉(zhuǎn)換為輸出的計算步驟。2算法的描述算法的描述；一個算法可以用自然語言、計算機(jī)程序語言或其它語言來說明，惟一的要求是該說明必須精確地描述計算過程。描述算法最合適的語言是介于自

34、然語言和程序語言之間的偽語言。算法分析算法分析算法分析的目的是（評價算法的效率）算法分析的目的是（評價算法的效率）1評價算法好壞的標(biāo)準(zhǔn)：評價算法好壞的標(biāo)準(zhǔn)：首先應(yīng)是“正確“的。此外主要考慮三點：①執(zhí)行算法所耗費的時間；②執(zhí)行算法所耗費的存儲空間，主要考慮輔助存儲空間；③算法應(yīng)易于理解，易于編碼，易于調(diào)試等。算法的效率算法的效率分為時間效率和空間效率真3算法的時間性能分析算法的時間性能分析（1）算法所耗費的時間=算法中每條語句的執(zhí)行時間之

35、和每條語句的執(zhí)行時間=語句的執(zhí)行次數(shù)(即頻度))語句執(zhí)行一次所需時間的乘積。【例】求兩個n階方陣的乘積C=AB其算法如下:#definen100n可根據(jù)需要定義這里假定為100voidMatrixMultiply(intA[a]，intB[n][n]，intC[n][n])intijk(1)f(i=0i＜nj)n1(2)f(j=0j＜nj)n(n1)(3)C[i][j]=0n2(4)f(k=0k＜nk)n2(n1)(5)C[i][j]=

36、C[i][j]A[i][k]B[k][j]n3該算法中所有語句的頻度之和為：T(n)=2n33n22n1分析：分析：算法MatrixMultiply的時間耗費T(n)是矩陣階數(shù)n的函數(shù)。（2）問題規(guī)模和算法的時間復(fù)雜度算法求解問題的輸入量稱為問題的規(guī)模規(guī)模(Size)用一個整數(shù)表示。【例】一個圖論問題的規(guī)模則是圖中的頂點數(shù)或邊數(shù)。一個算法的時間復(fù)雜度(也稱時間復(fù)雜性)T(n)是該算法的時間耗費，是該算法所求解問題規(guī)模n的函數(shù)。當(dāng)問題的規(guī)

37、模n趨向無窮大時，時間復(fù)雜度T(n)的數(shù)量級(階)稱為算法的漸進(jìn)時間復(fù)雜度算法的漸進(jìn)時間復(fù)雜度?！纠?】算法MatrixMultidy的時間復(fù)雜度T(n)如(1.1)式所示，當(dāng)n趨向無窮大時，顯然有當(dāng)n充分大時，T(n)和n3之比是一個不等于零的常數(shù)。即T(n)和n3是同階的，或者說T(n)和n3的數(shù)量級相同。記作T(n)=O(n3)是算法MatrixMultiply的漸近時間復(fù)雜度。數(shù)學(xué)符號數(shù)學(xué)符號“O“的嚴(yán)格的數(shù)學(xué)定義：的嚴(yán)格的數(shù)學(xué)

38、定義：若T(n)和f(n)是定義在正整數(shù)集合上的兩個函數(shù)，則T(n)=O(f(n))表示存在正的常數(shù)C和n0，使得當(dāng)n≥n0時都滿足0≤T(n)≤Cf(n)。（3）漸進(jìn)時間復(fù)雜度評價算法時間性能）漸進(jìn)時間復(fù)雜度評價算法時間性能：主要用算法時間復(fù)雜度的數(shù)量級(即算法的漸近時間復(fù)雜度)評價一個算法的時間性能。將漸近時間復(fù)雜度T(n)=O(f(n))簡稱為時間復(fù)雜度，其中的f(n)一般是算法中頻度最大的語句頻度。當(dāng)有若干個循環(huán)語句時，算法的時

39、間復(fù)雜度由嵌套層數(shù)最多的循環(huán)語句中最內(nèi)層語句的頻度當(dāng)有若干個循環(huán)語句時，算法的時間復(fù)雜度由嵌套層數(shù)最多的循環(huán)語句中最內(nèi)層語句的頻度f(n)決定的。決定的。（4）算法的時間復(fù)雜度不僅僅依賴于問題的規(guī)模，還與輸入實例的初始狀態(tài)有關(guān)?！纠?12】在數(shù)值A(chǔ)[0..n1]中查找給定值K的算法大致如下：(1)i=n1(2)while(i=0(4)returni此算法中的語句(3)的頻度不僅與問題規(guī)模n有關(guān)，還與輸入實例中A的各元素取值及K的取值有關(guān)