傳智播客數(shù)據(jù)結(jié)構(gòu)教程（14）,講師：尹成QQ:77025077博客:,C/C+,算法+實(shí)戰(zhàn),傳智播客,高薪就業(yè),第2頁,上堂課內(nèi)容回顧,1.二叉排序樹,特點(diǎn)：“左小右大”，中序遍歷可得從小到大順序,搜索：同子樹根結(jié)點(diǎn)比較，同找到，小向左，大向右！,插入：搜索父結(jié)點(diǎn)（相應(yīng)子樹空）,小插左，大插右！,刪除：無左子樹，右子樹替代刪除結(jié)點(diǎn)有左子樹，(1)左子樹替代刪除結(jié)點(diǎn)，右子樹接到左子樹最右下結(jié)點(diǎn)。（2）改進(jìn)：左子樹最右下結(jié)點(diǎn)t替代刪除結(jié)點(diǎn)，并將t的左子樹掛到其父節(jié)點(diǎn)的右子樹上。,第3頁,2.Huffman樹-最優(yōu)樹,(1)哈夫曼樹是：WPL最小的樹。,(2)Huffman算法的思路：權(quán)值大的結(jié)點(diǎn)用短路徑，權(quán)值小的結(jié)點(diǎn)用長路徑。,(3)構(gòu)造Huffman樹的步驟：對權(quán)值的合并、刪除與替換,(4)Huffman編碼規(guī)則：左“0”右“1”，是一種前綴碼也稱為最小冗余編碼、緊致碼等，它是數(shù)據(jù)壓縮學(xué)的基礎(chǔ)。,第4頁,哈夫曼樹相關(guān)算法,1.建立huffman樹：結(jié)點(diǎn)信息、父結(jié)點(diǎn)指針、權(quán)值、左右孩子指針。對權(quán)值的合并、刪除與替換,3.Huffman譯碼,2.Huffman編碼：左“0”右“1”，從葉子結(jié)點(diǎn)開始，Huffman編碼是一種前綴碼也稱為最小冗余編碼、緊致碼，等等，它是數(shù)據(jù)壓縮學(xué)的基礎(chǔ)。,看實(shí)際程序注解和演示！,第5頁,建立哈夫曼樹,typedefchardatatype;typedefstructnodedatatypename;folatweight;intparent,lchild,rchild;huftree;,整個(gè)哈夫曼樹的存儲結(jié)構(gòu)：2n-1個(gè)結(jié)點(diǎn)構(gòu)成的靜態(tài)鏈表,第6頁,建樹主要步驟：,2n-1個(gè)結(jié)點(diǎn)初始化；結(jié)點(diǎn)的合并，形成haffman樹注意：無刪除與替換操作，原結(jié)點(diǎn)保留,第7頁,初始狀態(tài)（上）與最終狀態(tài)（下）P210,第8頁,初始狀態(tài)（左）與最終狀態(tài)（右）,第9頁,/*數(shù)據(jù)初始化*m=2*n-1;/總共需要的空間HT=(HuffmanTree)malloc(m+1)*sizeof(HTNode);/分配空間/for(p=*HT,i=1;i=n;+p,+w)*p=wi-1.elem,wi-1.weight,0,0,0;for(i=1;i=n;+i)/結(jié)點(diǎn)、權(quán)值和指針初始化HTi.elem=wi-1.elem;HTi.m_weight=wi-1.m_weight;HTi.parent=HTi.lchild=HTi.rchild=0;for(;i=m;+i)/空結(jié)點(diǎn)初始化隱含i初值n1HTi.elem=0;HTi.m_weight=HTi.parent=HTi.lchild=HTi.rchild=0;,第10頁,/*建立哈夫曼樹*for(i=n+1;i=m;+i)Select(*HT,i-1,/兩結(jié)點(diǎn)權(quán)值相加新結(jié)點(diǎn)權(quán)值,合并,第11頁,哈夫曼編碼,找到n個(gè)結(jié)點(diǎn)的父結(jié)點(diǎn)從父節(jié)點(diǎn)開始到葉子的路徑記錄下來就是編碼，左0右1,注意是逆向編碼，自底向上,第12頁,靜態(tài)順序存儲,typedefstructcnodecharbitsleafnum+1;/編碼字串，最大深度為葉子結(jié)點(diǎn)數(shù)目intstart;/記錄起始點(diǎn)charch;/字符名稱hufcode;,結(jié)構(gòu)簡單但浪費(fèi)空間,第13頁,動態(tài)鏈?zhǔn)酱鎯?typedefchar*huffmancode;,HC=(HuffmanCode)malloc(n*sizeof(char*);HCi=(char*)malloc(n-start)*sizeof(char);,結(jié)構(gòu)復(fù)雜但節(jié)約空間,huffmancodeHC,第14頁,/*哈夫曼樹編碼*(*HC)=(HuffmanCode)malloc(n*sizeof(char*);/分配編碼空間數(shù)組char*HuffmanCodecd=(char*)malloc(n*sizeof(char);/分配求編碼的工作空間cdn-1=0;/編碼結(jié)束符號for(i=1;i=n;+i)/逐個(gè)字符求哈夫曼編碼start=n-1;/編碼結(jié)束符位置for(c=i,f=HTi.parent;f!=0;c=f,f=HTf.parent)/從葉子到根逆向求編碼if(HTf.lchild=c)cd-start=0;elsecd-start=1;(*HC)i=(char*)malloc(n-start)*sizeof(char);/為第i個(gè)字符分配編碼空間strcpy(*HC)i,第15頁,c=i;f=HTi.parent;/從葉子到根逆向求編碼while(f!=0)if(HTf.lchild=c)cd-start=0;/左0右1elsecd-start=1;c=f;f=HTf.parent;,for(c=i,f=HTi.parent;f!=0;c=f,f=HTf.parent),第16頁,哈夫曼譯碼,從根結(jié)點(diǎn)開始依次根據(jù)編碼0或1向下搜索到達(dá)根結(jié)點(diǎn)，提取根結(jié)點(diǎn)的字符繼續(xù)下一個(gè)循環(huán),第17頁,0011110110101,第18頁,例3:設(shè)字符集為26個(gè)英文字母，其出現(xiàn)頻度如下表所示。,注：若圓滿實(shí)現(xiàn)了此方案，平時(shí)成績獎勵5分！,先建哈夫曼樹，再利用此樹對報(bào)文“Thisprogramismyfavorite”進(jìn)行編碼和譯碼。,要求編程實(shí)現(xiàn)：,提示：為了避免在編程調(diào)試過程中輸入數(shù)據(jù)過于麻煩，可采用文件存儲編碼字符及其權(quán)重，每次讀入即可，或直接用數(shù)組存儲。,第19頁,本章小結(jié)（黃色為重點(diǎn)內(nèi)容）,1、定義和性質(zhì),2、存儲結(jié)構(gòu),3、遍歷,4、線索化：線索樹,先序遍歷,中序遍歷,二叉排序樹,第20頁,數(shù)據(jù)結(jié)構(gòu)課程的內(nèi)容,多對多（m:n),第21頁,7.1基本術(shù)語7.2存儲結(jié)構(gòu)7.3圖的遍歷7.4圖的其他運(yùn)算7.5圖的應(yīng)用,第7章圖,第22頁,7.1圖的基本術(shù)語,圖：記為G(V,E)其中：V是G的頂點(diǎn)集合，是有窮非空集；E是G的邊集合，是有窮集。,問：當(dāng)E(G)為空時(shí)，圖G存在否？答：還存在！但此時(shí)圖G只有頂點(diǎn)而沒有邊。,有向圖：無向圖：完全圖：,圖G中的每條邊都是有方向的；圖G中的每條邊都是無方向的；圖G任意兩個(gè)頂點(diǎn)都有一條邊相連接；,若n個(gè)頂點(diǎn)的無向圖有n(n-1)/2條邊,稱為無向完全圖若n個(gè)頂點(diǎn)的有向圖有n(n-1)條邊,稱為有向完全圖,V=vertexE=edge,第23頁,證明：,完全有向圖有n(n-1)條邊。證明：若是完全有向圖，則頂點(diǎn)1必必與所有其他頂點(diǎn)各有2條連線，即有2(n-1)條邊，頂點(diǎn)2有2(n-2)條邊，頂點(diǎn)n-1有2條邊,頂點(diǎn)n有0條邊.總邊數(shù)2(n-1n-210)=2(n-1+0)n/2=n(n-1),完全無向圖有n(n-1)/2條邊。證明：若是完全無向圖，則頂點(diǎn)1必與所有其他頂點(diǎn)各有1條連線，即有n-1條邊，頂點(diǎn)2有n-2條邊，頂點(diǎn)n-1有1條邊,頂點(diǎn)n有0條邊.總邊數(shù)n-1n-210=（n-1+0)n/2=n(n-1)/2,第24頁,例：判斷下列4種圖形各屬什么類型？,無向,無向圖(樹),有向圖,有向,n(n-1)/2條邊,n(n-1)條邊,G1的頂點(diǎn)集合為V(G1)=0,1,2,3邊集合為E(G1)=(0,1),(0,2),(0,3),(1,2),(1,3),(2,3),完全圖,完全圖,第25頁,稀疏圖：邊較少的圖。通常邊數(shù)n2,子圖：設(shè)有兩個(gè)圖G(V,E)和G(V,E)。若VV且EE,則稱圖G是圖G的子圖。,稠密圖：邊很多的圖。無向圖中，邊數(shù)接近n(n-1)/2；有向圖中，邊數(shù)接近n(n-1),帶權(quán)圖：即邊上帶權(quán)的圖。其中權(quán)是指每條邊可以標(biāo)上具有某種含義的數(shù)值（即與邊相關(guān)的數(shù)）。,網(wǎng)絡(luò)：帶權(quán)圖,第26頁,簡單路徑：,路徑上各頂點(diǎn)v1,v2,.,vm均不互相重復(fù)。,回路：,例：,若路徑上第一個(gè)頂點(diǎn)v1與最后一個(gè)頂點(diǎn)vm重合，則稱這樣的路徑為回路或環(huán)。,路徑：,在圖G(V,E)中,若從頂點(diǎn)vi出發(fā),沿一些邊經(jīng)過一些頂點(diǎn)vp1,vp2,vpm，到達(dá)頂點(diǎn)vj。則稱頂點(diǎn)序列(vivp1vp2.vpmvj)為從頂點(diǎn)vi到頂點(diǎn)vj的路徑。它經(jīng)過的邊(vi,vp1)、(vp1,vp2)、.、(vpm,vj)應(yīng)當(dāng)是屬于E的邊。,路徑長度：,非帶權(quán)圖的路徑長度是指此路徑上邊的條數(shù)；帶權(quán)圖的路徑長度是指路徑上各邊的權(quán)之和。,第27頁,路徑：1，2，3，5，6，3路徑長度：5(路徑上結(jié)點(diǎn)數(shù)-1)簡單路徑：1，2，3，5回路：1，2，3，5，6，3，1簡單回路：3，5，6，3,路徑：1，2，5，7，6，5，2，3路徑長度：7簡單路徑：1，2，5，7，6回路：1，2，5，7，6，5，2，1簡單回路：1，2，3，1,第28頁,弧頭和弧尾：有向邊(u,v)稱為弧，邊的始點(diǎn)u叫弧尾，終點(diǎn)v叫弧頭,頂點(diǎn)v的度是與它相關(guān)聯(lián)的邊的條數(shù)。記作TD(v)。在有向圖中,頂點(diǎn)的度等于該頂點(diǎn)的入度與出度之和。頂點(diǎn)v的入度是以v為終點(diǎn)的有向邊的條數(shù),記作ID(v);頂點(diǎn)v的出度是以v為始點(diǎn)的有向邊的條數(shù),記作OD(v)。,鄰接頂點(diǎn)：若(u,v)是E(G)中的一條邊，則稱u與v互為鄰接頂點(diǎn),度、入度和出度：,問：當(dāng)有向圖中僅1個(gè)頂點(diǎn)的入度為0,其余頂點(diǎn)的入度均為1，此時(shí)是何形狀？,答：是樹！而且是一棵有向樹！,第29頁,生成樹：,是一個(gè)極小連通子圖，它含有圖中全部頂點(diǎn)，但只有n-1條邊。如果在生成樹上添加1條邊，必定構(gòu)成一個(gè)環(huán)。若圖中有n個(gè)頂點(diǎn)，卻少于n-1條邊，必為非連通圖。,第30頁,連通圖：,在無向圖中,若從頂點(diǎn)v1到頂點(diǎn)v2有路徑,則稱頂點(diǎn)v1與v2是連通的。如果圖中任意一對頂點(diǎn)都是連通的,則稱此圖是連通圖。,在有向圖中,若對于每一對頂點(diǎn)vi和vj,都存在一條從vi到vj和從vj到vi的路徑,則稱此圖是強(qiáng)連通圖。,強(qiáng)連通圖：,有兩類圖形不在本章討論之列：,第31頁,ADTGraph數(shù)據(jù)對象V：v是具有相同特性的數(shù)據(jù)元素的集合，稱為頂點(diǎn)集。數(shù)據(jù)關(guān)系R：R=VR；VR=|v,wV且P(v,w),表示從v到w的弧，謂詞P(v,w)定義了弧的意義或信息基本操作P：CreatGraph(初始條件：圖G存在，v和圖中頂點(diǎn)有相同特征。操作結(jié)果：在圖G中添加新頂點(diǎn)。（參見P156-257）,圖的抽象數(shù)據(jù)類型,注意：V的大小寫含義不同！,第32頁,7.2圖的存儲結(jié)構(gòu),圖的特點(diǎn)：非線性結(jié)構(gòu)（m:n）,鄰接表鄰接多重表十字鏈表,設(shè)計(jì)為鄰接矩陣,鏈?zhǔn)酱鎯Y(jié)構(gòu)：,順序存儲結(jié)構(gòu)：,無！,（多個(gè)頂點(diǎn)，無序可言）但可用數(shù)組描述元素間關(guān)系。,可用多重鏈表,重點(diǎn)介紹：,鄰接矩陣(數(shù)組)表示法鄰接表(鏈?zhǔn)?表示法,第33頁,一、鄰接矩陣（數(shù)組）表示法,建立一個(gè)頂點(diǎn)表（記錄各個(gè)頂點(diǎn)信息）和一個(gè)鄰接矩陣（表示各個(gè)頂點(diǎn)之間關(guān)系）。設(shè)圖A=(V,E)有n個(gè)頂點(diǎn)，則圖的鄰接矩陣是一個(gè)二維數(shù)組A.Edgenn，定義為：,例1：,鄰接矩陣：,A.Edge=,（v1v2v3v4v5）,v1v2v3v4v5,0000000000000000000000000,分析1：無向圖的鄰接矩陣是對稱的；分析2：頂點(diǎn)i的度第i行(列)中1的個(gè)數(shù)；特別：完全圖的鄰接矩陣中，對角元素為0，其余全1。,0101010101010111010101110,0101010101010111010101110,頂點(diǎn)表：,第34頁,例2：有向圖的鄰接矩陣,分析1：有向圖的鄰接矩陣可能是不對稱的。分析2：頂點(diǎn)的出度=第i行元素之和，OD(Vi)=A.Edgeij頂點(diǎn)的入度=第i列元素之和。ID(Vi)=A.Edgeji頂點(diǎn)的度=第i行元素之和+第i列元素之和,即：TD(Vi)=OD(Vi)+ID(Vi),鄰接矩陣：,A.Edge=,(v1v2v3v4),v1v2v3v4,0000000000000000,注：在有向圖的鄰接矩陣中，第i行含義：以結(jié)點(diǎn)vi為尾的弧(即出度邊）；第i列含義：以結(jié)點(diǎn)vi為頭的弧(即入度邊）。,頂點(diǎn)表：,0110000000011000,0110000000011000,第35頁,容易實(shí)現(xiàn)圖的操作，如：求某頂點(diǎn)的度、判斷頂點(diǎn)之間是否有邊（?。?、找頂點(diǎn)的鄰接點(diǎn)等等。n個(gè)頂點(diǎn)需要n*n個(gè)單元存儲邊(弧);空間效率為O(n2)。對稀疏圖而言尤其浪費(fèi)空間。,特別討論：網(wǎng)（即有權(quán)圖）的鄰接矩陣,定義為：,以有向網(wǎng)為例：,鄰接矩陣：,N.Edge=,(v1v2v3v4v5v6),鄰接矩陣法優(yōu)點(diǎn)：,鄰接矩陣法缺點(diǎn)：,頂點(diǎn)表：,5748956531,5748956531,第36頁,注：用兩個(gè)數(shù)組分別存儲頂點(diǎn)表和鄰接矩陣#defineINFINITYINT_MAX/最大值#defineMAX_VERTEX_NUM20/假設(shè)的最大頂點(diǎn)數(shù)TypedefenumDG,DN,AG,ANGraphKind;/有向/無向圖，有向/無向網(wǎng)TypedefstructArcCell/?。ㄟ叄┙Y(jié)點(diǎn)的定義VRTypeadj;/頂點(diǎn)間關(guān)系，無權(quán)圖取1或0；有權(quán)圖取權(quán)值類型InfoType*info;/該弧相關(guān)信息的指針ArcCell,AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;,圖的鄰接矩陣存儲表示（參見教材P161）,對于n個(gè)頂點(diǎn)的圖或網(wǎng)，空間效率=O(n2),第37頁,Typedefstruct/圖的定義VertexTypevexsMAX_VERTEX_NUM;/頂點(diǎn)表，用一維向量即可AdjMatrixarcs;/鄰接矩陣IntVernum,arcnum;/頂點(diǎn)總數(shù)，?。ㄟ叄┛倲?shù)GraphKindkind;/圖的種類標(biāo)志Mgraph;,第38頁,二、鄰接表（鏈?zhǔn)剑┍硎痉?對每個(gè)頂點(diǎn)vi建立一個(gè)單鏈表，把與vi有關(guān)聯(lián)的邊的信息（即度或出度邊）鏈接起來，表中每個(gè)結(jié)點(diǎn)都設(shè)為3個(gè)域；,每個(gè)單鏈表還應(yīng)當(dāng)附設(shè)一個(gè)頭結(jié)點(diǎn)（設(shè)為2個(gè)域），存vi信息；,表結(jié)點(diǎn),頭結(jié)點(diǎn),鄰接點(diǎn)域，表示vi一個(gè)鄰接點(diǎn)的位置,鏈域，指向vi下一個(gè)邊或弧的結(jié)點(diǎn),數(shù)據(jù)域，與邊有關(guān)信息（如權(quán)值）,數(shù)據(jù)域，存儲頂點(diǎn)vi信息,鏈域，指向單鏈表的第一個(gè)結(jié)點(diǎn),每個(gè)單鏈表的頭結(jié)點(diǎn)另外用順序存儲結(jié)構(gòu)存儲。,第39頁,例1：無向圖的鄰接表,鄰接表,例2：有向圖的鄰接表,鄰接表(出邊),逆鄰接表(入邊),注：鄰接表不唯一，因各個(gè)邊結(jié)點(diǎn)的鏈入順序是任意的。,第40頁,例3：已知某網(wǎng)的鄰接（出邊）表，請畫出該網(wǎng)絡(luò)。,80,64,1,2,5,當(dāng)鄰接表的存儲結(jié)構(gòu)形成后，圖便唯一確定！,第41頁,分析1:對于n個(gè)頂點(diǎn)e條邊的無向圖，鄰接表中除了n個(gè)頭結(jié)點(diǎn)外，只有2e個(gè)表結(jié)點(diǎn),空間效率為O(n+2e)。若是稀疏圖(en2)，則比鄰接矩陣表示法O(n2)省空間。,鄰接表存儲法的特點(diǎn)：,分析2:在有向圖中，鄰接表中除了n個(gè)頭結(jié)點(diǎn)外，只有e個(gè)表結(jié)點(diǎn),空間效率為O(n+e)。若是稀疏圖，則比鄰接矩陣表示法合適。,它其實(shí)是對鄰接矩陣法的一種改進(jìn),怎樣計(jì)算無向圖頂點(diǎn)的度？,鄰接表的缺點(diǎn)：,怎樣計(jì)算有向圖頂點(diǎn)的出度？怎樣計(jì)算有向圖頂點(diǎn)的入度？怎樣計(jì)算有向圖頂點(diǎn)Vi的度：,需遍歷全表,鄰接表的優(yōu)點(diǎn)：,TD(Vi)=單鏈表中鏈接的結(jié)點(diǎn)個(gè)數(shù),OD(Vi)單鏈出邊表中鏈接的結(jié)點(diǎn)數(shù)ID(Vi)鄰接點(diǎn)為Vi的弧個(gè)數(shù),TD(Vi)=OD(Vi)+ID(Vi),空間效率高；容易尋找頂點(diǎn)的鄰接點(diǎn)；,判斷兩頂點(diǎn)間是否有邊或弧，需搜索兩結(jié)點(diǎn)對應(yīng)的單鏈表，沒有鄰接矩陣方便。,第42頁,討論：鄰接表與鄰接矩陣有什么異同之處？,1.聯(lián)系：鄰接表中每個(gè)鏈表對應(yīng)于鄰接矩陣中的一行，鏈表中結(jié)點(diǎn)個(gè)數(shù)等于一行中非零元素的個(gè)數(shù)。2.區(qū)別：對于任一確定的無向圖，鄰接矩陣是唯一的（行列號與頂點(diǎn)編號一致），但鄰接表不唯一（鏈接次序與頂點(diǎn)編號無關(guān)）。(考試怎么辦？給定順序）鄰接矩陣的空間復(fù)雜度為O(n2),而鄰接表的空間復(fù)雜度為O(n+e)。3.用途：鄰接矩陣多用于稠密圖的存儲（e接近n(n-1)/2)；而鄰接表多用于稀疏圖的存儲（edata;if(!visitedv)DFS2(list,v,p);p=p-link;,第54頁,DFS算法效率分析:,（設(shè)圖中有n個(gè)頂點(diǎn)，e條邊）如果用鄰接矩陣來表示圖，遍歷圖中每一個(gè)頂點(diǎn)都要從頭掃描該頂點(diǎn)所在行，因此遍歷全部頂點(diǎn)所需的時(shí)間為O(n2)。如果用鄰接表來表示圖，雖然有2e個(gè)表結(jié)點(diǎn)，但只需掃描e個(gè)結(jié)點(diǎn)即可完成遍歷，加上訪問n個(gè)頭結(jié)點(diǎn)的時(shí)間，因此遍歷圖的時(shí)間復(fù)雜度為O(n+e)。,結(jié)論：稠密圖適于在鄰接矩陣上進(jìn)行深度遍歷；稀疏圖適于在鄰接表上進(jìn)行深度遍歷。,第55頁,二、廣度優(yōu)先搜索(BFS),基本思想：仿樹的層次遍歷過程。,Breadth_FirstSearch,v1,BFS結(jié)果,例1：,例2：,v3,BFS結(jié)果,v4v5,起點(diǎn),遍歷步驟,起點(diǎn),v2v1v6,v9v8v7,第56頁,廣度遍歷：V1V2V3V4V5V6V7V8,廣度遍歷：V1V2V3V4V5V6V7V8,廣度遍歷：V1V2V3V4V6V7V8V5,練習(xí)：,第57頁,廣度優(yōu)先搜索（遍歷）步驟：,簡單歸納：在訪問了起始點(diǎn)v之后，依次訪問v的鄰接點(diǎn)；然后再依次訪問這些頂點(diǎn)中未被訪問過的鄰接點(diǎn)；直到所有頂點(diǎn)都被訪問過為止。,廣度優(yōu)先搜索是一種分層的搜索過程，每向前走一步可能訪問一批頂點(diǎn)，不像深度優(yōu)先搜索那樣有回退的情況。因此，廣度優(yōu)先搜索不是一個(gè)遞歸的過程，其算法也不是遞歸的。,第58頁,討論1：計(jì)算機(jī)如何實(shí)現(xiàn)BFS？,鄰接表,除輔助數(shù)組visitedn外，還需再開一輔助隊(duì)列！,例：,起點(diǎn),輔助隊(duì)列,v2已訪問過了,BFS遍歷結(jié)果,入隊(duì)！,初始f=n-1,r=0,第59頁,討論2：BFS算法如何編程？,BFS1(List,n,v)Visit(v);Visitedv=1;front=n-1;rear=0;qrear=v;while(rear!=front)front=(front+1)%n;v=qfront;p=Listv