C語言-復(fù)習(xí)-重點(diǎn)市公開課特等獎(jiǎng)市賽課微課一等獎(jiǎng)?wù)n件

數(shù)據(jù)結(jié)構(gòu)教材

李春葆數(shù)據(jù)結(jié)構(gòu)教程清華大學(xué)出版社嚴(yán)蔚敏數(shù)據(jù)結(jié)構(gòu)清華大學(xué)出版社參考書

李春葆數(shù)據(jù)結(jié)構(gòu)習(xí)題與解析(第2版或第3版)清華大學(xué)出版社第1頁概述模塊1：線性表模塊2：樹型結(jié)構(gòu)模塊3：圖型結(jié)構(gòu)模塊4：其它第2頁1.數(shù)據(jù)結(jié)構(gòu)定義

數(shù)據(jù)→數(shù)據(jù)元素→數(shù)據(jù)項(xiàng)數(shù)據(jù)結(jié)構(gòu)是指數(shù)據(jù)以及相互之間聯(lián)絡(luò)（或關(guān)系）。包含：（1）數(shù)據(jù)邏輯結(jié)構(gòu)。（2）數(shù)據(jù)存放結(jié)構(gòu)（物理結(jié)構(gòu)）。（3）施加在該數(shù)據(jù)上運(yùn)算。

概述第3頁

數(shù)據(jù)邏輯結(jié)構(gòu)是從邏輯關(guān)系上描述數(shù)據(jù)，它與數(shù)據(jù)存放無關(guān)，是獨(dú)立于計(jì)算機(jī)。數(shù)據(jù)存放結(jié)構(gòu)是邏輯結(jié)構(gòu)用計(jì)算機(jī)語言實(shí)現(xiàn)（亦稱為映象），它是依賴于計(jì)算機(jī)語言。數(shù)據(jù)運(yùn)算是定義在數(shù)據(jù)邏輯結(jié)構(gòu)上，每種邏輯結(jié)構(gòu)都有一組對(duì)應(yīng)運(yùn)算。但運(yùn)算實(shí)現(xiàn)與數(shù)據(jù)存放結(jié)構(gòu)相關(guān)。程序＝數(shù)據(jù)結(jié)構(gòu)＋算法概述第4頁（1）線性結(jié)構(gòu)（2）樹形結(jié)構(gòu)（3）圖形結(jié)構(gòu)概述邏輯結(jié)構(gòu)主要有三大類：第5頁存放結(jié)構(gòu)分為以下四種：（1）次序存放方法（2）鏈?zhǔn)酱娣欧椒ǎ?）索引存放方法（4）散列存放方法

概述第6頁2.算法

算法是對(duì)特定問題求解步驟一個(gè)描述，它是指令有限序列。概述第7頁算法五個(gè)主要特征：（1）有窮性（2）確定性（3）可行性（4）有輸入（5）有輸出

概述第8頁

算法時(shí)間復(fù)雜度：是指其基本運(yùn)算在算法中重復(fù)執(zhí)行次數(shù)。

算法中基本運(yùn)算次數(shù)T(n)是問題規(guī)模n某個(gè)函數(shù)f(n)，記作：T(n)=O(f(n))記號(hào)“O”讀作“大O”，它表示隨問題規(guī)模n增大算法執(zhí)行時(shí)間增加率和f(n)增加率相同。

概述第9頁例分析以下程序段時(shí)間復(fù)雜度。i=1;while(i<=n)i=i*2;解：上述算法中基本操作是語句i=i*2，設(shè)其頻度為T(n)，則有：2T(n)≤n即T(n)≤log2n=O(log2n)。所以，該程序段時(shí)間復(fù)雜度為O(log2n)。第10頁

算法空間復(fù)雜度：是對(duì)一個(gè)算法在運(yùn)行過程中暫時(shí)占用存放空間大小量度。

對(duì)于空間復(fù)雜度為O(1)算法稱為原地工作或就地工作算法。

概述第11頁■遞歸定義3.算法設(shè)計(jì)方法：遞歸在定義一個(gè)算法時(shí)出現(xiàn)調(diào)用本算法成份，稱之為遞歸。概述第12頁■遞歸模型由遞歸出口和遞歸體組成比如，求二叉樹全部結(jié)點(diǎn)個(gè)數(shù)：f(b)=0 b=NULLf(b)=f(b->lchild)+f(b->rchild)+1b≠NULL概述第13頁■遞歸算法設(shè)計(jì)①對(duì)原問題f(s)進(jìn)行分析，假設(shè)出合理“較小問題”f(s');②假設(shè)f(s')是可解，在此基礎(chǔ)上確定f(s)解，即給出f(s)與f(s')之間關(guān)系；③確定一個(gè)特定情況（如f(1)或f(0)）解，由此作為遞歸出口.概述第14頁bb->rchildb->lchild①假設(shè)出合理“較小問題”：假設(shè)左右子樹結(jié)點(diǎn)個(gè)數(shù)可求②求出f(s)與f(s‘)之間關(guān)系：f(b)=f(b->lchild)+f(b->rchild)+1③確定遞歸出口：f(NULL)=0概述第15頁intf(BTNode*b){if(b==NULL)return(0);elsereturn(f(b->lchild)+f(b->rchild)+1);}求解算法：概述第16頁例設(shè)計(jì)求f(n)=1+2+...+n遞歸算法解：f(n)為前n項(xiàng)之和，則f(n-1)=1+2+...+(n-1)假設(shè)f(n-1)可求，則f(n)=f(n-1)+n，所以：f(n)=1 當(dāng)n=1f(n)=f(n-1)+n當(dāng)n>1對(duì)應(yīng)遞歸算法以下：第17頁intf(intn){if(n==1)return(1);elsereturn(f(n-1)+n));}第18頁1.普通線性表線性表：含有相同特征數(shù)據(jù)元素一個(gè)有限序列。不是集合。模塊1：線性結(jié)構(gòu)邏輯結(jié)構(gòu)第19頁（1）次序表

typedefstruct{ ElemTypeelem[MaxSize]; /*存放次序表元素*/ intlength; /*存放次序表長度*/}SqList;存放結(jié)構(gòu)之一模塊1：線性結(jié)構(gòu)第20頁次序表基本運(yùn)算實(shí)現(xiàn)

插入數(shù)據(jù)元素算法：元素移動(dòng)次數(shù)不但與表長n相關(guān)；插入一個(gè)元素時(shí)所需移動(dòng)元素平均次數(shù)n／2。平均時(shí)間復(fù)雜度為O(n)。

模塊1：線性結(jié)構(gòu)第21頁

刪除數(shù)據(jù)元素算法:元素移動(dòng)次數(shù)也與表長n相關(guān)。刪除一個(gè)元素時(shí)所需移動(dòng)元素平均次數(shù)為(n-1)/2。刪除算法平均時(shí)間復(fù)雜度為O(n)。模塊1：線性結(jié)構(gòu)第22頁（2）鏈表

定義單鏈表結(jié)點(diǎn)類型:typedefstructLNode{ElemTypedata;structLNode*next; /*指向后繼結(jié)點(diǎn)*/}LinkList;存放結(jié)構(gòu)之二模塊1：線性結(jié)構(gòu)第23頁定義雙鏈表結(jié)點(diǎn)類型:typedefstructDNode {ElemTypedata;structDNode*prior; /*指向前驅(qū)結(jié)點(diǎn)*/structDNode*next; /*指向后繼結(jié)點(diǎn)*/}DLinkList;模塊1：線性結(jié)構(gòu)第24頁

■單鏈表基本運(yùn)算實(shí)現(xiàn)

重點(diǎn)：（1）頭插法建表和尾插法建表算法，它是很多算法設(shè)計(jì)基礎(chǔ)；（2）查找、插入和刪除操作。模塊1：線性結(jié)構(gòu)第25頁

頭插法建表該方法從一個(gè)空表開始,讀取字符數(shù)組a中字符,生成新結(jié)點(diǎn),將讀取數(shù)據(jù)存放到新結(jié)點(diǎn)數(shù)據(jù)域中,然后將新結(jié)點(diǎn)插入到當(dāng)前鏈表表頭上,直到結(jié)束為止。采取頭插法建表算法以下:模塊1：線性結(jié)構(gòu)第26頁voidCreateListF(LinkList*&L,ElemTypea[],intn){LinkList*s;inti;L=(LinkList*)malloc(sizeof(LinkList));/*創(chuàng)建頭結(jié)點(diǎn)*/L->next=NULL;for(i=0;i<n;i++){s=(LinkList*)malloc(sizeof(LinkList));/*創(chuàng)建新結(jié)點(diǎn)*/s->data=a[i];s->next=L->next; /*將*s插在原開始結(jié)點(diǎn)之前,頭結(jié)點(diǎn)之后*/L->next=s;}}模塊1：線性結(jié)構(gòu)第27頁adcbi=0i=1i=2i=3∧head采取頭插法建立單鏈表過程heada∧headda∧headcda∧headbcda∧第1步:建頭結(jié)點(diǎn)第2步:i＝0,新建a結(jié)點(diǎn),插入到頭結(jié)點(diǎn)之后第3步:i＝1,新建d結(jié)點(diǎn),插入到頭結(jié)點(diǎn)之后第4步:i＝2,新建c結(jié)點(diǎn),插入到頭結(jié)點(diǎn)之后第5步:i＝3,新建b結(jié)點(diǎn),插入到頭結(jié)點(diǎn)之后第28頁

尾插法建表

頭插法建立鏈表即使算法簡單,但生成鏈表中結(jié)點(diǎn)次序和原數(shù)組元素次序相反。若希望二者次序一致,可采取尾插法建立。該方法是將新結(jié)點(diǎn)插到當(dāng)前鏈表表尾上,為此必須增加一個(gè)尾指針r,使其一直指向當(dāng)前鏈表尾結(jié)點(diǎn)。采取尾插法建表算法以下:模塊1：線性結(jié)構(gòu)第29頁voidCreateListR(LinkList*&L,ElemTypea[],intn){LinkList*s,*r;inti;L=(LinkList*)malloc(sizeof(LinkList)); /*創(chuàng)建頭結(jié)點(diǎn)*/L->next=NULL;r=L;/*r一直指向終端結(jié)點(diǎn),開始時(shí)指向頭結(jié)點(diǎn)*/for(i=0;i<n;i++){s=(LinkList*)malloc(sizeof(LinkList));/*創(chuàng)建新結(jié)點(diǎn)*/s->data=a[i];r->next=s;/*將*s插入*r之后*/r=s;}r->next=NULL; /*終端結(jié)點(diǎn)next域置為NULL*/}第30頁adcbi=0i=1i=2i=3head頭結(jié)點(diǎn)adcbb∧采取尾插法建立單鏈表過程模塊1：線性結(jié)構(gòu)第31頁

例設(shè)C={a1,b1,a2,b2,…,an,bn}為一線性表,采取帶頭結(jié)點(diǎn)hc單鏈表存放,編寫一個(gè)算法,將其拆分為兩個(gè)線性表,使得:A={a1,a2,…,an},B={b1,b2,…,bn}模塊1：線性結(jié)構(gòu)第32頁

解:設(shè)拆分后兩個(gè)線性表都用帶頭結(jié)點(diǎn)單鏈表存放。先建立兩個(gè)頭結(jié)點(diǎn)*ha和*hb,它們用于存放拆分后線性表A和B,ra和rb分別指向這兩個(gè)單鏈表表尾,用p指針掃描單鏈表hc,將當(dāng)前結(jié)點(diǎn)*p鏈到ha未尾,p沿next域下移一個(gè)結(jié)點(diǎn),若不為空,則當(dāng)前結(jié)點(diǎn)*p鏈到hb未尾,p沿next域下移一個(gè)結(jié)點(diǎn),如此這么,直到p為空。最終將兩個(gè)尾結(jié)點(diǎn)next域置空。對(duì)應(yīng)算法以下:模塊1：線性結(jié)構(gòu)第33頁voidfun(LinkList*hc,LinkList*&ha,LinkList*&hb){LinkList*p=hc->next,*ra,*rb;ha=hc; /*ha頭結(jié)點(diǎn)利用hc頭結(jié)點(diǎn)*/ra=ha;/*ra一直指向ha末尾結(jié)點(diǎn)*/hb=(LinkList*)malloc(sizeof(LinkList));/*創(chuàng)建hb頭結(jié)點(diǎn)*/rb=hb;/*rb一直指向hb末尾結(jié)點(diǎn)*/模塊1：線性結(jié)構(gòu)第34頁while(p!=NULL){ra->next=p;ra=p;/*將*p鏈到ha單鏈表未尾*/p=p->next;rb->next=p;rb=p; /*將*p鏈到hb單鏈表未尾*/p=p->next;}ra->next=rb->next=NULL;/*兩個(gè)尾結(jié)點(diǎn)next域置空*/}模塊1：線性結(jié)構(gòu)第35頁例已知線性表元素遞增有序，并以帶頭結(jié)點(diǎn)單鏈表作存放結(jié)構(gòu)，設(shè)計(jì)一個(gè)高效算法，刪除表中全部值大于mink且小于maxk元素（若表中存在這么元素）。并分析所寫算法時(shí)間復(fù)雜度。模塊1：線性結(jié)構(gòu)第36頁

解：先在單鏈表中找到其data值則好大于mink結(jié)點(diǎn)*p，其前驅(qū)結(jié)點(diǎn)為*pre。繼續(xù)沿next鏈查找其值大于maxk結(jié)點(diǎn)，在這個(gè)過程中刪除*p結(jié)點(diǎn)。算法以下：

voiddelnode(SNode*h,ElemTypemaxk,ElemTypemink){ SNode*p,*pre; if(maxk>=mink) {pre=h; p=pre->next;模塊1：線性結(jié)構(gòu)第37頁while(p!=NULL&&p->data<=mink) {pre=p;p=p->next; } while(p!=NULL&&p->data<maxk)//刪除*p { pre->next=p->next; free(p); p=pre->next; } }}模塊1：線性結(jié)構(gòu)第38頁

■雙鏈表基本運(yùn)算實(shí)現(xiàn)

重點(diǎn)：插入和刪除結(jié)點(diǎn)算法。模塊1：線性結(jié)構(gòu)第39頁

■循環(huán)鏈表基本運(yùn)算實(shí)現(xiàn)

重點(diǎn)：判斷最終一個(gè)結(jié)點(diǎn)。模塊1：線性結(jié)構(gòu)第40頁例某線性表最慣用操作是在最終一個(gè)結(jié)點(diǎn)之后插入一個(gè)結(jié)點(diǎn)或刪除第一個(gè)結(jié)點(diǎn)，故采取

存放方式最節(jié)約運(yùn)算時(shí)間。A.單鏈表 B.僅有頭結(jié)點(diǎn)單循環(huán)鏈表C.雙鏈表 D.僅有尾指針單循環(huán)鏈表模塊1：線性結(jié)構(gòu)第41頁例設(shè)計(jì)一個(gè)算法在單鏈表中查找元素值為e結(jié)點(diǎn)序號(hào)算法LocateElem(L,e)。思緒：在單鏈表L中從頭開始找第1個(gè)值域與e相等結(jié)點(diǎn),若存在這么結(jié)點(diǎn),則返回位置,不然返回0。

intLocateElem(LinkList*L,ElemTypee){ LinkList*p=L->next;intn=1; while(p!=NULL&&p->data!=e) {p=p->next;n++;} if(p==NULL)return(0); elsereturn(n);}第42頁解：本題答案為D。在有尾指針r單循環(huán)鏈表中在最終一個(gè)結(jié)點(diǎn)之后插入結(jié)點(diǎn)*s操作是：s->next=r->next;r->next=s;r=s。刪除第一個(gè)結(jié)點(diǎn)操作是：p=r->next;r->next=p->next;free(p)。其時(shí)間復(fù)雜度均為O(1)。模塊1：線性結(jié)構(gòu)第43頁2.棧

(1)棧定義棧是一個(gè)先進(jìn)后出表?xiàng)；具\(yùn)算:進(jìn)棧，出棧。邏輯結(jié)構(gòu)模塊1：線性結(jié)構(gòu)第44頁

例已知一個(gè)棧進(jìn)棧序列是1,2,3,…,n,其輸出序列是p1,p2,…,pn,若p1=n,則pi值

。 (A)i (B)n-i (C)n-i+1 (D)不確定答:當(dāng)p1=n時(shí),輸出序列必是n,n-1,…,3,2,1,則有:p2=n-1,p3=n-2,…,pn=1推斷出pi=n-i+1,所以本題答案為C。第45頁

例設(shè)n個(gè)元素進(jìn)棧序列是1,2,3,…,n,其輸出序列是p1,p2,…,pn,若p1=3,則p2值

。 (A)一定是2 (B)一定是1 (C)不可能是1 (D)以上都不對(duì)答:當(dāng)p1=3時(shí),說明1,2,3先進(jìn)棧,馬上出棧3,然后可能出棧,即為2,也可能4或后面元素進(jìn)棧,再出棧。所以,p2可能是2,也可能是4,…,n,但一定不能是1。所以本題答案為C。模塊1：線性結(jié)構(gòu)第46頁（2）次序棧typedefstruct{ ElemTypeelem[MaxSize];inttop; /*棧指針*/}SqStack;存放結(jié)構(gòu)之一模塊1：線性結(jié)構(gòu)第47頁?？諚l件:s.top==-1棧滿條件:s.top==MaxSize-1進(jìn)棧:top++;s.data[s.top]=e;出棧:e=s.data[s.top];s.top—;

次序棧4要素:模塊1：線性結(jié)構(gòu)第48頁（3）鏈棧

typedefstructlinknode{ ElemTypedata; /*數(shù)據(jù)域*/structlinknode*next; /*指針域*/}LiStack;存放結(jié)構(gòu)之二模塊1：線性結(jié)構(gòu)第49頁帶頭結(jié)點(diǎn)單鏈表來實(shí)現(xiàn)(也可不帶頭結(jié)點(diǎn))?？諚l件:s->next==NULL棧滿條件:?模塊1：線性結(jié)構(gòu)第50頁3.隊(duì)列

(1)隊(duì)列定義

隊(duì)列是一個(gè)先進(jìn)先出表。隊(duì)列基本運(yùn)算:進(jìn)隊(duì),出隊(duì)邏輯結(jié)構(gòu)模塊1：線性結(jié)構(gòu)第51頁（2）次序隊(duì)typedefstruct{ ElemTypeelem[MaxSize]；intfront,rear；/*隊(duì)首和隊(duì)尾指針*/}SqQueue；

存放結(jié)構(gòu)之一模塊1：線性結(jié)構(gòu)第52頁隊(duì)空:q.front==q.rear隊(duì)滿:(q.rear+1)%MaxSize==q.front進(jìn)隊(duì):q.rear=(q.rear+1)％MaxSize;q.data[q.rear]=e;出隊(duì):q.front=(q.front+1)％MaxSize;e=q.data[q.front];

環(huán)形隊(duì)列4要素:模塊1：線性結(jié)構(gòu)第53頁（3）鏈隊(duì)structqnode/*數(shù)據(jù)結(jié)點(diǎn)*/{ElemTypedata;structqnode*next;}QNode;typedefstruct/*頭結(jié)點(diǎn)*/{QNode*front;QNode*rear;}LiQueue;存放結(jié)構(gòu)之二模塊1：線性結(jié)構(gòu)第54頁（2）次序串

（3）鏈串

（4）串模式匹配算法（不作要求）4.串（1）串定義

串、子串、串相等、空串、空格串模塊1：線性結(jié)構(gòu)第55頁5.數(shù)組和稀疏矩陣

(1)數(shù)組定義相同類型數(shù)據(jù)元素、有限序列模塊1：線性結(jié)構(gòu)第56頁(2)數(shù)組存放結(jié)構(gòu)

以行序?yàn)橹餍?LOC(ai,j)=LOC(ac1,c2)+[(i-c1)*(d2-c2+1)+(j-c2)]*k

以列序?yàn)橹餍騆OC(ai,j)=LOC(ac1,c2)+[(j-c2)*(d1-c1+1)+(i-c1)]*k

以數(shù)組A[c1..d1,c2..d2]為例模塊1：線性結(jié)構(gòu)第57頁（3）特殊矩陣壓縮存放■對(duì)稱矩陣

若一個(gè)n階方陣A[n][n]中元素滿足ai,j=aj,i（0≤i，j≤n-1），則稱其為n階對(duì)稱矩陣。

A[0..n-1][0..n-1]

B[0..n(n+1)/2]

i(i+1)/2+j 當(dāng)i≥j時(shí)k=j(j+1)/2+i 當(dāng)i＜j時(shí)模塊1：線性結(jié)構(gòu)第58頁■三角矩陣

采取類似壓縮方法.模塊1：線性結(jié)構(gòu)第59頁（4）稀疏矩陣存放結(jié)構(gòu)：■三元組表示■十字鏈表表示

各種表示基本思緒。非零元素遠(yuǎn)小于元素總數(shù)。模塊1：線性結(jié)構(gòu)第60頁

■一個(gè)廣義表中所含元素個(gè)數(shù)稱為它長度.6.廣義表GL=(a,(a),(a,b,c,d),())長度為4。模塊1：線性結(jié)構(gòu)第61頁

■一個(gè)廣義表中括號(hào)嵌套最大次數(shù)為它深度.GL=(a,(a),(a,b,c,d),())深度為2。模塊1：線性結(jié)構(gòu)第62頁

■表第一個(gè)元素a1為廣義表GL表頭，其余部分(a2，…，ai，ai+1，…，an)為GL表尾.

GL=(a,(a),(a,b,c,d),())表頭為a，表尾為((a),(a,b,c,d),())模塊1：線性結(jié)構(gòu)第63頁模塊2：樹形結(jié)構(gòu)

（1）樹定義遞歸定義適合于表示層次結(jié)構(gòu)數(shù)據(jù)1.樹第64頁（2）樹表示法(邏輯表示方法)■樹形表示法■文氏圖表示法■凹入表示法■括號(hào)表示法模塊2：樹形結(jié)構(gòu)

第65頁（3）樹遍歷■先根遍歷算法■后根遍歷算法模塊2：樹形結(jié)構(gòu)

第66頁（4）樹和二叉樹相互轉(zhuǎn)換■樹二叉樹■二叉樹樹模塊2：樹形結(jié)構(gòu)

第67頁2.二叉樹

（1）二叉樹定義根、左子樹、右子樹完全二叉樹,滿二叉樹定義模塊2：樹形結(jié)構(gòu)

第68頁

性質(zhì)1非空二叉樹上葉結(jié)點(diǎn)數(shù)等于雙分支結(jié)點(diǎn)數(shù)加1。即n0=n2+1.

性質(zhì)2非空二叉樹上第i層上至多有2i-1個(gè)結(jié)點(diǎn)（i≥1）。（2）二叉樹性質(zhì)模塊2：樹形結(jié)構(gòu)

第69頁

性質(zhì)3高度為h二叉樹至多有2h-1個(gè)結(jié)點(diǎn)（h≥1）。

性質(zhì)4完全二叉樹性質(zhì)。

性質(zhì)5含有n個(gè)（n＞0）結(jié)點(diǎn)完全二叉樹高度為

log2n+1

或

log2n

+1。（2）二叉樹性質(zhì)模塊2：樹形結(jié)構(gòu)

第70頁

例將一棵有99個(gè)結(jié)點(diǎn)完全二叉樹從根這一層開始，每一層從左到右依次對(duì)結(jié)點(diǎn)進(jìn)行編號(hào)，根結(jié)點(diǎn)編號(hào)為1，則編號(hào)為49結(jié)點(diǎn)右孩子編號(hào)為

。

A.98B.99C.50D.不存在

答：D模塊2：樹形結(jié)構(gòu)

第71頁例

深度為5二叉樹至多有

個(gè)結(jié)點(diǎn)。

A.16B.32C.31D.10

答：相同滿度時(shí)滿二叉樹結(jié)點(diǎn)最多，h=5滿二叉樹結(jié)點(diǎn)個(gè)數(shù)=25-1=31。C。模塊2：樹形結(jié)構(gòu)

第72頁（3）二叉樹存放結(jié)構(gòu)

■二叉樹次序存放結(jié)構(gòu)模塊2：樹形結(jié)構(gòu)

ABCDEF1234567891011121314ABCDEF第73頁i2i2i+1左孩子右孩子第74頁■二叉鏈存放結(jié)構(gòu)

typedefstructnode{ ElemTypedata; /*數(shù)據(jù)元素*/ structnode*lchild;/*指向左孩子*/ structnode*rchild;/*指向右孩子*/}BTNode;第75頁ABC左孩子右孩子第76頁（4）二叉樹遍歷

■先序遍歷■中序遍歷■后序遍歷■層次遍歷通慣用遞歸算法實(shí)現(xiàn)通慣用隊(duì)列來實(shí)現(xiàn)模塊2：樹形結(jié)構(gòu)

第77頁例假設(shè)二叉樹采取二叉鏈存放結(jié)構(gòu)存放,試設(shè)計(jì)一個(gè)算法,輸出一棵給定二叉樹全部葉子結(jié)點(diǎn)。解：輸出一棵二叉樹全部葉子結(jié)點(diǎn)遞歸模型f()以下：f(b)：不做任何事件 若b=NULLf(b)：輸出*b結(jié)點(diǎn)data域若*b為葉子結(jié)點(diǎn)f(b)：f(b->lchild);f(b->rchild) 其它情況模塊2：樹形結(jié)構(gòu)

第78頁

voidDispLeaf(BTNode*b){if(b!=NULL){ if(b->lchild==NULL&&b->rchild==NULL) printf("%c",b->data); DispLeaf(b->lchild); DispLeaf(b->rchild);}}模塊2：樹形結(jié)構(gòu)

先序遍歷思想第79頁例試設(shè)計(jì)判斷兩棵二叉樹是否相同算法，所謂二叉樹t1和t2是相同指是t1和t2都是空二叉樹；或者t1和t2根結(jié)點(diǎn)是相同，t1左子樹和t2左子樹是相同且t1右子樹與t2右子樹是相同。模塊2：樹形結(jié)構(gòu)

第80頁解本題遞歸模型以下：true 若t1=t2=NULLf(t1,t2)=false 若t1、t2之一為NULL,另一不為NULLf(t1->lchild,t2->lchild)&&f(t1->rchild,t2->rchild) 其它情況

對(duì)應(yīng)算法以下：模塊2：樹形結(jié)構(gòu)

第81頁intlike(BTNode*b1,BTNode*b2){ intlike1,like2; if(b1==NULL&&b2==NULL) return1; elseif(b1==NULL||b2==NULL) return0; else {like1=like(b1->lchild,b2->lchild); like2=like(b1->rchild,b2->rchild); return(like1&like2); }}模塊2：樹形結(jié)構(gòu)

后序遍歷思想第82頁例設(shè)計(jì)一個(gè)算法求二叉樹全部結(jié)點(diǎn)個(gè)數(shù)。解：對(duì)應(yīng)算法以下：intnodenum(BTNode*bt){if(bt!=NULL)return(nodenum(bt->lchild)+nodenum(bt->lchild)+1);elsereturn(0);}模塊2：樹形結(jié)構(gòu)

后序遍歷思想第83頁例設(shè)計(jì)一個(gè)算法釋放一棵二叉樹bt全部結(jié)點(diǎn)。解：算法以下：voidrelease(BSTNode*&bt){if(bt!=NULL){release(bt->lchild);release(bt->rchild);free(bt);}}模塊2：樹形結(jié)構(gòu)

后序遍歷思想第84頁（5）線索二叉樹

共有2n-(n-1)=n+1個(gè)空鏈域線索化模塊2：樹形結(jié)構(gòu)

線索化與某種遍歷方式相關(guān)第85頁3.哈夫曼樹（1）哈夫曼樹定義WPL最小，沒有單分支結(jié)點(diǎn)即n1=0模塊2：樹形結(jié)構(gòu)

第86頁（2）哈夫曼樹結(jié)構(gòu)過程（3）哈夫曼編碼結(jié)構(gòu)過程模塊2：樹形結(jié)構(gòu)

第87頁■頂點(diǎn)度、入度和出度■完全圖■子圖■路徑和路徑長度■連通、連通圖和連通分量■強(qiáng)連通圖和強(qiáng)連通分量■權(quán)和網(wǎng)

模塊3：圖形結(jié)構(gòu)（1）圖基本概念第88頁（2）圖存放結(jié)構(gòu)■鄰接矩陣存放方法

掌握兩種存放方法優(yōu)缺點(diǎn)，同一個(gè)功效在不一樣存放結(jié)構(gòu)上實(shí)現(xiàn)算法?！鲟徑颖泶娣欧椒K3：圖形結(jié)構(gòu)第89頁（3）圖遍歷

■深度優(yōu)先搜索遍歷

離初始點(diǎn)越遠(yuǎn)越優(yōu)先訪問。1267354訪問序列：1，2，3，4，5，6，7模塊3：圖形結(jié)構(gòu)第90頁voidDFS(ALGraph*G,intv){ArcNode*p;Visited[v]=1;/*置已訪問標(biāo)識(shí)*/printf("%d",v); /*輸出被訪問頂點(diǎn)編號(hào)*/p=G->adjlist[v].firstarc;while(p!=NULL){if(visited[p->adjvex]==0) DFS(G,p->adjvex);p=p->nextarc; }}模塊3：圖形結(jié)構(gòu)第91頁1267354■廣度優(yōu)先搜索遍歷

離初始點(diǎn)越近越優(yōu)先訪問。訪問序列：1，2，6，7，3，5，4模塊3：圖形結(jié)構(gòu)第92頁voidBFS(ALGraph*G,intv){ ArcNode*p; intqueue[MAXV],front=0,rear=0; intvisited[MAXV];intw,i; for(i=0;i<G->n;i++)visited[i]=0; printf("%2d",v); visited[v]=1; /*置已訪問標(biāo)識(shí)*/ rear=(rear+1)%MAXV; queue[rear]=v;/*v進(jìn)隊(duì)*/模塊3：圖形結(jié)構(gòu)第93頁 while(front!=rear)/*若隊(duì)列不空時(shí)循環(huán)*/ { front=(front+1)%MAXV; w=queue[front];/*出隊(duì)并賦給w*/ p=G->adjlist[w].firstarc; while(p!=NULL) {if(visited[p->adjvex]==0) {printf("%2d",p->adjvex); visited[p->adjvex]=1; rear=(rear+1)%MAXV; queue[rear]=p->adjvex; } p=p->nextarc; } }}模塊3：圖形結(jié)構(gòu)第94頁例試以鄰接表為存放結(jié)構(gòu)，分別寫出基于DFS和BPS遍歷算法來判別頂點(diǎn)i和頂點(diǎn)j(i≠j)之間是否有路徑。解：先置全局變量visited[]為0，然后從頂點(diǎn)i開始進(jìn)行某種遍歷，遍歷之后，若visited[j]=0，說明頂點(diǎn)i與頂點(diǎn)j之間沒有路徑；不然說明它們之間存在路徑。模塊3：圖形結(jié)構(gòu)第95頁基于DFS遍歷算法以下：intvisited[MaxVertexNum];intDFSTrave(ALGraph*G，inti，intj){intk;for(k=0;k<G->n;k++)visited[k]=0;DFS(G，i);//從頂點(diǎn)i開始進(jìn)行深度優(yōu)先遍歷if(visited[j]==0)return0;elsere