數(shù)據(jù)結構課程的主要內容-資料下載頁
2025-06-25 07:23本頁面
【正文】 lchild指示結點的后繼167。 樹和森林167。 樹的存儲結構167。 雙親表示法 用一組地址連續(xù)的空間存放樹中的結點，每個結點存放本身的信息和雙親結點所在的位置序號。167。 孩子表示法216。 多重鏈表——每個結點有多個指針域，分別指向其每個子樹。同構或不同構。216。 孩子鏈表 ——每個結點有一個孩子鏈表，n個結點鏈表的頭指針順序存儲。216。 孩子雙親表示法——雙親表示和孩子鏈表表示法結合起來。167。 孩子兄弟表示法——二叉鏈表表示法***** 二叉鏈表作為樹的存儲結構，鏈表中的兩個指針域分別指向該結點的第一個孩子和該結點的下一個兄弟。167。 樹、森林與二叉樹的轉換167。 以二叉鏈表作為轉換的依據(jù)。167。 樹轉化成二叉樹后，二叉樹根一定沒有右子樹。167。 森林的第二棵樹樹根看成是第一棵樹樹根的兄弟。167。 樹與森林的遍歷167。 樹的先序遍歷是指先訪問樹的根結點，然后依次先序遍歷根的各子樹。等價于先序遍歷該樹對應的二叉樹。167。 樹的后序遍歷是指先依次后序遍歷樹的根結點的各子樹，然后訪問根結點。等價于中序遍歷該樹對應的二叉樹。167。 先序遍歷森林是指從左到右依次按先序遍歷森林中的每一棵樹，相當于先序遍歷該森林對應的二叉樹。167。 后序遍歷森林是指從左到右依次按后序遍歷森林中的每一棵樹，相當于中序遍歷該森林對應的二叉樹。167。 赫夫曼樹及其應用167。 最優(yōu)二叉樹——赫夫曼樹 從樹中一個結點到另一個結點之間的分支構成這兩個結點之間的路徑，路徑上的分支數(shù)目稱做路徑長度。樹的路徑長度是從樹根到每一結點的路徑長度之和。結點的帶權路徑長度為從該結點到樹根之間的路徑長度與結點上權的乘積。樹的帶權路徑長度為樹中所有葉子結點的帶權路徑長度之和，記作WPL。 假設有n個權值{w1,w2,…,wn}，試構造一棵有n個葉子結點的二叉樹，每個葉子結點帶權為wi，則其中帶權路徑長度WPL最小的二叉樹稱做最優(yōu)二叉樹或赫夫曼樹。167。 赫夫曼算法——構造赫夫曼樹根據(jù)給定的n個權值構成n棵二叉樹的集合F，每棵二叉樹Ti只有一個帶權為wi的根結點。在F中選取兩棵根結點的權值最小的樹作為左右子樹構造一棵新二叉樹，其根結點的權值為左右子樹根結點的權值之和。在F中刪除這兩棵樹，將新二叉樹加入F重復構造，直到 F中只含一棵樹為止，這棵樹就是赫夫曼樹。167。 赫夫曼編碼——電報碼電文的總長盡可能短——出現(xiàn)次數(shù)多的字符采用盡可能短的編碼。任一個字符的編碼都不是另一個字符編碼的前綴——前綴編碼。設計電文總長最短的二進制前綴編碼即為以n種字符出現(xiàn)的頻率作權，設計一棵赫夫曼樹的問題。約定赫夫曼樹的左分支表示字符‘0’，右分支表示字符‘1’，從根結點到葉子結點的路徑上分支字符組成的字符串作為該葉子結點字符的編碼。圖 圖是復雜的非線性結構，結點之間的關系是任意的，任何兩個數(shù)據(jù)元素都可能相關。圖的應用極為廣泛。l 圖的定義和術語l 圖是兩個集合的二元組，G=（V，E），V表示頂點的有窮非空集合，E是頂點之間關系的有窮集合。l 若圖中的每條邊都是有方向的，頂點之間的關系v,w表示從v到w的一條弧，v為弧尾或初始點，w為弧頭或終端點，該圖為有向圖。l 若圖中的每條邊無方向，有v,w必有w,v，頂點之間的關系以無序對v,w表示，表示從v到w的一條邊，該圖為無向圖。l n表示圖中頂點數(shù)目，e表示邊或弧的數(shù)目，若不考慮頂點自身的邊或弧，無向圖e的取值范圍是0~n(n1)/2，具有n(n1)/2條邊的無向圖為完全圖；有向圖e的取值范圍是0~n(n1)，具有n(n1) 條邊的有向圖為有向完全圖。有很少條邊或弧(enlogn)的圖為稀疏圖，反之為稠密圖。與圖的邊或弧相關的數(shù)稱為權，帶權的圖稱為網(wǎng)。l 假設兩個圖，G=(V,E)和G’=(V’,G’)，如果V’205。V且E’205。E，則稱G’為G的子圖。l 圖從頂點v到v’的路徑是一個頂點序列，路徑長度是路徑上的邊或弧的數(shù)目。第一個頂點和最后一個頂點相同的路徑稱為回路或環(huán)，序列中頂點不重復的回路為簡單路徑。除第一個頂點和最后一個頂點之外，其余頂點不重復出現(xiàn)的回路為簡單回路或簡單環(huán)。l 無向圖l 若邊(v,w)206。E，則稱頂點v,w互為鄰接點，即v,w相鄰接，邊(v,w)依附于頂點v,w，邊(v,w)和頂點相關聯(lián)。頂點的度是和v相關聯(lián)的邊的數(shù)目，記為TD(v)。l 無向圖中，若頂點v到頂點v’有路徑，稱v和v’是連通的。若對于圖中任意兩個頂點v,w都是連通的，則該圖為連通圖。連通分量是無向圖中的極大連通子圖。l 一個連通圖的生成樹是一個極小連通子圖，它含有圖中全部頂點，但只有足以構成一棵樹的n1條邊。如果在樹上添加一條邊，必定構成一個環(huán)。有n1條邊的圖不一定是生成樹。l 有向圖l 若弧(v,w)206。E，則稱頂點v鄰接到頂點w，頂點w鄰接自頂點v，弧(v,w)和頂點v,w相關聯(lián)。以頂點v為頭的弧的數(shù)目為v的入度ID(v)，以v為尾的弧的數(shù)目為v的出度OD(v)，頂點v的度TD(v)=ID(v)+OD(v)。l 有向圖中，每一對(v,w)206。V，若v到w和w到v都存在路徑，則G是強連通圖。有向圖中的極大強連通子圖是有向圖的強連通分量。l 若一個有向圖恰有一個頂點的入度為0，其余頂點的入度均為1，則是一棵有向樹。一棵有向圖的生成森林由若干棵有向樹組成，含有圖中全部頂點，但只有足以構成若干棵不相交的有向樹的弧。l 圖的存儲結構l 數(shù)組表示法——兩個數(shù)組分別存儲數(shù)據(jù)元素（頂點）信息和數(shù)據(jù)元素之間關系（邊或?。┬畔ⅰ徑泳仃嚒 鄰接表l 無向圖的鄰接表——為每個頂點建立一個單鏈表，鏈表中的結點表示依附于該頂點的邊。結點由三個域組成，其中鄰接點域表示與該頂點鄰接的點在圖中的位置，鏈域指示下一條邊的結點，數(shù)據(jù)域存儲和邊相關的信息。l 各頂點鏈表的表頭結點通常以順序結構的形式存儲，以便隨機訪問任一頂點的鏈表。l 有向圖的鄰接表和逆鄰接表 鄰接表鏈表中的結點表示以該頂點為尾的弧，而逆鄰接表鏈表中的結點表示以該頂點為頭的弧。l 十字鏈表（有向圖） 兩類結點——弧結點和頂點結點。 l 鄰接多重表（無向圖）l 圖的遍歷l 深度優(yōu)先搜索l 廣度優(yōu)先搜索
法律信息相關推薦
鄂ICP備17016276號-1