《大學(xué)計(jì)算機(jī)基礎(chǔ)》 第8章數(shù)據(jù)結(jié)構(gòu)與算法

《大學(xué)計(jì)算機(jī)基礎(chǔ)》

第8章數(shù)據(jù)結(jié)皮與算法

福格是什么7

程序:數(shù)據(jù)結(jié)構(gòu)+算法!

大連民族學(xué)院計(jì)算機(jī)學(xué)院趙丕錫教授

例：某校對(duì)100個(gè)學(xué)生進(jìn)行獎(jiǎng)勵(lì)，學(xué)生信息存在磁盤文件“file.dat”中,

條件是其三門成績?nèi)吭?0分以上才能進(jìn)行獎(jiǎng)勵(lì)，打印出被獎(jiǎng)勵(lì)學(xué)生

的學(xué)號(hào)。

□以C語言為例，程序代碼如卜.：

#include<stdio.h>

Voidmain()

{

structstu/*數(shù)據(jù)類型*/

{

intnum;

floatscore[3];

)a[100];/*定義變量*/

FILE*fp：IntIJ;

MM,

fp=fopen(file.datzT);/*打開文件file.dat*/

for(i=0;i<100;i++)

{

Fread(&a[i]zsizeof(structstu),l,fp);/*從文件中讀取數(shù)據(jù)*/

for(j=0;j<3;j++)

if(a[i].score[j]<90)/*判斷三門成績是否全都高于90分*/

break;

if(j>=3)/*如果符合條件，輸出其學(xué)號(hào)*/

printf(Mnum:%d\a[i].num);

}

Fclose(fp);

)由此可見，程序包括：對(duì)數(shù)據(jù)的描述，在程序中要指定數(shù)據(jù)的類型和數(shù)據(jù)的組織形式。

對(duì)操作的描述，即對(duì)數(shù)據(jù)的操作處理步驟

《大學(xué)計(jì)算機(jī)基礎(chǔ)》主講人：趙丕錫教授

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

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

對(duì)數(shù)據(jù)的描述。即在程序中要指定數(shù)據(jù)的類型和

數(shù)據(jù)的組織形式。

算法(algorithm)：

對(duì)操作的描述。即對(duì)數(shù)據(jù)的操作處理步驟。

程序：就是用計(jì)算機(jī)語言表示的數(shù)據(jù)結(jié)構(gòu)和算法。

程序設(shè)計(jì)：用計(jì)算機(jī)語言編寫程序的過程。兩個(gè)基本步驟：

工、設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)和算法。

2、用一種計(jì)算機(jī)語言表示出來。

因此，撤輾輅構(gòu)易算法是福格世計(jì)的基砒。

《大學(xué)計(jì)算機(jī)基礎(chǔ)》主講人：趙丕錫教授

8.1算法

8J」算法的基本概念

算法(algorithm)：對(duì)操作的描述。即對(duì)數(shù)據(jù)的操作處理

步驟。

算法的表示方法：

自然語言、流程圖、N-S流程圖、偽代碼、計(jì)算機(jī)語言

《大學(xué)計(jì)算機(jī)基礎(chǔ)》主講人：趙丕錫教授

案例：計(jì)算sum=1+2+3+.,?+n的算法

一、用自然語言描述

\輸即數(shù)據(jù)4數(shù)；

右設(shè)置累加器suniq初始制為『殳置計(jì)數(shù)器T

初始值為1。

3、當(dāng)i小于或等于n時(shí)，做累加，即將sum與i相

力口，其和再放入sum中。計(jì)數(shù)器i取下一個(gè)數(shù),

即i等于i+1，直到i大于n時(shí)終止。

4、輸出累加和sum。

《大學(xué)計(jì)算機(jī)基礎(chǔ)》主講人：趙丕錫教授

八流程圖描述：sum=l+2+3+…+n的算法

:開始；

/輸入n/

]

Sumv=O

iv=l

《大學(xué)計(jì)算機(jī)基礎(chǔ)》主講人：趙丕錫教授

二、N-S圖描述：sum=1+2+3+…+n的算法

N-S圖是美國學(xué)者I.Nassi和B.5岫。1(1。皿1211在1973年提出的一種流程圖,

其主要特點(diǎn)是不帶有流程線，整個(gè)算法完全寫在一個(gè)大的矩形框中。

N-S圖方式《大學(xué)計(jì)算機(jī)基礎(chǔ)》主講人：趙丕錫教授

四、偽代碼描述：sum=：L+2+3+.?.+ri的算法

就是用文字和符號(hào)的方式來描述算法。在實(shí)際應(yīng)用中，人們往往

用接近于某種程序語言的代碼形式作為偽代碼。這樣可以方便編程。

偽代碼方式

《大學(xué)計(jì)算機(jī)基礎(chǔ)》主講人：趙丕錫教授

五、計(jì)算機(jī)語言描述：程序

用C語言描述sum=1+2+3+…+n的算法____

Main()

{intn;

intsum=O,i=l;

scanf("％cT,&n);

for(i=l;i<=n;i++)

{sum=sum+i;}

printfCsum=%d\n\sum);

}

《大學(xué)計(jì)算機(jī)基礎(chǔ)》主講人：趙丕錫教授

一、算法的5個(gè)基本特征

工、可行性

2、確定性

3、有窮性

4、有零個(gè)或多個(gè)輸入

5、有一個(gè)或多個(gè)輸出

二、算法的2個(gè)基本要素

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

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

《大學(xué)計(jì)算機(jī)基礎(chǔ)》主講人：趙丕錫教授

算法的基本要素之一：對(duì)數(shù)據(jù)的運(yùn)算和操作

在計(jì)算機(jī)系統(tǒng)中，基本的運(yùn)算和操作有以下四類：

①算術(shù)運(yùn)算：主要包括加、減、乘、除等運(yùn)算。

②邏輯運(yùn)算：主要包括“邏輯與”、“邏輯或”、“邏輯非”

等運(yùn)算。

③關(guān)系運(yùn)算：主要包括“大于”、“大于或等于"、“小于”、

“小于或等于"、“等于”、“不等于”等運(yùn)算。

④數(shù)據(jù)傳輸：主要包括賦值、輸入、輸出等操作。

算法流程圖例子

《大學(xué)計(jì)算機(jī)基礎(chǔ)》主講人：趙丕錫教授

算法的基本要素之二：算法的控制結(jié)構(gòu)

控制結(jié)構(gòu)--算法中各種操作步驟之間的執(zhí)行順序。

順序結(jié)構(gòu)

港就選擇結(jié)構(gòu)

控制結(jié)構(gòu)

I循環(huán)結(jié)構(gòu)

算法流程圖例子

《大學(xué)計(jì)算機(jī)基礎(chǔ)》主講人：趙丕錫教授

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

六種：列舉法、姆納法、遹推、

遹歸、減4?遁雅技術(shù)、回溯法。

工、列舉法

列舉法就是根據(jù)所要解決的問題，把所有可

能的情況都一一列舉出來，并用問題中給定的條

件來檢驗(yàn)?zāi)男┦切枰?，哪些是不需要的?/p>

《大學(xué)計(jì)算機(jī)基礎(chǔ)》主講人：趙丕錫教授

2、歸納法

歸納法的基本思想是通過列舉少量的特殊情況，經(jīng)過分析,

最后找出一般的關(guān)系。

可以看出，歸納法可以解決列舉量為無限的問題。

3、遞推

遞推是指從已知的初始條件出發(fā)，逐步推出所要求的結(jié)果。

《大學(xué)計(jì)算機(jī)基礎(chǔ)》主講人：趙丕錫教授

4、遞歸

在解決某些復(fù)雜問題時(shí)，為了降低問題的復(fù)雜程度（如問題的

規(guī)模等），可以將問題逐層分解，最后歸結(jié)為一些最簡單的問題。

例8.2有5個(gè)人坐在一起，問第5個(gè)人多少歲？他說比第4個(gè)

人大2歲。問第4個(gè)人的歲數(shù)，他說比第3個(gè)人大2歲。問第3

個(gè)人，又說比第2個(gè)人大2歲。問第2個(gè)人，說比第1個(gè)人大2

歲。最后問第1個(gè)人，他說是10歲。請(qǐng)問第5個(gè)人多大？

《大學(xué)計(jì)算機(jī)基礎(chǔ)》主講人：趙丕錫教授

用遞歸方法求解，遞歸過程如下:

age(5)=age(4)十2

age(4)=age(3)十2

age(3)=age(2)十2

age(2)=age(1)十2

age(1)=10

《大學(xué)計(jì)算機(jī)基礎(chǔ)》主講人：趙丕錫教授

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

“減半”是指將問題的規(guī)模減半，而問題的性質(zhì)不變；

“遞推”是指重復(fù)“減半”的過程。

例8.3設(shè)方程f(x)=0在區(qū)間［a,b］上有實(shí)根，且f(a)與f(b)

符號(hào)相反，即f(a)f(b)<0。利用二分法求該方程在區(qū)間［a,

b］上的一個(gè)實(shí)根。

用二分法求方程實(shí)根的減半遞推過程如下：

首先計(jì)算區(qū)間的中點(diǎn)c=(a+b)/2,然后計(jì)算函數(shù)在中點(diǎn)c的值f

(c),并判斷f(c)是否為0。若f(c)=0,則說明c就是所求的根，

求解過程結(jié)束；如果f(c)#0,則根據(jù)以下原則將原區(qū)間減半：

《大學(xué)計(jì)算機(jī)基礎(chǔ)》主講人：趙丕錫教授

若f(a)f(c)<0,則取原區(qū)間的前半部分，；

若f(b)f(c)<0,則取原區(qū)間的后半部分。

最后根據(jù)計(jì)算精度的要求，判斷減半后的區(qū)間長度是否

已經(jīng)很?。?/p>

若|a—b|《￡,則過程結(jié)束，取(a+b)/2為根的近似值；

若|a—b|>e,則重復(fù)上述的減半過程。

《大學(xué)計(jì)算機(jī)基礎(chǔ)》主講人：趙丕錫教授

6、回溯法

對(duì)于某些問題，一種有效的方法是“試”，即通過對(duì)問

題的分析，找出一個(gè)解決問題的線索，然后沿著這個(gè)線索逐

步試探，對(duì)于每一步的試探，若試探成功，就得到問題的解,

若試探失敗，就逐步回退，換別的路線再進(jìn)行試探。這種方

法稱為回溯法。回溯法在處理復(fù)雜數(shù)據(jù)結(jié)構(gòu)方面有著廣泛的

應(yīng)用。

《大學(xué)計(jì)算機(jī)基礎(chǔ)》主講人：趙丕錫教授

小結(jié):

0.1舁皆

8.1.1算法的基本概念

一、算法的基本特征

工、可行性

2、確定性

3、有窮性

4、有零個(gè)或多個(gè)輸入

5、有一個(gè)或多個(gè)輸出

二、算法的基本要素

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

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

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

列舉法、歸納法、遞推、遞歸減半遞推技術(shù)、回溯法

《大學(xué)計(jì)算機(jī)基礎(chǔ)》主講人：趙丕錫教授

8.1算法

8.1,2算法的復(fù)雜度

選用算法首先考慮正確性，還要考慮執(zhí)行

算法所耗費(fèi)的時(shí)間和存儲(chǔ)空間，同時(shí)算法應(yīng)易于

理解、編碼、調(diào)試等。

算法的復(fù)雜度可分為時(shí)間復(fù)雜度和空間復(fù)

雜度，是衡量算法優(yōu)劣的度量。

《大學(xué)計(jì)算機(jī)基礎(chǔ)》主講人：趙丕錫教授

一、算法的時(shí)間復(fù)雜度

算法的時(shí)間復(fù)雜度：執(zhí)行算法所需要的計(jì)算工作量。

算法的計(jì)算工作量：用算法所執(zhí)行的基本運(yùn)算次數(shù)來度量,

基本運(yùn)算次數(shù)：是問題規(guī)模的函數(shù)。

則：算法的計(jì)算工作量=f（n）,其中n是問題的規(guī)模。

《大學(xué)計(jì)算機(jī)基礎(chǔ)》主講人：趙丕錫教授

在分析一個(gè)給定問題算法的時(shí)間復(fù)雜度時(shí)，可以采用

F面兩種方法來分析算法的工作量。

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

平均性態(tài)分析是指用各種特定輸入下的基本運(yùn)算次數(shù)的加權(quán)平均

值來度量算法的工作量。假設(shè)x是所有可能輸入中的某個(gè)特定輸

入，用p(x)表示x出現(xiàn)的概率(即輸入為x的概率)，用t(x)

表示算法在輸入為x時(shí)所執(zhí)行的基本運(yùn)算次數(shù)，則算法的平均性

態(tài)定義為

A(n)=ZP(x)t(x)

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

《大學(xué)計(jì)算機(jī)基礎(chǔ)》主講人：趙丕錫教授

(2)最壞情況復(fù)雜性(Worst?CaseComplexity)

最壞情況分析是指在規(guī)模為n時(shí)，算法所執(zhí)行的基本運(yùn)算的最大次

數(shù)。它定義為

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

xeDn

其中，Dn和t(x)的含義同上?？梢钥闯?，最壞情況分析

W(n)的計(jì)算要比平均性態(tài)分析A(n)的計(jì)算方便得多。

實(shí)際上，W(n)給出了估計(jì)算法工作量的一個(gè)上界，因此，它比

A(n)更具有實(shí)用價(jià)值，是分析算法的時(shí)間復(fù)雜度常用的一個(gè)方法。

《大學(xué)計(jì)算機(jī)基礎(chǔ)》主講人：趙丕錫教授

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

----執(zhí)行這個(gè)算法所需要的內(nèi)存空間O

類似算法的時(shí)間復(fù)雜度，空間復(fù)雜度作為算法所

需存儲(chǔ)空間的度量。

《大學(xué)計(jì)算機(jī)基礎(chǔ)》主講人：趙丕錫教授

8.1算法課堂練習(xí)題

考題（2005_4）:（11）算法具有五個(gè)特性,以下選項(xiàng)中不屬于算法特性

的是

（A）有窮性（B）簡潔性（C）可行性（D）確定性

答案：B

考題（2005_4）5.問題處理方案的正確而完整的描述稱為

答案：算法

《大學(xué)計(jì)算機(jī)基礎(chǔ)》主講人：趙丕錫教授

考題(2005_9)(1)算法復(fù)雜度主要包括時(shí)間

復(fù)雜度和復(fù)雜度。

答案：空間

《大學(xué)計(jì)算機(jī)基礎(chǔ)》主講人：趙丕錫教授

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

數(shù)據(jù)結(jié)構(gòu)主要研究三個(gè)問題:

入數(shù)據(jù)集合中各數(shù)據(jù)元素之間所固有的邏輯關(guān)

系，即數(shù)據(jù)的邏輯結(jié)構(gòu);

2、在對(duì)數(shù)據(jù)進(jìn)行處理時(shí)，各數(shù)據(jù)元素在計(jì)算機(jī)

中的存儲(chǔ)關(guān)系，即數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu);

3、對(duì)各種數(shù)據(jù)結(jié)構(gòu)進(jìn)行的運(yùn)算。

《大學(xué)計(jì)算機(jī)基礎(chǔ)》主講人：趙丕錫教授

8.2.1什么是數(shù)據(jù)結(jié)構(gòu)？

例8.5無序表的順序查找與有序表的對(duì)分查找。

41228638127758605236

Ca)無序表

12223638415258607786

(b)有序表

圖S.1數(shù)據(jù)元素存放順序不同的兩個(gè)表

《大學(xué)計(jì)算機(jī)基礎(chǔ)》主講人：趙丕錫教授

現(xiàn)實(shí)世界中存在的一切個(gè)體都可以是數(shù)據(jù)元素。

例如：“春、夏、秋、冬”，可以作為季節(jié)的數(shù)據(jù)元素；

“26、56、65、73、26、…”，可以作為數(shù)值的數(shù)據(jù)元素；

“父親、兒子、女兒”，可以作為家庭成員的數(shù)據(jù)元素。

在數(shù)據(jù)處理領(lǐng)域中，每一個(gè)需要處理的對(duì)象都可以抽象成

數(shù)據(jù)元素。數(shù)據(jù)元素一般簡稱為元素。

《大學(xué)計(jì)算機(jī)基礎(chǔ)》主講人：趙丕錫教授

在具有相同特點(diǎn)的數(shù)據(jù)元素集合中，各個(gè)數(shù)據(jù)元素之間存在著

某種關(guān)系（即聯(lián)系），這種關(guān)系反映了數(shù)據(jù)元素所固有的一種

結(jié)構(gòu)。

在數(shù)據(jù)處理中，通常把數(shù)據(jù)元素之間這種固有的關(guān)系簡單地

用前后件關(guān)系（或直接前驅(qū)與直接后繼關(guān)系）來描述。

例如：在“春、夏、秋、冬”中，“春”是“夏”前件，……。

一般來說，數(shù)據(jù)元素之間的任何關(guān)系都可以用前后件關(guān)系來

____________________________________________________

《大學(xué)計(jì)算機(jī)基礎(chǔ)》主講人：趙丕錫教授

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

數(shù)據(jù)結(jié)構(gòu)是指帶有結(jié)構(gòu)的數(shù)據(jù)元素的集合。

這里所說的結(jié)構(gòu)實(shí)際上就是指數(shù)據(jù)元素之間的前后件關(guān)系。

由此可見，一個(gè)數(shù)據(jù)結(jié)構(gòu)應(yīng)包含如下兩種信息：

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

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

數(shù)據(jù)元素之間的前后件關(guān)系是指它們的邏輯關(guān)系，這與它們?cè)谟?jì)

算機(jī)中的存儲(chǔ)位置無關(guān)。

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

《大學(xué)計(jì)算機(jī)基礎(chǔ)》主講人：趙丕錫教授

由前面的敘述可以看出，數(shù)據(jù)的邏輯結(jié)構(gòu)有兩個(gè)基本要素：

一是數(shù)據(jù)元素的集合，通常記為D；

二是D上的關(guān)系，它反映了D中各數(shù)據(jù)元素之間的前后件關(guān)系，

通常記為R。

因此，一個(gè)數(shù)據(jù)的邏輯結(jié)構(gòu)可以表示成B=(D,R),其中B

表示數(shù)據(jù)的邏輯結(jié)構(gòu)。

《大學(xué)計(jì)算機(jī)基礎(chǔ)》主講人：趙丕錫教授

例8.7一年四季的數(shù)據(jù)邏輯結(jié)構(gòu)可以表示成

B=（D,R）

D=｛春，夏，秋，冬｝

R=｛（春，夏），（夏，秋），（秋，冬））

例8.8家庭成員的數(shù)據(jù)邏輯結(jié)構(gòu)可以表示成

B=（D,R）

D=｛父親，兒子,女兒｝

R=｛（父親，兒子），（父親，女兒）｝

《大學(xué)計(jì)算機(jī)基礎(chǔ)》主講人：趙丕錫教授

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

儲(chǔ)結(jié)構(gòu)（也稱數(shù)據(jù)的物理結(jié)構(gòu)）。

★在數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)中，不僅要存放各數(shù)據(jù)元素的信息，還需

要存放各數(shù)據(jù)元素之間的前后件關(guān)系的信息。

★一種數(shù)據(jù)的邏輯結(jié)構(gòu)可以表示成多種存儲(chǔ)結(jié)構(gòu)。

★常用的存儲(chǔ)結(jié)構(gòu)有順序、鏈接、索引等存儲(chǔ)結(jié)構(gòu)。

★對(duì)于一種數(shù)據(jù)的邏輯結(jié)構(gòu)，如果采用不同的存儲(chǔ)結(jié)構(gòu)，則數(shù)據(jù)

處理的效率是不同的。因此，在進(jìn)行數(shù)據(jù)處理時(shí)，選擇合適的

存儲(chǔ)結(jié)構(gòu)是非常重要的。

《大學(xué)計(jì)算機(jī)基礎(chǔ)》主講人：趙丕錫教授

8?2.2數(shù)據(jù)結(jié)構(gòu)的圖形表示

數(shù)據(jù)結(jié)構(gòu)除了可以用前面的所定的二元關(guān)系表示外，

還可以用圖形來表示。

圖一年四季數(shù)據(jù)結(jié)構(gòu)的圖形表示

圖&3濠庭成員數(shù)據(jù)結(jié)構(gòu)的圖形表示

《大學(xué)計(jì)算機(jī)基礎(chǔ)》主講人：趙丕錫教授

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

［據(jù)結(jié)構(gòu)中各數(shù)據(jù)元素之間前后件關(guān)系的復(fù)雜程度,

般將數(shù)據(jù)結(jié)構(gòu)分為兩大類：線性結(jié)構(gòu)與非線性結(jié)構(gòu)。

如果一個(gè)非空的數(shù)據(jù)結(jié)構(gòu)滿足下列條件：

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

(2)有且只有一個(gè)終端結(jié)點(diǎn)；

(3)除根結(jié)點(diǎn)外，其他結(jié)點(diǎn)均只有一個(gè)前件；

(4)除終端結(jié)點(diǎn)外，其他結(jié)點(diǎn)均只有一個(gè)后件。

則稱該數(shù)據(jù)結(jié)構(gòu)為線性結(jié)構(gòu)。線性結(jié)構(gòu)又稱線性表。

《大學(xué)計(jì)算機(jī)基礎(chǔ)》主講人：趙丕錫教授

課堂練習(xí)：

8?2數(shù)據(jù)結(jié)構(gòu)的基本概念

考題(2005_4):(1)數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是指

(A)存儲(chǔ)在外存中的數(shù)據(jù)

(B)數(shù)據(jù)所占的存儲(chǔ)空間量

(C)數(shù)據(jù)在計(jì)算機(jī)中的順序存儲(chǔ)方式

(D)數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)中的表示

答案：D

《大學(xué)計(jì)算機(jī)基礎(chǔ)》主講人：趙丕錫教授

考題（2005_9）:（4）下列敘述正確的是（）。

A）一個(gè)邏輯數(shù)據(jù)結(jié)構(gòu)只能有一種存儲(chǔ)結(jié)構(gòu)

B）數(shù)據(jù)的邏輯結(jié)構(gòu)屬于線性結(jié)構(gòu)，存儲(chǔ)結(jié)構(gòu)屬于非線

性結(jié)構(gòu)

C）一個(gè)邏輯數(shù)據(jù)結(jié)構(gòu)可以有多種存儲(chǔ)結(jié)構(gòu)，且各種存儲(chǔ)

結(jié)構(gòu)不影響數(shù)據(jù)處理的效率

D）一個(gè)邏輯數(shù)據(jù)結(jié)構(gòu)可以有多種存儲(chǔ)結(jié)構(gòu)，且各種存儲(chǔ)

結(jié)構(gòu)影響數(shù)據(jù)處理的效率

答案：D

《大學(xué)計(jì)算機(jī)基礎(chǔ)》主講人：趙丕錫教授

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

8.3.1線性表的基本概念

線性表(LinearList)是最簡單、最常用的

一種數(shù)據(jù)結(jié)構(gòu)。所謂線性表，是指n個(gè)數(shù)據(jù)元素的

有限序列。

線性表可以表示為(為，a2,…，電，…，

an),其中％是屬于數(shù)據(jù)對(duì)象的元素，通常也稱其

為線性表中的一個(gè)結(jié)點(diǎn)。

當(dāng)n=0時(shí)，稱為空表。

《大學(xué)計(jì)算機(jī)基礎(chǔ)》主講人：趙丕錫教授

8.3.2線性表的順序存儲(chǔ)結(jié)構(gòu)

在計(jì)算機(jī)中存放線性表，一種最簡單的方法是順序存儲(chǔ)。其

特點(diǎn)如下：

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

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

放的。

■■■■■■

aiHi-lHi%

線性表的起始地址

圖8.5線性的順序存儲(chǔ)結(jié)構(gòu)示意圖—

《大學(xué)計(jì)算機(jī)基礎(chǔ)》主講人：趙丕錫教授

對(duì)于線性表的順序存儲(chǔ)結(jié)構(gòu)，可以進(jìn)行各種處理。

下面主要討論線性表在順序存儲(chǔ)結(jié)構(gòu)下的插入與刪除

運(yùn)算。

F面通過一個(gè)例子來說明如何在順序存儲(chǔ)結(jié)構(gòu)的線性表

中插入一個(gè)新元素。

《大學(xué)計(jì)算機(jī)基礎(chǔ)》主講人：趙丕錫教授

例8，1圖8.6(a)是為一個(gè)長度為5的線性表

順序存儲(chǔ)在長度為8的存儲(chǔ)型］中。

(a)長度為5的線性表c)推入51后的線性表

8.6線性表在順序存儲(chǔ)結(jié)構(gòu)下的插入

《大學(xué)計(jì)算機(jī)基礎(chǔ)》主講人：趙丕錫教授

例8?12圖8,7（a）是一個(gè)長度為7的線性表順序存儲(chǔ)在長

度為8的存儲(chǔ)空間中。現(xiàn)在要求刪除表中的第2個(gè)元素（即刪除

元素23）。

111111111

2256256

356|325325

425486486

r

86534552

6346526

75277

S82

cG長度為7的線性表<bJ刪除23后的線性表c）刪除34后的線性表

8-7線性表在順序存儲(chǔ)結(jié)構(gòu)下的性計(jì)算機(jī)基礎(chǔ)》主講人：趙丕錫教授

課堂練習(xí)：

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

考題(2005_4)(5)下列對(duì)于線性表的描述中正確的是

A)存儲(chǔ)空間不一定是連續(xù)，且各元素的存儲(chǔ)順序是任意的

B)存儲(chǔ)空間不一定是連續(xù)，且前件元素一定存儲(chǔ)在后件元素的前

面

C)存儲(chǔ)空間必須連續(xù),且各前件元素一定存儲(chǔ)在后件元素的前面

D)存儲(chǔ)空間必須連續(xù)，且各元素的存儲(chǔ)順序是任意的

答案：A

《大學(xué)計(jì)算機(jī)基礎(chǔ)》主講人：趙丕錫教授

8.4棧和隊(duì)列

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

1.棧的基本概念

棧(stack)是限定僅在一端進(jìn)行插入和

刪除運(yùn)算的線性表0—「

在棧中，允許插入與刪除的一端稱為棧頂,

而不允許插入與刪除的另一端稱為棧底。

《大學(xué)計(jì)算機(jī)基礎(chǔ)》主講人：趙丕錫教授

棧的順序存儲(chǔ)結(jié)構(gòu)如圖8.8所示。

十指向錢頂?shù)闹羔?/p>

■

■

aa

ai

圖S.2棧的順序存儲(chǔ)結(jié)構(gòu)示意圖

《大學(xué)計(jì)算機(jī)基礎(chǔ)》主講人：趙丕錫教授

4一指向拔頂?shù)闹羔?/p>

8.4.1棧及其基本運(yùn)算:

包

0

2.棧的基本運(yùn)算圉82瞬順序存篙結(jié)構(gòu)示意圖

棧的基本運(yùn)算有三種：入棧、退棧與讀棧頂元素。

(1)入棧運(yùn)算

入棧運(yùn)算是指在棧頂位置插入一個(gè)新元素。

這個(gè)運(yùn)算有兩個(gè)基本操作：

首先將棧頂指針進(jìn)一，然后將新元素插入到棧頂指針指

向的位置;

《大學(xué)計(jì)算機(jī)基礎(chǔ)》主講人：趙丕錫教授

退棧運(yùn)算是指取出棧頂元素并賦給某個(gè)變量。

這個(gè)運(yùn)算有兩個(gè)基本操作:

首先將棧頂元素賦給一個(gè)指定的變量，然后將棧頂指針

退—ko

—指向橫頂?shù)闹羔?/p>

■

■

32

心

圖S.8樓的順序存儲(chǔ)結(jié)構(gòu)示意圖

《大學(xué)計(jì)算機(jī)基礎(chǔ)》主講人：趙丕錫教授

（3）BW基本運(yùn)算

讀棧頂元素是指將棧頂元素賦給一個(gè)指定的變量。在這

個(gè)運(yùn)算中，棧頂指針不會(huì)改變。

一指向棧頂?shù)闹羔?/p>

*

*■

如

ai

旗裕I蝴孵高精桀解吳邕題丕錫教授

例8.13在圖8.9中，設(shè)top為指向棧頂元素的指針。圖8.9(a)為容量為

8的棧順序存儲(chǔ)空間，棧中已有4個(gè)元素；圖&9(b)與圖8.9(c)分別為

入棧與退棧后的狀態(tài)。

topf8

7top->7

topf242424

525252

222222

121212

(a)有4個(gè)元素的極1b)插入7和E后的棧(a)退出1個(gè)元素后的棧

圖8.9橫在順序存儲(chǔ)結(jié)構(gòu)下的運(yùn)算

《大學(xué)計(jì)算機(jī)基礎(chǔ)》主講人：趙丕錫教授

考題(2005_4)(2)下列關(guān)于棧的描述中錯(cuò)誤的

(A)棧是先進(jìn)后出的先性表

(B)棧只能順序存儲(chǔ)

(C)棧具有記憶作用

(D)對(duì)棧的插入和刪除操作中，不需要改變棧底指

針

答案：B

《大學(xué)計(jì)算機(jī)基礎(chǔ)》主講人：趙丕錫教授

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

1.隊(duì)列的基本概念

隊(duì)列(queue)是限定僅在表的一端進(jìn)行插入，而

t在表的另一端進(jìn)行刪除的線性表。二

在隊(duì)列中，允許插入的一端稱為隊(duì)尾，

允許刪除的一端稱為隊(duì)頭。

隊(duì)列又稱為“先進(jìn)先出”或“后進(jìn)后出”的線性表。

在隊(duì)列中，通常用指針front指向隊(duì)頭，用

rear指向隊(duì)尾，如圖8,10所示。

《大學(xué)計(jì)算機(jī)基礎(chǔ)》主講人：趙丕錫教授

1.隊(duì)列的基本概念

退隊(duì)*abcde一人隊(duì)

frontrear

圖8.10隊(duì)列示意圖

《大學(xué)計(jì)算機(jī)基礎(chǔ)》主講人：趙丕錫教授

圖8,1是在隊(duì)列中進(jìn)行插入與刪除的示意圖。

front->afront-a

bbfront-*b

ccc

ddd

rear-^-ee

rear-^,rear-*

Ca)一個(gè)隊(duì)列(b)插入一個(gè)元索后的隊(duì)列(O刪除一個(gè)元素后的隊(duì)列

圖笈11隊(duì)列運(yùn)算示意圖

《大學(xué)計(jì)算機(jī)基礎(chǔ)》主講人：趙丕錫教授

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

BA萬ll的lllffi庫存儲(chǔ)結(jié)構(gòu)船菜田很環(huán)隊(duì)列的形式，就是將

隊(duì)列存儲(chǔ)空間的最后一個(gè)位置繞到第一個(gè)位置，形

成邏輯上的環(huán)狀空間，供隊(duì)列循環(huán)使用，如圖8?12

所示。

tear一1

fiontf

圖以12循環(huán)隊(duì)列存儲(chǔ)空間示意圖

《大學(xué)計(jì)算機(jī)基礎(chǔ)》主講人：趙丕錫教授

圖8,13(a)是一個(gè)長度為6的循環(huán)隊(duì)列存儲(chǔ)空間，其中已有4個(gè)元素。

圖8?13(b)是在圖8.11(a)的循環(huán)隊(duì)列中又加入了1個(gè)元素后的

狀態(tài)。

■)是電0檀?(U)的施訂隊(duì)列中退出了1個(gè)元素后的狀態(tài)。

6e6e

5a5a

4b4b

3cfront-*-3c

front-*2d2

reai^-1rear^-1

(a)有4個(gè)元素的循環(huán)隊(duì)列(b)加入e后的循環(huán)隊(duì)列(C退出d后的循環(huán)隊(duì)列

圖名白循環(huán)隊(duì)列運(yùn)算示意圖

《大學(xué)計(jì)算機(jī)基礎(chǔ)》主講人：趙丕錫教授

考題（2005_9）（3）以下關(guān)于棧的描述正確的

是（）。.———一—三

B）在棧中只能刪除元素而不能插入

C）棧是特殊的線性表，只能在一端插入或刪除元素

D）棧是特殊的線性表，只能在一端插入元素，而在

另一端刪除元素

答案：C

《大學(xué)計(jì)算機(jī)基礎(chǔ)》主講人：趙丕錫教授

考題(2005_9)(5)數(shù)據(jù)結(jié)構(gòu)分為邏輯

隊(duì)列屬于結(jié)構(gòu)。

答案：存儲(chǔ)

《大學(xué)計(jì)算機(jī)基礎(chǔ)》主講人：趙丕錫教授

8.5線性鏈表

8.5.1線性鏈表的基本概念

F面舉一個(gè)例子來說明線性鏈表的存儲(chǔ)結(jié)構(gòu)。

假設(shè)有4個(gè)學(xué)生的某門功課的成績分別是a，a2,a3,a4,這4個(gè)

數(shù)據(jù)在內(nèi)存中的存儲(chǔ)單元地址分別是1248、工488、工366和

1522,其鏈表結(jié)構(gòu)如圖8?14(a)所示。

1248148813661522

a)線性鏈表的螂腦基礎(chǔ)》主講人：趙丕錫教授

實(shí)際上，常用圖8」4(b)來奏示它們的邏輯關(guān)系。

11nLi

HEAD-----?丐-------k&2---------?>&3---------?己4

(b)線性窿表的遺輯狀態(tài)

《大學(xué)計(jì)算機(jī)基礎(chǔ)》主講人：趙丕錫教授

在一些應(yīng)用中，對(duì)線性鏈表中的每個(gè)結(jié)點(diǎn)設(shè)置兩個(gè)指針

域，一個(gè)指向其前件結(jié)點(diǎn)，稱為前件指針或左指針;

樣的線性鏈表稱為雙向鏈表，其邏輯狀態(tài)如圖8,15

所示。

圖也15雙向捱表示意圖

《大學(xué)計(jì)算機(jī)基礎(chǔ)》主講人：趙丕錫教授

2.帶鏈的棧

由于棧也是線性表，所以也可采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。圖8?16是棧在鏈

式存儲(chǔ)時(shí)的邏輯狀態(tài)示意圖

當(dāng)計(jì)算機(jī)系統(tǒng)或用戶程序需要存嘉/滸，就可從這個(gè)可利用棧中

取出棧頂結(jié)點(diǎn)，如圖8?17(a)所示；

HULL

圖￡.16帶鏈的棧

HULL

2從可用核中取得一個(gè)結(jié)點(diǎn)

《大學(xué)計(jì)算機(jī)基礎(chǔ)》主講人：趙丕錫教授

當(dāng)計(jì)算機(jī)系統(tǒng)或用戶程序釋放一個(gè)存儲(chǔ)結(jié)點(diǎn)(該元素從

表中刪除)時(shí)，則要將該結(jié)點(diǎn)放回到可利用棧的棧

(b)將一個(gè)結(jié)點(diǎn)送回可利用棧

圖8-17可利用梭及其運(yùn)算

《大學(xué)計(jì)算機(jī)基礎(chǔ)》主講人：趙丕錫教授

3.帶鏈的隊(duì)列

由于隊(duì)列也是線性表，所以也可以采用鏈?zhǔn)酱鎯?chǔ)結(jié)

構(gòu)。圖8?18(a)是隊(duì)列固鏈?zhǔn)酱鎯?chǔ)時(shí)的邏輯狀態(tài)

示意圖。

frontrear

aXLUULL

(a)帶鏈的隊(duì)列

《大學(xué)計(jì)算機(jī)基礎(chǔ)》主講人：趙丕錫教授

圖8?18(b)是將一個(gè)新結(jié)點(diǎn)插入隊(duì)列的示意圖。

圖8,8(c)是將隊(duì)頭結(jié)點(diǎn)退出隊(duì)列的示意圖。

frontrear

aa%+1nun

l%IL

(b)在帶捱的隊(duì)列中插入一個(gè)結(jié)點(diǎn)

frontrear

(C在帶髀的隊(duì)列中刪除一個(gè)結(jié)點(diǎn)

圖應(yīng)IX帶舞的隊(duì)列霰其例算機(jī)基礎(chǔ)》主講人：趙丕錫教授

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

F面主要介紹線性鏈表的插入與刪除兩種運(yùn)算。

1.線性鏈表的插入運(yùn)算殍」

假設(shè)可利用棧與線性鏈表如圖8?19(a)所示。

現(xiàn)在要在線性鏈表中包含元素a的結(jié)點(diǎn)之前插入一個(gè)包

含新元素b的結(jié)點(diǎn)。其插入過程如下：

HEAD

(G原可利用極與線性鏈表

《大學(xué)計(jì)算機(jī)基礎(chǔ)》主講人：趙丕錫教授

(1)從可利用棧中取一個(gè)結(jié)點(diǎn)，并設(shè)指針變量P指向該結(jié)點(diǎn)(即把

該結(jié)點(diǎn)的存儲(chǔ)地址存放在變量P中)，并使該結(jié)點(diǎn)的數(shù)據(jù)域?yàn)椴?/p>

入的元素值b。這時(shí)，可利用棧的狀態(tài)如圖8?19(b)所示。

，▲一

ft個(gè)結(jié)點(diǎn)，并設(shè)指針變量q

指向該結(jié)點(diǎn)。線性鏈表如圖8?19(b)所示。

(b)從可利用核中取得一個(gè)由F所指向的結(jié)點(diǎn)，在線性錐表中找到由Q所指向的結(jié)點(diǎn)

《大學(xué)計(jì)算機(jī)基礎(chǔ)》主講人：趙丕錫教授

(3)最后將p所指的結(jié)點(diǎn)插入到q所指的結(jié)點(diǎn)之后。這只要改變以

下兩個(gè)結(jié)點(diǎn)的指針域內(nèi)容既可：首先使P所指的結(jié)點(diǎn)的指針域指

向包含元素a的結(jié)點(diǎn)，然后將q所指的結(jié)點(diǎn)的指針域內(nèi)容改為指

Cc)將新結(jié)點(diǎn)插入到指定結(jié)點(diǎn)之前

圖8.19線性捱表的插入

《大學(xué)計(jì)算機(jī)基礎(chǔ)》主講人：趙丕錫教授

2.線性鏈表的刪除

設(shè)可利用棧與線性鏈表如圖8.20(a)所示。現(xiàn)在要在線性鏈表中

刪瞟也!兒案即煽乩則刪臊出程如F：

原可利用梭與線性椎表

《大學(xué)計(jì)算機(jī)基礎(chǔ)》主講人：趙丕錫教授

首先在線性鏈表中找到包含元素a的結(jié)點(diǎn)，設(shè)指針變量

P指向該結(jié)點(diǎn)，并設(shè)指針變量q指向前一個(gè)結(jié)點(diǎn)，然

后將P所指向的結(jié)點(diǎn)從線性鏈表中刪除，即讓q所指

Q蛙占的生奸相白「訴生電的結(jié)點(diǎn)；加理R20

(b)所示。

《大學(xué)計(jì)算機(jī)基礎(chǔ)》主講人：趙丕錫教授

最后，將p所指向的包含元素a的結(jié)點(diǎn)送回可利用棧，

如圖8.20(c)所示。此時(shí)，線性鏈表的刪除運(yùn)算

___________________

HEAD

Cc)將被刪除的結(jié)點(diǎn)送回可利用點(diǎn)后

圖82。線性鏈表的刪除

《大學(xué)計(jì)算機(jī)基礎(chǔ)》主講人：趙丕錫教授

8.5.3循環(huán)鏈表及其基本運(yùn)算

循環(huán)鏈表的結(jié)構(gòu)具有下面兩個(gè)磨點(diǎn):

(1)在循環(huán)鏈表中增加了一個(gè)表頭結(jié)點(diǎn)。表頭結(jié)點(diǎn)的

數(shù)據(jù)域?yàn)槿我饣蛘吒鶕?jù)需要來設(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)狀鏈，如圖8?21所示。

《大學(xué)計(jì)算機(jī)基礎(chǔ)》主講人：趙丕錫教授

其中圖8.21(a)是一個(gè)非空的循環(huán)鏈表，圖8.21

(b)是一個(gè)空的循環(huán)鏈表。

HEAD

袤炙結(jié)省

1a)非空循環(huán)捱表

HEAD

表頭結(jié)電

(b)空循環(huán)鏈表

國221循環(huán)鏈表的邏輯狀態(tài)

《大學(xué)計(jì)算機(jī)基礎(chǔ)》主講人：趙丕錫教授

8.6樹與二叉樹

8.6.1樹的基本概念

樹(tree)是一種非線性結(jié)構(gòu)。在樹這種數(shù)據(jù)結(jié)構(gòu)中，所有

數(shù)據(jù)元素之間的關(guān)系具有明顯的層次特點(diǎn)。圖8?22表示

了一棵一般的樹。

圖8.22樹的結(jié)構(gòu)圖-----------------------------

《大學(xué)計(jì)算機(jī)基礎(chǔ)》主講人：趙丕錫教授

實(shí)際上，能用樹結(jié)構(gòu)表示的例子有許多。例如，圖8.23中的樹

表示了學(xué)校行政關(guān)系結(jié)構(gòu)。

圖8.23學(xué)校行政層次結(jié)構(gòu)樹

《大學(xué)計(jì)算機(jī)基礎(chǔ)》主講人：趙丕錫教授

□下面介紹樹這種數(shù)據(jù)結(jié)構(gòu)中的一些基本特征和基本術(shù)語。

□在樹結(jié)構(gòu)中，每一個(gè)結(jié)點(diǎn)只有一個(gè)前件，稱為父結(jié)點(diǎn)，沒有

前件的結(jié)點(diǎn)只有一個(gè)，稱為根結(jié)三（簡稱根）。例如，在圖

8?22中，結(jié)點(diǎn)A是樹的根結(jié)點(diǎn)。

□在樹結(jié)構(gòu)中，每一個(gè)結(jié)點(diǎn)可以有多個(gè)后件，它們都稱為該結(jié)

點(diǎn)的子結(jié)點(diǎn)。沒有后件的結(jié)點(diǎn)稱為葉子結(jié)點(diǎn)。例如，在圖

8?22中，結(jié)點(diǎn)E、F、G、H、I、J均為葉子結(jié)點(diǎn)。

□在樹結(jié)構(gòu)中，一個(gè)結(jié)點(diǎn)所擁有的后件的個(gè)數(shù)稱為該結(jié)點(diǎn)的度。

例如，在圖8.22中，根結(jié)點(diǎn)A的度為3；結(jié)點(diǎn)B的度為2；

結(jié)點(diǎn)C的度為工；葉子結(jié)點(diǎn)的度為0。

□在樹結(jié)構(gòu)中，所有結(jié)點(diǎn)中的最大的度稱為樹的度。例如，圖

8.22所示的樹的度為3。

《大學(xué)計(jì)算機(jī)基礎(chǔ)》主講人：趙丕錫教授

□由于樹結(jié)構(gòu)具有明顯的層次關(guān)系，即樹是一種層次結(jié)構(gòu)，所以

在樹結(jié)構(gòu)中，一般按如下原則分層：

口根結(jié)點(diǎn)在第1層。同一層上痛露黃的所有子結(jié)點(diǎn)都在下一層。

例如，在圖8.22中，根結(jié)點(diǎn)A在第1層；結(jié)點(diǎn)B、C、D在第2

層；結(jié)點(diǎn)E、F、G、H、工、J在第3層。

□樹的最大層數(shù)稱為樹的深度。例如，圖8.22所示的樹的深度為

3o

《大學(xué)計(jì)算機(jī)基礎(chǔ)》主講人：趙丕錫教授

在樹結(jié)構(gòu)中，以某結(jié)點(diǎn)的一個(gè)子結(jié)點(diǎn)為根構(gòu)成的樹稱為該結(jié)點(diǎn)

的一棵子樹。例如，在圖8.22中：根結(jié)點(diǎn)A有3棵子樹，

別以E、F為根結(jié)點(diǎn)。在樹結(jié)構(gòu)中，葉子結(jié)點(diǎn)沒有子樹。

《大學(xué)計(jì)算機(jī)基礎(chǔ)》主講人：趙丕錫教授

8.6.2二叉樹及其基本運(yùn)算

1.二叉樹的基本概念

二叉樹(binarytree)是一種非常用的非線性數(shù)據(jù)

結(jié)構(gòu)。二叉樹與前面介紹的樹結(jié)構(gòu)不同，但它與樹

結(jié)構(gòu)很相似，并且，有關(guān)樹結(jié)構(gòu)的所有術(shù)語都可以

用到二叉樹這種數(shù)據(jù)結(jié)構(gòu)上。

《大學(xué)計(jì)算機(jī)基礎(chǔ)》主講人：趙丕錫教授

二叉樹具有以下兩個(gè)特點(diǎn)：

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

且分別稱為該結(jié)點(diǎn)的左子樹與

右子樹。

圖8.25所示是一顆二叉樹，根結(jié)點(diǎn)為A,其左子樹包含結(jié)點(diǎn)B、

D、G、H,右子樹包含結(jié)點(diǎn)C、E、F、工、Jo根A的左子樹

又是一顆二叉樹，其根結(jié)點(diǎn)為B,有非空的左子樹（由結(jié)點(diǎn)D、

G、H組成）和空的右子樹。根A的右子樹也是一顆二叉樹，

其根結(jié)點(diǎn)G有非空的左子樹（由結(jié)點(diǎn)E、I、J組成）和右子

樹（由結(jié)點(diǎn)F組成）。

《大學(xué)計(jì)算機(jī)基礎(chǔ)》主講人：趙丕錫教授

在二叉樹中，一個(gè)結(jié)點(diǎn)可以只有左子樹而沒有右子樹,

也可以只有右子樹而沒有左子樹。例如，圖8.26

但如果作為已

們就相同了。

圖8.264顆不同的二叉樹

《大學(xué)計(jì)算機(jī)基礎(chǔ)》主講人：趙丕錫教授

2.滿二叉樹與完全二叉樹

滿二叉樹與完全二叉樹是兩種特殊的二叉樹。

(1)滿二叉樹

且所有葉子結(jié)點(diǎn)都在同一層上，這樣的二叉樹稱為滿二叉樹。

圖8?27(a)、8.27(b)分別是深度為2、3的滿二叉樹。

困8.27滿二叉樹

《大學(xué)計(jì)算機(jī)基礎(chǔ)》主講人：趙丕錫教授

(2)完全二叉樹

完全二叉樹是指除最后一層外，每一層上的結(jié)點(diǎn)數(shù)均達(dá)到最大值，

而在最后一層上只缺少右邊的若干結(jié)點(diǎn)。顯然，滿二叉樹也是完

—虬網(wǎng)〕而短—君芮二叉附。典8.28是兩顆；料

度為3的完全二叉樹。

圖S.2S兩顆深度為3完全二叉樹

《大學(xué)計(jì)算機(jī)基礎(chǔ)》主講人：趙丕錫教授

3.二叉樹的基本性質(zhì)

二叉樹具有下列重要性質(zhì)：

性質(zhì)工在二叉樹中，第信的結(jié)點(diǎn)數(shù)最多為

個(gè)(i>l)O

性質(zhì)2在深度為k的二叉樹中，結(jié)點(diǎn)總數(shù)最多

為2kT個(gè)(k'l)o

《大學(xué)計(jì)算機(jī)基礎(chǔ)》主講人：趙丕錫教授

性質(zhì)3對(duì)任意一棵二叉樹，度為0的結(jié)點(diǎn)（即葉子結(jié)點(diǎn)）總是比度

為2的結(jié)點(diǎn)多一個(gè)。

例如，在圖8?25所示的二叉樹中，有5個(gè)葉子結(jié)點(diǎn)，有4個(gè)度為

2的結(jié)點(diǎn)，度為0的結(jié)點(diǎn)比度為2的結(jié)點(diǎn)多一個(gè)。

《大學(xué)計(jì)算機(jī)基酬T至皆火：趙丕錫教授

個(gè)結(jié)點(diǎn)的二叉樹，其深度至少為

[log2n]+l,其中[logzii]表示取log2n的整數(shù)部

分。（2）具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為

[log2n]+lo

《大學(xué)計(jì)算機(jī)基礎(chǔ)》主講人：趙丕錫教授

性質(zhì)5如果對(duì)一棵有n個(gè)結(jié)點(diǎn)的完全二叉樹的結(jié)點(diǎn)從1到n按層序編

號(hào)，則對(duì)任一結(jié)點(diǎn)i(IWiWn),有

則結(jié)點(diǎn)i是二叉修感想，它沒有父結(jié)點(diǎn)：如果>工,

則其父結(jié)點(diǎn)編號(hào)為口/2］。

(2)如果2i>n,則結(jié)點(diǎn)i無左子結(jié)點(diǎn)(結(jié)點(diǎn)i為葉子結(jié)點(diǎn))；否貝IJ,

其左子結(jié)點(diǎn)是結(jié)點(diǎn)2i。

(3)如果2i+1>n,則結(jié)點(diǎn)i無右子結(jié)點(diǎn)；否則，其右子結(jié)點(diǎn)是結(jié)

點(diǎn)2i+工。

根據(jù)完全二叉樹的這個(gè)性質(zhì)，如果按從上到下、從左到右順序存儲(chǔ)

完全二叉樹的各結(jié)點(diǎn)，則很容易確定每一個(gè)結(jié)點(diǎn)的父結(jié)點(diǎn)、左子

結(jié)點(diǎn)和右子結(jié)點(diǎn)的位置。

《大學(xué)計(jì)算機(jī)基礎(chǔ)》主講人：趙丕錫教授

8.6.3二叉樹的存儲(chǔ)結(jié)構(gòu)

二叉樹通常采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。用于存儲(chǔ)二叉樹中各

元素的存儲(chǔ)結(jié)點(diǎn)由兩部分組成：數(shù)據(jù)域與指針域。

《大學(xué)計(jì)算機(jī)基礎(chǔ)》主講人：趙丕錫教授

由于在二叉樹的存儲(chǔ)結(jié)構(gòu)中每個(gè)存儲(chǔ)結(jié)點(diǎn)有兩個(gè)指針域,

因此，二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)也稱為二叉鏈表。圖

8,3U表爾一乂柱表的容楷術(shù)意圖。

S8.30二叉鏈表存儲(chǔ)示意圖

《大學(xué)訐算機(jī)基礎(chǔ)》主講人：趙丕錫教授

8.6.4二叉樹的遍歷

遍歷是二叉樹的重要運(yùn)算。二叉樹的遍歷是指按一定的次序訪問二

又判中削理I幽煦，■及I綺熏帔訪問隊(duì)且只被訪響一次。

在遍歷二叉樹的過程中，一般先遍歷左子樹，然后再遍歷右子樹。

在先左后右的原則下，根據(jù)訪問根結(jié)點(diǎn)的次序，二叉樹的遍歷可

以分為三種：前序遍歷、中序遍歷、后序遍歷。

下面分別介紹這三種遍歷的方法，并用D、L、R分別表示“訪問根

結(jié)點(diǎn)”、“遍歷根結(jié)點(diǎn)的左子樹”和"遍歷根結(jié)點(diǎn)的右子樹”。

《大學(xué)計(jì)算機(jī)基礎(chǔ)》主講人：趙丕錫教授

1.前序遍歷（DLR）

前序遍歷是指首先訪問根結(jié)點(diǎn)，然后遍歷左子樹，最后遍歷右

,仍然先訪問根結(jié)點(diǎn)，然

后遍歷左子樹，最后遍歷右子樹

例如，對(duì)圖8.31中的二叉樹進(jìn)行前序遍歷，則遍歷的

結(jié)果為ABDGCEH1F。

《大學(xué)計(jì)算機(jī)基礎(chǔ)》主講人：趙丕錫教授

2.中序遍歷(LDR)

中序遍歷是指首先遍歷左子樹，然后訪問根結(jié)點(diǎn)，最后遍歷右

,仍然先遍歷左子樹，然

后訪問根結(jié)點(diǎn)，最后遍歷右子樹。

例如，對(duì)圖8?31中的二叉樹進(jìn)行中序遍歷，則遍歷結(jié)果為

DGBAHEICFo

《大學(xué)計(jì)算機(jī)基礎(chǔ)》主講人：趙丕錫教授

3.后序遍歷（LRD）

后序遍歷是指首先遍歷左子樹，然后遍歷右子樹，最后訪問根

,仍然先遍歷左子樹，然

后遍歷右子樹，最后訪問根結(jié)點(diǎn)。

例如，對(duì)圖8?31中的二叉樹進(jìn)行后序遍歷，則遍歷結(jié)果為

GDBHIEFCAo

《大學(xué)計(jì)算機(jī)基礎(chǔ)》主講人：趙丕錫教授

考題（2005_4）1■■某二叉樹中度為2的縝點(diǎn)有

中啟二11]個(gè)葉子結(jié)點(diǎn)。

答案：19

《大學(xué)計(jì)算機(jī)基礎(chǔ)》主講人：趙丕錫教授

考題(2005_4)(4)一棵二叉樹第六層

-I棉特點(diǎn)小篇一屆工的結(jié)占新帚名為

答案：32

《大學(xué)計(jì)算機(jī)基礎(chǔ)》主講人：趙丕錫教授

8.7查找與排序技術(shù)

8.7.1順序查找

順序查找又稱為順序搜索。

順序查找一般是指在線性表中查找指定的元素，基本方法如下：從線性

表的第一個(gè)元素開始，依次將線性表中的元素與被查找元素進(jìn)行比

較，若相等則表示找到（即查找成功）；若線性表中所有的元素都

與被查元素進(jìn)行了比較，但都不相等，則表示線性表中沒有要查找

的元素（即查找失?。?/p>

《大學(xué)計(jì)算機(jī)基礎(chǔ)》主講人：趙丕錫教授

8.7.2二分法查找

二分法查找只適用于順序存儲(chǔ)的有序表，即要求線性

表中的元素按元素值的大小排列（遞減排列或遞增

排列）。假設(shè)有序線性表是按元素值遞增排列的,

并設(shè)表的長度為n,被查元素為x,則二分法查找

過程如下:

《大學(xué)計(jì)算機(jī)基礎(chǔ)》主講人：趙丕錫教授

將X與線性表的中間元素進(jìn)行比較:

若中間元素的值等于X,則說明查成功，查找結(jié)束;

蓼Y,卜1玉山［同三雯的估

>4I1yV，」JI11」JLlLJJIf^L

若X大于中間元素的值，則在線性表的后半部分以相同的方法查找。

這個(gè)過程一直進(jìn)行到查找成功或子表長度為0（說明線性表中沒有這

個(gè)元素）為止。

可以看出，當(dāng)有序的線性表為順序存儲(chǔ)時(shí)才能采用二分查找?？梢?/p>

證明，對(duì)于長度為n的有序線性表，在最壞情況下，二分查找只

需要比較log2n次，順序查找需要比較n次?？梢?，二分查找的

效率要比順序查找高得多。

《大學(xué)計(jì)算機(jī)基礎(chǔ)》主講人：趙丕錫教授

8.7.3交換類排序法

1.冒泡排序法

ffi泡排序法是一種最簡單的交換類排序方法,它是通過相鄰數(shù)據(jù)元素

的交換逐步將線性表變成有序的。冒泡排序法的操作過程如下:

首先，從表頭開始往后掃描線性表，在掃描過程中依次比較相鄰兩元

素的大小，若前面的元素大于后面的元素，則將它們互換，稱之

為消去了一個(gè)逆序。顯然，在掃描過程中，不斷地將兩相鄰元素

中的大者往后移動(dòng)，最后就將線性表中的最大者換到了表的最后。

《大學(xué)計(jì)算機(jī)基礎(chǔ)》主講人：趙丕錫教授

然后，按相反的方向掃描剩下的線性表，在掃描過程中依次比較相鄰

兩個(gè)元素的大小，若后面的元素小于前面的元素，則將它們互換,

這樣就又消去了一個(gè)逆序。

顯決，在掃描過程中，不斷地將廊骸元素中的小者往前移動(dòng)，最后

就將剩下的線性表中的最小者換到了表的最前面。

此時(shí)，線性表的第一個(gè)元素就是最小者，最后一個(gè)元素就是最大者。

對(duì)剩下的元素構(gòu)成的線性表重復(fù)上述過程，直到剩下的元素為空或者

在掃描過程中沒有交換任何元素，此時(shí)，線性表變?yōu)橛行颉?/p>

《大學(xué)計(jì)算機(jī)基礎(chǔ)》主講人：趙丕錫教授

圖8.32是冒泡排序法的示意圖。圖中有下劃線的元素表示

掃描過程中的第一個(gè)和最后一個(gè)元素的位置。

從冒泡排序法的操作過程可以看出，對(duì)長度為n的線性表,

E壞的情況下需要進(jìn)行（nT）+（n-2）+...+2+l=n

（n-1）/2次比較。

原序列628131957

第1遍（從前往后）6118579

（從后在前）126135c87r9

第2遍（從前往后）121356789

（從后在刖）112356789

第3遍（從前往后）112356789

最后結(jié)果112356789

8.32冒泡排序示意圖大學(xué)計(jì)算機(jī)基礎(chǔ)》主講人：趙丕錫教授

2.快速排序法

快速排序法是對(duì)冒泡排序法的改進(jìn)，又叫作分區(qū)交換排序法。

快速排序法的基本思想如下：

從線性表中任意選