自考數(shù)據(jù)結構筆記(超級詳細-可做考試條)

1、更多優(yōu)質自考資料盡在百度貼吧自考樂園自考樂園俱樂部（:tieba.club5346389）歡迎?加入...歡迎?交流...止不住的驚喜等著你........1自考數(shù)據(jù)結構筆記(詳盡版)感謝熱心自考人：liuii322筆記特點筆記特點：圖例豐富，超級詳細，幾乎涵蓋本課程所有要求掌握的知識點，。。。用于復習和做小條概論學習數(shù)據(jù)結構的意義.....................................................

2、.................................................................................................................5概論算法的描述和分析(一).............................................................................................

3、....................................................................5線性表鏈式存儲結構單鏈表的運算（一）............................................................................................................................14三棧和隊列棧棧

4、的定義及基本運算.....................................................................................................................................22三棧和隊列隊列隊列的定義及基本運算............................................................

5、..................................................................25三棧和隊列隊列順序隊列.............................................................................................................................................

6、.............25棧和隊列隊列鏈隊列....................................................................................................................................................................26三棧和隊列棧和隊列的應用實例棧的應用實例（一）.......

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

8、....................................................30圖圖的概念（一）..............................................................................................................................................................

9、.................63圖圖的存儲結構鄰接矩陣表示法............................................................................................................................................67圖圖的遍歷深度優(yōu)先遍歷（一）...............................

10、.............................................................................................................72圖圖的遍歷廣度優(yōu)先遍歷（一）...............................................................................................

11、...........................................75圖生成樹和最小生成樹生成樹.................................................................................................................................................77圖生成樹和最小生成樹最小生成樹

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

13、........................................................................................82圖拓撲排序（一）..........................................................................................................................

14、...................................................84排序排序基本概念（一）............................................................................................................................................................

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

16、.........................................................................................88排序插入排序希爾排序.......................................................................................................................

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

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

19、..................................................................................96排序歸并排序（一）...............................................................................................................................

20、............................................98排序分配排序基數(shù)排序.............................................................................................................................................................101排序各種

21、內部排序方法的比較和選擇（一）..........................................................................................................................102查找查找的基本概念.......................................................................

22、..................................................................................................103查找線性表的查找順序查找...........................................................................................................

23、..................................................104查找線性表的查找二分查找（一）......................................................................................................................................105查找線性表的查找分塊查找...

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

25、.............................................................................109查找樹上的查找Ｂ－樹..................................................................................................................................

26、...........................114查找散列技術散列表的概念....................................................................................................................................................121查找散列技術散列函數(shù)的構造方法............

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

28、.........................................................................123文件順序文件..........................................................................................................................................

29、.............................................125文件索引文件（一）...................................................................................................................................................................

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

31、.........................................................................................130文件散列文件..........................................................................................................................

32、.............................................................131更多優(yōu)質自考資料盡在百度貼吧自考樂園自考樂園俱樂部（:tieba.club5346389）歡迎?加入...歡迎?交流...止不住的驚喜等著你........31計算機處理問題的分類計算機處理問題的分類（1）數(shù)值計算問題（2）非數(shù)值性問題2非數(shù)值問題求解非數(shù)值問題求解瑞士計算機科學家沃思教授曾提出：算法數(shù)據(jù)結構=

33、程序數(shù)據(jù)結構是數(shù)據(jù)的邏輯結構和存儲結構，算法是對數(shù)據(jù)運算的描述概論概論算法的描述和分析算法的描述和分析(一)數(shù)據(jù)的運算通過算法(Algithm)描述1算法算法：非形式地說，算法是任意一個良定義的計算過程。它以一個或多個值作為輸入，并產生一個或多個值作為輸出。（1）一個算法可以被認為是用來解決一個計算問題的工具。（2）一個算法是一系列將輸入轉換為輸出的計算步驟。2算法的描述算法的描述；一個算法可以用自然語言、計算機程序語言或其它語言來說明

34、，惟一的要求是該說明必須精確地描述計算過程。描述算法最合適的語言是介于自然語言和程序語言之間的偽語言。算法分析算法分析算法分析的目的是（評價算法的效率）算法分析的目的是（評價算法的效率）1評價算法好壞的標準：評價算法好壞的標準：首先應是“正確“的。此外主要考慮三點：①執(zhí)行算法所耗費的時間；②執(zhí)行算法所耗費的存儲空間，主要考慮輔助存儲空間；③算法應易于理解，易于編碼，易于調試等。算法的效率算法的效率分為時間效率和空間效率真3算法的時間性能

35、分析算法的時間性能分析（1）算法所耗費的時間=算法中每條語句的執(zhí)行時間之和每條語句的執(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][

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

37、)T(n)是該算法的時間耗費，是該算法所求解問題規(guī)模n的函數(shù)。當問題的規(guī)模n趨向無窮大時，時間復雜度T(n)的數(shù)量級(階)稱為算法的漸進時間復雜度算法的漸進時間復雜度?！纠?】算法MatrixMultidy的時間復雜度T(n)如(1.1)式所示，當n趨向無窮大時，顯然有當n充分大時，T(n)和n3之比是一個不等于零的常數(shù)。即T(n)和n3是同階的，或者說T(n)和n3的數(shù)量級相同。記作T(n)=O(n3)是算法MatrixMultipl

38、y的漸近時間復雜度。數(shù)學符號數(shù)學符號“O“的嚴格的數(shù)學定義：的嚴格的數(shù)學定義：若T(n)和f(n)是定義在正整數(shù)集合上的兩個函數(shù)，則T(n)=O(f(n))表示存在正的常數(shù)C和n0，使得當n≥n0時都滿足0≤T(n)≤Cf(n)。（3）漸進時間復雜度評價算法時間性能）漸進時間復雜度評價算法時間性能：主要用算法時間復雜度的數(shù)量級(即算法的漸近時間復雜度)評價一個算法的時間性能。將漸近時間復雜度T(n)=O(f(n))簡稱為時間復雜度，其中

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