1、第1章數(shù)據(jù)結(jié)構(gòu)和算法I .教學(xué)目標(biāo)1.理解算法的基本概念。2.理解數(shù)據(jù)結(jié)構(gòu)的基本概念。3.理解線性表及其順序存儲(chǔ)結(jié)構(gòu)。4.了解堆棧和隊(duì)列的基本知識(shí)。5.理解線性鏈表。6.理解樹(shù)和二叉樹(shù)的基本概念，掌握二叉樹(shù)的性質(zhì)和遍歷。7、了解搜索技術(shù)。8、了解分揀技術(shù)。二。教學(xué)方法1、重點(diǎn)內(nèi)容和經(jīng)常性測(cè)試內(nèi)容的重點(diǎn)。2.舉例說(shuō)明程序設(shè)計(jì)中的重點(diǎn)和難點(diǎn)，如實(shí)際問(wèn)題。三。主要內(nèi)容1.算法的時(shí)間復(fù)雜度和空間復(fù)雜度。2.判斷線性結(jié)構(gòu)和非線性結(jié)構(gòu)。3.堆棧和隊(duì)列的基本知識(shí)，計(jì)算堆棧和隊(duì)列中的元素?cái)?shù)量。4.二叉樹(shù)的基本性質(zhì)和二叉樹(shù)的遍歷。5.搜索方法和排序技術(shù)中的最壞情況時(shí)間。四、教學(xué)內(nèi)容1.1算法1.1.1算法的基本

2、概念算法是指對(duì)問(wèn)題解決方案的準(zhǔn)確和完整的描述。1.算法的基本特征：(理解記憶)(1)可行性(2)確定性算法的確定性意味著算法中的每一步都必須明確定義，不允許有歧義的解釋或歧義。(3)貧窮算法的有限性意味著算法必須在有限的時(shí)間內(nèi)完成，也就是說(shuō)，算法必須在執(zhí)行有限的步驟后終止。(4)有效性所謂的算法是一組嚴(yán)格定義操作順序的規(guī)則，每條規(guī)則都是有效和清晰的，并且這個(gè)順序?qū)⒃谟邢薜拇螖?shù)內(nèi)終止。所謂的算法是一組嚴(yán)格定義操作順序的規(guī)則，每條規(guī)則都是有效和清晰的，并且這個(gè)順序?qū)⒃谟邢薜拇螖?shù)內(nèi)終止。2.算法的基本要素：(1)算法中數(shù)據(jù)對(duì)象的運(yùn)算和運(yùn)算。(2)算法的控制結(jié)構(gòu)：順序、選擇和循環(huán)(記憶)3.算法設(shè)計(jì)的

3、基本方法：(理解)(1)枚舉法(2)歸納(3)遞歸(4)遞歸(5)半遞歸技術(shù)(6)回溯法1.1.2算法的復(fù)雜性算法的復(fù)雜度主要包括時(shí)間復(fù)雜度和空間復(fù)雜度。1.算法的時(shí)間復(fù)雜度是指執(zhí)行算法所需的計(jì)算工作量。算法的工作量由算法執(zhí)行的基本操作的數(shù)量來(lái)衡量。算法執(zhí)行的基本時(shí)間與問(wèn)題的規(guī)模有關(guān)。分析算法工作量的方法：(理解)(1)平均行為(2)最壞情況的復(fù)雜性最壞情況分析是指當(dāng)比例為n時(shí)，算法執(zhí)行的最大基本操作數(shù)。2.算法的空間復(fù)雜度通常指執(zhí)行算法所需的內(nèi)存空間。算法占用的存儲(chǔ)空間包括算法程序占用的空間、輸入初始數(shù)據(jù)占用的存儲(chǔ)空間以及算法執(zhí)行過(guò)程中所需的額外空間。算法的時(shí)間復(fù)雜度不一定與空間復(fù)雜度相關(guān)。

4、1.2數(shù)據(jù)結(jié)構(gòu)的基本概念1.2.1什么是數(shù)據(jù)結(jié)構(gòu)簡(jiǎn)而言之，數(shù)據(jù)結(jié)構(gòu)指的是相互關(guān)聯(lián)的數(shù)據(jù)元素的集合。例如：(1)一年四季的名稱春天，夏天，秋天，冬天(2)代表家庭成員的每個(gè)成員父親，兒子，女兒在數(shù)據(jù)處理領(lǐng)域，數(shù)據(jù)元素之間的這種內(nèi)在關(guān)系通常簡(jiǎn)單地用先行關(guān)系來(lái)描述。先行關(guān)系是數(shù)據(jù)元素之間的基本關(guān)系。一般來(lái)說(shuō)，數(shù)據(jù)元素之間的任何關(guān)系都可以用先行關(guān)系來(lái)描述。1.數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)是指反映數(shù)據(jù)元素之間邏輯關(guān)系的數(shù)據(jù)結(jié)構(gòu)。2.數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)計(jì)算機(jī)存儲(chǔ)空間中數(shù)據(jù)邏輯結(jié)構(gòu)的存儲(chǔ)形式稱為數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)(也稱為數(shù)據(jù)物理結(jié)構(gòu))。注意：數(shù)據(jù)的邏輯結(jié)構(gòu)可以根據(jù)需要表示為各種存儲(chǔ)結(jié)構(gòu)，即，數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)不

5、一一對(duì)應(yīng)。常用的數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)包括序列、鏈接、索引等。1.2.2數(shù)據(jù)結(jié)構(gòu)的圖示冬天的秋天夏天春天上圖顯示了全年數(shù)據(jù)結(jié)構(gòu)的圖形表示兒子女兒父親上圖顯示了家庭成員代際關(guān)系的數(shù)據(jù)結(jié)構(gòu)的圖形表示1、節(jié)點(diǎn)的基本概念理解根節(jié)點(diǎn)：在數(shù)據(jù)結(jié)構(gòu)中，沒(méi)有前因的節(jié)點(diǎn)稱為根節(jié)點(diǎn)葉節(jié)點(diǎn)(終端節(jié)點(diǎn)):沒(méi)有post的節(jié)點(diǎn)稱為葉節(jié)點(diǎn)。內(nèi)部節(jié)點(diǎn)：除根節(jié)點(diǎn)和終端節(jié)點(diǎn)外的其他節(jié)點(diǎn)通常稱為內(nèi)部節(jié)點(diǎn)。2.操作理解(1)插入操作：在數(shù)據(jù)結(jié)構(gòu)中添加一個(gè)新節(jié)點(diǎn)。(2)刪除操作：刪除數(shù)據(jù)結(jié)構(gòu)中的一個(gè)節(jié)點(diǎn)。插入和刪除操作是數(shù)據(jù)結(jié)構(gòu)的兩種基本操作。1.2.3線性結(jié)構(gòu)和非線性結(jié)構(gòu)如果非空數(shù)據(jù)結(jié)構(gòu)滿足以下兩個(gè)條件：(1)只有一個(gè)根節(jié)點(diǎn)；(2)每個(gè)節(jié)點(diǎn)最

6、多有一個(gè)前部和一個(gè)后部。數(shù)據(jù)結(jié)構(gòu)是線性結(jié)構(gòu)。線性結(jié)構(gòu)也稱為線性表。如果一個(gè)數(shù)據(jù)結(jié)構(gòu)不是線性的，它被稱為非線性結(jié)構(gòu)。線性結(jié)構(gòu)和非線性結(jié)構(gòu)都可以是空數(shù)據(jù)結(jié)構(gòu)。注意：記憶(1)線性結(jié)構(gòu)包括線性表、堆棧、隊(duì)列、循環(huán)隊(duì)列和線性鏈表(2)非線性結(jié)構(gòu)：樹(shù)和二叉樹(shù)1.3線性表及其順序存儲(chǔ)結(jié)構(gòu)(理解)1.3.1線性表的基本概念線性表是最簡(jiǎn)單也是最常用的數(shù)據(jù)結(jié)構(gòu)。(線性結(jié)構(gòu))1.3.2線性表的順序存儲(chǔ)結(jié)構(gòu)在計(jì)算機(jī)中存儲(chǔ)線性表的最簡(jiǎn)單方法之一是順序存儲(chǔ)，也稱為順序分配。線性表的順序存儲(chǔ)結(jié)構(gòu)具有以下兩個(gè)基本特征：(1)線性表中所有元素占用的存儲(chǔ)空間是連續(xù)的；(2)線性表中的數(shù)據(jù)元素以邏輯順序存儲(chǔ)在存儲(chǔ)空間中。在編程語(yǔ)

7、言中，通常定義一維數(shù)組來(lái)表示線性表的順序存儲(chǔ)空間。1.3.3序列表的插入操作(簡(jiǎn)單理解)1.3.4序列表的刪除操作(簡(jiǎn)單理解)1.4堆棧和隊(duì)列1.4.1堆棧及其基本操作1.什么是堆棧堆棧是一個(gè)線性表，僅限于一端的插入和刪除操作。記憶數(shù)據(jù)組織原則：“先進(jìn)先出”或“后進(jìn)先出”內(nèi)存堆棧具有存儲(chǔ)功能。使用頂部指針指向堆棧頂部(頂部元素)，底部指針指向堆棧底部(底部元素)2.堆棧的順序存儲(chǔ)結(jié)構(gòu)及其操作(理解)在編程語(yǔ)言中，一維數(shù)組被用作堆棧的順序存儲(chǔ)空間。堆棧的基本操作：(1)堆垛作業(yè)(2)回堆操作(3)讀取堆棧的頂部元素附加內(nèi)容：計(jì)算堆棧中元素的數(shù)量，m代表容量，b代表底部，t代表頂部大-小1=堆棧中

8、元素的數(shù)量1.4.2隊(duì)列及其基本操作1.什么是隊(duì)列隊(duì)列是線性表，允許一端插入，另一端刪除。隊(duì)列的數(shù)據(jù)組織原則是“先進(jìn)先出”或“后進(jìn)先出”使用頭部指針指向頭部元素的下一個(gè)位置，使用尾部指針指向尾部元素。在編程語(yǔ)言中，一維數(shù)組被用作隊(duì)列的順序存儲(chǔ)空間。2.循環(huán)隊(duì)列及其與運(yùn)算在實(shí)際應(yīng)用中，隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)一般采用循環(huán)隊(duì)列的形式。(1)排隊(duì)操作(2)退出團(tuán)隊(duì)附加內(nèi)容：計(jì)算隊(duì)列中元素的數(shù)量。m代表能力，f代表團(tuán)隊(duì)領(lǐng)導(dǎo)指針，r代表團(tuán)隊(duì)領(lǐng)導(dǎo)指針(1) f =r元素?cái)?shù)=m-f r1.5線性鏈表(只需理解)1.5.1線性鏈表的基本概念1.線性鏈表線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)稱為線性鏈表。2.帶鏈條的堆棧3.帶鏈條的隊(duì)

9、列1.5.2線性鏈表的基本操作1.在線性鏈表中查找指定的元素2.插入線性鏈表3.刪除線性鏈表1.5.3循環(huán)鏈表及其基本操作1.6樹(shù)和二叉樹(shù)(強(qiáng)調(diào))1.6.1樹(shù)木的基本概念樹(shù)是一個(gè)簡(jiǎn)單的非線性結(jié)構(gòu)。樹(shù)形結(jié)構(gòu)的基本術(shù)語(yǔ)：(理解)1.根節(jié)點(diǎn)：在樹(shù)結(jié)構(gòu)中，只有一個(gè)沒(méi)有前因的節(jié)點(diǎn)，稱為樹(shù)的根2.子節(jié)點(diǎn)：每個(gè)節(jié)點(diǎn)的后繼節(jié)點(diǎn)稱為該節(jié)點(diǎn)的子節(jié)點(diǎn)3.葉節(jié)點(diǎn)：沒(méi)有余數(shù)的節(jié)點(diǎn)4.節(jié)點(diǎn)度：節(jié)點(diǎn)擁有的余數(shù)。5.樹(shù)的度：所有節(jié)點(diǎn)的最大度稱為樹(shù)的度。6.樹(shù)的深度：樹(shù)的分層。樹(shù)的最大高度叫做樹(shù)的深度。7.子樹(shù)：以某個(gè)子節(jié)點(diǎn)為根的樹(shù)稱為該節(jié)點(diǎn)的子樹(shù)。1.6.2二叉樹(shù)及其基本性質(zhì)1.什么是二叉樹(shù)二叉樹(shù)有以下兩個(gè)特點(diǎn)：(1)非空二

10、叉樹(shù)只有一個(gè)根節(jié)點(diǎn)；(2)每個(gè)節(jié)點(diǎn)最多有兩個(gè)子樹(shù)，分別稱為節(jié)點(diǎn)的左子樹(shù)和右子樹(shù)。節(jié)點(diǎn)的最大度數(shù)是2，樹(shù)的最大度數(shù)是2。2.二叉樹(shù)的基本性質(zhì)屬性1在二叉樹(shù)的第k級(jí)上最多有2k-1個(gè)(k=1)節(jié)點(diǎn)屬性2中深度為m的二叉樹(shù)最多有2m-1個(gè)節(jié)點(diǎn)屬性3在任何二叉樹(shù)中，0度的點(diǎn)(即葉節(jié)點(diǎn))總是比2度的節(jié)點(diǎn)多一個(gè)。n0=n2 1性質(zhì)4是具有n個(gè)節(jié)點(diǎn)的二叉樹(shù)，其深度至少為log2n 1，其中l(wèi)og2n表示log2n的整數(shù)部分。3.全二叉樹(shù)和全二叉樹(shù)(1)在全二叉樹(shù)的第k層上有2k-1個(gè)節(jié)點(diǎn)，在m深度的全二叉樹(shù)中有2m-1個(gè)節(jié)點(diǎn)。DEFGCBA(2)完全二叉樹(shù)除了最后一層，每層的節(jié)點(diǎn)數(shù)都達(dá)到最大。在最后一層，只

11、有右邊的幾個(gè)節(jié)點(diǎn)丟失了。完整的二叉樹(shù)也是完整的二叉樹(shù)，而完整的二叉樹(shù)通常不是完整的二叉樹(shù)。完整的二叉樹(shù)也有以下兩個(gè)屬性：性質(zhì)5中具有n個(gè)節(jié)點(diǎn)的完全二叉樹(shù)的深度是log2n 1。屬性6讓完整的二叉樹(shù)共享.此外：(1)完全二叉樹(shù)度為1的節(jié)點(diǎn)數(shù)為0或1。n1=0，1n0=n2 1n=n0 n1 n2(2)如果完整二叉樹(shù)中的節(jié)點(diǎn)總數(shù)是n，n0是葉節(jié)點(diǎn)數(shù)，那么A.n是偶數(shù)，n0=n/2B.n是奇數(shù)，n0=(n 1)/21.6.3二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)二叉樹(shù)通常采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。1.6.4二叉樹(shù)的遍歷master二叉樹(shù)遍歷是指不重復(fù)訪問(wèn)二叉樹(shù)中的所有節(jié)點(diǎn)。在“先左后右”的原則下，根據(jù)訪問(wèn)根節(jié)點(diǎn)的順序，有三種遍歷

12、二叉樹(shù)的方法。1.序言遍歷：根節(jié)點(diǎn)左子樹(shù)右子樹(shù)2.中間順序遍歷：左子樹(shù)根節(jié)點(diǎn)右子樹(shù)3.序列后遍歷：左子樹(shù)右子樹(shù)根節(jié)點(diǎn)DEBCAF遍歷結(jié)果：(1)序言遍歷：ABDECF(2)中間順序遍歷：DBEAFC(3)后順序遍歷：DEBFCA1.7搜索技術(shù)對(duì)于長(zhǎng)度為n的有序線性表1.7.1按順序搜索在最壞的情況下，順序搜索需要被比較n次。1.7.2二分法搜索在最壞的情況下，二分搜索(二分法搜索)需要比較log2n次。1.8分揀技術(shù)1.8.1交換類排序方法1.氣泡分選法在最壞的情況下，比較的次數(shù)是n(n-1)/22.快速排序方法在最壞的情況下，比較的次數(shù)是n(n-1)/21.8.2插入類排序方法1.簡(jiǎn)單的插入排序方法在最壞的情況下，比較的次數(shù)是n(n-1)/22.希爾分類方法在最壞的情況下，比較的次數(shù)是O(n1.5)1.8.3選擇