第1章 數(shù)據(jù)結(jié)構(gòu)與算法

1、章節(jié)章節(jié)名稱名稱內(nèi)容簡介內(nèi)容簡介第一章第一章數(shù)據(jù)結(jié)構(gòu)與算數(shù)據(jù)結(jié)構(gòu)與算法法主要介紹算法的基本特性、時間復(fù)雜度、空間復(fù)雜度、數(shù)據(jù)結(jié)構(gòu)、隊、棧、樹等考點。第二章第二章程序設(shè)計基礎(chǔ)程序設(shè)計基礎(chǔ)主要介紹面向?qū)ο蟮幕咎攸c、多態(tài)性、封裝性、類、消息、繼承、對象等考點。第三章第三章軟件工程基礎(chǔ)軟件工程基礎(chǔ)主要介紹軟件開發(fā)的三個階段、軟件開發(fā)方法、結(jié)構(gòu)化分析方法軟件測試和程序調(diào)試的區(qū)別、軟件測試黑盒測試、程序調(diào)試的任務(wù)軟件工程的主要思想、軟件危機、軟件開發(fā)環(huán)境等考點。第四章第四章數(shù)據(jù)庫設(shè)計基數(shù)據(jù)庫設(shè)計基礎(chǔ)礎(chǔ)主要介紹關(guān)系運算是考試的重點、數(shù)據(jù)庫設(shè)計的四個階段、兩個實體間的關(guān)系、數(shù)據(jù)獨立性、層次模型、網(wǎng)狀模型、數(shù)

2、據(jù)庫概念設(shè)計過程、數(shù)據(jù)庫的設(shè)計方法等考點。u數(shù)據(jù)結(jié)構(gòu)嚴(yán)蔚敏，吳偉民數(shù)據(jù)結(jié)構(gòu)嚴(yán)蔚敏，吳偉民 清華清華大學(xué)出版社大學(xué)出版社u數(shù)據(jù)庫系統(tǒng)概論數(shù)據(jù)庫系統(tǒng)概論 薩師煊，王珊高薩師煊，王珊高等教育出版社等教育出版社u軟件工程實例教程吳潔明軟件工程實例教程吳潔明 清清華大學(xué)出版社華大學(xué)出版社uC C程序設(shè)計（第四版）學(xué)習(xí)輔導(dǎo)程序設(shè)計（第四版）學(xué)習(xí)輔導(dǎo) 譚浩強譚浩強 清華大學(xué)出版社清華大學(xué)出版社1.1 算法算法1.2 數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)結(jié)構(gòu)的基本概念1.3 線性表及其順序存儲結(jié)構(gòu)線性表及其順序存儲結(jié)構(gòu)1.4 棧和隊列棧和隊列1.5 線性鏈表線性鏈表1.6 樹與二叉樹樹與二叉樹1.7 查找技術(shù)查找技術(shù)1.8

3、 排序技術(shù)排序技術(shù)1.1 算法學(xué)習(xí)要點算法學(xué)習(xí)要點u熟悉各名詞、術(shù)語的含義，掌握基本熟悉各名詞、術(shù)語的含義，掌握基本概念。概念。u理解算法的重要特性及其確切含義。理解算法的重要特性及其確切含義。u了解算法基本要素及算法設(shè)計基本方了解算法基本要素及算法設(shè)計基本方法。法。u掌握算法復(fù)雜度的計算方法。掌握算法復(fù)雜度的計算方法。1.1.1 算法的基本概念算法的基本概念 算法算法是為了解決某類問題而規(guī)定的一個有限長的操作序列操作序列。一個算法必須滿足以下u重要特性：重要特性：可行性可行性(effectiveness)(effectiveness)確定性確定性(definiteness)(definite

4、ness)有窮性有窮性(finiteness) (finiteness) 擁有足夠的情報：有輸入、有輸出擁有足夠的情報：有輸入、有輸出（1）可行性）可行性(effectiveness)算法中的所有操作都必須算法中的所有操作都必須足夠基本足夠基本，都，都可以通過已經(jīng)實現(xiàn)的基本操作運算有限可以通過已經(jīng)實現(xiàn)的基本操作運算有限次實現(xiàn)之。次實現(xiàn)之。（2）確定性）確定性(definiteness)對于每種情況下所應(yīng)執(zhí)行的操作，在算對于每種情況下所應(yīng)執(zhí)行的操作，在算法中都有確切的規(guī)定，使算法的執(zhí)行者法中都有確切的規(guī)定，使算法的執(zhí)行者或閱讀者都能明確其含義及如何執(zhí)行?；蜷喿x者都能明確其含義及如何執(zhí)行。并且在任

5、何條件下，并且在任何條件下，算法都只有一條執(zhí)算法都只有一條執(zhí)行路徑行路徑。（3）有窮性）有窮性(finiteness) 對于任意一組合法輸入值，在執(zhí)行對于任意一組合法輸入值，在執(zhí)行有窮有窮步驟步驟之后一定能結(jié)束，即：算法中的每之后一定能結(jié)束，即：算法中的每個步驟都能在個步驟都能在有限時間有限時間內(nèi)完成。內(nèi)完成。（4）擁有足夠的情報：有輸入、有輸出）擁有足夠的情報：有輸入、有輸出有輸入：有輸入：作為算法加工對象的量值，通常體現(xiàn)作為算法加工對象的量值，通常體現(xiàn)為算法中的一組變量。有些輸入量需要在算法為算法中的一組變量。有些輸入量需要在算法執(zhí)行過程中輸入，而有的算法表面上可以沒有執(zhí)行過程中輸入，而有

6、的算法表面上可以沒有輸入，實際上已被嵌入算法之中。輸入，實際上已被嵌入算法之中。有輸出有輸出：它是一組與：它是一組與“輸入輸入”有確定關(guān)系的量有確定關(guān)系的量值，是算法進(jìn)行信息加工后得到的結(jié)果，這種值，是算法進(jìn)行信息加工后得到的結(jié)果，這種確定關(guān)系即為算法的功能。確定關(guān)系即為算法的功能。u 算法的基本算法的基本要素要素（1 1）對數(shù)據(jù)對象的運算和操作）對數(shù)據(jù)對象的運算和操作算術(shù)運算：加、減、乘、除等算術(shù)運算：加、減、乘、除等邏輯運算：與、或、非等邏輯運算：與、或、非等關(guān)系運算：大于、小于、等于、不等于等關(guān)系運算：大于、小于、等于、不等于等數(shù)據(jù)傳輸：賦值、輸入、輸出數(shù)據(jù)傳輸：賦值、輸入、輸出（2 2

7、）算法的控制結(jié)構(gòu)）算法的控制結(jié)構(gòu)順序結(jié)構(gòu)順序結(jié)構(gòu)選擇結(jié)構(gòu)選擇結(jié)構(gòu)循環(huán)結(jié)構(gòu)循環(huán)結(jié)構(gòu) 指令系統(tǒng)：指令系統(tǒng)：一個計算機系統(tǒng)能執(zhí)行的所有指令的集合。一個計算機系統(tǒng)能執(zhí)行的所有指令的集合。計算機算法計算機算法就是計算機能處理的操作所組成的指令序列。就是計算機能處理的操作所組成的指令序列。 u 算法設(shè)計基本方法算法設(shè)計基本方法（1 1）列舉法）列舉法（2 2）歸納法）歸納法（3 3）遞推）遞推（4 4）遞歸）遞歸（5 5）減半遞推技術(shù)：如二分法）減半遞推技術(shù)：如二分法（6 6）回溯法）回溯法 1.1.2 算法復(fù)雜度算法復(fù)雜度算法復(fù)雜度主要包括：算法復(fù)雜度主要包括：u時間復(fù)雜度時間復(fù)雜度u空間復(fù)雜度空間復(fù)雜

8、度u 算法的算法的時間時間復(fù)雜度復(fù)雜度算法時間復(fù)雜度是指執(zhí)行算法所需要的計算算法時間復(fù)雜度是指執(zhí)行算法所需要的計算工作量。工作量。算法工作量算法工作量=f(n)=f(n)算法的工作量用算法所執(zhí)行的基本運算次數(shù)算法的工作量用算法所執(zhí)行的基本運算次數(shù)來度量，而算法執(zhí)行的基本運算次數(shù)是問題來度量，而算法執(zhí)行的基本運算次數(shù)是問題規(guī)模的函數(shù)，即：規(guī)模的函數(shù)，即：算法工作量算法工作量=f(n)=f(n)如下算法：如下算法：i=1;i=1;while (i=n)while (i=n) i=i i=i* *2;2;設(shè)循環(huán)執(zhí)行的次數(shù)為設(shè)循環(huán)執(zhí)行的次數(shù)為m,m,則：則：第第1 1次循環(huán)時，次循環(huán)時，i=1i=1時

9、時i=2i=2第第2 2次循環(huán)時，次循環(huán)時，i=2i=2時時i=2i=2* *2=i2=i2 2第第3 3次循環(huán)時，次循環(huán)時，i=4i=4時時i=2i=23 3第第m m次循環(huán)時，次循環(huán)時，i=2i=2m-1m-1時時i=2i=2m m此時此時n=2n=2m m 取對數(shù)，則有取對數(shù)，則有m=logm=log2 2n n此算法工作量為此算法工作量為loglog2 2n n如下算法：如下算法：i=s=0;i=s=0;while (sn)while (s1k1，則該結(jié)點的父結(jié)點編號為則該結(jié)點的父結(jié)點編號為INT(k/2)INT(k/2)； 若若2kn2kn，則編號為，則編號為k k的結(jié)點的左子結(jié)點編

10、號為的結(jié)點的左子結(jié)點編號為2k2k；否則該結(jié)點無左子結(jié)點（也無右子結(jié)點）；否則該結(jié)點無左子結(jié)點（也無右子結(jié)點）； 若若2k+1n2k+1n，則編號為，則編號為k k的結(jié)點的右子結(jié)點編號為的結(jié)點的右子結(jié)點編號為2k+12k+1；否則該結(jié)點無右子結(jié)點。；否則該結(jié)點無右子結(jié)點。 u滿二叉樹是指除最后一層外，每一層上的所滿二叉樹是指除最后一層外，每一層上的所有結(jié)點有兩個子結(jié)點，則有結(jié)點有兩個子結(jié)點，則k k層上有層上有2 2k-1k-1個結(jié)點個結(jié)點深度為深度為m m的滿二叉樹有的滿二叉樹有2 2m m-1-1個結(jié)點。個結(jié)點。u完全二叉樹是指除最后一層外，每一層上完全二叉樹是指除最后一層外，每一層上的結(jié)

11、點數(shù)均達(dá)到最大值，在最后一層上只的結(jié)點數(shù)均達(dá)到最大值，在最后一層上只缺少右邊的若干結(jié)點。缺少右邊的若干結(jié)點。u順序存儲結(jié)構(gòu)：適用于完全二叉樹順序存儲結(jié)構(gòu)：適用于完全二叉樹1.6.3 1.6.3 二叉樹的存儲結(jié)構(gòu)二叉樹的存儲結(jié)構(gòu)u鏈?zhǔn)酱鎯Y(jié)構(gòu)：適用于非完全二叉樹鏈?zhǔn)酱鎯Y(jié)構(gòu)：適用于非完全二叉樹指向該結(jié)點左孩子的指針指向該結(jié)點右孩子的指針 數(shù)據(jù)元素的內(nèi)容 前序遍歷（前序遍歷（DLRDLR）: :首先訪問根結(jié)點，然后遍歷左子樹，首先訪問根結(jié)點，然后遍歷左子樹，最后遍歷右子樹；最后遍歷右子樹； 中序遍歷（中序遍歷（LDRLDR）: :首先遍歷左子樹，然后訪問根結(jié)點，首先遍歷左子樹，然后訪問根結(jié)點，最后

12、遍歷右子樹；最后遍歷右子樹； 后序遍歷（后序遍歷（LRDLRD）: :首先遍歷左子樹，然后訪問遍歷右子首先遍歷左子樹，然后訪問遍歷右子樹，最后訪問根結(jié)點。樹，最后訪問根結(jié)點。1.6.4 1.6.4 二叉樹的遍歷二叉樹的遍歷u按根、左子樹和右子樹三部分進(jìn)行遍歷按根、左子樹和右子樹三部分進(jìn)行遍歷u三種遍歷得到的相應(yīng)序列三種遍歷得到的相應(yīng)序列1.7 查找技術(shù)查找技術(shù)u查找技術(shù)的相關(guān)概念：查找技術(shù)的相關(guān)概念： 查找表查找表：用于查找的數(shù)據(jù)元素集合稱為查找表。：用于查找的數(shù)據(jù)元素集合稱為查找表。查找表由同一類型的數(shù)據(jù)元素（或記錄）構(gòu)成。查找表由同一類型的數(shù)據(jù)元素（或記錄）構(gòu)成。 靜態(tài)查找表靜態(tài)查找表在查

13、找過程中查找表本身不發(fā)生變在查找過程中查找表本身不發(fā)生變化。對靜態(tài)查找表進(jìn)行的查找操作稱為靜態(tài)查化。對靜態(tài)查找表進(jìn)行的查找操作稱為靜態(tài)查找。找。 動態(tài)查找表動態(tài)查找表在查找過程中查找表可能會發(fā)生變在查找過程中查找表可能會發(fā)生變化。對動態(tài)查找表進(jìn)行的查找操作稱為動態(tài)查化。對動態(tài)查找表進(jìn)行的查找操作稱為動態(tài)查找。找。u查找技術(shù)的相關(guān)概念：查找技術(shù)的相關(guān)概念： 關(guān)鍵字：關(guān)鍵字：是數(shù)據(jù)元素中的某個數(shù)據(jù)項。是數(shù)據(jù)元素中的某個數(shù)據(jù)項。 查找：查找：在數(shù)據(jù)元素集合中查找滿足某種條件的在數(shù)據(jù)元素集合中查找滿足某種條件的數(shù)據(jù)元素的過程稱為查找。數(shù)據(jù)元素的過程稱為查找。 查找條件查找條件是是“關(guān)鍵字值等于某個給定

14、值關(guān)鍵字值等于某個給定值”。 查找算法的時間效率查找算法的時間效率：查找過程的主要操作是：查找過程的主要操作是關(guān)鍵字的比較，所以通常以關(guān)鍵字的比較，所以通常以“平均比較次數(shù)平均比較次數(shù)”來衡量查找算法的時間效率。來衡量查找算法的時間效率。1.7 查找技術(shù)查找技術(shù)u順序查找的使用情況：順序查找的使用情況：u二分法查找只適用于順序存儲的有序表，二分法查找只適用于順序存儲的有序表，對于長度為對于長度為n n的有序線性表，最壞情況只需的有序線性表，最壞情況只需比較比較loglog2 2n n次。次。 線性表為無序表；線性表為無序表； 表采用鏈?zhǔn)酱鎯Y(jié)構(gòu)。表采用鏈?zhǔn)酱鎯Y(jié)構(gòu)。1.8 排序技術(shù)排序技術(shù)u排

15、序是指將一個無序序列整理成按值非遞減排序是指將一個無序序列整理成按值非遞減順序排列的有序序列。順序排列的有序序列。u交換類排序法：（交換類排序法：（1 1）冒泡排序法，需要比）冒泡排序法，需要比較的次數(shù)為較的次數(shù)為n(n-1)/2n(n-1)/2；（；（2 2）快速排序法。）快速排序法。u插入類排序法：（插入類排序法：（1 1）簡單插入排序法，最）簡單插入排序法，最壞情況需要壞情況需要n(n-1)/2n(n-1)/2次比較；（次比較；（2 2）希爾排）希爾排序法，最壞情況需要序法，最壞情況需要O(n1.5)O(n1.5)次比較。次比較。u順序查找：長度為順序查找：長度為n n的線性表，平均要進(jìn)

16、行的線性表，平均要進(jìn)行n/2n/2，最壞要進(jìn)行，最壞要進(jìn)行n n次比較。（?？迹┐伪容^。（?？迹﹗二分查找：對于長度為二分查找：對于長度為n n的線性表，在最壞的線性表，在最壞情況進(jìn)行情況進(jìn)行l(wèi)og2nlog2n次。次。u選擇類排序法：（選擇類排序法：（1 1）簡單選擇排序法）簡單選擇排序法, , 最最壞情況需要壞情況需要n(n-1)/2n(n-1)/2次比較；（次比較；（2 2）堆排序）堆排序法，最壞情況需要法，最壞情況需要O(nlog2n)O(nlog2n)次比較。次比較。u構(gòu)造如下樹型結(jié)構(gòu)構(gòu)造如下樹型結(jié)構(gòu)qQNodeQElemTypedatanumnamenextpQElemTypenu

17、m12345namebcdefqqQElemTypenum012345nameabcdef0aTPTreePTNode012345nodesdataabcdefparent-100112n61bnext0anext0anext0anextQLinkQueueQNodefrontdatanextreardatanextqLinkQueuefrontrearu初始化隊列初始化隊列u輸入根結(jié)點輸入根結(jié)點a a，并使之入隊，并使之入隊TPTreePTNode0nodesdataaparent-1nqqQElemTypenum0nameaQNodeQElemTypedata0aNULLQNodeQEle

18、mTypedatanumnameNULLQNodeQElemTypedatanumnameqLinkQueuefrontrearu根結(jié)點根結(jié)點a a出隊出隊qqQElemTypenum0nameaQNodeQElemTypedata0aNULLQNodeQElemTypedatanumnameQNodeQElemTypedatanumnameNULLqLinkQueuefrontrearu輸入根結(jié)點輸入根結(jié)點a a的孩子的孩子bcbc并入隊并入隊qqQElemTypenum0nameaTPTreePTNode01nodesdataabparent-10npQElemTypenum1namebQNodeQElemTypedata1bNULLQNodeQElemTypedatanumnameNULLQNodeQElemTypedatanumna