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

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

2、試指導(dǎo)視頻講解真題解析部分全國(guó)計(jì)算機(jī)等級(jí)考試二級(jí) C+鋪言程序設(shè)計(jì)真題及詳解（一）全國(guó)計(jì)算機(jī)等級(jí)考試二級(jí) C+吾言程序設(shè)計(jì)真題及詳解（二）全國(guó)計(jì)算機(jī)等級(jí)考試二級(jí) C+吾言程序設(shè)計(jì)真題及詳解（三）全國(guó)計(jì)算機(jī)等級(jí)考試二級(jí) C+吾言程序設(shè)計(jì)真題及詳解（四）教材精講部分視頻講解第一部分公共基礎(chǔ)知識(shí)視頻講解考試形式1 .公共基礎(chǔ)知識(shí)不單獨(dú)考試，與其他二級(jí)科目組合在一起，作為二級(jí)科目考核內(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)行軟件開(kāi)發(fā)的能力。6 .掌握數(shù)據(jù)庫(kù)的基本知識(shí)，了解關(guān)系數(shù)據(jù)庫(kù)的設(shè)計(jì)。知識(shí)點(diǎn)分布1 .數(shù)據(jù)結(jié)構(gòu)與算法2 .程序設(shè)計(jì)基礎(chǔ)3 .軟件工程基礎(chǔ)4 .數(shù)據(jù)庫(kù)設(shè)計(jì)基礎(chǔ)第1章 數(shù)據(jù)結(jié)構(gòu)與算法視頻講解本章考點(diǎn)1 .算法的基本概念；算法復(fù)雜度的概念和意義(時(shí)間復(fù)雜度與空間復(fù)雜度)2 .數(shù)據(jù)結(jié)構(gòu)的定義；數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)；數(shù)據(jù)結(jié)構(gòu)的圖形表示； 線性結(jié)構(gòu)與非線性結(jié)構(gòu)的概念。3 .線性表的定義；線性表的順序存儲(chǔ)結(jié)構(gòu)及其插入與刪除運(yùn)算。4 .棧和隊(duì)列的定義；棧和隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)及其基本運(yùn)算。5 .線性單鏈表、雙向鏈表與循環(huán)鏈表的結(jié)構(gòu)及其基本運(yùn)算。6 .樹(shù)的基本概念；二叉樹(shù)的定

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

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

6、幾何？假設(shè)買(mǎi)母雞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萬(wàn)次。優(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)基本思想通過(guò)列舉少量的特殊情況，經(jīng)過(guò)分析最后找出一般的關(guān)系。(2)特點(diǎn)歸納是一種抽象，即從特殊現(xiàn)象中找出一般關(guān)系。(3)使用由于在歸納的過(guò)程中不可能對(duì)所有的情況進(jìn)行列舉。因此，最后由歸納得 到的結(jié)論還只是一種猜測(cè)，還需要對(duì)這種猜測(cè)加以必要的證明。實(shí)際上，通過(guò) 精心觀察而得到的猜測(cè)得不到證實(shí)或最后證明猜測(cè)是錯(cuò)的，也是常有的事。3 .遞推(1)基本思想從已知的初始條件出發(fā)，逐次推出所要求的各中間結(jié)果和最后結(jié)果。(2)特點(diǎn)本質(zhì)上屬于歸納法，遞推關(guān)系式往往是歸納的結(jié)果。(3)使用遞推算法在數(shù)值計(jì)算中是極為常見(jiàn)

8、的。但是，對(duì)于數(shù)值型的遞推算法必須要注意數(shù)值計(jì)算的穩(wěn)定性問(wèn)題。4 .遞歸*(1)基本思想為了降低問(wèn)題的復(fù)雜程度，將問(wèn)題逐層分解，最后歸結(jié)為一些最簡(jiǎn)單的問(wèn) 題，這種將問(wèn)題逐層分解的過(guò)程，實(shí)際上并沒(méi)有對(duì)問(wèn)題進(jìn)行求解，而只是當(dāng)解 決了最后那些最簡(jiǎn)單的問(wèn)題后，再沿著原來(lái)分解的逆過(guò)程逐步進(jìn)行綜合。(2)特點(diǎn)結(jié)構(gòu)清晰，可讀性強(qiáng)。(3)使用遞歸在可計(jì)算性理論和算法設(shè)計(jì)中占有很重要的地位。(4)分類(lèi)直接遞歸(自己調(diào)用自己)和間接遞歸( P調(diào)用Q Q又調(diào)用P)。例1.2 編寫(xiě)一個(gè)過(guò)程，對(duì)于輸入的參數(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ù)所謂“減半”，是指將問(wèn)題的規(guī)模減半，而問(wèn)題的性質(zhì)不變；所謂“遞推”， 是指重復(fù)“減半”的過(guò)程。例1.3 設(shè)方程f (x) =0在區(qū)間a , b上有實(shí)根，且f (a)與f (b)異號(hào)。 利用二分法求該方程在區(qū)間a , b上的一個(gè)實(shí)根。用二分法求方程實(shí)根的減半遞推過(guò)程如下：首先取給定區(qū)間的中點(diǎn) c= (a+b) /2。然后判斷f (c)是否為0o若f (c) =0,則說(shuō)明C即為所求的根，求解過(guò)程結(jié)束；如果f (c)乎0,則根據(jù)以下原則

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

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

12、定輸入下的基本運(yùn)算次數(shù)的加權(quán)平均值來(lái)度量算法的工作量。最壞情況復(fù)雜性(Worst-Case Complexity)規(guī)模為n時(shí)，算法所執(zhí)行的基本運(yùn)算的最大次數(shù)。w)=max«(X)x D n例1.4 采用順序搜索法，在長(zhǎng)度為n的一維數(shù)組中查找值為 x的元素。即 從數(shù)組的第一個(gè)元素開(kāi)始，逐個(gè)與被查值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ì)算工作量與輸入無(wú)關(guān)時(shí)，即當(dāng)規(guī)模為n時(shí)，在所有可能的輸入下，算法所執(zhí)行

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

14、 存儲(chǔ)結(jié)構(gòu)；(3)對(duì)各種數(shù)據(jù)結(jié)構(gòu)進(jìn)行的運(yùn)算。討論以上問(wèn)題的目的：(1)提高數(shù)據(jù)處理的速度；(2)盡量節(jié)省在數(shù)據(jù)處理過(guò)程中所占用的計(jì)算機(jī)存儲(chǔ)空間。一、什么是數(shù)據(jù)結(jié)構(gòu)定義：數(shù)據(jù)結(jié)構(gòu)是指相互有關(guān)聯(lián)的數(shù)據(jù)元素的集合。數(shù)據(jù)元素具有廣泛的含義：描述一年四季的季節(jié)名：春、夏、秋、冬表示數(shù)值的各個(gè)數(shù)：18、11、35、23、16表示家庭成員的各成員名：父親、兒子、女兒數(shù)據(jù)處理：對(duì)數(shù)據(jù)集合中的各元素以各種方式進(jìn)行運(yùn)算，包括插入、刪除、 查找、更改等運(yùn)算，也包括對(duì)數(shù)據(jù)元素進(jìn)行分析。*作為某種處理，其中的數(shù)據(jù)元素一般具有某種共同特征，一般情況下，在 具有相同特征的數(shù)據(jù)元素集合中，各個(gè)數(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)。一個(gè)數(shù)據(jù)結(jié)構(gòu)應(yīng)包含以下兩方面的信息：表示數(shù)據(jù)元素的信息；表示各數(shù)據(jù)元素之間的前后件關(guān)系。(2)數(shù)據(jù)的邏輯結(jié)構(gòu)有兩個(gè)要素：一是數(shù)據(jù)元素的集合，通常記為D;二是D上的關(guān)系，它反映了 D中各數(shù)據(jù)元素之間的前后件關(guān)系，通常記為R;即一個(gè)數(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) * 對(duì)于一些復(fù)雜的數(shù)據(jù)結(jié)構(gòu)來(lái)說(shuō)，它的數(shù)據(jù)元素可以是另一種數(shù)據(jù)結(jié)構(gòu)。例如，mXn的矩陣是一個(gè)數(shù)據(jù)結(jié)構(gòu)。在這個(gè)數(shù)據(jù)結(jié)構(gòu)中，矩陣的每一行Ai= (an , ai2,，an) , i=1 , 2,，m可以看成是它的一個(gè)數(shù)據(jù)元素。即這個(gè)數(shù)據(jù)結(jié)構(gòu)的數(shù)據(jù)元素的集合為D=A1, A2,，AmD上的一個(gè)關(guān)系為R= (Ai, A) ,(A2, A),，(A, A+1),，(Am-1, Am)

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

18、據(jù)處理的效率是不同的。二、數(shù)據(jù)結(jié)構(gòu)的圖形表示一個(gè)數(shù)據(jù)結(jié)構(gòu)除了用二元關(guān)系表示外，還可以直觀地用圖形表示。(1)對(duì)于數(shù)據(jù)集合D中的每一個(gè)數(shù)據(jù)元素用中間標(biāo)有元素值的方框表示，一般稱(chēng)之為數(shù)據(jù)結(jié)點(diǎn)，并簡(jiǎn)稱(chēng)為結(jié)點(diǎn)；(2)對(duì)于關(guān)系R中的每一個(gè)二元組，用一條有向線段從前件結(jié)點(diǎn)指向后件 結(jié)點(diǎn)，有時(shí)箭頭可省去。圖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)中，沒(méi)有前件的結(jié)點(diǎn)稱(chēng)為根結(jié)點(diǎn)；沒(méi)有后件的結(jié)點(diǎn)稱(chēng)為終端結(jié)點(diǎn)(也稱(chēng)為葉子結(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)分為兩大類(lèi)型：線性結(jié)構(gòu)與非線性結(jié)構(gòu)。如果一個(gè)非空的數(shù)據(jù)結(jié)構(gòu)滿(mǎn)足下列兩個(gè)條件：(1)有且只有一個(gè)根結(jié)點(diǎn)；(2)每一個(gè)結(jié)點(diǎn)最多有一個(gè)前件，也最多有一個(gè)后件。則稱(chēng)該數(shù)據(jù)結(jié)構(gòu)為線性結(jié)構(gòu)，線性結(jié)構(gòu)又稱(chēng)線性表。* 在一個(gè)線性結(jié)構(gòu)中插入或刪除任何一個(gè)結(jié)點(diǎn)后還應(yīng)是線性結(jié)構(gòu)。圖1.4 不是線性結(jié)構(gòu)的數(shù)據(jù)結(jié)構(gòu)特例如果一個(gè)數(shù)據(jù)結(jié)構(gòu)不是線性結(jié)構(gòu)，則稱(chēng)之為非線性結(jié)構(gòu)。* 線性結(jié)構(gòu)與非線性結(jié)構(gòu)都可以

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

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

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

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

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

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

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

27、有記憶作用。* 往棧中插入一個(gè)元素稱(chēng)為入棧運(yùn)算，從棧中刪除一個(gè)元素(即刪除棧頂元 素)稱(chēng)為退棧運(yùn)算。計(jì)算機(jī)系統(tǒng)在處理時(shí)要用一個(gè)線性表來(lái)動(dòng)態(tài)記憶調(diào)用過(guò)程中的路徑，其基 本原則如下：(1)在開(kāi)始執(zhí)行程序前，建立一個(gè)線性表，初始狀態(tài)為空；(2)發(fā)生調(diào)用時(shí)，將當(dāng)前調(diào)用的返回點(diǎn)地址插入到線性表的末尾；(3)當(dāng)遇到從某個(gè)子程序返回時(shí)，其返回點(diǎn)地址從線性表的末尾取出(即 刪除線性表的最后一個(gè)元素)。圖1.9 棧不'意圖圖1.8中給出了具有嵌套調(diào)用關(guān)系的五個(gè)程序，其中主程序要調(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中五個(gè)程序在執(zhí)行過(guò)程中的調(diào)用順序以及線性表中元素變化的情況 如下：(1)主程序開(kāi)始執(zhí)行前，建立一個(gè)空線性表。即線性表的狀態(tài)為()o(2)開(kāi)始執(zhí)行主程序MAIN當(dāng)要調(diào)用子程序SUB1時(shí)，先將本次調(diào)用的返回點(diǎn)地址A插入到線性表的末尾。此時(shí)，線性表的狀態(tài)為(A) o(3)開(kāi)始調(diào)用執(zhí)行子程序 SUB1當(dāng)要調(diào)用子程序 SUB2時(shí)，先將本次調(diào)用 的返回點(diǎn)地址B插入到線性表的末尾。止匕時(shí),線性表的X犬態(tài)為(A, B)。(4)開(kāi)始調(diào)用執(zhí)行子程序 SUB2當(dāng)要調(diào)用子程序 SUB3時(shí)，先將本次調(diào)用的返回點(diǎn)地址C插入到線性表的末尾。此時(shí)，線性表的狀態(tài)為(A,

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

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

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

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

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

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

35、反映了隊(duì)列中元素動(dòng)態(tài) 變化的情況。圖1.11 具有6個(gè)元素的隊(duì)列示意圖圖1.12 隊(duì)列運(yùn)算示意圖2 .循環(huán)隊(duì)列及其運(yùn)算定義：所謂循環(huán)隊(duì)列，就是將隊(duì)列存儲(chǔ)空間的最后一個(gè)位置繞到第一個(gè)位 置，形成邏輯上的環(huán)狀空間，供隊(duì)列循環(huán)使用。* 在循環(huán)隊(duì)列中，用隊(duì)尾指針rear指向隊(duì)列中的隊(duì)尾元素，用排頭指針front 指向排頭元素的前一個(gè)位置，因此，從排頭指針front指向的后一個(gè)位置直到隊(duì)尾指針rear指向的位置之間所有的元素均為隊(duì)列中的元素。* 循環(huán)隊(duì)列的初始狀態(tài)為空，即rear=front=m ,如圖1.13所示。圖1.13 循環(huán)隊(duì)列存儲(chǔ)空間示意圖循環(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時(shí)，則置rear=1。每進(jìn)行一次退隊(duì)運(yùn)算，排頭指針就進(jìn)一。當(dāng)排頭指針front=m+1時(shí)，則置front=1 0圖1.14 循環(huán)隊(duì)列運(yùn)算例* 當(dāng)循環(huán)隊(duì)列滿(mǎn)時(shí)有front=rear ,而當(dāng)循環(huán)隊(duì)列空時(shí)也有 front=rear 。即 在循環(huán)隊(duì)列中，當(dāng)front=rear 時(shí)，不能確定是隊(duì)列滿(mǎn)還是隊(duì)列空。在實(shí)際使用循環(huán)隊(duì)列時(shí)，為了能區(qū)分隊(duì)列滿(mǎn)還是隊(duì)列空，通常還需增加一 個(gè)標(biāo)志s, s值的定義如下：由此可以得出隊(duì)列空與隊(duì)列滿(mǎn)的條件如下：隊(duì)列空的條件為s=0；隊(duì)列滿(mǎn)的條件為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ì)尾加入一個(gè)新元素。操作過(guò)程如下：首先判斷循環(huán)隊(duì)列是否滿(mǎn)。當(dāng)循環(huán)隊(duì)列非空（S=1）且隊(duì)尾指針等于排頭指針時(shí)，說(shuō)明循環(huán)隊(duì)列已滿(mǎn)，不能進(jìn)行入隊(duì)運(yùn)算。這種情況稱(chēng)為“上溢”。此 時(shí)算法結(jié)束。然后將隊(duì)尾指針進(jìn)一（即 rear=rear+1 ）,并當(dāng)rear=m+1時(shí)置rear=1 。最后將新元素x插入隊(duì)尾指針指向的位置，并且置循環(huán)隊(duì)列非空標(biāo)志。（2）退隊(duì)運(yùn)算退隊(duì)運(yùn)算是指在循環(huán)隊(duì)列的排頭位置退出一個(gè)元素并賦給指定的變量。操 作過(guò)程如下：首先判斷循環(huán)隊(duì)列是否為空。當(dāng)循環(huán)隊(duì)列為空（s=0）時(shí)，不能進(jìn)行退隊(duì)運(yùn)算。這種情況稱(chēng)為“下溢”。此時(shí)算法結(jié)束。

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

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

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

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

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

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

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

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

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

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

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

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

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

51、樹(shù)的基本性質(zhì)性質(zhì)1在二叉樹(shù)的第k層上，最多有2k-1 (k>1)個(gè)結(jié)點(diǎn)。性質(zhì)2深度為m的二叉樹(shù)最多有2m-1個(gè)結(jié)點(diǎn)。21-1+22-1+2m-1=221性質(zhì)3在任意一棵二叉樹(shù)中，度為 0的結(jié)點(diǎn)(即葉子結(jié)點(diǎn))總是比度為 2 的結(jié)點(diǎn)多一個(gè)。二叉樹(shù)中總的結(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個(gè)結(jié)點(diǎn)的二叉樹(shù)，其深度至少為log 2n+1 ,其中l(wèi)og 2n表 示取log 2n的整數(shù)部分。3 .滿(mǎn)二叉樹(shù)與完全二叉樹(shù)(

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

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

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

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