大學(xué)計(jì)算機(jī)基礎(chǔ)（第6版）（微課版） 課件 第6章 算法與數(shù)據(jù)結(jié)構(gòu)

第6章算法與數(shù)據(jù)結(jié)構(gòu)大學(xué)計(jì)算機(jī)基礎(chǔ)課程組2022年4月程序數(shù)據(jù)結(jié)構(gòu)=算法+主要內(nèi)容算法的基本知識(shí)1數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)2幾種常見的算法33主要內(nèi)容1算法及其基本特點(diǎn)算法描述方法算法復(fù)雜度分析數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)2幾種常見的算法34算法的基本知識(shí)數(shù)據(jù)結(jié)構(gòu)的概念常見的幾種數(shù)據(jù)結(jié)構(gòu)及其基本操查找算法、排序算法、遞推算法、枚舉算法、貪心算法、分治算法算法(algorithms):是為了求解問題而給出的有限的指令序列，每條指令表示一個(gè)或多個(gè)操作?！鉀Q問題的步驟程序是算法的一種實(shí)現(xiàn)，計(jì)算機(jī)按照程序逐步執(zhí)行算法，實(shí)現(xiàn)對(duì)問題的求解。6.1算法（algorithm）基礎(chǔ)方案設(shè)計(jì)方案實(shí)現(xiàn)數(shù)據(jù)模型基本想法數(shù)據(jù)表示數(shù)據(jù)處理選擇語言選擇IDE方法設(shè)計(jì)6.1.1計(jì)算機(jī)求解問題的過程6.1.2算法的特點(diǎn)有窮性：一個(gè)算法必須能在執(zhí)行有窮步之后結(jié)束，且每一步都可在有窮時(shí)間內(nèi)完成；確定性：算法中每一條指令必須有確切的含義，不具有二義性?？尚行裕核惴ㄖ忻枋龅牟僮鞫伎赏ㄟ^已經(jīng)實(shí)現(xiàn)的基本運(yùn)算執(zhí)行有限次來實(shí)現(xiàn)。輸入：一個(gè)算法有零個(gè)或多個(gè)輸入，這些輸入取自某個(gè)特定的對(duì)象的集合輸出：一個(gè)算法有一個(gè)或多個(gè)輸出，這些輸出是同輸入具有某種特定關(guān)系的量。算法設(shè)計(jì)者在構(gòu)思和設(shè)計(jì)了一個(gè)算法之后，必須清楚準(zhǔn)確地將所設(shè)計(jì)的求解步驟記錄下來，即描述算法。常用的描述算法的方法有自然語言流程圖程序設(shè)計(jì)語言偽代碼等。下面以計(jì)算10個(gè)數(shù)的平均值算法為例進(jìn)行介紹6.1.3算法的描述方法自然語言（1）定義一個(gè)變量sum用來記錄10個(gè)數(shù)的和，并給其賦值為0。（2）輸入一個(gè)數(shù)x，并將輸入的這個(gè)數(shù)x與sum進(jìn)行加法計(jì)算，用sum記錄加法計(jì)算的結(jié)果。（3）重復(fù)執(zhí)行（2）10次。第1次執(zhí)行（2）時(shí)sum中記錄了第1個(gè)數(shù)的值，第2次執(zhí)行（2）后sum中記錄了前2個(gè)數(shù)的和，第3次執(zhí)行（2）后sum中記錄了前3個(gè)數(shù)的和……，第10次執(zhí)行（2）后sum中記錄下了10個(gè)數(shù)的和。（4）將sum除以10，得到10個(gè)數(shù)的平均值。用自然語言描述算法，最大的優(yōu)點(diǎn)是容易理解，缺點(diǎn)是容易出現(xiàn)二義性，并且算法通常都很冗長流程圖用流程圖描述算法，優(yōu)點(diǎn)是直觀易懂，缺點(diǎn)是嚴(yán)密性不如程序設(shè)計(jì)語言，靈活性不如自然語言程序設(shè)計(jì)語言用程序設(shè)計(jì)語言描述的算法能由計(jì)算機(jī)直接執(zhí)行，而缺點(diǎn)是抽象性差.#include<stdio.h>intmain(){floatsum=0,x; inti=1; while(i<=10){ scanf("%f",&x); sum=sum+x i=i+1; } printf("%f",sum/10); return0;}偽代碼偽代碼是介于自然語言和程序設(shè)計(jì)語言之間的方法，它采用某一程序設(shè)計(jì)語言的基本語法，操作指令可以結(jié)合自然語言來設(shè)計(jì)。（1）sum=0,i=1;（2）如果i<=10,則執(zhí)行下面操作，否則，轉(zhuǎn)（3）。

①輸入x;

②sum=sum+x;

③i=i+1;

④轉(zhuǎn)（2），繼續(xù)執(zhí)行（3）輸出sum/10.6.1.4算法復(fù)雜度分析解決同一個(gè)問題總是存在著多種算法，而算法設(shè)計(jì)者在所花費(fèi)的時(shí)間和所使用的空間資源往往要兩者之間采取折中。算法設(shè)計(jì)者可以通過算法分析，判斷所提出的算法是否現(xiàn)實(shí)，分析算法的效率以求改進(jìn)。算法分析的內(nèi)容算法運(yùn)行所需要的時(shí)間，稱為時(shí)間復(fù)雜性算法運(yùn)行所需要的輔助空間，稱為空間復(fù)雜性撇開與計(jì)算機(jī)硬件、軟件有關(guān)的因素，可以認(rèn)為一個(gè)特定算法“運(yùn)行工作量”的大小，只依賴于問題的規(guī)模n，即輸入量的大小。如： 對(duì)一個(gè)長度是n一維數(shù)組排序，問題規(guī)模為n

對(duì)一個(gè)m*n的二維數(shù)組進(jìn)行排序，問題規(guī)模為m*n算法執(zhí)行時(shí)間T是問題規(guī)模的函數(shù)，計(jì)為T(n).

算法時(shí)間復(fù)雜度分析算法的時(shí)間復(fù)雜度估計(jì)主要評(píng)估n逐步增大時(shí)，T(n)的增長趨勢(shì)#include<stdio.h>intmain(){

floatsum=0,x; inti=1,n;

scanf("%d”,&n);while(i<=10){ scanf("%f",&x); sum=sum+x i=i+1; } printf("%f",sum/10); return0;}

n程序的執(zhí)行時(shí)間:∑語句i的執(zhí)行次數(shù)×執(zhí)行時(shí)間

i=1(=1)語句頻度:語句重復(fù)執(zhí)行的次數(shù)計(jì)算機(jī)執(zhí)行簡單操作的時(shí)間，可認(rèn)為是常量。nnnn11時(shí)間復(fù)雜度：

算法的執(zhí)行時(shí)間(所有語句的語句頻度之和）T(n)=1+n+n+n+n+1=2+4n問題規(guī)模：求解問題的輸入量

limT(n)/n=lim(2+4n)/n=1n－>∞當(dāng)問題規(guī)模n→∞時(shí)T(n)與某一量同階,稱作算法的漸近時(shí)間復(fù)雜度（asymptotictimecomplexity，隨著問題規(guī)模的增加，算法運(yùn)行時(shí)間的增長趨勢(shì)）

：記作：T(n)=O(n)O是order的簡寫例2:算法的時(shí)間復(fù)雜度分析intcount=0;

O(1)O(n)count=0;for(i=1;i<=n;i++)for(j=1;j<=n;j++)count++;O(n2)intn=8,count=0,i;for(i=1;i<=n;i++)count++;常見的時(shí)間復(fù)雜度量級(jí)有常數(shù)階O(1)（算法執(zhí)行時(shí)間是一個(gè)與問題規(guī)模無關(guān)的常數(shù)）、對(duì)數(shù)階O(log2n)、線性階O(n)、線性對(duì)數(shù)階O(nlog2n)、平方階O(n2)、立方階O(n3)、K次方階O(nk)、指數(shù)階O(2n)等等。算法的空間復(fù)雜度算法的空間復(fù)雜度是指在算法的執(zhí)行過程中，需要的輔助空間數(shù)量。輔助空間是除算法本身和輸入輸出數(shù)據(jù)所占據(jù)的空間外，算法臨時(shí)開辟的存儲(chǔ)空間。通常記作：S(n)=O(f(n))其中，n為問題規(guī)模，分析方法與算法的時(shí)間復(fù)雜度類似。輔助空間的統(tǒng)計(jì)將數(shù)組a中的元素逆置方法一：intx;for(i=0;i<n/2;i++) x=a[i];a[i]=a[n-i];a[n-i]=x;方法二：intb[]for(i=0;i<n;i++)b[i]=a[n-i];for(i=0;i<n;i++)a[i]=b[i];需要一個(gè)輔助空間，O(1)需要年n個(gè)輔助空間，O(n)6.2數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)用計(jì)算機(jī)求解問題一般包含兩個(gè)步驟：⑴抽象出問題的模型；⑵求該模型的解。對(duì)于數(shù)值問題抽象出的模型通常是數(shù)學(xué)方程，例如圖形的面積與周長等預(yù)報(bào)人口增長情況的模型更多的非數(shù)值問題是難以用數(shù)學(xué)方程來描述的。數(shù)值計(jì)算問題實(shí)例：計(jì)算課程平均成績學(xué)號(hào)姓名班級(jí)性別課程成績2021001韓華計(jì)算機(jī)21-1女832021002劉明計(jì)算機(jī)21-1男802021003劉茜計(jì)算機(jī)21-1女902021004王藝計(jì)算機(jī)21-1男75大學(xué)計(jì)算機(jī)課程成績表要完成平均成績的計(jì)算，需要將所有同學(xué)的考試成績加起來，然后除以學(xué)生總?cè)藬?shù)，即可得到該門課程的平成績。該問題屬于數(shù)值計(jì)算問題非數(shù)值計(jì)算問題實(shí)例：確定學(xué)生名次學(xué)號(hào)姓名班級(jí)性別課程成績2021001韓華計(jì)算機(jī)21-1女832021002劉明計(jì)算機(jī)21-1男802021003劉茜計(jì)算機(jī)21-1女902021004王藝計(jì)算機(jī)21-1男75大學(xué)計(jì)算機(jī)課程成績表要排出名次，需要按照考試成績對(duì)表中數(shù)據(jù)進(jìn)行降序排序。該操作不會(huì)修改表中數(shù)據(jù)的值，只會(huì)改變表中數(shù)據(jù)的排列順序。這類問題不能通過設(shè)計(jì)一個(gè)數(shù)學(xué)模型的方式來解決，屬于非數(shù)值計(jì)算問題非數(shù)值計(jì)算問題實(shí)例：微信聯(lián)系人管理6.2.2數(shù)據(jù)結(jié)構(gòu)的幾個(gè)基本概念數(shù)據(jù)（Data）:是對(duì)客觀事物的符號(hào)表示，在計(jì)算機(jī)科學(xué)中是指能輸入到計(jì)算機(jī)并被計(jì)算機(jī)程序處理的符號(hào)的總稱。數(shù)據(jù)元素（DataElement）:是數(shù)據(jù)的基本單位，也可以稱為結(jié)點(diǎn)，在計(jì)算機(jī)程序中通常作為一個(gè)整體進(jìn)行考慮。數(shù)據(jù)項(xiàng)（DataItem）：數(shù)據(jù)元素一般由若干數(shù)據(jù)項(xiàng)組成，數(shù)據(jù)項(xiàng)是構(gòu)成數(shù)據(jù)元素最小的、不可分割的單位。數(shù)據(jù)結(jié)構(gòu)（DataStructure）:

相互之間存在一定關(guān)系的數(shù)據(jù)的集合。 是數(shù)據(jù)及其元素之間相互關(guān)系的表示。邏輯結(jié)構(gòu)：數(shù)據(jù)元素之間一般存在某種特定的關(guān)系，這種關(guān)系稱為數(shù)據(jù)的邏輯結(jié)構(gòu)。物理結(jié)構(gòu)（存儲(chǔ)結(jié)構(gòu)）：數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)內(nèi)存中的表示形式。包括數(shù)據(jù)元素的表示和其關(guān)系的表示。邏輯結(jié)構(gòu)線性結(jié)構(gòu)（linearstructure）樹型結(jié)構(gòu)（treestructure）圖結(jié)構(gòu)（graphstructure）集合（set）線性結(jié)構(gòu)實(shí)例學(xué)號(hào)姓名班級(jí)性別課程成績2021001韓華計(jì)算機(jī)21-1女832021002劉明計(jì)算機(jī)21-1男802021003劉茜計(jì)算機(jī)21-1女902021004王藝計(jì)算機(jī)21-1男75線性關(guān)系具有以下特點(diǎn)：（1）有且僅有一個(gè)開始結(jié)點(diǎn)和一個(gè)終端結(jié)點(diǎn)（注：一個(gè)結(jié)點(diǎn)即為一個(gè)數(shù)據(jù)元素）。（2）其余所有結(jié)點(diǎn)都只有一個(gè)直接前驅(qū)和一個(gè)直接后繼。樹結(jié)構(gòu)：樹結(jié)構(gòu)具有以下特點(diǎn)：（1）只有一個(gè)結(jié)點(diǎn)沒有直接前驅(qū)。（2）可以有多個(gè)結(jié)點(diǎn)沒有直接后繼。（3）樹中的每個(gè)結(jié)點(diǎn)，如果有直接前驅(qū)，直接前驅(qū)只有一個(gè)；如果有直接后繼，直接后繼可以有多個(gè)。圖結(jié)構(gòu)在圖結(jié)構(gòu)中一個(gè)結(jié)點(diǎn)可以有0個(gè)或多個(gè)直接前驅(qū)和直接后繼。ABDCAEDCBDACBE樹狀結(jié)構(gòu)圖或網(wǎng)狀結(jié)構(gòu)CBDA集合線性結(jié)構(gòu)數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)計(jì)算機(jī)的主存儲(chǔ)器的特性其存儲(chǔ)空間提供了一種具有非負(fù)整數(shù)地址編碼的，相鄰單元的集合，其基本的存儲(chǔ)單元是字節(jié)計(jì)算機(jī)的指令具有按地址隨機(jī)訪問存儲(chǔ)空間內(nèi)任意單元的能力，訪問不同地址所需的訪問時(shí)間基本相同數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)又稱物理結(jié)構(gòu)，是數(shù)據(jù)及其邏輯結(jié)構(gòu)在計(jì)算機(jī)中的表示存儲(chǔ)結(jié)構(gòu)的分類：1.順序結(jié)構(gòu) 2.鏈?zhǔn)浇Y(jié)構(gòu)順序（sequential）存儲(chǔ)用一塊無空隙的存儲(chǔ)區(qū)域存儲(chǔ)數(shù)據(jù)稱為順序存儲(chǔ)順序存儲(chǔ)把一組結(jié)點(diǎn)存儲(chǔ)在按地址相鄰的順序存儲(chǔ)單元里，結(jié)點(diǎn)間的邏輯后繼關(guān)系用存儲(chǔ)單元的自然順序關(guān)系來表達(dá)鏈?zhǔn)剑╨inked）存儲(chǔ)ABCF

DE6.2.5幾種常見的數(shù)據(jù)結(jié)構(gòu)線性表?xiàng)ｊ?duì)列二叉樹線性表及其基本操作由0個(gè)或多個(gè)具有線性邏輯關(guān)系的數(shù)據(jù)元素組成的一個(gè)有限序列稱為線性表(LinearList)?？梢圆捎孟旅娴耐ㄓ眯问矫枋鲆粋€(gè)線表：L=（a1,a2,a3,……,an）在上述形式化的描述中,ai代表一個(gè)數(shù)據(jù)元素，下標(biāo)i代表數(shù)據(jù)元素在線性表中的編號(hào)?？梢圆捎庙樞虼鎯?chǔ)結(jié)構(gòu)或鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)存儲(chǔ)一個(gè)線性表順序表采用順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ)的線性表稱為順序表。順序存儲(chǔ)是利用一維數(shù)組實(shí)現(xiàn)的。順序表中查找第i個(gè)數(shù)據(jù)元素根據(jù)順序存儲(chǔ)的特點(diǎn)，可以直接利用順序表中第一個(gè)數(shù)據(jù)元素的地址（用loc(a1)表示），計(jì)算出順序表中第i個(gè)數(shù)據(jù)元素的地址（用loc(ai)表示）,計(jì)算公式見公式（1）：loc(ai)=loc(a1)+(i-1)*c （公式1）公式（1）中的c是一個(gè)整數(shù)，表示每個(gè)數(shù)據(jù)元素所占內(nèi)存大小。算法的時(shí)間復(fù)雜度為O(1)。順序表中插入第i個(gè)數(shù)據(jù)元素插入操作是指在長度為n的順序表中插入一個(gè)數(shù)據(jù)元素，插入之后順序表的長度變?yōu)閚+1。時(shí)間復(fù)雜度為O(n)順序表中刪除第i個(gè)數(shù)據(jù)元素刪除操作是指在長度是n的順序表中刪除一個(gè)數(shù)據(jù)元素，刪除之后順序表的長度變?yōu)閚-1。刪除操作可以按位置刪除，也可以按值刪除。按位置刪除時(shí)，需要指明刪除的位置；按值刪除時(shí)，需要查找要?jiǎng)h除的元素在順序表中的位置，之后再進(jìn)行刪除。時(shí)間復(fù)雜度為O(n)單鏈表及基本操作單鏈表中查找第i個(gè)數(shù)據(jù)元素利用工作指針移動(dòng)的次數(shù)評(píng)估算法的時(shí)間復(fù)雜度。分析這一查找過程可以看到，查找操作所需要移動(dòng)指針的次數(shù)與單鏈表的長度成正比該查找算法的時(shí)間復(fù)雜度為度為O(n)單鏈表中插入第i個(gè)數(shù)據(jù)元素單鏈中第5個(gè)元素的位置上插入88時(shí)間復(fù)雜度也為O(n)單鏈表中刪除第i個(gè)數(shù)據(jù)元素單鏈中刪除第5個(gè)元素的操作過程。時(shí)間復(fù)雜度也為O(n)雙鏈表可以采用雙鏈表存儲(chǔ)一個(gè)線性表。在雙鏈表中，每個(gè)結(jié)點(diǎn)既存儲(chǔ)了后繼結(jié)點(diǎn)的地址，又存儲(chǔ)了其前驅(qū)結(jié)點(diǎn)的地址。雙鏈表中插入第i個(gè)數(shù)據(jù)元素時(shí)間復(fù)雜度為O(n)雙鏈表中刪除第i個(gè)數(shù)據(jù)元素時(shí)間復(fù)雜度為O(n)棧是僅允許在線性表的同一端進(jìn)行插入或刪除操作的線性表允許插入或刪除操作的這一端稱為棧頂,另一端稱為棧底棧具有FILO（FirstInLastOut）的特點(diǎn)。a1a2a3入棧出棧棧底棧頂插入：入棧、進(jìn)棧、壓棧刪除：出棧、彈棧棧頂棧頂棧的示意圖棧的操作特性：后進(jìn)先出a1a2a3入棧出棧棧底棧頂插入：入棧、進(jìn)棧、壓棧刪除：出棧、彈棧棧頂棧的示意圖例：有三個(gè)元素按a、b、c的次序依次進(jìn)棧，且每個(gè)元素只允許進(jìn)一次棧，則可能的出棧序列有多少種？棧底棧頂ab棧頂c棧頂情況1：棧底棧頂ab棧頂c棧頂出棧序列：c出棧序列：c、b出棧序列：c、b、a例：有三個(gè)元素按a、b、c的次序依次進(jìn)棧，且每個(gè)元素只允許進(jìn)一次棧，則可能的出棧序列有多少種？情況1：棧底棧頂ab棧頂出棧序列：b情況2：例：有三個(gè)元素按a、b、c的次序依次進(jìn)棧，且每個(gè)元素只允許進(jìn)一次棧，則可能的出棧序列有多少種？棧底a出棧序列：b出棧序列：b、c出棧序列：b、c、ac棧頂棧頂注意：棧只是對(duì)表插入和刪除操作的位置進(jìn)行了限制，并沒有限定插入和刪除操作進(jìn)行的時(shí)間。例：有三個(gè)元素按a、b、c的次序依次進(jìn)棧，且每個(gè)元素只允許進(jìn)一次棧，則可能的出棧序列有多少種？情況2：隊(duì)列空隊(duì)列：不含任何數(shù)據(jù)元素的隊(duì)列。

隊(duì)列：只允許在一端進(jìn)行插入操作，而另一端進(jìn)行刪除操作的線性表。允許插入（也稱入隊(duì)、進(jìn)隊(duì)）的一端稱為隊(duì)尾，允許刪除（也稱出隊(duì)）的一端稱為隊(duì)頭。（a1,a2,……,an）隊(duì)尾隊(duì)頭a1a2a3入隊(duì)隊(duì)尾隊(duì)頭出隊(duì)隊(duì)頭隊(duì)列的操作特性：先進(jìn)先出(FIFO,LILO)二叉樹二叉樹中包含n(n>=0)個(gè)結(jié)點(diǎn)。n為0時(shí)，二叉樹是一棵空樹。非空的二叉樹中包含一個(gè)樹根；除根結(jié)點(diǎn)外，其余的結(jié)點(diǎn)分為兩個(gè)互不相交的子集，分別稱為根結(jié)點(diǎn)的左子樹和右子樹。二叉樹的基本形態(tài)Ф空二叉樹只有一個(gè)根結(jié)點(diǎn)左子樹根結(jié)點(diǎn)只有左子樹右子樹根結(jié)點(diǎn)只有右子樹左子樹右子樹根結(jié)點(diǎn)同時(shí)有左右子樹結(jié)點(diǎn)的度：結(jié)點(diǎn)所擁有的子樹的個(gè)數(shù)。葉子結(jié)點(diǎn)：度為0的結(jié)點(diǎn)，也稱為終端結(jié)點(diǎn)。分支結(jié)點(diǎn)：度不為0的結(jié)點(diǎn)，也稱為非終端結(jié)點(diǎn)。孩子、雙親：樹中某結(jié)點(diǎn)子樹的根結(jié)點(diǎn)稱為這個(gè)結(jié)點(diǎn)的孩子結(jié)點(diǎn)，這個(gè)結(jié)點(diǎn)稱為它孩子結(jié)點(diǎn)的雙親結(jié)點(diǎn)；兄弟：具有同一個(gè)雙親的孩子結(jié)點(diǎn)互稱為兄弟。結(jié)點(diǎn)所在層數(shù)：根結(jié)點(diǎn)的層數(shù)為1；對(duì)其余任何結(jié)點(diǎn)，若某結(jié)點(diǎn)在第k層，則其孩子結(jié)點(diǎn)在第k+1層。樹的深度：樹中所有結(jié)點(diǎn)的最大層數(shù)，也稱高度。層序編號(hào)：將樹中結(jié)點(diǎn)按照從上層到下層、同層從左到右的次序依次給他們編以從1開始的連續(xù)自然數(shù)。特殊的二叉樹斜樹1.所有結(jié)點(diǎn)都只有左子樹的二叉樹稱為左斜樹；2.所有結(jié)點(diǎn)都只有右子樹的二叉樹稱為右斜樹；3.左斜樹和右斜樹統(tǒng)稱為斜樹。1.在斜樹中，每一層只有一個(gè)結(jié)點(diǎn)；2.斜樹的結(jié)點(diǎn)個(gè)數(shù)與其深度相同。

斜樹的特點(diǎn)：ABCABC滿二叉樹在一棵二叉樹中，如果所有分支結(jié)點(diǎn)都存在左子樹和右子樹，并且所有葉子都在同一層上。滿二叉樹的特點(diǎn)：葉子只能出現(xiàn)在最下一層；只有度為0和度為2的結(jié)點(diǎn)。特殊的二叉樹CDEFGHIJKLMNO1112131415滿二叉樹不是滿二叉樹，雖然所有分支結(jié)點(diǎn)都有左右子樹，但葉子不在同一層上。滿二叉樹在同樣深度的二叉樹中結(jié)點(diǎn)個(gè)數(shù)最多滿二叉樹在同樣深度的二叉樹中葉子結(jié)點(diǎn)個(gè)數(shù)最多A1523467BCDEFGLM89特殊的二叉樹完全二叉樹對(duì)一棵具有n個(gè)結(jié)點(diǎn)的二叉樹按層序編號(hào)，如果編號(hào)為i（1≤i≤n）的結(jié)點(diǎn)與同樣深度的滿二叉樹中編號(hào)為i的結(jié)點(diǎn)在二叉樹中的位置完全相同。特殊的二叉樹CDEFGHIJKLMNO1112131415CDEFGHIJ在滿二叉樹中，從最后一個(gè)結(jié)點(diǎn)開始，連續(xù)去掉任意個(gè)結(jié)點(diǎn)，即是一棵完全二叉樹。A1523467910BCDEFGHIJK11L12M13N14O158CDEFGHIJ不是完全二叉樹，結(jié)點(diǎn)10與滿二叉樹中的結(jié)點(diǎn)10不是同一個(gè)結(jié)點(diǎn)特殊的二叉樹1.葉子結(jié)點(diǎn)只能出現(xiàn)在最下兩層，且最下層的葉子結(jié)點(diǎn)都集中在二叉樹的左部；2.完全二叉樹中如果有度為1的結(jié)點(diǎn)，只可能有一個(gè)，且該結(jié)點(diǎn)只有左孩子。

3.深度為k的完全二叉樹在k-1層上一定是滿二叉樹。完全二叉樹的特點(diǎn)CDEFGHIJ性質(zhì)1：二叉樹的第k層最多有2k-1個(gè)結(jié)點(diǎn)。性質(zhì)2：深度為k的二叉樹中最多有2k-1個(gè)結(jié)點(diǎn)；最少有k個(gè)結(jié)點(diǎn)。性質(zhì)3：在一棵二叉樹中，度為0的結(jié)點(diǎn)個(gè)數(shù)比度為2的結(jié)點(diǎn)個(gè)數(shù)多一個(gè)。性質(zhì)4：含有n個(gè)結(jié)點(diǎn)的完全二叉樹的高度為log2n。性質(zhì)5：完全二叉樹中編號(hào)是i的結(jié)點(diǎn)，如果有左兒，左兒子的編號(hào)是2×i，如果有右兒子，右兒子的編號(hào)是2×i+1；如果有父親，父親編號(hào)是i/2。【性質(zhì)1】在二叉樹的第k層上最多有2k-1個(gè)結(jié)點(diǎn)（k≥1）ABCDFEHG【性質(zhì)2】深度為m的二叉樹最多有2m-1個(gè)結(jié)點(diǎn)（m≥1）A1523467910BCDEFGHIJK11L12M13N14O158【性質(zhì)3】在任意一棵二叉樹中，若度為0的結(jié)點(diǎn)（即葉子結(jié)點(diǎn)）的個(gè)數(shù)為n0，度為2的結(jié)點(diǎn)數(shù)為n2，則n0=n2+1。

ABCDFEHG度為2的結(jié)點(diǎn)葉子結(jié)點(diǎn)性質(zhì)3：在一棵二叉樹中，如果葉子結(jié)點(diǎn)數(shù)為n0，度為2的結(jié)點(diǎn)數(shù)為n2，則有:n0＝n2＋1。

證明:設(shè)n為二叉樹的結(jié)點(diǎn)總數(shù)，n1為二叉樹中度為1的結(jié)點(diǎn)數(shù)，則有：

n＝n0＋n1＋n2

在二叉樹中，除了根結(jié)點(diǎn)外，其余結(jié)點(diǎn)都有唯一的一個(gè)分枝進(jìn)入，由于這些分枝是由度為1和度為2的結(jié)點(diǎn)射出的，一個(gè)度為1的結(jié)點(diǎn)射出一個(gè)分枝，一個(gè)度為2的結(jié)點(diǎn)射出兩個(gè)分枝，所以有：

n＝n1＋2n2＋1因此可以得到：n0＝n2＋1。在有n個(gè)結(jié)點(diǎn)的滿二叉樹中，有多少個(gè)葉子結(jié)點(diǎn)？因?yàn)樵跐M二叉樹中沒有度為1的結(jié)點(diǎn)，只有度為0的葉子結(jié)點(diǎn)和度為2的分支結(jié)點(diǎn)，所以，n＝n0+n2n0＝n2+1

即葉子結(jié)點(diǎn)n0＝（n+1）/2

性質(zhì)3：在一棵二叉樹中，如果葉子結(jié)點(diǎn)數(shù)為n0，度為2的結(jié)點(diǎn)數(shù)為n2，則有:n0＝n2＋1。

性質(zhì)4：具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為log2n+1。

證明：假設(shè)具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為k，根據(jù)完全二叉樹的定義和性質(zhì)2，有下式成立

2k-1≤n＜2k

2k-1-1…2k-12k-1———第k-1層———第k層…最少結(jié)點(diǎn)數(shù)最多結(jié)點(diǎn)數(shù)

證明：假設(shè)具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為k，根據(jù)完全二叉樹的定義和性質(zhì)2，有下式成立

2k-1≤n＜2k性質(zhì)4：具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為log2n+1。

對(duì)不等式取對(duì)數(shù)，有：

k-1≤log2n＜k即：

log2n＜k≤log2n+1由于k是整數(shù)，故必有k＝log2n+1。

性質(zhì)5：對(duì)一棵具有n個(gè)結(jié)點(diǎn)的完全二叉樹中從1開始按層序編號(hào)，則對(duì)于任意的序號(hào)為i（1≤i≤n）的結(jié)點(diǎn)（簡稱為結(jié)點(diǎn)i），有：

（1）如果i＞1， 則結(jié)點(diǎn)i的雙親結(jié)點(diǎn)的序號(hào)為

i/2；如果i＝1， 則結(jié)點(diǎn)i是根結(jié)點(diǎn)，無雙親結(jié)點(diǎn)。(2)如果2i≤n， 則結(jié)點(diǎn)i的左孩子的序號(hào)為2i； 如果2i＞n，則結(jié)點(diǎn)i無左孩子。(3)如果2i＋1≤n， 則結(jié)點(diǎn)i的右孩子的序號(hào)為2i＋1；如果2i＋1＞n，則結(jié)點(diǎn)

i無右孩子。

可以用歸納法證明其中的（2）和（3）：當(dāng)i=1時(shí)，結(jié)論成立123(2)如果2i≤n，則結(jié)點(diǎn)i的左孩子的序號(hào)為2i；如果2i＞n，則結(jié)點(diǎn)i無左孩子。

(3)如果2i＋1≤n，則結(jié)點(diǎn)i的右孩子的序號(hào)為2i＋1；如果2i＋1＞n，則結(jié)點(diǎn)i無右孩子。假設(shè)：對(duì)于序號(hào)為j(1≤j≤i)的結(jié)點(diǎn)，當(dāng)2×j≤n時(shí)，其左孩子存在且序號(hào)為2×j，當(dāng)2×j>n時(shí)，其左孩子不存在；當(dāng)2×j+1≤n時(shí)，其右孩子存在且序號(hào)為2×j+1，當(dāng)2×j+1>n時(shí)，其右孩子不存在。(2)如果2i≤n，則結(jié)點(diǎn)i的左孩子的序號(hào)為2i；如果2i＞n，則結(jié)點(diǎn)i無左孩子。

(3)如果2i＋1≤n，則結(jié)點(diǎn)i的右孩子的序號(hào)為2i＋1；如果2i＋1＞n，則結(jié)點(diǎn)i無右孩子。j2j2j+1當(dāng)i=j+1時(shí)，根據(jù)完全二叉樹的定義，若其左孩子存在，其左孩子結(jié)點(diǎn)的序號(hào)等于=2×i，且有2×i≤n；如果2×i>n，則左孩子不存在。若右孩子結(jié)點(diǎn)存在，右孩子結(jié)點(diǎn)的序號(hào)為2×i+1，且有2×i+1≤n；如果2×i+1>n，則右孩子不存在。故（2）和（3）得證。j2j2j+1i=j+12i2i+1由（2）和（3）我們可以很容易證明（1）。如果i＝1，則結(jié)點(diǎn)i是根結(jié)點(diǎn)，無雙親結(jié)點(diǎn)。如果i＞1，則結(jié)點(diǎn)i的雙親結(jié)點(diǎn)的序號(hào)為

[i/2]；

i2i2i+1118910456723對(duì)一棵具有n個(gè)結(jié)點(diǎn)的完全二叉樹中從1開始按層序編號(hào)，則結(jié)點(diǎn)i的雙親結(jié)點(diǎn)為

i/2；結(jié)點(diǎn)i的左孩子為2i；結(jié)點(diǎn)i的右孩子為2i＋1。

性質(zhì)5表明，在完全二叉樹中，結(jié)點(diǎn)的層序編號(hào)反映了結(jié)點(diǎn)之間的邏輯關(guān)系。二叉樹的遍歷操作

二叉樹的遍歷是指從根結(jié)點(diǎn)出發(fā)，按照某種次序訪問二叉樹中的所有結(jié)點(diǎn)，使得每個(gè)結(jié)點(diǎn)被訪問一次且僅被訪問一次。抽象操作，可以是對(duì)結(jié)點(diǎn)進(jìn)行的各種處理，這里簡化為輸出結(jié)點(diǎn)的數(shù)據(jù)。二叉樹的遍歷方式：DLR、LDR、LRD、DRL、RDL、RLD

如果限定先左后右，則二叉樹遍歷方式有三種：前序：DLR中序：LDR后序：LRD層序遍歷：按二叉樹的層序編號(hào)的次序訪問各結(jié)點(diǎn)。

考慮二叉樹的組成：根結(jié)點(diǎn)D左子樹L右子樹R二叉樹前序（根）遍歷若二叉樹為空，則空操作返回；否則：①訪問根結(jié)點(diǎn)；②前序遍歷根結(jié)點(diǎn)的左子樹；③前序遍歷根結(jié)點(diǎn)的右子樹。前序遍歷序列：ABDGCEFABCDEFG中序（根）遍歷若二叉樹為空，則空操作返回；否則：①中序遍歷根結(jié)點(diǎn)的左子樹；②訪問根結(jié)點(diǎn)；③中序遍歷根結(jié)點(diǎn)的右子樹。

中序遍歷序列：DGBAECFABCDEFG后序（根）遍歷若二叉樹為空，則空操作返回；否則：①后序遍歷根結(jié)點(diǎn)的左子樹；②后序遍歷根結(jié)點(diǎn)的右子樹。③訪問根結(jié)點(diǎn)；后序遍歷序列：GDBEFCAABCDEFG層序遍歷二叉樹的層次遍歷是指從二叉樹的第一層（即根結(jié)點(diǎn)）開始，從上至下逐層遍歷，在同一層中，則按從左到右的順序?qū)Y(jié)點(diǎn)逐個(gè)訪問。

層序遍歷序列：ABCDEFGABCDEFG--/+*abcdef二叉樹遍歷操作練習(xí)前序遍歷結(jié)果：-+a*b-cd/ef中序遍歷結(jié)果：a+b*c-d-e/f后序遍歷結(jié)果：abcd-*+ef/-6.3常見的幾種算法查找算法排序算法枚舉、遞推、貪心、分治等算法查找算法順序查找算法折半查找算法順序查找是指從數(shù)組的一端開始，依次將要查找的數(shù)據(jù)元素與數(shù)組中的數(shù)據(jù)元素進(jìn)行比較的過程。折半查找在有序表中（low,high,low<=high），取中間記錄作為比較對(duì)象，若給定值與中間記錄的關(guān)鍵碼相等，則查找成功；若給定值小于中間記錄的關(guān)鍵碼，則在中間記錄的左半?yún)^(qū)繼續(xù)查找；若給定值大于中間記錄的關(guān)鍵碼，則在中間記錄的右半?yún)^(qū)繼續(xù)查找。不斷重復(fù)上述過程，直到查找成功，或所查找的區(qū)域無記錄，查找失敗。折半查找的基本思想

[r1………rmid-1]rmid[rmid+1………rn]

如果k<rmid

如果k>rmid查找左半?yún)^(qū)查找右半?yún)^(qū)k（mid=(1+n)/2）例：查找值為14的記錄的過程：

012345678910111213

7141821232931353842464952low=1high=13mid=7

high=6mid=3

high=2

mid=1

31>1418>147<14low=2mid=2

14=14例：查找值為22的記錄的過程：

012345678910111213

7141821232931353842464952low=1high=13mid=7

high=6mid=3

high=4

mid=5

31>2218<2223>22low=4mid=4

21<22low=5low>high排序：給定一組記錄的集合{r1,r2,……,rn}，其相應(yīng)的關(guān)鍵碼分別為{k1,k2,……,kn}，排序是將這些記錄排列成順序?yàn)閧rs1,rs2,……,rsn}的一個(gè)序列，使得相應(yīng)的關(guān)鍵碼滿足ks1≤ks2≤……≤ksn（稱為升序）或ks1≥ks2≥……≥ksn（稱為降序）。正序：待排序序列中的記錄已按關(guān)鍵碼排好序。逆序（反序）：待排序序列中記錄的排列順序與排好序的順序正好相反。趟：在排序過程中，將待排序的記錄序列掃描一遍稱為一趟。 通常，一次排序過程需要進(jìn)行多趟掃描才能完成排序的基本概念排序的分類-根據(jù)排序過程中所進(jìn)行的基本操作分：1.基于比較：基本操作——關(guān)鍵碼的比較和記錄的移動(dòng)，其最差時(shí)間下限已經(jīng)被證明為O（nlog2n）。2.

不基于比較：根據(jù)關(guān)鍵碼的分布特征。比如，桶式排序，基數(shù)排序（多關(guān)鍵字排序）排序的基本概念基于比較的內(nèi)排序1.插入排序2.交換排序3.選擇排序4.歸并排序不基于比較的內(nèi)排序1.分配排序 桶式排序 基數(shù)排序時(shí)間復(fù)雜性：基本操作。內(nèi)排序在排序過程中的基本操作：⑴比較：關(guān)鍵碼之間的比較；⑵移動(dòng)：記錄從一個(gè)位置移動(dòng)到另一個(gè)位置。2.空間復(fù)雜性：

輔助存儲(chǔ)空間。輔助存儲(chǔ)空間是指在數(shù)據(jù)規(guī)模一定的條件下，除了存放待排序記錄占用的存儲(chǔ)空間之外，執(zhí)行算法所需要的其他存儲(chǔ)空間。排序算法的性能基本思想：在插入第i（i＞1）個(gè)記錄時(shí)，前面的i-1個(gè)記錄已經(jīng)排好序。直接插入排序有序序列無序序列r1r2ri-1rirnri+1…………r'1r'2r'i-1r'i……rnri+1……基本思想：在插入第i（i＞1）個(gè)記錄時(shí)，前面的i-1個(gè)記錄已經(jīng)排好序。（1）如何構(gòu)造初始的有序序列？（2）如何查找待插入記錄的插入位置?直接插入排序需解決的關(guān)鍵問題?直接插入排序過程示例

r0123456211825221025*212125i=218221025*25i=318221025*2225222110252115102525*2521151025*252118151018181025*i=418i=61825*i=5直接插入排序算法性能分析最好情況下（正序）：

12345時(shí)間復(fù)雜度為O(n)。比較次數(shù)：n-1移動(dòng)次數(shù)：2(n-1)123451234512345123452345直接插入排序算法性能分析最好情況下（正序）：

比較次數(shù)：n-1移動(dòng)次數(shù)：2(n-1)最壞情況下（逆序或反序）：時(shí)間復(fù)雜度為O(n2)。54321453213452123451123454321比較次數(shù)：移動(dòng)次數(shù)：2)1)(2(2-+=?=nnini2)1)(4(1-+=+?nnin2=i）（時(shí)間復(fù)雜度為O(n)。平均情況下（隨機(jī)排列）：

直接插入排序算法性能分析時(shí)間復(fù)雜度為O(n2)。比較次數(shù)：移動(dòng)次數(shù)：4)1)(4(-+=?nnn2=i4)1)(2(2-+=?=nnnii2（21+i）交換排序的主要操作是交換，其主要思想是：在待排序列中選兩個(gè)記錄，將它們的關(guān)鍵碼相比較，如果反序（即排列順序與排序后的次序正好相反），則交換它們的存儲(chǔ)位置。

交換排序反序則交換rirj交換類排序的兩種方法冒泡排序快速排序起泡排序基本思想：兩兩比較相鄰記錄的關(guān)鍵碼，如果反序則交換，直到?jīng)]有反序的記錄為止。

rj

rj+1ri+1≤……

≤rn-1≤rn

無序區(qū)有序區(qū)1≤j≤i-1已經(jīng)位于最終位置反序則交換05981269385381起泡排序過程示例

059812693853810598126938538105981269385381起泡排序的時(shí)間性能分析最好情況（正序）：比較次數(shù)：n-1移動(dòng)次數(shù)：012345時(shí)間復(fù)雜度為O(n)。12345最壞情況（反序）：起泡排序的時(shí)間性能分析最好情況（正序）：比較次數(shù)：n-1移動(dòng)次數(shù)：054321時(shí)間復(fù)雜度為O(n)；時(shí)間復(fù)雜度為O(n2)。43215321452134512345比較次數(shù)：移動(dòng)次數(shù)：2)1(1-=?=nn(n-i)n-1i2)1(1-=?=n3n3(n-i)n-1i平均情況：時(shí)間復(fù)雜度為O(n2)。選擇排序的主要操作是選擇，其主要思想是：每趟排序在當(dāng)前待排序序列中選出關(guān)鍵碼最小的記錄，添加到有序序列中。

有序序列r1r2ri-1rirnrk…………無序序列rnri+1r1r2ri-1……riri……交換最小記錄選擇排序簡單選擇排序示例0821i=2最小者08交換21,08最小者16交換25,16最小者21交換49,212128i=12516490808i=3210828492128491625161625i=4最小者25交換25,28i=5最小者28不交換簡單選擇排序示例492108281625254921081628252849210816282528無序區(qū)只有一個(gè)記錄歸并排序歸并排序的主要操作是歸并，其主要思想是：將若干有序序列逐步歸并，最終得到一個(gè)有序序列。

歸并排序歸并：將兩個(gè)或兩個(gè)以上的有序序列合并成一個(gè)有序序列的過程。二路歸并排序60203154455652060531445565

60203154455655203160

4455655203144556065二路歸并排序算法的性能分析時(shí)間性能：一趟歸并操作是將r[1]~r[n]中相鄰的長度為h的有序序列進(jìn)行兩兩歸并，并把結(jié)果存放到r1[1]~r1[n]中，這需要O(n)時(shí)間。整個(gè)歸并排序需要進(jìn)行趟，因此，總的時(shí)間代價(jià)是O(nlog2n)。這是歸并排序算法的最好、最壞、平均的時(shí)間性能?？臻g性能：算法在執(zhí)行時(shí)，需要占用與原始記錄序列同樣數(shù)量的存儲(chǔ)空間，因此空間復(fù)雜度為O(n)。éùn2log桶式排序假設(shè)待排序的記錄的值在0~m-1之間設(shè)置m個(gè)桶，依次掃描待排序的記錄，R[1]，…，R[n-1]，把關(guān)鍵字等于k的記錄全都裝入到第k個(gè)箱子里(分配)，然后按序號(hào)依次將各非空的箱子首尾連接起來(收集)。

3151321526338分/p>

680123456789收集1313233515268桶式排序分析特點(diǎn)：需要較多的桶時(shí)間復(fù)雜性一次分配，O(n)一次收集，O(m)O(n+m)空間復(fù)雜性O(shè)(m)基數(shù)排序每張撲克牌有兩個(gè)“關(guān)鍵碼”：花色和面值。其有序關(guān)系為：

花色：

面值：2

<3<4<5<6<7<8<9<10<J<Q<K<A基數(shù)排序“花色”優(yōu)先及高于“面值”方法一：先按花色分成4堆；然后，每堆再按“面值”排；最后，收成一堆。

1,2,3…K

1,2,3…K

1,2,3…K

1,2,3…K“花色”優(yōu)先及高于“面值”方法二？ 先按面值分成13堆；收成一堆。再按花色分成四堆，最后，收成一堆。A

2

3

4

5

6

7

8

9

10

J

Q

K

1,2,3…K

1,2,3…K

1,2,3…K

1,2,3…K基數(shù)排序基數(shù)排序（低位優(yōu)先）基數(shù)排序是典型的LSD排序方法，利用“分配”和“收集”兩種運(yùn)算對(duì)單關(guān)鍵碼進(jìn)行排序?；舅枷霃年P(guān)鍵字的最“低位”開始，將關(guān)鍵字分配到r(基數(shù)）個(gè)堆（桶）中；按桶的編號(hào)將關(guān)鍵字收集起來；然后，以“次低位”將關(guān)鍵字又分配到r個(gè)桶中；再收集，……，重復(fù)直到“