第二部分 基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算(上)

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 線性表及順序存儲(chǔ)結(jié)構(gòu)n2.3 線性鏈表及運(yùn)算n2.4 數(shù)組n2.5 樹與二叉樹n2.6 圖n2.7 作業(yè)題目2.1數(shù)據(jù)結(jié)構(gòu)的基本概念n2.1.1 兩個(gè)例子n有序表與無序表分析n從兩個(gè)表中可以看出來數(shù)據(jù)元素在表中順序?qū)Σ檎倚视泻艽笥绊?.1.1 兩個(gè)例子n2.1.1 學(xué)生登記表 假設(shè)查找假設(shè)查找90的同學(xué)時(shí)，就必須遍歷整個(gè)數(shù)據(jù)表格。這樣效率很低。的同學(xué)時(shí)，就必須遍歷整個(gè)數(shù)據(jù)表格。這樣效率很低。2.1數(shù)據(jù)結(jié)構(gòu)的基本概念2

2、.1.2 什么是數(shù)據(jù)結(jié)構(gòu)n簡單地講，數(shù)據(jù)結(jié)構(gòu)是指相互關(guān)聯(lián)的數(shù)據(jù)元素的集數(shù)據(jù)結(jié)構(gòu)是指相互關(guān)聯(lián)的數(shù)據(jù)元素的集合合。例如：圖書館的卡片目錄就是一個(gè)復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，高等院校的學(xué)生號(hào)也是一個(gè)復(fù)雜的數(shù)據(jù)結(jié)構(gòu)n數(shù)據(jù)元素具有廣泛的意義，一般來講現(xiàn)實(shí)世界中客觀存在的一切個(gè)體都可以是數(shù)據(jù)元素。例如：季節(jié)：春夏秋冬，家庭成員：父親，兒子，女兒。n總之，在數(shù)據(jù)處理領(lǐng)域每一個(gè)需要處理的對(duì)象都可以抽象為一個(gè)數(shù)據(jù)元素，簡稱元素、結(jié)點(diǎn)、記錄元素、結(jié)點(diǎn)、記錄。n有時(shí)一個(gè)有時(shí)一個(gè)數(shù)據(jù)元素?cái)?shù)據(jù)元素可以由若干可以由若干數(shù)據(jù)項(xiàng)數(shù)據(jù)項(xiàng)(Data Item)組成。組成。數(shù)據(jù)項(xiàng)數(shù)據(jù)項(xiàng)是具有獨(dú)立含義的是具有獨(dú)立含義的最小標(biāo)識(shí)單最小標(biāo)識(shí)單位位。

3、2.1.2 什么是數(shù)據(jù)結(jié)構(gòu)姓姓名名俱樂俱樂部名部名稱稱出生日期出生日期年年 月月 日日 入隊(duì)入隊(duì)日期日期職職位位業(yè)業(yè)績績2.1.2 什么是數(shù)據(jù)結(jié)構(gòu)n1、數(shù)據(jù)的邏輯結(jié)構(gòu)：n數(shù)據(jù)結(jié)構(gòu)是指帶有結(jié)構(gòu)的數(shù)據(jù)元素的組合。其實(shí)所謂結(jié)構(gòu)就是指數(shù)據(jù)元素之間的前后件關(guān)系。因此一個(gè)數(shù)據(jù)結(jié)構(gòu)應(yīng)該包含有兩個(gè)方面的知識(shí)：n1、數(shù)據(jù)元素信息n2、各數(shù)據(jù)元素之間的前后件關(guān)系。n反映數(shù)據(jù)元素之間前后件的邏輯關(guān)系，就是數(shù)據(jù)的邏輯結(jié)構(gòu)。2.1.2 什么是數(shù)據(jù)結(jié)構(gòu)n形式定義：形式定義：某一數(shù)據(jù)對(duì)象的所有數(shù)據(jù)成員之間的關(guān)系。記某一數(shù)據(jù)對(duì)象的所有數(shù)據(jù)成員之間的關(guān)系。記為：為： B B = (D, R) = (D, R) 其中，其中，D

4、D 是某數(shù)據(jù)元素的集合，是某數(shù)據(jù)元素的集合， R R 是各數(shù)據(jù)是各數(shù)據(jù)元素間的前后件關(guān)系。元素間的前后件關(guān)系。n例如：家庭關(guān)系數(shù)據(jù)結(jié)構(gòu)可以表示成：例如：家庭關(guān)系數(shù)據(jù)結(jié)構(gòu)可以表示成：n B B = (D, R) = (D, R)n D =D =春，夏，秋，冬春，夏，秋，冬 n R =( R =(春春, ,夏夏),),（夏（夏, ,秋）秋）, ,（秋（秋, ,冬冬 ） 2.1.2 什么是數(shù)據(jù)結(jié)構(gòu)n2、數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)：、數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)：n數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)空間中數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)空間中的存放形式稱為數(shù)據(jù)的儲(chǔ)存結(jié)構(gòu)。的存放形式稱為數(shù)據(jù)的儲(chǔ)存結(jié)構(gòu)。n數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)依賴于計(jì)算機(jī)語言。數(shù)據(jù)的

5、存儲(chǔ)結(jié)構(gòu)依賴于計(jì)算機(jī)語言。 順序存儲(chǔ)表示順序存儲(chǔ)表示 鏈接存儲(chǔ)表示鏈接存儲(chǔ)表示 索引存儲(chǔ)表示索引存儲(chǔ)表示 散列存儲(chǔ)表示散列存儲(chǔ)表示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)特例線性表的兩個(gè)條件：線性表的兩個(gè)條件：1、有且只有一個(gè)根節(jié)點(diǎn)、有且只有一個(gè)根節(jié)點(diǎn)2、每個(gè)節(jié)點(diǎn)最多有一個(gè)前、每個(gè)節(jié)點(diǎn)最多有一個(gè)前件，也最多只有一個(gè)后件。件，也最多只有一個(gè)后件。沒有前件的結(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.2 線性表及其順序存儲(chǔ)結(jié)構(gòu)n2.2.1 線性表及

6、其運(yùn)算n 1、什么是線性表n 2、線性表的順序存儲(chǔ)結(jié)構(gòu)n 3、線性表在順序存儲(chǔ)下的插入運(yùn)算n 4、線性表在順序存儲(chǔ)下的刪除運(yùn)算n 5、順序表類n2.2.2 棧及其應(yīng)用n2.2.3 隊(duì)列及其應(yīng)用2.2.1.1 什么是線性表定義：定義： n n（ 0 0）個(gè)數(shù)據(jù)元素的有限序列，記作個(gè)數(shù)據(jù)元素的有限序列，記作（a1, ai-1, ai, ai+1, an） 其中其中,ai 是表中數(shù)據(jù)元素，是表中數(shù)據(jù)元素，n 是表長度。是表長度。特點(diǎn)特點(diǎn): n同一線性表中元素具有相同特性。同一線性表中元素具有相同特性。n相鄰數(shù)據(jù)元素之間存在序偶關(guān)系。相鄰數(shù)據(jù)元素之間存在序偶關(guān)系。n除根結(jié)點(diǎn)和終端結(jié)點(diǎn)外，其他每一個(gè)元素

7、有一除根結(jié)點(diǎn)和終端結(jié)點(diǎn)外，其他每一個(gè)元素有一個(gè)且僅有一個(gè)前件也有且僅有一個(gè)后件。個(gè)且僅有一個(gè)前件也有且僅有一個(gè)后件。N=0N=0，為空表。，為空表。2.2.1.1 什么是線性表n線性表的順序存儲(chǔ)結(jié)構(gòu)具有以下兩個(gè)基本特點(diǎn)：n1、線性表中元素所占的存儲(chǔ)空間是連續(xù)的。n2、表中各元素在存儲(chǔ)空間中按邏輯順序存放的。n地址關(guān)系滿足：nADD(ai)=ADR(a1)+(i-1)k2.2.1.2 線性表的順序存儲(chǔ)結(jié)構(gòu)2.2.1.2 線性表的順序存儲(chǔ)結(jié)構(gòu)線性表的初始化templatevoid init_sq_LList(T * v,int m, int * n)v = new Tm;*n = 0;return

8、 ;2.2.1.3 線性表順序存儲(chǔ)下插入運(yùn)算n例：在下面圖中的第2個(gè)元素插入87，然后在第9個(gè)元素之前插入14。2.2.1.3 線性表順序存儲(chǔ)下插入運(yùn)算n假設(shè)線性表的存儲(chǔ)空間為V1:m,表長度為n,插入位置為i,插入元素是b,則插入的過程如下：n1)判斷異常情況：n a)存儲(chǔ)空間已滿(n=m)時(shí)，上溢算法結(jié)束。n b)in，最后元素后插入n c)i1，第1個(gè)元素前插入n2)然后從最后元素到第i個(gè)元素往后移動(dòng)1個(gè)位置n3)將新元素插入到第i位置，表長度加1.2.2.1.3 線性表順序存儲(chǔ)下插入運(yùn)算templatevoid ins_sq_LList(T * v,int m,int *n,int i

9、,T 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 線性表順序存儲(chǔ)下刪除運(yùn)算n例題：在下面圖中，現(xiàn)在要求刪除第一個(gè)元素29，然后刪除第6個(gè)元素。2.2.1.4 線性表順序存儲(chǔ)下刪除運(yùn)算n假設(shè)線性表的存儲(chǔ)空間為V1:m，線性表長度為n(nn,或者1，則在線性表的兩端進(jìn)行刪除n2）從第i+1元素開始到最后一個(gè)元素，均前移一個(gè)位置n3）最后將線性表的長度減少1。2.2.1.4 線性表順序存儲(chǔ)下刪除運(yùn)算templatevoid del_sq_LLis

10、t(T * 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;作業(yè)內(nèi)容1設(shè)計(jì)一個(gè)靜態(tài)數(shù)組存儲(chǔ)結(jié)構(gòu)的順序表類，要求編程實(shí)現(xiàn)如下任務(wù)：1）建立一個(gè)線性表，首先依次輸人整數(shù)數(shù)據(jù)元素（個(gè)數(shù)根據(jù)自己的需要鍵盤給定）2）刪除指定位置的數(shù)據(jù)元素（指定元素位置通過鍵盤輸入）再依次顯示刪除后的線性表中的數(shù)據(jù)元素。3）查找指定數(shù)據(jù)的數(shù)據(jù)元素（指

11、定數(shù)據(jù)的大小通過鍵盤輸入），若找到則顯示位置，若沒有找到就顯示0。要求：采用順序表實(shí)現(xiàn)，假設(shè)該順序表的數(shù)據(jù)元素個(gè)數(shù)在最壞情況下不會(huì)超過50個(gè)。2.2.2 棧n什么是棧2.3 棧n定義定義:是限定僅在表尾進(jìn)行插入或刪除操作的是限定僅在表尾進(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è)棧用順序

12、存儲(chǔ)空間S(1:m)中，S(bottom)表示棧底元素，S(top)表示棧頂元素。Top=0，表示?？?，top=m表示棧滿。n/棧的初始化程序templatevoid init_stack(T *s ,int m, int *top)s = new Tm;*top =0;return;入棧n入棧需要注意?？臻g是否已溢出。templatevoid push(T *s ,int m, int *top, T x)if(*top = m)coutoverflowendl;return;*top = *top + 1;s*top - 1 = x;return;出棧n要注意棧是否空，為空說明出棧無效te

13、mplateT pop(T *s , int *top)T value;if(*top = 0)coutunderflowendl;eixt(0);value = s*top - 1;*top = *top - 1;return value;讀棧頂元素templateT top(T *s , int *top)T value;if(*top = 0)coutunderflowendl;eixt(0);value = s*top - 1;return value;2.2.3 隊(duì)列n定義定義:只允許在表的一端進(jìn)行插入，而在另一只允許在表的一端進(jìn)行插入，而在另一端刪除元素的線性表。端刪除元素的線性表

14、。n在隊(duì)列中，允許插入的一端叫隊(duì)尾（在隊(duì)列中，允許插入的一端叫隊(duì)尾（rear）n允許刪除的一端稱為對(duì)頭允許刪除的一端稱為對(duì)頭(front)。n特點(diǎn)：先進(jìn)先出特點(diǎn)：先進(jìn)先出 (FIFO) a1 ，a2， a3，an出隊(duì)列出隊(duì)列入隊(duì)列入隊(duì)列隊(duì)隊(duì)頭頭隊(duì)隊(duì)尾尾2.2.3 隊(duì)列隊(duì)列示意圖 2.2.3 隊(duì)列(a)線性隊(duì)列線性隊(duì)列 3 2 1 0 (a)rear=front= -1(隊(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ì)隊(duì)空時(shí)，隊(duì)空時(shí)， 令令rear=front=

15、 -1，當(dāng)有當(dāng)有新元素入隊(duì)時(shí)，尾指針加新元素入隊(duì)時(shí)，尾指針加1，當(dāng)有元，當(dāng)有元素出隊(duì)時(shí)，頭指針加素出隊(duì)時(shí)，頭指針加1。故在非空隊(duì)。故在非空隊(duì)列中，列中，頭指針頭指針始終指向始終指向隊(duì)頭元素前一隊(duì)頭元素前一個(gè)位置個(gè)位置，而，而尾指針尾指針始終指向始終指向隊(duì)尾元素隊(duì)尾元素的位置的位置 MAX=4假設(shè)假設(shè)MAX=4，當(dāng)隊(duì)列處于圖（，當(dāng)隊(duì)列處于圖（c）狀態(tài)，）狀態(tài)，rear+1=4時(shí)隊(duì)滿，時(shí)隊(duì)滿，此時(shí)不能插入新元素，但實(shí)際上隊(duì)列可用空間沒有滿，這是此時(shí)不能插入新元素，但實(shí)際上隊(duì)列可用空間沒有滿，這是一種假溢出現(xiàn)象。解決方法：將隊(duì)列頭尾相連形成一個(gè)環(huán)。一種假溢出現(xiàn)象。解決方法：將隊(duì)列頭尾相連形成一個(gè)環(huán)。

16、n線性隊(duì)列隊(duì)滿的條件：線性隊(duì)列隊(duì)滿的條件： rear + 1 = MAXn線性隊(duì)列隊(duì)空的條件：線性隊(duì)列隊(duì)空的條件： rear = front 3 2 1 0 (a)rear=front= -1(隊(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 0 1 2 3(3) 隊(duì)空隊(duì)空區(qū)別隊(duì)空與隊(duì)滿的方法：如果區(qū)別隊(duì)空與隊(duì)滿的方法：如果隊(duì)尾加隊(duì)尾加1后等于隊(duì)頭指針即為隊(duì)后等于隊(duì)頭指針即為隊(duì)滿，即少用一個(gè)元素空間。

17、滿，即少用一個(gè)元素空間。將頭尾連接成一將頭尾連接成一個(gè)環(huán)，形成循環(huán)個(gè)環(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=fronte2(rear+1)%MAX=front另外一種辦法就是加一個(gè)判斷另外一種辦法就是加一個(gè)判斷是否為空標(biāo)志位是否為空標(biāo)志位s來進(jìn)行區(qū)分。來進(jìn)行區(qū)分。2.2.3 隊(duì)列n隊(duì)列運(yùn)算n（1）設(shè)置一個(gè)空隊(duì)列；n（2）插入一個(gè)新的隊(duì)尾元素

18、，稱為進(jìn)隊(duì)；n（3）刪除隊(duì)頭元素，稱為出隊(duì)；n（4）讀取隊(duì)頭元素；隊(duì)列的初始化n假設(shè)隊(duì)列為q，front為隊(duì)頭，rear為隊(duì)尾，m為隊(duì)列容量，s表示隊(duì)列是否為空，為1表示非空。templatevoid init_Queue(T *q,int m,int *front,int *rear,int *s)q = new Tm;*front = *rear =m;*s= 0;入隊(duì)操作templatevoid addcq(T *q,int m,int *front,int *rear,int *s,T x)if(*s = 1) &(*rear = *front)coutoverflowendl

19、;return;*rear += 1;if(*rear = m+1) *rear = 1;q*rear - 1 =x;*s = 1;return ;出隊(duì)列tempalteT delcq(T *q,int m,int *rear,int *front,int *s)T y;if(*s = 0)coutunderflowendl;exit(0);*front = (*front+1)%m;y = q*front -1;if(*front = *rear)*s = 0;return;題目n 定義數(shù)據(jù)元素的數(shù)據(jù)類型為如下形式的結(jié)構(gòu)體：ntypedef structn char taskname10;/

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

21、線性表結(jié)構(gòu)。2.3.1 線性鏈表的基本概念n鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)：n每個(gè)節(jié)點(diǎn)有兩部分組成：一個(gè)部分用存儲(chǔ)數(shù)據(jù)元素，稱為數(shù)據(jù)域；另外一部分存放指針，叫為指針域。n鏈?zhǔn)酱鎯?chǔ)中元素之間的前后件關(guān)系可以通過指針來標(biāo)識(shí)。n鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)既可以用于順序存儲(chǔ)，也可以用于較復(fù)雜的非線性存儲(chǔ)。2.3.1 線性鏈表的基本概念n1 線性鏈表鏈?zhǔn)降拇鎯?chǔ)結(jié)構(gòu)線性鏈表的邏輯結(jié)構(gòu)2.3.1 線性鏈表的基本概念線性鏈表例2.3.1 線性鏈表的基本概念template /T為虛擬類型為虛擬類型struct node T d; node *next;template /模板聲明模板聲明,數(shù)據(jù)元素虛擬類型為數(shù)據(jù)元素虛擬類型為Tclass l

22、inked_List /線性鏈表類線性鏈表類 private: /數(shù)據(jù)成員數(shù)據(jù)成員node *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)前插入新元素bT del_linked_List(）; /刪除鏈頭結(jié)點(diǎn)刪除鏈頭結(jié)點(diǎn);2.3.1 線性鏈表的基本概念template /模板聲明模板聲

23、明,數(shù)據(jù)元素虛擬類型為數(shù)據(jù)元素虛擬類型為Tint linked_List : linked_List ()head = null;template linked_List : flag_linked_list()if(head = null)return 0;return 1;2.3.1 線性鏈表的基本概念template void linked_List : prt_linked_List()node * p;if(p=null)cout“empty list”endl; return;docoutdnext;while(p!=null);return;2.3.1 線性鏈表的基本概念temp

24、late void linked_List : ins_linked_List(T x) node * p;p = new node;P-d = x;p-next = head;head = p;return;2.3.1 線性鏈表的基本概念template T linked_List : del_linked_List(T x) T y;node * q;if(head = null)cout“empty list”d;head = q-next;delete q;return y;2.3.1 線性鏈表的基本概念n3.帶鏈的棧（代碼略）圖2.23 帶鏈的?？衫脳＜捌溥\(yùn)算2.3.1 線性鏈表的

25、基本概念n4 帶鏈的隊(duì)列（代碼略）帶鏈的隊(duì)列及其運(yùn)算2.3.2 線性鏈表的基本運(yùn)算n1、在指定節(jié)點(diǎn)前插入一個(gè)新元素n2、刪除指定元素n3、將兩個(gè)鏈表合成一個(gè)線性鏈表n4、線性表的分解n5、逆轉(zhuǎn)線性表n6、復(fù)制線性鏈表n7、線性表的排序n8、線性表的查找相關(guān)操作n首先定義一個(gè)線性鏈表類linked_Llist，具體如下：/文件名linked_Llist.h#include using namespace std;template /T為虛擬類型struct node T d; node *next;template /模板聲明,數(shù)據(jù)元素虛擬類型為Tclass linked_LList /線性鏈表

26、類 private: /數(shù)據(jù)成員 node *head; /鏈表頭指針 public: /成員函數(shù) linked_LList(); /構(gòu)造函數(shù),建立空鏈表 void prt_linked_LList(); /掃描輸出鏈表中元素/在包含元素x的結(jié)點(diǎn)前插入新元素b void ins_linked_LList(T, T); int del_linked_LList(T); /刪除包含元素x的結(jié)點(diǎn);1. 線性鏈表的插入n線性鏈表的插入：在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)下的線性表中插入一個(gè)新元素。n首先要給該元素分配一個(gè)新結(jié)點(diǎn)，以便用于存儲(chǔ)該元素的值；n然后將存放新元素值的結(jié)點(diǎn)鏈接到線性鏈表中指定的位置。n此外，在插入時(shí)

27、，對(duì)于空表或者在第一個(gè)結(jié)點(diǎn)之前插入必須單獨(dú)考慮。分析n由于插入的新結(jié)點(diǎn)由系統(tǒng)根據(jù)用戶（程序）需求隨用隨申請(qǐng)，因此，只要系統(tǒng)還有剩余存儲(chǔ)空間，在線性鏈表插入時(shí)總能取到存儲(chǔ)插入元素的新結(jié)點(diǎn)，不會(huì)發(fā)生“上溢”的情況。n由于整個(gè)系統(tǒng)的存儲(chǔ)空間是公用的，多個(gè)線性鏈表可以共享它，從而很方便地實(shí)現(xiàn)了存儲(chǔ)空間的動(dòng)態(tài)分配。n此外，線性鏈表在插入過程中不發(fā)生數(shù)據(jù)元素的移動(dòng)的現(xiàn)象，只需改變有關(guān)結(jié)點(diǎn)的指針即可，從而提高了插入的效率。 線性線性鏈表的插入運(yùn)算鏈表的插入運(yùn)算插入（三種情況）第一種情況：在第一個(gè)結(jié)點(diǎn)前插入第一種情況：在第一個(gè)結(jié)點(diǎn)前插入 p -next-next = head ; head = p;（插入前）

28、（插入前） （插入后）（插入后）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 ( (插入前插入前) () (插入后插入后) )p qqtemplate void linked_LList:ins_linked_LList(T x, T b) /在包含元素x的結(jié)點(diǎn)前插

29、入新元素b node *p, *q; p=new node; /申請(qǐng)一個(gè)新結(jié)點(diǎn) p-d=b; /置新結(jié)點(diǎn)的數(shù)據(jù)域 if (head=NULL) /原鏈表為空 head=p; p-next=NULL; return; if (head-d=x) /在第一個(gè)結(jié)點(diǎn)前插入 p-next=head; head=p; return; q=head; while (q-next!=NULL)&(q-next)-d)!=x) q=q-next; /尋找包含元素x的前一個(gè)結(jié)點(diǎn)q p-next=q-next; q-next=p; /新結(jié)點(diǎn)p插入到結(jié)點(diǎn)q之后 return; 線性鏈表的插入操作，如果線性鏈表

30、的插入操作，如果在空表中插入新結(jié)點(diǎn)或者新在空表中插入新結(jié)點(diǎn)或者新結(jié)點(diǎn)的插入位置在表的第一結(jié)點(diǎn)的插入位置在表的第一結(jié)點(diǎn)之前，則需要單獨(dú)考慮結(jié)點(diǎn)之前，則需要單獨(dú)考慮線性鏈表的插入運(yùn)算線性鏈表的插入運(yùn)算templateVoid linked_List:ins_linked_list(T x,T b)node * p,*q=head;p = new node;p-d =b;if(head =null)head = p;p-next =null;return;if(head-d = x)p-next = head; head = p; return;while(q-next!=null)&(q-

31、next-d!=x)q = q-next;p-next = q-next; q-next = p;return;2. 線性鏈表的刪除n線性鏈表的刪除：在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)下的線性表中刪除包含指定元素的結(jié)點(diǎn)。n首先要在線性鏈表中找到這個(gè)結(jié)點(diǎn)；n然后將要?jiǎng)h除結(jié)點(diǎn)的存儲(chǔ)空間釋放回系統(tǒng)。線性鏈表的刪除運(yùn)算線性鏈表的刪除運(yùn)算刪除前刪除前刪除后刪除后ai-1xai+1qpqai-1ai+1xp = q-next-next; q-next = p-next;template int linked_LList:del_linked_LList(T x) /刪除包含元素x的結(jié)點(diǎn)元素 node *p, *q; if (

32、head=NULL) return(0); /鏈表為空，無刪除的元素 if (head-d)=x) /刪除第一個(gè)結(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的前一個(gè)結(jié)點(diǎn)q if (q-next=NULL) return(0); /鏈表中無刪除的元素 p=q-next; q-next=p-next; /刪除q的下一個(gè)結(jié)點(diǎn)p delete p; /釋放結(jié)點(diǎn)p的存儲(chǔ)空間 return(1); 線性鏈表的刪除運(yùn)算線性鏈

33、表的刪除運(yùn)算templateint linked_List:del_linked_list(T x) node*p,*q;if(head = null) return 0;if(head-d = x)p= head-next;delete head;head = p; return 1; q=head;while(q-next!=null)& (q-next-d!=x)q= q-next;if(q-next = null) return 0;/無元素可以刪除無元素可以刪除p=q-next;q-next =p-next;delete p;return 1;分析n插入與刪除算法需要考慮的兩

34、種特殊情況：1.在插入時(shí)，對(duì)于空表或者在第一個(gè)結(jié)點(diǎn)之前插入必須單獨(dú)考慮；2.在刪除時(shí)，對(duì)于空表及刪除第一個(gè)結(jié)點(diǎn)必須單獨(dú)考慮，并且還要考慮到鏈表中不存在被刪除元素的情況。2.3.3 循環(huán)鏈表n對(duì)于線性單鏈表，其插入與刪除操作雖然比較方便，但還存在一個(gè)問題：對(duì)于空表與對(duì)第一個(gè)結(jié)點(diǎn)的處理必須單獨(dú)考慮，使得空表與非空表的運(yùn)算不統(tǒng)一。n解決方法：循環(huán)鏈表（Circular Linked List）。循環(huán)鏈表的兩個(gè)特點(diǎn)1.在循環(huán)鏈表中增加了一表頭結(jié)點(diǎn)，其數(shù)據(jù)域?yàn)槿我饣蛘吒鶕?jù)需要來設(shè)置，指針域指向線性表的第一個(gè)元素的結(jié)點(diǎn)。循環(huán)鏈表的表頭指針HEAD指向表頭結(jié)點(diǎn)。2.循環(huán)鏈表中最后一個(gè)結(jié)點(diǎn)的指針域不是空，而是

35、指向表頭結(jié)點(diǎn)。即在循環(huán)鏈表中，所有結(jié)點(diǎn)的指針構(gòu)造了一個(gè)環(huán)狀鏈。圖圖2.28 循環(huán)鏈表的邏輯狀態(tài)循環(huán)鏈表的邏輯狀態(tài)（第（第72頁）頁）循環(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)鏈表中，只要指出表中任何一個(gè)結(jié)點(diǎn)的位置，就可以從它出發(fā)訪問到表中其它所有的結(jié)點(diǎn)。而線性單鏈表做不到這一點(diǎn)。2.由于在循環(huán)鏈表中設(shè)置了一個(gè)

36、表頭結(jié)點(diǎn)，因此，在任何情況下，循環(huán)鏈表中至少有一個(gè)結(jié)點(diǎn)存在，從而使空表與非空表的運(yùn)算統(tǒng)一。3.釋放整個(gè)循環(huán)鏈表要比線性單鏈表方便的多。圖示： 線性單鏈表與循環(huán)鏈表的釋放n對(duì)于線性單鏈表，為了釋放全表，需要從第一個(gè)結(jié)點(diǎn)開始，順鏈找到最后一個(gè)結(jié)點(diǎn)；n再修改最后一個(gè)結(jié)點(diǎn)的指針域，使其指向可利用棧的棧頂結(jié)點(diǎn)，并將棧頂指針指向線性單鏈表的第一個(gè)結(jié)點(diǎn)。00TOP(a) 釋放線性單鏈表釋放線性單鏈表n對(duì)于循環(huán)鏈表，只需直接改變表頭結(jié)點(diǎn)的指針域，讓其指向可利用棧的棧頂結(jié)點(diǎn)；n同時(shí)讓棧頂指針指向循環(huán)鏈表的第一個(gè)結(jié)點(diǎn)（表頭結(jié)點(diǎn)后面的結(jié)點(diǎn)）即可。0表頭結(jié)點(diǎn)表頭結(jié)點(diǎn)TOPTOP(b) 釋放循環(huán)鏈表釋放循環(huán)鏈表n循環(huán)鏈

37、表類：/文件名Linked_Clist.h#include using namespace std;template struct node /循環(huán)鏈表結(jié)點(diǎn)類型 T d; node *next;順序表與鏈表的比較順序表與鏈表的比較基于空間的比較基于空間的比較n存儲(chǔ)分配的方式存儲(chǔ)分配的方式u順序表的存儲(chǔ)空間是靜態(tài)分配的順序表的存儲(chǔ)空間是靜態(tài)分配的u鏈表的存儲(chǔ)空間是動(dòng)態(tài)分配的鏈表的存儲(chǔ)空間是動(dòng)態(tài)分配的n存儲(chǔ)密度存儲(chǔ)密度 = = 結(jié)點(diǎn)數(shù)據(jù)本身所占的存儲(chǔ)量結(jié)點(diǎn)數(shù)據(jù)本身所占的存儲(chǔ)量/ /結(jié)點(diǎn)結(jié)點(diǎn)結(jié)構(gòu)所占的存儲(chǔ)總量結(jié)構(gòu)所占的存儲(chǔ)總量u順序表的存儲(chǔ)密度順序表的存儲(chǔ)密度 = 1= 1u鏈表的存儲(chǔ)密度鏈表的存儲(chǔ)

38、密度 1 0，則，則有且僅有一個(gè)特定的稱之為根有且僅有一個(gè)特定的稱之為根(Root)的結(jié)點(diǎn)，它的結(jié)點(diǎn)，它只有直接后繼，但沒有直接前驅(qū)；只有直接后繼，但沒有直接前驅(qū)；當(dāng)當(dāng)n 1，除根以外的其它結(jié)點(diǎn)劃分為，除根以外的其它結(jié)點(diǎn)劃分為 m (m 0) 個(gè)互不相交的有限集個(gè)互不相交的有限集 T1, T2 , Tm，其中，其中每個(gè)集合本身又是一棵樹，并且稱為根的子樹每個(gè)集合本身又是一棵樹，并且稱為根的子樹(SubTree)2.5 樹與二叉樹ACGBDEFKLHMIJ例如例如A只有根結(jié)點(diǎn)的樹只有根結(jié)點(diǎn)的樹有有13個(gè)結(jié)點(diǎn)的樹個(gè)結(jié)點(diǎn)的樹其中：其中：A是根；其余結(jié)點(diǎn)分成三個(gè)互不相交的子集，是根；其余結(jié)點(diǎn)分成三個(gè)互

39、不相交的子集，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二叉樹二叉樹 (Binary Tree)定義定義五種形態(tài)五種形態(tài)一棵二叉樹是結(jié)點(diǎn)的一個(gè)有限集合，一棵二叉樹是結(jié)點(diǎn)的一個(gè)有限集合，該集合或者為空，或者是由一個(gè)根結(jié)點(diǎn)加該集合或者為空，或者是由一個(gè)根結(jié)點(diǎn)加上兩棵分別稱為左子樹和右子樹的、互不上兩棵分別稱為左子樹和右子樹的、互不相交的二叉樹組成。相交的二叉樹組成。LLRR特點(diǎn)特點(diǎn)每個(gè)結(jié)點(diǎn)至多只有兩棵子樹（二叉

40、樹中每個(gè)結(jié)點(diǎn)至多只有兩棵子樹（二叉樹中不存在度大于不存在度大于2的結(jié)點(diǎn)）的結(jié)點(diǎn)）二叉樹舉例二叉樹例二叉樹性質(zhì)二叉樹性質(zhì)性質(zhì)性質(zhì)1 在二叉樹的第在二叉樹的第 i 層上至多有層上至多有 2i 1個(gè)結(jié)點(diǎn)。個(gè)結(jié)點(diǎn)。(i 1) 證明用歸納法證明用歸納法證明：當(dāng)證明：當(dāng)i=1時(shí)，只有根結(jié)點(diǎn)，時(shí)，只有根結(jié)點(diǎn)，2 i-1=2 0=1。假設(shè)對(duì)所有假設(shè)對(duì)所有j，ij 1，命題成立，即第，命題成立，即第j層上至多有層上至多有2 j-1 個(gè)結(jié)點(diǎn)。個(gè)結(jié)點(diǎn)。由歸納假設(shè)第由歸納假設(shè)第i-1 層上至多有層上至多有 2i 2個(gè)結(jié)點(diǎn)。個(gè)結(jié)點(diǎn)。由于二叉樹的每個(gè)結(jié)點(diǎn)的度至多為由于二叉樹的每個(gè)結(jié)點(diǎn)的度至多為2，故在第，故在第i層上的最

41、大結(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個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn)(k 1)。證明：由性質(zhì)證明：由性質(zhì)1可見，深度為可見，深度為k的二叉樹的最大結(jié)點(diǎn)數(shù)為的二叉樹的最大結(jié)點(diǎn)數(shù)為 kii11220 + 21 + + 2 k-1 = 2 k- -1kii1(層上的最大結(jié)點(diǎn)數(shù)）第二叉樹性質(zhì)二叉樹性質(zhì)性質(zhì)性質(zhì)3 對(duì)任何一棵二叉樹對(duì)任何一棵二叉樹T, 如果其葉結(jié)點(diǎn)數(shù)為如果其葉結(jié)點(diǎn)數(shù)為 n0, 度為度為2的結(jié)點(diǎn)數(shù)為的結(jié)點(diǎn)數(shù)為 n2,則則n0n21.證明：若度為證明：若度為

42、1的結(jié)點(diǎn)有的結(jié)點(diǎn)有 n1 個(gè)，總結(jié)點(diǎn)個(gè)數(shù)為個(gè)，總結(jié)點(diǎn)個(gè)數(shù)為 n，總邊數(shù)為，總邊數(shù)為 e，則根據(jù)二，則根據(jù)二叉樹的定義，叉樹的定義， n = n0 + n1 + n2 e = 2n2 + n1 = n - - 1 因此，有因此，有 2n2 + n1 = n0 + n1 + n2 - - 1 n2 = n0 - - 1 n0 = n2 + 1 兩種特殊形態(tài)的二叉樹兩種特殊形態(tài)的二叉樹定義定義1 滿二叉樹滿二叉樹 (Full Binary Tree) 一棵深度為一棵深度為k且有且有2 k-1個(gè)結(jié)點(diǎn)的二叉樹稱為個(gè)結(jié)點(diǎn)的二叉樹稱為滿二叉樹。滿二叉樹。621754389 10 1113141512滿二叉樹

43、滿二叉樹書上的三個(gè)例子2154367216543非完全二叉樹非完全二叉樹定義定義2 完全二叉樹完全二叉樹 (Complete Binary Tree) 若設(shè)二叉樹的高度為若設(shè)二叉樹的高度為h，則共有，則共有h層。除第層。除第 h 層外，其它各層層外，其它各層 (0 h- -1) 的結(jié)點(diǎn)數(shù)都達(dá)到最大的結(jié)點(diǎn)數(shù)都達(dá)到最大個(gè)數(shù)，第個(gè)數(shù)，第 h 層層從右向左從右向左連續(xù)缺若干結(jié)點(diǎn)，這就是連續(xù)缺若干結(jié)點(diǎn)，這就是完全二叉樹。完全二叉樹。621754389 1011 12完全二叉樹完全二叉樹性質(zhì)性質(zhì)4 具有具有 n (n 0) 個(gè)結(jié)點(diǎn)的完全二叉?zhèn)€結(jié)點(diǎn)的完全二叉樹的深度為樹的深度為 log2(n) 1證明：證明

44、：設(shè)完全二叉樹的深度為設(shè)完全二叉樹的深度為 h，則根據(jù)性，則根據(jù)性質(zhì)質(zhì)2和完全二叉樹的定義有和完全二叉樹的定義有2h1 - - 1 n 2h- - 1或或 2h1 n 2h取對(duì)數(shù)取對(duì)數(shù) h1 0, 則則 i 的雙親為的雙親為 (i - -1)/2 n 若若2*i+1 n, 則則 i 的左子女為的左子女為 2*i+1，若，若2*i+2 - 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-rightChil