算法和數(shù)據(jù)結(jié)構(gòu)

程序設(shè)計(jì)=計(jì)算機(jī)編程語(yǔ)言+數(shù)據(jù)結(jié)構(gòu)+算法數(shù)據(jù)結(jié)構(gòu)是指數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)，而算法則是對(duì)數(shù)據(jù)運(yùn)算的描述。程序設(shè)計(jì)的實(shí)質(zhì)是對(duì)實(shí)際問(wèn)題選擇一種好的數(shù)據(jù)結(jié)構(gòu)，加之設(shè)計(jì)一個(gè)好的算法。第一頁(yè)，共七十九頁(yè)，編輯于2023年，星期三算法的定義算法的要素算法的表示算法與計(jì)算機(jī)程序的關(guān)系算法設(shè)計(jì)的基本方法對(duì)算法的評(píng)價(jià)第二頁(yè)，共七十九頁(yè)，編輯于2023年，星期三算法的定義

一組明確的可執(zhí)行步驟的有序集合例：輸入兩個(gè)正整數(shù)m和n(m>n),求它們的最大公約數(shù),記為god(m,n)。根據(jù)歐幾里德算法：若r是m÷n的余數(shù),則gcd(m,n)=gcd(n,r)第三頁(yè)，共七十九頁(yè)，編輯于2023年，星期三適合計(jì)算機(jī)實(shí)現(xiàn)的算法(輾轉(zhuǎn)相除法)：如m=28,n=8,則god(28,8)=god(8,4)=god(4,0)=4算法描述自然語(yǔ)言：輸入m,n(m>n)；求m/n的余數(shù)r；如果r≠0則將n放入m，r放入n，轉(zhuǎn)第2步繼續(xù)；如果r=0則轉(zhuǎn)第4步輸出最大公約數(shù)n。第四頁(yè)，共七十九頁(yè)，編輯于2023年，星期三開(kāi)始mmodn→rn→mr→n是否結(jié)束打印n輸入m,nr=0?流程圖：第五頁(yè)，共七十九頁(yè)，編輯于2023年，星期三算法的特征有窮性（finiteness）--能在有限時(shí)間內(nèi)做完；確定性（definiteness）--每一步驟都有明確定義；可行性（effectiveness）--能實(shí)現(xiàn)和達(dá)到預(yù)期目的；信息性（information）--能提供足夠的情報(bào)，具有輸入、輸出。算法的要素精確,簡(jiǎn)單和抽象分級(jí)第六頁(yè)，共七十九頁(yè)，編輯于2023年，星期三算法的表示流程圖N-S圖偽碼程序流程圖 N－S圖

偽碼第七頁(yè)，共七十九頁(yè)，編輯于2023年，星期三算法與計(jì)算機(jī)程序算法是邏輯步驟計(jì)算機(jī)程序是使用某種編程語(yǔ)言表達(dá)算法第八頁(yè)，共七十九頁(yè)，編輯于2023年，星期三算法設(shè)計(jì)的基本方法列舉法---根據(jù)提出的問(wèn)題列舉所有可能的情況，并用問(wèn)題中給定的條件檢驗(yàn)?zāi)男┦切枰模男┦遣恍枰?；遞推法---從已知的初始條件出發(fā)，逐次地推出所要求的各中間結(jié)果和最后結(jié)果；減半遞推法---工程上常用的分治法，即將問(wèn)題的規(guī)模減半來(lái)解，最后重復(fù)“減半”的過(guò)程；第九頁(yè)，共七十九頁(yè)，編輯于2023年，星期三遞歸法

---首先將問(wèn)題逐層分解最后歸結(jié)為一些最簡(jiǎn)單的問(wèn)題，解決這些最簡(jiǎn)單問(wèn)題后再沿著原來(lái)分解的逆過(guò)程逐步進(jìn)行綜合?；厮莘?--在處理復(fù)雜數(shù)據(jù)結(jié)構(gòu)時(shí)，通過(guò)對(duì)問(wèn)題的分析找出一個(gè)解決問(wèn)題的線索，然后沿著次線索逐步試探，若失敗就逐步回退并換別的路線再進(jìn)行試探；歸納法---通過(guò)列舉足夠多的特殊情況發(fā)現(xiàn)其中一些規(guī)律，經(jīng)過(guò)分析最終找出一般的關(guān)系；第十頁(yè)，共七十九頁(yè)，編輯于2023年，星期三算法舉例第十一頁(yè)，共七十九頁(yè)，編輯于2023年，星期三輸入一個(gè)數(shù)maxn=2當(dāng)n<=10成立輸入一個(gè)數(shù)xx>maxymax=xn=n+1輸出其中的最大值max

輸入十個(gè)數(shù)，找出最大數(shù)輸出（遞推法）第十二頁(yè)，共七十九頁(yè)，編輯于2023年，星期三假定一對(duì)剛出生的小兔子，一個(gè)月后就能長(zhǎng)成大兔子，再過(guò)一個(gè)月后就開(kāi)始生小兔子，并且也正好生一對(duì)兔子。問(wèn)在沒(méi)有兔子死亡的情況下，一對(duì)初生的兔子一年后可繁殖成多少對(duì)兔子。（遞推法）解：用F(n)表示第n個(gè)月的兔子對(duì)數(shù)。第一個(gè)月：F(1)=1第二個(gè)月：F(2)=F(1)+0=1第三個(gè)月：F(3)=F(2)+1=2第四個(gè)月：F(4)=F(3)+1=3第五個(gè)月：F(5)=F(4)+2=5第六個(gè)月：F(6)=F(5)+3=8第七個(gè)月：F(7)=F(6)+5=13第十三頁(yè)，共七十九頁(yè)，編輯于2023年，星期三遞推到一年后即第十三個(gè)月，得Fibonacci數(shù)列：1，1，2，3，5，8，13，21，34，55，89，144，233分析可知：第n個(gè)月的兔子對(duì)數(shù)由兩部分組成：一是第n-1

個(gè)月的兔子對(duì)數(shù)；二是第n-2

個(gè)月的兔子對(duì)數(shù)所以得遞推關(guān)系為

F(1)=1F(2)=1…

F(n)=F(n-1)+F(n-2)n=3,4,…第十四頁(yè)，共七十九頁(yè)，編輯于2023年，星期三求Fibonacci數(shù)列流程圖開(kāi)始F1=1,F2=1,n=3n<14F3=F1+F2

F1=F2,F2=F3n=n+1輸出Fn結(jié)束NY第十五頁(yè)，共七十九頁(yè)，編輯于2023年，星期三設(shè)每只母雞值3元，每只公雞值2元，每只小雞值0.5元?，F(xiàn)要用100元錢買100只雞，設(shè)計(jì)買雞方案算法。（列舉法）解：設(shè)買母雞I只，買公雞J只，買小雞K只，則有第十六頁(yè)，共七十九頁(yè)，編輯于2023年，星期三猴子吃桃子：小猴在一天摘了若干個(gè)桃子，當(dāng)天吃掉一半多一個(gè)；第二天接著吃了剩下的桃子的一半多一個(gè)；以后每天都吃尚存桃子的一半零一個(gè)，到第7天早上要吃時(shí)只剩下一個(gè)了，問(wèn)小猴那天共摘下了多少個(gè)桃子？設(shè)第n天的桃子為Ｘn，那么它是前一天的桃子數(shù)Ｘn-1的二分之一減一。遞推關(guān)系為：

第7天：1第6天：4第5天：10第4天：22第3天：46第2天：94第1天：190第十七頁(yè)，共七十九頁(yè)，編輯于2023年，星期三猴子吃桃子算法的流程圖i>1i=i-1x=xixi=2(x+1)輸出i,xii=7,x=1結(jié)束NY開(kāi)始第7天：1第6天：4第5天：10第4天：22第3天：46第2天：94第1天：190第十八頁(yè)，共七十九頁(yè)，編輯于2023年，星期三0f(x1)f(x2)f(x3)f(x4)x1x2x3x4減半遞推（迭代）法設(shè)方程f(x)=0在區(qū)間[x1,x2]上有一個(gè)實(shí)根，且f(x1)與f(x2)異號(hào)，用二分法求該方程在區(qū)間[x1,x2]上的實(shí)根。減半遞推過(guò)程：求中點(diǎn)：x3=1/2(x1+x2)判f(x3)是否接近0？若接近0，x3即為所求根若不接近0，則將原區(qū)間減半舍棄與f(x3)同號(hào)者：x2=x3

再求中點(diǎn)：x4=1/2(x1+x3)如此重復(fù)得：x1,x2,…,xn-1,xn當(dāng)xn與xn-1之差小于給定的誤差En時(shí)，xn即為近似解迭代關(guān)系：x3=(x1+x2)/2舍棄與f(x3)同號(hào)者：f(x3)*f(x2)>0:x2=x3;/*為下一次迭代做準(zhǔn)備*/f(x3)*f(x1)>0:x1=x3;第十九頁(yè)，共七十九頁(yè)，編輯于2023年，星期三f(x3)*f(x1)<0f(x3)=..f(x1)=..f(x2)=...x1=x3x2=x3輸入x1,x2結(jié)束NY開(kāi)始x3=(x1+x2)/2|f(x3)|>10-4輸出結(jié)果x3YN流程圖第二十頁(yè)，共七十九頁(yè)，編輯于2023年，星期三算法的評(píng)價(jià)時(shí)間復(fù)雜度：指算法中包含簡(jiǎn)單操作的次數(shù)假如，隨著問(wèn)題規(guī)模n的增長(zhǎng)，算法執(zhí)行時(shí)間的增長(zhǎng)率和f(n)的增長(zhǎng)率相同，則可記作：T(n)=O(f(n))稱T(n)為算法的(漸近)時(shí)間復(fù)雜度一般以數(shù)量級(jí)的形式給出如Ο(1),Ο(log2n),Ο(n),Ο(n2)其中Ο(1)表示算法的時(shí)間復(fù)雜度為常量，它不隨數(shù)據(jù)量n的改變而改變，如訪問(wèn)一個(gè)數(shù)據(jù)表中第一個(gè)元素時(shí)，無(wú)論該表的大小如何，其時(shí)間復(fù)雜度均為Ο(1)第二十一頁(yè)，共七十九頁(yè)，編輯于2023年，星期三Fori=1ton－1do{y=y+1;/*①*/Forj=0to2ndox=x+1;/*②*/}語(yǔ)句①的執(zhí)行次數(shù)為：n－1，語(yǔ)句②的執(zhí)行次數(shù)為：（n－1）（2n＋1）＝2n2－n－1該程序段的時(shí)間復(fù)雜度為：T（n）＝O（n－1＋2n2－n－1）＝O（n2）第二十二頁(yè)，共七十九頁(yè)，編輯于2023年，星期三空間復(fù)雜度空間復(fù)雜度主要考慮在算法運(yùn)行過(guò)程中臨時(shí)占用的存儲(chǔ)空間的大小假如，隨著問(wèn)題規(guī)模n的增大，算法運(yùn)行所需存儲(chǔ)量的增長(zhǎng)率與g(n)的增長(zhǎng)率相同，則可記作：S(n)=O(g(n))稱S(n)為算法的空間復(fù)雜度第二十三頁(yè)，共七十九頁(yè)，編輯于2023年，星期三數(shù)據(jù)結(jié)構(gòu)的基本術(shù)語(yǔ)數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)第二十四頁(yè)，共七十九頁(yè)，編輯于2023年，星期三基本術(shù)語(yǔ)數(shù)據(jù)：信息的載體，它能夠被計(jì)算機(jī)識(shí)別、存儲(chǔ)和加工處理。數(shù)據(jù)元素：是數(shù)據(jù)的基本單位。數(shù)據(jù)項(xiàng)：具有獨(dú)立意義的最小數(shù)據(jù)單位，是對(duì)數(shù)據(jù)元素屬性的描述，也稱域或字段。數(shù)據(jù)對(duì)象：指具有相同性質(zhì)的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個(gè)子集。數(shù)據(jù)處理：指對(duì)數(shù)據(jù)集合中的各元素，以各種方式進(jìn)行處理，包括對(duì)數(shù)據(jù)的插入、刪除、查找、更新、排序等基本運(yùn)算，也包括對(duì)數(shù)據(jù)元素進(jìn)行分析。第二十五頁(yè)，共七十九頁(yè)，編輯于2023年，星期三數(shù)據(jù)結(jié)構(gòu)的定義：互相有關(guān)聯(lián)的數(shù)據(jù)元素的集合一個(gè)數(shù)據(jù)結(jié)構(gòu)應(yīng)包含兩方面信息：所有數(shù)據(jù)元素的信息各數(shù)據(jù)元素之間的關(guān)系第二十六頁(yè)，共七十九頁(yè)，編輯于2023年，星期三數(shù)據(jù)結(jié)構(gòu)研究的內(nèi)容數(shù)據(jù)集合中，各種數(shù)據(jù)元素之間所固有的邏輯關(guān)系，即數(shù)據(jù)的邏輯結(jié)構(gòu)。在對(duì)數(shù)據(jù)進(jìn)行處理時(shí)，各數(shù)據(jù)元素在計(jì)算機(jī)中的存儲(chǔ)關(guān)系，即數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)。對(duì)各種數(shù)據(jù)結(jié)構(gòu)進(jìn)行的運(yùn)算，其中常用的有檢索、插入、刪除、排序等。第二十七頁(yè)，共七十九頁(yè)，編輯于2023年，星期三數(shù)據(jù)的邏輯結(jié)構(gòu)--反映數(shù)據(jù)元素之間的邏輯關(guān)系一個(gè)數(shù)據(jù)結(jié)構(gòu)可以表示為一個(gè)二元組：B=（D，R）D是數(shù)據(jù)元素的集合，R是定義在D上的二元關(guān)系的集合，反映了D中各元素之間的前驅(qū)與后繼關(guān)系二個(gè)要素?cái)?shù)據(jù)元素的集合DD上的二元關(guān)系R舉例第二十八頁(yè)，共七十九頁(yè)，編輯于2023年，星期三例1.一年四季的數(shù)據(jù)結(jié)構(gòu)。

表示為：Season=（D，R）

D=（春，夏，秋，冬）

R=（（春，夏），（夏，秋），（秋，冬））例2.n維向量X=（x1，x2，……，xn）的數(shù)據(jù)結(jié)構(gòu)。

表示為：X=（D，R）

D=（x1，x2，……，xn）

R=（（x1，x2），（x2，x3）…，（xn-1，xn））例3.家庭成員的數(shù)據(jù)結(jié)構(gòu)。

表示為：Family=（D，R）

D=（父親，兒子，女兒）

R=（（父親，兒子），（父親，女兒））第二十九頁(yè)，共七十九頁(yè)，編輯于2023年，星期三根據(jù)數(shù)據(jù)結(jié)構(gòu)中各數(shù)據(jù)元素之間的前驅(qū)與后繼關(guān)系的復(fù)雜程度，邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為線性結(jié)構(gòu)和非線性結(jié)構(gòu)。一個(gè)非空的線性數(shù)據(jù)結(jié)構(gòu)應(yīng)滿足兩個(gè)條件：有且僅有一個(gè)根結(jié)點(diǎn)（沒(méi)有前驅(qū)的結(jié)點(diǎn)）；每一個(gè)結(jié)點(diǎn)最多只有一個(gè)前驅(qū)，一個(gè)后繼；如果一個(gè)數(shù)據(jù)結(jié)構(gòu)不是線性的，則稱為非線性結(jié)構(gòu)（樹(shù)形結(jié)構(gòu)、圖形結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu)）。例1、例2屬于線性結(jié)構(gòu)，例3為非線性結(jié)構(gòu)。第三十頁(yè)，共七十九頁(yè)，編輯于2023年，星期三三種基本結(jié)構(gòu)圖示線性結(jié)構(gòu)：元素之間是一對(duì)一的關(guān)系樹(shù)形結(jié)構(gòu)：元素之間是一對(duì)多的關(guān)系(非線性)

圖形結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu)：元素之間是多對(duì)多的關(guān)系(非線性)

第三十一頁(yè)，共七十九頁(yè)，編輯于2023年，星期三數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)：即數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)存 儲(chǔ)空間中的存放形式常見(jiàn)四種：順序存儲(chǔ)結(jié)構(gòu)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)索引存儲(chǔ)結(jié)構(gòu)散列存儲(chǔ)結(jié)構(gòu)第三十二頁(yè)，共七十九頁(yè)，編輯于2023年，星期三線性表的基本概念線性表的順序存儲(chǔ)及其運(yùn)算線性表的鏈?zhǔn)酱鎯?chǔ)及其運(yùn)算第三十三頁(yè)，共七十九頁(yè)，編輯于2023年，星期三線性表的基本概念線性表是由n（n>=0）個(gè)元素a1，a2，…，an組成的有限序列，記為：（a1，a2，…，an）。數(shù)據(jù)元素（也稱為結(jié)點(diǎn)）的個(gè)數(shù)n稱為線性表的長(zhǎng)度，n=0時(shí)稱此線性表為空表。非空線性表（a1,a2,…,an）的結(jié)構(gòu)特征：若線性表非空，第一個(gè)元素?zé)o前驅(qū)；最后一個(gè)元素?zé)o后繼；其他元素僅有一個(gè)直接前驅(qū)和一個(gè)直接后繼。第三十四頁(yè)，共七十九頁(yè)，編輯于2023年，星期三線性表的順序存儲(chǔ)及其運(yùn)算線性表的順序存儲(chǔ)所有元素所占的存儲(chǔ)空間連續(xù)各數(shù)據(jù)元素在存儲(chǔ)空間中按邏輯順序依次存放ADR(ai)=ADR(a1)+(i-1)k第三十五頁(yè)，共七十九頁(yè)，編輯于2023年，星期三順序表的基本運(yùn)算順序表的插入長(zhǎng)度為n的順序表（a1,a2,…,ai,…,an），在第i個(gè)元素之前插入一個(gè)新元素x，插入后得到長(zhǎng)度為n+1的順序表（a1,a2,…,x,ai,…,an）算法：從an到ai,依次后移，然后插入x線性表的刪除

將表的第i（1≤i≤n）個(gè)結(jié)點(diǎn)刪去，使長(zhǎng)度為n的線性表（a1，…，ai-1，ai，ai+1，…，an）變成長(zhǎng)度為n-1的線性表（a1，…，ai-1，ai+1，…，an）算法：從ai+1到an,依次前移第三十六頁(yè)，共七十九頁(yè)，編輯于2023年，星期三線性表的順序存儲(chǔ)結(jié)構(gòu)具有簡(jiǎn)單、存儲(chǔ)密度大、空間利用率高、對(duì)表中任一元素可直接確定其存儲(chǔ)地址（隨機(jī)存?。⑿矢叩葍?yōu)點(diǎn)；但是也有明顯的不足：在順序表中進(jìn)行插入與刪除等操作時(shí)，需大量移動(dòng)數(shù)據(jù)元素，浪費(fèi)時(shí)間。對(duì)于大的線性表，特別是元素變動(dòng)頻繁的大線性表，不宜采用順序存儲(chǔ)結(jié)構(gòu)，而是采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。第三十七頁(yè)，共七十九頁(yè)，編輯于2023年，星期三線性表的鏈?zhǔn)酱鎯?chǔ)及其運(yùn)算鏈?zhǔn)酱鎯?chǔ)一個(gè)鏈表結(jié)點(diǎn)由兩個(gè)域構(gòu)成：數(shù)據(jù)域和指針域數(shù)據(jù)域存放數(shù)據(jù)元素值指針域指向該結(jié)點(diǎn)的后繼結(jié)點(diǎn)通過(guò)每個(gè)結(jié)點(diǎn)的指針域?qū)個(gè)結(jié)點(diǎn)按其邏輯順序連接在一起而構(gòu)成的數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)，稱為鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。用一個(gè)頭指針專門用來(lái)指向線性鏈表中的第一個(gè)結(jié)點(diǎn)，線性鏈表中最后一個(gè)元素沒(méi)有后繼，指針域?yàn)榭眨ㄓ肗ULL或0表示）。第三十八頁(yè)，共七十九頁(yè)，編輯于2023年，星期三線性鏈表的物理存儲(chǔ)狀態(tài)線性鏈表的邏輯存儲(chǔ)狀態(tài)第三十九頁(yè)，共七十九頁(yè)，編輯于2023年，星期三單鏈表的基本運(yùn)算單鏈表的結(jié)點(diǎn)插入算法：（1）找到ai-1存儲(chǔ)位置p（2）確定要插入的新結(jié)點(diǎn)的位置s（3）在新結(jié)點(diǎn)的數(shù)據(jù)域中輸入x（4）新結(jié)點(diǎn)的指針域指向結(jié)點(diǎn)ai。（5）結(jié)點(diǎn)p的指針域指向新結(jié)點(diǎn)第四十頁(yè)，共七十九頁(yè)，編輯于2023年，星期三單鏈表的結(jié)點(diǎn)刪除算法：

（1）找到ai-1的存儲(chǔ)位置p（因?yàn)樵趩捂湵碇薪Y(jié)點(diǎn)ai的存儲(chǔ)地址是在其直接前趨結(jié)點(diǎn)ai-1的指針域中）（2）找到ai的存儲(chǔ)位置r（3）令p的指針域指向ai的直接后繼結(jié)點(diǎn)（即把a(bǔ)i從鏈上摘下）（4）釋放結(jié)點(diǎn)ai的空間，將其歸還給"存儲(chǔ)池"。第四十一頁(yè)，共七十九頁(yè)，編輯于2023年，星期三棧及其基本運(yùn)算隊(duì)列及其基本運(yùn)算第四十二頁(yè)，共七十九頁(yè)，編輯于2023年，星期三棧及其基本運(yùn)算定義：堆棧（Stack）可以看成是一種“特殊的”線性表，這種線性表上的插入和刪除運(yùn)算限定在表的某一端進(jìn)行的。(1)通常稱插入、刪除的這一端為棧頂（Top），另一端稱為棧底（Bottom）。(2)當(dāng)表中沒(méi)有元素時(shí)稱為空棧。(3)棧為后進(jìn)先出的線性表，簡(jiǎn)稱為L(zhǎng)IFO表。

棧的示意圖第四十三頁(yè)，共七十九頁(yè)，編輯于2023年，星期三棧的順序存儲(chǔ)及其運(yùn)算利用一組地址連續(xù)的存儲(chǔ)單元依次存放自棧底到棧頂?shù)臄?shù)據(jù)元素。通常，棧底指針指向?？臻g的低地址一端入棧運(yùn)算首先將棧頂指針加1（即top加1）然后將新元素插入到棧頂指針指向的位置。當(dāng)棧頂指針已經(jīng)指向存儲(chǔ)空間的最后一個(gè)位置時(shí)，說(shuō)明?？臻g已滿，不可能再進(jìn)行入棧操作。這種情況稱為棧的“上溢”。上溢是一種出錯(cuò)狀態(tài)，應(yīng)設(shè)法避免。

第四十四頁(yè)，共七十九頁(yè)，編輯于2023年，星期三棧在順序存儲(chǔ)結(jié)構(gòu)下的運(yùn)算第四十五頁(yè)，共七十九頁(yè)，編輯于2023年，星期三退棧運(yùn)算首先將棧頂元素（即棧頂指針指向的元素）賦給一個(gè)指定的變量然后將棧頂指針減1（即top減1）。當(dāng)棧頂指針為0時(shí)，說(shuō)明棧空，不可能進(jìn)行退棧運(yùn)算。這種情況稱為棧的“下溢”錯(cuò)誤。讀棧頂運(yùn)算讀棧頂元素是指將棧頂元素賦給一個(gè)指定的變量。在這個(gè)運(yùn)算中，棧頂指針不會(huì)改變。當(dāng)棧頂指針為0時(shí)，說(shuō)明?？眨x不到棧頂元素。第四十六頁(yè)，共七十九頁(yè)，編輯于2023年，星期三隊(duì)列及其基本運(yùn)算定義：是只允許在一端進(jìn)行插入，而在另一端進(jìn)行刪除的運(yùn)算受限的線性表。允許刪除的一端稱為隊(duì)頭（Front），允許插入的一端稱為隊(duì)尾（Rear）。隊(duì)列亦稱作先進(jìn)先出的線性表，簡(jiǎn)稱為FIFO表。具有7個(gè)元素的隊(duì)列示意圖第四十七頁(yè)，共七十九頁(yè)，編輯于2023年，星期三插入和刪除隊(duì)列元素示意圖入隊(duì)運(yùn)算首先將新元素插入到隊(duì)尾指針指向的位置，然后將隊(duì)尾指針加1（即rear＋1）出隊(duì)運(yùn)算首先將隊(duì)首指針指向的元素賦給指定的變量，然后將隊(duì)首指針加1（即front＋1）第四十八頁(yè)，共七十九頁(yè)，編輯于2023年，星期三循環(huán)隊(duì)列及其運(yùn)算循環(huán)隊(duì)列：將隊(duì)列存儲(chǔ)空間的最后一個(gè)位置繞到第一個(gè)位置，形成邏輯上的環(huán)狀空間初始狀態(tài)為空：rear=front當(dāng)隊(duì)列滿了，也有：rear=front，需要一個(gè)標(biāo)志變量s循環(huán)隊(duì)列存儲(chǔ)空間示意圖第四十九頁(yè)，共七十九頁(yè)，編輯于2023年，星期三循環(huán)隊(duì)列出隊(duì)運(yùn)算首先將隊(duì)首指針指向的元素賦給指定的變量，然后將隊(duì)首指針加1（即front＋1），并當(dāng)front＝m＋1時(shí)置front＝1，這時(shí)如果front＝rear，則說(shuō)明隊(duì)空，應(yīng)將s置0。當(dāng)循環(huán)隊(duì)列為空時(shí)，不能進(jìn)行出隊(duì)運(yùn)算，這種情況稱為“下溢”。循環(huán)隊(duì)列及其刪除運(yùn)算示意圖第五十頁(yè)，共七十九頁(yè)，編輯于2023年，星期三循環(huán)隊(duì)列入隊(duì)運(yùn)算首先將新元素插入到隊(duì)尾指針指向的位置，然后將隊(duì)尾指針加1（即rear＋1），當(dāng)rear＝m＋1時(shí)置rear＝1，這時(shí)如果s＝0，則置s＝1，表示隊(duì)列非空。當(dāng)循環(huán)隊(duì)列非空（即s＝1）且font＝rear時(shí)，說(shuō)明循環(huán)隊(duì)列已滿，不能進(jìn)行入隊(duì)運(yùn)算，這種情況稱為“上溢”。循環(huán)隊(duì)列及其插入除運(yùn)算示意圖第五十一頁(yè)，共七十九頁(yè)，編輯于2023年，星期三樹(shù)的基本概念二叉樹(shù)及其基本性質(zhì)二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)二叉樹(shù)的遍歷第五十二頁(yè)，共七十九頁(yè)，編輯于2023年，星期三樹(shù)型結(jié)構(gòu)是以分支關(guān)系定義的層次結(jié)構(gòu)，是一種重要的非線性結(jié)構(gòu)?；靖拍疃x：樹(shù)是n個(gè)結(jié)點(diǎn)的有限集T，具有明顯的層次結(jié)構(gòu)。其中：一個(gè)特定的結(jié)點(diǎn)稱為該樹(shù)的根（root）結(jié)點(diǎn);結(jié)點(diǎn)之外的其余結(jié)點(diǎn)可分為m（m≥0）個(gè)互不相交的有限集合T1,T2,......,Tm，且其中每一個(gè)集合本身又是一棵樹(shù)，稱之為根的子樹(shù)（subtree）。只有根結(jié)點(diǎn)的樹(shù)AHGFBEDCAKMJIL一般的樹(shù)第五十三頁(yè)，共七十九頁(yè)，編輯于2023年，星期三基本術(shù)語(yǔ)結(jié)點(diǎn)的度樹(shù)的度葉子分支結(jié)點(diǎn)雙親和孩子結(jié)點(diǎn)的層樹(shù)的深度兄弟和堂兄弟祖先和子孫有序樹(shù)和無(wú)序樹(shù)森林HGFBEDCAKMJIL樹(shù)的圖形表示結(jié)點(diǎn)的度：一個(gè)結(jié)點(diǎn)的子樹(shù)數(shù)目。結(jié)點(diǎn)A的度：3結(jié)點(diǎn)C的度：1結(jié)點(diǎn)M的度：0樹(shù)的度：所有結(jié)點(diǎn)中最大的度。樹(shù)的度：3葉子：樹(shù)中度為0的結(jié)點(diǎn)。葉子：E,K,L,G,H,M,J分支結(jié)點(diǎn)：樹(shù)中度不為0的結(jié)點(diǎn)。分支結(jié)點(diǎn)：A,B,F,C,D,I雙親和孩子：結(jié)點(diǎn)的子樹(shù)的根稱為該結(jié)點(diǎn)的孩子，相應(yīng)地，該結(jié)點(diǎn)稱為孩子結(jié)點(diǎn)的雙親結(jié)點(diǎn)A是B,C,D的雙親，B,C,D是結(jié)點(diǎn)A的孩子結(jié)點(diǎn)的層：約定樹(shù)的根節(jié)點(diǎn)的層為1，其余結(jié)點(diǎn)的層是其雙親的層加1結(jié)點(diǎn)A的層：1結(jié)點(diǎn)B,C,D的層：2結(jié)點(diǎn)E,F,G的層：3樹(shù)的深度：樹(shù)中各結(jié)點(diǎn)的層的最大值。圖中的樹(shù)的深度：4兄弟和堂兄弟：同一雙親的結(jié)點(diǎn)互稱為兄弟，其雙親在同一層但不屬于同一雙親的結(jié)點(diǎn)互稱為堂兄弟。結(jié)點(diǎn)E,F,G是兄弟，G,H,I是堂兄弟祖先和子孫：一個(gè)結(jié)點(diǎn)的祖先是指從該結(jié)點(diǎn)到樹(shù)根所經(jīng)分支上的所有結(jié)點(diǎn)。一個(gè)結(jié)點(diǎn)的子樹(shù)上的所有結(jié)點(diǎn)稱為該結(jié)點(diǎn)的子孫。E的祖先有A和B，而E、F、G、K、L是B的子孫。有序樹(shù)和無(wú)序樹(shù)：如果樹(shù)中任一結(jié)點(diǎn)的各顆子樹(shù)規(guī)定從左至右是有序的，即不能互換位置，則稱該樹(shù)為有序樹(shù)，否則稱為無(wú)序樹(shù)。森林：n（n≥0）棵互不相交的樹(shù)的集合稱為森林。刪去一棵樹(shù)的根結(jié)點(diǎn)便得到一個(gè)森林；反過(guò)來(lái)，給一個(gè)森林加上一個(gè)結(jié)點(diǎn)，使原森林的各棵樹(shù)成為所加結(jié)點(diǎn)的子樹(shù)，便得到一棵樹(shù)。第五十四頁(yè)，共七十九頁(yè)，編輯于2023年，星期三

二叉樹(shù)是樹(shù)形結(jié)構(gòu)的一個(gè)重要類型。許多實(shí)際問(wèn)題抽象出來(lái)的數(shù)據(jù)結(jié)構(gòu)往往是二叉樹(shù)的形式，即使是一般的樹(shù)也能簡(jiǎn)單地轉(zhuǎn)換為二叉樹(shù)，而且二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)及其算法都較為簡(jiǎn)單，因此二叉樹(shù)顯得特別重要。二叉樹(shù)的定義定義：二叉樹(shù)是n(n≥0)個(gè)結(jié)點(diǎn)的有限集，它或者是空集(n=0)，或者由一個(gè)根結(jié)點(diǎn)及兩棵互不相交的、分別稱作這個(gè)根的左子樹(shù)和右子樹(shù)的二叉樹(shù)組成。第五十五頁(yè)，共七十九頁(yè)，編輯于2023年，星期三NLR空樹(shù)只含根結(jié)點(diǎn)NNN右子樹(shù)為空樹(shù)左子樹(shù)為空樹(shù)左右子樹(shù)均不為空樹(shù)二叉樹(shù)的五種基本形態(tài)：LR第五十六頁(yè)，共七十九頁(yè)，編輯于2023年，星期三二叉樹(shù)的基本性質(zhì)性質(zhì)1在二叉樹(shù)的第i層至多有2i-1個(gè)結(jié)點(diǎn)(i≥1)性質(zhì)2深度為k(k≥1)的二叉樹(shù)至多有2k-1個(gè)結(jié)點(diǎn)性質(zhì)3對(duì)任何一棵二叉樹(shù)T，如果其葉子結(jié)點(diǎn)數(shù)為n0,度為2的結(jié)點(diǎn)數(shù)為n2，則n0=n2+1第五十七頁(yè)，共七十九頁(yè)，編輯于2023年，星期三123456789101112131415abcdefghij兩類特殊的二叉樹(shù)：滿二叉樹(shù)：指的是深度為k且含有2k-1個(gè)結(jié)點(diǎn)的二叉樹(shù)。完全二叉樹(shù)：樹(shù)中所含的n個(gè)結(jié)點(diǎn)和滿二叉樹(shù)中編號(hào)為1至n的結(jié)點(diǎn)一一對(duì)應(yīng)。第五十八頁(yè)，共七十九頁(yè)，編輯于2023年，星期三性質(zhì)4具有n(n≥1)個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為[log2n]+1(其中[log2n]表示取log2n的整數(shù)部分)性質(zhì)5如果對(duì)一棵有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的結(jié)點(diǎn)按順序編號(hào)，則對(duì)任一結(jié)點(diǎn)i(1≤i≤n),有：（1）如果i=1,則結(jié)點(diǎn)i是二叉樹(shù)的根，無(wú)雙親；如果i>1，則其雙親是[i/2]（2）如果2i＞n，則結(jié)點(diǎn)i無(wú)左孩子；否則其左孩子是結(jié)點(diǎn)2i（3）如果2i+1＞n，則結(jié)點(diǎn)i無(wú)右孩子；否則其右孩子是結(jié)點(diǎn)2i+1第五十九頁(yè)，共七十九頁(yè)，編輯于2023年，星期三二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)完全二叉樹(shù)順序存儲(chǔ)將完全二叉樹(shù)中所有結(jié)點(diǎn)按編號(hào)順序依次存儲(chǔ)在一個(gè)地址連續(xù)的存儲(chǔ)單元中。一般二叉樹(shù)的順序存儲(chǔ)①將一般二叉樹(shù)添上一些"虛結(jié)點(diǎn)"，成為"完全二叉樹(shù)"②將各結(jié)點(diǎn)按編號(hào)順序依次存儲(chǔ)在一個(gè)地址連續(xù)的存儲(chǔ)單元中，其中"虛結(jié)點(diǎn)"用""表示完全二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu)非完全二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu)第六十頁(yè)，共七十九頁(yè)，編輯于2023年，星期三二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu)的優(yōu)缺點(diǎn)①對(duì)完全二叉樹(shù)而言，順序存儲(chǔ)結(jié)構(gòu)既簡(jiǎn)單又節(jié)省存儲(chǔ)空間。②一般的二叉樹(shù)采用順序存儲(chǔ)結(jié)構(gòu)時(shí)，雖然簡(jiǎn)單，但易造成存儲(chǔ)空間的浪費(fèi)。最壞的情況下，一個(gè)深度為k且只有k個(gè)結(jié)點(diǎn)的右單支樹(shù)需要2k-1個(gè)結(jié)點(diǎn)的存儲(chǔ)空間,空間利用率僅為k/(2k-1)。③在對(duì)順序存儲(chǔ)的二叉樹(shù)做插入和刪除結(jié)點(diǎn)操作時(shí)，要大量移動(dòng)結(jié)點(diǎn)。第六十一頁(yè)，共七十九頁(yè)，編輯于2023年，星期三二叉樹(shù)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)用鏈接方式存儲(chǔ)二叉樹(shù)時(shí)，每個(gè)結(jié)點(diǎn)除了存儲(chǔ)結(jié)點(diǎn)本身的數(shù)據(jù)外，還應(yīng)設(shè)置兩個(gè)指針域lchild和rchild，分別指向該結(jié)點(diǎn)的左孩子和右孩子。例：二叉樹(shù)的二叉鏈表：

二叉鏈表結(jié)點(diǎn)的結(jié)構(gòu)第六十二頁(yè)，共七十九頁(yè)，編輯于2023年，星期三二叉樹(shù)的遍歷“遍歷”是任何類型均有的操作。對(duì)線性結(jié)構(gòu)而言，只有一條搜索路徑(因?yàn)槊總€(gè)結(jié)點(diǎn)均只有一個(gè)后繼)，故不需要另加討論。而二叉樹(shù)是非線性結(jié)構(gòu)，每個(gè)結(jié)點(diǎn)有兩個(gè)后繼，存在多條遍歷路徑，所以就存在按什么樣的搜索路徑進(jìn)行遍歷的問(wèn)題。第六十三頁(yè)，共七十九頁(yè)，編輯于2023年，星期三二叉樹(shù)的遍歷順著某一條搜索路徑巡訪二叉樹(shù)中的每個(gè)結(jié)點(diǎn)，使得每個(gè)結(jié)點(diǎn)均被訪問(wèn)一次，而且僅被訪問(wèn)一次。

遍歷二叉樹(shù)的過(guò)程實(shí)質(zhì)是把二叉樹(shù)的各結(jié)點(diǎn)進(jìn)行線性排列的過(guò)程。假設(shè)遍歷二叉樹(shù)時(shí)訪問(wèn)結(jié)點(diǎn)的操作就是輸出結(jié)點(diǎn)數(shù)據(jù)域的值，那么遍歷的結(jié)果得到一個(gè)線性序列。第六十四頁(yè)，共七十九頁(yè)，編輯于2023年，星期三遍歷方案

從二叉樹(shù)的遞歸定義可知，一棵非空的二叉樹(shù)由根結(jié)點(diǎn)及左、右子樹(shù)這三個(gè)基本部分組成。因此，在任一給定結(jié)點(diǎn)上，可以按某種次序執(zhí)行三個(gè)操作：

（1）訪問(wèn)結(jié)點(diǎn)本身(N)，

（2）遍歷該結(jié)點(diǎn)的左子樹(shù)(L)，

（3）遍歷該結(jié)點(diǎn)的右子樹(shù)(R)。以上三種操作有六種執(zhí)行次序：

NLR、LNR、LRN、NRL、RNL、RLN。第六十五頁(yè)，共七十九頁(yè)，編輯于2023年，星期三遍歷二叉樹(shù)的執(zhí)行蹤跡

三種遞歸遍歷算法的搜索路線相同：從根結(jié)點(diǎn)出發(fā)，逆時(shí)針沿著二叉樹(shù)外緣移動(dòng)，對(duì)每個(gè)結(jié)點(diǎn)均途徑三次，最后回到根結(jié)點(diǎn)。

第六十六頁(yè)，共七十九頁(yè)，編輯于2023年，星期三先根遍歷算法：若二叉樹(shù)為空樹(shù)，則空操作；否則（1）訪問(wèn)根結(jié)點(diǎn)；（2）先根遍歷左子樹(shù)；（3）先根遍歷右子樹(shù)。先根遍歷得到的先根序列為：

ABDCEF

第六十七頁(yè)，共七十九頁(yè)，編輯于2023年，星期三中（根）序的遍歷算法：若二叉樹(shù)為空樹(shù)，則空操作；否則，（1）中根遍歷左子樹(shù)；（2）訪問(wèn)根結(jié)點(diǎn)；（3）中根遍歷右子樹(shù)。中根序列為：

DBAECF

第六十八頁(yè)，共七十九頁(yè)，編輯于2023年，星期三后（根）序的遍歷算法：若二叉樹(shù)為空樹(shù)，則空操作；否則，（1）后根遍歷左子樹(shù)；（2）后根遍歷右子樹(shù)；（3）訪問(wèn)根結(jié)點(diǎn)。后根序列為：

DBEFCA

第六十九頁(yè)，共七十九頁(yè)，編輯于2023年，星期三先根遍歷序列：

ABDFCE中根遍歷序列：

BFDACE

后根遍歷序列：

FDBECA例1：第七十頁(yè)，共七十九頁(yè)，編輯于2023年，星期三例2：先根遍歷序列：

-+a*b-cd/ef中根遍歷序列：

a+b*c-d-e/f

后根遍歷序列：abcd-*+ef/-

第七十一頁(yè)，共七十九頁(yè)，編輯于2023年，星期三ABCDEFGHK先根序列：中根序列：后根序列：A

BCD

EFGHKBDCA

EHGKFDCBHKGFE

A例3：第七十二頁(yè)，共七十九頁(yè)，編輯于2023年，星期三先根遍歷序列：

ABDHIECFGJ中根遍歷序列

HDIBEAFCJG后根遍歷序列：

HIDEBFJGCA例4：第七十三頁(yè)，共七十九頁(yè)，編輯于2023年，星期三查找的定義查找的方法第七十四頁(yè)，共七十九頁(yè)，編輯于2023年，星期三定義查找就是根據(jù)給定的值，在一組數(shù)據(jù)中確定一個(gè)其數(shù)值等于給定值的數(shù)據(jù)元素，若存在這樣的數(shù)據(jù)元素說(shuō)明查找是成功的，否則查找是不成功的。衡量查找算法好壞的標(biāo)準(zhǔn)是以平均查找比較的次數(shù)來(lái)定。查找方法順序查找折半查找序號(hào)1234567891011數(shù)據(jù)513192137566475808892成功：采用順序查找方法來(lái)查找21，需要比較4次；采用折半查找方法來(lái)查找21，需要比較3次；不成功：采用順序查找方法來(lái)查找66，需要比較11次；采果采用折半查找方法來(lái)查找66，需要比較4次；第七十五頁(yè)，共七十九頁(yè)，編輯于2023年，星期三選擇排序交換排序插入排序第七十六頁(yè)，共七十九頁(yè)，編輯于2023年，星期三排序是指將一個(gè)無(wú)序序列整理成一個(gè)按規(guī)定次序重新排列的有序序列。選擇排序

原始序列8921564885161947第1遍選擇1621564885891947第2遍選擇1619564885892147第3遍選擇1619214885895647第4遍選擇1619214785895648第5遍選擇