整理自高教版《全國(guó)計(jì)算機(jī)等級(jí)考試二級(jí)教程——公共基礎(chǔ)知識(shí)》和人郵版《全國(guó)計(jì)算機(jī)等級(jí)考試教程 二級(jí)公共基礎(chǔ)知識(shí)》
線性鏈表
線性鏈表的基本概念
線性表的順序存儲(chǔ)結(jié)構(gòu)存在以下幾方面的缺點(diǎn)：
- 對(duì)于大的線性表耀里，特別是元素插入或刪除很頻繁的情況下蜈缤，采用順序存儲(chǔ)結(jié)構(gòu)的插入與刪除運(yùn)算效率很低。
- 在順序存儲(chǔ)結(jié)構(gòu)下备韧，線性表的存儲(chǔ)空間不便于擴(kuò)充劫樟。
- 線性表的順序存儲(chǔ)結(jié)構(gòu)不便于對(duì)存儲(chǔ)空間的動(dòng)態(tài)分配痪枫。
因此织堂，對(duì)于大的線性表叠艳，特別是元素變動(dòng)頻繁的大線性表不宜采用順序存儲(chǔ)結(jié)構(gòu)，而是采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)易阳。
假設(shè)數(shù)據(jù)結(jié)構(gòu)中的每一個(gè)數(shù)據(jù)結(jié)點(diǎn)對(duì)應(yīng)于一個(gè)存儲(chǔ)單元附较，這種存儲(chǔ)單元稱為存儲(chǔ)點(diǎn)，簡(jiǎn)稱結(jié)點(diǎn)潦俺。
在鏈?zhǔn)酱鎯?chǔ)方式中拒课，要求每個(gè)結(jié)點(diǎn)有兩部分組成：數(shù)據(jù)域和指針域。其中指針用于指向該結(jié)點(diǎn)的前一個(gè)或后一個(gè)結(jié)點(diǎn)（即前件或后件）事示。數(shù)據(jù)元素之間的邏輯關(guān)系是由指針域來(lái)確定的早像。
鏈?zhǔn)酱鎯?chǔ)方式既可用于表示線性結(jié)構(gòu)，也可用于表示非線性結(jié)構(gòu)肖爵。在表示較復(fù)雜的非線性結(jié)構(gòu)時(shí)卢鹦，其指針域的個(gè)數(shù)要多一些。
線性鏈表
線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)稱為線性鏈表劝堪。
將計(jì)算機(jī)中的每一個(gè)存儲(chǔ)結(jié)點(diǎn)分為兩部分：一部分用于存儲(chǔ)數(shù)據(jù)元素的值冀自，稱為數(shù)據(jù)域；另一部分用于存儲(chǔ)下一個(gè)數(shù)據(jù)元素的存儲(chǔ)序號(hào)（即存儲(chǔ)結(jié)點(diǎn)的地址）秒啦，即指向后件的點(diǎn)熬粗，稱為指針域。
在線性鏈表中余境，用一個(gè)專門的指針HEAD指向線性鏈表中第一個(gè)數(shù)據(jù)元素的結(jié)點(diǎn)（即存放線性鏈表中第一個(gè)數(shù)據(jù)元素的存儲(chǔ)結(jié)點(diǎn)的序號(hào)）驻呐。線性表中最后一個(gè)元素沒(méi)有后件，因此葛超，線性鏈表中最后一個(gè)結(jié)點(diǎn)的指針域?yàn)榭眨ㄓ肗ULL或0來(lái)表示）暴氏，表示鏈表終止。
在線性鏈表中绣张，各數(shù)據(jù)元素之間的前后件關(guān)系是由各結(jié)點(diǎn)的指針域來(lái)表示的答渔，指向線性表中第一個(gè)結(jié)點(diǎn)的指針HEAD稱為頭指針，當(dāng)HEAD=NULL（或0）時(shí)稱為空表侥涵。
在線性單鏈表中沼撕，每一個(gè)結(jié)點(diǎn)只有一個(gè)指針域，由這個(gè)指針只能找到后件結(jié)點(diǎn)芜飘，但找不到前件結(jié)點(diǎn)务豺。因此，在這種線性鏈表中嗦明，只能順指針向鏈尾方向進(jìn)行掃描笼沥，這對(duì)于某些問(wèn)題的處理會(huì)帶來(lái)不便。為了彌補(bǔ)線性單鏈表的這個(gè)缺點(diǎn)，在某些應(yīng)用中奔浅，對(duì)線性鏈表中的每個(gè)結(jié)點(diǎn)設(shè)置兩個(gè)指針馆纳，一個(gè)稱為左指針（Llink）用以指向其前件結(jié)點(diǎn)；另一個(gè)稱為右指針（Rlink）汹桦，用以指向其后件結(jié)點(diǎn)鲁驶。這樣的線性鏈表稱為線性雙鏈表。
帶鏈的棧
棧也是線性表舞骆，也可以采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)钥弯。
在實(shí)際應(yīng)用中，帶鏈的椂角荩可以用來(lái)手機(jī)計(jì)算機(jī)存儲(chǔ)空間中所有空閑的存儲(chǔ)結(jié)點(diǎn)脆霎，這種帶鏈的棧稱為可利用棧。
帶鏈的隊(duì)列
隊(duì)列也是線性表狈惫，也可以采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)绪穆。
線性鏈表的基本運(yùn)算
在線性鏈表中查找指定的元素
當(dāng)找到包含指定元素的前一個(gè)結(jié)點(diǎn)后，就可以在該結(jié)點(diǎn)后插入新結(jié)點(diǎn)或刪除該結(jié)點(diǎn)后的一個(gè)結(jié)點(diǎn)虱岂。
在鏈表中玖院，如果有指定元素，則掃描到等于該元素值的結(jié)點(diǎn)時(shí)第岖，停止掃描难菌，返回該結(jié)點(diǎn)的位置。因此蔑滓，如果鏈表中有多個(gè)等于指定元素的結(jié)點(diǎn)只返回第一個(gè)結(jié)點(diǎn)的位置郊酒。如果鏈表中沒(méi)有元素的值等于指定元素，則掃描完所有元素后键袱，返回NULL燎窘。
線性鏈表的插入
線性鏈表的插入是指在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)下的線性表中插入一個(gè)新元素。
假設(shè)現(xiàn)在要在線性鏈表中包含元素x的結(jié)點(diǎn)之前插入一個(gè)新元素b蹄咖，插入過(guò)程如下：
- 從可利用棧取得一個(gè)結(jié)點(diǎn)褐健。設(shè)該結(jié)點(diǎn)號(hào)為p（即取得結(jié)點(diǎn)的存儲(chǔ)序號(hào)存放在變量p中），并置結(jié)點(diǎn)p的數(shù)據(jù)域?yàn)椴迦氲脑刂礲澜汤。
- 在線性鏈表中尋找包含元素x的前一個(gè)結(jié)點(diǎn)蚜迅，設(shè)該結(jié)點(diǎn)的存儲(chǔ)序號(hào)為q。
- 最后將結(jié)點(diǎn)p插入到結(jié)點(diǎn)q之后俊抵。為了實(shí)現(xiàn)這一步谁不，只要改變以下兩個(gè)結(jié)點(diǎn)的指針域內(nèi)容:a. 使結(jié)點(diǎn)p指向包含元素x的結(jié)點(diǎn)（結(jié)點(diǎn)q的后件結(jié)點(diǎn)）；b.使結(jié)點(diǎn)q的指針域內(nèi)容改為指向結(jié)點(diǎn)p徽诲。
由線性鏈表的插入過(guò)程可以看出刹帕，由于插入的新結(jié)點(diǎn)取自于可利用棧吵血，因此，只要可利用棧不空偷溺，在線性鏈表插入時(shí)總能取到存儲(chǔ)插入元素的新結(jié)點(diǎn)践瓷，不會(huì)發(fā)生“上溢”的情況。而且亡蓉，由于可利用棧是公用的，多個(gè)線性鏈表可以共享它喷舀，從而很方便地實(shí)現(xiàn)了存儲(chǔ)空間的動(dòng)態(tài)分配砍濒。另外，線性鏈表的插入過(guò)程中不發(fā)生數(shù)據(jù)元素移動(dòng)的現(xiàn)象硫麻，只需改變有關(guān)結(jié)點(diǎn)的指針即可爸邢，從而提高了插入的效率。
線性鏈表的刪除
線性鏈表的刪除是指在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)下的線性表中刪除包含指定元素的結(jié)點(diǎn)拿愧。
為了在線性鏈表中刪除包含指定元素的結(jié)點(diǎn)杠河，首先要在線性鏈表中找到這個(gè)結(jié)點(diǎn)，然后將要?jiǎng)h除的結(jié)點(diǎn)放回可利用棧浇辜。
假設(shè)現(xiàn)在要在線性鏈表中刪除包含元素x的結(jié)點(diǎn)券敌，其刪除過(guò)程如下：
- 在線性鏈表中尋找包含元素x的前一個(gè)結(jié)點(diǎn)，設(shè)該結(jié)點(diǎn)的序號(hào)為q柳洋。
- 將結(jié)點(diǎn)q后的結(jié)點(diǎn)p從線性鏈表中刪除待诅，即讓結(jié)點(diǎn)q的指針指向包含元素x的結(jié)點(diǎn)p的指針指向的結(jié)點(diǎn)。
- 將包含元素x的結(jié)點(diǎn)p送回可利用棧熊镣。
此時(shí)卑雁，線性鏈表的刪除運(yùn)算完成。
循環(huán)鏈表
循環(huán)鏈表的結(jié)構(gòu)與線性鏈表相比绪囱，具有以下兩個(gè)特點(diǎn)：
- 循環(huán)鏈表中增加了一個(gè)表頭結(jié)點(diǎn)测蹲，循環(huán)鏈表的頭指針域指向表頭結(jié)點(diǎn)。
- 循環(huán)鏈表中最后一個(gè)結(jié)點(diǎn)的指針域不是空鬼吵，而是指向表頭結(jié)點(diǎn)扣甲。即在循環(huán)鏈表中，所有結(jié)點(diǎn)的指針構(gòu)成了一個(gè)環(huán)狀鏈齿椅。
在實(shí)際應(yīng)用中文捶，循環(huán)鏈表與線性單鏈表相比主要有兩個(gè)優(yōu)點(diǎn)：
- 在循環(huán)鏈表中，只要指出表中任何一個(gè)結(jié)點(diǎn)的位置媒咳，就可以從它出發(fā)訪問(wèn)到表中其他所有的結(jié)點(diǎn)粹排。
- 在任何情況下循環(huán)鏈表中至少有一個(gè)結(jié)點(diǎn)，從而使空表與非空表的運(yùn)算統(tǒng)一涩澡。
樹(shù)與二叉樹(shù)
樹(shù)的基本概念
樹(shù)是一種簡(jiǎn)單的非線性結(jié)構(gòu)顽耳。
在樹(shù)結(jié)構(gòu)中肌访，每個(gè)結(jié)點(diǎn)只有一個(gè)前件，稱為父結(jié)點(diǎn)圣勒，沒(méi)有前件的結(jié)點(diǎn)只有一個(gè)盆色，稱為樹(shù)的根結(jié)點(diǎn)，簡(jiǎn)稱為樹(shù)的根胰耗。每個(gè)結(jié)點(diǎn)可以有多個(gè)后件限次，它們都稱為該結(jié)點(diǎn)的子結(jié)點(diǎn)，沒(méi)有后件的結(jié)點(diǎn)稱為葉子結(jié)點(diǎn)柴灯。一個(gè)結(jié)點(diǎn)所擁有的后件個(gè)數(shù)稱為該結(jié)點(diǎn)的度卖漫，所有結(jié)點(diǎn)中的最大的度稱為樹(shù)的度。
樹(shù)中的結(jié)點(diǎn)數(shù)=樹(shù)中所有結(jié)點(diǎn)的度之和+1
在樹(shù)結(jié)構(gòu)中赠群，一般按照如下原則分層：
- 根結(jié)點(diǎn)在第一層羊始。
- 同一層上所有結(jié)點(diǎn)的子結(jié)點(diǎn)都在下一層。
- 數(shù)的最大層次稱為樹(shù)的深度查描。
- 在樹(shù)中突委，以某結(jié)點(diǎn)的一個(gè)子結(jié)點(diǎn)為根構(gòu)成的樹(shù)稱為該結(jié)點(diǎn)的一棵子樹(shù)，
- 葉子節(jié)點(diǎn)沒(méi)有子樹(shù)冬三。
樹(shù)在計(jì)算機(jī)中通常用多重鏈表來(lái)表示匀油。
二叉樹(shù)及其基本性質(zhì)
什么是二叉樹(shù)
二叉樹(shù)具有以下兩個(gè)特點(diǎn)：
- 非空二叉樹(shù)只有一個(gè)根結(jié)點(diǎn)。
- 每一個(gè)結(jié)點(diǎn)最多有兩棵子樹(shù)勾笆，且分別稱為該結(jié)點(diǎn)的左子樹(shù)與右子樹(shù)钧唐。
在二叉樹(shù)中，每一個(gè)結(jié)點(diǎn)的度最大為2匠襟。
二叉樹(shù)的基本性質(zhì)
- 在二叉樹(shù)的第k層上钝侠，最多有2^(k-1)個(gè)結(jié)點(diǎn)。
- 深度為m的二叉樹(shù)最多有2^m-1個(gè)結(jié)點(diǎn)酸舍。
- 在任意一棵二叉樹(shù)中帅韧，度為0的結(jié)點(diǎn)（葉子結(jié)點(diǎn)）總是比度為2的結(jié)點(diǎn)多1個(gè)。
- 具有n個(gè)結(jié)點(diǎn)的二叉樹(shù)啃勉，其深度至少為[log2n]+1忽舟，其中[log2n]表示取log2n的整數(shù)部分。
- 具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為[log2n]+1淮阐。
- 設(shè)完全二叉樹(shù)共有n個(gè)結(jié)點(diǎn)叮阅，如果從根結(jié)點(diǎn)開(kāi)始，按層序（每一層從左到右）用自然數(shù)1,2泣特，……浩姥，n給結(jié)點(diǎn)進(jìn)行編號(hào)，則對(duì)于編號(hào)為k的結(jié)點(diǎn)有以下結(jié)論：
- 若k=1状您，則該結(jié)點(diǎn)為根結(jié)點(diǎn)勒叠，若k＞1兜挨，則該結(jié)點(diǎn)的父結(jié)點(diǎn)編號(hào)為INT（k/2）（k/2取整數(shù)）。
- 若2k≤n眯分，則編號(hào)為k的結(jié)點(diǎn)的左子結(jié)點(diǎn)編號(hào)為2k拌汇，否則該結(jié)點(diǎn)無(wú)左、右子結(jié)點(diǎn)弊决。
- 若2k+1≤n噪舀，則編號(hào)為k的結(jié)點(diǎn)的右子結(jié)點(diǎn)編號(hào)為2k+1，否則該結(jié)點(diǎn)無(wú)右子結(jié)點(diǎn)飘诗。
滿二叉樹(shù)與完全二叉樹(shù)
滿二叉樹(shù)與完全二叉樹(shù)是兩種特殊形態(tài)的二叉樹(shù)与倡。
滿二叉樹(shù)
除最后一層外，每一層上所有的結(jié)點(diǎn)都有兩個(gè)子結(jié)點(diǎn)疚察，即每一層上的結(jié)點(diǎn)樹(shù)都達(dá)到最大值。
滿二叉樹(shù)的第k層上有2^(k-1)個(gè)結(jié)點(diǎn)仇奶，深度為m的滿二叉樹(shù)有2(m-1)個(gè)結(jié)點(diǎn)貌嫡。
完全二叉樹(shù)
除最后一層外，每一層上的結(jié)點(diǎn)樹(shù)均達(dá)到最大值该溯，在最后一層上只缺少右邊的若干結(jié)點(diǎn)岛抄。
滿二叉樹(shù)也是完全二叉樹(shù)，完全二叉樹(shù)一般不是滿二叉樹(shù)
二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)
在計(jì)算機(jī)中狈茉，二叉樹(shù)通常采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)夫椭。
對(duì)于滿二叉樹(shù)和完全二叉樹(shù)，可以按層序進(jìn)行順序存儲(chǔ)氯庆，但順序存儲(chǔ)結(jié)構(gòu)對(duì)一般的二叉樹(shù)不適用蹭秋。
二叉樹(shù)的遍歷
二叉樹(shù)的遍歷指不重復(fù)地訪問(wèn)二叉樹(shù)中的所有結(jié)點(diǎn)。
在遍歷二叉樹(shù)的過(guò)程中堤撵，一般先遍歷左子樹(shù)仁讨，然后再遍歷右子樹(shù)。
前序遍歷（DLR）
首先訪問(wèn)根結(jié)點(diǎn)实昨，然后遍歷左子樹(shù)洞豁，最后遍歷右子樹(shù)。并且在遍歷左右子樹(shù)時(shí)荒给，仍然先訪問(wèn)根結(jié)點(diǎn)丈挟，然后遍歷左子樹(shù)，最后遍歷右子樹(shù)志电。
前序遍歷二叉樹(shù)的過(guò)程是一個(gè)遞歸的過(guò)程曙咽。
中序遍歷（LDR）
首先遍歷左子樹(shù)，然后訪問(wèn)根結(jié)點(diǎn)挑辆，最后遍歷右子樹(shù)桐绒。并且在遍歷左右子樹(shù)時(shí)夺脾，仍然先遍歷左子樹(shù)，然后訪問(wèn)根結(jié)點(diǎn)茉继，最后遍歷右子樹(shù)咧叭。
中序遍歷二叉樹(shù)也是一個(gè)遞歸的過(guò)程。
后序遍歷（LRD）
首先遍歷左子樹(shù)烁竭，然后遍歷右子樹(shù)菲茬，最后訪問(wèn)根結(jié)點(diǎn)。并且在遍歷左右子樹(shù)時(shí)派撕，仍然先遍歷左子樹(shù)婉弹，然后遍歷右子樹(shù)，最后訪問(wèn)根結(jié)點(diǎn)终吼。
后序遍歷二叉樹(shù)也是一個(gè)遞歸的過(guò)程镀赌。
