公共基礎(chǔ)知識(shí)

課程簡(jiǎn)介

計(jì)算機(jī)二級(jí)考試是以程序設(shè)計(jì)為主的計(jì)算機(jī)等級(jí)考試，目的是促進(jìn)考生學(xué)習(xí)程序設(shè)計(jì)的

熱情，提高考生的程序設(shè)計(jì)水平。而程序設(shè)計(jì)離不開(kāi)算法、軟件工程等知識(shí)的。本課程作為

計(jì)算機(jī)二級(jí)考試的公共基礎(chǔ)課程，從理論的角度對(duì)數(shù)據(jù)結(jié)構(gòu)、軟件工程、結(jié)構(gòu)化程序設(shè)計(jì)與

面向?qū)ο蟮某绦蛟O(shè)計(jì)、數(shù)據(jù)庫(kù)基礎(chǔ)知識(shí)進(jìn)行了簡(jiǎn)單的介紹，擴(kuò)展考生的知識(shí)面，并對(duì)程序設(shè)

計(jì)知識(shí)有一個(gè)系統(tǒng)的了解。

本課程一共有四個(gè)部分。第一部分，主要介紹算法的基本概念，數(shù)據(jù)結(jié)構(gòu)的基本概念和

定義，線性表及其基本運(yùn)算，二叉樹(shù)的基本概念、存儲(chǔ)結(jié)構(gòu)及其應(yīng)用，并介紹了一些常用的

算法；第二部分，主要介紹程序設(shè)計(jì)的方法與風(fēng)格，結(jié)構(gòu)化程序設(shè)計(jì)，面向?qū)ο蟮某绦蛟O(shè)計(jì)

方法，對(duì)象，方法，屬性及繼承與多態(tài)性；第三部分，主要介紹軟件工程的基本概念，結(jié)構(gòu)

化分析方法，結(jié)構(gòu)化設(shè)計(jì)方法，軟件測(cè)試的基本方法和程序的調(diào)試方法，從工程的角度對(duì)軟

件開(kāi)發(fā)進(jìn)行了介紹：第四部分，主要介紹數(shù)據(jù)庫(kù)，數(shù)據(jù)庫(kù)管理系統(tǒng)，數(shù)據(jù)庫(kù)系統(tǒng)的基本概念,

數(shù)據(jù)模型，實(shí)體聯(lián)系模型及E-R圖等基本概念，關(guān)系代數(shù)理論中的基本運(yùn)算，數(shù)據(jù)庫(kù)設(shè)計(jì)的

基本方法和步驟。

本課程作為公共基礎(chǔ)課，在有限的篇幅和學(xué)時(shí)的情況卜，當(dāng)然不能將所涉及到的相關(guān)知

識(shí)都講透，如果對(duì)這些知識(shí)感興趣，可去查閱相關(guān)主題的書(shū)籍，深入學(xué)習(xí)。

第一章的參考書(shū)：各類(lèi)《數(shù)據(jù)結(jié)構(gòu)》教程

第二章的參考書(shū)：各類(lèi)介紹程序設(shè)計(jì)與算法、面向?qū)ο蟪绦蛟O(shè)計(jì)的教程

第三章的參考書(shū)：各類(lèi)《軟件工程》教程

第四章的參考書(shū)：各類(lèi)《數(shù)據(jù)庫(kù)原理與應(yīng)用》教程的基礎(chǔ)部分

學(xué)習(xí)方法

本課程的學(xué)習(xí)，要求認(rèn)真看書(shū)，對(duì)書(shū)中的內(nèi)容進(jìn)行歸納和總結(jié)，將所有的知識(shí)穿成一條

線。

在看書(shū)的過(guò)程中，要仔細(xì)閱讀，對(duì)書(shū)中重要的內(nèi)容、概念要記住，因?yàn)楸菊n程的考試是

采用標(biāo)準(zhǔn)化的考試方式，單選和填空兩種題型，因此要求考生對(duì)知識(shí)的掌握要準(zhǔn)確，不能模

棱兩可。

反復(fù)地看書(shū)，做題，因?yàn)楸菊n程主要是一些理論的知識(shí)，要求記憶的內(nèi)容很多，因此,

必須多做題，多看書(shū)，在做題的過(guò)程中檢驗(yàn)自己對(duì)知識(shí)的理解和掌握情況是否到位、正確。

自己總結(jié)課程的內(nèi)容，也是幫助理解和記憶的好方法。

第一章數(shù)據(jù)結(jié)構(gòu)與算法

一、學(xué)習(xí)目標(biāo)與要求

1.了解算法的基本概念和一些常用的算法，學(xué)會(huì)計(jì)算算法的時(shí)間復(fù)雜度；

2.掌握數(shù)據(jù)結(jié)構(gòu)的基本概念，并了解數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)，學(xué)會(huì)利用圖形的方

式表示數(shù)據(jù)結(jié)構(gòu)；

3.了解線性表的基本概念，并掌握線性表的順序存儲(chǔ)結(jié)構(gòu)以及順序存儲(chǔ)的線性表的基

本運(yùn)算；

4.了解棧和隊(duì)列的基本概念，并掌握它們的基本運(yùn)算；

5.了解線性鏈表的基本概念，并掌握線性鏈表的基本運(yùn)算，同時(shí)，了解循環(huán)鏈表的基

本概念和基本操作；

6.理解樹(shù)的概念，尤其是二叉樹(shù)的基本概念和相關(guān)性質(zhì)，掌握二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)和遍

歷技術(shù)；

7.掌握查找技術(shù)，學(xué)會(huì)利用順序查找和二分查找在數(shù)列中查找指定的數(shù)據(jù)：

8.學(xué)會(huì)利用相關(guān)的排序技術(shù)實(shí)現(xiàn)無(wú)序數(shù)列的排序操作。

二、內(nèi)容要點(diǎn)

（一）算法

1.算法的基本概念

算法是指解題方案的準(zhǔn)確而完整的描述。即是一組嚴(yán)謹(jǐn)?shù)囟x運(yùn)算順序的規(guī)則，并且每

一個(gè)規(guī)則都是有效的，且是明確的，沒(méi)有二義性，同時(shí)該規(guī)則將在有限次運(yùn)算后可終止。

1）算法的基本特征

（1）可行性

由于算法的設(shè)計(jì)是為了在某一個(gè)特定的計(jì)算工具上解決某一個(gè)實(shí)際的問(wèn)題而設(shè)計(jì)的，因

此，它總是受到計(jì)算工具的限制，使執(zhí)行產(chǎn)生偏差。

如：計(jì)算機(jī)的數(shù)值有效位是有限的，當(dāng)大數(shù)和小數(shù)進(jìn)行運(yùn)算時(shí)，往往會(huì)因?yàn)橛行粩?shù)的

影響而使小數(shù)丟失，因此，在算法設(shè)計(jì)時(shí)，應(yīng)該考慮到這一點(diǎn)。

（2）確定性

算法的設(shè)計(jì)必須是每一個(gè)步驟都有明確的定義，不允許有模糊的解釋,也不能有多義性。

例如，一個(gè)實(shí)際的問(wèn)題，小寶和萍萍共有12個(gè)蘋(píng)果，小寶比萍萍多4個(gè)，請(qǐng)問(wèn)小寶和

[%+y=12

萍萍各有兒個(gè)蘋(píng)果？這個(gè)問(wèn)題，我們可以立一個(gè)方程〈來(lái)求解，要求x和y

[x-y=4

的值，公式是正確的，但如何讓計(jì)算能夠進(jìn)行計(jì)算，我們的算法不能把公式直接輸進(jìn)去，而

應(yīng)該設(shè)計(jì)出解題的步驟和過(guò)程。

即設(shè)計(jì)的算法是計(jì)算工具所能夠正常解決問(wèn)題的過(guò)程。

(3)有窮性

算法的有窮性，即在一定的時(shí)間是能夠完成的，即算法應(yīng)該在計(jì)算有限個(gè)步驟后能夠正

常結(jié)束。

例如，在數(shù)學(xué)中的無(wú)窮級(jí)數(shù)，在計(jì)算機(jī)中只能求有限項(xiàng)，即計(jì)算的過(guò)程是有窮的。

(4)擁有足夠的情報(bào)

算法的執(zhí)行與輸入的數(shù)據(jù)和提供的初始條件相關(guān)，不同的輸入或初始條件會(huì)有不同的輸

出結(jié)果，提供準(zhǔn)確的初始條件和數(shù)據(jù)，才能使算法正確執(zhí)行。

2)算法的基本要素

?是數(shù)據(jù)對(duì)象的運(yùn)算和操作，二是算法的控制結(jié)構(gòu)。

(1)算法中對(duì)數(shù)據(jù)的運(yùn)算和操作

算法實(shí)際上是按解題要求從環(huán)境能進(jìn)行的所有操作中選擇合適的操作所組成的一組指

令序列。即算法是計(jì)算機(jī)所能夠處理的操作所組成的指令序列。

(2)算法的控制結(jié)構(gòu)

算法的功能不僅取決于所選用的操作，而且還與各操作之間的順序有關(guān)。

在算法中，操作的執(zhí)行順序乂稱(chēng)算法的控制結(jié)構(gòu)，?般的算法控制結(jié)構(gòu)有三種：順序結(jié)

構(gòu)、選擇結(jié)構(gòu)和循環(huán)結(jié)構(gòu)。

在算法描述是，有相關(guān)的工具對(duì)這三種結(jié)構(gòu)進(jìn)行描述，常用的描述工具有：流程圖、N-S

結(jié)構(gòu)圖和算法描述語(yǔ)言等。

3)算法設(shè)計(jì)的基本方法

為用計(jì)算機(jī)解決實(shí)際問(wèn)題而設(shè)計(jì)的算法，即是計(jì)算機(jī)算法。

通常的算法設(shè)計(jì)有如下幾種：

(1)列舉法

列舉法的基本思想是，根據(jù)提出的問(wèn)題，列舉出所有可能的情況，并用問(wèn)題中給定的條

件檢驗(yàn)?zāi)男┦菨M(mǎn)足條件的，哪些是不滿(mǎn)足條件的。列舉法通常用于解決“是否存在”或“有

哪些可能”等問(wèn)題。

例如，我國(guó)古代的趣味數(shù)學(xué)題：“百錢(qián)買(mǎi)百雞”、“雞兔同籠”等，均可采用列舉法進(jìn)行

解決。

使用列舉法時(shí)，要對(duì)問(wèn)題進(jìn)行詳細(xì)的分析，將與問(wèn)題有關(guān)的知識(shí)條理化、完備化、系統(tǒng)

化，從中找出規(guī)律。

(2)歸納法

歸納法的基本思想是，通過(guò)列舉少量的特殊情況，經(jīng)過(guò)分析，最后找出一般的關(guān)系。歸

納是一種抽象，即從特殊現(xiàn)象中找出一般規(guī)律。但由于在歸納法中不可能對(duì)所有的情況進(jìn)行

列舉，因此，該方法得到的結(jié)論只是一種猜測(cè)，還需要進(jìn)行證明。

(3)遞推

遞推，即是從已知的初始條件出發(fā)，逐次推出所要求的各個(gè)中間環(huán)節(jié)和最后結(jié)果。其中

初始條件或問(wèn)題本身已經(jīng)給定，或是通過(guò)對(duì)問(wèn)題的分析與化簡(jiǎn)而確定。

遞推的本質(zhì)也是一種歸納，遞推關(guān)系式通常是歸納的結(jié)果。

例如，裴波那契數(shù)列，是采用遞推的方法解決問(wèn)題的。

(4)遞歸

在解決一些復(fù)雜問(wèn)題時(shí)，為了降低問(wèn)題的復(fù)雜程序，通常是將問(wèn)題逐層分解，最后歸結(jié)

為一些最簡(jiǎn)單的問(wèn)題。這種將問(wèn)題逐層分解的過(guò)程，并沒(méi)有對(duì)問(wèn)題進(jìn)行求解，而只是當(dāng)解決

了最后的問(wèn)題那些最簡(jiǎn)單的問(wèn)題后，再沿著原來(lái)分解的逆過(guò)程逐步進(jìn)行綜合，這就是遞歸的

方法。

遞歸分為直接遞歸和間接遞歸兩種方法。如果一個(gè)算法直接調(diào)用自己，稱(chēng)為直接遞歸調(diào)

用；如果一個(gè)算法A調(diào)用另一個(gè)算法B,而算法B又調(diào)用算法A,則此種遞歸稱(chēng)為間接遞歸

調(diào)用。

(5)減半遞推技術(shù)

減半遞推即將問(wèn)題的規(guī)模減半，然后，重復(fù)相同的遞推操作。

例如，一元二次方程的求解。

(6)回溯法

有些實(shí)際的問(wèn)題很難歸納出一組簡(jiǎn)單的遞推公式或直觀的求解步驟，也不能使用無(wú)限的

列舉。對(duì)于這類(lèi)問(wèn)題，只能采用試探的方法，通過(guò)對(duì)問(wèn)題的分析，找出解決問(wèn)題的線索，然

后沿著這個(gè)線索進(jìn)行試探，如果試探成功，就得到問(wèn)題的解，如果不成功，再逐步回退，換

別的路線進(jìn)行試探。這種方法，即稱(chēng)為回溯法。

如人工智能中的機(jī)器人下棋。

2.算法復(fù)雜度

算法的復(fù)雜度包括時(shí)間復(fù)雜度和空間復(fù)雜度。

1)時(shí)間復(fù)雜度

即實(shí)現(xiàn)該算法需要的計(jì)算工作量。算法的工作量用算法所執(zhí)行的基本運(yùn)算次數(shù)來(lái)計(jì)算。

同一個(gè)問(wèn)題規(guī)模下，如果算法執(zhí)行所需要的基本次數(shù)取決于某一特定輸入時(shí)，可以用以

下兩種方法來(lái)分析算法的工作量：

算法工作量=f(n)

(1)平均性態(tài)

用各種特定輸入下的基本運(yùn)算次數(shù)的加權(quán)平均值來(lái)度量算法的工作量。

設(shè)x是某個(gè)可能輸入中的某個(gè)特定輸入，p(x)是x出現(xiàn)的概率，t(x)是算法在輸入為x

時(shí)所執(zhí)行的基本運(yùn)算次數(shù)，則算法的平均性態(tài)定義為：

4九)=￡〃(%"(%)

X叫

D“表示當(dāng)規(guī)模為n時(shí)，算法執(zhí)行時(shí)所有可能輸入的集合。

(2)最壞情況復(fù)雜度

指在規(guī)模為n時(shí)，算法所執(zhí)行的基本運(yùn)算的最大次數(shù)。它定義為：

W(n)=max{?(x)}

xwDn

例如，在具有n個(gè)元素的數(shù)列中搜索一個(gè)數(shù)x。

(〃+1招

平均性態(tài)：A(n)=ZPh=Z*7+(1-q)n=-------+(1-q)n

<=in2

即該數(shù)在數(shù)列中任何位置出現(xiàn)的數(shù)列是相同的，也有可能不存在，存在的概率為q。

如果有一半的機(jī)會(huì)存在，則概率q為1/2,平均性態(tài)：

/八1

("+l)x13

A(〃)=-------—+(1——)/iq—〃

224

如果查找的元素一定在數(shù)列中，則每個(gè)數(shù)存在的概率即為1,則平均性態(tài)為:

，/、n+1n

A（n）=-----?—

22

最壞情況分析：即要查找的元素x在數(shù)列的最后或不在數(shù)列中，顯然，它的最壞情況復(fù)

雜度為：W(n)=max{t,\\<i<n+l}=n

2）算法的空間復(fù)雜度

指要執(zhí)行該算法所需要的內(nèi)存空間。算法所占用的內(nèi)存空間包括算法程序所占的空間、

輸入的初始數(shù)據(jù)所占的存儲(chǔ)空間以及算法執(zhí)行過(guò)程中所需要的額外空間，如執(zhí)行過(guò)程中工作

單元以及某種數(shù)據(jù)結(jié)構(gòu)所需要的附加存儲(chǔ)空間等。

（二）數(shù)據(jù)結(jié)構(gòu)的基本概念

1.概念

數(shù)據(jù)結(jié)構(gòu)是指相互有關(guān)聯(lián)的數(shù)據(jù)元素的集合。它包括以下兩個(gè)方面：

?表示數(shù)據(jù)元素的信息

?表示各數(shù)據(jù)之間的前后件關(guān)系

1）數(shù)據(jù)的邏輯結(jié)構(gòu)

是指反映數(shù)據(jù)元素之間的邏輯關(guān)系的數(shù)據(jù)結(jié)構(gòu)。

數(shù)據(jù)的邏輯結(jié)構(gòu)有兩個(gè)要素：

?數(shù)據(jù)元素的集合，記作D

?數(shù)據(jù)之間的前后件關(guān)系，記作R

則數(shù)據(jù)結(jié)構(gòu)B=（D,R）

2）數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)

數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)空間中的存放形式稱(chēng)為數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)，或數(shù)據(jù)的物理結(jié)

構(gòu)。

即數(shù)據(jù)存儲(chǔ)時(shí)，不僅要存放數(shù)據(jù)元素的信息，而且要存儲(chǔ)數(shù)據(jù)元素之間的前后件關(guān)系的

信息。

通常的數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)有順序、鏈接、索引等存儲(chǔ)結(jié)構(gòu)。

2.數(shù)據(jù)結(jié)構(gòu)的圖形表示

數(shù)據(jù)結(jié)構(gòu)的圖形表示有兩個(gè)元素：

?中間標(biāo)有元素值的方框表示數(shù)據(jù)元素，稱(chēng)為數(shù)據(jù)結(jié)點(diǎn)

?用有向線段表示數(shù)據(jù)元素之間的前后件關(guān)系，即有向線段從前件結(jié)點(diǎn)指向后件結(jié)點(diǎn)

注意：在結(jié)構(gòu)圖中，沒(méi)有前件的結(jié)點(diǎn)稱(chēng)為根結(jié)點(diǎn)，沒(méi)有后件的結(jié)點(diǎn)稱(chēng)為終端結(jié)點(diǎn)，也稱(chēng)

葉子結(jié)點(diǎn)。

3.線性結(jié)構(gòu)與非線性結(jié)構(gòu)

如果一個(gè)數(shù)據(jù)元素都沒(méi)有，該數(shù)據(jù)結(jié)構(gòu)稱(chēng)為空數(shù)據(jù)結(jié)構(gòu)；在空數(shù)據(jù)結(jié)構(gòu)中插入一個(gè)新的

元素后數(shù)據(jù)結(jié)構(gòu)變?yōu)榉强諗?shù)據(jù)結(jié)構(gòu)：將數(shù)據(jù)結(jié)構(gòu)中的所有元素均刪除，則該數(shù)據(jù)結(jié)構(gòu)變成空

數(shù)據(jù)結(jié)構(gòu)。

如果?個(gè)非空的數(shù)據(jù)結(jié)構(gòu)滿(mǎn)足如下條件，則該數(shù)據(jù)結(jié)構(gòu)為線性結(jié)構(gòu)：

?有且只有一個(gè)根結(jié)點(diǎn)

?每一?個(gè)結(jié)點(diǎn)最多只有一個(gè)前件，也最多只有一個(gè)后件

線性結(jié)構(gòu)又稱(chēng)線性表。

注意：在線性結(jié)構(gòu)表中插入或刪除元素，該線性表仍然應(yīng)滿(mǎn)足線性結(jié)構(gòu)。

如果一個(gè)數(shù)據(jù)結(jié)構(gòu)不滿(mǎn)足線性結(jié)構(gòu)，則稱(chēng)為非線性結(jié)構(gòu)。

（三）線性表及其順序存儲(chǔ)結(jié)構(gòu)

1.基本概念

線性表是最常用的數(shù)據(jù)結(jié)構(gòu)，它由一組數(shù)據(jù)元素組成。

注意：這里的數(shù)據(jù)元素是一個(gè)廣義的數(shù)據(jù)元素，并不僅僅是指一個(gè)數(shù)據(jù)。如，矩陣、學(xué)

生記錄表等。

非空線性表的結(jié)構(gòu)特征：

?有且只有一個(gè)根結(jié)點(diǎn)，它無(wú)前件

?有且只有一個(gè)終端結(jié)點(diǎn)，它無(wú)后件

?除根結(jié)點(diǎn)和終端結(jié)點(diǎn)之外，所有的結(jié)點(diǎn)有且只有一個(gè)前件和一個(gè)后件。線性表中結(jié)

點(diǎn)的個(gè)數(shù)稱(chēng)為結(jié)點(diǎn)的長(zhǎng)度n。當(dāng)n=0時(shí);稱(chēng)為空表。

2.順序存儲(chǔ)結(jié)構(gòu)

順序存儲(chǔ)結(jié)構(gòu)的特點(diǎn)：

?線性表中所有的元素所占的存儲(chǔ)空間是連續(xù)的

?線性表中各數(shù)據(jù)元素在存儲(chǔ)空間中是按邏輯順序依次存放的

通常，順序存儲(chǔ)結(jié)構(gòu)中，線性表中每一個(gè)數(shù)據(jù)元素在計(jì)算機(jī)存儲(chǔ)空間中的存儲(chǔ)地址由該

元素在線性表中的位置序號(hào)唯一確定。

線性表的順序存儲(chǔ)結(jié)構(gòu)卜的基本運(yùn)算：

?在指定位置插入一個(gè)元素

?刪除線性表中的指定元素

?查找某個(gè)或某些特定的元素

?線性表的排序

?按要求將一個(gè)線性表拆分為多個(gè)線性表

?將多個(gè)線性表合并為一個(gè)線性表

?復(fù)制線性表

?逆轉(zhuǎn)一個(gè)線性表

3.線性表的基本操作

1）順序表的插入運(yùn)算

在順序存儲(chǔ)結(jié)構(gòu)的線性表中插入一個(gè)元素。

注意：找到插入位置后，將插入位置開(kāi)始的所有元素從最后?個(gè)元素開(kāi)始順序后移。另

外，在定義線性表時(shí)，一定要定義足夠的空間，否則，將不允許插入元素。

2）順序表的刪除運(yùn)算

在順序在存儲(chǔ)結(jié)構(gòu)的線性表中刪除一個(gè)元素。

注意：找到刪除的數(shù)據(jù)元素后，從該元素位置開(kāi)始，將后面的元素?向前移動(dòng)，在移

動(dòng)完成后，線性表的長(zhǎng)度減1

（四）棧和隊(duì)列

1.棧及其基本運(yùn)算

1）棧

棧是一種特殊的線性表，它是限定在?端進(jìn)行插入和刪除的線性表。它的插入和刪除只

能在表的一端進(jìn)行，而另一端是封閉的，不允許進(jìn)行插入和刪除操作。

在棧中，允許插入和刪除操作?端稱(chēng)為棧頂，不允許插入和刪除操作的一端則稱(chēng)為棧底。

棧頂?shù)脑乜偸亲詈蟊徊迦氲脑兀彩亲钕缺粍h除的元素。它遵循的原則是：先進(jìn)后出或

后進(jìn)先出。

堆棧指針總是指向棧頂元素的。

2）棧的順序存儲(chǔ)及其運(yùn)算

在棧的順序存儲(chǔ)空間S（1：m）中，S（bottom）通常為棧底元素，S（top）為棧頂元

素。Top=0表示?？?；top=m表示棧滿(mǎn)。

1）入棧運(yùn)算

即在棧的頂部插入一個(gè)新元素。操作方式是：將棧頂指針加1,再將元素插入至指針?biāo)?/p>

指的位置。

2）退棧運(yùn)算

退棧運(yùn)算即將棧頂元素取出并賦給一個(gè)指定的變量。操作方式是：先將棧頂元素賦給指

定的變量，再將棧頂指針減1。

3）讀棧頂元素

將棧頂元素賦給某一指定變量，但棧頂指針不變。

2.隊(duì)列及其基本運(yùn)算

1）隊(duì)列

隊(duì)列即是允許在一端進(jìn)行插入，而在另一端進(jìn)行刪除的線性表。允許插入的一端稱(chēng)為隊(duì)

尾，通常用一個(gè)尾指針指向隊(duì)尾；允許刪除的一端稱(chēng)為隊(duì)首，通常用一個(gè)隊(duì)首指針指向排隊(duì)

元素的前個(gè)位置。

隊(duì)列遵循的規(guī)則是：先進(jìn)先出或后進(jìn)后出

2）循環(huán)隊(duì)列及其運(yùn)算

隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)?般采用循環(huán)隊(duì)列的形式。

循環(huán)隊(duì)列，即是次隊(duì)列存儲(chǔ)空間的最后?個(gè)位置繞到第一個(gè)位置，形成邏輯上的環(huán)狀空

間，供隊(duì)列循環(huán)使用。

在循環(huán)隊(duì)列中，用隊(duì)尾指針rear指向隊(duì)列中的隊(duì)尾元素，用排頭指針front指向排頭

元素的前一個(gè)位置，因此，從排頭指針front指向的后一個(gè)位置到隊(duì)尾指針rear指向的位

置之間所有的元素均為隊(duì)列中的元素。

循環(huán)隊(duì)列的初始狀態(tài)為空，即rear=front=m。這里m即為隊(duì)列的存儲(chǔ)空間。

循環(huán)隊(duì)列的基本運(yùn)算：入隊(duì)運(yùn)算和退隊(duì)運(yùn)算。

入隊(duì)運(yùn)算：每進(jìn)行一次入隊(duì)運(yùn)算，隊(duì)尾指針加1。當(dāng)隊(duì)尾指針rear=m+l時(shí)，即表示隊(duì)

列空間的尾部已經(jīng)放置了元素，則下一個(gè)元素應(yīng)該旋轉(zhuǎn)到隊(duì)列空間的首部，即rear=l

退隊(duì)運(yùn)算：每退隊(duì)一個(gè)元素，排頭指針加1。當(dāng)排頭指針front=m+l時(shí)，即排頭指針指

向隊(duì)列空間的尾部，退隊(duì)后，排頭指針指向隊(duì)列空間的開(kāi)始，即front=l。

在隊(duì)列操作時(shí)，循環(huán)隊(duì)列滿(mǎn)時(shí)，front=rear,隊(duì)列空時(shí),也有rear=front,即在隊(duì)列

空或滿(mǎn)時(shí)，排頭指針和隊(duì)尾指針均指向同一個(gè)位置。要判斷隊(duì)列空或滿(mǎn)時(shí)，還應(yīng)增加一個(gè)標(biāo)

志，s值的定義：

_JO表示隊(duì)列空

表示隊(duì)列滿(mǎn)

判斷隊(duì)列空與隊(duì)列滿(mǎn)的條件下：

隊(duì)列空的條件：s=0

隊(duì)列滿(mǎn)的條件：s=l、front=rear

（1）入隊(duì)運(yùn)算

即在隊(duì)尾加入一個(gè)新元素。這個(gè)運(yùn)算有兩個(gè)基本操作：首先，將隊(duì)尾指針加1,即

rear=rear+l,當(dāng)rear=m+l時(shí)，置rear=l,然后，將新元素插入到隊(duì)尾指針指向的位置。

當(dāng)循環(huán)隊(duì)列非空（s=l）,且front=rear時(shí)，隊(duì)列滿(mǎn)，不能進(jìn)行入隊(duì)操作。此情況稱(chēng)''上

溢”。

（2）退隊(duì)操作

即將隊(duì)首的元素賦給一個(gè)指定的變量。該運(yùn)算也有兩個(gè)基本操作：首先，將排頭指針加

1,即front=front+L當(dāng)front=m+l時(shí),置front=l,然后，將排頭指針指向的元素賦給指

定的變量。

當(dāng)循環(huán)隊(duì)列為空（s=0）時(shí)，不能進(jìn)行退隊(duì)運(yùn)算。此種情況稱(chēng)為“下溢”。

（五）線性鏈表

1.基本概念

前面的線性表均是采用順序存儲(chǔ)結(jié)構(gòu)及在順序存儲(chǔ)結(jié)構(gòu)下的運(yùn)算。

1）順序存儲(chǔ)的優(yōu)點(diǎn):

?結(jié)構(gòu)簡(jiǎn)單

?運(yùn)算方便

2）順序存儲(chǔ)結(jié)構(gòu)的缺點(diǎn)：

?要在順序存儲(chǔ)的線性表中插入一個(gè)新元素或刪除一個(gè)元素時(shí)，為了保證插入或刪除

后的線性表仍然為順序存儲(chǔ)。在插入或刪除元素時(shí)，需要移動(dòng)大量的數(shù)據(jù)元素，因

此運(yùn)算效率較低。

?如果一個(gè)線性表分配順序存儲(chǔ)空間后，如果出現(xiàn)線性表的存儲(chǔ)空間已滿(mǎn)，但還需要

插入元素時(shí).，會(huì)發(fā)生“上溢”錯(cuò)誤。

?在實(shí)際應(yīng)用時(shí)，可能有多個(gè)線性表同時(shí)使用存儲(chǔ)空間，這樣給存儲(chǔ)空間的分配帶來(lái)

問(wèn)題，有可能使有的隊(duì)列空間不夠或過(guò)多造成浪費(fèi)。

基于上述情況，對(duì)于大的線性表或元素變動(dòng)頻繁的大線性表不宜采用順序存儲(chǔ)結(jié)構(gòu)，而

應(yīng)采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。

3）鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

假設(shè)每一個(gè)數(shù)據(jù)結(jié)點(diǎn)對(duì)應(yīng)一個(gè)存儲(chǔ)單元，該存儲(chǔ)單元稱(chēng)為存儲(chǔ)結(jié)點(diǎn)，簡(jiǎn)稱(chēng)結(jié)點(diǎn)。

在鏈?zhǔn)酱鎯?chǔ)方式中，要求每一個(gè)結(jié)點(diǎn)由兩部分組成：一部分用于存放數(shù)據(jù)元素，你為數(shù)

據(jù)域；另一部分用于存放指針，稱(chēng)為指針域。該指針用于指向該結(jié)點(diǎn)的前一個(gè)或后一個(gè)結(jié)點(diǎn)。

在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中，存儲(chǔ)數(shù)據(jù)結(jié)構(gòu)的存儲(chǔ)空間可以不連續(xù)，各數(shù)據(jù)結(jié)點(diǎn)的存儲(chǔ)順序與數(shù)

據(jù)元素之間的邏輯關(guān)系不一致，而數(shù)據(jù)元素之間的邏輯關(guān)系是由指針域來(lái)確定的。

鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)既可以用于線性結(jié)構(gòu)，也可用于非線性結(jié)構(gòu)。

4）線性鏈表

線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)稱(chēng)為線性鏈表。

將存儲(chǔ)空間劃分成若干的小塊，每塊占用若干個(gè)字節(jié)，這些小塊稱(chēng)為存儲(chǔ)結(jié)點(diǎn)。

將存儲(chǔ)結(jié)點(diǎn)分為兩個(gè)部分，一部分用于存儲(chǔ)數(shù)據(jù)元素的值，稱(chēng)為數(shù)據(jù)域：另一部分用于

存儲(chǔ)元素之間的前后件關(guān)系，即存放下一個(gè)元素在存儲(chǔ)序號(hào)（即存儲(chǔ)地址），即指向后件結(jié)

點(diǎn)，稱(chēng)為指針域。

在線性鏈表中用一個(gè)專(zhuān)門(mén)的指針HEAD指向線性鏈表中第一個(gè)數(shù)據(jù)元素的結(jié)點(diǎn)（即存放

第一個(gè)元素的地址）。線性表中最后一個(gè)元素沒(méi)有后件，因此，線性鏈表中的最后一個(gè)結(jié)點(diǎn)

的指針域?yàn)榭眨ㄓ肗ull或0表示），表示鏈終結(jié)。

在線性鏈表中，各元素的存儲(chǔ)序號(hào)是不連續(xù)的，元素間的前后件關(guān)系與位置關(guān)系也是不

一致的。在線性鏈表中，前后件的關(guān)系依靠各結(jié)點(diǎn)的指針來(lái)指示，指向表的第一個(gè)元素的指

針HEAD稱(chēng)為頭指針，當(dāng)HEAD=NULL時(shí)，表示該鏈表為空。

對(duì)于線性鏈表，可以從頭指針開(kāi)始，沿著各結(jié)點(diǎn)的指針掃描到鏈表中的所有結(jié)點(diǎn)。

這種線性鏈表稱(chēng)為線性單鏈表，即可以從表頭開(kāi)始向后掃描鏈表中的所有結(jié)點(diǎn)，而不能

從中間或表尾結(jié)點(diǎn)向前掃描位于該結(jié)點(diǎn)之前的元素。

這種鏈表結(jié)構(gòu)的缺點(diǎn)是不能任意地對(duì)鏈表中的元素按下同的方向進(jìn)行掃描。在某些應(yīng)用

時(shí)，如果對(duì)鏈表中的元素設(shè)置兩個(gè)指針域，一個(gè)為指向前件的指針域，稱(chēng)為左指針（LLink）,

一個(gè)為指向后件的指針域，稱(chēng)為右指針（RLink）。則這種鏈表是雙向鏈表。

5）帶鏈的棧

帶鏈的棧即是用來(lái)收集計(jì)算機(jī)存儲(chǔ)空間中的所有空閑的存儲(chǔ)結(jié)點(diǎn)，這種帶鏈的棧稱(chēng)為可

利用棧。

當(dāng)需要存儲(chǔ)結(jié)點(diǎn)時(shí)，即從可利用的棧的頂部取出棧頂結(jié)點(diǎn)；當(dāng)系統(tǒng)要釋放一個(gè)存儲(chǔ)結(jié)點(diǎn)

時(shí).，將該結(jié)點(diǎn)空間放回到可利用棧的棧頂。

即在計(jì)算機(jī)中所有空閑的空間，均可以以結(jié)點(diǎn)的方式鏈接到可利用棧中，隨著其他線性

鏈表中結(jié)點(diǎn)的插入與刪除，可利用棧處于動(dòng)態(tài)變化之中，即可利用棧經(jīng)常要進(jìn)行退棧和入棧

操作。

6）帶鏈的隊(duì)列

隊(duì)列也是線性表，也可利用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)來(lái)進(jìn)行保存。

2.線性鏈表的基本運(yùn)算

線性鏈表包括的基本運(yùn)算：

?在鏈表中包含指定元素的結(jié)點(diǎn)之前插入一個(gè)新元素

?在鏈表中刪除包含指定元素的結(jié)點(diǎn)

?將兩個(gè)線性鏈表按要求合并成一個(gè)線性鏈表

?將一個(gè)線性鏈表按要求進(jìn)行分解

?逆轉(zhuǎn)線性鏈表

?復(fù)制線性鏈表

?線性鏈表的排序

?線性鏈表的查找

1）線性鏈表中查找指定的元素

在線性鏈表中查找元素x：從頭指針指向的結(jié)點(diǎn)開(kāi)始往后沿指針進(jìn)行掃描，直到后面已

沒(méi)有結(jié)點(diǎn)或下一個(gè)結(jié)點(diǎn)的數(shù)據(jù)域?yàn)閄為止。

元素的查找，經(jīng)常是為了進(jìn)行插入或刪除操作而進(jìn)行的，因此，在查找時(shí)，往往是需要

記錄下該結(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn)。

2）線性鏈表的插入

線性鏈表的插入即在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的線性表中插入一個(gè)新元素。

在線性鏈表中包含元素x的結(jié)點(diǎn)之前插入新元素b,插入過(guò)程：

（1）從可利用棧中取得一個(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)椴迦氲脑刂礲。

（2）在線性鏈表中尋找包含元素x的前一個(gè)結(jié)點(diǎn)，該結(jié)點(diǎn)的存儲(chǔ)序號(hào)為q。

（3）將結(jié)點(diǎn)p插入到結(jié)點(diǎn)q之后。具體的操作：首先，使結(jié)點(diǎn)p插入到結(jié)點(diǎn)q之后（即

結(jié)點(diǎn)q的后件結(jié)點(diǎn)），然后，使結(jié)點(diǎn)q的指針域內(nèi)容改為指向結(jié)點(diǎn)P。

線性鏈表的插入操作，新結(jié)點(diǎn)是為來(lái)自于可利用棧，因此不會(huì)造成線性表的溢出。同樣,

由于可利用?？杀欢鄠€(gè)線性表利用，因此，不會(huì)造成存儲(chǔ)空間的浪費(fèi)，大家動(dòng)態(tài)地共同使用

存儲(chǔ)空間。

3）線性鏈表的刪除

線性鏈表的刪除，即是在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)卜的線性表中刪除指定元素的結(jié)點(diǎn)。

操作方式：

（1）在線性表中找到包含指定元素X的前一個(gè)結(jié)點(diǎn)P

（2）將該結(jié)點(diǎn)p后的包含元素x的結(jié)點(diǎn)從線性鏈表中刪除，然后將被刪除結(jié)點(diǎn)的后一

個(gè)結(jié)點(diǎn)q的地址提供給結(jié)點(diǎn)P的指針域，即將結(jié)點(diǎn)P指向結(jié)點(diǎn)q。

（3）將刪除的結(jié)點(diǎn)送回可利用棧。

從以上的刪除操作可見(jiàn)，刪除一個(gè)指定的元素，不需要移動(dòng)其他的元素即可實(shí)現(xiàn)，這是

順序存儲(chǔ)的線性表所不能實(shí)現(xiàn)的。同時(shí)，此操作還可更有效地利用計(jì)算機(jī)的存儲(chǔ)空間。

3.循環(huán)鏈表及其基本操作

在線性鏈表中，雖然對(duì)數(shù)據(jù)元素的插入和刪除操作比較簡(jiǎn)單，但由于它對(duì)第一個(gè)結(jié)點(diǎn)和

空表需要單獨(dú)處理，使得空表與非空表的處理不??致。

循環(huán)鏈表，即是采用另一種鏈接方式，它的特點(diǎn)如下：

(1)在循環(huán)鏈表中增加一個(gè)表頭結(jié)點(diǎn)，其數(shù)據(jù)域?yàn)槿我饣蚋鶕?jù)需要來(lái)設(shè)置，指針域指

向線性表的第一個(gè)元素的結(jié)點(diǎn)。循環(huán)鏈表的頭指針指向表頭結(jié)點(diǎn)。

(2)循環(huán)鏈表中最后一個(gè)結(jié)點(diǎn)的指針域不是空的，而是指向表頭結(jié)點(diǎn)。在循環(huán)鏈表中，

所有結(jié)點(diǎn)的指針構(gòu)成一個(gè)環(huán)狀鏈。

在循環(huán)鏈表中，只要指出表中任何一個(gè)結(jié)點(diǎn)的位置，均可以從它開(kāi)始掃描到所有的結(jié)點(diǎn)，

而線性鏈表做不到，線性鏈表是一種單向的鏈表，只能按照指針的方向進(jìn)行掃描。

循環(huán)鏈表中設(shè)置了一個(gè)表頭結(jié)點(diǎn)，因此，在任何時(shí)候都至少有一個(gè)結(jié)點(diǎn)，因此空表與非

空表的運(yùn)算相統(tǒng)一。

(六)樹(shù)與二叉樹(shù)

1.樹(shù)的基本概念

樹(shù)是一種簡(jiǎn)單的非線性結(jié)構(gòu)。在樹(shù)結(jié)構(gòu)中，數(shù)據(jù)元素之間有著明顯的層次結(jié)構(gòu)。在樹(shù)的

圖形表示中，用直線連接兩端的結(jié)點(diǎn)，上端點(diǎn)為前件，下端點(diǎn)為后件。

在樹(shù)結(jié)構(gòu)中，每一個(gè)結(jié)點(diǎn)只有一個(gè)前件，稱(chēng)為父結(jié)點(diǎn)。如A即為結(jié)點(diǎn)B、C、D的父結(jié)點(diǎn)。

沒(méi)有父結(jié)點(diǎn)的結(jié)點(diǎn)只有個(gè)，稱(chēng)為根結(jié)點(diǎn)。如上圖所示，結(jié)點(diǎn)A即為根結(jié)點(diǎn)。

每一個(gè)結(jié)點(diǎn)可以有多個(gè)后件，它們均稱(chēng)為該結(jié)點(diǎn)的子結(jié)點(diǎn)。如結(jié)點(diǎn)G、H、I是結(jié)點(diǎn)D

的子結(jié)點(diǎn)。

沒(méi)有后件的結(jié)點(diǎn)，稱(chēng)為葉子結(jié)點(diǎn)。上圖中，葉子結(jié)點(diǎn)有：J、M、N、L、C、G、H、I。

在樹(shù)結(jié)構(gòu)中，一個(gè)結(jié)點(diǎn)所擁有的后件結(jié)點(diǎn)個(gè)數(shù)稱(chēng)為該結(jié)點(diǎn)的度。例如，結(jié)點(diǎn)D的度為3,

結(jié)點(diǎn)E的度為1等，按此原則，所有葉子結(jié)點(diǎn)的度均為0。

在樹(shù)中，所有結(jié)點(diǎn)中最大的度稱(chēng)為該樹(shù)的度。上圖所示的樹(shù)中，所有結(jié)點(diǎn)中最大的度是

3,所以該樹(shù)的度為3。

樹(shù)分層，根結(jié)點(diǎn)為第一層，往下依次類(lèi)推。同一層結(jié)點(diǎn)的所有子結(jié)點(diǎn)均在下一層。如上

圖：A結(jié)點(diǎn)在第1層，B、C、D結(jié)點(diǎn)在第2層；E、F、G、H、I在第3層；J、K、L在第4

層；M、N在第5層。

樹(shù)的最大層次稱(chēng)為樹(shù)的深度。上圖樹(shù)的深度為5o

在樹(shù)中，某結(jié)點(diǎn)的?個(gè)子結(jié)點(diǎn)為根構(gòu)成的樹(shù)稱(chēng)作該結(jié)點(diǎn)的子樹(shù)。葉子結(jié)點(diǎn)沒(méi)有子樹(shù)。

在計(jì)算機(jī)中，可以用樹(shù)來(lái)表示算術(shù)表達(dá)式。原則如下：

（1）表達(dá)式中每一個(gè)運(yùn)算符在樹(shù)中對(duì)應(yīng)??個(gè)結(jié)點(diǎn)，稱(chēng)為運(yùn)算符結(jié)點(diǎn)

（2）運(yùn)算符的每一個(gè)運(yùn)算對(duì)象在樹(shù)中為該運(yùn)算符結(jié)點(diǎn)的子樹(shù)（在樹(shù)中的順序?yàn)閺淖蟮?/p>

右）

（3）運(yùn)算對(duì)象中的單變量均為葉子結(jié)點(diǎn)

樹(shù)在計(jì)算機(jī)中用多重鏈表表示。多重鏈表中的每個(gè)結(jié)點(diǎn)描述了樹(shù)中對(duì)應(yīng)結(jié)點(diǎn)的信息，而

每個(gè)結(jié)點(diǎn)中的鏈域（即指針域）個(gè)數(shù)將隨著樹(shù)中該結(jié)點(diǎn)的度而定義。

如果在樹(shù)中，每一個(gè)結(jié)點(diǎn)的子結(jié)點(diǎn)的個(gè)數(shù)不相同，因此在多重鏈中各結(jié)點(diǎn)的鏈域個(gè)數(shù)也

不相同，會(huì)導(dǎo)致算法太復(fù)雜。因此，在樹(shù)中，常采用定長(zhǎng)結(jié)點(diǎn)來(lái)表示樹(shù)中的每一個(gè)結(jié)點(diǎn)，即

取樹(shù)的度作為每個(gè)結(jié)點(diǎn)的鏈域的個(gè)數(shù)。這樣，管理相對(duì)簡(jiǎn)化了，但會(huì)造成空間的浪費(fèi)，因?yàn)?/p>

有許多的結(jié)點(diǎn)存在空鏈域。

2.二叉樹(shù)及其基本性質(zhì)

1）二叉樹(shù)的定義

二叉樹(shù)的特點(diǎn)：

?非空二叉樹(shù)只有一個(gè)根結(jié)點(diǎn)

?每一個(gè)結(jié)點(diǎn)最多只有兩個(gè)子結(jié)點(diǎn),且結(jié)點(diǎn)分左右。則?個(gè)結(jié)點(diǎn)最多可以有兩棵子樹(shù),

分別稱(chēng)為左子樹(shù)和右子樹(shù)

在二叉樹(shù)中，每一個(gè)結(jié)點(diǎn)的度最大為2,即二叉樹(shù)的度為2。在二叉樹(shù)中，任何的子樹(shù)

也均為二叉樹(shù)。

在二叉樹(shù)中，每一個(gè)結(jié)點(diǎn)的子樹(shù)被分為左子樹(shù)和右子樹(shù)。在二叉樹(shù)中，允許某一個(gè)結(jié)點(diǎn)

只有左子樹(shù)或只有右子樹(shù)。如果一個(gè)結(jié)點(diǎn)既沒(méi)有左子樹(shù)，也沒(méi)有右子樹(shù)，則該結(jié)點(diǎn)為葉子結(jié)

點(diǎn)。

2）二叉樹(shù)的性質(zhì)

性質(zhì)1：在二叉樹(shù)的第k層上，最多有2卜‘（k》l）個(gè)結(jié)點(diǎn)。

性質(zhì)2：深度為m的二叉樹(shù)最多有2-1個(gè)結(jié)點(diǎn)。

性質(zhì)3：在任意一棵二叉樹(shù)中，度為0的結(jié)點(diǎn)（即葉子結(jié)點(diǎn)）總比度為2的結(jié)點(diǎn)多一個(gè)。

性質(zhì)4：具有n個(gè)結(jié)點(diǎn)的二叉樹(shù)，其深度至少為［log2n］+l,其中［logzn］表示logzn的

整數(shù)部分。

3）滿(mǎn)二叉樹(shù)與完全二叉樹(shù)

（1）滿(mǎn)二叉樹(shù)

滿(mǎn)二叉樹(shù)的特點(diǎn)：

除最后一層外，每一層上的所有結(jié)點(diǎn)都有兩個(gè)子結(jié)點(diǎn)。即在滿(mǎn)二叉樹(shù)中，每一層上的結(jié)

點(diǎn)數(shù)都達(dá)到最大值，即在滿(mǎn)二叉樹(shù)上的第k層上有個(gè)結(jié)點(diǎn)。如下即為一棵滿(mǎn)二叉樹(shù)。

滿(mǎn)二叉樹(shù)

(2)完全二叉樹(shù)

特點(diǎn)：除最后一層外，每一層上的結(jié)點(diǎn)數(shù)均達(dá)到最大值，在最后一層上只缺少右邊的若

干個(gè)結(jié)點(diǎn)。

即如果從根結(jié)點(diǎn)開(kāi)始，對(duì)二叉樹(shù)的結(jié)點(diǎn)自上而下、自左而右用自然數(shù)進(jìn)行連續(xù)編號(hào)，則

深度為m、且有n個(gè)結(jié)點(diǎn)的二叉樹(shù)，當(dāng)且僅當(dāng)其每一個(gè)結(jié)點(diǎn)都與深度為m的滿(mǎn)二叉樹(shù)中編號(hào)

從1到n的結(jié)點(diǎn)一一對(duì)應(yīng)，則是完全二叉樹(shù)。

對(duì)于完全二叉樹(shù)，葉子結(jié)點(diǎn)只能在層次最大的兩層中出現(xiàn)；對(duì)于任何一個(gè)結(jié)點(diǎn)，若其右

完全二叉樹(shù)

分支下的子樹(shù)結(jié)點(diǎn)的最大層次為p,則其分支下的子孫結(jié)點(diǎn)的最大層次為p或p+屋

完全二叉樹(shù)具有的性質(zhì)：

性質(zhì)5：具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為[logzn]+l

性質(zhì)6：設(shè)完全二叉樹(shù)共有n個(gè)結(jié)點(diǎn)。如果從根結(jié)點(diǎn)開(kāi)始，按層次(每一層從左到右)

用自然數(shù)1、2……、n給結(jié)點(diǎn)編號(hào)，對(duì)于編號(hào)為k(k=l,2,……n)的結(jié)點(diǎn)有如下結(jié)論：

①若k=l,則該結(jié)點(diǎn)為根結(jié)點(diǎn)，它沒(méi)有父結(jié)點(diǎn)；若k>l,則該結(jié)點(diǎn)的父結(jié)點(diǎn)編號(hào)為

INT(k/2)o

②若兼Wn,則編號(hào)為k的結(jié)點(diǎn)的左子結(jié)點(diǎn)編號(hào)為2k；否則該結(jié)點(diǎn)無(wú)左子結(jié)點(diǎn)(當(dāng)然

也沒(méi)有右子結(jié)點(diǎn))

③若2k+lWn,則編號(hào)為k的結(jié)點(diǎn)的右子結(jié)點(diǎn)編號(hào)為2k+l；否則該結(jié)點(diǎn)無(wú)右子結(jié)點(diǎn).

3.二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)

二叉樹(shù)的存儲(chǔ)常采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。

存儲(chǔ)二叉樹(shù)中各元素的存儲(chǔ)結(jié)點(diǎn)由兩個(gè)部分組成：數(shù)據(jù)域和指針域。在二叉樹(shù)中，由于

每個(gè)結(jié)點(diǎn)可有兩個(gè)子結(jié)點(diǎn)，則它的指針域有兩個(gè)：一個(gè)用于存儲(chǔ)該結(jié)點(diǎn)的左子結(jié)點(diǎn)的存儲(chǔ)地

址，即稱(chēng)為左指針域；個(gè)用于存儲(chǔ)指向該結(jié)點(diǎn)的右子結(jié)點(diǎn)的存儲(chǔ)地址，稱(chēng)為右指針域。

存儲(chǔ)結(jié)構(gòu)如下：

LehiIdValueRchild

i|L(i)|V(i)|R(i)

即二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)中每一個(gè)存儲(chǔ)結(jié)點(diǎn)都有兩個(gè)指針域，因此，二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

也稱(chēng)為二叉樹(shù)的鏈表。在二叉樹(shù)在存儲(chǔ)中，用一個(gè)頭指針指向二叉樹(shù)的根結(jié)點(diǎn)的存儲(chǔ)地址。

如圖所示的二叉樹(shù)：

中的存放方式是:

iL(i)V(i)R(i)

BT玲12A3

24B5

36C7

48D9

510E11

612F13

714G15

816H17

918I0

100J0

110K0

120L0

130M0

140N0

15000

160P0

170Q0

180R0

當(dāng)然，對(duì)于滿(mǎn)二叉樹(shù)或完全二叉樹(shù)而言，也可采用順序存儲(chǔ)的方式，但順序存儲(chǔ)的方式

不適合其他的二叉樹(shù)。

4.二叉樹(shù)的遍歷

二叉樹(shù)的遍歷即是不重復(fù)地訪問(wèn)二叉樹(shù)的所有結(jié)點(diǎn)。

在遍歷二叉樹(shù)時(shí)，一般先遍歷左子樹(shù)，然后再遍歷右子樹(shù)。在先左后右的原則下，二叉

樹(shù)的遍歷又可分為三種：前序遍歷、中序遍歷和后序遍歷。

1）前序遍歷

前序遍歷即先訪問(wèn)根結(jié)點(diǎn)，然后遍歷左子樹(shù)，最后遍歷右子樹(shù)。在遍歷左子樹(shù)和遍歷右

子樹(shù)時(shí)，依然是先遍歷根結(jié)點(diǎn)，然后是左子樹(shù)，再是右子樹(shù)。

操作的具體方式：

?若二叉樹(shù)為空，則結(jié)束返回。

?否則：訪問(wèn)根結(jié)點(diǎn)f前序遍歷左子樹(shù)一前序遍歷右子樹(shù)

如上圖所示的完全二叉樹(shù)，它的前序遍歷結(jié)果是：A、B、D、H、P、Q、I、R、E、J、K、

C、F、L、M、G、N、0

2）中序遍歷

中序遍歷，即先遍歷左子樹(shù)，然后訪問(wèn)根結(jié)點(diǎn)，最后是遍歷右子樹(shù)。

具體的操作方式：

?若二叉樹(shù)為空，則結(jié)束返回。

?否則：中序遍歷左子樹(shù)-訪問(wèn)根結(jié)點(diǎn)f中序遍歷右子樹(shù)

這里強(qiáng)調(diào)，在遍歷左子樹(shù)和右子樹(shù)時(shí)，仍然要采用中序遍歷的方法。

如上圖所示的完全二叉樹(shù)，它的中序遍歷結(jié)果是：P、H、Q、D、R、I、B、J、E、K、A、

L、F、M、C、N、G、0

3）后序遍歷

后序遍歷，即選遍歷左子樹(shù)，然后是遍歷右子樹(shù)，最后訪問(wèn)根結(jié)點(diǎn)。

具體的操作方式：

?若二叉樹(shù)為空，則結(jié)束返回。

?否則：前序遍歷左子樹(shù)一前序遍歷右子樹(shù)—訪問(wèn)根結(jié)點(diǎn)

如上圖所示的完全二叉樹(shù)，它的后序遍歷結(jié)果是：P、Q、H、R、I、D、J、K、E、B、L、

M、F、N、0、G、C、A

（七）查找技術(shù)

查找即是指在一個(gè)給定的數(shù)據(jù)結(jié)構(gòu)中查找某個(gè)指定的元素。

1.順序查找

順序查找又稱(chēng)順序搜索。一般是在線性表中查找指定的元素。

基本操作方法是：

從線性表的第一個(gè)元素開(kāi)始，與被查元素進(jìn)行比較，相等則查找成功，否則繼續(xù)向后查

找。如果所有的元素均查找完畢后都不相等，則該元素在指定的線性表中不存在。

順序查找的最好情況：要查找的元素在線性表的第一個(gè)元素，則查找效率最高；如果要

查找的元素在線性表的最后或根本不存在，則查找需要搜索所有的線性表元素，這種情況是

最差情況。

對(duì)于線性表而言，順序查找效率很低。但對(duì)于以卜的線性表，也只能采用順序查找的方

法：

?線性表為無(wú)序表，即表中的元素沒(méi)有排列不是按大小順序進(jìn)行排列的，這類(lèi)線性表

不管它的存儲(chǔ)方式是順序存儲(chǔ)還是鏈?zhǔn)酱鎯?chǔ)，都只能按順序查找方式進(jìn)行查找

?即使是有序線性表，如果采用鏈?zhǔn)酱鎯?chǔ)，也只能采用順序查找方式

例如，現(xiàn)有線性表：7、2、1、5、9、4,要在序列中查找元素6,查找的過(guò)程是：

?整個(gè)線性表的長(zhǎng)度為5

?查找計(jì)次n=l,將元素6與序列的第一個(gè)7元素進(jìn)行比較，不等，繼續(xù)查找

?n=2,將6與第二個(gè)元素2進(jìn)行比較，不等，繼續(xù)

?n=3,將6與第三個(gè)元素1進(jìn)行比較，不等，繼續(xù)

?n=4,將6與第四個(gè)元素5進(jìn)行比較，不等，繼續(xù)

?n=5,將6與第五個(gè)元素9進(jìn)行比較，不等，繼續(xù)

?"6,將6與第六個(gè)元素4進(jìn)行比較，不等，繼續(xù)

?n=7,超出線性表的長(zhǎng)度，查找結(jié)束，則該表中不存在要查找的元素。

2.二分查找

二分查找只適用于順序存儲(chǔ)的有序表。此處所述的有序表是指線性中的元素按值非遞減

排列（即由小到大，但允許相鄰元素值相等）。

二分查找的方法如下：

將要查找的元素與有序序列的中間元素進(jìn)行比較：

?如果該元素比中間元素大，則繼續(xù)在線性表的后半部分（中間項(xiàng)以后的部分）進(jìn)行

查找

?如果要查找的元素的值比中間元素的值小，則繼續(xù)在線性表的前半部分（中間項(xiàng)以

前的部分）進(jìn)行查找

這個(gè)查找過(guò)程一直按相同的順序進(jìn)行下去，一直到查找成功或子表長(zhǎng)度為o（說(shuō)明線性

表中沒(méi)有要查找的元素）

有序線性表的二分法查找，條件是必須這個(gè)有序線性表的存儲(chǔ)方式是順序存儲(chǔ)的。它的

查找效率比順序查找要高得多，它的最壞情況的查找次數(shù)是log2n次，而順序查找的最壞情

況的查找次數(shù)是n次。

當(dāng)然，二分查找的方法也支持順序存儲(chǔ)的遞減序列的線性表。

有非遞減有序線性表：1、2、4、5、7、9,要查找元素6。查找的方法是：

?序列長(zhǎng)度為n=6,中間元素的序號(hào)m=[（n+l）/2]=3

?查找計(jì)次k=l,將元素6與中間元素即元素4進(jìn)行比較，不等，6>4

?查找計(jì)次k=2,查找繼續(xù)在后半部分進(jìn)行，后半部分子表的長(zhǎng)度為3,計(jì)算中間元

素的序號(hào)：m=3+[（3+l）/2]=5,將元素與后半部分的中間項(xiàng)進(jìn)行比較，即第5個(gè)元

素中的7進(jìn)行比較，不等，6<7

?查找計(jì)次k=3,繼續(xù)查找在后半部分序列的前半部分子序列中查找，子表長(zhǎng)度為1,

則中間項(xiàng)序號(hào)即為m=3+[（l+l）/2]=4,即與第4個(gè)元素5進(jìn)行比較，不相等，繼續(xù)

查找的子表長(zhǎng)度為0,則查找結(jié)束

（A）排序技術(shù)

排序即是將一個(gè)無(wú)序的序列整理成按值非遞減順序排列的有序序列。在這里，我們討論

的是順序存儲(chǔ)的線性表的排序操作。

1.交換類(lèi)排序法

交換類(lèi)排序法，即是借助于數(shù)據(jù)元素之間的互相交換進(jìn)行排序的方法。

1）冒泡排序法

冒泡排序法即是利用相鄰數(shù)據(jù)元素之間的交換逐步將線性表變成有序序列的操作方法。

操作過(guò)程如下：

?從表頭開(kāi)始掃描線性表，在掃描過(guò)程中逐次比較相鄰兩個(gè)元素的大小，若相鄰兩個(gè)

元素中前一個(gè)元素的值比后一個(gè)元素的值大，將兩個(gè)元素位置進(jìn)行交換，當(dāng)掃描完

成一遍時(shí)，則序列中最大的元素被放置到序列的最后。

?再繼續(xù)對(duì)序列從頭進(jìn)行掃描，這一次掃描的長(zhǎng)度是序列長(zhǎng)度減1,因?yàn)樽畲蟮脑?/p>

已經(jīng)就位了，采用與前相同的方法，兩兩之間進(jìn)行比較，將次大數(shù)移到子序列的末

尾。

?按相同的方法繼續(xù)掃描，每次掃描的子序列的長(zhǎng)度均比上?次減1,直至子序列的

長(zhǎng)度為1時(shí)，排序結(jié)束。

例如，有序列5、2、9、4、1、7、6,將該序列從小到大進(jìn)行排列。

采用冒泡排序法，具體操作步驟如下：

序列長(zhǎng)度n=7

原序列5294176

第一遍（從前往后）5<-->294176

259<-->4176

2549<-->176

23419<-->76

254179<-->6

第一遍結(jié)束后2541769

第二遍（從前往后）25<-->41769

245<-->1769

24157——69

2415679

第二遍結(jié)束后2415679

第三遍（從前往后）24<-->15679

2145679

第三遍結(jié)束2145679

第四遍（從前往后）2<-->145679

1245679

第四遍結(jié)束1245679

最后結(jié)果1245679

掃描的次數(shù)，最多需要掃描n-1次，如果序列已經(jīng)就位，則掃描結(jié)束。測(cè)試是否已經(jīng)就

位，可設(shè)置一個(gè)標(biāo)志，如果該次掃描沒(méi)有數(shù)據(jù)交換，則說(shuō)明數(shù)據(jù)排序結(jié)束。

2）快速排序法

冒泡排序方法每次交換只能改變相鄰兩個(gè)元素之間的逆序，速度相對(duì)較慢。如果將兩個(gè)

不相鄰的元素之間進(jìn)行交換，可以消除多個(gè)逆序。

快速排序的方法是：

從線性表中選取一個(gè)元素，設(shè)為T(mén),將線性表后面小于T的元素移到前面，而前面大于

T的元素移到后面，結(jié)果將線性表分成兩個(gè)部分（稱(chēng)為兩個(gè)子表），T插入到其分界線的位置

處，這個(gè)過(guò)程稱(chēng)為線性表的分割。對(duì)過(guò)對(duì)線性表的一次分割，就以T為分界線，將線性表分

成前后兩個(gè)子表，且前面子表中的所有元素均不大于T,而后面的所有元素均不小于T。

再將前后兩個(gè)子表再進(jìn)行相同的快速排序，將子表再進(jìn)行分割，直到所有的子表均為空,

則完成快速排序操作。

在快速排序過(guò)程中，隨著對(duì)各子表不斷的進(jìn)行分割，劃分出的子表會(huì)越來(lái)越多，但一次

又只能對(duì)一個(gè)子表進(jìn)行分割處理，需要將暫時(shí)不用的子表記憶起來(lái)，這里可用棧來(lái)實(shí)現(xiàn)。

對(duì)某個(gè)子表進(jìn)行分割后，可以將分割出的后一個(gè)子表的第一個(gè)元素與最后一個(gè)元素的位

置壓入棧中，而繼續(xù)對(duì)前一個(gè)子表進(jìn)行再分割；當(dāng)分割出的子表為空時(shí)，可以從棧中退出一

個(gè)子表進(jìn)行分割。

這個(gè)過(guò)程直到校為空為止，說(shuō)明所有子表為空，沒(méi)有子表再需分割，排序就完成。

2.插入類(lèi)排序法

1)簡(jiǎn)單插入排序

插入排序，是指將無(wú)序序列中的各元素依次插入到已經(jīng)有序的線性表中。

插入排序操作的思路：在線性表中，只包含第1個(gè)元素的子表，作為該有序表。從線性

表的第2個(gè)元素開(kāi)始直到最后一個(gè)元素,逐次將其中的每一個(gè)元素插入到前面的有序的子表

中。

該方法與冒泡排序方法的效率相同，最壞的情況下需要n(n-D/2次比較。

例如,有序列5、2、9、4、1、7、6,將該序列從小到大進(jìn)行排列。

采用簡(jiǎn)單插入排序法，具體操作步驟如下：

序列長(zhǎng)度n=7

5294176

Tj二2

2594176

Tj=3

2594176

tj=4

2459176

Tj=5

1245976

tj=6

1245796

Tj=7

插入排序后的結(jié)果1245679

2)希爾排序法

希爾排序法的基本思想：

將整個(gè)無(wú)序序列分割成若干小的子序列分別進(jìn)行插入排序。

子序列的分割方法：將相隔某個(gè)增量h的元素構(gòu)成一個(gè)子序列，在排序的過(guò)程中，逐次

減小這個(gè)增量，最后當(dāng)h減小到1時(shí)，再進(jìn)行一次插入排序操作，即完成排序。

k

增量序列--般取h.=n/2(k=l,2,-,[log2n]),其中n為待排序序列的長(zhǎng)度。

3.選擇類(lèi)排序法

1)簡(jiǎn)單選擇排序法

基本思路：掃描整個(gè)線性表，從中選出最小的元素，將它交換到表的最前面，然后對(duì)后

面的子表采用相同的方法，直到子表為空為止。

對(duì)于長(zhǎng)度為n的序列，需要掃描n-1次，每一次掃描均找出剩余的子表中最小的元素,

然后將該最小元素與子表的第一個(gè)元素進(jìn)行交換。

例如,有序列5、2、9、4、1、7、6,將該序列從小到大進(jìn)行排列。

采用簡(jiǎn)單選擇排序法，具體操作步驟如下:

原序列5294176

第一遍掃描1294576

第二遍掃描1294576

第三遍掃描1249576

第四遍掃描1245976

第五遍掃描1245679

第六遍掃描1245679

排序結(jié)果1245679

2）堆排序法

堆排序法屬于選擇類(lèi)排序方法。

堆的定義：具有n個(gè)元素的序列（M兒,…,h.），當(dāng)且僅當(dāng)滿(mǎn)足

/?,>兒,.一/?,<人

,或，'，」（1=1,2,…,n/2）時(shí)稱(chēng)之為堆。

4>h2j+lhj<h2j+l

本節(jié)只討論滿(mǎn)足前者條件的堆。

由堆的定義看，堆頂元素（即第一個(gè)元素）必為最大項(xiàng)。

可以用?維數(shù)組或完全二叉樹(shù)來(lái)表示堆的結(jié)構(gòu)。

用完全二叉樹(shù)表示堆時(shí)，樹(shù)中所有非葉子結(jié)點(diǎn)值均不小于其左右子樹(shù)的根結(jié)點(diǎn)的值，因

此堆頂（完全二叉樹(shù)的根結(jié)點(diǎn)）元素必須為序列的n個(gè)元素中的最大項(xiàng)。

例如，有序列5、2、9、4、1、7、6,將該序列從小到大進(jìn)行排列。

利用堆排序法將該序列進(jìn)行排序。

無(wú)序堆調(diào)整根結(jié)點(diǎn)調(diào)整子樹(shù)的根結(jié)點(diǎn)

建堆的過(guò)程

操作方式即：先將無(wú)序堆的根結(jié)點(diǎn)5與左右子樹(shù)的根結(jié)點(diǎn)2、9進(jìn)行比較，5<9,將5

與9進(jìn)行交換；整后，對(duì)左右子樹(shù)進(jìn)行堆調(diào)整，左子樹(shù)的根結(jié)點(diǎn)2小于其左葉子結(jié)點(diǎn)5,調(diào)

整；右子樹(shù)的根結(jié)點(diǎn)5小于其左右子結(jié)點(diǎn)7和6,根據(jù)堆的要求，將5與7進(jìn)行調(diào)整。

根據(jù)堆的定義，可以得到堆排序的方法：

（1）首先將一個(gè)無(wú)序序列建成堆

（2）然后將堆頂元素（序列中的最大項(xiàng)）與堆中最后一個(gè)元素交換（最大項(xiàng)應(yīng)該在序

列的最后）。

三、例題分析

1.選擇題

1)算法指的是

A)計(jì)算機(jī)程序B)解決問(wèn)題的計(jì)算方法

O排序算法D)解決問(wèn)題的有限運(yùn)算序列

【答案】D

2)線性表采用鏈?zhǔn)酱鎯?chǔ)時(shí)，結(jié)點(diǎn)的存儲(chǔ)地址

A)必須是不連續(xù)的B)連續(xù)與否均可

C)必須是連續(xù)的D)和頭結(jié)點(diǎn)的存儲(chǔ)地址相連續(xù)

【答案】B

3)將長(zhǎng)度為n的單鏈表鏈接在長(zhǎng)度為m的單鏈表之后的算法的時(shí)間復(fù)雜度為

A)0(1)B)0(n)C)0(m)D)0(m+n)

【答案】C

5)樹(shù)型結(jié)構(gòu)最適合用來(lái)描述

A)有序的數(shù)據(jù)元素

B)無(wú)序的數(shù)據(jù)元素

C)數(shù)據(jù)元素之間的具有層次關(guān)系的數(shù)據(jù)

D)數(shù)據(jù)元素之間沒(méi)有關(guān)系的數(shù)據(jù)

【答案】C

6)若深度為5的完全二叉樹(shù)的第5層有3個(gè)葉結(jié)點(diǎn)，則該二叉樹(shù)的結(jié)點(diǎn)數(shù)是

A)15B)16C)17D)18

【答案】D

7)若某完全二叉樹(shù)的深度為h,則該完全二叉樹(shù)中至少有多少個(gè)結(jié)點(diǎn)

A)2"B)2"-1C)2H1ID)2h''+l

【答案】B

8)在非空二叉樹(shù)的中序遍歷序列中，二叉樹(shù)的根結(jié)點(diǎn)的左邊應(yīng)該

A)只有左子樹(shù)上的所有結(jié)點(diǎn)B)只有左子樹(shù)上的部分結(jié)點(diǎn)

C)只有右子樹(shù)上的所有結(jié)點(diǎn)D)只有右子樹(shù)上的部分結(jié)點(diǎn)

【答案】A

9)設(shè)數(shù)組data[m]作為循環(huán)隊(duì)列SQ的存儲(chǔ)空間，front為隊(duì)頭指針，rear為隊(duì)尾指針，

則執(zhí)行出隊(duì)操作后其頭指針front值為

A)front=front+lB)front=(front+l)%(m-l)

C)front=(front-1)%mD)front=(front+l)%m

【答案】D

10)用某種排序方法對(duì)關(guān)鍵字序列(25,84,21,47,15,27,68,35,20)進(jìn)行排序

時(shí)，序列的變化情況如下：

20,15,21,25,47,27,68,35,8