數(shù)據(jù)結(jié)構(gòu)考研考點(diǎn)精講及復(fù)習(xí)思路

《《數(shù)據(jù)結(jié)構(gòu)》考研考點(diǎn)精講及復(fù)習(xí)思《數(shù)據(jù)結(jié)構(gòu)》考研分析與指導(dǎo)~、考試特點(diǎn)分１．在計(jì)算機(jī)專業(yè)入學(xué)統(tǒng)，作為專業(yè)課綜合中的一個(gè)版塊進(jìn)行。在部分自主命題院校入學(xué)考試中有單獨(dú)作為一個(gè)科目進(jìn)行，也有和其他一門或者兩門科目聯(lián)合出題。２．出題形式多為選擇題和綜合應(yīng)用３．側(cè)重于基礎(chǔ)知識點(diǎn)及對知識點(diǎn)靈活運(yùn)用的考二、復(fù)習(xí)方１．分清復(fù)習(xí)的階段，把握復(fù)習(xí)進(jìn)２．親手做題，在練習(xí)中總結(jié)出題方向和方法，重視，透徹分析，揣摩出題人心理。只有做好一定量的習(xí)題，才能幫助理解和牢固掌握考點(diǎn)。３．講過的知識點(diǎn)和題徹底掌握并及時(shí)回顧，不要學(xué)過忘過。４．注重知識點(diǎn)之間的聯(lián)系５．不可忽視基礎(chǔ)概念和知識體系。但是同時(shí)還要做到重點(diǎn)突出，突破難點(diǎn)，查缺補(bǔ)漏三、考試內(nèi)容及分值分布章重難必考考試題１．緒選２．線性√√√選擇、綜合分３．棧和隊(duì)√√√選擇、綜合分４．√√選擇、填５．?dāng)?shù)組和廣義選擇、填６．√√√選擇、綜合分７．√√√選擇、綜合分８．查√√√選擇、綜合分９．排√√√選擇、綜合分１四、章節(jié)知識點(diǎn)及題型分章知識題型題型易考１數(shù)據(jù)結(jié)構(gòu)的定義、邏輯結(jié)的分類、算法的定義和雜度和物理結(jié)構(gòu)法性能的選題邏輯結(jié)構(gòu)和物理結(jié)構(gòu)的和算法性能的復(fù)雜度分類、法的定義２性表的概念及運(yùn)算性表的順序性表的鏈?zhǔn)皆囗?xiàng)式的表示相加選題１．線性表的定義和基２．線性表的順序３．線性表的鏈?zhǔn)奖具\(yùn)算綜合析題１．線性表算法的設(shè)的定義和運(yùn)的順序和鏈選題１．棧和隊(duì)列的定義和２．棧和隊(duì)列的順序運(yùn)鏈?zhǔn)剑硹ｊ?duì)的應(yīng)列的定義和運(yùn)列的順序和鏈列的應(yīng)用式綜合析題棧和隊(duì)列的應(yīng)用算４類型的定的順序和鏈?zhǔn)降哪Ｊ狡ヅ渌惴ㄟx題１．串的定義和綜合析題２．串的模式匹配算５組的定義和運(yùn)算組的順序殊矩陣的壓縮義表選題數(shù)組和廣義表的定義和矩陣的壓縮的概念與定叉樹的定義和結(jié)構(gòu)選題樹與二叉樹的定義樹、森林和二叉樹的系結(jié)構(gòu)６二叉樹的遍歷與線化、森林和二叉樹的關(guān)夫曼樹及其應(yīng)用系綜合析題哈夫曼樹及其應(yīng)選題圖的定義和結(jié)圖的定義與圖的結(jié)構(gòu)７的遍小生成撲排序和關(guān)鍵路徑短路徑綜合析題最小生成樹拓?fù)渑判蜿P(guān)鍵路徑最短路２續(xù)章知識題題型易考選擇查找的定義順序查找１．查找基本概念折半查找８２．基于靜３．基于綜合分題索二引叉順排序序表樹查找４．哈希的查找平衡二叉排序樹Ｂ樹哈希的解決９①排②交換排③選擇排④歸并排⑤基數(shù)排綜合分題各種排序方法的應(yīng)用３第一 緒~、考試分考重點(diǎn)與難考中常見題復(fù)習(xí)思路與方數(shù)邏、四綜１．熟和物；練，結(jié)?構(gòu)二、考點(diǎn)講數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計(jì)算的程序設(shè)計(jì)問題時(shí)處理的操作對象以及它們之間的關(guān)系和操作等等的學(xué)科。１．基本概·數(shù)據(jù)（Ｄａｔａ）對客觀事物的符號描述，能輸入到計(jì)算機(jī)中并被計(jì)算機(jī)程序處理的符號的總稱；能被計(jì)算機(jī)識別、和加工處理的信息的載體。字母：ａ～ｚ，單詞圖、音頻信號等表·數(shù)據(jù)元素（ＤａｔａＥｌｅｍｅｎｔ）數(shù)據(jù)元素是組成數(shù)據(jù)的基本單位，是數(shù)據(jù)集合的，在計(jì)算機(jī)中通常作為一個(gè)整體進(jìn)行考慮和處理。例，“對弈樹”中的一個(gè)格４書目信息中的一條書數(shù)據(jù)項(xiàng)：一個(gè)數(shù)據(jù)元素可由若干個(gè)數(shù)據(jù)項(xiàng)組成例，一條書目信息是由書名、作者名、分類等多個(gè)數(shù)據(jù)項(xiàng)組成的數(shù)據(jù)項(xiàng)是數(shù)據(jù)的不可分割的最小單位。例如：有一個(gè)學(xué)生表如下所示。這個(gè)表中的數(shù)據(jù)元素是學(xué)生記錄，每個(gè)數(shù)據(jù)元素由四個(gè)數(shù)據(jù)（即學(xué)號、姓別、和班號）組成學(xué)班１張男８劉女李女陳男王男董男５王女·數(shù)據(jù)結(jié)構(gòu)（Ｄａｔａ數(shù)據(jù)結(jié)構(gòu)是指相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素集合結(jié)構(gòu)（Ｓｔｒｕｃｔｕｒｅ）：數(shù)據(jù)元素相互之間的關(guān)系。在形式上可用二元組表示：ＤａｔａＳｔｒｕｃｔｕｒｅ＝（Ｄ，Ｄ：數(shù)據(jù)元素的有限集Ｓ：Ｄ上關(guān)系的有限集Ｄ＝｛ｋｉ｜１≤ｎ０ｋｉ示集合Ｄ中的第ｉ個(gè)結(jié)點(diǎn)或數(shù)據(jù)元ｎ為Ｄ中結(jié)點(diǎn)的個(gè)若ｎ＝０，則Ｄ是一個(gè)空集，表示Ｄ無結(jié)構(gòu)可言，有時(shí)也可以認(rèn)為它具有任意的結(jié)構(gòu)Ｓ＝｛ｒｊ｜１≤ｍｍ０ｒｊ示集合Ｓ中的第ｊ個(gè)二元關(guān)系（簡稱關(guān)系ｍ為Ｓ中關(guān)系的個(gè)若ｍ＝０，則Ｓ是一個(gè)空集，表明集合Ｄ中的元結(jié)點(diǎn)間不存在任何關(guān)系，彼此是獨(dú)立Ｄ上的一個(gè)關(guān)系ｒ是序偶的集合，對于ｒ中的任一序偶＜ｘ，ｙ＞（ｘ，ｙＤ），稱序偶的第一結(jié)點(diǎn)為第二結(jié)點(diǎn)的直接前驅(qū)結(jié)點(diǎn)（通常簡稱前驅(qū)結(jié)點(diǎn)），稱第二結(jié)點(diǎn)為第一結(jié)點(diǎn)的直接后繼結(jié)點(diǎn)（通常簡稱后繼結(jié)點(diǎn)）。如在＜ｘ，ｙ＞的序偶中，ｘ為ｙ的前驅(qū)結(jié)點(diǎn)，而ｙ為ｘ的后繼結(jié)點(diǎn)。若某個(gè)結(jié)點(diǎn)沒有前驅(qū)，則稱該結(jié)點(diǎn)為開始結(jié)點(diǎn)；若某個(gè)結(jié)點(diǎn)沒有后繼，則稱該結(jié)點(diǎn)為終端結(jié)點(diǎn)；除此之外的節(jié)點(diǎn)稱為節(jié)點(diǎn)“尖括號”表示有向關(guān)系，“圓括號”表示無向關(guān)系例如：用二元組表示學(xué)生表，學(xué)生表有７個(gè)結(jié)點(diǎn)，依次用ｋ１～ｋ７表示，則對應(yīng)的二元組表示為：ＤａｔａＳｔｒｕｃｔｕｒｅ＝（Ｄ，Ｓ）其中：Ｄ＝｛ｋ１，ｋ２，ｋ３，ｋ４，ｋ５，ｋ６，ｋ７Ｓ＝｛＜ｋ１，ｋ２＞，＜ｋ２，ｋ３＞，＜ｋ３，ｋ４＞，＜ｋ４，ｋ５＞，＜ｋ５，ｋ６＞，＜ｋ６，ｋ７＞邏輯結(jié)構(gòu)圖：可以將數(shù)據(jù)結(jié)構(gòu)用圖形形象地表示出來，圖形中的每個(gè)結(jié)點(diǎn)對應(yīng)著一個(gè)數(shù)據(jù)元素，兩結(jié)點(diǎn)之間的連線對應(yīng)著關(guān)系中的一個(gè)序偶。上述“學(xué)生表”數(shù)據(jù)結(jié)構(gòu)用下圖的圖形表示２．?dāng)?shù)據(jù)結(jié)構(gòu)的內(nèi)邏輯結(jié)數(shù)據(jù)元間的關(guān)邏輯結(jié)構(gòu)可看作是從具體問題抽象出來的數(shù)學(xué)模型按照邏輯關(guān)系的不同特性分類：邏輯結(jié)構(gòu)類型的分（１）線性結(jié)所謂線性結(jié)構(gòu)，該結(jié)構(gòu)中的結(jié)點(diǎn)之間存在一對一的關(guān)系其特點(diǎn)是：開始結(jié)點(diǎn)和終端結(jié)點(diǎn)都是惟一的，除了開始結(jié)點(diǎn)和終端結(jié)點(diǎn)以外，其余結(jié)點(diǎn)都有且僅有一個(gè)前驅(qū)結(jié)點(diǎn)，有且僅有一個(gè)后繼結(jié)點(diǎn)。順序表就是典型的線性結(jié)構(gòu)（２）非線性結(jié)所謂非線性結(jié)構(gòu)，該結(jié)構(gòu)中的結(jié)點(diǎn)之間存在一對多或多對多的關(guān)系。它又可以細(xì)分為樹形結(jié)構(gòu)和圖形結(jié)構(gòu)兩類。所謂樹形結(jié)構(gòu)，該結(jié)構(gòu)中的結(jié)點(diǎn)之間存在一對多的關(guān)系。其特點(diǎn)是每個(gè)結(jié)點(diǎn)最多只有一個(gè)前驅(qū)６但可以有多個(gè)后繼，可以有多個(gè)終端結(jié)點(diǎn)。非線性結(jié)構(gòu)樹形結(jié)構(gòu)簡稱為樹ＵＮＩＸ文件系統(tǒng)的系統(tǒng)結(jié)構(gòu)所謂圖形結(jié)構(gòu)，該結(jié)構(gòu)中的結(jié)點(diǎn)之間存在多對多的關(guān)系。其特點(diǎn)是每個(gè)結(jié)點(diǎn)的前驅(qū)和后繼的個(gè)數(shù)都可以是任意的。因此，可能沒有開始結(jié)點(diǎn)和終端結(jié)點(diǎn)，也可能有多個(gè)開始結(jié)點(diǎn)、多個(gè)終端結(jié)點(diǎn)。圖形結(jié)構(gòu)簡稱為圖。結(jié)構(gòu)（物理結(jié)構(gòu)）邏輯結(jié)構(gòu)在計(jì)算機(jī)中的 映象，是邏輯結(jié)構(gòu)在計(jì)算機(jī)中的實(shí)現(xiàn)，它包括數(shù)據(jù)元素的表示和關(guān)系的表示。順序結(jié)非順序結(jié)構(gòu)（鏈?zhǔn)?結(jié)構(gòu)）索引結(jié)構(gòu)散列結(jié)例如：用順序法和鏈?zhǔn)椒ū硎鞠旅娴膶W(xué)生表學(xué)班１張男８劉女李女陳男王男董男５王女用順序法存放學(xué)生表的結(jié)構(gòu)體定義為７《《數(shù)據(jù)結(jié)構(gòu)》考研考點(diǎn)精講及復(fù)習(xí)思ｓｔｒｕｃｔＳｔｕｄ／號／／／號／／／／／ ｃｈａｒｎａｍｅ［８］；ｃｈａｒｓｅｘ［２］ｃｈａｒｃｌａｓｓ［４］ Ｓｔｕｄｓ［７］＝｛１，“張斌”，“男”，“９９０１”｝…｛５，＂王萍＂，＂女＂，＂９９０１＂｝結(jié)構(gòu)體數(shù)組Ｓｔｕｄｓ各元素在內(nèi)存中按順序存放，即第ｉ（１ｉ６個(gè)學(xué)生對應(yīng)的元素Ｓｔｕｄｓ［ｉ］存放在第ｉ＋１個(gè)學(xué)生對應(yīng)的元素Ｓｔｕｄｓ［ｉ＋１］之前，Ｓｔｕｄｓ［ｉ＋１］正好在Ｓｔｕｄｓ［ｉ］之后。用鏈?zhǔn)椒ù娣艑W(xué)生表的結(jié)構(gòu)體定義為：ｔｙｐｅｄｅｆｓｔｒｕｃｔｎｏｄｅ｛ｉｎｔ／號／ｃｈａｒｎａｍｅ［８］／／ｃｈａｒｓｅｘ［２］ｃｈａｒｃｌａｓｓ［４］／ 性別／ 指向下ｓｔｒｕｃｔ指向下｝

學(xué)生的指針學(xué)生表構(gòu)成的鏈表如下圖所示。其中的ｈｅａｄ為第一個(gè)數(shù)據(jù)元素的指針鏈?zhǔn)椒ǖ娜秉c(diǎn)·空間占用無法隨機(jī)８鏈?zhǔn)椒ǖ膬?yōu)點(diǎn)便于修改（、刪除、移動）３．算法（１）算法（Ａｌｇｏｒｉｔｈｍ）的定Ａｌｇｏｒｉｔｈｍｉｓａｆｉｎｉｔｅｓｅｔｏｆｒｕｌｅｓｗｈｉｃｈｇｉｖｅｓａｓｅｑｕｅｎｃｅｏｆｏｐｅｒａｔｉｏｎｆｏｒｓｏｌｖｉｎｇａｓｐｅｃｉｆｉｃｔｙｐｅｏｆｐｒｏｂｌｅｍ．（算法是規(guī)則的有限集合，是為解決特定問題而規(guī)定的一系列操作。）（２）算法的特①有窮性：有限步驟之內(nèi)正常結(jié)束，不能形成無窮循環(huán)②確定性：算法中的每一個(gè)步驟必須有確定含義，無二義性③可行性：原則上能精確進(jìn)行，操作可通過已實(shí)現(xiàn)的基本運(yùn)算執(zhí)行有限次而完成④輸入：有多個(gè)或０個(gè)輸入⑤輸出：至少有一個(gè)或多個(gè)輸出在算法的五大特性中，最基本的是有限性、確定性和可行性。４．算法描述的工具描述算法的方自然語言：優(yōu) 簡單。缺 有歧異，表達(dá)復(fù)雜思想不明晰，不能方式很好結(jié)高級程序設(shè)計(jì)語言，如Ｐａｓｃａｌ，Ｃ／Ｃ＋＋，Ｊａｖａ等。優(yōu)點(diǎn) 克服了自然語言的缺點(diǎn)，可直接執(zhí)行。缺點(diǎn) 對部分問題的描述比較煩雜， 類語言。和高級程序設(shè)計(jì)語言類似，但是對其中一些比較煩雜的部分進(jìn)行和簡化（原因：類舉法主要目的是為了清晰的表述思想）例：兩個(gè)數(shù)據(jù)ａ，ｂ交換空舉自然語言：交換ａ，ｂ的空間高級語言：｛ｘ＝ａ；ａ＝ｂ；ｂ＝ｘ；｝類語言：ａｂ；／／交換空間５．對算法作性能評衡量算法效率的方法主要有兩大類事后統(tǒng)計(jì)：利用計(jì)算機(jī)的時(shí)鐘事前分析估算：用高級語言編寫的程序運(yùn)行的時(shí)間主要取決于如下因素算法問題規(guī)模使用語言：級別越高，效率越低；編譯程序；機(jī)器通常，從算法中選取一種對于研究的問題來說是基本操作的原操作，以該基本操作重復(fù)執(zhí)行的次數(shù)作為算法執(zhí)行的時(shí)間度量?；静僮髦貜?fù)執(zhí)行的次數(shù)分別為１，ｎ，９設(shè)算法的問題規(guī)模為頻度：語句重復(fù)執(zhí)行的次數(shù)稱為該語句的頻度，記ｆ（ｎ）對算法各基本操作的頻度求和，便可得算法的時(shí)間復(fù)雜度。但實(shí)際中所關(guān)心的主要是一個(gè)算法所花時(shí)間的數(shù)量級，即取算法各基本操作的最大頻度數(shù)量級。時(shí)間復(fù)雜度：算法執(zhí)行時(shí)間度量，記Ｔ（ｎ）＝Ｏ（ａｘｌｅｖｅｌｆ（ｎ）））。ｆ（ｎ）＝１＋ｎ＋ｎ２＋ｎ３Ｔ（ｎ）＝Ｏ（ｎ３）Ｏ的數(shù)學(xué)定義：若Ｔ（ｎ）和ｆ（ｎ）是定義在正整數(shù)集合上的兩個(gè)函數(shù)，則如果存在正常數(shù)Ｃ和ｎ得當(dāng)ｎ≥時(shí)，總滿足０Ｔｎ）≤Ｃｆｎ），則記做Ｔ（ｎ）＝Ｏ（ｆ（ｎ））也就是只求出Ｔ（ｎ）的最高階（數(shù)量級），忽略其低階項(xiàng)和常系數(shù)，這樣既可簡化Ｔ（ｎ）的計(jì)算，能比較客觀地反映出當(dāng)ｎ很大時(shí)，算法的時(shí)間性能。６．算法的空間復(fù)雜度關(guān)于算法的空間需求，類似于算法的時(shí)間復(fù)雜度，采用空間復(fù)雜度作為算法所需空間的量度，記作：Ｓ（ｎ）＝Ｏ（ｆ（ｎ）三、舉１．從邏輯結(jié)構(gòu)上可以把數(shù)據(jù)結(jié)構(gòu)分為（ ）兩大類．【交通科技大學(xué)】Ａ．動態(tài)結(jié)構(gòu)、靜態(tài)結(jié)構(gòu)Ｂ．順序結(jié)構(gòu)、鏈?zhǔn)浇Y(jié)Ｃ．線性結(jié)構(gòu)、非線性結(jié)構(gòu)Ｄ．初等結(jié)構(gòu)、構(gòu)造型結(jié)２．在下面的程序段中，對ｘ的賦值語句的頻度為（ ）【工商大學(xué)】ＦＯＲｉ：＝１ＴＯｎＤＯＦＯＲｊ：＝１ＴＯｎｘ：＝ｘ＋２Ａ．Ｏ（ Ｂ．Ｏ（ Ｃ．Ｏ（ｎ２ Ｄ．Ｏ（ｌｏｇ２３．以下屬于邏輯結(jié)構(gòu)的是 ）【西安電子科技大學(xué)Ａ．順序 Ｂ．哈希 Ｃ．有序 Ｄ．單鏈四、本講小本章講解了數(shù)據(jù)、數(shù)據(jù)結(jié)構(gòu)、算法的基本概念，數(shù)據(jù)的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)。重點(diǎn)講解了數(shù)據(jù)的４種邏輯結(jié)構(gòu)和４種物理結(jié)構(gòu)，以及算法復(fù)雜度。第二 線性分２． 線性表的概念及運(yùn)算［一般了解２．２ 線性表的順序［熟練掌握］２． 線性表的鏈?zhǔn)剑凼炀氄莆盏冢笨贾攸c(diǎn)與難考考重點(diǎn)與難考中常見題復(fù)習(xí)思路與方線性表的基本概念和常用線性表在常用操作、性表選擇題、２．儲掌握線性?操作、線性表的順序方式?的順序?綜合分析題二、考點(diǎn)講２． 線性表的概念及運(yùn)１．線性表的定—個(gè)線性表是具有ｎ個(gè)數(shù)據(jù)元素的有限序列。２．線性表的長度

記為（ａ１，…，ａｉ－ａｉａｉ，…，ａｎ線性表中元素的個(gè)數(shù)ｎ（ｎ＞＝０），ｎ＝０時(shí)，稱為空表

ｉ個(gè)元素，稱ｉ為數(shù)據(jù)元素ａｉ性表中的位序４．線性表的邏輯結(jié)例子英文字母表（Ａ，Ｂ，…，Ｚ）車輛登記表５．線性表的特同一性：線性表由同類數(shù)據(jù)元素組成，每一個(gè)ａｉ須屬于同一數(shù)據(jù)對象有窮性：線性表由有限個(gè)數(shù)據(jù)元素組成，表長度就是表中數(shù)據(jù)元素的個(gè)數(shù)有序性：線性表中相鄰數(shù)據(jù)元間存在著序偶關(guān)系＜ａｉ，ａｉ＋１＞。６．線性表的基本運(yùn)算初始化ＩｎｉｔＬｉｓｔ（Ｌ建立一個(gè)空表求表長ＬｉｓｔＬｅｎｇｔｈ（Ｌ）返回線性表的長度讀表元素ｅｔＥｍＬ，ｉ，ｅ用ｅ返回Ｌ中第ｉ個(gè)數(shù)據(jù)元素的值定位ＬａｅＥｌｅｍＬ，ｅ，ｃｍｅ））返回滿足關(guān)系的數(shù)據(jù)元素的位序ＬｉｓｔＩｎｓｅｒｔ（Ｌｉ，ｅ）在Ｌ中第ｉ個(gè)位置之前新的數(shù)據(jù)元素ｅ，線性表的長度增１。刪除ＬｉｓｔＤｅｌｅｔｅ（Ｌｉ，＆ｅ）刪除Ｌ的第ｉ個(gè)位置上的數(shù)據(jù)元素ｅ，線性表的長度減１輸出ＬｉｓｔＤｉｓｐｌａｙ（Ｌ）按前后次序輸出線性表的所有元素練習(xí)１：兩個(gè)線性表ＬＡ和ＬＢ分別表示兩個(gè)集合Ａ和Ｂ，現(xiàn)求一個(gè)新的集合Ａ＝∪Ｂ。ｖｏｉｄｕｎｉｏｎ（ＬｉｓｔａＬｉｓｔＬｂ）｛Ｌａｌｅｎ＝ＬｉｓｔＬｅｎｇｔｈ（Ｌａ）；Ｌｂｌｅｎ＝ＬｉｓｔＬｅｎｇｔｈ（Ｌｂ）ｆｏｒ（ｉ＝１；ｉ＜＝Ｌｂｌｅｎ；ｉ＋＋）｛ｔＥｍＬｂ，ｉ，ｅ）；ｉｆ（?。幔澹牛恚蹋幔?，ｅｑｕａｌ））ＬｉｓｔＩｎｓｅｒｔ（Ｌａ，＋＋Ｌａｌｅｎ，ｅ）；｝｝練習(xí)

Ｏ（ＬｉｓｔＬｅｎｇｔｈ（Ｌａ）×ＬｉｓｔＬｅｎｇｔｈ（Ｌｂ）兩個(gè)線性表ＬＡ和ＬＢ中的數(shù)據(jù)元素按值非遞減有序排列，現(xiàn)將ＬＡ和ＬＢ歸并為一個(gè)新的線性表，ＬＣ中的數(shù)據(jù)元素仍按值非遞減有序排列。ＬＡ＝（３，５，８，ＬＢ＝（２，６，８，９，１１，１５，ＬＣ＝（２，３，５，６，８，８，９，１１，１１，１５，ａ，當(dāng)ａ!ｂｃｂ，當(dāng)ａ＞ｂｖｏＭｒｇｅｉｔＬｉｓｔＬａ，ＬｉｓｔＬｂ，Ｌｉｓｔ｛ＩｎｉｔＬｉｓｔ（Ｌｃ）Ｌａｌｅｎ＝ＬｉｓｔＬｅｎｇｔｈ（Ｌａ）； Ｌｂｌｅｎ＝ＬｉｓｔＬｅｎｇｔｈ（Ｌｂ）；ｉ＝ｊ＝１；ｋ＝０；ｗｈｉｌｅ（（ｉ＜＝Ｌａｌｅｎ）＆＆（ｊ＜＝Ｌｂｌｅｎ））ｔＥｍＬａ，ｉ，ａ）；ｔＥｍＬｂ，ｊ，ｂ）ｉｆ（ａ＜＝ｂ）｛ＬｉｓｔＩｎｓｅｒｔ（Ｌｃ，＋＋ｋ，ａ）；＋＋ｉ；｝ｅｌｓｅ｛ＬｉｓｔＩｎｓｅｒｔ（Ｌｃ，＋＋ｋ，ｂ）；＋＋ｊ；｝｝ｗｈｉｌｅ（ｉ＜＝Ｌａｌｅｎ）ｔＥｍＬａ，ｉ＋＋，ａ）；ＬｉｓｔＩｎｓｅｒｔ（Ｌｃ，＋＋ｋ，ａ）；｝ｗｈｉｌｅ（ｊ＜＝Ｌｂｌｅｎ）｛ｔＥｍＬｂ，ｊ＋＋，ｂ）；ＬｉｓｔＩｎｓｅｒｔ（Ｌｃ，＋＋ｋ，ｂ）；｝Ｏ（ＬｉｓｔＬｅｎｇｔｈ（Ｌａ）＋ＬｉｓｔＬｅｎｇｔｈ（Ｌｂ））例，Ｌａ＝（３，５，８），Ｌｂ＝（２，６，８，９，１５）構(gòu)造Ｌｃ＝（２，３，５，６，８，８，９，１５）首先，Ｌａｌｅｎ＝３；Ｌｂｌｅｎ＝５；２．２ 線性表的順序表示１．順序表：按順序方式構(gòu)造的線性表假設(shè)線性表中有ｎ個(gè)元素，每個(gè)元素占ｋ個(gè)單元，第一個(gè)元素的地址為ｌｏｃ（ａ），則可以通過如下公式計(jì)算出第ｉ個(gè)元素的地址ｌｏｃ（ａｉ）：ｌｏｃ（ａｉ）＝ｌｏｃ（ａ１）＋（ｉ－１）×ｋ其中ｌｏｃ（ａ１）稱為址。２．順序表的特點(diǎn)邏輯結(jié)構(gòu)中相鄰的數(shù)據(jù)元素在結(jié)構(gòu)中仍然相鄰線性表的順序結(jié)構(gòu)是一種隨機(jī)存取的結(jié)構(gòu)。３．順序表的描述：ｔｙｐｅｄｅｆ｛ＥｌｅｍＴｙｐｅ ／／當(dāng)前長 ｌｉｓｔｓｉｚｅ；／／分配的容｝／／ＥｌｅｍＴｙｐｅｅｌｅｍ［Ｅｔｙｐｅｄｅｆ＃Ｅｐｅ ＃為根據(jù)具體問題確定的數(shù)據(jù)類型ｔｙｐｅｄｅｆｉｎｔ ４．順序表上基本運(yùn)算的實(shí)初始化ＳｔａｔｕｓＩｎｉｔＬｉｓｔＳｑ（ＳｑＬｉｓｔ｛Ｌ．ｅｌｅｍ＝（ＥｌｅｍＴｙｐｅ）ａｌｃ（ＬＩＳＴＩＮＩＴＳＩＺＥｓｉｚｅｏｆ（ＥｌｅｍＴｙｐｅ））；ｉｆ（！Ｌ．ｅｘｉｔ（ＯＥＬＷ；Ｌ．ｌｅｎｇｔｈ＝０；Ｌ．ｌｉｓｔｓｉｚｅ＝ＬＩＳＴＩＮＩＴｒｅｔｕｒｎ｝Ｌ．ｅｌｅｍ＝ｎｅｗＥｌｅｍＴｙｐｅ［ＬＩＳＴＩＮＩＴＳＩＺＥ］順序表的：在表中第４個(gè)元前“２１“順序表中元ＳｔａｔｕｓＬｉｓｔＩｎｓｅｒｔＳｑ（ＳｑＬｉｓｔ＆Ｌ，ｉｎｔｉ，ＥｌｅｍＴｙｐｅｅ）｛ｉｆ（（ｉ＜１）｜｜（ｉ＞Ｌ．ｌｅｎｇｔｈ＋１））ｒｅｔｕｒｎＥＲＲＯＲ；ｉｆ（Ｌ．ｌｅｎｇｔｈ＞＝Ｌ．ｌｉｓｔｓｉｚｅ）｛ｒｅａｌｌｏｃ（…）；…．；／／越界處理；｝ｑ＝＆（Ｌ．ｅｌｅｍ［ｉ－１］）ｆｏｒ（ｐ＝＆（Ｌ．ｅｌｅｍ［Ｌ．ｌｅｎｇｔｈ－１］；ｐ＞＝ｑ；－－（ｐ＋１）＝ｐ；ｑ＝ｅ；＋＋Ｌ．ｌｅｎｇｔｈ；ｎ｝／／越界處ｉｆ（Ｌ．ｌｅｎｇｔｈ＞＝Ｌ．ｌｉｓｔｓｉｚｅ ｎｅｗｂａｓｅ＝（ＥｌｅｍＴｙｐｅ）ｒｅａｌｌｏｃ（Ｌ．ｅｌｅｍ（Ｌ．ｌｉｓｔｓｉｚｅ＋ＬＩＳＴＩＮＣＲＥＭＥＮＴ）ｓｉｚｅｏｆ（ＥｌｅｍＴｙｐｅ））ｉｆ（?。睿澹鳎猓幔螅澹?ｅｘｉｔ（ＯＶＥＬＷ；Ｌ．ｅｌｅｍ＝ｎｅｗｂａｓｅ；Ｌ．ｌｉｓｔｓｉｚｅ＋＝ＬＩＳＴＩＮＣＲＥＭＥＮＴ；算法時(shí)間復(fù)雜度：時(shí)間主要花在移動元素上，而移動元素的個(gè)數(shù)取決于元素位置。ｉ＝１，需移動ｎ個(gè)元素；ｉ＝ｎ＋１，需移動０個(gè)元素ｉ＝ｉ，需移動ｎ－ｉ＋１個(gè)元素假設(shè)ｐｉ是在第ｉ個(gè)元前一個(gè)新元素的概則長度為ｎ的線性表 一個(gè)元素所需移動元素次數(shù)的期望Ｅｉｓ＝∑ｐｉ（ｎ－ｉ＋１）ｉ設(shè)在任何位置元素等概率，ｎ

＝ｎ＋１ ｎ＋１（ｎ－ｉ＋１）ｉ ｎ＋ｉ

Ｏ（順序表的歸并，表中元素非遞減排列ｖｉｄＭｅｒｇｓＳｑ（ＳｑＬｉｓｔＬａ，ＳｑＬｉｓｔＬｂ，ＳｑＬｉｓｔｃ｛ｐａ＝Ｌａ．ｅｌｅｍ；ｐｂ＝Ｌｂ．Ｌｃ．ｌｉｓｔｓｉｚｅ＝Ｌｃ．ｌｅｎｇｔｈ＝Ｌａ．ｌｅｎｇｔｈ＋Ｌｂ．ｌｅｎｇｔｈ；ｐｃ＝Ｌｃ．ｅｌｅｍ＝（ＥｌｅｍＴｙｐｅ）ｌｃ…）；ｉｆ（！Ｌｃ．ｅｌｅｍ）ｅｘｉｔ（ＯＶＬＷ；ｐａｌａｓｔ＝Ｌａ．ｅｌｅｍ＋Ｌａ．ｌｅｎｇｔｈ－１；ｐｂｌａｓｔ＝Ｌｂ．ｅｌｅｍ＋Ｌｂ．ｌｅｎｇｔｈ－１；ｗｈｉｌｅ（（ｐａ＜＝ｐａｌａｓｔ）＆＆ｐｂ＜＝ｐｂｌａｓｔ））｛ｉｆ（ｐａ＜＝ｐｂ） ｐｃ＋＋＝ｐａ＋＋；ｅｌｓｅｐｃ＋＋＝ ｐｂ＋＋；｝ｗｈｉｌｅ（ｐａ＜＝ｐａｌａｓｔ）ｐｃ＋＋＝ｐａ＋＋；ｗｈｉｌｅ（ｐｂ＜＝ｐｂｌａｓｔ） ｐｃ＋＋＝ｐｂ＋＋；｝順序表的基礎(chǔ)要點(diǎn)１．無需為表示元素間的邏輯關(guān)系而增加額外的空間，密度大（１００％）；２．可隨機(jī)存取表中的任一元素。３．或刪除一個(gè)元素時(shí)，需平均移動表的一半元素，具體的個(gè)數(shù)與該元素的位置有關(guān)，在等概率情況下，ｎ／２，刪除（ｎ－１）／２；Ｏ（ｎ）４．分配只能預(yù)先進(jìn)行分配５．將兩個(gè)各有ｎ個(gè)元素的有序表歸并為一個(gè)有序表，其最少的比較次數(shù)是：ｎ練習(xí)２．２９已知Ａ、Ｂ、Ｃ為三個(gè)元素值遞增有序的順序表，現(xiàn)要求對Ａ作如下運(yùn)算，刪去那些既在Ｂ中出現(xiàn)又在Ｃ中出現(xiàn)的元素，實(shí)現(xiàn)上述算法并分析時(shí)間復(fù)雜度。Ａ＝Ａ－（Ａ＝（１，２，６，６，８，９，１０，１０，１１，１５）Ｂ＝（１，２，６，６，７，９，１０，１５）Ｃ＝（３，４，６，７，７，９，９，９，１０，Ａ＝（１，２，８，１１，１５）分析：先從Ｂ和Ｃ中找出公有元素，記為ｅＡ中從當(dāng)前位置開始，凡小于ｓａｍｅ的元素均保留（存到新的位置），等于ｓａｍｅ的跳過大于ｓａｍｅ時(shí)就再找下一個(gè)ｖｏｉｄＳｑＬｉｓｔＩｎｔｅｒｓｅｃｔＤｅｌｅｔｅ（ＳｑＬｉｓｔＡＳｑＬｉｓｔＢ，ＳｑＬｉｓｔ ｐａ＝Ａ．ｅｌｅｍ；ｐａｌａｓｔ；ｐｂ；ｐｂｌａｓｔ；ｐｃ；ｐｃｌａｓｔ；ｗｈｉｌｅ（（ｐａ＜＝ｐａｌａｓｔ）＆＆（ｐｂ＜＝ｐｂｌａｓｔ）＆＆（ｐｃ＜＝ｐｃｌａｓｔ））｛ｉｆ（ｐｂ＜ｐｃ） ｐｂ＋＋；ｅｌｓｅ｛

ｐｃ＋＋ｓａｍｅ＝ｗｈｉｌｅ（（ｐｂ＜＝ｐｂｌａｓｔ）ｗｈｉｌｅ（（ｐｃ＜＝ｐｃ

＆＆（ｐｂ＝＝ａｅ＆＆（ｐｃ＝＝ｍｅ

ｐｂ＋＋；ｐｃ＋＋ｗｈｉｌｅ（（ｐａ＜＝ｐａｌａｓｔ）＆＆（ｐａ＜ｍｅ）ｐ０＋＋＝ ｐａ＋＋；｝／／

ｗｈｉｌｅ（（ｐａ＜＝ｐａ

＆＆（ｐａ＝＝ａｅ ｐａ＋＋｝／／ｗｈｉｌｅ（ｐａ＜＝ｐａｐ０＋＋＝ Ａ．ｌｅｎｇｔｈ＝ｐ０"Ａ．ｅｌｅｍ；｝三、舉１．下面關(guān)于線性表的敘述中，錯(cuò)誤的是哪一個(gè)？（ ）【北方交通大學(xué)】Ａ．線性表采用順序，必須占用一片連續(xù)的單元。Ｂ．線性表采用順序，便于進(jìn)行和刪除操作Ｃ．線性表采用，不必占用一片連續(xù)的單元。Ｄ．線性表采用，便于和刪除操作。２．若長度為ｎ的線性表采用順序結(jié)構(gòu)，在其第ｉ個(gè)位置一個(gè)新元素的算法的時(shí)間復(fù)雜為 ）（１＜＝ｉ＜＝ｎ＋１）?！竞娇蘸教齑髮W(xué)Ａ．Ｏ（ Ｂ．Ｏ（ Ｃ．Ｏ（ Ｄ．Ｏ（ｎ２四、本講小本講主要講解了：線性表的基本概念和常用操作、線性表的順序方式。?？碱}型：選擇題，綜合分析題。應(yīng)試方法：理解并熟練掌握線性表的順序方式和線性表的基本運(yùn)算在現(xiàn)行方式下在實(shí)現(xiàn)方法。第２~、考試分考重點(diǎn)與難考試中常見題復(fù)習(xí)思路與方線性表的鏈?zhǔn)浇Y(jié)構(gòu)?綜?式存二、考點(diǎn)講２．３ 線性表的鏈?zhǔn)奖硎揪€性表鏈?zhǔn)浇Y(jié)構(gòu)的特點(diǎn)：用一組任意的單元線性表的元素，不要求邏輯上相鄰的元素在物理位置上也相鄰刪除時(shí)不需移動大量元素；失去順序表可隨機(jī)存取的優(yōu)點(diǎn)。例，整數(shù)數(shù)組ａ［３］＝｛３，５，６｝１．線性鏈表（單鏈表結(jié)點(diǎn)：數(shù)據(jù)元素的映象數(shù)據(jù)域用來結(jié)點(diǎn)的值指針域用來數(shù)據(jù)元素的直接后繼的地址（或位置）頭指指示鏈表中第一個(gè)結(jié)點(diǎn)的位置，單鏈表可由頭指針唯一確定單鏈表的映頭結(jié)在鏈表的第一個(gè)結(jié)點(diǎn)之前附設(shè)一個(gè)結(jié)點(diǎn)，頭指針指向頭結(jié)點(diǎn)。設(shè)置頭結(jié)點(diǎn)的目的是空表與非空表的操作，簡化鏈表操作的實(shí)現(xiàn)。首元結(jié)鏈表中線性表中第一個(gè)數(shù)據(jù)元素的結(jié)點(diǎn)鏈表結(jié)構(gòu)描述：ＴｙｐｅｄｅｆｓｔｒｕｃｔＬＮｏｄｅ｛ＥｌｅｍＴｙｐｅｓｔｒｕｃｔ 單鏈表基本運(yùn)算實(shí)現(xiàn)（１）初始化線性表ＩｎｉｔＬｉｓｔ（該運(yùn)算建立一個(gè)空的單鏈表，即創(chuàng)建一個(gè)頭結(jié)點(diǎn)。ｖｏｉｄＩｎｉｔＬｉｓｔ（ＬｉｎｋＬｉｓｔＬ）｛Ｌ＝（ＬｉｎｋＬｉｓｔ）ｃｓｉｚｅｏｆ（ＬＮｏｄｅ））創(chuàng)／創(chuàng)／Ｌ－＞ｎｅｘｔ＝｝

建頭結(jié)（２）銷毀線性表ＤｅｓｔｒｏｙＬｉｓｔ（單鏈表Ｌ占用的內(nèi)存空間。即逐一全部結(jié)點(diǎn)的空間?！丁稊?shù)據(jù)結(jié)構(gòu)》考研考點(diǎn)精講及復(fù)習(xí)思ｖｏｉｄＤｅｓｔｒｏｙＬｉｓｔ（ＬｉｎｋＬｉｓｔ｛ＬｉｎｋＬｉｓｔｐ＝Ｌ，ｑ＝ｐ－＞ｎｅｘｔ；ｗｈｉｌｅ（ｑ?。剑危眨蹋蹋?ｆｒｅｅ（ｐ）ｐ＝ｑ；ｑ＝ｐ－＞｝ｆｒｅｅ（ｐ）｝（３）判線性表是否為空表ＬｉｓｔＥｍｐｔｙ（若單鏈表Ｌ沒有數(shù)據(jù)結(jié)點(diǎn)，則返回真，否則返回假。ｉｎｔＬｉｓｔＥｍｐｔｙ（ＬｉｎｋＬｉｓｔＬ）｛ｒｅｔｕｒｎ（Ｌ－＞ｎｅｘｔ＝＝ＮＵＬＬ）｝（４）求線性表的長度ＬｉｓｔＬｅｎｇｔｈ（Ｌ）返回單鏈表Ｌ中數(shù)據(jù)結(jié)點(diǎn)的個(gè)數(shù)。ｉｎｔＬｉｓｔＬｅｎｇｔｈ（ＬｉｎｋＬｉｓｔＬ）｛ＬｉｎｋＬｉｓｔｐ＝Ｌ；ｉｎｔｉ＝０；ｗｈｉｌｅ（ｐ－＞ｎｅｘｔ?。剑危眨蹋蹋椋穑剑穑荆颍澹簦酰颍睿ǎ椋ǎ担┹敵鼍€性表ＤｉｓｐＬｉｓｔ（逐一掃描單鏈表Ｌ的每個(gè)數(shù)據(jù)結(jié)點(diǎn)，并顯示各結(jié)點(diǎn)的ｄａｔａ域值。ｖｏｉｄＤｉｓｐＬｉｓｔ（ＬｉｎｋＬｉｓｔＬ）｛ＬｉｎｋＬｉｓｔｐ＝Ｌ－＞ｎｅｘｔ；ｗｈｉｌｅ（ｐ！＝ＮＵＬＬ） ｐｒｉｎｔｆ（＂％ｃ＂，ｐ－＞ｄａｔａ）；ｐ＝ｐ－＞ｎｅｘｔ；｝ｐｒｉｎｔｆ（＂＼ｎ＂）｝（６）取表元ＳｔａｔｕｓｔＥｍＬｉｎｋＬｉｓｔＬ，ｉｎｔｉ，ＥｌｅｍＴｙｐｅ｛ｐ＝Ｌ－＞ｎｅｘｔ；ｊ＝１；ｗｈｉｌｅ（ｐ＆＆ｊ＜ｉ）｛ｐ＝ｐ－＞ｎｅｘｔ；＋＋｝ｉｆ（?。穑辏荆椋颍澹簦酰颍睿牛遥遥希?；ｅ＝ｐ－＞ｄａｔａ；ｒｅｔｕｒｎ｝例，取第ｉ＝３個(gè)元素ｅ＝ｐ－＞ｄａｔａ＝Ｓｕｎ時(shí)間復(fù)雜度：Ｏ（ｎ）·在單鏈表第ｉ個(gè)結(jié)點(diǎn)前一個(gè)結(jié)點(diǎn)的過（７）ＳｔａｔｕｓＬｉｓｔＩｎｓｅｒｔ（ＬｉｎｋＬｉｓｔ＆Ｌ，ｉｎｔｉ，ＥｌｅｍＴｙｐｅ｛ｐ＝Ｌ；ｊ＝ｗｈｉｌｅ（ｐ＆＆ｊ＜ｉ－１）｛ｐ＝ｐ－＞ｎｅｘｔ；＋＋ｊ｝ｉｆ（！ｐ｜｜ｊ＞ｉ－１） ｒｅｔｕｒｎＥＲＲＯＲ；ｓ＝ （ＬｉｎｋＬｉｓｔ）ｃｓｉｚｅｏｆ（ＬＮｏｄｅ））；ｓ－＞ｄａｔａ＝ｅ；ｓ－＞ｎｅｘｔ＝ｐ－＞ｎｅｘｔ；ｐ－＞ｎｅｘｔ＝ｓ；ｒｅｔｕｒｎ｝·刪除單鏈表的第ｉ個(gè)結(jié)點(diǎn)的過（８）刪ＳｔａｔｕｓＬｉｓｔＤｅｌｅｔｅ（ＬｉｎｋＬｉｓｔＬｉｎｔｉ，ＥｌｅｍＴｙｐｅ｛ｐ＝Ｌ；ｊ＝ｗｈｉｌｅ（ｐ－＞ｎｅｘｔ＆＆ｊ＜ｉ－１）｛ｐ＝ｐ－＞ｎｅｘｔ；＋＋ｊ｝ｉｆ（?。ǎ穑荆睿澹簦辏荆椋保颍澹簦酰颍睿牛遥遥希?；ｒ＝ｐ－＞ｎｅｘｔ；ｅ＝ｒ－＞ｐ－＞ｎｅｘｔ＝ｐ－＞ｎｅｘｔ－ｎｅｘｔ；／／（ｐ－＞ｎｅｘｔ＝ｒ－＞ｎｅｘｔ；）ｆｒｅｅ（ｒ）；ｒｅｔｕｒｎＯＫ；｝·動態(tài)建立單鏈表的過（９）頭插法建ＣｒｅａｔｅＬｉｓｔＨ（ＬｉｎｋＬｉｓｔＬｉｎｔ｛Ｌ＝（ＬｉｎｋＬｉｓｔ）ｃｓｉｚｅｏｆ（ＬＮｏｄｅ））；Ｌ－＞ｎｅｘｔ＝ＮＵＬＬ；ｆｏｒ（ｉ＝ｎ；ｉ＞０；－－ｉ）ｓ＝（ＬｉｎｋＬｉｓｔ）ｃｓｉｚｅｏｆ（ＬＮｏｄｅ））；ｓｃａｎｆ（＆ｓ－＞ｄａｔａ）；ｓ－＞ｎｅｘｔ＝Ｌ－＞ｎｅｘｔ；Ｌ－＞ｎｅｘｔ＝ｓ；｝｝·法建（１０）法建ＣｒｅａｔｅＬｉｓｔＴ（ＬｉｎｋＬｉｓｔＬｉｎｔ｛ｔａｉｌ＝Ｌ＝（ＬｉｎｋＬｉｓｔ）ｃｓｉｚｅｏｆ（ＬＮｏｄｅ））；Ｌ－＞ｎｅｘｔ＝ＮＵＬＬ；ｆｏｒ（ｉ＝ｎ；ｉ＞０；－－ｉ）ｓ＝（ＬｉｎｋＬｉｓｔ）ｃｓｉｚｅｏｆ（ＬＮｏｄｅ））；ｓｃａｎｆ（＆ｓ－＞ｄａｔａ）；ｓ－＞ｎｅｘｔ＝ＮＵＬＬ；ｔａｉｌ－＞ｎｅｘｔ＝ｓ；①ｔａｉｌ＝ｓ；｝｝（１１）按元素值查找ａｔｅＥｍＬ，思路：在單鏈表Ｌ中從頭開始找第１個(gè)值域與ｅ相等的結(jié)點(diǎn)，若存在這樣的結(jié)點(diǎn)，則返回位置，否則返回０。ｉｎｔｏａｅＥｍＬｉｎｋＬｉｓｔＬ，ＥｌｅｍＴｙｐｅ｛ＬｉｎｋＬｉｓｔｐ＝Ｌ－＞ｎｅｘｔ；ｉｎｔｎ＝１；ｗｈｉｌｅ（ｐ?。剑危眨蹋蹋ΓΓ穑荆洌幔簦幔。?ｐ＝ｐ－＞ｎｅｘｔ；ｎ＋＋； ｉｆ（ｐ＝＝ＮＵＬＬ） ｒｅｔｕｒｎ（０）；ｅｌｓｅｒｅｔｕｒｎ（ｎ）｝練習(xí)：已知Ｌ是結(jié)點(diǎn)的非空單鏈表，指針ｐ所指的結(jié)點(diǎn)既不是第一個(gè)結(jié)點(diǎn)，也不是最后一個(gè)結(jié)點(diǎn)。刪除 ｐ結(jié)點(diǎn)的直接后繼結(jié)點(diǎn)的語句序列ｑ＝ｐ－＞ｎｅｘｔ；ｐ－＞ｎｅｘｔ＝ｑ－＞ｎｅｘｔ；ｆｒｅｅ（ｑ）；刪除 ｐ結(jié)點(diǎn)的直接前驅(qū)結(jié)點(diǎn)的語句序列ｑ＝Ｌ；ｗｈｉｌｅ（ｑ－＞ｎｅｘｔ－＞ｎｅｘｔ?。剑穑?ｑ＝ｑ－＞ｎｅｘｔ；ｓ＝ｑ－＞ｎｅｘｔ；ｑ－＞ｎｅｘｔ＝ｐ；ｆｒｅｅ（ｓ）；刪除 ｐ結(jié)點(diǎn)的語句序列ｑ＝Ｌ；ｗｈｉｌｅ（ｑ－＞ｎｅｘｔ?。剑穑?ｑ＝ｑ－＞ｎｅｘｔ；ｑ－＞ｎｅｘｔ＝ｐ－＞ｎｅｘｔ；ｆｒｅｅ（ｐ）刪除首元結(jié)點(diǎn)的語句序列ｑ＝Ｌ－＞ｎｅｘｔ；Ｌ－＞ｎｅｘｔ＝ｑ－＞ｎｅｘｔ；ｆｒｅｅ（ｑ）；刪除最后一個(gè)結(jié)點(diǎn)的語句序ｗｈｉｌｅ（ｐ－＞ｎｅｘｔ－＞ｎｅｘｔ?。剑危眨蹋蹋?ｐ＝ｐ－＞ｎｅｘｔ；ｑ＝ｐ－＞ｎｅｘｔ；ｐ－＞ｎｅｘｔ＝ＮＵＬＬ；ｆｒｅｅ（ｑ）；鏈?zhǔn)浇Y(jié)構(gòu)的特點(diǎn)非隨機(jī)存貯結(jié)構(gòu)，所以取表元素要慢于順序表。節(jié)約了大塊內(nèi)存適合于和刪除操實(shí)際上用空間換取了時(shí)間，結(jié)點(diǎn)中加入了指針，使得這兩種操作轉(zhuǎn)換為指針操作；２．靜態(tài)鏈表有些高級程序設(shè)計(jì)語言并沒有指針類型，如ＦＯＲＴＲＡＮ和ＪＡＶＡ。可以用數(shù)組來表示一個(gè)鏈表，稱為靜態(tài)鏈表。可定義如下＃ｄｅｆｉｎｅＭＡＸＳＩＺＥ ／／最多元素個(gè)數(shù)ｔｙｐｅｄｅｆｓｔｒｕｃｔ｛ＥｌｅｍＴｙｐｅ ｃｕｒ；／／游標(biāo)，指示｝ｐｅｎｔＳＬｉｎｋＬｉｓｔ［ＸＥｉ＝ｓ［ｉ］．ｃｕｒ；指針后移操ｌｃｉ＝ｓ［０］．ｃｕｒ；第一個(gè)可用結(jié)點(diǎn)位ｉｆ（ｓ［０］． ｓ［０］．ｃｕｒ＝ｓ［ｉ］． ／／ｋ結(jié)ｓ［ｋ］．ｃｕｒ＝ｓ［０］．ｃｕｒ；［０］．ｃｕｒ＝Ｉｎｓｅｒｔ：／／將ｉ插在ｒ之ｓ［ｉ］．ｃｕｒ＝ｓ［ｒ］．ｃｕｒ；ｓ［ｒ］．ｃｕｒ＝ｉ；Ｄｅｌｅｔｅ：；／／ｐ為ｋ的直接前驅(qū)，ｓ［ｐ］．ｃｕｒ＝ｓ［ｋ］．ｃｕｒＦｒｅｅ（ｋ）；單鏈表基礎(chǔ)要點(diǎn)在單鏈表中，不能從當(dāng)前結(jié)點(diǎn)出發(fā)到任一結(jié)點(diǎn)在單鏈表中，刪除某一指定結(jié)點(diǎn)時(shí)，必須找到該結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)線性表的鏈?zhǔn)浇Y(jié)構(gòu)是一種順序存取的結(jié)構(gòu)，不具有隨機(jī)任一元素的特點(diǎn)設(shè)置頭結(jié)點(diǎn)的作用：使在鏈表的第一個(gè)位置上的操作和表中其它位置上的操作—致，無需進(jìn)行特殊處理，對空表和非空表的處理。循環(huán)鏈表循環(huán)鏈表是另一種形式的鏈?zhǔn)浇Y(jié)構(gòu)可從當(dāng)前結(jié)點(diǎn)出發(fā)，到任一結(jié)點(diǎn)循環(huán)單鏈表多重循環(huán)鏈表。單循環(huán)鏈表設(shè)置尾指針ｒｅａｒ，比設(shè)頭指針更好連接兩個(gè)只設(shè)尾指針的單循環(huán)鏈表Ｌ１和Ｌ２操作如下：ｐ＝Ｒ１"＞ｎｅｘｔ；／／保存Ｌ１的頭結(jié)點(diǎn)指針Ｒ１－＞ｎｅｘｔ＝Ｒ２－＞ｎｅｘｔ－＞ｎｅｘｔ；／／頭尾連接ｆｒｅｅ（Ｒ２－＞ｎｅｘｔ）；／／第二個(gè)表的頭結(jié)Ｒ２－＞ｎｅｘｔ＝操作與線性單鏈表基本一致，差別只是在于算法中的循環(huán)結(jié)束條件不是ｐ是否為空，而是ｐ是否等于頭指針。例：取循環(huán)鏈表第ｉ個(gè)元素ＳｔａｔｕｓＧｅｔＥｌｅｍＬ（ ＆ｅ ｐ＝Ｌ－＞ｎｅｘｔ；ｊ＝１ｗｈｉｌｅ（ｐ！＝Ｌ＆＆ ｊ＜ｉ） ｐ＝ｐ－＞ｎｅｘｔ；＋＋ｊ；｝ｉｆ（ｐ＝＝Ｌ｜｜ｊ＞ｉ）ｒｅｔｕｒｎＥＲＲＯＲ；ｅ＝ｐ－＞ｄａｔａ；ｒｅｔｕｒｎ｝雙鏈表希望查找前驅(qū)的時(shí)間復(fù)雜度達(dá)到Ｏ（１），可以用空間換時(shí)間，每個(gè)結(jié)點(diǎn)再加一個(gè)指向前驅(qū)的指針域，使鏈表可以進(jìn)行雙方向查找。用這種結(jié)點(diǎn)結(jié)構(gòu)組成的鏈表稱為雙向鏈表。結(jié)點(diǎn)的結(jié)構(gòu)圖雙向鏈表的邏輯表示雙向鏈表（ＤｏｕｂｌｅＬｉｎｋｅｄＬｉｓｔ）類型描述ｔｙｐｅｄｅｆｓｔｒｕｃｔｓｔｒｕｃｔＤｕＬＮｏｄｅ

ｓｔｒｕｃｔ ｝ 雙向循環(huán)鏈ｐ－＞ｎｅｘｔ－＞ｐｒｉｏｒ＝ｐ－＞ｐｒｉｏｒ－＞·雙向鏈表的前（后 操①ｓ－＞ｐｒｉｏｒ＝ｐ－＞ ②ｐ－＞ｐｒｉｏｒ－＞ｎｅｘｔ＝③ｓ－＞ｎｅｘｔ＝ ④ｐ－＞ｐｒｉｏｒ＝①ｓ－＞ｎｅｘｔ＝ｑ－＞ ②ｑ－＞ｎｅｘｔ－＞ｐｒｉｏｒ＝③ｓ－＞ｐｒｉｏｒ＝ ④ｑ－＞ｎｅｘｔ＝雙向鏈表的刪除操①ｐ－＞ｐｒｉｏｒ－＞ｎｅｘｔ＝ｐ－＞②ｐ－＞ｎｅｘｔ－＞ｐｒｉｏｒ＝ｐ－＞刪除 ｐ的直接后繼結(jié)點(diǎn)的語句序列ｑ＝ｐ－＞ｎｅｘｔ；ｐ－＞ｎｅｘｔ＝ｐ－＞ｎｅｘｔ－＞ｎｅｘｔ；ｐ－＞ｎｅｘｔ－＞ｐｒｉｏｒ＝ｐ；ｆｒｅｅ（ｑ）刪除 ｐ的直接前驅(qū)結(jié)點(diǎn)的語句序列ｑ＝ｐ－＞ｐｒｉｏｒ；ｐ－＞ｐｒｉｏｒ＝ｐ－＞ｐｒｉｏｒ－＞ｐｒｉｏｒ；ｐ－＞ｐｒｉｏｒ－＞ｎｅｘｔ＝ｐ；ｆｒｅｅ（ｑ）《《數(shù)據(jù)結(jié)構(gòu)》考研考點(diǎn)精講及復(fù)習(xí)思ｒｅｔｕｒｎ｝②找結(jié)點(diǎn)的中序后繼結(jié)結(jié)點(diǎn)ｐ，無右孩子，右指針指向其后繼，否則ｐ的右子樹中“最左下”結(jié)點(diǎn)。ＢｉＴｈｒＴｒｅｅＰｏｓｔＮｏｄｅ（ＢｉＴｈｒＴｒｅｅｐ）｛ｐｏｓｔ＝ｐ－＞ｉｆ（ｐ－＞ＲＴａｇ＝＝０）／／有右孩子ｗｈｉｌｅ（ｐｏｓｔ－＞ＬＴａｇ＝＝０）ｐｏｓｔ＝ｐｏｓｔ－＞ｌｃｈｉｌｄ；ｒｅｔｕｒｎ｝結(jié)點(diǎn)的線索二叉鏈表結(jié)點(diǎn)的中序線索二叉鏈表中序遍歷線索二叉樹 ／／０：有孩子；１：無孩子ＶｏｉｄＩｎＯｒｄｅｒＴｒａｖｅｒｓｅＴｈｒ（ＢｉＴｈｒＴｒｅｅ ｛ｐ＝Ｔ－＞ｌｃｈｉｌｄ；ｗｈｉｌｅ（ｐ?。剑裕鳎瑁椋欤澹ǎ穑荆蹋裕幔纾剑剑埃穑剑穑荆欤悖瑁椋欤?；ｃｏｕｔ＜＜ｐ－＞ｄａｔａ＜＜“”；ｗｈｉｌｅ（（ｐ－＞ＲＴａｇ＝＝１）＆＆（ｐ－＞ｒｃｈｉｌｄ！＝Ｔ） ｐ＝ｐ－＞ｒｃｈｉｌｄ；ｃｏｕｔ＜＜ｐ－＞ｄａｔａ＜＜“”；｝ｐ＝ｐ－＞｝｝建立線索化鏈表（以中序?yàn)槔茨撤N次序?qū)⒍骀湵砭€索化，實(shí)質(zhì)是在遍歷過程中用線索取代空指針對線索樹進(jìn)行遍歷，顯然其效率要比傳統(tǒng)方式高些。如果程序中經(jīng)常要進(jìn)行二叉樹的遍歷或者需要查找在遍歷過程中所的線性序列中前驅(qū)和后繼，此時(shí)應(yīng)當(dāng)采用線索鏈表表示。６． 樹和森１．樹的結(jié)構(gòu)（三種方法雙親表示法：用一組連續(xù)的空間來樹中的結(jié)點(diǎn)，在保存每個(gè)結(jié)點(diǎn)的同時(shí)附設(shè)一個(gè)指示器來指示其雙親結(jié)點(diǎn)在表中的位置，其結(jié)點(diǎn)的結(jié)構(gòu)如下：樹的雙親結(jié)構(gòu)示意＃ｄｅｆｉｎｅＭＡＸＴＲＥＥＳＩＺＥ１００ｔｙｐｅｄｅｆｓｔｒｕｃｔＰＴＮｏｄｅ｛ＴＥｌｅｍ ｝ＰＴＮｏｄｅ；Ｔｙｐｅｄｅｆｓｔｒｕｃｔ｛ＰＴＮｏｄｅｎｏｄｅｓ［ＭＡＸＴＲＥＥＳＩＺＥ］ ｒ， ／／根的位置和結(jié)點(diǎn)｝雙親表示法的類型說明孩子表示法①定長結(jié)點(diǎn)長空鏈域個(gè)數(shù)：ｎｋ"（ｎ）＝ｎ（ｋ－１）＋②把每個(gè)結(jié)點(diǎn)的孩子結(jié)點(diǎn)排列起來，構(gòu)成一個(gè)單鏈表，稱為孩子鏈表。ｎ個(gè)結(jié)點(diǎn)共有ｎ個(gè)孩子鏈表（葉子結(jié)點(diǎn)的孩子鏈表為空表），而ｎ個(gè)結(jié)點(diǎn)的數(shù)據(jù)和ｎ個(gè)孩子鏈表的頭指針又組成一個(gè)順序表ｔｙｐｅｄｅｆｓｔｒｕｃｔＣＴＮｏｄｅ｛／孩子結(jié)點(diǎn)的定義 ｓｔｒｕｃｔＣＴＮｏｄｅ｝

該孩子結(jié)點(diǎn)性表中的位置／ｔｙｐｅｄｅｆｓｔｒｕｃｔ｛ＴＥｌｅｍＴｙｐｅｄａｔａ；

／順序表結(jié)點(diǎn)的結(jié)構(gòu)定 指 結(jié)點(diǎn)的信息指 ＦｉｒｓｔＣｈｉｌｄ；｝

向孩子鏈表的頭指 樹ｔｙｐｅｄｅｆｓｔｒｕｃｔ｛ 的定 樹順 ｎｏｄｅｓ［ＭＡＸＴＲＥＥＳＩＺＥ］； 序 順根ｉｎｔｒｏｏｔ，ｎｕｍ；根／｝結(jié)孩子兄弟表示法ｔｙｐｅｄｅｆｓｔｒｕｃｔＣＳＮｏｄｅ｛ＥｌｅｍＴｙｐｅｄａｔａ； 結(jié)

結(jié)點(diǎn)的位置和樹的結(jié)點(diǎn)個(gè)數(shù)第點(diǎn)信 第ＳｔｒｕｃｔＣＳＮｏｄｅＦｉｒｓｔＣｈｉｌｄ，ＮｅｘｔＳｉｂｌｉｎｇ；｝

—個(gè)孩子，下一個(gè)兄弟樹樹的孩子兄弟結(jié)構(gòu)示意２．樹、森林與二叉樹的相互轉(zhuǎn)·樹轉(zhuǎn)換為二叉（１）在所有相鄰兄弟結(jié)點(diǎn)之間加一水平連線（２）對每個(gè)非葉結(jié)點(diǎn)ｋ，除了其最左邊的孩子結(jié)點(diǎn)外，刪去ｋ與其他孩子結(jié)點(diǎn)的連線（３）所有水平線段以左邊結(jié)點(diǎn)為順時(shí)針旋轉(zhuǎn)４５度，使之結(jié)構(gòu)層次分明。樹做這樣的轉(zhuǎn)換所構(gòu)成的二叉樹是唯一的。樹與二叉樹的對·森林轉(zhuǎn)換為二叉森林也可以方便地用孩子兄弟鏈表表示。森林轉(zhuǎn)換為二叉樹的方法如下（１）將森林中的每棵樹轉(zhuǎn)換成相應(yīng)的二叉樹（２）第一棵二叉樹不動，從第二棵二叉樹開始，依次把后一棵二叉樹的根結(jié)點(diǎn)作為前一棵二叉樹根結(jié)點(diǎn)的右孩子，當(dāng)所有二叉樹連在一起后，所得到的二叉樹就是由森林轉(zhuǎn)換得到的二叉樹。·二叉樹還原為樹或森將一棵二叉樹還原為樹或森林，具體方法如下《《數(shù)據(jù)結(jié)構(gòu)》考研考點(diǎn)精講及復(fù)習(xí)思（１）若某結(jié)點(diǎn)是其雙親的左孩子，則把該結(jié)點(diǎn)的右孩子、右孩子的右孩子……都與該結(jié)點(diǎn)的雙親結(jié)點(diǎn)用線連起來。（２）刪掉原二叉樹中所有雙親結(jié)點(diǎn)與右孩子結(jié)點(diǎn)的連線（３）整理由（１）、（２）兩步所得到的樹或森林，使之結(jié)構(gòu)層次分明二叉樹到森林的轉(zhuǎn)換示３．樹與森林的遍·樹的遍歷（兩種１）先根遍若樹非空，則遍歷方法為①根結(jié)點(diǎn)②從左到右，依次先根遍歷根結(jié)點(diǎn)的每一棵子樹。等同于轉(zhuǎn)換的二叉樹進(jìn)行先序遍歷先根遍歷序列ＡＢＥＣＦＨＧＤ２）后根遍歷若樹非空，則遍歷方法為①從左到右，依次后根遍歷根結(jié)點(diǎn)的每一棵子樹②根結(jié)點(diǎn)等同于轉(zhuǎn)換的二叉樹進(jìn)行中序遍歷后根遍歷序列為ＥＢＨＦＧＣＤＡ·森林的遍歷（２種１）中序遍若森林非空，則遍歷方法為①森林中第一棵樹的根結(jié)點(diǎn)②先序遍歷第一棵樹的根結(jié)點(diǎn)的子樹森林③先序遍歷除去第一棵樹之后剩余的樹構(gòu)成的森林。先序遍歷序列為ＡＢＣＤＥＦＧＨＩＪ等同于轉(zhuǎn)換的二叉樹進(jìn)行先序遍歷２）先序遍歷若森林非空，則遍歷方法為①中序遍歷森林中第一棵樹的根結(jié)點(diǎn)的子樹森林②第一棵樹的根結(jié)點(diǎn)③中序遍歷除去第一棵樹之后剩余的樹構(gòu)成的森林。中序遍歷序列為 等同于轉(zhuǎn)換的二叉樹進(jìn)行中序遍歷４．幾個(gè)問題①給定樹的先根遍歷序列和后根遍歷序列可唯一畫出一棵樹。先根遍歷序列：ＡＢＥＣＦＨＧＤ后根遍歷序列：ＥＢＨＦＧＣＤ②給定森林的先序遍歷序列和中序遍歷序列可唯一確定一森林。先序遍歷序列：ＡＢＣＤＥＦＧＨＩＪ中序遍歷序列：ＢＣＤＡＦＥＨＪＩ③關(guān)于二叉樹的先序、中序和后序遍歷序列確定二叉樹的問題·任何ｎ（ｎ０個(gè)不同結(jié)點(diǎn)的二叉樹，都可由它的中序序列和先序序列唯一地確定證明先序序列是ａ１ａ２…ａｎ中序序列是ｂ１ｂ２…ｂｎ根結(jié)點(diǎn)：ａ在中序序列中與ａ同的結(jié)點(diǎn)為：ｂｊ｛ｂ１…ｂｊ－１｝ｂｊ｛ｂｊ＋１…ｂｎ｝←→ａ１｛ａ２…ａｋ｝｛ａｋ＋１…ａｎ例已知先序序列為ＡＢＤＧＣＥＦ，中序序列為·任何ｎ（ｎ＞０）個(gè)不同結(jié)點(diǎn)的二叉樹，都可由它的中序序列和后序序列唯一地確定。證明：后序序列是ａ１ａ２…ａｎ中序序列是ｂ１ｂ２…ｂｎ根結(jié)點(diǎn)：ａｎ在中序序列中與ａｎ同的結(jié)點(diǎn)為：ｂｊ｛ｂ１…ｂｊ－１｝ｂｊ｛ｂｊ＋１…ｂｎ｝←→ａ１ａ２…ａｋ｝｛ａｋ＋１…ａｎ－１｝ａｎ例后序序列為ＧＤＢＥＦＣＡ，中序序列為ＤＧＢＡＥＣＦ６．５樹與等價(jià)問離散數(shù)學(xué)中的定等價(jià)關(guān)系：若集合Ｓ中的關(guān)系Ｒ是自反的、對稱的和傳遞的，則稱為等價(jià)關(guān)系等價(jià)類：Ｒ是集合Ｓ的等價(jià)關(guān)系，由［ｘ］Ｒ＝｛ｙ｜ｙ∈Ｓ∧ｙ給出的集合［ｘ］Ｒ稱為由ｘ生成的一個(gè)Ｒ等價(jià)類。劃分：Ｒ是Ｓ上的等價(jià)關(guān)系，可以按Ｒ將Ｓ劃分為若干不相交的子集……，它們的并即為Ｓ，則這些子集Ｓｉ是Ｓ的Ｒ等價(jià)類。如何劃分等價(jià)類假設(shè)集合Ｓ有ｎ個(gè)元素，ｍ個(gè)形如（ｘ，ｙ）的等價(jià)偶對確定了等價(jià)關(guān)系Ｒ，求Ｓ的劃分。一種算法：１）令Ｓ中每個(gè)元素各自形成一個(gè)只含單個(gè)成員的子集，記為…，Ｓｎ２）重復(fù)讀入ｍ個(gè)偶對，對每個(gè)偶對（ｘ，ｙ），判斷ｘ和ｙ所屬的子集，設(shè)ｘ∈Ｓ，ｙ∈Ｓ，若ＳｉＳ，則將Ｓｊ入Ｓｉ并置Ｓｊ空。處理完ｍ個(gè)偶對后剩下的非空子集就是Ｓ的Ｒ等價(jià)類。劃分等價(jià)類需要的操作：１）構(gòu)造只含單個(gè)元素的集合２）判定某個(gè)元素所屬集合３）合并兩個(gè)互不相交的集ＦＳｔ若Ｓ是ＦＳｅ類型的集合，則它由子集Ｓｉ構(gòu)成，∪…Ｓ＝Ｓ。基本操作：Ｉｎｉｔｉａｌ（＆Ｓ，ｎ，ｘ１，ｘ…，ｘｎ）：構(gòu)造由ｎ個(gè)子集構(gòu)成的集合Ｓ，每個(gè)子集只含單個(gè)元素。Ｆｉｎｄ（Ｓ，ｘ）：查找ｘ所屬的子集Ｓｉｅｅ＆Ｓ，ｉ，ｊ）：合并兩個(gè)不相交的集合ＳｉＳｊｅ類型的實(shí)現(xiàn)根據(jù)Ｆｉｎｄ和Ｍｅｒｇｅ兩個(gè)操作的特點(diǎn)，用樹來實(shí)現(xiàn)Ｓｅｔ以森林Ｆ＝（…，Ｔｎ）表示Ｓｅ類型的集合Ｓ，每顆樹Ｔｉ示一個(gè)子集Ｓｉ樹中每個(gè)結(jié)點(diǎn)表示子集中的一個(gè)成員ｘ令每個(gè)結(jié)點(diǎn)中包含一個(gè)指向其雙親的指針約定根結(jié)點(diǎn)兼作子集的名稱集合的合并將一棵樹的根指向另一顆樹的根＃ｄｅｆｉｎｅＭＡＸＴＲＥＥＳＩＺＥ１００ｔｙｐｅｄｅｆｓｔｒｕｃｔＰＴＮｏｄｅ｛ＴＥｌ ｝ＰＴＮｏｄｅ；Ｔｙｐｅｄｅｆｓｔｒｕｃｔ｛ＰＴＮｏｄｅｎｏｄｅｓ［ＭＡＸＴＲＥＥＳＩＺＥ］；ｉｎｔｒ，ｎ； ／／根的位置和結(jié)點(diǎn)數(shù)｝ＴｙｐｅｄｅｆＰＴｒｅｅＳｔｉｎｔｆｉｎｄｍｆｓｅｔ（ＭＦＳｅｔＳ，ｉｎｔ｛ｉｆ（ｉ＜１｜｜ｉ＞Ｓ．ｎ）ｒｅｔｕｒｎ－ｆｏｒ（ｊ＝ｉ；Ｓ．ｎｏｄｅｓ［ｊ］．ｐａｒｅｎｔ＞０；ｊ＝Ｓ．ｎｏｄｅ［ｊ］． ｒｅｔｕｒｎ｝Ｓｔａｔｕｓｍｅｒｇｅｍｆｓｅｔ（ＭＦＳｅｔＳｉｎｔｉ，ｉｎｔ｛ｉｆ（ｉ＜１｜｜ｉ＞Ｓ．ｎ｜｜ｊ＜１｜｜ｊ＞Ｓ．ｎ）ｒｅｔｕｒｎＥＲＲＯＲ；Ｓ．ｎｏｄｅ［ｉ］．ｐａｒｅｎｔ＝ｊ；ｒｅｔｕｒｎ｝時(shí)間復(fù)雜度分別為Ｏ（ｄ）和Ｏ（１），ｄ為樹的深（７）掌握線索二叉樹的概念和相關(guān)算法的實(shí)現(xiàn)（８）掌握哈夫曼樹的定義、哈夫曼樹的構(gòu)造過程和哈夫曼編碼產(chǎn)生方法（９）靈活運(yùn)用二叉樹這種數(shù)據(jù)結(jié)構(gòu)解決一些綜合應(yīng)用問題二、舉１．已知一棵二叉樹的前序遍歷結(jié)果為ＡＢＣＤＥＦ，中序遍歷結(jié)果為ＣＢＡＥＤＦ，則后序遍歷的結(jié)果 ）【浙江大學(xué)Ａ． Ｂ． Ｃ． Ｄ．不２．已知某二叉樹的后序遍歷序列是ｄａｂｅｃ，中序遍歷序列是ｄｅｂａｃ，它的前序遍歷是（ 大學(xué)】Ａ． Ｂ． Ｃ． Ｄ．３．一棵左子樹為空的二叉樹在先序線索化后，其中空的鏈域的個(gè)數(shù)是（ ）【合肥工業(yè)大學(xué)】Ａ．不確定 Ｂ．０ Ｃ．１ Ｄ．２４．若Ｘ是二叉中序線索樹中一個(gè)有左孩子的結(jié)點(diǎn)，且Ｘ不為根，則Ｘ的前驅(qū)為（ 大學(xué)】Ａ．Ｘ的雙 Ｂ．Ｘ的右子樹中最左的結(jié)Ｃ．Ｘ的左子樹中最右結(jié) Ｄ．Ｘ的左子樹中最右葉節(jié)５．設(shè)Ｆ是一個(gè)森林，Ｂ是由Ｆ變換得的二叉樹。若Ｆ中有ｎ個(gè)非終端結(jié)點(diǎn)，則Ｂ中右指針域?yàn)榭盏慕Y(jié)點(diǎn)有（ ）個(gè)?！疚靼搽娮涌萍即髮W(xué)】Ａ．ｎ－ Ｂ． Ｃ．ｎ＋ Ｄ．ｎ＋三、本講小線索二叉樹的概念和相關(guān)算法的實(shí)現(xiàn)。樹、森林與二叉樹的關(guān)系樹的簡單應(yīng)第３~、考點(diǎn)講情況：改進(jìn)方法Ｍｅｒｇｅ時(shí)，總是將成員少的子集根結(jié)點(diǎn)指向含成員多的子集的修改結(jié)構(gòu)，令根結(jié)點(diǎn)的ｐａｒｅｎｔ域子集中所含成員數(shù)目的負(fù)可以將ｆｉｎｄｍｆｓｅｔ的復(fù)雜度降到Ｏ（ｌｏｇｎ）Ｓｔａｔｕｓｍｉｘｍｆｓｅｔ（ｅＳｉｎｔｉ，ｉｎｔｊ）｛ｉｆ（ｉ＜１｜｜ｉ＞Ｓ．ｎ｜｜ｊ＜１｜｜ｊ＞Ｓ．ｎ）ｒｅｔｕｒｎｉｆ（Ｓ．ｎｏｄｅｓ［ｉ］．ｐａｒｅｎｔ＞Ｓ．ｎｏｄｅｓ［ｊ］．ｐａｒｅｎｔ）｛Ｓ．ｎｏｄｅｓ［ｊ］．ｐａｒｅｎｔ＋＝Ｓ．ｎｏｄｅｓ［ｉ］．ｐａｒｅｎｔ；Ｓ．ｎｏｄｅｓ［ｉ］．ｐａｒｅｎｔ＝｝Ｓ．ｎｏｄｅｓ［ｉ］．ｐａｒｅｎｔ＋＝Ｓ．ｎｏｄｅｓ［ｊ］．ｐａｒｅｎｔ；Ｓ．ｎｏｄｅｓ［ｊ］．ｐａｒｅｎｔ＝ｉ；｝ｒｅｔｕｒｎ｝進(jìn)一步的改進(jìn)：Ｆｉｎｄ時(shí)壓縮路當(dāng)所查元素不在第二層時(shí)，將所有從根到該元素路徑上的元素都變成根結(jié)點(diǎn)的孩子ｉｎｔｆｉｘｍｆｓｅｔ（ＭＦＳｅｔＳｉｎｔｉ）｛ｉｆ（ｉ＜１｜｜ｉ＞Ｓ．ｎ）ｒｅｔｕｒｎ－ｆｏｒ（ｊ＝ｉ；Ｓ．ｎｏｄｅｓ［ｊ］．ｐａｒｅｎｔ＞０；ｊ＝Ｓ．ｎｏｄｅ［ｊ］．ｐａｒｅｎｔ） ｆｏｒ（ｋ＝ｉ；ｋ！ ＝ｊ；ｋ＝ｔ）｛ｔ＝Ｓ．ｎｏｄｅｓ［ｋ］． Ｓ．ｎｏｄｅｓ［ｋ］．ｐａｒｅｎｔ＝｝ｒｅｔｕｒｎ｝６．６ 哈夫曼樹及其應(yīng)用１．哈夫曼樹①路徑長從樹中一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)之間的分支構(gòu)成這兩個(gè)結(jié)點(diǎn)之間的路徑，路徑上的分支數(shù)目稱做路徑長度。②樹的路徑長從樹根到每一結(jié)點(diǎn)的路徑長度之和③結(jié)點(diǎn)的權(quán)和帶權(quán)路徑長給樹的每個(gè)結(jié)點(diǎn)賦予一個(gè)具有某種實(shí)際意義的實(shí)數(shù)，稱該實(shí)數(shù)為這個(gè)結(jié)點(diǎn)的權(quán)。在樹形結(jié)構(gòu)中，把從樹根到某一結(jié)點(diǎn)的路徑長度與該結(jié)點(diǎn)的權(quán)的乘積，叫做該結(jié)點(diǎn)的帶權(quán)路徑長度。④樹的帶權(quán)路徑長度ＷＰＬ（ＷｅｉｇｈｔＰａｔｈＬｅｎｇｔｈｏｆＴｒｅｅ）樹中所有葉子結(jié)點(diǎn)的帶權(quán)路徑長度之和，通常記為：ｗｎ∑ＷＰＬｗｎ∑ｋ１ｋＬａ）＝７×２＋５×２＋２×２＋４×２＝３６Ｌｂ）＝４×２＋７×３＋５×３＋２×１＝４６Ｌｃ）＝７×１＋５×２＋２×３＋４×３＝３５⑤哈夫曼樹（最優(yōu)二叉樹設(shè)二叉樹具有ｎ個(gè)帶權(quán)值的葉子結(jié)點(diǎn)，那么從根結(jié)點(diǎn)到各個(gè)葉子結(jié)點(diǎn)的路徑長度與相應(yīng)結(jié)點(diǎn)權(quán)值的乘積的和，叫做二叉樹的帶權(quán)路徑長度。具有最小帶權(quán)路徑長度的二叉樹稱為哈夫曼樹２．構(gòu)造哈夫曼樹（哈夫曼算法１）由給定的ｎ個(gè)權(quán)值｛．．．，Ｗｎ｝，構(gòu)造ｎ棵只有一個(gè)葉子結(jié)點(diǎn)的二叉樹，從而得到一個(gè)二２）在Ｆ中選取根結(jié)點(diǎn)的權(quán)值最小和次小的兩棵二叉樹作為左、右子樹構(gòu)造一棵新的二叉樹，這棵新的二叉樹根結(jié)點(diǎn)的權(quán)值為其左、右子樹根結(jié)點(diǎn)權(quán)值之和；３）在集合Ｆ中刪除作為左、右子樹的兩棵二叉樹，并將新建立的二叉樹加入到集合Ｆ中；４）重復(fù)（２）、（３）兩步，當(dāng)Ｆ中只剩下一棵二叉樹時(shí)，這棵二叉樹便是所要建立的哈夫曼樹。給定權(quán)值ｗ＝（１，３，５，７）來構(gòu)造一棵哈夫曼樹３．哈夫曼編碼１）編碼例，傳送ＡＢＡＣＣＤ，四種字符，可以分別編碼為００，０１，１０，１１。則原電文轉(zhuǎn)換為０００１００１０１０１１。對方接收后，采用二位一分進(jìn)行譯碼當(dāng)然，為電文編碼時(shí)，總是希望總長越短越好如果對每個(gè)字符設(shè)計(jì)長度不等的編碼，且讓電文中出現(xiàn)次數(shù)較多的字符