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