第1章 數(shù)據(jù)結構與算法

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

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

3、 排序技術排序技術1.1 算法學習要點算法學習要點u熟悉各名詞、術語的含義，掌握基本熟悉各名詞、術語的含義，掌握基本概念。概念。u理解算法的重要特性及其確切含義。理解算法的重要特性及其確切含義。u了解算法基本要素及算法設計基本方了解算法基本要素及算法設計基本方法。法。u掌握算法復雜度的計算方法。掌握算法復雜度的計算方法。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)對于每種情況下所應執(zhí)行的操作，在算對于每種情況下所應執(zhí)行的操作，在算法中都有確切的規(guī)定，使算法的執(zhí)行者法中都有確切的規(guī)定，使算法的執(zhí)行者或閱讀者都能明確其含義及如何執(zhí)行。或閱讀者都能明確其含義及如何執(zhí)行。并且在任

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

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

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

8、度u 算法的算法的時間時間復雜度復雜度算法時間復雜度是指執(zhí)行算法所需要的計算算法時間復雜度是指執(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;設循環(huán)執(zhí)行的次數(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，則該結點的父結點編號為則該結點的父結點編號為INT(k/2)INT(k/2)； 若若2kn2kn，則編號為，則編號為k k的結點的左子結點編

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

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

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

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

14、值關鍵字值等于某個給定值”。 查找算法的時間效率查找算法的時間效率：查找過程的主要操作是：查找過程的主要操作是關鍵字的比較，所以通常以關鍵字的比較，所以通常以“平均比較次數(shù)平均比較次數(shù)”來衡量查找算法的時間效率。來衡量查找算法的時間效率。1.7 查找技術查找技術u順序查找的使用情況：順序查找的使用情況：u二分法查找只適用于順序存儲的有序表，二分法查找只適用于順序存儲的有序表，對于長度為對于長度為n n的有序線性表，最壞情況只需的有序線性表，最壞情況只需比較比較loglog2 2n n次。次。 線性表為無序表；線性表為無序表； 表采用鏈式存儲結構。表采用鏈式存儲結構。1.8 排序技術排序技術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的線性表，平均要進

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

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

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