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

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

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

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

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

6、幾何？假設買母雞I只、公雞J只、小雞KN。根據題意，粗略的列舉算法描述 如下：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共有三層循環，每層循環各需要循環101次，大約為100萬次。優化后的算法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共有兩層循環，循環次數為2 .歸納法(1)基本思想通過列舉少量的特殊情況，經過分析最后找出一般的關系。(2)特點歸納是一種抽象，即從特殊現象中找出一般關系。(3)使用由于在歸納的過程中不可能對所有的情況進行列舉。因此，最后由歸納得 到的結論還只是一種猜測，還需要對這種猜測加以必要的證明。實際上，通過 精心觀察而得到的猜測得不到證實或最后證明猜測是錯的，也是常有的事。3 .遞推(1)基本思想從已知的初始條件出發，逐次推出所要求的各中間結果和最后結果。(2)特點本質上屬于歸納法，遞推關系式往往是歸納的結果。(3)使用遞推算法在數值計算中是極為常見

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

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

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

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

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

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

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

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

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

18、據處理的效率是不同的。二、數據結構的圖形表示一個數據結構除了用二元關系表示外，還可以直觀地用圖形表示。(1)對于數據集合D中的每一個數據元素用中間標有元素值的方框表示，一般稱之為數據結點，并簡稱為結點；(2)對于關系R中的每一個二元組，用一條有向線段從前件結點指向后件 結點，有時箭頭可省去。圖1-1 一年四季數據結構的圖形表示圖1-2家庭成員間輩分關系數據結構的圖形表示例1.8 用圖形表示數據結構 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) 在數據結構中，沒有前件的結點稱為根結點；沒有后件的結點稱為終端結點(也稱為葉子結點)。圖1.3 例1.8數據結構的圖形表示三、線性結構與非線性結構根據數據結構中各數據元素之間前后件關系的復雜程度，一般將數據結構分為兩大類型：線性結構與非線性結構。如果一個非空的數據結構滿足下列兩個條件：(1)有且只有一個根結點；(2)每一個結點最多有一個前件，也最多有一個后件。則稱該數據結構為線性結構，線性結構又稱線性表。* 在一個線性結構中插入或刪除任何一個結點后還應是線性結構。圖1.4 不是線性結構的數據結構特例如果一個數據結構不是線性結構，則稱之為非線性結構。* 線性結構與非線性結構都可以

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

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

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

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

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

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

26、來說是合適的，因為順序存儲的結構比較簡單。*但這種順序存儲的方式對于元素經常需要變動的大線性表就不太合適了， 因為插入與刪除的效率比較低。第四節棧和隊列一、棧及其基本運算1 .什么是棧定義：限定在一端進行插入與刪除的線性表* 在棧中，允許插入與刪除的一端稱為棧頂，而不允許插入與刪除的另一端 稱為棧底。用指針top來指不棧頂的位置，用指針 bottom指向棧底。* 棧頂元素總是最后被插入的元素，從而也是最先能被刪除的元素；棧底元 素總是最先被插入的元素，從而也是最后才能被刪除的元素。即棧是按照“先 進后出”或“后進先出”的原則組織數據的，因此，棧也被稱為“先進后出” 表或“后進先出”表。* 棧具

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

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

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

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

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

32、算有三種：入棧、退棧與讀棧頂元素。(1)入棧運算入棧運算是指在棧頂位置插入一個新元素。操作過程如下：首先判斷棧頂指針是否已經指向存儲空間的最后一個位置。如果是，則 說明棧空間已滿，不可能再進行入棧操作(這種情況稱為棧“上溢”錯誤)， 算法結束。然后將棧頂指針進一(即top加1)。最后將新元素x插入棧頂指針指向的位置。(2)退棧運算退棧運算是指取出棧頂元素并賦給一個指定的變量。操作過程如下：首先判斷棧頂指針是否為 00如果是，則說明棧空，不可能進行退棧操作(這種情況稱為棧“下溢”錯誤)，算法結束。然后將棧頂元素(棧頂指針指向的元素)賦給一個指定的變量。最后將棧頂指針退一(即 top減1)。(3)

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

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

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

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

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

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

39、表分配順序存儲空間后，如果出現線性表的存儲空間已 滿，但還需要插入新的元素時，就會發生“上溢”錯誤。（3）線性表的順序存儲結構不便于對存儲空間的動態分配。因此，對于大的線性表，特別是元素變動頻繁的大線性表不宜采用順序存 儲結構，而是采用下面要介紹的鏈式存儲結構。* 假設數據結構中的每一個數據結點對應于一個存儲單元，這種存儲單元稱 為存儲結點，簡稱結點。* 在鏈式存儲方式中，要求每個結點由兩部分組成：一部分用于存放數據元 素值，稱為數據域；另一部分用于存放指針，稱為指針域。其中指針用于指向 該結點的前一個或后一個結點（即前件或后件）。* 在鏈式存儲結構中，存儲數據結構的存儲空間可以不連續，各數據

40、結點的 存儲順序與數據元素之間的邏輯關系可以不一致，而數據元素之間的邏輯關系 是由指針域來確定的。* 鏈式存儲方式既可用于表示線性結構，也可用于表示非線性結構。在用鏈 式結構表示較復雜的非線性結構時，其指針域的個數要多一些。1 .線性鏈表定義：線性表的鏈式存儲結構稱為線性鏈表。為了存儲線性表中的每一個元素，一方面要存儲數據元素的值，另一方面 要存儲各數據元素之間的前后件關系。圖1.15 線性鏈表的存儲空間為了適應線性表的鏈式存儲結構，計算機存儲空間被劃分為一個一個小塊， 每一小塊占若干字節，通常稱這些小塊為存儲結點。圖1.16 線性鏈表的一個存儲結點* 在線性鏈表中，用一個專門的指針HEA討旨

41、向線性鏈表中第一個數據元素的結點（即存放線性表中第一個數據元素的存儲結點的序號）。線性表中最后一個元素沒有后件，因此，線性鏈表中最后一個結點的指針域為空（用NULL或0表示），表示鏈表終止。圖1.17 線性鏈表的邏輯結構* 在線性表的鏈式存儲結構中，各數據結點的存儲序號是不連續的，并且各 結點在存儲空間中的位置關系與邏輯關系也不一致。* 當HEAD= NULL（或0）時稱為空表。圖1.18 線性鏈表例* 在這種鏈表中，每一個結點只有一個指針域，由這個指針只能找到后件結 點，但不能找到前件結點。因此，在這種線性鏈表中，只能順指針向鏈尾方向進行掃描，這對于某些 問題的處理會帶來不便，因為在這種鏈接

42、方式下，由某一個結點出發，只能找 到它的后件，而為了找出它的前件，必須從頭指針開始重新尋找。為了彌補線性單鏈表的這個缺點，在某些應用中，對線性鏈表中的每個結 點設置兩個指針，一個稱為左指針（Llink ）,用以指向其前件結點；另一個稱 為右指針（Rlink ）,用以指向其后件結點。這樣的線性鏈表稱為雙向鏈表。圖1.19 雙向鏈表示意圖2 .帶鏈的棧棧也是線性表，也可以采用鏈式存儲結構。圖1.20 帶鏈的棧在實際應用中，帶鏈的棧可以用來收集計算機存儲空間中所有空閑的存儲 結點，這種帶鏈的棧稱為可利用棧。圖1.21 可利用棧及其運算與順序棧一樣，帶鏈棧的基本操作有以下幾個：棧的初始化。即建立一個空

43、棧的順序存儲空間。入棧運算。是指在棧頂位置插入一個新元素。退棧運算。是指取出棧頂元素并賦給一個指定的變量。讀棧頂元素。是指將棧頂元素賦給一個指定的變量。3 .帶鏈的隊列隊列也是線性表，也可以采用鏈式存儲結構。圖1.22 帶鏈的隊列及其運算與順序隊列一樣，帶鏈隊列的基本操作有以下幾個：隊列的初始化。即建立一個空隊列的順序存儲空間。入隊運算。是指在循環隊列的隊尾加入一個新元素。退隊運算。是指在循環隊列的排頭位置退出一個元素并賦給指定的變量。二、線性鏈表的基本運算線性鏈表的運算主要有以下幾個：在線性鏈表中包含指定元素的結點之前插入一個新元素。在線性鏈表中刪除包含指定元素的結點。將兩個線性鏈表按要求合

44、并成一個線性鏈表將一個線性鏈表按要求進行分解。逆轉線性鏈表。復制線性鏈表。線性鏈表的排序。線性鏈表的查找。1 .在線性鏈表中查找指定元素在非空線性鏈表中尋找包含指定元素值 x的前一個結點p的基本方法如下:從頭指針指向的結點開始往后沿指針進行掃描，直到后面已沒有結點或下 一個結點的數據域為x為止。因此，由這種方法找到的結點 p有兩種可能：*當線性鏈表中存在包含元素 x的結點時，則找到的p為第一次遇到的包含 元素x的前一個結點序號；*當線性鏈表中不存在包含元素 x的結點時，則找到的p為線性鏈表中的最 后一個結點號。2 .線性鏈表的插入(1)定義在鏈式存儲結構下的線性表中插入一個新元素。(2)插入過

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

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

47、元素后，不需要移動表的數據元素，只需改變被刪 除元素所在結點的前一個結點的指針域即可。*當從線性鏈表中刪除一個元素后，該元素的存儲結點就變為空閑，應將該 空閑結點送回到可利用棧。三、循環鏈表前面所討論的線性鏈表中，其插入與刪除的運算雖然比較方便，但還存在 一個問題，在運算過程中對于空表和對第一個結點的處理必須單獨考慮，使空 表與非空表的運算不統一。1 .循環鏈表的特點(1)在循環鏈表中增加了一個表頭結點，其數據域為任意或者根據需要來 設置，指針域指向線性表的第一個元素的結點。循環鏈表的頭指針指向表頭結 點。(2)循環鏈表中最后一個結點的指針域不是空，而是指向表頭結點。即在 循環鏈表中，所有結點

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

49、每一個結點只有一個前件，稱為父結點，沒有前件的結點只 有一個，稱為樹的根結點，簡稱為樹的根。* 在樹結構中，每一個結點可以有多個后件，它們都稱為該結點的子結點。 沒有后件的結點稱為葉子結點。* 在樹結構中，一個結點所擁有的后件個數稱為該結點的度。* 在樹中，所有結點中的最大的度稱為樹的度。* 樹中的結點數=樹中所有結點的度之和+1 0* 根結點在第1層。同一層上所有結點的所有子結點都在下一層。樹的最大 層次稱為樹的深度。在計算機中，可以用樹結構來表示算術表達式。用樹來表示算術表達式的原則如下：表達式中的每一個運算符在樹中對應一個結點，稱為運算符結點。運算符的每一個運算對象在樹中為該運算符結點的

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

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

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

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

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

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