全國計(jì)算機(jī)等級考試二級c語言程序設(shè)計(jì)教材精講真題解析講義與視頻課程

1、全國計(jì)算機(jī)等級考試二級C+語言程序設(shè)計(jì)【教材精講+真題解析】 講義與視頻課程最新資料，WORD式，可編輯修改！目錄視頻講解教師簡介教材精講部分視頻講解第一部分公共基礎(chǔ)知識視頻講解第1章 數(shù)據(jù)結(jié)構(gòu)與算法視頻講解第2章 程序設(shè)計(jì)基礎(chǔ)視頻講解第3章 軟件工程基礎(chǔ)視頻講解第4章 數(shù)據(jù)庫設(shè)計(jì)基礎(chǔ)視頻講解第二部分 C+S言程序設(shè)計(jì)視頻講解第1章 C+鋪言人述視頻講解第2章 數(shù)據(jù)類型、運(yùn)算符和表達(dá)式視頻講解第3章 基本控制結(jié)構(gòu)視頻講解第4章 數(shù)組、指專f與引用視頻講解第5章函數(shù)視頻講解第6章 類和對象視頻講解第7章繼承和派生視頻講解第8章運(yùn)算符重載視頻講解第9章模板視頻講解第10章 C+毓視頻講解第11章考

2、試指導(dǎo)視頻講解真題解析部分全國計(jì)算機(jī)等級考試二級 C+鋪言程序設(shè)計(jì)真題及詳解（一）全國計(jì)算機(jī)等級考試二級 C+吾言程序設(shè)計(jì)真題及詳解（二）全國計(jì)算機(jī)等級考試二級 C+吾言程序設(shè)計(jì)真題及詳解（三）全國計(jì)算機(jī)等級考試二級 C+吾言程序設(shè)計(jì)真題及詳解（四）教材精講部分視頻講解第一部分公共基礎(chǔ)知識視頻講解考試形式1 .公共基礎(chǔ)知識不單獨(dú)考試，與其他二級科目組合在一起，作為二級科目考核內(nèi)容的一部分。2 .考試方式為上機(jī)考試，10道選擇題，占10分。大綱基本要求1 .掌握算法的基本概念。2 .掌握基本數(shù)據(jù)結(jié)構(gòu)及其操作。3 .掌握基本排序和查找算法。4 .掌握逐步求精的結(jié)構(gòu)化程序設(shè)計(jì)方法。5 .掌握軟件工程

3、的基本方法， 具有初步應(yīng)用相關(guān)技術(shù)進(jìn)行軟件開發(fā)的能力。6 .掌握數(shù)據(jù)庫的基本知識，了解關(guān)系數(shù)據(jù)庫的設(shè)計(jì)。知識點(diǎn)分布1 .數(shù)據(jù)結(jié)構(gòu)與算法2 .程序設(shè)計(jì)基礎(chǔ)3 .軟件工程基礎(chǔ)4 .數(shù)據(jù)庫設(shè)計(jì)基礎(chǔ)第1章 數(shù)據(jù)結(jié)構(gòu)與算法視頻講解本章考點(diǎn)1 .算法的基本概念；算法復(fù)雜度的概念和意義(時間復(fù)雜度與空間復(fù)雜度)2 .數(shù)據(jù)結(jié)構(gòu)的定義；數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲結(jié)構(gòu)；數(shù)據(jù)結(jié)構(gòu)的圖形表示； 線性結(jié)構(gòu)與非線性結(jié)構(gòu)的概念。3 .線性表的定義；線性表的順序存儲結(jié)構(gòu)及其插入與刪除運(yùn)算。4 .棧和隊(duì)列的定義；棧和隊(duì)列的順序存儲結(jié)構(gòu)及其基本運(yùn)算。5 .線性單鏈表、雙向鏈表與循環(huán)鏈表的結(jié)構(gòu)及其基本運(yùn)算。6 .樹的基本概念；二叉樹的定

4、義及其存儲結(jié)構(gòu)；二叉樹的前序、中序和后 序遍歷。7 .順序查找與二分法查找算法； 基本排序算法(交換類排序，選擇類排序, 插入類排序)。第一節(jié)算法一、算法的基本概念1 .算法的定義算法是指解題方案的準(zhǔn)確而完整的描述，即算法是對特定問題求解步驟的 一種描述。*算法不等于程序，也不等于計(jì)算方法。2 .算法的基本特征(1)可行性(Effectiveness )算法中的每一個步驟必須能夠?qū)崿F(xiàn)。算法執(zhí)行的結(jié)果要能夠達(dá)到預(yù)期的目的。(2)確定性(Definiteness )算法的確定性，是指算法中的每一個步驟都必須是有明確定義的，不允許 有模棱兩可的解釋，也不允許有多義性。(3)有窮性(Finitenes

5、s )算法的有窮性是指算法必須能在有限的時間內(nèi)做完，即算法必須能在執(zhí)行 有限個步驟之后終止。*算法的有窮性還應(yīng)包括合理的執(zhí)行時間(4)擁有足夠的情報輸入是否足夠并正確，輸出是否合理。 初始狀態(tài)是否正確。二、算法設(shè)計(jì)基本方法1 .列舉法 (1)基本思想根據(jù)提出的問題，列舉所有可能的情況，并用問題中給定的條件檢驗(yàn)?zāi)男?是需要的，哪些是不需要的。(2)特點(diǎn)簡單，方便用計(jì)算機(jī)進(jìn)行大量列舉；情況較多時，工作量將會很大。(3)使用將與問題有關(guān)的知識條理化、完備化、系統(tǒng)化，從中找出規(guī)律，進(jìn)行分類， 減少列舉量。例1.1 今有雞母一，值錢三；雞翁一，值錢二；雞雛一，值錢半。凡百錢 買百雞，問雞母、雞翁、雞雛各

6、幾何？假設(shè)買母雞I只、公雞J只、小雞KN。根據(jù)題意，粗略的列舉算法描述 如下：FOR I=0 TO 100 STEP 1 DOFOR J=0 TO 100 STEP 1 DOFOR K=0 TO 100 STEP 1 DO IF ( (I+J+K=100) AND(3*I+2*J+0.5*K=100.0 ) ) THENPRINT I , J, K END共有三層循環(huán)，每層循環(huán)各需要循環(huán)101次，大約為100萬次。優(yōu)化后的算法FOR I=0 TO 33 STEP 1DOFOR J=0 TO 50-1.5*I STEP 1 DO K=100-I-J IF (3*I+2*J+0.5*K=100.0

7、 ) THEN PRINT I , J, K END共有兩層循環(huán)，循環(huán)次數(shù)為2 .歸納法(1)基本思想通過列舉少量的特殊情況，經(jīng)過分析最后找出一般的關(guān)系。(2)特點(diǎn)歸納是一種抽象，即從特殊現(xiàn)象中找出一般關(guān)系。(3)使用由于在歸納的過程中不可能對所有的情況進(jìn)行列舉。因此，最后由歸納得 到的結(jié)論還只是一種猜測，還需要對這種猜測加以必要的證明。實(shí)際上，通過 精心觀察而得到的猜測得不到證實(shí)或最后證明猜測是錯的，也是常有的事。3 .遞推(1)基本思想從已知的初始條件出發(fā)，逐次推出所要求的各中間結(jié)果和最后結(jié)果。(2)特點(diǎn)本質(zhì)上屬于歸納法，遞推關(guān)系式往往是歸納的結(jié)果。(3)使用遞推算法在數(shù)值計(jì)算中是極為常見

8、的。但是，對于數(shù)值型的遞推算法必須要注意數(shù)值計(jì)算的穩(wěn)定性問題。4 .遞歸*(1)基本思想為了降低問題的復(fù)雜程度，將問題逐層分解，最后歸結(jié)為一些最簡單的問 題，這種將問題逐層分解的過程，實(shí)際上并沒有對問題進(jìn)行求解，而只是當(dāng)解 決了最后那些最簡單的問題后，再沿著原來分解的逆過程逐步進(jìn)行綜合。(2)特點(diǎn)結(jié)構(gòu)清晰，可讀性強(qiáng)。(3)使用遞歸在可計(jì)算性理論和算法設(shè)計(jì)中占有很重要的地位。(4)分類直接遞歸(自己調(diào)用自己)和間接遞歸( P調(diào)用Q Q又調(diào)用P)。例1.2 編寫一個過程，對于輸入的參數(shù) n,依次打印輸出自然數(shù)1到n 非遞歸算法：wrt (int n )(FOR k=1 TO n STEP 1 DO

9、 PRINT kRETURN遞歸算法：wrt1 (int n )(IF (n乎0) THEN(wrtl (n-1 ) PRINT n)RETURN)5 .減半遞推技術(shù)所謂“減半”，是指將問題的規(guī)模減半，而問題的性質(zhì)不變；所謂“遞推”， 是指重復(fù)“減半”的過程。例1.3 設(shè)方程f (x) =0在區(qū)間a , b上有實(shí)根，且f (a)與f (b)異號。 利用二分法求該方程在區(qū)間a , b上的一個實(shí)根。用二分法求方程實(shí)根的減半遞推過程如下：首先取給定區(qū)間的中點(diǎn) c= (a+b) /2。然后判斷f (c)是否為0o若f (c) =0,則說明C即為所求的根，求解過程結(jié)束；如果f (c)乎0,則根據(jù)以下原則

10、將原區(qū)間減半：若f (a) f (c) <0,則取原區(qū)間的前半部分；若f (b) f (c) <0,則取原區(qū)間的后半部分。最后判斷減半后的區(qū)間長度是否已經(jīng)很小：若|a- b卜£ ,則過程結(jié)束，取(a+b) /2為根的近似值；若|a- b| e ,則重復(fù)上述的減半過程。6 .回溯法(1)基本思想通過對問題的分析，找出一個解決問題的線索，然后沿著這個線索逐步試探，對于每一步的試探，若試探成功，就得 到問題的解，若試探失敗，就逐步回退，換別的路線再進(jìn)行試探。這種方法稱 為回溯法。(2)特點(diǎn)在工程上，有些實(shí)際問題很難歸納出一組簡單的遞推公式或直觀的求解步驟，并且也不能進(jìn)行無限的列

11、舉。對于這類問題，一種有效的方法是“試”。三、算法復(fù)雜度主要包括時間復(fù)雜度和空間復(fù)雜度。7 .算法的時間復(fù)雜度(1)定義執(zhí)行算法所需要的計(jì)算工作量。(2)衡量標(biāo)準(zhǔn)通常用算法在執(zhí)行過程中所需基本運(yùn)算的執(zhí)行次數(shù)來度量算法的工作量。算法所執(zhí)行的基本運(yùn)算次數(shù)還與問題的規(guī)模有關(guān)。綜上所述，算法的工作量用算法所執(zhí)行的基本運(yùn)算次數(shù)來度量，而算法所執(zhí)行的基本運(yùn)算次數(shù)是問題規(guī)模的函數(shù)，即算法的工作量 =f (n)。(3)存在問題算法所執(zhí)行的基本運(yùn)算次數(shù)還可能與特定的輸入有關(guān)，而實(shí)際上又不可能 將所有可能情況下算法所執(zhí)行的基本運(yùn)算次數(shù)都列舉出來。(4)解決方法平均性態(tài)(Average Behavior )用各種特

12、定輸入下的基本運(yùn)算次數(shù)的加權(quán)平均值來度量算法的工作量。最壞情況復(fù)雜性(Worst-Case Complexity)規(guī)模為n時，算法所執(zhí)行的基本運(yùn)算的最大次數(shù)。w)=max«(X)x D n例1.4 采用順序搜索法，在長度為n的一維數(shù)組中查找值為 x的元素。即 從數(shù)組的第一個元素開始，逐個與被查值x進(jìn)行比較?；具\(yùn)算為 x與數(shù)組元素的比較。(1)平均性態(tài)分析設(shè)被查項(xiàng)x在數(shù)組中出現(xiàn)的概率為 q, i=n+1表示x不在數(shù)組中的情況(2)最壞性態(tài)分析W(n) =maxti | l <i <n+1=n注：當(dāng)算法的計(jì)算工作量與輸入無關(guān)時，即當(dāng)規(guī)模為n時，在所有可能的輸入下，算法所執(zhí)行

13、的基本運(yùn)算次數(shù)是一定的，此時有 A(n)=W(n) 08 .算法的空間復(fù)雜度定義：執(zhí)行這個算法所需要的內(nèi)存空間。(1)算法程序所占的空間；(2)輸入的初始數(shù)據(jù)所占的存儲空間；(3)算法執(zhí)行過程中所需要的額外空間。*如果額外空間量相對于問題規(guī)模來說是常數(shù)，則稱該算法是原地工作的。*在許多實(shí)際問題中，為了減少算法所占的存儲空間，通常采用壓縮存儲技 術(shù)，以便盡量減少不必要的額外空間。第二節(jié)數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)結(jié)構(gòu)作為計(jì)算機(jī)的一門學(xué)科，主要研究和討論以下三個方面的問題：(1)數(shù)據(jù)集合中各數(shù)據(jù)元素之間所固有的邏輯關(guān)系，即數(shù)據(jù)的邏輯結(jié)構(gòu)；(2)在對數(shù)據(jù)進(jìn)行處理時，各數(shù)據(jù)元素在計(jì)算機(jī)中的存儲關(guān)系，即數(shù)據(jù)的

14、 存儲結(jié)構(gòu)；(3)對各種數(shù)據(jù)結(jié)構(gòu)進(jìn)行的運(yùn)算。討論以上問題的目的：(1)提高數(shù)據(jù)處理的速度；(2)盡量節(jié)省在數(shù)據(jù)處理過程中所占用的計(jì)算機(jī)存儲空間。一、什么是數(shù)據(jù)結(jié)構(gòu)定義：數(shù)據(jù)結(jié)構(gòu)是指相互有關(guān)聯(lián)的數(shù)據(jù)元素的集合。數(shù)據(jù)元素具有廣泛的含義：描述一年四季的季節(jié)名：春、夏、秋、冬表示數(shù)值的各個數(shù)：18、11、35、23、16表示家庭成員的各成員名：父親、兒子、女兒數(shù)據(jù)處理：對數(shù)據(jù)集合中的各元素以各種方式進(jìn)行運(yùn)算，包括插入、刪除、 查找、更改等運(yùn)算，也包括對數(shù)據(jù)元素進(jìn)行分析。*作為某種處理，其中的數(shù)據(jù)元素一般具有某種共同特征，一般情況下，在 具有相同特征的數(shù)據(jù)元素集合中，各個數(shù)據(jù)元素之間存在有某種關(guān)系，這種

15、關(guān) 系反映了該集合中的數(shù)據(jù)元素所固有的一種結(jié)構(gòu)。1 .數(shù)據(jù)的邏輯結(jié)構(gòu)(1)定義反映數(shù)據(jù)元素之間邏輯關(guān)系的數(shù)據(jù)結(jié)構(gòu)。一個數(shù)據(jù)結(jié)構(gòu)應(yīng)包含以下兩方面的信息：表示數(shù)據(jù)元素的信息；表示各數(shù)據(jù)元素之間的前后件關(guān)系。(2)數(shù)據(jù)的邏輯結(jié)構(gòu)有兩個要素：一是數(shù)據(jù)元素的集合，通常記為D;二是D上的關(guān)系，它反映了 D中各數(shù)據(jù)元素之間的前后件關(guān)系，通常記為R;即一個數(shù)據(jù)結(jié)構(gòu)可以表示成 B= ( D, R)。例1.5 一年四季的數(shù)據(jù)結(jié)構(gòu)可以表示成B= (D, R)D=春，夏，秋，冬R=(春，夏)，(夏，秋)，(秋，冬) 例1.6 家庭成員數(shù)據(jù)結(jié)構(gòu)可以表示成B= (D, R)D=父親，兒子，女兒R=(父親，兒子)，(父親，

16、女兒) 例1.7 n 維向量X= (x% X2,，xn)也是一種數(shù)據(jù)結(jié)構(gòu)。即 X= (D, R),其中數(shù)據(jù)元素的集合為：D=x1, x2,，xn關(guān)系為：R= (x1, x2) , (x2, x3),，(xn-1 , xn) * 對于一些復(fù)雜的數(shù)據(jù)結(jié)構(gòu)來說，它的數(shù)據(jù)元素可以是另一種數(shù)據(jù)結(jié)構(gòu)。例如，mXn的矩陣是一個數(shù)據(jù)結(jié)構(gòu)。在這個數(shù)據(jù)結(jié)構(gòu)中，矩陣的每一行Ai= (an , ai2,，an) , i=1 , 2,，m可以看成是它的一個數(shù)據(jù)元素。即這個數(shù)據(jù)結(jié)構(gòu)的數(shù)據(jù)元素的集合為D=A1, A2,，AmD上的一個關(guān)系為R= (Ai, A) ,(A2, A),，(A, A+1),，(Am-1, Am)

17、顯然，數(shù)據(jù)結(jié)構(gòu)A中的每一個數(shù)據(jù)元素：又是另一個數(shù)據(jù)結(jié)構(gòu)D上的一個關(guān)系為：R=，ai2),2.數(shù)據(jù)的存儲結(jié)構(gòu)A (i=1 , 2,，m),即數(shù)據(jù)元素的集合為：D=ai1 , ai2,，ainai2, ai3) , ,，(aj , ai, j+1) , ,，(ai, n-1, a) 定義：數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲空間中的存放形式。* 各數(shù)據(jù)元素在計(jì)算機(jī)存儲空間中的位置關(guān)系與它們的邏輯關(guān)系不一定是相同的，而且一般也不可能相同。* 在數(shù)據(jù)的存儲結(jié)構(gòu)中，不僅要存放各數(shù)據(jù)元素的信息，還需要存放各數(shù)據(jù) 元素之間的前后件關(guān)系的信息。* 常用的存儲結(jié)構(gòu)有順序、鏈接、索引等存儲結(jié)構(gòu)。* 采用不同的存儲結(jié)構(gòu)，其數(shù)

18、據(jù)處理的效率是不同的。二、數(shù)據(jù)結(jié)構(gòu)的圖形表示一個數(shù)據(jù)結(jié)構(gòu)除了用二元關(guān)系表示外，還可以直觀地用圖形表示。(1)對于數(shù)據(jù)集合D中的每一個數(shù)據(jù)元素用中間標(biāo)有元素值的方框表示，一般稱之為數(shù)據(jù)結(jié)點(diǎn)，并簡稱為結(jié)點(diǎn)；(2)對于關(guān)系R中的每一個二元組，用一條有向線段從前件結(jié)點(diǎn)指向后件 結(jié)點(diǎn)，有時箭頭可省去。圖1-1 一年四季數(shù)據(jù)結(jié)構(gòu)的圖形表示圖1-2家庭成員間輩分關(guān)系數(shù)據(jù)結(jié)構(gòu)的圖形表示例1.8 用圖形表示數(shù)據(jù)結(jié)構(gòu) B=(D, R),其中D=di | 1< i <7_d 1, cb, da, ch, ck, de, cbR= (d1,da),(d1,d7),( d2,&) ,(da,de),

19、( d，ds) 在數(shù)據(jù)結(jié)構(gòu)中，沒有前件的結(jié)點(diǎn)稱為根結(jié)點(diǎn)；沒有后件的結(jié)點(diǎn)稱為終端結(jié)點(diǎn)(也稱為葉子結(jié)點(diǎn))。圖1.3 例1.8數(shù)據(jù)結(jié)構(gòu)的圖形表示三、線性結(jié)構(gòu)與非線性結(jié)構(gòu)根據(jù)數(shù)據(jù)結(jié)構(gòu)中各數(shù)據(jù)元素之間前后件關(guān)系的復(fù)雜程度，一般將數(shù)據(jù)結(jié)構(gòu)分為兩大類型：線性結(jié)構(gòu)與非線性結(jié)構(gòu)。如果一個非空的數(shù)據(jù)結(jié)構(gòu)滿足下列兩個條件：(1)有且只有一個根結(jié)點(diǎn)；(2)每一個結(jié)點(diǎn)最多有一個前件，也最多有一個后件。則稱該數(shù)據(jù)結(jié)構(gòu)為線性結(jié)構(gòu)，線性結(jié)構(gòu)又稱線性表。* 在一個線性結(jié)構(gòu)中插入或刪除任何一個結(jié)點(diǎn)后還應(yīng)是線性結(jié)構(gòu)。圖1.4 不是線性結(jié)構(gòu)的數(shù)據(jù)結(jié)構(gòu)特例如果一個數(shù)據(jù)結(jié)構(gòu)不是線性結(jié)構(gòu)，則稱之為非線性結(jié)構(gòu)。* 線性結(jié)構(gòu)與非線性結(jié)構(gòu)都可以

20、是空的數(shù)據(jù)結(jié)構(gòu)。* 一個空的數(shù)據(jù)結(jié)構(gòu)究竟是屬于線性結(jié)構(gòu)還是屬于非線性結(jié)構(gòu)，這要根據(jù)具 體情況來確定。* 如果對該數(shù)據(jù)結(jié)構(gòu)的運(yùn)算是按線性結(jié)構(gòu)的規(guī)則來處理的，則屬于線性結(jié) 構(gòu)；否則屬于非線性結(jié)構(gòu)。第三節(jié)線性表及其順序存儲結(jié)構(gòu)一、線性表的基本概念線性表(Linear List )是最簡單、最常用的一種數(shù)據(jù)結(jié)構(gòu)。如：一個n維向量、矩陣，學(xué)生情況登記表；綜上所述，線性表是由n (n>0)個數(shù)據(jù)元素a1, a2,，an組成的一個 有限序列，表中的每一個數(shù)據(jù)元素，除了第一個外，有且只有一個前件，除了最后一個外，有且只有一個后件。即線性表或是一個空表，或可以表示為( al, a2,，ai ,，an)其中

21、ai (i=1 , 2,，n)是屬于數(shù)據(jù)對象的元素，通常 也稱其為線性表中的一個結(jié)點(diǎn)。非空線性表有如下一些結(jié)構(gòu)特征：(1)有且只有一個根結(jié)點(diǎn) ai它無前件；(2)有且只有一個終端結(jié)點(diǎn) an,它無后件；(3)除根結(jié)點(diǎn)與終端結(jié)點(diǎn)外，其他所有結(jié)點(diǎn)有且只有一個前件，也有且只 有一個后件。*線性表中結(jié)點(diǎn)的個數(shù)n稱為線性表的長度。*當(dāng)n=0時，稱為空表。二、線性表的順序存儲結(jié)構(gòu)1.特點(diǎn)(1)線性表中所有元素所占的存儲空間是連續(xù)的；(2)線性表中各數(shù)據(jù)元素在存儲空間中是按邏輯順序依次存放的。在線性表的順序存儲結(jié)構(gòu)中，其前后件兩個元素在存儲空間中是緊鄰的， 且前件元素一定存儲在后件元素的前面。圖1.5 線性表

22、的順序存儲結(jié)構(gòu)*在程序設(shè)計(jì)語言中，通常定義一個一維數(shù)組來表示線性表的順序存儲空 間。*在用一維數(shù)組存放線性表時，該一維數(shù)組的長度通常要定義得比線性表的實(shí)際長度大一些，以便對線性表進(jìn)行各種運(yùn)算，特別是插入運(yùn)算。2.在線性表的順序存儲結(jié)構(gòu)下，可以對線性表進(jìn)行各種處理。主要的運(yùn)算 有以下幾種：(1)在線性表的指定位置處加入一個新的元素(即線性表的插入)；(2)在線性表中刪除指定的元素(即線性表的刪除)；(3)在線性表中查找某個(或某些)特定的元素(即線性表的查找)；(4)對線性表中的元素進(jìn)行整序(即線性表的排序)；(5)按要求將一個線性表分解成多個線性表(即線性表的分解)；(6)按要求將多個線性表合

23、并成一個線性表(即線性表的合并)；(7)復(fù)制一個線性表(即線性表的復(fù)制)；(8)逆轉(zhuǎn)一個線性表(即線性表的逆轉(zhuǎn))等。三、順序表的插入運(yùn)算例1.9 圖1.6 (a)為一個長度為8的線性表順序存儲在長度為 10的存儲 空間中?，F(xiàn)在要求在第 2個元素(即18)之前插入一個新元素 87。然后在線性 表的第9個元素之前插入一個新元素 14。圖1.6 線性表在順序存儲結(jié)構(gòu)下的插入假設(shè)線性表的存儲空間為 V (1: m ,線性表的長度為n (n< nj),插入的 位置為i (i表示在第i個元素之前插入)，插入新元素。則插入的過程如下：(1)首先處理以下三種異常情況：* 當(dāng)存儲空間已滿(即n=n)時為“

24、上溢”錯誤，不能進(jìn)行插入，算法結(jié)束；* 當(dāng)i>n時，認(rèn)為在最后一個元素之后(第 n+1個元素之前)插入；* 當(dāng)i<1時，認(rèn)為在第1個元素之前插入。(2)然后從最后一個元素開始，直到第 i個元素，其中每一個元素均往后 移動一*個位置。(3)最后將新元素插入到第i個位置，并且將線性表的長度增加1。*由于大多數(shù)情況下需要移動數(shù)據(jù)元素，在線性表順序存儲的情況下，要插 入一個新元素，其效率是很低的。四、順序表的刪除運(yùn)算例1.10 圖1.7 (a)為一個長度為8的線性表順序存儲在長度為 10的存 儲空間中?，F(xiàn)在要求刪除線性表中的第 1個元素(即刪除元素29) o再刪除線 性表中的第6個元素。圖

25、1.7 線性表在順序存儲結(jié)構(gòu)下的刪除假設(shè)線性表的存儲空間為 V (1: m ,線性表的長度為n (n<nj),刪除的 位置為i (表示刪除第i個元素)。則刪除的過程如下：(1)首先處理以下兩種異常情況：*當(dāng)線性表為空(即n=0)時錯誤，不能進(jìn)行刪除，算法結(jié)束；*當(dāng)i<1或i>n時，錯誤，不能進(jìn)行刪除，算法結(jié)束；(2)刪除線性表中的第i個元素；(3)然后從第i+1個元素開始，直到最后一個元素，其中每一個元素均依 次往前移動一個位置；(4)最后將線性表的長度減小 1。*由線性表在順序存儲結(jié)構(gòu)下的插入與刪除運(yùn)算可以看出，線性表的順序存 儲結(jié)構(gòu)對于小線性表或者其中元素不常變動的線性表

26、來說是合適的，因?yàn)轫樞虼鎯Φ慕Y(jié)構(gòu)比較簡單。*但這種順序存儲的方式對于元素經(jīng)常需要變動的大線性表就不太合適了， 因?yàn)椴迦肱c刪除的效率比較低。第四節(jié)棧和隊(duì)列一、棧及其基本運(yùn)算1 .什么是棧定義：限定在一端進(jìn)行插入與刪除的線性表* 在棧中，允許插入與刪除的一端稱為棧頂，而不允許插入與刪除的另一端 稱為棧底。用指針top來指不棧頂?shù)奈恢?，用指?bottom指向棧底。* 棧頂元素總是最后被插入的元素，從而也是最先能被刪除的元素；棧底元 素總是最先被插入的元素，從而也是最后才能被刪除的元素。即棧是按照“先 進(jìn)后出”或“后進(jìn)先出”的原則組織數(shù)據(jù)的，因此，棧也被稱為“先進(jìn)后出” 表或“后進(jìn)先出”表。* 棧具

27、有記憶作用。* 往棧中插入一個元素稱為入棧運(yùn)算，從棧中刪除一個元素(即刪除棧頂元 素)稱為退棧運(yùn)算。計(jì)算機(jī)系統(tǒng)在處理時要用一個線性表來動態(tài)記憶調(diào)用過程中的路徑，其基 本原則如下：(1)在開始執(zhí)行程序前，建立一個線性表，初始狀態(tài)為空；(2)發(fā)生調(diào)用時，將當(dāng)前調(diào)用的返回點(diǎn)地址插入到線性表的末尾；(3)當(dāng)遇到從某個子程序返回時，其返回點(diǎn)地址從線性表的末尾取出(即 刪除線性表的最后一個元素)。圖1.9 棧不'意圖圖1.8中給出了具有嵌套調(diào)用關(guān)系的五個程序，其中主程序要調(diào)用子程序SUB1 SUB1要調(diào)用子程序SUB2 SUB2要調(diào)用子程序SUB3 SUB諜調(diào)用子程序 SUB4 SUB4不再調(diào)用其

28、他子程序了。圖1.8 主程序與子程序之間的調(diào)用關(guān)系圖1.8中五個程序在執(zhí)行過程中的調(diào)用順序以及線性表中元素變化的情況 如下：(1)主程序開始執(zhí)行前，建立一個空線性表。即線性表的狀態(tài)為()o(2)開始執(zhí)行主程序MAIN當(dāng)要調(diào)用子程序SUB1時，先將本次調(diào)用的返回點(diǎn)地址A插入到線性表的末尾。此時，線性表的狀態(tài)為(A) o(3)開始調(diào)用執(zhí)行子程序 SUB1當(dāng)要調(diào)用子程序 SUB2時，先將本次調(diào)用 的返回點(diǎn)地址B插入到線性表的末尾。止匕時,線性表的X犬態(tài)為(A, B)。(4)開始調(diào)用執(zhí)行子程序 SUB2當(dāng)要調(diào)用子程序 SUB3時，先將本次調(diào)用的返回點(diǎn)地址C插入到線性表的末尾。此時，線性表的狀態(tài)為(A,

29、B,C) 0(5)開始調(diào)用執(zhí)行子程序 SUB3當(dāng)要調(diào)用子程序 SUB4時，先將本次調(diào)用的返回點(diǎn)地址D插入到線性表的末尾。此時，線性表的狀態(tài)為(A, B, C, D) 0由上述逐步調(diào)用的過程可以看出，每次發(fā)生調(diào)用時，都需要將當(dāng)前調(diào)用的 返回點(diǎn)地址插入到線性表的末尾，而這種對線性表的插入操作是不需要移動線 性表中原有元素的。并且，各返回點(diǎn)地址在線性表中的存放順序恰好是調(diào)用順 序。(6)開始調(diào)用執(zhí)行子程序 SUB4由于子程序SUB4不再調(diào)用其他子程序， 執(zhí)行完子程序SUB4后要返回到子程序SUB3的地址D處。其中返回點(diǎn)地址 D取 自線性表的最后一個元素。取出 D后，線性表的狀態(tài)為(A, B, C)

30、0(7)返回到子程序SUB3的D處繼續(xù)執(zhí)行，執(zhí)行完子程序 SUB3后要返回到 子程序SUB2的地址C處。其中返回點(diǎn)地址 C取自線性表的最后一個元素。取出 C后，線性表的狀態(tài)為(A, B)。(8)返回到子程序SUB2的C處繼續(xù)執(zhí)行，執(zhí)行完子程序 SUB2后萋返回到 子程序SUB1的地址B處。其中返回點(diǎn)地址、取自線性表的最后一個元素。取出 B后，線性表的狀態(tài)為(A) 0(9)返回到子程序SUB1的B處繼續(xù)執(zhí)行，執(zhí)行完子程序 SUB1后要返回到 主程序MAIN的地址A處。其中返回點(diǎn)地址 A取自線性表最后一個元素。取出 A 后，線性表變空，即線性表的狀態(tài)為()o(10)返回到主程序 MAIN的A處繼續(xù)

31、執(zhí)行，直到主程序 MAIN執(zhí)行完成。由上述逐步返回的過程可以看出，當(dāng)由子程序返回到上一個調(diào)用程序時， 需要從線性表的末尾取出返回點(diǎn)地址，即從線性表中刪除最后一個元素，而這 種對線性表的刪除操作也是不需要移動線性表中其他數(shù)據(jù)元素的。2 .棧的順序存儲及其運(yùn)算圖1.10 (a)是容量為10的棧順序存儲空間，棧中已有 6個元素；圖1.10 (b)與圖1.10 (c)分別為入棧與退棧后的狀態(tài)。圖1.10 棧在順序存儲結(jié)構(gòu)下的運(yùn)算在棧的順序存儲空間 S (1:成中，S ( bottom )通常為棧底元素(在棧非空 的情況下)，S (top )為棧頂元素。top=0表示棧空；top=m表示棧滿。棧的基本運(yùn)

32、算有三種：入棧、退棧與讀棧頂元素。(1)入棧運(yùn)算入棧運(yùn)算是指在棧頂位置插入一個新元素。操作過程如下：首先判斷棧頂指針是否已經(jīng)指向存儲空間的最后一個位置。如果是，則 說明棧空間已滿，不可能再進(jìn)行入棧操作(這種情況稱為?！吧弦纭卞e誤)， 算法結(jié)束。然后將棧頂指針進(jìn)一(即top加1)。最后將新元素x插入棧頂指針指向的位置。(2)退棧運(yùn)算退棧運(yùn)算是指取出棧頂元素并賦給一個指定的變量。操作過程如下：首先判斷棧頂指針是否為 00如果是，則說明?？?，不可能進(jìn)行退棧操作(這種情況稱為?！跋乱纭卞e誤)，算法結(jié)束。然后將棧頂元素(棧頂指針指向的元素)賦給一個指定的變量。最后將棧頂指針退一(即 top減1)。(3)

33、讀棧頂元素讀棧頂元素是指將棧頂元素賦給一個指定的變量。操作過程如下：首先判斷棧頂指針是否為 00如果是，則說明棧空，讀不到棧頂元素，算 法結(jié)束。然后將棧頂元素賦給指定的變量 y o必須注意，這個運(yùn)算不刪除棧頂元素，只是將它的值賦給一個變量，因此， 在這個運(yùn)算中棧頂指針不會改變。二、隊(duì)列及其基本運(yùn)算1 .什么是隊(duì)列在操作系統(tǒng)中，用一個線性表來組織管理用戶程序的排隊(duì)執(zhí)行，原則是：初始時線性表為空；當(dāng)有用戶程序來到時，將該用戶程序加入到線性表的末尾進(jìn)行等待；當(dāng)計(jì)算機(jī)系統(tǒng)執(zhí)行完當(dāng)前的用戶程序后，就從線性表的頭部取出一個用 戶程序執(zhí)行。由這個例子可以看出，在這種線性表中，需要加入的元素總是插入到線性 表

34、的末尾，并且又總是從線性表的頭部取出(刪除)元素。這種線性表稱為隊(duì) 列。定義：隊(duì)列(Queue是指允許在一端進(jìn)行插入、而在另一端進(jìn)行刪除的線 性表。* 允許插入的一端稱為隊(duì)尾，通常用一個稱為尾指針（Rear）的指針指向隊(duì)尾元素，即尾指針總是指向最后被插入的元素；允許刪除的一端稱為排頭（也 稱為隊(duì)頭），通常也用一個排頭指針（Front ）指向排頭元素的前一個位置。* 在隊(duì)列這種數(shù)據(jù)結(jié)構(gòu)中，最先插入的元素將最先能夠被刪除，反之，最后 插入的元素將最后才能被刪除。因此，隊(duì)列又稱為“先進(jìn)先出”或“后進(jìn)后出”的線性表，它體現(xiàn)了 “先來先服務(wù)”的原則。* 在隊(duì)列中，隊(duì)尾指針rear與排頭指針front共同

35、反映了隊(duì)列中元素動態(tài) 變化的情況。圖1.11 具有6個元素的隊(duì)列示意圖圖1.12 隊(duì)列運(yùn)算示意圖2 .循環(huán)隊(duì)列及其運(yùn)算定義：所謂循環(huán)隊(duì)列，就是將隊(duì)列存儲空間的最后一個位置繞到第一個位 置，形成邏輯上的環(huán)狀空間，供隊(duì)列循環(huán)使用。* 在循環(huán)隊(duì)列中，用隊(duì)尾指針rear指向隊(duì)列中的隊(duì)尾元素，用排頭指針front 指向排頭元素的前一個位置，因此，從排頭指針front指向的后一個位置直到隊(duì)尾指針rear指向的位置之間所有的元素均為隊(duì)列中的元素。* 循環(huán)隊(duì)列的初始狀態(tài)為空，即rear=front=m ,如圖1.13所示。圖1.13 循環(huán)隊(duì)列存儲空間示意圖循環(huán)隊(duì)列主要有兩種基本運(yùn)算：入隊(duì)運(yùn)算與退隊(duì)運(yùn)算。每進(jìn)行

36、一次入隊(duì)運(yùn)算，隊(duì)尾指針就進(jìn)一。當(dāng)隊(duì)尾指針rear=m+1時，則置rear=1。每進(jìn)行一次退隊(duì)運(yùn)算，排頭指針就進(jìn)一。當(dāng)排頭指針front=m+1時，則置front=1 0圖1.14 循環(huán)隊(duì)列運(yùn)算例* 當(dāng)循環(huán)隊(duì)列滿時有front=rear ,而當(dāng)循環(huán)隊(duì)列空時也有 front=rear 。即 在循環(huán)隊(duì)列中，當(dāng)front=rear 時，不能確定是隊(duì)列滿還是隊(duì)列空。在實(shí)際使用循環(huán)隊(duì)列時，為了能區(qū)分隊(duì)列滿還是隊(duì)列空，通常還需增加一 個標(biāo)志s, s值的定義如下：由此可以得出隊(duì)列空與隊(duì)列滿的條件如下：隊(duì)列空的條件為s=0；隊(duì)列滿的條件為s=1且front=rear 。假設(shè)循環(huán)隊(duì)列的初始狀態(tài)為空，即：s=0,且

37、front=rear=m。（1）入隊(duì)運(yùn)算入隊(duì)運(yùn)算是指在循環(huán)隊(duì)列的隊(duì)尾加入一個新元素。操作過程如下：首先判斷循環(huán)隊(duì)列是否滿。當(dāng)循環(huán)隊(duì)列非空（S=1）且隊(duì)尾指針等于排頭指針時，說明循環(huán)隊(duì)列已滿，不能進(jìn)行入隊(duì)運(yùn)算。這種情況稱為“上溢”。此 時算法結(jié)束。然后將隊(duì)尾指針進(jìn)一（即 rear=rear+1 ）,并當(dāng)rear=m+1時置rear=1 。最后將新元素x插入隊(duì)尾指針指向的位置，并且置循環(huán)隊(duì)列非空標(biāo)志。（2）退隊(duì)運(yùn)算退隊(duì)運(yùn)算是指在循環(huán)隊(duì)列的排頭位置退出一個元素并賦給指定的變量。操 作過程如下：首先判斷循環(huán)隊(duì)列是否為空。當(dāng)循環(huán)隊(duì)列為空（s=0）時，不能進(jìn)行退隊(duì)運(yùn)算。這種情況稱為“下溢”。此時算法結(jié)束。

38、然后將排頭指針進(jìn)一 （即front=front+1 ），并當(dāng)front=m+1時置front=1再將排頭指針指向的元素賦給指定的變量最后判斷退隊(duì)后循環(huán)隊(duì)列是否為空。當(dāng)front=rear 時置循環(huán)隊(duì)列空標(biāo)志（即 s=0） 0第五節(jié)線性鏈表一、線性鏈表的基本概念*線性表的順序存儲結(jié)構(gòu)具有簡單、運(yùn)算方便等優(yōu)點(diǎn)，特別是對于小線性表 或長度固定的線性表，采用順序存儲結(jié)構(gòu)的優(yōu)越性更為突出。*線性表的順序存儲結(jié)構(gòu)存在的缺點(diǎn)：（1）在一般情況下，要在順序存儲的線性表中插入一個新元素或刪除一個 元素時，為了保證插入或刪除后的線性表仍然為順序存儲，則在插入或刪除過 程中需要移動大量的數(shù)據(jù)元素。（2）當(dāng)為一個線性

39、表分配順序存儲空間后，如果出現(xiàn)線性表的存儲空間已 滿，但還需要插入新的元素時，就會發(fā)生“上溢”錯誤。（3）線性表的順序存儲結(jié)構(gòu)不便于對存儲空間的動態(tài)分配。因此，對于大的線性表，特別是元素變動頻繁的大線性表不宜采用順序存 儲結(jié)構(gòu)，而是采用下面要介紹的鏈?zhǔn)酱鎯Y(jié)構(gòu)。* 假設(shè)數(shù)據(jù)結(jié)構(gòu)中的每一個數(shù)據(jù)結(jié)點(diǎn)對應(yīng)于一個存儲單元，這種存儲單元稱 為存儲結(jié)點(diǎn)，簡稱結(jié)點(diǎn)。* 在鏈?zhǔn)酱鎯Ψ绞街校竺總€結(jié)點(diǎn)由兩部分組成：一部分用于存放數(shù)據(jù)元 素值，稱為數(shù)據(jù)域；另一部分用于存放指針，稱為指針域。其中指針用于指向 該結(jié)點(diǎn)的前一個或后一個結(jié)點(diǎn)（即前件或后件）。* 在鏈?zhǔn)酱鎯Y(jié)構(gòu)中，存儲數(shù)據(jù)結(jié)構(gòu)的存儲空間可以不連續(xù)，各數(shù)據(jù)

40、結(jié)點(diǎn)的 存儲順序與數(shù)據(jù)元素之間的邏輯關(guān)系可以不一致，而數(shù)據(jù)元素之間的邏輯關(guān)系 是由指針域來確定的。* 鏈?zhǔn)酱鎯Ψ绞郊瓤捎糜诒硎揪€性結(jié)構(gòu)，也可用于表示非線性結(jié)構(gòu)。在用鏈 式結(jié)構(gòu)表示較復(fù)雜的非線性結(jié)構(gòu)時，其指針域的個數(shù)要多一些。1 .線性鏈表定義：線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)稱為線性鏈表。為了存儲線性表中的每一個元素，一方面要存儲數(shù)據(jù)元素的值，另一方面 要存儲各數(shù)據(jù)元素之間的前后件關(guān)系。圖1.15 線性鏈表的存儲空間為了適應(yīng)線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)，計(jì)算機(jī)存儲空間被劃分為一個一個小塊， 每一小塊占若干字節(jié)，通常稱這些小塊為存儲結(jié)點(diǎn)。圖1.16 線性鏈表的一個存儲結(jié)點(diǎn)* 在線性鏈表中，用一個專門的指針HEA討旨

41、向線性鏈表中第一個數(shù)據(jù)元素的結(jié)點(diǎn)（即存放線性表中第一個數(shù)據(jù)元素的存儲結(jié)點(diǎn)的序號）。線性表中最后一個元素沒有后件，因此，線性鏈表中最后一個結(jié)點(diǎn)的指針域?yàn)榭眨ㄓ肗ULL或0表示），表示鏈表終止。圖1.17 線性鏈表的邏輯結(jié)構(gòu)* 在線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)中，各數(shù)據(jù)結(jié)點(diǎn)的存儲序號是不連續(xù)的，并且各 結(jié)點(diǎn)在存儲空間中的位置關(guān)系與邏輯關(guān)系也不一致。* 當(dāng)HEAD= NULL（或0）時稱為空表。圖1.18 線性鏈表例* 在這種鏈表中，每一個結(jié)點(diǎn)只有一個指針域，由這個指針只能找到后件結(jié) 點(diǎn)，但不能找到前件結(jié)點(diǎn)。因此，在這種線性鏈表中，只能順指針向鏈尾方向進(jìn)行掃描，這對于某些 問題的處理會帶來不便，因?yàn)樵谶@種鏈接

42、方式下，由某一個結(jié)點(diǎn)出發(fā)，只能找 到它的后件，而為了找出它的前件，必須從頭指針開始重新尋找。為了彌補(bǔ)線性單鏈表的這個缺點(diǎn)，在某些應(yīng)用中，對線性鏈表中的每個結(jié) 點(diǎn)設(shè)置兩個指針，一個稱為左指針（Llink ）,用以指向其前件結(jié)點(diǎn)；另一個稱 為右指針（Rlink ）,用以指向其后件結(jié)點(diǎn)。這樣的線性鏈表稱為雙向鏈表。圖1.19 雙向鏈表示意圖2 .帶鏈的棧棧也是線性表，也可以采用鏈?zhǔn)酱鎯Y(jié)構(gòu)。圖1.20 帶鏈的棧在實(shí)際應(yīng)用中，帶鏈的?？梢杂脕硎占?jì)算機(jī)存儲空間中所有空閑的存儲 結(jié)點(diǎn)，這種帶鏈的棧稱為可利用棧。圖1.21 可利用棧及其運(yùn)算與順序棧一樣，帶鏈棧的基本操作有以下幾個：棧的初始化。即建立一個空

43、棧的順序存儲空間。入棧運(yùn)算。是指在棧頂位置插入一個新元素。退棧運(yùn)算。是指取出棧頂元素并賦給一個指定的變量。讀棧頂元素。是指將棧頂元素賦給一個指定的變量。3 .帶鏈的隊(duì)列隊(duì)列也是線性表，也可以采用鏈?zhǔn)酱鎯Y(jié)構(gòu)。圖1.22 帶鏈的隊(duì)列及其運(yùn)算與順序隊(duì)列一樣，帶鏈隊(duì)列的基本操作有以下幾個：隊(duì)列的初始化。即建立一個空隊(duì)列的順序存儲空間。入隊(duì)運(yùn)算。是指在循環(huán)隊(duì)列的隊(duì)尾加入一個新元素。退隊(duì)運(yùn)算。是指在循環(huán)隊(duì)列的排頭位置退出一個元素并賦給指定的變量。二、線性鏈表的基本運(yùn)算線性鏈表的運(yùn)算主要有以下幾個：在線性鏈表中包含指定元素的結(jié)點(diǎn)之前插入一個新元素。在線性鏈表中刪除包含指定元素的結(jié)點(diǎn)。將兩個線性鏈表按要求合

44、并成一個線性鏈表將一個線性鏈表按要求進(jìn)行分解。逆轉(zhuǎn)線性鏈表。復(fù)制線性鏈表。線性鏈表的排序。線性鏈表的查找。1 .在線性鏈表中查找指定元素在非空線性鏈表中尋找包含指定元素值 x的前一個結(jié)點(diǎn)p的基本方法如下:從頭指針指向的結(jié)點(diǎn)開始往后沿指針進(jìn)行掃描，直到后面已沒有結(jié)點(diǎn)或下 一個結(jié)點(diǎn)的數(shù)據(jù)域?yàn)閤為止。因此，由這種方法找到的結(jié)點(diǎn) p有兩種可能：*當(dāng)線性鏈表中存在包含元素 x的結(jié)點(diǎn)時，則找到的p為第一次遇到的包含 元素x的前一個結(jié)點(diǎn)序號；*當(dāng)線性鏈表中不存在包含元素 x的結(jié)點(diǎn)時，則找到的p為線性鏈表中的最 后一個結(jié)點(diǎn)號。2 .線性鏈表的插入(1)定義在鏈?zhǔn)酱鎯Y(jié)構(gòu)下的線性表中插入一個新元素。(2)插入過

45、程從可利用棧取得一個結(jié)點(diǎn)， 設(shè)該結(jié)點(diǎn)號為p (即取得結(jié)點(diǎn)的存儲序號存放在變量p中)，并置結(jié)點(diǎn)p的數(shù)據(jù)域?yàn)椴迦氲脑刂?b0在線性鏈表中尋找包含元素 x的前一個結(jié)點(diǎn)，設(shè)該結(jié)點(diǎn)的存儲序號為 q最后將結(jié)點(diǎn)p插入到結(jié)點(diǎn)q之后。為了實(shí)現(xiàn)這一步，只要改變以下兩個 結(jié)點(diǎn)的指針域內(nèi)容：a.使結(jié)點(diǎn)P指向包含元素x的結(jié)點(diǎn)(即結(jié)點(diǎn)q的后件結(jié)點(diǎn))。b.使結(jié)點(diǎn)q的指針域內(nèi)容改為指向結(jié)點(diǎn) p。(a)原來的可利用棧與線性鏈表(b)從可利用棧取得結(jié)點(diǎn) p,在線性鏈表中找到包含元素 x的前一個結(jié)點(diǎn)q(c) p插入到q之后圖1.23 線性鏈表的插入* 只要可利用棧不空，在線性鏈表插入時總能取到存儲插入元素的新結(jié)點(diǎn)， 不會發(fā)生“上

46、溢”的情況。* 可利用棧是公用的，多個線性鏈表可以共享它，從而很方便地實(shí)現(xiàn)了存儲 空間的動態(tài)分配。* 線性鏈表在插入過程中不發(fā)生數(shù)據(jù)元素移動的現(xiàn)象，只需改變有關(guān)結(jié)點(diǎn)的 指針即可，從而提高了插入的效率。3.線性鏈表的刪除(1)定義：在鏈?zhǔn)酱鎯Y(jié)構(gòu)下的線性表中刪除包含指定元素的結(jié)點(diǎn)。(2)刪除過程在線性鏈表中尋找包含元素 x的前一個結(jié)點(diǎn)，設(shè)該結(jié)點(diǎn)序號為 q0將結(jié)點(diǎn)q后的結(jié)點(diǎn)p從線性鏈表中刪除，即讓結(jié)點(diǎn) q的指針指向包含元 素x的結(jié)點(diǎn)p的指針指向的結(jié)點(diǎn)。將包含元素x的結(jié)點(diǎn)p送回可利用棧。此時，線性鏈表的刪除運(yùn)算完成。(c)將被刪除的結(jié)點(diǎn)p送回可利用棧后圖1.24 線性鏈表的刪除*在線性鏈表中刪除一個

47、元素后，不需要移動表的數(shù)據(jù)元素，只需改變被刪 除元素所在結(jié)點(diǎn)的前一個結(jié)點(diǎn)的指針域即可。*當(dāng)從線性鏈表中刪除一個元素后，該元素的存儲結(jié)點(diǎn)就變?yōu)榭臻e，應(yīng)將該 空閑結(jié)點(diǎn)送回到可利用棧。三、循環(huán)鏈表前面所討論的線性鏈表中，其插入與刪除的運(yùn)算雖然比較方便，但還存在 一個問題，在運(yùn)算過程中對于空表和對第一個結(jié)點(diǎn)的處理必須單獨(dú)考慮，使空 表與非空表的運(yùn)算不統(tǒng)一。1 .循環(huán)鏈表的特點(diǎn)(1)在循環(huán)鏈表中增加了一個表頭結(jié)點(diǎn)，其數(shù)據(jù)域?yàn)槿我饣蛘吒鶕?jù)需要來 設(shè)置，指針域指向線性表的第一個元素的結(jié)點(diǎn)。循環(huán)鏈表的頭指針指向表頭結(jié) 點(diǎn)。(2)循環(huán)鏈表中最后一個結(jié)點(diǎn)的指針域不是空，而是指向表頭結(jié)點(diǎn)。即在 循環(huán)鏈表中，所有結(jié)點(diǎn)

48、的指針構(gòu)成了一個環(huán)狀鏈。2 .循環(huán)鏈表與線性單鏈表相比主要有以下兩個方面的優(yōu)點(diǎn)：(1)在循環(huán)鏈表中，只要指出表中任何一個結(jié)點(diǎn)的位置，就可以從它出發(fā) 訪問到表中其他所有的結(jié)點(diǎn)。線性單鏈表做不到這一點(diǎn)。(2)由于在循環(huán)鏈表中設(shè)置了一個表頭結(jié)點(diǎn)，因此，在任何情況下循環(huán)鏈 表中至少有一個結(jié)點(diǎn)存在，從而使空表與非空表的運(yùn)算統(tǒng)一。(a)非空循環(huán)鏈表(b)空循環(huán)鏈表圖1.25 循環(huán)鏈表的邏輯狀態(tài)第六節(jié)樹與二叉樹一、樹的基本概念定義：樹(Tree)是一種簡單的非線性結(jié)構(gòu)，樹中所有數(shù)據(jù)元素之間的關(guān) 系具有明顯的層次特性。圖1.26 一般的樹圖1.27 學(xué)校行政層次結(jié)構(gòu)樹圖1.28 書的層次結(jié)構(gòu)樹* 在樹結(jié)構(gòu)中，

49、每一個結(jié)點(diǎn)只有一個前件，稱為父結(jié)點(diǎn)，沒有前件的結(jié)點(diǎn)只 有一個，稱為樹的根結(jié)點(diǎn)，簡稱為樹的根。* 在樹結(jié)構(gòu)中，每一個結(jié)點(diǎn)可以有多個后件，它們都稱為該結(jié)點(diǎn)的子結(jié)點(diǎn)。 沒有后件的結(jié)點(diǎn)稱為葉子結(jié)點(diǎn)。* 在樹結(jié)構(gòu)中，一個結(jié)點(diǎn)所擁有的后件個數(shù)稱為該結(jié)點(diǎn)的度。* 在樹中，所有結(jié)點(diǎn)中的最大的度稱為樹的度。* 樹中的結(jié)點(diǎn)數(shù)=樹中所有結(jié)點(diǎn)的度之和+1 0* 根結(jié)點(diǎn)在第1層。同一層上所有結(jié)點(diǎn)的所有子結(jié)點(diǎn)都在下一層。樹的最大 層次稱為樹的深度。在計(jì)算機(jī)中，可以用樹結(jié)構(gòu)來表示算術(shù)表達(dá)式。用樹來表示算術(shù)表達(dá)式的原則如下：表達(dá)式中的每一個運(yùn)算符在樹中對應(yīng)一個結(jié)點(diǎn)，稱為運(yùn)算符結(jié)點(diǎn)。運(yùn)算符的每一個運(yùn)算對象在樹中為該運(yùn)算符結(jié)點(diǎn)的

50、子樹(在樹中的順序 為從左到右)。運(yùn)算對象中的單變量均為葉子結(jié)點(diǎn)。* 表示一*個表達(dá)式的表達(dá)式樹是不唯一*的。a*(b+e/d) +e*h-g*f (s, t , x+y)(a)表達(dá)式樹之一 (b)表達(dá)式樹之二 樹在計(jì)算機(jī)中通常用多重鏈表表示。* 多重鏈表中的每個結(jié)點(diǎn)描述了樹中對應(yīng)結(jié)點(diǎn)的信息，而每個結(jié)點(diǎn)中的鏈域 (指針域)個數(shù)將隨樹中該結(jié)點(diǎn)的度而定。圖1.30 樹鏈表中的結(jié)點(diǎn)結(jié)構(gòu)二、二叉樹及其基本性質(zhì)1 .什么是二叉樹二叉樹具有以下兩個特點(diǎn)：非空二叉樹只有一個根結(jié)點(diǎn)；每一個結(jié)點(diǎn)最多有兩棵子樹，且分別稱為該結(jié)點(diǎn)的左子樹與右子樹。*在二叉樹中，每一個結(jié)點(diǎn)的度最大為2。圖1.31 二叉樹例2 .二叉

51、樹的基本性質(zhì)性質(zhì)1在二叉樹的第k層上，最多有2k-1 (k>1)個結(jié)點(diǎn)。性質(zhì)2深度為m的二叉樹最多有2m-1個結(jié)點(diǎn)。21-1+22-1+2m-1=221性質(zhì)3在任意一棵二叉樹中，度為 0的結(jié)點(diǎn)(即葉子結(jié)點(diǎn))總是比度為 2 的結(jié)點(diǎn)多一個。二叉樹中總的結(jié)點(diǎn)數(shù)為n=n 0+n1+n2 (1)進(jìn)入分支的總數(shù)為 m n=m+1 (2)總的射出分支數(shù)應(yīng)與總的進(jìn)入分支數(shù)相等m=n+2n2 (3)n=n1+2n2+1 (4)n0+n1+n2=n1+2n2+1n0=1+1性質(zhì)4具有n個結(jié)點(diǎn)的二叉樹，其深度至少為log 2n+1 ,其中l(wèi)og 2n表 示取log 2n的整數(shù)部分。3 .滿二叉樹與完全二叉樹(

52、1)滿二叉樹定義：滿二叉樹是指這樣的一種二叉樹：除最后一層外，每一層上的所有 結(jié)點(diǎn)都有兩個子結(jié)點(diǎn)。*在滿二叉樹中，每一層上的結(jié)點(diǎn)數(shù)都達(dá)到最大值，即在滿二叉樹的第k層上有2k-1個結(jié)點(diǎn)，且深度為m的滿二叉樹有2m-1個結(jié)點(diǎn)。(a)深度為2的滿二叉樹(b)深度為3的滿二叉樹(c)深度為4的滿二叉樹 圖1.32 滿二叉樹(2)完全二叉樹定義：所謂完全二叉樹是指這樣的二叉樹：除最后一層外，每一層上的結(jié) 點(diǎn)數(shù)均達(dá)到最大值；在最后一層上只缺少右邊的若干結(jié)點(diǎn)。更確切地說，如果從根結(jié)點(diǎn)起，對二叉樹的結(jié)點(diǎn)自上而下、自左至右用自 然數(shù)進(jìn)行連續(xù)編號，則深度為 m且有n個結(jié)點(diǎn)的二叉樹，當(dāng)且僅當(dāng)其每一個結(jié) 點(diǎn)都與深度為

53、m的滿二叉樹中編號從1到n的結(jié)點(diǎn)一一對應(yīng)時，稱之為完全二 叉樹。* 對于完全二叉樹來說，葉子結(jié)點(diǎn)只可能在層次最大的兩層上出現(xiàn)；對于任 何一個結(jié)點(diǎn)，若其右分支下的子孫結(jié)點(diǎn)的最大層次為P,則其左分支下的子孫結(jié)點(diǎn)的最大層次或?yàn)镻,或?yàn)镻+1。圖1.33 完全二叉樹* 滿二叉樹也是完全二叉樹，而完全二叉樹一般不是滿二叉樹。完全二叉樹還具有以下兩個性質(zhì)：性質(zhì)5具有n個結(jié)點(diǎn)的完全二叉樹的深度為log 2n+1。性質(zhì)6 設(shè)完全二叉樹共有n個結(jié)點(diǎn)。如果從根結(jié)點(diǎn)開始，按層序(每一 層從左到右)用自然數(shù)1,2,，n給結(jié)點(diǎn)進(jìn)行編號，則對于編號為k(k=1,2, n)的結(jié)點(diǎn)有以下結(jié)論：若k=1,則該結(jié)點(diǎn)為根結(jié)點(diǎn)，它沒

54、有父結(jié)點(diǎn)；若 k>1,則該結(jié)點(diǎn)的父結(jié)點(diǎn) 編號為INT (k/2) 0若2k<n,則編號為k的結(jié)點(diǎn)的左子結(jié)點(diǎn)編號為 2k;否則該結(jié)點(diǎn)無左子 結(jié)點(diǎn)(顯然也沒有右子結(jié)點(diǎn))。若2k+1&n,則編號為k的結(jié)點(diǎn)的右子結(jié)點(diǎn)編號為 2k+1;否則該結(jié)點(diǎn)無 右子結(jié)點(diǎn)。三、二叉樹的存儲結(jié)構(gòu)在計(jì)算機(jī)中，二叉樹通常采用鏈?zhǔn)酱鎯Y(jié)構(gòu)。* 用于存儲二叉樹中各元素的存儲結(jié)點(diǎn)也由兩部分組成：數(shù)據(jù)域與指針域。* 用于存儲二叉樹的存儲結(jié)點(diǎn)的指針域有兩個：一個用于指向該結(jié)點(diǎn)的左子 結(jié)點(diǎn)的存儲地址，稱為左指針域；另一個用于指向該結(jié)點(diǎn)的右子結(jié)點(diǎn)的存儲地 址，稱為右指針域。因此，二叉樹的鏈?zhǔn)酱鎯Y(jié)構(gòu)也稱為二叉鏈表。圖

55、1.34 二叉樹存儲結(jié)點(diǎn)的結(jié)構(gòu)圖1.35 二叉樹的鏈?zhǔn)酱鎯Y(jié)構(gòu)* 對于滿二叉樹與完全二叉樹來說，可以按層序進(jìn)行順序存儲，這樣，不僅 節(jié)省了存儲空間，又能方便地確定每一個結(jié)點(diǎn)的父結(jié)點(diǎn)與左右子結(jié)點(diǎn)的位置， 但順序存儲結(jié)構(gòu)對于一般的二叉樹不適用。四、二叉樹的遍歷定義：二叉樹的遍歷是指不重復(fù)地訪問二叉樹中的所有結(jié)點(diǎn)。* 在遍歷二叉樹的過程中，一般先遍歷左子樹，然后再遍歷右子樹。在先左 后右的原則下，根據(jù)訪問根結(jié)點(diǎn)的次序，二叉樹的遍歷可以分為三種：前序遍 歷、中序遍歷、后序遍歷。1 .前序遍歷(DLR定義：在訪問根結(jié)點(diǎn)、遍歷左子樹與遍歷右子樹這三者中，首先訪問根結(jié) 點(diǎn)，然后遍歷左子樹，最后遍歷右子樹；并且，在遍歷左、右子樹時，仍然先 訪問根結(jié)點(diǎn)，然后遍歷左子樹，最后遍歷右子樹。二叉樹前序遍歷的簡單描述：若二叉樹為空，則結(jié)束返回。否則：訪問根結(jié)點(diǎn)；前序遍歷左子