數(shù)據(jù)結構教案742

#l7l7具有n個結點的哈夫曼樹共有2n-1個結點。2.如何構造一棵哈夫曼樹？(參考P88)3．哈夫曼編碼對一棵哈夫曼樹約定：指向左孩子的分支表示為0，指向右孩子的分支表示為1。取從根到葉子結點一路上的“0”或“1”組成的序列，稱為葉子結點的前綴編碼。三、分類和判定樹1．用于描述分類問題的二叉樹稱為判定樹。判定樹的每個分支結點對應一種判斷，每個葉子結點對應一種分類結果。2.一個分類問題對應著若干棵判定樹，其中必有一棵判定樹的WPL最小，WPL又稱平均比較次數(shù)。3．一棵判定樹對應著一種算法，哈夫曼樹對應的算法的時間性能最好。4．如何對一個分類問題寫最優(yōu)的算法？對分類結果畫哈夫曼樹；根據(jù)哈夫曼樹寫算法；第7章圖7．1圖的定義和術語一、圖的定義圖G由頂點集V和邊集E組成，記為G=(V,E)。最簡單的圖只有一個頂點；每條邊由其連接的兩個頂點表示：例：無向邊(vl,v2)；有向邊<vl,v2>,<v2,vl>二、術語1.鄰接點若頂點vi,vj存在一條邊，則vi,vj互為鄰接點。在有向邊VVi，Vj>中，稱Vi為起點，Vj為終點。2．頂點的入邊,出邊若存在一條有向邊Vvi，Vj>,則稱它為Vi的出邊，Vj的入邊。3．頂點的入度，出度頂點的度：與頂點v相關聯(lián)的邊數(shù)，記為D(v)；頂點的入度，出度：在有向圖中，頂點v的入邊的數(shù)目，稱為入度，記為ID(v)；頂點v的出邊的數(shù)目，稱為出度，記為OD(v)；D(v)=ID(v)+OD(v)4．無向完全圖，有向完全圖無向完全圖：任意兩個頂點之間都存在一條邊的無向圖；有向完全圖：任意兩個頂點之間都存在方向相反的兩條邊的有向圖；5．子圖設有兩個圖G=（V,E）和G=（V,E）,若'是的子集，E是的子集，則G是的子圖。6連通圖和連通分量連通：在無向圖中，若兩個頂點有路徑，則稱兩頂點是連通的；連通圖：任意兩個頂點都連通的無向圖；連通分量：無向圖中的極大連通子圖。7強連通圖和強連通分量強連通：在有向圖中，若至u，至u都有路徑，則稱，是強連通的；強連通圖：任意兩個頂點都強連通的有向圖；強連通分量：有向圖中的極大連通子圖。8．帶權圖：又稱網(wǎng)帶權有向圖（有向網(wǎng)）帶權無向圖（無向網(wǎng)）7圖的存儲結構一、鄰接矩陣1．鄰接矩陣的構建將各個頂點排成一行和一列，形成矩陣。若行、列頂點之間存在一條邊，則對應元素記1，否則，對應元素記0。2．鄰接矩陣的特點無向圖的鄰接矩陣是對稱的，有向圖的鄰接矩陣一般不對稱。3．用鄰接矩陣表示加權圖只要把元素換成相應邊的權值，元素換成8即可。4．鄰接矩陣的用途便于查找每個頂點的度、入度、出度。無向圖：每個頂點的度等于該頂點相應的行或列中1元素的個數(shù)。有向圖：每個頂點的出度等于該頂點相應行中1元素的個數(shù)，入度等于相應列中1元素的個數(shù)。二、鄰接鏈表樹的孩子鏈表、圖的鄰接鏈表組織結構相同。1．鄰接鏈表的構建①為每個頂點建立一個鄰接鏈表，一個圖有幾個頂點，就有幾個鄰接鏈表。頂點的鄰接鏈表是一個帶頭結點的單鏈表，用于存儲與相鄰接的頂點序號。將所有頭結點組織成一維數(shù)組。2．鄰接鏈表的用途便于求頂點的度、出度。無向圖：每個頂點的度等于它的鄰接鏈表中表結點的個數(shù)。有向圖：每個頂點的出度等于它的鄰接鏈表中表結點的個數(shù)。3．如何求頂點的入度？構造一個逆鄰接鏈表，即頂點的逆鄰接鏈表存儲的是與的入邊相關聯(lián)的頂點序號。注：一個圖的鄰接矩陣是唯一的，但鄰接表一般不唯一。7．3圖的遍歷1．樹的遍歷｛先根遍歷：根結點、各棵子樹后根遍歷：各棵子樹、根結點層次遍歷2．圖的遍歷：適應于無向圖，也適應于有向圖。-深度優(yōu)先搜索遍歷：類似樹的先根遍歷。i廣度優(yōu)先搜索遍歷：類似樹的層次遍歷3．深度優(yōu)先搜索遍歷：首先訪問出發(fā)點V.,然后任選一個V.的未訪問過的鄰接點V.,以V.為新的出發(fā)點繼續(xù)iijj進行深度優(yōu)先搜索。深度優(yōu)先搜索遍歷、廣度優(yōu)先搜索遍歷得到的頂點序列不唯一。7．4圖的應用一、最小生成樹1．什么叫生成樹？從n個頂點的連通圖G中，取它的全部頂點和n-1條邊構成子圖G，如果這些邊剛好將g的全部頂點連通但又不形成回路，則稱子圖g是的一棵生成樹。注意：①一個連通圖可以有多棵生成樹。②生成樹是邊數(shù)極少的連通子圖。連通分量：指極大連通子圖。根據(jù)圖的寬度優(yōu)先遍歷或深度優(yōu)先遍歷可構造生成樹。2．最小生成樹①生成樹的權：各條邊權值之和權值最小的生成樹，稱為最小生成樹。②帶權無向圖才可構造最小生成樹。求造價最低的通訊網(wǎng)問題，實際是求最小生成樹問題。構造最小生成樹的算法：Prim（普里姆）算法二、拓撲排序1．拓撲序列在有向圖中，若不存在回路，則所有頂點可排成一個線性序列，以便列出各頂點的前后關系，稱此序列為拓撲序列。2．拓撲排序：實現(xiàn)有向圖的一個拓撲序列的過程。任何一個有向無環(huán)圖，其全部頂點可以排成一個拓撲序列，且其拓撲序列不唯一。若圖中入度為0的頂點和出度為0的頂點都是唯一的，則其拓撲序列是唯一的。3．構成有向圖拓撲序列的過程從圖中選擇一個入度為0的頂點，輸出該頂點。從圖中刪除該頂點及其相關聯(lián)的所有邊。重復執(zhí)行1，2，直到找不到入度為0的頂點。三、最短路徑1．最短路徑問題帶權有向圖才存在最短路徑問題。圖的路徑長度：一條路徑上各條邊的權值之和。2．求一個源點到其余各個頂點的最短路徑：Dijkstra迪杰斯特拉）算法從源點到其余各個頂點的最短路徑中，先求最短的一條，再求次短的一條，以此順序，最后求最長的一條。3．Dijkstra算法描述①假設S為頂點集合，初值為源點v0。首先從v0出發(fā)的所有邊中找出權值最小的邊的終點加入到S中。下一條最短路徑是終點不在S中，中間只經(jīng)過S中的頂點且路徑長度最短，找到后將終點加入到S中。反復執(zhí)行（3）,直到所有頂點都加入到S中。例：根據(jù)P115圖7.17，求頂點VI到其余各頂點的最短路徑。終占k、八、、V2V3V4V5集合S

第1次10OO30100{V1,V2}第2次106030100{V1,V2,V4}第3次10503090{V1,V2,V4,V3}第4次10503060{V1,V2,V4,V3,V5}V1到各頂點的最短路徑是：Vf2(,)1：(,)V1fV：3(V,1V,4V)3V1fV5：(V,1V,4V,3V)5第8章查找8．1基本概念、各種數(shù)據(jù)的邏輯結構數(shù)據(jù)邏輯結構特點線性表線性結構數(shù)據(jù)兀素之間存在著一對一的邏輯關系。樹樹型結構數(shù)據(jù)兀素之間存在著一對多的邏輯關系。圖圖狀結構數(shù)據(jù)兀素之間存在著多對多的邏輯關系。查找表集合數(shù)據(jù)兀素之間不存在任何關系。二、查找表1．定義：查找表是一種以集合為邏輯結構，以查找為核心運算的數(shù)據(jù)結構例：一個平面表格，當各條記錄可以任意排列時，就成為查找表。2．關鍵字：由一個或多個數(shù)據(jù)項組成，可標識若干條記錄；主鍵：由一個或多個數(shù)據(jù)項組成，能唯一標識一條記錄。3．查找：在查找表中尋找關鍵字值等于給定值的記錄，若找到，則返回記錄號；否則，則查找失敗。4．靜態(tài)查找表和動態(tài)查找表靜態(tài)查找表：只做建表、查找操作；動態(tài)查找表：做建表、查找、插入、刪除操作。8．2靜態(tài)查找表?靜態(tài)查找表的存儲結構：順序表、有序表、索引順序表一、順序表上的查找1．順序表的類型定義typedefstruct{intkey;類型data;}ELEMENT;typedefstruct{ELEMENTr[maxsize];intlen;}SSTABLE;2．在順序表上實現(xiàn)查找運算，采用“順序查找法”對順序表從后往前依次查找關鍵字值等于給定值k的記錄，若找到,則返回記錄的序號。3．查找長度：記錄的鍵值與給定值的比較次數(shù)，稱為查找長度。它用來衡量查找算法的時間性能。查找成功的平均查找長度n€1ASL=°（口為記錄條數(shù)）厶查找不成功的平均查找長度為：n二、有序表上的查找1．查找表中各元素之間無任何邏輯關系，但各元素的鍵值存在次序關系。2．有序表：各元素按關鍵字值升序（或降序）排列的順序表。3．在有序表上實現(xiàn)查找運算，采用“二分查找法”每次將查找區(qū)間中間位置上的記錄鍵值與給定值k作比較，若不等則縮小查找區(qū)間，直到查找成功，或查找區(qū)間長度為0。例：在有序表（5，12，30，45，70，73，80，85，89，100，103，109）查找關鍵字值為85的記錄，則二分查找法的過程為：5,12,30,45,70,73,80,85,89,100,103,109123456789101112第1次查找：low=1,high=12，則mid=6第2次查找：low=7,high=12，則mid=9第3次查找：low=7,high=8,則mid=7第4次查找：low=8,high=8,則mid=8（8號記錄的關鍵字值為85,查找成功。）三、索引順序表上的查找1．索引順序表由兩部分組成：一個順序表和一個索引表,且滿足：順序表的記錄鍵值“按塊有序”。對于順序表的每一塊,索引表有相應的一個“索引項”,每個索引項含兩大域：塊起始位置和塊內最大鍵值。2．在索引順序表上實現(xiàn)查找運算，采用“分塊查找法”①確定待查鍵值所在的塊。（索引表）②在塊內查找待查的鍵值。（順序表）?小結：三種查找法的比較：順序查找二分查找分塊查找查找效率最低最高居中限制最少最多居中8．3動態(tài)查找表廠靜態(tài)查找表（順序表、有序表、索引順序表）查找表J動態(tài)查找表（二叉排序樹、散列表）一、二叉排序樹對二叉樹進行中根遍歷，若得到的結點鍵值的序列是逐漸遞增的有序序列，則稱為二叉排序樹。特點：任一結點的鍵值大于其左子樹上所有結點的鍵值，小于其右子樹上所有結點的鍵值。二、二叉排序樹的生成生成二叉排序樹的過程就是一個反復插入結點的過程，且保