數(shù)據(jù)結(jié)構(gòu)知識(shí)點(diǎn)總結(jié)(編輯修改稿)
2025-07-19 15:17 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 i）。元素總數(shù)n（n+1）/=max（i，j），J=min（i，j），LOCa（ij）=LOC（sa[0]）+（I*（I+1）/2+J）*d. 三角矩陣： 上三角陣：k=i*（2ni+1）/2+ji，LOCa（ij）=LOC（sa[0]）+k*d. 下三角陣：k=i*（i+1）/2+j，LOCa（ij）=LOC（sa[0]）+k*d. 對(duì)角矩陣：k=2i+j，LOCa（ij）=LOC（sa[0]）+k*d. 稀疏矩陣的壓縮存儲(chǔ)方式用三元組表把非零元素的值和它所在的行號(hào)列號(hào)做為一個(gè)結(jié)點(diǎn)存放在一起，用這些結(jié)點(diǎn)組成的一個(gè)線性表來(lái)表示。但這種壓縮存儲(chǔ)方式將失去隨機(jī)存儲(chǔ)功能。加入行表記錄每行的非零元素在三元組表中的起始位置，即帶行表的三元組表。 廣義表是n（n≥0）個(gè)元素的有限序列，其中的元素是原子或者是一個(gè)廣義表?！ V義表表頭和表尾的概念： 若廣義表LS非空（n≥1），則這個(gè)廣義表的第一個(gè)元素就是表頭。 其余的元素組成的表稱為L(zhǎng)S的表尾，所以表尾必是一個(gè)子表。廣義表有兩種表示法，一種是括號(hào)表示法，一種是圖形表示法?！ V義表與樹(shù)（形結(jié)構(gòu)）相對(duì)應(yīng)，這個(gè)廣義表就是純表?！ ∪绻粋€(gè)廣義表的結(jié)點(diǎn)又可以被其他結(jié)點(diǎn)所共享，則這個(gè)表稱為再入表?！ ≡试S遞歸的表稱為遞歸表?！ 【€性表∈純表（樹(shù)）∈再入表∈遞歸表 .可見(jiàn)，廣義表是對(duì)線性表和樹(shù)的推廣?！ V義表有兩個(gè)特殊的基本運(yùn)算： 取表頭head（LS）：取表中的第一個(gè)數(shù)據(jù)元素，不能對(duì)空表操作。 取表尾tail（LS）；取除表頭外，其余數(shù)據(jù)元素構(gòu)成的子表，不能對(duì)空表操作。 第六章 樹(shù) 樹(shù)是n個(gè)結(jié)點(diǎn)的有限集合，非空時(shí)必須滿足：只有一個(gè)稱為根的結(jié)點(diǎn)；其余結(jié)點(diǎn)形成m個(gè)不相交的子集，并稱根的子樹(shù)?！ 「情_(kāi)始結(jié)點(diǎn)；結(jié)點(diǎn)的子樹(shù)數(shù)稱度；度為0的結(jié)點(diǎn)稱葉子（終端結(jié)點(diǎn)）；度不為0的結(jié)點(diǎn)稱分支結(jié)點(diǎn)（非終端結(jié)點(diǎn)）；除根外的分支結(jié)點(diǎn)稱內(nèi)部結(jié)點(diǎn)； 有序樹(shù)是子樹(shù)有左，右之分的樹(shù)；無(wú)序樹(shù)是子樹(shù)沒(méi)有左，右之分的樹(shù)；森林是m個(gè)互不相交的樹(shù)的集合； 樹(shù)的四種不同表示方法：樹(shù)形表示法；嵌套集合表示法；凹入表示法廣義表表示法。 二叉樹(shù)的定義：是n≥0個(gè)結(jié)點(diǎn)的有限集，它是空集（n=0）或由一個(gè)根結(jié)點(diǎn)及兩棵互不相交的分別稱作這個(gè)根的左子樹(shù)和右子樹(shù)的二叉樹(shù)組成?！ 《鏄?shù)不是樹(shù)的特殊情形，與度數(shù)為2的有序樹(shù)不同。 二叉樹(shù)的4個(gè)重要性質(zhì)： 二叉樹(shù)上第i層上的結(jié)點(diǎn)數(shù)目最多為2^（i1）（i≥1）。； 深度為k的二叉樹(shù)至多有（2^k）1個(gè)結(jié)點(diǎn)（k≥1）； 在任意一棵二叉樹(shù)中，若終端結(jié)點(diǎn)的個(gè)數(shù)為n0，度為2的結(jié)點(diǎn)數(shù)為n2，則n0=n2+1； 具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為int（log2n）+1. 滿二叉樹(shù)是一棵深度為k，結(jié)點(diǎn)數(shù)為（2^k）1的二叉樹(shù)；完全二叉樹(shù)是滿二叉樹(shù)在最下層自右向左去處部分結(jié)點(diǎn)； 二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu)就是把二叉樹(shù)的所有結(jié)點(diǎn)按照層次順序存儲(chǔ)到連續(xù)的存儲(chǔ)單元中。（存儲(chǔ)前先將其畫(huà)成完全二叉樹(shù)） 樹(shù)的存儲(chǔ)結(jié)構(gòu)多用的是鏈?zhǔn)酱鎯?chǔ)。BinTNode的結(jié)構(gòu)為lchild|data|rchild，把所有BinTNode類型的結(jié)點(diǎn)，加上一個(gè)指向根結(jié)點(diǎn)的BinTree型頭指針就構(gòu)成了二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，稱為二叉鏈表。它就是由根指針root唯一確定的。共有2n個(gè)指針域，n+1個(gè)空指針。根據(jù)訪問(wèn)結(jié)點(diǎn)的次序不同可得三種遍歷：先序遍歷（前序遍歷或先根遍歷），中序遍歷（或中根遍歷）、后序遍歷（或后根遍歷）。時(shí)間復(fù)雜度為O（n）。利用二叉鏈表中的n+1個(gè)空指針域來(lái)存放指向某種遍歷次序下的前趨結(jié)點(diǎn)和后繼結(jié)點(diǎn)的指針，這些附加的指針就稱為“線索”，加上線索的二叉鏈表就稱為線索鏈表。線索使得查找中序前趨和中序后繼變得簡(jiǎn)單有效，但對(duì)于查找指定結(jié)點(diǎn)的前序前趨和后序后繼并沒(méi)有什么作用。樹(shù)和森林及二叉樹(shù)的轉(zhuǎn)換是唯一對(duì)應(yīng)的。轉(zhuǎn)換方法： 樹(shù)變二叉樹(shù)：兄弟相連，保留長(zhǎng)子的連線?！《鏄?shù)變樹(shù)：結(jié)點(diǎn)的右孩子與其雙親連?！ ∩肿兌鏄?shù)：樹(shù)變二叉樹(shù)，各個(gè)樹(shù)的根相連。樹(shù)的存儲(chǔ)結(jié)構(gòu)：有雙親鏈表表示法：結(jié)點(diǎn)data | parent，對(duì)于求指定結(jié)點(diǎn)的雙親或祖先十分方便，但不適于求指定結(jié)點(diǎn)的孩子及后代?！『⒆渔湵肀硎痉ǎ簽闃?shù)中每個(gè)結(jié)點(diǎn)data | next設(shè)置一個(gè)孩子鏈表firstchild，并將data | firstchild存放在一個(gè)向量中。 雙親孩子鏈表表示法：將雙親鏈表和孩子鏈表結(jié)合。 孩子兄弟鏈表表示法：結(jié)點(diǎn)結(jié)構(gòu)leftmostchild |data | rightsibing，附加兩個(gè)分別指向該結(jié)點(diǎn)的最左孩子和右鄰兄弟的指針域?！ ?shù)的前序遍歷與相對(duì)應(yīng)的二叉樹(shù)的前序遍歷一致；樹(shù)的后序遍歷與相對(duì)應(yīng)的二叉樹(shù)的中序遍歷一致?！ ?shù)的帶權(quán)路徑長(zhǎng)度是樹(shù)中所有葉結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度之和。樹(shù)的帶權(quán)路徑長(zhǎng)度最小的二叉樹(shù)就稱為最優(yōu)二叉樹(shù)（即哈夫曼樹(shù)）?！ ≡谌~子的權(quán)值相同的二叉樹(shù)中，完全二叉樹(shù)的路徑長(zhǎng)度最短?！ 」蚵鼧?shù)有n個(gè)葉結(jié)點(diǎn)，共有2n1個(gè)結(jié)點(diǎn)，沒(méi)有度為1的結(jié)點(diǎn)，這類樹(shù)又稱為嚴(yán)格二叉樹(shù)?！ ∽冮L(zhǎng)編碼技術(shù)可以使頻度高的字符編碼短，而頻度低的字符編碼長(zhǎng)，但是變長(zhǎng)編碼可能使解碼產(chǎn)生二義性。如00、00001這三個(gè)碼無(wú)法在解碼時(shí)確定是哪一個(gè)，所以要求在字符編碼時(shí)任一字符的編碼都不是其他字符編碼的前綴，這種碼稱為前綴碼（其實(shí)是非前綴碼）。 哈夫曼樹(shù)的應(yīng)用最廣泛地是在編碼技術(shù)上，它能夠容易地求出給定字符集及其概率分布的最優(yōu)前綴碼。哈夫曼編碼的構(gòu)造很容易，只要畫(huà)好了哈夫曼樹(shù)，按分支情況在左路徑上寫(xiě)代碼0，
語(yǔ)文相關(guān)推薦
鄂ICP備17016276號(hào)-1