1、第二章 基本數(shù)據(jù)結(jié)構(gòu)及運(yùn)算學(xué)習(xí)內(nèi)容n研究的內(nèi)容：n1、數(shù)據(jù)集合各數(shù)據(jù)間的邏輯結(jié)構(gòu)n2、數(shù)據(jù)集合各數(shù)據(jù)間的物理結(jié)構(gòu)n3、數(shù)據(jù)結(jié)構(gòu)的運(yùn)算內(nèi)容目錄n2.1 數(shù)據(jù)結(jié)構(gòu)的基本概念n2.2 線性表及順序存儲結(jié)構(gòu)n2.3 線性鏈表及運(yùn)算n2.5 樹與圖2.1數(shù)據(jù)結(jié)構(gòu)的基本概念n2.1.1 兩個例子n有序表與無序表分析n從兩個表中可以看出來數(shù)據(jù)元素在表中順序?qū)Σ檎倚视泻艽笥绊?.1.1 兩個例子n2.1.1 學(xué)生登記表 假設(shè)查找假設(shè)查找90的同學(xué)時，就必須遍歷整個數(shù)據(jù)表格。這樣效率很低。的同學(xué)時，就必須遍歷整個數(shù)據(jù)表格。這樣效率很低。2.1數(shù)據(jù)結(jié)構(gòu)的基本概念2.1.2 什么是數(shù)據(jù)結(jié)構(gòu)1數(shù)據(jù)（數(shù)據(jù)（data）

2、數(shù)據(jù)是指能夠輸入到計(jì)算機(jī)中，并被計(jì)算機(jī)識別和處理的符號的集合。 2數(shù)據(jù)元素（數(shù)據(jù)元素（data element）數(shù)據(jù)元素是組成數(shù)據(jù)的基本單位。數(shù)據(jù)元素是一個數(shù)據(jù)整體中相對獨(dú)立的單位。 但它還可以分割成若干個具有不同屬性的項(xiàng)（字段），故不是組成數(shù)據(jù)的最小單位2.1.2 什么是數(shù)據(jù)結(jié)構(gòu)姓姓名名俱樂俱樂部名部名稱稱出生日期出生日期年年 月月 日日 入隊(duì)入隊(duì)日期日期職職位位業(yè)業(yè)績績2.1.2 什么是數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)： 是指相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素所組成的集合。數(shù)據(jù)結(jié)構(gòu)包含三個方面的內(nèi)容，即數(shù)據(jù)的邏輯結(jié)構(gòu)，數(shù)據(jù)的存貯結(jié)構(gòu)和對數(shù)據(jù)所施加的運(yùn)算。這三個方面的關(guān)系為：這三個方面的關(guān)系為

3、： n數(shù)據(jù)的邏輯結(jié)構(gòu)獨(dú)立于計(jì)算機(jī)，是數(shù)據(jù)本身所固有的n存貯結(jié)構(gòu)是邏輯結(jié)構(gòu)在計(jì)算機(jī)存貯器中的映像，必須依賴于計(jì)算機(jī)。n運(yùn)算是指所施加的一組操作總稱。運(yùn)算的定義直接依賴于邏輯結(jié)構(gòu)，但運(yùn)算的實(shí)現(xiàn)必依賴于存貯結(jié)構(gòu)。2.1.2 什么是數(shù)據(jù)結(jié)構(gòu)n數(shù)據(jù)結(jié)構(gòu)應(yīng)該包含有兩個方面的知識：（1）數(shù)據(jù)元素信息（2）各數(shù)據(jù)元素之間的前后件關(guān)系。n反映數(shù)據(jù)元素之間前后件的邏輯關(guān)系，就是數(shù)據(jù)的邏輯結(jié)構(gòu)。n形式定義：形式定義：某一數(shù)據(jù)對象的所有數(shù)據(jù)成員之間的關(guān)系。記為：某一數(shù)據(jù)對象的所有數(shù)據(jù)成員之間的關(guān)系。記為： B B = (D, R) = (D, R) 其中，其中，D D 是某數(shù)據(jù)元素的集合，是某數(shù)據(jù)元素的集合， R R

4、 是各數(shù)據(jù)元素間的是各數(shù)據(jù)元素間的前后件關(guān)系。前后件關(guān)系。2.1.2 什么是數(shù)據(jù)結(jié)構(gòu)3、數(shù)據(jù)的常見存儲結(jié)構(gòu)：、數(shù)據(jù)的常見存儲結(jié)構(gòu)：(1) 順序存貯順序存貯所有元素存放在一片連續(xù)的存貯單元中，邏輯上相鄰的元素存放到計(jì)算機(jī)內(nèi)存仍然相鄰。(2) 鏈?zhǔn)酱尜A鏈?zhǔn)酱尜A所有元素存放在可以不連續(xù)的存貯單元中，元素之間的關(guān)系通過地址確定，邏輯上相鄰的元素存放到計(jì)算機(jī)內(nèi)存后不一定是相鄰的。(3) 索引存貯索引存貯 (4) 散列存貯散列存貯2.1.3 數(shù)據(jù)結(jié)構(gòu)的圖形表示一年四季數(shù)據(jù)結(jié)構(gòu)的圖形表示家庭成員間輩分關(guān)系數(shù)據(jù)結(jié)構(gòu)的圖形不是線性結(jié)構(gòu)的數(shù)據(jù)結(jié)構(gòu)特例線性表的兩個條件：線性表的兩個條件：1、有且只有一個根節(jié)點(diǎn)、有且

5、只有一個根節(jié)點(diǎn)2、每個節(jié)點(diǎn)最多有一個前、每個節(jié)點(diǎn)最多有一個前件，也最多只有一個后件。件，也最多只有一個后件。沒有前件的結(jié)點(diǎn)稱為根結(jié)點(diǎn)；沒有前件的結(jié)點(diǎn)稱為根結(jié)點(diǎn)；沒有后件的結(jié)點(diǎn)稱為終端結(jié)點(diǎn)沒有后件的結(jié)點(diǎn)稱為終端結(jié)點(diǎn)（葉子結(jié)點(diǎn)）。（葉子結(jié)點(diǎn)）。2.1.4 算法（算法（algorithm）定義：通俗地講，算法就是一種解題的方法。更嚴(yán)格地說，算法是由若干條指令組成的有窮序列，它必須滿足下述條件（也稱為算法的五大特性）：（1）輸入：具有0個或多個輸入的外界量（算法開始前的初始量）（2）輸出：至少產(chǎn)生一個輸出，它們是算法執(zhí)行完后的結(jié)果。（3）有窮性：每條指令的執(zhí)行次數(shù)必須是有限的。（4）確定性：每條指令的

6、含義都必須明確，無二義性。（5）可行性：每條指令的執(zhí)行時間都是有限的，算法是可行的。2.1.4 算法（算法（algorithm）算法分析算法分析-時間時間復(fù)雜度復(fù)雜度 一個算法花費(fèi)的時間與算法中語句的執(zhí)行次數(shù)成正比，哪個算法中語句執(zhí)行次數(shù)多，它花費(fèi)時間就多。 數(shù)據(jù)結(jié)構(gòu)中數(shù)據(jù)元素個數(shù)n稱為問題的規(guī)模，當(dāng)n不斷變化時，語句的執(zhí)行次數(shù)也會變化。一個算法中的時間復(fù)雜度一般用語句執(zhí)行次數(shù)的數(shù)量級來衡量。例如： for(i=1; i=n; i+) for(j =1; jn，最后元素后插入n c)i1，第1個元素前插入n2)然后從最后元素到第i個元素往后移動1個位置n3)將新元素插入到第i位置，表長度加1.

7、2.2.1.3 線性表順序存儲下插入運(yùn)算void ins_sq_LList(int * v,int m,int *n,int i,int b)int k;if(*n = m)coutoverflow *n)i = *n + 1;else if( i = i; k-)vk = vk-1;vi-1 = b;*n += 1; 2.2.1.4 線性表順序存儲下刪除運(yùn)算n例題：在下面圖中，現(xiàn)在要求刪除第一個元素29，然后刪除第6個元素。2.2.1.4 線性表順序存儲下刪除運(yùn)算n假設(shè)線性表的存儲空間為V1:m，線性表長度為n(nn,或者1，則在線性表的兩端進(jìn)行刪除n2）從第i+1元素開始到最后一個元素，均

8、前移一個位置n3）最后將線性表的長度減少1。2.2.1.4 線性表順序存儲下刪除運(yùn)算void del_sq_LList(int * v,int m, int *n,int i)int k;if(*n = 0)coutunderflow!endl; return;if(i *n)cout“This element is not in the listendl;for(k = i; k *n; k+)vk-1 = vk;*n = *n -1;return;2.2.1.5 線性表順序存儲下元素定位int Locate_sq_LList(int * v,int x, int &n)int i=0;wh

9、ile(in) & Vi!=x) i+; if(in) return (i+1); else return 0;作業(yè)內(nèi)容1設(shè)計(jì)一個靜態(tài)數(shù)組存儲結(jié)構(gòu)的順序表類，要求編程實(shí)現(xiàn)如下任務(wù)：1）建立一個線性表，首先依次輸人整數(shù)數(shù)據(jù)元素（個數(shù)根據(jù)自己的需要鍵盤給定）2）刪除指定位置的數(shù)據(jù)元素（指定元素位置通過鍵盤輸入）再依次顯示刪除后的線性表中的數(shù)據(jù)元素。3）查找指定數(shù)據(jù)的數(shù)據(jù)元素（指定數(shù)據(jù)的大小通過鍵盤輸入），若找到則顯示位置，若沒有找到就顯示0。要求：采用順序表實(shí)現(xiàn)，假設(shè)該順序表的數(shù)據(jù)元素個數(shù)在最壞情況下不會超過50個。2.2.2 棧n什么是棧2.3 棧n定義定義:是限定僅在表尾進(jìn)行插入或刪除操作的是

10、限定僅在表尾進(jìn)行插入或刪除操作的線性表。線性表。n允許插入和刪除的一端允許插入和刪除的一端n稱為棧頂稱為棧頂(top)，另一端，另一端n稱為棧底稱為棧底(bottom)n特點(diǎn)：后進(jìn)先出特點(diǎn)：后進(jìn)先出 (LIFO)a1topbottoman.進(jìn)棧進(jìn)棧 出棧出棧2.2.2 棧n棧的基本運(yùn)算有：n入棧；n出棧；n取棧頂元素；n判斷棧是否為空n判斷棧的溢出等棧的初始化n假設(shè)棧用順序存儲空間S(1:m)中，S(bottom)表示棧底元素，S(top)表示棧頂元素。Top=0，表示?？?，top=m表示棧滿。n/棧的初始化程序void init_stack(int *s ,int m, int *top)*

11、s = new intm;*top =0;return;入棧n入棧需要注意?？臻g是否已溢出。void push(int *s ,int m, int *top, int x)if(*top = m)coutoverflowendl;return;*top = *top + 1;s*top - 1 = x;return;出棧n要注意棧是否空，為空說明出棧無效int pop(int *s , int *top)int value;if(*top = 0)coutunderflowendl;eixt(0);value = s*top - 1;*top = *top - 1;return value;

12、讀棧頂元素int top(int *s , int *top)int value;if(*top = 0)coutunderflowendl;eixt(0);value = s*top - 1;return value;2.2.3 隊(duì)列n定義定義:只允許在表的一端進(jìn)行插入，而在另一只允許在表的一端進(jìn)行插入，而在另一端刪除元素的線性表。端刪除元素的線性表。n在隊(duì)列中，允許插入的一端叫隊(duì)尾（在隊(duì)列中，允許插入的一端叫隊(duì)尾（rear）n允許刪除的一端稱為對頭允許刪除的一端稱為對頭(front)。n特點(diǎn)：先進(jìn)先出特點(diǎn)：先進(jìn)先出 (FIFO) a1 ，a2， a3，an出隊(duì)列出隊(duì)列入隊(duì)列入隊(duì)列隊(duì)隊(duì)頭頭隊(duì)

13、隊(duì)尾尾2.2.3 隊(duì)列隊(duì)列示意圖 順序存儲的隊(duì)列中，每次出隊(duì)列的元素必定是隊(duì)頭元素，順序存儲的隊(duì)列中，每次出隊(duì)列的元素必定是隊(duì)頭元素，因此如果采取與普通順序表同樣的操作方式，則每次出隊(duì)操因此如果采取與普通順序表同樣的操作方式，則每次出隊(duì)操作必然將整個隊(duì)列向前移動，這使得效率大大降低。作必然將整個隊(duì)列向前移動，這使得效率大大降低。 因此在順序存儲的隊(duì)列中，出隊(duì)和入隊(duì)操作都不移動元因此在順序存儲的隊(duì)列中，出隊(duì)和入隊(duì)操作都不移動元素而是移動指針。素而是移動指針。 2.2.3 隊(duì)列(a)線性隊(duì)列線性隊(duì)列 3 2 1 0 (a)rear=front= 0(隊(duì)空）隊(duì)空） e3 e4 (c)(c) e1,e

14、2出隊(duì)，出隊(duì)，e4入隊(duì)入隊(duì) 隊(duì)隊(duì) 滿滿rear =4front e1 e2 e3 (b)rearfront(b)e1,e2,e3入隊(duì)入隊(duì)隊(duì)空時，隊(duì)空時， 令令rear=front= 0，當(dāng)有當(dāng)有新元素入隊(duì)時，尾指針加新元素入隊(duì)時，尾指針加1，當(dāng)有元，當(dāng)有元素出隊(duì)時，頭指針加素出隊(duì)時，頭指針加1。故在非空隊(duì)。故在非空隊(duì)列中，列中，頭指針頭指針始終指向始終指向隊(duì)頭元素前一隊(duì)頭元素前一個位置個位置，而，而尾指針尾指針始終指向始終指向隊(duì)尾元素隊(duì)尾元素的位置的位置 MAX=4假設(shè)假設(shè)MAX=4，當(dāng)隊(duì)列處于圖（，當(dāng)隊(duì)列處于圖（c）狀態(tài)，）狀態(tài)，rear=4時隊(duì)滿，此時隊(duì)滿，此時不能插入新元素，但實(shí)際上隊(duì)列

15、可用空間沒有滿，這是一時不能插入新元素，但實(shí)際上隊(duì)列可用空間沒有滿，這是一種假溢出現(xiàn)象。解決方法：將隊(duì)列頭尾相連形成一個環(huán)。種假溢出現(xiàn)象。解決方法：將隊(duì)列頭尾相連形成一個環(huán)。n線性隊(duì)列隊(duì)滿的條件：線性隊(duì)列隊(duì)滿的條件： rear = MAXn線性隊(duì)列隊(duì)空的條件：線性隊(duì)列隊(duì)空的條件： rear = front 3 2 1 0 (a)rear=front=0(隊(duì)空）隊(duì)空） e3 e4 (c)(c) e1,e2出隊(duì)，出隊(duì)，e4入隊(duì)入隊(duì) 隊(duì)隊(duì) 滿滿rear =4front e1 e2 e3 (b)rearfront(b)e1,e2,e3入隊(duì)入隊(duì) MAX=4 (b) 循環(huán)隊(duì)列循環(huán)隊(duì)列 rear front

16、 0 1 2 3(3) 隊(duì)空隊(duì)空區(qū)別隊(duì)空與隊(duì)滿的方法：如果區(qū)別隊(duì)空與隊(duì)滿的方法：如果隊(duì)尾加隊(duì)尾加1后等于隊(duì)頭指針即為隊(duì)后等于隊(duì)頭指針即為隊(duì)滿，即少用一個元素空間。滿，即少用一個元素空間。將頭尾連接成一將頭尾連接成一個環(huán)，形成循環(huán)個環(huán)，形成循環(huán)隊(duì)列。隊(duì)列。 rear(1)一般情況一般情況 front 0 1 2 3e4e3循環(huán)隊(duì)列隊(duì)空的條件：循環(huán)隊(duì)列隊(duì)空的條件： rear=front (2) 全部空間占滿全部空間占滿 front e3 e4 0 1 2 3 reare5e2循環(huán)隊(duì)列全部空間占滿循環(huán)隊(duì)列全部空間占滿 rear=fronte2rear%MAX+1=front另外一種辦法就是加一個判斷

17、另外一種辦法就是加一個判斷是否為空標(biāo)志位是否為空標(biāo)志位s來進(jìn)行區(qū)分。來進(jìn)行區(qū)分。2.2.3 隊(duì)列n隊(duì)列運(yùn)算n（1）設(shè)置一個空隊(duì)列；n（2）插入一個新的隊(duì)尾元素，稱為進(jìn)隊(duì)；n（3）刪除隊(duì)頭元素，稱為出隊(duì)；n（4）讀取隊(duì)頭元素；隊(duì)列的初始化n假設(shè)隊(duì)列為q，front為隊(duì)頭，rear為隊(duì)尾，m為隊(duì)列容量，s表示隊(duì)列是否為空，為1表示非空。void init_Queue(int *q,int m,int *front,int *rear,int *s)*q = new intm;*front = *rear =m;*s= 0;入隊(duì)操作void addcq(int *q,int m,int *front

18、,int *rear,int *s,int x)if(*s = 1) &(*rear = *front)coutoverflowendl;return;*rear += 1;if(*rear = m+1) *rear = 1;q*rear - 1 =x;*s = 1;return ;出隊(duì)列int delcq(int *q,int m,int *rear,int *front,int *s)int y;if(*s = 0)coutunderflowendl;exit(0);*front = *front%m+1;y = q*front -1;if(*front = *rear)*s = 0;re

19、turn y;測控領(lǐng)域相關(guān)應(yīng)用舉例例題1：在某類產(chǎn)品生產(chǎn)線、輸送線的開關(guān)控制中，涉及到對多個電機(jī)的順序開啟，和逆序關(guān)停問題。假定需要順序開啟A1、A2、A3、A4、A5共計(jì)5個電機(jī)，關(guān)停時需要按照A5、A4、A3、A2、A1的順序操作。試設(shè)計(jì)一個數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)對電機(jī)關(guān)停操作指令的存儲。 例題2：工業(yè)控制中，多設(shè)備之間的通信時，當(dāng)設(shè)備來不及處理數(shù)據(jù)時，通常會采用緩存機(jī)制。結(jié)合應(yīng)用需求，思考如下問題：1. 采用何種結(jié)構(gòu)構(gòu)建緩存？2. 緩存大小設(shè)定依據(jù)？3. 緩存的操作（如讀、寫緩存）實(shí)現(xiàn)方法？作業(yè)題目n 定義數(shù)據(jù)元素的數(shù)據(jù)類型為如下形式的結(jié)構(gòu)體：ntypedef structn char taskn

20、ame10;/任務(wù)名n int taskno;/任務(wù)號n DataType；n 設(shè)計(jì)一個包含5個數(shù)據(jù)元素的測試數(shù)據(jù)，并設(shè)計(jì)一個主函數(shù)實(shí)現(xiàn)依次把5個數(shù)據(jù)元素入棧，然后出棧堆棧中的數(shù)據(jù)元素并在屏幕上顯示。2.3 線性鏈表及其運(yùn)算n2.3.1 線性鏈表的基本概念n2.3.2 線性鏈表的基本運(yùn)算n2.3.3 循環(huán)鏈表2.3.1 線性鏈表的基本概念n線性表的順序存儲存在以下幾個方面的缺點(diǎn)：n1、插入或者刪除一個節(jié)點(diǎn)，需要涉及到大量元素的移動問題。n2、容易出現(xiàn)上溢或者下溢現(xiàn)象，存儲空間不易擴(kuò)展。n3、多個線性表共享存儲空間時，存在存儲問題。n因此在涉及到元素大量移動變動的表中，不宜采用線性表結(jié)構(gòu)。2.3

21、.1 線性鏈表的基本概念鏈?zhǔn)酱鎯Y(jié)構(gòu)：鏈?zhǔn)酱鎯Y(jié)構(gòu)：n每個節(jié)點(diǎn)有兩部分組成：一個部分用存儲數(shù)據(jù)元素，稱為數(shù)據(jù)域；另外一部分存放指針，叫為指針域。n鏈?zhǔn)酱鎯χ性刂g的前后件關(guān)系可以通過指針來標(biāo)識。n鏈?zhǔn)酱鎯Y(jié)構(gòu)既可以用于順序存儲，也可以用于較復(fù)雜的非線性存儲。2.3.1 線性鏈表的基本概念n1 線性鏈表鏈?zhǔn)降拇鎯Y(jié)構(gòu)線性鏈表的邏輯結(jié)構(gòu)2.3.1 線性鏈表的基本概念線性鏈表例2.3.1 線性鏈表的基本概念struct node int d; struct node *next;class linked_List /線性鏈表類線性鏈表類 private: /數(shù)據(jù)成員數(shù)據(jù)成員struct node

22、*head; /鏈表頭指針鏈表頭指針 public: /成員函數(shù)成員函數(shù)linked_List(); /構(gòu)造函數(shù)構(gòu)造函數(shù),建立空鏈表建立空鏈表 int flag_linked_list(); /判斷鏈表是否為空判斷鏈表是否為空void prt_linked_List(); /掃描輸出鏈表中的元素掃描輸出鏈表中的元素void ins_linked_List(T); /在頭結(jié)點(diǎn)前插入新元素在頭結(jié)點(diǎn)前插入新元素bint del_linked_List(）; /刪除鏈頭結(jié)點(diǎn)刪除鏈頭結(jié)點(diǎn);2.3.1 線性鏈表的基本概念/構(gòu)造函數(shù)構(gòu)造函數(shù) 初始化鏈表初始化鏈表linked_List : linked_Li

23、st ()head = null;/判斷鏈表是否為空判斷鏈表是否為空int linked_List : flag_linked_list()if(head = null)return 0;return 1;2.3.1 線性鏈表的基本概念/掃描輸出鏈表中的元素掃描輸出鏈表中的元素void linked_List : prt_linked_List()struct node * p; p=head;if(p=null)cout“empty list”endl; return;docoutdnext;while(p!=null);return;2.3.1 線性鏈表的基本概念 /在頭結(jié)點(diǎn)前插入新元素在

24、頭結(jié)點(diǎn)前插入新元素bvoid linked_List : ins_linked_List(int x) struct node * p;p = new node;P-d = x;p-next = head;head = p;return;2.3.1 線性鏈表的基本概念/刪除鏈頭結(jié)點(diǎn)刪除鏈頭結(jié)點(diǎn)int linked_List : del_linked_List( ) int y;struct node * q;if(head = null)cout“empty list”d;head = q-next;delete q;return y;2.3.1 線性鏈表的基本概念n3.帶鏈的棧（代碼略）圖2

25、.23 帶鏈的?？衫脳＜捌溥\(yùn)算2.3.1 線性鏈表的基本概念n4 帶鏈的隊(duì)列（代碼略）帶鏈的隊(duì)列及其運(yùn)算2.3.2 線性鏈表的基本運(yùn)算n1、在指定節(jié)點(diǎn)前插入一個新元素n2、刪除指定元素n3、將兩個鏈表合成一個線性鏈表n4、線性表的分解n5、逆轉(zhuǎn)線性表n6、復(fù)制線性鏈表n7、線性表的排序n8、線性表的查找相關(guān)操作n首先定義一個線性鏈表類linked_Llist，具體如下： struct node int d; struct node *next; ; class linked_LList /線性鏈表類 private: /數(shù)據(jù)成員 struct node *head; /鏈表頭指針 publi

26、c: /成員函數(shù) linked_LList(); /構(gòu)造函數(shù),建立空鏈表 void prt_linked_LList(); /掃描輸出鏈表中元素/在包含元素x的結(jié)點(diǎn)前插入新元素b void ins_linked_LList(int, int); int del_linked_LList(int); /刪除包含元素x的結(jié)點(diǎn);1. 線性鏈表的插入n線性鏈表的插入：在鏈?zhǔn)酱鎯Y(jié)構(gòu)下的線性表中插入一個新元素。n首先要給該元素分配一個新結(jié)點(diǎn)，以便用于存儲該元素的值；n然后將存放新元素值的結(jié)點(diǎn)鏈接到線性鏈表中指定的位置。n此外，在插入時，對于空表或者在第一個結(jié)點(diǎn)之前插入必須單獨(dú)考慮。 線性線性鏈表的插入運(yùn)

27、算鏈表的插入運(yùn)算插入（三種情況）第一種情況：在第一個結(jié)點(diǎn)前插入第一種情況：在第一個結(jié)點(diǎn)前插入 p -next-next = head ; head = p;（插入前）（插入前） （插入后）（插入后）xheadppxhead第二種情況：在鏈表中間插入第二種情況：在鏈表中間插入 p -next-next = q-next-next; q-next-next = p；x ( (插入前插入前) () (插入后插入后) )pxqpq第三種情況：在鏈表末尾第三種情況：在鏈表末尾插入插入p-next = q- next;/p-next = null;q-next-next = p；p ( (插入前插入前)

28、() (插入后插入后) )p qqtemplate void linked_LList:ins_linked_LList(T x, T b) /在包含元素x的結(jié)點(diǎn)前插入新元素b node *p, *q; p=new node; /申請一個新結(jié)點(diǎn) p-d=b; /置新結(jié)點(diǎn)的數(shù)據(jù)域 if (head=NULL) /原鏈表為空 head=p; p-next=NULL; return; if (head-d=x) /在第一個結(jié)點(diǎn)前插入 p-next=head; head=p; return; q=head; while (q-next!=NULL)&(q-next)-d)!=x) q=q-next;

29、/尋找包含元素x的前一個結(jié)點(diǎn)q p-next=q-next; q-next=p; /新結(jié)點(diǎn)p插入到結(jié)點(diǎn)q之后 return; 線性鏈表的插入操作，如果線性鏈表的插入操作，如果在空表中插入新結(jié)點(diǎn)或者新在空表中插入新結(jié)點(diǎn)或者新結(jié)點(diǎn)的插入位置在表的第一結(jié)點(diǎn)的插入位置在表的第一結(jié)點(diǎn)之前，則需要單獨(dú)考慮結(jié)點(diǎn)之前，則需要單獨(dú)考慮2. 線性鏈表的刪除n線性鏈表的刪除：在鏈?zhǔn)酱鎯Y(jié)構(gòu)下的線性表中刪除包含指定元素的結(jié)點(diǎn)。n首先要在線性鏈表中找到這個結(jié)點(diǎn)；n然后將要刪除結(jié)點(diǎn)的存儲空間釋放回系統(tǒng)。線性鏈表的刪除運(yùn)算線性鏈表的刪除運(yùn)算刪除前刪除前刪除后刪除后ai-1xai+1qpqai-1ai+1xp = q-nex

30、t-next; q-next = p-next;template int linked_LList:del_linked_LList(T x) /刪除包含元素x的結(jié)點(diǎn)元素 node *p, *q; if (head=NULL) return(0); /鏈表為空，無刪除的元素 if (head-d)=x) /刪除第一個結(jié)點(diǎn) p=head-next; delete head; head=p; return(1); q=head; while (q-next!=NULL)&(q-next)-d)!=x) q=q-next; /尋找包含元素x的前一個結(jié)點(diǎn)q if (q-next=NULL) retur

31、n(0); /鏈表中無刪除的元素 p=q-next; q-next=p-next; /刪除q的下一個結(jié)點(diǎn)p delete p; /釋放結(jié)點(diǎn)p的存儲空間 return(1); 分析n插入與刪除算法需要考慮的兩種特殊情況：1.在插入時，對于空表或者在第一個結(jié)點(diǎn)之前插入必須單獨(dú)考慮；2.在刪除時，對于空表及刪除第一個結(jié)點(diǎn)必須單獨(dú)考慮，并且還要考慮到鏈表中不存在被刪除元素的情況。n例題：在測控領(lǐng)域，控制設(shè)備硬件資源相對有限（運(yùn)算能力、內(nèi)存、通信能力等），而這些設(shè)備通常需要具備參數(shù)檢查、數(shù)據(jù)處理、控制、通信等多種功能，因此在控制軟件設(shè)計(jì)中需要考慮有限內(nèi)存資源的合理使用，才能夠較好地實(shí)現(xiàn)上述功能。具體來講

32、，檢測數(shù)據(jù)、控制指令、發(fā)送數(shù)據(jù)、接收數(shù)據(jù)等數(shù)據(jù)的存儲結(jié)構(gòu)必須合理設(shè)計(jì)，才能夠有效利用內(nèi)存資源。結(jié)合應(yīng)用需求，思考如下問題：n采用何種結(jié)構(gòu)來實(shí)現(xiàn)上述數(shù)據(jù)的存儲？n如何構(gòu)建該種數(shù)據(jù)結(jié)構(gòu)？鏈表在測控領(lǐng)域應(yīng)用2.3.3 循環(huán)鏈表n對于線性單鏈表，其插入與刪除操作雖然比較方便，但還存在一個問題：對于空表與對第一個結(jié)點(diǎn)的處理必須單獨(dú)考慮，使得空表與非空表的運(yùn)算不統(tǒng)一。n解決方法：循環(huán)鏈表（Circular Linked List）。循環(huán)鏈表的兩個特點(diǎn)1.在循環(huán)鏈表中增加了一表頭結(jié)點(diǎn)，其數(shù)據(jù)域?yàn)槿我饣蛘吒鶕?jù)需要來設(shè)置，指針域指向線性表的第一個元素的結(jié)點(diǎn)。循環(huán)鏈表的表頭指針HEAD指向表頭結(jié)點(diǎn)。2.循環(huán)鏈表中

33、最后一個結(jié)點(diǎn)的指針域不是空，而是指向表頭結(jié)點(diǎn)。即在循環(huán)鏈表中，所有結(jié)點(diǎn)的指針構(gòu)造了一個環(huán)狀鏈。循環(huán)鏈表的邏輯狀態(tài)循環(huán)鏈表的邏輯狀態(tài)循環(huán)鏈表與線性單鏈表的比較判斷判斷線性單鏈表線性單鏈表為空的條件：為空的條件：判斷判斷循環(huán)鏈表循環(huán)鏈表為空的條件：為空的條件：head=NULLhead-next=heada1a2an-1an.HEADa1a2an-1an.HEADHEAD循環(huán)鏈表循環(huán)鏈表表頭結(jié)點(diǎn)表頭結(jié)點(diǎn)首元結(jié)點(diǎn)首元結(jié)點(diǎn)線性單鏈表線性單鏈表循環(huán)鏈表的特點(diǎn)1.在循環(huán)鏈表中，只要指出表中任何一個結(jié)點(diǎn)的位置，就可以從它出發(fā)訪問到表中其它所有的結(jié)點(diǎn)。而線性單鏈表做不到這一點(diǎn)。2.由于在循環(huán)鏈表中設(shè)置了一個表

34、頭結(jié)點(diǎn)，因此，在任何情況下，循環(huán)鏈表中至少有一個結(jié)點(diǎn)存在，從而使空表與非空表的運(yùn)算統(tǒng)一。3.釋放整個循環(huán)鏈表要比線性單鏈表方便的多。n對于線性單鏈表，為了釋放全表，需要從第一個結(jié)點(diǎn)開始，順鏈找到最后一個結(jié)點(diǎn)；0Headn從HEAD開始，逐個節(jié)點(diǎn)釋放，直到又回到HEAD處，最后釋放HEAD即可。(b) 釋放循環(huán)鏈表釋放循環(huán)鏈表a1a2an-1an.HEAD順序表與鏈表的比較順序表與鏈表的比較基于空間的比較基于空間的比較n存儲分配的方式存儲分配的方式u順序表的存儲空間是靜態(tài)分配的順序表的存儲空間是靜態(tài)分配的u鏈表的存儲空間是動態(tài)分配的鏈表的存儲空間是動態(tài)分配的n存儲密度存儲密度 = = 結(jié)點(diǎn)數(shù)據(jù)本

35、身所占的存儲量結(jié)點(diǎn)數(shù)據(jù)本身所占的存儲量/ /結(jié)點(diǎn)結(jié)點(diǎn)結(jié)構(gòu)所占的存儲總量結(jié)構(gòu)所占的存儲總量u順序表的存儲密度順序表的存儲密度 = 1= 1u鏈表的存儲密度鏈表的存儲密度 1 0，則，則有且僅有一個特定的稱之為根有且僅有一個特定的稱之為根(Root)的結(jié)點(diǎn)，它的結(jié)點(diǎn)，它只有直接后繼，但沒有直接前驅(qū)；只有直接后繼，但沒有直接前驅(qū)；當(dāng)當(dāng)n 1，除根以外的其它結(jié)點(diǎn)劃分為，除根以外的其它結(jié)點(diǎn)劃分為 m (m 0) 個互不相交的有限集個互不相交的有限集 T1, T2 , Tm，其中，其中每個集合本身又是一棵樹，并且稱為根的子樹每個集合本身又是一棵樹，并且稱為根的子樹(SubTree)2.5.1.1 樹與二叉

36、樹的定義ACGBDEFKLHMIJ例如例如A只有根結(jié)點(diǎn)的樹只有根結(jié)點(diǎn)的樹有有13個結(jié)點(diǎn)的樹個結(jié)點(diǎn)的樹其中：其中：A是根；其余結(jié)點(diǎn)分成三個互不相交的子集，是根；其余結(jié)點(diǎn)分成三個互不相交的子集，T1=B,E,F,K,L； T2=C,G； T3=D,H,I,J,M,T1,T2,T3都是根都是根A的子樹，且本身也是一棵樹的子樹，且本身也是一棵樹樹的基本術(shù)語樹的基本術(shù)語1層2層4層3層height= 4ACGBDEFKLHMIJ見教材P.872.5.1.1 樹與二叉樹的定義二叉樹二叉樹 (Binary Tree)定義定義五種形態(tài)五種形態(tài)一棵二叉樹是結(jié)點(diǎn)的一個有限集合，該集一棵二叉樹是結(jié)點(diǎn)的一個有限集合，

37、該集合或者為空，或者是由一個根結(jié)點(diǎn)加上兩棵分合或者為空，或者是由一個根結(jié)點(diǎn)加上兩棵分別稱為左子樹和右子樹的、互不相交的二叉樹別稱為左子樹和右子樹的、互不相交的二叉樹組成。組成。LLRR特點(diǎn)特點(diǎn)每個結(jié)點(diǎn)至多只有兩棵子樹（二叉樹中每個結(jié)點(diǎn)至多只有兩棵子樹（二叉樹中不存在度大于不存在度大于2的結(jié)點(diǎn)）的結(jié)點(diǎn)）二叉樹是有序樹二叉樹是有序樹二叉樹舉例二叉樹例兩種特殊形態(tài)的二叉樹兩種特殊形態(tài)的二叉樹定義定義1 滿二叉樹滿二叉樹 (Full Binary Tree) 一棵深度為一棵深度為k且有且有2 k-1個結(jié)點(diǎn)的二叉樹稱為個結(jié)點(diǎn)的二叉樹稱為滿二叉樹。滿二叉樹。621754389 10 1113141512滿

38、二叉樹滿二叉樹2154367216543非完全二叉樹非完全二叉樹定義定義2 完全二叉樹完全二叉樹 (Complete Binary Tree) 若設(shè)二叉樹的高度為若設(shè)二叉樹的高度為h，則共有，則共有h層。除第層。除第 h 層外，其它各層層外，其它各層 (1 h- -1) 的結(jié)點(diǎn)數(shù)都達(dá)到最大的結(jié)點(diǎn)數(shù)都達(dá)到最大個數(shù)，第個數(shù)，第 h 層層從右向左從右向左連續(xù)缺若干結(jié)點(diǎn)，這就是連續(xù)缺若干結(jié)點(diǎn)，這就是完全二叉樹。完全二叉樹。621754389 1011 12完全二叉樹完全二叉樹2.5.1.2二叉樹性質(zhì)二叉樹性質(zhì)性質(zhì)性質(zhì)1 在二叉樹的第在二叉樹的第 i 層上至多有層上至多有 2i 1個結(jié)點(diǎn)。個結(jié)點(diǎn)。(i

39、1) 證明用歸納法證明用歸納法證明：當(dāng)證明：當(dāng)i=1時，只有根結(jié)點(diǎn)，時，只有根結(jié)點(diǎn)，2 i-1=2 0=1。假設(shè)對所有假設(shè)對所有j，ij 1，命題成立，即第，命題成立，即第j層上至多有層上至多有2 j-1 個結(jié)點(diǎn)。個結(jié)點(diǎn)。由歸納假設(shè)第由歸納假設(shè)第i-1 層上至多有層上至多有 2i 2個結(jié)點(diǎn)。個結(jié)點(diǎn)。由于二叉樹的每個結(jié)點(diǎn)的度至多為由于二叉樹的每個結(jié)點(diǎn)的度至多為2，故在第，故在第i層上的最大結(jié)點(diǎn)數(shù)為第層上的最大結(jié)點(diǎn)數(shù)為第i-1層層上的最大結(jié)點(diǎn)數(shù)的上的最大結(jié)點(diǎn)數(shù)的2倍，即倍，即2* 2i 2= 2 i-1。性質(zhì)性質(zhì)2 深度為深度為 k 的二叉樹至多有的二叉樹至多有 2 k- -1個結(jié)點(diǎn)個結(jié)點(diǎn)(k 1

40、)。證明：由性質(zhì)證明：由性質(zhì)1可見，深度為可見，深度為k的二叉樹的最大結(jié)點(diǎn)數(shù)為的二叉樹的最大結(jié)點(diǎn)數(shù)為 kii11220 + 21 + + 2 k-1 = 2 k- -1kii1層上的最大結(jié)點(diǎn)數(shù)）第(2.5.1.2二叉樹性質(zhì)二叉樹性質(zhì)性質(zhì)性質(zhì)3 對任何一棵二叉樹對任何一棵二叉樹T, 如果其葉結(jié)點(diǎn)數(shù)為如果其葉結(jié)點(diǎn)數(shù)為 n0, 度為度為2的結(jié)點(diǎn)數(shù)為的結(jié)點(diǎn)數(shù)為 n2,則則n0n21.證明：設(shè)二叉樹含有證明：設(shè)二叉樹含有n1個度為個度為1的結(jié)點(diǎn)，則二叉樹結(jié)點(diǎn)的結(jié)點(diǎn)，則二叉樹結(jié)點(diǎn)總數(shù)顯然為：總數(shù)顯然為：n0 + n1 + n2（1）再看看樹的分支數(shù)，再看看樹的分支數(shù)，n2個度為個度為2的結(jié)點(diǎn)必然有的結(jié)點(diǎn)必

41、然有2n2個分個分支，支，n1個度為個度為1的結(jié)點(diǎn)必然有的結(jié)點(diǎn)必然有n1個分支。又因?yàn)槌Y(jié)個分支。又因?yàn)槌Y(jié)點(diǎn)外，其余每個結(jié)點(diǎn)都有一個分支進(jìn)入。因此二叉樹點(diǎn)外，其余每個結(jié)點(diǎn)都有一個分支進(jìn)入。因此二叉樹的分支數(shù)加的分支數(shù)加1就是結(jié)點(diǎn)總數(shù)。即結(jié)點(diǎn)總數(shù)為：就是結(jié)點(diǎn)總數(shù)。即結(jié)點(diǎn)總數(shù)為：1 + n1 + 2n2（2）由（由（1）（）（2）兩式可知：）兩式可知：n0=n2+1 性質(zhì)性質(zhì)4 具有具有 n (n 0) 個結(jié)點(diǎn)的完全二叉?zhèn)€結(jié)點(diǎn)的完全二叉樹的深度為樹的深度為 log2(n) 1證明：證明：設(shè)完全二叉樹的深度為設(shè)完全二叉樹的深度為 h，則根據(jù)性，則根據(jù)性質(zhì)質(zhì)2和完全二叉樹的定義有和完全二叉樹的定

42、義有2h1 - - 1 n 2h- - 1或或 2h1 n 2h取對數(shù)取對數(shù) h1 log2n - leftChild ); destroy ( current - rightChild ); delete current; 基本算法基本算法BinTreeNode *Parent ( BinTreeNode * start, BinTreeNode * current ) /找當(dāng)前結(jié)點(diǎn)的雙親結(jié)點(diǎn)，并返回找當(dāng)前結(jié)點(diǎn)的雙親結(jié)點(diǎn)，并返回 if ( start = NULL ) return NULL; if ( start-leftChild = current | start-rightChild

43、 = current ) return start; /找到找到 BinTreeNode *p; /否則否則 if ( p = Parent ( start-leftChild, current )!= NULL ) return p; /在左子樹中找在左子樹中找 else return Parent(start-rightChild, current); /在右子樹中找在右子樹中找void Traverse ( BinTreeNode *current) /搜索并輸出根為搜索并輸出根為current的二叉樹的二叉樹 if ( current != NULL ) cout -data -lef

44、tChild); Traverse ( current-rightChild); 2.5.2.2二叉樹遍歷二叉樹遍歷樹的遍歷就是按某種次序訪問樹中的結(jié)點(diǎn)，要求每樹的遍歷就是按某種次序訪問樹中的結(jié)點(diǎn)，要求每個結(jié)點(diǎn)訪問一次且僅訪問一次。個結(jié)點(diǎn)訪問一次且僅訪問一次。設(shè)訪問根結(jié)點(diǎn)記作設(shè)訪問根結(jié)點(diǎn)記作 V 遍歷根的左子樹記作遍歷根的左子樹記作 L 遍歷根的右子樹記作遍歷根的右子樹記作 R則可能的遍歷次序有：則可能的遍歷次序有： 前序前序 VLR 中序中序 LVR 后序后序 LRV VLR中序遍歷中序遍歷中序遍歷二叉樹算法的定義：中序遍歷二叉樹算法的定義：若二叉樹為空，則空操作；若二叉樹為空，則空操作；否

45、則否則中序遍歷左子樹中序遍歷左子樹 (L)；訪問根結(jié)點(diǎn)訪問根結(jié)點(diǎn) (V)；中序遍歷右子樹中序遍歷右子樹 (R)。遍歷結(jié)果遍歷結(jié)果 a + b * c - - d - - e / f中序遍歷二叉樹的遞歸算法中序遍歷二叉樹的遞歸算法void InOrder ( BinTreeNode *T ) if ( T != NULL ) InOrder ( T-leftChild ); cout -data; InOrder ( T-rightChild ); 前序遍歷二叉樹算法的定義：前序遍歷二叉樹算法的定義：若二叉樹為空，則空操作；若二叉樹為空，則空操作；否則否則訪問根結(jié)點(diǎn)訪問根結(jié)點(diǎn) (V)；前序遍歷左子樹前序遍歷左子樹 (L)；前序遍歷右子樹前序遍歷右子樹 (R)。遍歷結(jié)果遍歷結(jié)果 - - + a * b - - c d / e f前序遍歷前序遍歷 (Preorder Traversal)前序遍歷二叉樹的遞歸算法前序遍歷二叉樹的遞歸算法void PreOrder ( BinTreeNode *T ) if ( T != NULL ) cout -data; PreOrder ( T-leftChild ); PreOrder ( T-rightChild ); 后序遍歷二叉樹算法的