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

／學(xué)生的指針學(xué)生表構(gòu)成的鏈表如下圖所示。其中的ｈｅａｄ為第一個(gè)數(shù)據(jù)元素的指針鏈?zhǔn)酱鎯?chǔ)法的缺點(diǎn)存儲(chǔ)空間占用無(wú)法隨機(jī)訪８式式存儲(chǔ)法的優(yōu)點(diǎn)便于修改（插入、刪除、移動(dòng)３．算（１）算法（Ａｌｇｏｒｉｔｈｍ）的定Ａｌｇｏｒｉｔｈｍｉｓａｆｉｎｉｔｅｓｅｔｏｆｒｕｌｅｓｗｈｉｃｈｇｉｖｅｓａｓｅｑｕｅｎｃｅｏｆｏｐｅｒａｔｉｏｎｆｏｒｓｏｌｖｉｎｇａｓｐｅｃｉｆｉｃｔｙｐｅｏｆｐｒｏｂｌｅｍ．（算法是規(guī)則的有限集合，是為解決特定問(wèn)題而規(guī)定的一系列操作。）（２）算法的特①有窮性：有限步驟之內(nèi)正常結(jié)束，不能形成無(wú)窮循環(huán)②確定性：算法中的每一個(gè)步驟必須有確定含義，無(wú)二義性③可行性：原則上能精確進(jìn)行，操作可通過(guò)已實(shí)現(xiàn)的基本運(yùn)算執(zhí)行有限次而完成④輸入：有多個(gè)或０個(gè)輸入⑤輸出：至少有一個(gè)或多個(gè)輸出在算法的五大特性中，最基本的是有限性、確定性和可行性。４．算法描述的工具描述算法的方自然語(yǔ)言：優(yōu) 簡(jiǎn)單。缺 有歧異，表達(dá)復(fù)雜思想不明晰，不能和實(shí)現(xiàn)方式很好結(jié)高級(jí)程序設(shè)計(jì)語(yǔ)言，如Ｐａｓｃａｌ，Ｃ／Ｃ＋＋，Ｊａｖａ等。優(yōu)點(diǎn) 克服了自然語(yǔ)言的缺點(diǎn)，可直接執(zhí)行。缺點(diǎn) 對(duì)部分問(wèn)題的描述比較煩雜， 類語(yǔ)言。和高級(jí)程序設(shè)計(jì)語(yǔ)言類似，但是對(duì)其中一些比較煩雜的部分進(jìn)行和簡(jiǎn)化（原因：類主要目的是為了清晰的表述思想舉例：兩個(gè)數(shù)據(jù)ａ，ｂ交換空舉自然語(yǔ)言：交換ａ，ｂ的存儲(chǔ)空間高級(jí)語(yǔ)言：｛ｘ＝ａ；ａ＝ｂ；ｂ＝ｘ；｝類語(yǔ)言：ａｂ；／／交換空間５．對(duì)算法作性能評(píng)衡量算法效率的方法主要有兩大類事后統(tǒng)計(jì)：利用計(jì)算機(jī)的時(shí)鐘事前分析估算：用高級(jí)語(yǔ)言編寫的程序運(yùn)行的時(shí)間主要取決于如下因素：算法；問(wèn)題規(guī)模使用語(yǔ)言：級(jí)別越高，效率越低；編譯程序；機(jī)器通常，從算法中選取一種對(duì)于研究的問(wèn)題來(lái)說(shuō)是基本操作的原操作，以該基本操作重復(fù)執(zhí)行的次數(shù)作為算法執(zhí)行的時(shí)間度量。基本操作重復(fù)執(zhí)行的次數(shù)分別為１，ｎ，９設(shè)算法的問(wèn)題規(guī)模為頻度：語(yǔ)句重復(fù)執(zhí)行的次數(shù)稱為該語(yǔ)句的頻度，記ｆ（ｎ）對(duì)算法各基本操作的頻度求和，便可得算法的時(shí)間復(fù)雜度。但實(shí)際中我們所關(guān)心的主要是一個(gè)算法所花時(shí)間的數(shù)量級(jí)，即取算法各基本操作的最大頻度數(shù)量級(jí)。時(shí)間復(fù)雜度：算法執(zhí)行時(shí)間度量，記Ｔ（ｎ）＝Ｏ（ａｘｌｅｖｅｌｆ（ｎ）））。ｆ（ｎ）＝１＋ｎ＋ｎ２＋ｎ３Ｔ（ｎ）＝Ｏ（ｎ３）Ｏ的數(shù)學(xué)定義：若Ｔ（ｎ）和ｆ（ｎ）是定義在正整數(shù)集合上的兩個(gè)函數(shù)，則如果存在正常數(shù)Ｃ和ｎ得當(dāng)ｎ≥時(shí)，總滿足０Ｔｎ）≤Ｃｆｎ），則記做Ｔ（ｎ）＝Ｏ（ｆ（ｎ））也就是只求出Ｔ（ｎ）的最高階（數(shù)量級(jí)），忽略其低階項(xiàng)和常系數(shù)，這樣既可簡(jiǎn)化Ｔ（ｎ）的計(jì)算，能比較客觀地反映出當(dāng)ｎ很大時(shí)，算法的時(shí)間性能。６．算法的空間復(fù)雜度關(guān)于算法的存儲(chǔ)空間需求，類似于算法的時(shí)間復(fù)雜度，我們采用空間復(fù)雜度作為算法所需存儲(chǔ)空間的量度，記作：Ｓ（ｎ）＝Ｏ（ｆ（ｎ）三、真題舉１．從邏輯結(jié)構(gòu)上可以把數(shù)據(jù)結(jié)構(gòu)分為（ ）兩大類．【武漢交通科技大學(xué)】Ａ．動(dòng)態(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é)２．在下面的程序段中，對(duì)ｘ的賦值語(yǔ)句的頻度為（ ）【北京工商大學(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)算［一般了解］２．２線性表的順序存儲(chǔ)［熟練掌握］２．３線性表的鏈?zhǔn)酱鎯?chǔ)［熟練掌握］第１~、考試分考重點(diǎn)與難考中常見(jiàn)題復(fù)習(xí)思路與方線性表的基本概念和常用線性表在常用操作、性表選擇題、２．掌握線性表的順序存操作、線性表的順序存儲(chǔ)方式?的順序存儲(chǔ)?綜合分析題儲(chǔ)式和線性表的基本運(yùn)算在現(xiàn)行存方式下的實(shí)現(xiàn)方法?二、考點(diǎn)講２．１ 線性表的概念及運(yùn)算１．線性表的定義—個(gè)線性表是具有ｎ個(gè)數(shù)據(jù)元素的有限序列。記為（ａ１，…，ａｉａｉａｉ…，ａｎ２．線性表的長(zhǎng)線性表中元素的個(gè)數(shù)ｎ（ｎ＞＝０），ｎ＝０時(shí)，稱為空表。３．位序ａｉ第ｉ個(gè)元素，稱ｉ為數(shù)據(jù)元素ａｉ在線性表中的位序。４．線性表的邏輯結(jié)構(gòu)例子·英文字母表（Ａ，Ｂ，…，Ｚ）車輛登記表５．線性表的特同一性：線性表由同類數(shù)據(jù)元素組成，每一個(gè)ａｉ須屬于同一數(shù)據(jù)對(duì)象有窮性：線性表由有限個(gè)數(shù)據(jù)元素組成，表長(zhǎng)度就是表中數(shù)據(jù)元素的個(gè)數(shù)有序性：線性表中相鄰數(shù)據(jù)元素之間存在著序偶關(guān)系＜ａｉａｉ＞。６．線性表的基本運(yùn)算初始化ＩｎｉｔＬｉｓｔ（Ｌ建立一個(gè)空表求表長(zhǎng)ＬｉｓｔＬｅｎｇｔｈ（Ｌ）返回線性表的長(zhǎng)度讀表元素ｅｔＥｍＬ，ｉ，ｅ用ｅ返回Ｌ中第ｉ個(gè)數(shù)據(jù)元素的值定位ＬａｅＥｌｅｍＬ，ｅ，ｃｍｅ））返回滿足關(guān)系的數(shù)據(jù)元素的位序插入ＬｉｓｔＩｎｓｅｒｔ（Ｌｉ，ｅ）在Ｌ中第ｉ個(gè)位置之前插入新的數(shù)據(jù)元素ｅ，線性表的長(zhǎng)度增１刪除ＬｉｓｔＤｅｌｅｔｅ（Ｌｉ，＆ｅ）刪除Ｌ的第ｉ個(gè)位置上的數(shù)據(jù)元素ｅ，線性表的長(zhǎng)度減１輸出ＬｉｓｔＤｉｓｐｌａｙ（Ｌ）按前后次序輸出線性表的所有元素練習(xí)１：兩個(gè)線性表ＬＡ和ＬＢ分別表示兩個(gè)集合Ａ和Ｂ，現(xiàn)求一個(gè)新的集合Ａ＝∪Ｂ。ｖｏｉｄｕｎｉｏｎ（ＬｉｓｔａＬｉｓｔＬｂ）｛Ｌａｌｅｎ＝ＬｉｓｔＬｅｎｇｔｈ（Ｌａ）；Ｌｂｌｅｎ＝ＬｉｓｔＬｅｎｇｔｈ（Ｌｂ）ｆｏｒ（ｉ＝１；ｉ＜＝Ｌｂｌｅｎ；ｉ＋＋）｛ｔＥｍＬｂ，ｉ，ｅ）；ｉｆ（?。幔澹牛恚蹋?，ｅ，ｅｑｕａｌ））ＬｉｓｔＩｎｓｅｒｔ（Ｌａ，＋＋Ｌａｌｅｎ，ｅ）；｝｝練習(xí)

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

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

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

｝／／

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

建頭結(jié)（２）銷毀線性表ＤｅｓｔｒｏｙＬｉｓｔ（釋放單鏈表Ｌ占用的內(nèi)存空間。即逐一釋放全部結(jié)點(diǎn)的空間ｖｏｉｄｖｏｉｄＤｅｓｔｒｏｙＬｉｓｔ（ＬｉｎｋＬｉｓｔ｛ＬｉｎｋＬｉｓｔｐ＝Ｌ，ｑ＝ｐ－＞ｗｈｉｌｅ（ ＝ ｆｒｅｅ（ｐ）ｐ＝ｑ；ｑ＝ｐ－＞｝ｆｒｅｅ（ｐ）｝（３）判線性表是否為空表ＬｉｓｔＥｍｐｔｙ（若單鏈表Ｌ沒(méi)有數(shù)據(jù)結(jié)點(diǎn)，則返回真，否則返回假。ｉｎｔＬｉｓｔＥｍｐｔｙ（ＬｉｎｋＬｉｓｔＬ）｛ｒｅｔｕｒｎ（Ｌ－＞ｎｅｘｔ＝＝ＮＵＬＬ）｝（４）求線性表的長(zhǎng)度ＬｉｓｔＬｅｎｇｔｈ（Ｌ）返回單鏈表Ｌ中數(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)的過(guò)（７）插ＳｔａｔｕｓＬｉｓｔＩｎｓｅｒｔ（ＬｉｎｋＬｉｓｔ＆Ｌ，ｉｎｔｉ，ＥｌｅｍＴｙｐｅ｛ｐ＝Ｌ；ｊ＝ｗｈｉｌｅ（ｐ＆＆ｊ＜ｉ－１）｛ｐ＝ｐ－＞ｎｅｘｔ；＋＋ｊ｝ｉｆ（?。穑辏荆椋保?ｒｅｔｕｒｎＥＲＲＯＲ；ｓ＝ （ＬｉｎｋＬｉｓｔ）ｃｓｉｚｅｏｆ（ＬＮｏｄｅ））；ｓ－＞ｄａｔａ＝ｅ；ｓ－＞ｎｅｘｔ＝ｐ－＞ｎｅｘｔ；ｐｐ－＞ｎｅｘｔ＝ｓ；ｒｅｔｕｒｎ｝·刪除單鏈表的第ｉ個(gè)結(jié)點(diǎn)的過(guò)（８）刪ＳｔａｔｕｓＬｉｓｔＤｅｌｅｔｅ（ＬｉｎｋＬｉｓｔＬｉｎｔｉ，ＥｌｅｍＴｙｐｅ｛ｐ＝Ｌ；ｊ＝ｗｈｉｌｅ（ｐ－＞ｎｅｘｔ＆＆ｊ＜ｉ－１）｛ｐ＝ｐ－＞ｎｅｘｔ；＋＋ｊ｝ｉｆ（?。ǎ穑荆睿澹簦辏荆椋保颍澹簦酰颍睿牛遥遥希?；ｒ＝ｐ－＞ｎｅｘｔ；ｅ＝ｒ－＞ｐ－＞ｎｅｘｔ＝ｐ－＞ｎｅｘｔ－ｎｅｘｔ；／／（ｐ－＞ｎｅｘｔ＝ｒ－＞ｎｅｘｔ；）ｆｒｅｅ（ｒ）；ｒｅｔｕｒｎＯＫ；｝·動(dòng)態(tài)建立單鏈表的過(guò)（９）頭插法建ＣｒｅａｔｅＬｉｓｔＨ（ＬｉｎｋＬｉｓｔＬｉｎｔ｛ＬＬ＝（ＬｉｎｋＬｉｓｔ）ｃｓｉｚｅｏｆＬＮｏｄｅ））Ｌ－＞ｎｅｘｔ＝ＬＮｏｄｅ））ｆｏｒ（ｉ＝ｎ；ｉ＞０；－－ｉ）ｓ＝（ＬｉｎｋＬｉｓｔ）ｃｓｉｚｅｏｆ（ＬＮｏｄｅ））；ｓｃａｎｆ（＆ｓ－＞ｄａｔａ）；ｓ－＞ｎｅｘｔ＝Ｌ－＞ｎｅｘｔ；Ｌ－＞ｎｅｘｔ＝ｓ；｝｝·尾插法建（１０）尾插法建ＣｒｅａｔｅＬｉｓｔＴ（ＬｉｎｋＬｉｓｔＬｉｎｔ｛ｔａｉｌ＝Ｌ＝（ＬｉｎｋＬｉｓｔ）ｃｓｉｚｅｏｆ（ＬＮｏｄｅ））；Ｌ－＞ｎｅｘｔ＝ＮＵＬＬ；ｆｏｒ（ｉ＝ｎ；ｉ＞０；－－ｉ）ｓ＝（ＬｉｎｋＬｉｓｔ）ｃｓｉｚｅｏｆ（ＬＮｏｄｅ））；ｓｃａｎｆ（＆ｓ－＞ｄａｔａ）；ｓ－＞ｎｅｘｔ＝ＮＵＬＬ；ｔａｉｌ－＞ｎｅｘｔ＝ｓ；①ｔａｉｌ＝ｓ；｝｝（１１）按元素值查找ａｔｅＥｍＬ，思路：在單鏈表Ｌ中從頭開(kā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)的語(yǔ)句序列ｑ＝ｐ－＞ｎｅｘｔ；ｐ－＞ｎｅｘｔ＝ｑ－＞ｎｅｘｔ；ｆｒｅｅ（ｑ）；刪除 ｐ結(jié)點(diǎn)的直接前驅(qū)結(jié)點(diǎn)的語(yǔ)句序列ｑ＝Ｌ；ｗｈｉｌｅ（ｑ－＞ｎｅｘｔ－＞ｎｅｘｔ?。剑穑?ｑ＝ｑ－＞ｎｅｘｔ；ｓ＝ｑ－＞ｎｅｘｔ；ｑ－＞ｎｅｘｔ＝ｐ；ｆｒｅｅ（ｓ）；刪除 ｐ結(jié)點(diǎn)的語(yǔ)句序列ｑ＝Ｌ；ｗｈｉｌｅ（ｑ－＞ｎｅｘｔ?。剑穑?ｑ＝ｑ－＞ｎｅｘｔ；ｑ－＞ｎｅｘｔ＝ｐ－＞ｎｅｘｔ；ｆｒｅｅ（ｐ）刪除首元結(jié)點(diǎn)的語(yǔ)句序列ｑ＝Ｌ－＞ｎｅｘｔ；Ｌ－＞ｎｅｘｔ＝ｑ－＞ｎｅｘｔ；ｆｒｅｅ（ｑ）；刪除最后一個(gè)結(jié)點(diǎn)的語(yǔ)句序ｗｈｉｌｅ（ｐ－＞ｎｅｘｔ－＞ｎｅｘｔ?。剑危眨蹋蹋?ｐ＝ｐ－＞ｎｅｘｔ；ｑ＝ｐ－＞ｎｅｘｔ；ｐ－＞ｎｅｘｔ＝ＮＵＬＬ；ｆｒｅｅ（ｑ）；鏈?zhǔn)浇Y(jié)構(gòu)的特點(diǎn)非隨機(jī)存貯結(jié)構(gòu)，所以取表元素要慢于順序表。節(jié)約了大塊內(nèi)存適合于插入和刪除操了指針，了指針，使得種操作轉(zhuǎn)換際上用空間換取了時(shí)間，結(jié)點(diǎn)中加兩指針操作２．靜態(tài)鏈有些高級(jí)程序設(shè)計(jì)語(yǔ)言并沒(méi)有指針類型，如ＦＯＲＴＲＡＮ和ＪＡＶＡ。我們可以用數(shù)組來(lái)表示和實(shí)現(xiàn)一個(gè)鏈表，稱為靜態(tài)鏈表。可定義如下＃ｄｅｆｉｎｅＭＡＸＳＩＺＥ ／／最多元素個(gè)數(shù)ｔｙｐｅｄｅｆｓｔｒｕｃｔ｛ＥｌｅｍＴｙｐｅ ｃｕｒ；／／游標(biāo)，指示｝ｐｅｎｔＳＬｉｎｋＬｉｓｔ［ＸＥｉ＝ｓ［ｉ］．ｃｕｒ；指針后移操ｌｃｉ＝ｓ［０］．ｃｕｒ；第一個(gè)可用結(jié)點(diǎn)位ｉｆ（ｓ［０］． ｓ［０］．ｃｕｒ＝ｓ［ｉ］． ／／釋放ｋ結(jié)ｓ［ｋ］．ｃｕｒ＝ｓ［０］．ｃｕｒ；ｓ［０］．ｃｕｒ＝ｋ；Ｉｎｓｅｒｔ：／／將ｉ插在ｒ之ｓ［ｉ］．ｃｕｒ＝ｓ［ｒ］．ｃｕｒ；ｓ［ｒ］．ｃｕｒ＝ｉ；Ｄｅｌｅｔｅ：；／／ｐ為ｋ的直接前驅(qū)，釋放ｓ［ｐ］．ｃｕｒ＝ｓ［ｋ］．ｃｕｒＦｒｅｅ（ｋ）；單鏈表基礎(chǔ)要點(diǎn)在單鏈表中，不能從當(dāng)前結(jié)點(diǎn)出發(fā)訪問(wèn)到任一結(jié)點(diǎn)在單鏈表中，刪除某一指定結(jié)點(diǎn)時(shí)，必須找到該結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是一種順序存取的存儲(chǔ)結(jié)構(gòu)，不具有隨機(jī)訪問(wèn)任一元素的特點(diǎn)設(shè)置頭結(jié)點(diǎn)的作用：使在鏈表的第一個(gè)位置上的操作和表中其它位置上的操作—致，無(wú)需進(jìn)行特殊處理，對(duì)空表和非空表的處理統(tǒng)一。循環(huán)鏈表循環(huán)鏈表是另一種形式的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)可從當(dāng)前結(jié)點(diǎn)出發(fā)，訪問(wèn)到任一結(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)的語(yǔ)句序列ｑ＝ｐ－＞ｎｅｘｔ；ｐ－＞ｎｅｘｔ＝ｐ－＞ｎｅｘｔ－＞ｎｅｘｔ；ｐ－＞ｎｅｘｔ－＞ｐｒｉｏｒ＝ｐ；ｆｒｅｅ（ｑ）刪除 ｐ的直接前驅(qū)結(jié)點(diǎn)的語(yǔ)句序列ｑ＝ｐ－＞ｐｒｉｏｒ；ｐ－＞ｐｒｉｏｒ＝ｐ－＞ｐｒｉｏｒ－＞ｐｒｉｏｒ；ｐ－＞ｐｒｉｏｒ－＞ｎｅｘｔ＝ｐ；ｆｒｅｅ（ｑ）ｒｅｔｕｒｎｒｅｔｕｒｎ｝②找結(jié)點(diǎn)的中序后繼結(jié)結(jié)點(diǎn)ｐ，無(wú)右孩子，右指針指向其后繼，否則ｐ的右子樹(shù)中“最左下”結(jié)點(diǎn)。ＢｉＴｈｒＴｒｅｅＰｏｓｔＮｏｄｅ（ＢｉＴｈｒＴｒｅｅｐ）｛ｐｏｓｔ＝ｐ－＞ｉｆ（ｐ－＞ＲＴａｇ＝＝０）／／有右孩子ｗｈｉｌｅ（ｐｏｓｔ－＞ＬＴａｇ＝＝０）ｐｏｓｔ＝ｐｏｓｔ－＞ｌｃｈｉｌｄ；ｒｅｔｕｒｎ｝帶頭結(jié)點(diǎn)的線索二叉鏈帶頭結(jié)點(diǎn)的中序線索二叉鏈中序遍歷線索二叉樹(shù) ／／０：有孩子；１：無(wú)孩子ＶｏｉｄＩｎＯｒｄｅｒＴｒａｖｅｒｓｅＴｈｒ（ＢｉＴｈｒＴｒｅｅ ｛ｐ＝Ｔ－＞ｌｃｈｉｌｄ；ｗｈｉｌｅ（ｐ！＝Ｔ）ｗｈｉｌｅ（ｐ－＞ＬＴａｇ＝＝０）ｐ＝ｐ－＞ｌｃｈｉｌｄ；ｃｏｕｔ＜＜ｐ－＞ｄａｔａ＜＜“”；ｗｈｉｌｅ（（ｐ－＞ＲＴａｇ＝＝１）＆＆（ｐ－＞ｒｃｈｉｌｄ?。剑裕?ｐ＝ｐ－＞ｒｃｈｉｌｄ；ｃｏｕｔ＜＜ｐ－＞ｄａｔａ＜＜“”；｝ｐ＝ｐ－＞｝｝·按建立線索化鏈表（以中序?yàn)槔龑?duì)某種次序行遍歷，表線索化，要比傳統(tǒng)方式高些。用如線果索程取序代中空經(jīng)指常針要。進(jìn)行二叉樹(shù)的遍歷或需要查找在遍歷過(guò)程中所的線性序列中前驅(qū)和后繼，此時(shí)應(yīng)當(dāng)采用線索鏈表表示。６．４ 樹(shù)和森林１．樹(shù)的存儲(chǔ)結(jié)構(gòu)（三種方法雙親表示法：用一組連續(xù)的空間來(lái)存儲(chǔ)樹(shù)中的結(jié)點(diǎn)，在保存每個(gè)結(jié)點(diǎn)的同時(shí)附設(shè)一個(gè)指示器來(lái)指示其雙親結(jié)點(diǎn)在表中的位置，其結(jié)點(diǎn)的結(jié)構(gòu)如下：樹(shù)的雙親存儲(chǔ)結(jié)構(gòu)示意＃ｄｅｆｉｎｅＭＡＸＴＲＥＥＳＩＺＥ１００ｔｙｐｅｄｅｆｓｔｒｕｃｔＰＴＮｏｄｅ｛ＴＥｌｅｍ ｝ＰＴＮｏｄｅ；Ｔｙｐｅｄｅｆｓｔｒｕｃｔ｛ＰＴＮｏｄｅｎｏｄｅｓ［ＭＡＸＴＲＥＥＳＩＺＥ］ ｒ， ／／根的位置和結(jié)點(diǎn)｝雙親表示法的類型說(shuō)明孩子表示法①定長(zhǎng)結(jié)點(diǎn)長(zhǎng)空鏈域個(gè)數(shù)：ｎｋ"（ｎ）＝ｎ（ｋ－１）＋②把每個(gè)結(jié)點(diǎn)的孩子結(jié)點(diǎn)排列起來(lái)，構(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é)｝ＣｈｉｌｄＰｔｒ；ｔｙｐｅｄｅｆｓｔｒｕｃｔ｛／ｐｅｄａｔａ； 結(jié)

指向下一個(gè)孩子結(jié)點(diǎn)的指順序表結(jié)點(diǎn)的結(jié)構(gòu)定義 ／ＴＥｌｅｍＴｙ點(diǎn)的信 ／ＣｈｉｌｄＰｔｒＦｉｒｓｔＣｈｉｌｄ順指 向孩子鏈表的頭指針指｝ｔｙｐｅｄｅｆｓｔｒｕｃｔ｛

樹(shù)的定 樹(shù)順 ｎｏｄｅｓ［ＭＡＸＴＲＥＥＳＩＺＥ］； 序 順ｉｎｔｒｏｏｔ，ｎｕｍ； 根結(jié)點(diǎn)的位置和樹(shù)的結(jié)點(diǎn)個(gè)數(shù)／｝孩子兄弟表示法ｔｙｐｅｄｅｆｓｔｒｕｃｔＣＳＮｏｄｅ｛結(jié)第ＥｌｅｍＴｙｐｅ 點(diǎn)信 結(jié)第ＳｔｒｕｃｔＣＳＮｏｄｅＦｉｒｓｔＣｈｉｌｄ，ＮｅｘｔＳｉｂｌｉｎｇ；｝ 這種存儲(chǔ)結(jié)構(gòu)便于實(shí)現(xiàn)樹(shù)的各種操作

—個(gè)孩子，下一個(gè)兄弟樹(shù)的孩子兄弟鏈存儲(chǔ)結(jié)構(gòu)示意圖２．樹(shù)、森林與二叉樹(shù)的相互轉(zhuǎn)換·樹(shù)轉(zhuǎn)換為二叉（１）在所有相鄰兄弟結(jié)點(diǎn)之間加一水平連線（（２）對(duì)每個(gè)非葉結(jié)點(diǎn)ｋ，除了其最左邊的孩子結(jié)點(diǎn)外，刪去ｋ與其他孩子結(jié)點(diǎn)的連線（３）所有水平線段以左邊結(jié)點(diǎn)為軸心順時(shí)針旋轉(zhuǎn)４５度，使之結(jié)構(gòu)層次分明。樹(shù)做這樣的轉(zhuǎn)換所構(gòu)成的二叉樹(shù)是唯一的。樹(shù)與二叉樹(shù)的對(duì)·森林轉(zhuǎn)換為二叉森林也可以方便地用孩子兄弟鏈表表示。森林轉(zhuǎn)換為二叉樹(shù)的方法如下（１）將森林中的每棵樹(shù)轉(zhuǎn)換成相應(yīng)的二叉樹(shù)（２）第一棵二叉樹(shù)不動(dòng)，從第二棵二叉樹(shù)開(kāi)始，依次把后一棵二叉樹(shù)的根結(jié)點(diǎn)作為前一棵二叉樹(shù)根結(jié)點(diǎn)的右孩子，當(dāng)所有二叉樹(shù)連在一起后，所得到的二叉樹(shù)就是由森林轉(zhuǎn)換得到的二叉樹(shù)?！ざ鏄?shù)還原為樹(shù)或森將一棵二叉樹(shù)還原為樹(shù)或森林，具體方法如下（）若某結(jié)點(diǎn)是其雙親的左孩子，則把該結(jié)點(diǎn)的右孩子、右孩子的右孩子……都與該結(jié)點(diǎn)的雙結(jié)點(diǎn)

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

ｗｎｋｎＬａ）＝７×２＋５×２＋２×２＋４×２＝３６Ｌｂ）＝４×２＋７×３＋５×３＋２×１＝４６Ｌｃ）＝７×１＋５×２＋２×３＋４×３＝３５⑤哈夫曼樹(shù)（最優(yōu)二叉樹(shù)設(shè)二叉樹(shù)具有ｎ個(gè)帶權(quán)值的葉子結(jié)點(diǎn)，那么從根結(jié)點(diǎn)到各個(gè)葉子結(jié)點(diǎn)的路徑長(zhǎng)度與相應(yīng)結(jié)點(diǎn)權(quán)值的乘積的和，叫做二叉樹(shù)的帶權(quán)路徑長(zhǎng)度。具有最小帶權(quán)路徑長(zhǎng)度的二叉樹(shù)稱為哈夫曼樹(shù)２．構(gòu)造哈夫曼樹(shù)（哈夫曼算法１）由給定的ｎ個(gè)權(quán)值｛．．．，Ｗｎ｝，構(gòu)造ｎ棵只有一個(gè)葉子結(jié)點(diǎn)的二叉樹(shù)，從而得到一個(gè)二２）在Ｆ中選取根結(jié)點(diǎn)的權(quán)值最小和次小的兩棵二叉樹(shù)作為左、右子樹(shù)構(gòu)造一棵新的二叉樹(shù)，這新的二叉樹(shù)根結(jié)點(diǎn)的權(quán)值為其左、右子樹(shù)根結(jié)點(diǎn)權(quán)值之和３）３）在集合Ｆ中刪除作為左、右子樹(shù)新加入到集合Ｆ中兩棵二叉樹(shù)，并建立的二叉４）重復(fù)（２）、（３）兩步，當(dāng)Ｆ