自考數(shù)據(jù)結(jié)構(gòu)筆記(超級(jí)詳細(xì)-可做考試條)

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

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

3、....................................................................5線(xiàn)性表鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)單鏈表的運(yùn)算（一）............................................................................................................................14三棧和隊(duì)列棧棧

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

5、..................................................................25三棧和隊(duì)列隊(duì)列順序隊(duì)列.............................................................................................................................................

6、.............25棧和隊(duì)列隊(duì)列鏈隊(duì)列....................................................................................................................................................................26三棧和隊(duì)列棧和隊(duì)列的應(yīng)用實(shí)例棧的應(yīng)用實(shí)例（一）.......

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

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

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

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

11、...........................................75圖生成樹(shù)和最小生成樹(shù)生成樹(shù).................................................................................................................................................77圖生成樹(shù)和最小生成樹(shù)最小生成樹(shù)

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

13、........................................................................................82圖拓?fù)渑判颍ㄒ唬?.........................................................................................................................

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

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

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

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

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

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

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

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

22、..................................................................................................103查找線(xiàn)性表的查找順序查找...........................................................................................................

23、..................................................104查找線(xiàn)性表的查找二分查找（一）......................................................................................................................................105查找線(xiàn)性表的查找分塊查找...

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

25、.............................................................................109查找樹(shù)上的查找Ｂ－樹(shù)..................................................................................................................................

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

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

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

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

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

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

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

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

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

35、分析算法的時(shí)間性能分析（1）算法所耗費(fèi)的時(shí)間=算法中每條語(yǔ)句的執(zhí)行時(shí)間之和每條語(yǔ)句的執(zhí)行時(shí)間=語(yǔ)句的執(zhí)行次數(shù)(即頻度))語(yǔ)句執(zhí)行一次所需時(shí)間的乘積?！纠壳髢蓚€(gè)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該算法中所有語(yǔ)句的頻度之和為：T(n)=2n33n22n1分析：分析：算法MatrixMultiply的時(shí)間耗費(fèi)T(n)是矩陣階數(shù)n的函數(shù)。（2）問(wèn)題規(guī)模和算法的時(shí)間復(fù)雜度算法求解問(wèn)題的輸入量稱(chēng)為問(wèn)題的規(guī)模規(guī)模(Size)用一個(gè)整數(shù)表示?！纠恳粋€(gè)圖論問(wèn)題的規(guī)模則是圖中的頂點(diǎn)數(shù)或邊數(shù)。一個(gè)算法的時(shí)間復(fù)雜度(也稱(chēng)時(shí)間復(fù)雜性

37、)T(n)是該算法的時(shí)間耗費(fèi)，是該算法所求解問(wèn)題規(guī)模n的函數(shù)。當(dāng)問(wèn)題的規(guī)模n趨向無(wú)窮大時(shí)，時(shí)間復(fù)雜度T(n)的數(shù)量級(jí)(階)稱(chēng)為算法的漸進(jìn)時(shí)間復(fù)雜度算法的漸進(jìn)時(shí)間復(fù)雜度。【例3】算法MatrixMultidy的時(shí)間復(fù)雜度T(n)如(1.1)式所示，當(dāng)n趨向無(wú)窮大時(shí)，顯然有當(dāng)n充分大時(shí)，T(n)和n3之比是一個(gè)不等于零的常數(shù)。即T(n)和n3是同階的，或者說(shuō)T(n)和n3的數(shù)量級(jí)相同。記作T(n)=O(n3)是算法MatrixMultipl

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

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