鄭州航院計(jì)算機(jī)科學(xué)與應(yīng)用系

太

常

虐

然召芭

印

照感

小

騏熱熱*

藏

臂卷卷M監(jiān)

平^

^

^

^

1

9黑

卡

教學(xué)目的

學(xué)習(xí)本章的目的是了解數(shù)據(jù)結(jié)構(gòu)在程序設(shè)計(jì)中的作

用，能正確理解線性表、棧和隊(duì)列三種不同數(shù)據(jù)結(jié)構(gòu)的

異同，能夠在程序設(shè)計(jì)中正確選用數(shù)據(jù)結(jié)構(gòu)以便解決編

程中的問題。

了解樹和二叉樹的基本概念。

學(xué)習(xí)本章的另外一個(gè)目的是學(xué)會(huì)對一批數(shù)據(jù)進(jìn)行順

序查找和二分查找的基本方法，并且掌握選擇排序和冒

泡排序兩種最基本的排序算法設(shè)計(jì)思路和代碼實(shí)現(xiàn)。

鄭州航院計(jì)算機(jī)科學(xué)與應(yīng)用條M<l>M

教學(xué)要求

(1)理解數(shù)據(jù)結(jié)構(gòu)的概念，研究數(shù)據(jù)結(jié)構(gòu)涉及的內(nèi)容。

(2)了解什么是線性表，掌握線性表的順序存儲(chǔ)結(jié)構(gòu)，

順序表的插入和刪除算法。

(3)了解棧和隊(duì)列的基本概念，為什么說棧是后進(jìn)先

出表，隊(duì)列是先進(jìn)先出表，熟悉進(jìn)棧、出棧、進(jìn)隊(duì)、出

隊(duì)的基本操作。

(4)理解樹和二叉樹的定義，了解樹的兩種存儲(chǔ)結(jié)構(gòu)

表示以及二叉樹的二叉鏈表表示。會(huì)寫出二叉樹的前序、

中序和后序遍歷方法。

鄭州航院計(jì)算機(jī)科學(xué)與應(yīng)用條IIMVI〉網(wǎng)

教學(xué)要求

(5)掌握順序表的順序查找和二分查找算法，能獨(dú)自

寫出相應(yīng)的程序代碼^

(6)掌握選擇排序和冒泡排序算法的基本思想，能順

利寫出上述算法的程序代碼。

鄭州航院計(jì)算機(jī)科學(xué)與應(yīng)用條囪

置點(diǎn)難點(diǎn)

重占.

~~Hk八、、,

?線性表的順序存儲(chǔ)結(jié)構(gòu)以及插入和刪除算法

?棧和隊(duì)列的概念

?樹和二叉樹的概念，二叉樹的二叉鏈表表示及其遍歷

?順序表的順序查找和二分查找算法

?選擇排序算法，冒泡排序算法

鄭州航院計(jì)算機(jī)科學(xué)與應(yīng)用條

點(diǎn)難點(diǎn)

難點(diǎn)：

?線性表順序存儲(chǔ)結(jié)構(gòu)的插入和刪除算法

?循環(huán)隊(duì)列的類型描述，進(jìn)隊(duì)和出隊(duì)算法

?二叉樹的二叉鏈表表示

?有序表的兩分查找算法

?選擇排序算法的基本思想及其實(shí)現(xiàn)

?冒泡排序算法的基本思想及其實(shí)現(xiàn)

鄭州航院計(jì)算機(jī)科學(xué)與應(yīng)用條

教學(xué)容

5.1算法與數(shù)據(jù)結(jié)構(gòu)的基本概念

5.2線性表

5.3棧和隊(duì)列

5.4樹和二叉樹

5.5查找

5.6排序

鄭州航院計(jì)算機(jī)科學(xué)與應(yīng)用條

5.1算法與數(shù)據(jù)結(jié)構(gòu)的基本概念

5.1.1算法及其特征----------------------------------

著名計(jì)算機(jī)科學(xué)家DE.Knuth

(1)什么是算法？在《THEART°FCOMPUTER

PROGRAMMING》一書中稱：

“一個(gè)算法，就是一個(gè)有窮規(guī)則

的集合，其中之規(guī)則規(guī)定了一個(gè)

解決某一特定類型的問題的運(yùn)算

序列。”

鄭州航院計(jì)算機(jī)科學(xué)與應(yīng)用條___r

5.1.1算法及其特征

(1)什么是算法?(1)確定性

(2)有效性

(2)算法的特征

(3)有零個(gè)或多個(gè)輸入

(4)有一個(gè)或多個(gè)輸出

(5)有窮性

鄭州航院計(jì)算機(jī)科學(xué)與應(yīng)用條M<l>M

5.1.1算法及其特征

(1)什么是算法？

(2)算法的特征

(3)算法需要用計(jì)算機(jī)語言描述出來，才能在計(jì)算機(jī)上實(shí)

現(xiàn)算法欲解決的問題。

鄭州航院計(jì)算機(jī)科學(xué)與應(yīng)用條M<l>M

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

數(shù)據(jù)是描述宏觀事物

(1)數(shù)據(jù)

的數(shù)字、字符以及一切能

夠輸入到計(jì)算機(jī)中的符號

集合。它是計(jì)算機(jī)程序使

用和加工的“原料”。

鄭州航院計(jì)算機(jī)科學(xué)與應(yīng)用條

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

(1)數(shù)據(jù)

(2)數(shù)據(jù)元素?cái)?shù)據(jù)元素是數(shù)據(jù)的

基本單位，也稱為數(shù)據(jù)

結(jié)點(diǎn)。一個(gè)數(shù)據(jù)元素可

以由若干個(gè)數(shù)據(jù)項(xiàng)組成。

0

鄭州航院計(jì)算機(jī)科學(xué)與應(yīng)用條

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

(1)數(shù)據(jù)

數(shù)據(jù)對象是具有相

(2)數(shù)據(jù)元素同特性的數(shù)據(jù)元素的集

(3)數(shù)據(jù)對象合。數(shù)據(jù)對象中的數(shù)據(jù)

元素彼此之間存在的相

互關(guān)系或相互聯(lián)系叫做

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

___________r

鄭州航院計(jì)算機(jī)科學(xué)與應(yīng)用系M<>>8

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

（1）數(shù)據(jù)

（）數(shù)據(jù)元素

2數(shù)據(jù)結(jié)構(gòu)就是具

（3）數(shù)據(jù)對象有結(jié)構(gòu)的數(shù)據(jù)元素

（4）數(shù)據(jù)結(jié)構(gòu)的集合。

0

鄭州航院計(jì)算機(jī)科學(xué)與應(yīng)用系

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

1.數(shù)據(jù)的邏輯結(jié)構(gòu)對數(shù)據(jù)元素之間邏輯關(guān)系的描述。

________________________________

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

鄭州航院計(jì)算機(jī)科學(xué)與應(yīng)用條M<l>M

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

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

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

(2)樹形結(jié)構(gòu)

鄭州航院計(jì)算機(jī)科學(xué)與應(yīng)用條M<l>M

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

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

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

(2)樹形結(jié)構(gòu)

(3)圖狀結(jié)構(gòu)

鄭州航院計(jì)算機(jī)科學(xué)與應(yīng)用條M<l>M

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

2.數(shù)據(jù)的物理結(jié)構(gòu)

數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)中的映像，即存儲(chǔ)表示。

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

特點(diǎn)是邏輯上相鄰的兩個(gè)數(shù)據(jù)元素存儲(chǔ)在物理位置

上也相鄰的兩個(gè)存儲(chǔ)單元，數(shù)據(jù)元素之間的關(guān)系由存儲(chǔ)

單元的鄰接關(guān)系來體現(xiàn)。

的由...

鄭州航院計(jì)算機(jī)科學(xué)與應(yīng)用條?I<Iy?〉網(wǎng)

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

2.數(shù)據(jù)的物理結(jié)構(gòu)

（1）順序存儲(chǔ)結(jié)構(gòu)

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

非順序存儲(chǔ)結(jié)構(gòu)是指邏輯上相鄰的元素在物理位置上

不要求相鄰，它們之間的邏輯關(guān)系用指針來鏈接。r

___________________________________________________________V

List-------?0------>1779------?1832------?1986------?20770

鄭州航院計(jì)算機(jī)科學(xué)與應(yīng)用條M<l>M

5.2線性表

5.2.7線性表的定義

線性表是心0個(gè)數(shù)據(jù)元素，…,an的有序集合。

(3i932,…，ai-i9a,8i+i9…，an)

ai的直接刖趨為ai-1,at的直接后繼為ai為。即除表中的ai與an

之外，其他每個(gè)元素有且僅有一個(gè)直接前趨和一個(gè)直接后繼元素。

5.2線性表

5.2.1線性表的定義

線性表是nNO個(gè)數(shù)據(jù)元素ai,a2,...,an的有序集合。

（a1，32,…，3i-i,a,8i+i,…，an）

ai的直接前趨為ai-1,at的直接后繼為ai+1。即除表中的ai與an

之外，其他每個(gè)元素有且僅有一個(gè)直接前趨和一個(gè)直接后繼元素。

鄭州航院計(jì)算機(jī)科學(xué)與應(yīng)用條M<l>M

5.2線性表

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

用一組地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)線性表的數(shù)據(jù)元素。

特點(diǎn)：以元素在計(jì)算機(jī)內(nèi)“物理位置相鄰”來表示線性表中數(shù)據(jù)元

素之間的邏輯關(guān)系。線性表中任一數(shù)據(jù)元素都可以隨機(jī)存取。

數(shù)組下標(biāo)

0123456n

aia2as343536a7■■■3n

地址連續(xù)的

存儲(chǔ)單元

鄭州航院計(jì)算機(jī)科學(xué)與應(yīng)用條

5.2線性表

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

用一組地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)線性表的數(shù)據(jù)元素。

特點(diǎn)：以元素在計(jì)算機(jī)內(nèi)“物理位置相鄰”來表示線性表中數(shù)據(jù)元

素之間的邏輯關(guān)系。線性表中任一數(shù)據(jù)元素都可以隨機(jī)存取。

地址連續(xù)的

存儲(chǔ)單元

鄭州航院計(jì)算機(jī)科學(xué)與應(yīng)用條

5.3棧和隊(duì)列

5.3.1棧

1棧的定義及其基本操作

棧是一種只允許在表

(1)棧

的一端進(jìn)行插入和刪除

運(yùn)算的線性表。亦稱棧

是“后進(jìn)先出表”。

_________________F

鄭州航院計(jì)算機(jī)科學(xué)與應(yīng)用條M<l>M

5.3.1棧

1棧的定義及其基本操作

(1)棧

在棧中，允許插入、

(2)棧頂、棧底

刪除的一端叫棧頂，棧

頂元素的位置由棧頂指

針(通常用top表示)

指出，另一端稱為棧底。

鄭州航院計(jì)算機(jī)科學(xué)與應(yīng)用系H<>M

5.3.1棧

1棧的定義及其基本操作

(1)棧

(2)棧頂、棧底

當(dāng)表中沒有元素

(3)空棧

時(shí)，稱之為空棧。

___r

鄭州航院計(jì)算機(jī)科學(xué)與應(yīng)用條

5.3.1棧

1棧的定義及其基本操作

(1)棧

棧的插入運(yùn)算簡稱

棧頂、棧底

為入棧或進(jìn)棧，刪除

(3)空棧

運(yùn)算簡稱為出?；蛲?/p>

(4)進(jìn)棧、出棧棧。

0

鄭州航院計(jì)算機(jī)科學(xué)與應(yīng)用條

5.3.1棧

2棧的表示和實(shí)現(xiàn)

棧的順序存儲(chǔ)結(jié)構(gòu),

（1）棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

是利用一組地址連續(xù)的

存儲(chǔ)單元作為棧的存儲(chǔ)

（2）棧的順序存儲(chǔ)結(jié)構(gòu)

空間，同時(shí)附設(shè)指針top

指示棧頂元素在順序棧

中的位置。0

鄭州航院計(jì)算機(jī)科學(xué)與應(yīng)用條M<l>M

5.3.2隊(duì)列

1.隊(duì)列的定義及其基本操作

⑴隊(duì)列隊(duì)列也簡稱隊(duì)，它是一

種只允許在表的一端進(jìn)行插

入操作而在表的另一端進(jìn)行

刪除操作的線性表。隊(duì)列也

稱為“先進(jìn)先出表”。

鄭州航院計(jì)算機(jī)科學(xué)與應(yīng)用條M<l>M

5.3.2隊(duì)列

1.隊(duì)列的定義及其基本操作

(1)隊(duì)列允許進(jìn)行插入的一端

(2)隊(duì)尾與隊(duì)頭稱為隊(duì)尾，隊(duì)尾元素的位

置由rear指出;

允許刪除的一端稱為

隊(duì)頭，隊(duì)頭元素的位置由

front指出。0

鄭州航院計(jì)算機(jī)科學(xué)與應(yīng)用條M<l>M

5.3.2隊(duì)歹U

2.隊(duì)的循環(huán)隊(duì)列實(shí)現(xiàn)

所謂“循環(huán)隊(duì)列”是指把順序

隊(duì)列設(shè)想成頭尾相連的循環(huán)表，使

得存儲(chǔ)空間可以重復(fù)使用。

鄭州航院計(jì)算機(jī)科學(xué)與應(yīng)用條M<l>M

5.4樹和二叉樹

5.4.7樹

1.樹的定義：

樹是g0結(jié)點(diǎn)的有窮集合T。當(dāng)n=0時(shí)稱之為空樹。在任何一棵非

空樹T中，必有一個(gè)特定的結(jié)點(diǎn)，稱之為T的根結(jié)點(diǎn)；其余結(jié)點(diǎn)被分成

m20個(gè)不相交的子集T1、T2、…、Tm,其中每一個(gè)子集Ti（七區(qū)m）本身

2.樹的存儲(chǔ)結(jié)構(gòu)

1）帶雙親的孩子鏈表表示法

這種存儲(chǔ)結(jié)構(gòu)是指，把每個(gè)結(jié)點(diǎn)的多個(gè)孩子視為一個(gè)線性表，且以

單鏈表作為存儲(chǔ)結(jié)構(gòu)。

鄭州航院計(jì)算機(jī)科學(xué)與應(yīng)用多：!<<[>[>[]

帶雙親的樹的孩子鏈表表示

鄭州航院計(jì)算機(jī)科

2.樹的存儲(chǔ)結(jié)構(gòu)

2）孩子兄弟鏈表表示法

孩子兄弟表示法又稱為二叉樹表示方法。即鏈表中結(jié)點(diǎn)的兩個(gè)

指針域分別指向該結(jié)點(diǎn)的第1個(gè)孩子結(jié)點(diǎn)和下一個(gè)兄弟結(jié)點(diǎn)。

鄭州航院計(jì)算機(jī)科學(xué)與應(yīng)用條M<l>M

5.4樹和二叉樹

5.4.2二叉樹

1.二叉樹的定義

二叉樹是忙0個(gè)結(jié)點(diǎn)的有限集合。在任意一棵非空二叉樹中，

每個(gè)結(jié)點(diǎn)至多只有兩棵子樹，并且二叉樹的子樹有左右之分，其次

序不能任意顛倒。

5.4樹和二叉樹

542二叉樹

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

般情況下,利用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)表示二叉樹。

Lchilddatarchild

鄭州航院計(jì)算機(jī)科學(xué)與應(yīng)用條M<l>M

5.4樹和二叉樹

542二叉樹

3.二叉樹的遍歷

二叉樹的遍歷是指，按一定的次序巡訪該樹中每個(gè)結(jié)點(diǎn)，使得

每個(gè)結(jié)點(diǎn)被訪問且僅被訪問一次。可見，遍歷的過程就使得原來具

有層次特性的各結(jié)點(diǎn)變成了一個(gè)結(jié)點(diǎn)的線性序列。

二叉鏈樹由根結(jié)點(diǎn)、左子樹、右子樹三個(gè)基本單元組成，假如

以L、D、R分別表示遍歷左子樹、訪問根結(jié)點(diǎn)和遍歷右子樹，且限

定先左后右，則可有DLR、LDR、LRD三種遍歷二叉樹的方法，并

且分別稱之為先（根）序遍歷，中（根）序遍歷和后（根）序遍歷。

鄭州航院計(jì)算機(jī)科學(xué)與應(yīng)用條M<l>M

5.5查找

5.5.1查詢表的概念

(1)查詢表查詢表是由同一類型

的數(shù)據(jù)元素構(gòu)成的集合，

集合中的數(shù)據(jù)元素之間存

在著完全松散的關(guān)系。

只作“查找”操作的表

稱為靜態(tài)查找表。0

鄭州航院計(jì)算機(jī)科學(xué)與應(yīng)用條

5.5.1查詢表的概念

（1）查詢表

關(guān)鍵字是數(shù)據(jù)元素

（2）關(guān)鍵字

（或記錄）中某個(gè)數(shù)據(jù)項(xiàng)

的值，用它可以標(biāo)識(shí)一個(gè)

數(shù)據(jù)元素（或記錄）。

鄭州航院計(jì)算機(jī)科學(xué)與應(yīng)用條

5.5.1查詢表的概念

(1)查詢表

查找是根據(jù)給定的某個(gè)值,

(2)關(guān)鍵字

在查找表中確定一個(gè)其關(guān)鍵字

(3)查找

等于給定值的記錄或數(shù)據(jù)元素,

若表中存在這樣的一個(gè)記錄,

則稱查找是成功的；若表中不

存在關(guān)鍵字等于給定值的記錄,

則稱查找失敗。

鄭州航院計(jì)算機(jī)科學(xué)與應(yīng)用條

5.5.2順序表的查找

編寫一個(gè)函數(shù)，功能為從整型數(shù)組A中查

找整數(shù)x是否存在(數(shù)組A(0)并未存儲(chǔ)

數(shù)據(jù))。若x存在則返回x在數(shù)組中的下標(biāo)，

否則返回O。

_________________________________r

012345678

2442636915894721

鄭州航院計(jì)算機(jī)科學(xué)與應(yīng)用條M<l>M

5.5.2順序表的查找

FunctionSearch(ByRefA()AsInteger,ByVaixAsInteger)

AsInteger

'A(O)沒有存儲(chǔ)數(shù)據(jù)

DimiAsInteger

A(0)=x

i=UBound(A)

WhileA(i)<>x

i=i-1

EndWhile

Returni

EndFunction

鄭州航院計(jì)算機(jī)科學(xué)與應(yīng)用條DO<l>M

5.5.3有序表的查找

(1)對有序表的查找可以采用折半查找(亦稱對分查找或

二分查找)來實(shí)現(xiàn)。

(2)折半查找過程

先確定待查記錄所在的范圍(區(qū)間)，然后逐步縮小區(qū)間，

直到查找成功或找不到該數(shù)據(jù)元素為止。

用low和high指針分別指示待查數(shù)據(jù)元素所在范圍的下界和上

界，指針mid指示區(qū)間的中間位置，即mid=int(low+high)/2。

、折半查找算法演示

鄭州航院計(jì)算機(jī)科學(xué)與應(yīng)用條

1、查找成功的演示（查找key=21）

1234567891011

0513192137566475808892

▲▲

lowhigh

鄭州航院計(jì)算機(jī)科學(xué)與應(yīng)用條M<l>M

1、查找成功的演示（查找key=21）

1234567891011

0513192137566475808892

▲▲▲

lowmidhigh

mid=(low+high)/2=(1+11)/2=6

鄭州航院計(jì)算機(jī)科學(xué)與應(yīng)用條DO<l>M

1、查找成功的演示（查找key=21）

1234567891011

0513192137566475808892

▲▲▲

lowmidhigh

key=21<v[mid]=56o

所以key應(yīng)該處于區(qū)間[low,mid-1]中

鄭州航院計(jì)算機(jī)科學(xué)與應(yīng)用條M<l>M

1、查找成功的演示（查找key=21）

1234567891011

0513192137566475808892

▲

lowhigh

鄭州航院計(jì)算機(jī)科學(xué)與應(yīng)用條M<l>M

1、查找成功的演示（查找key=21）

1234567891011

0513192137566475808892

▲

lowhigh

luwmid

mid=(low+high)/2=(1+5)/2=3

鄭州航院計(jì)算機(jī)科學(xué)與應(yīng)用條DO<l>M

1、查找成功的演示（查找key=21）

1234567891011

0513192137566475808892

▲

lowhigh

luwmid

key=21>v[mid]=19o

所以key應(yīng)該處于區(qū)間[mid+1,high]中

鄭州航院計(jì)算機(jī)科學(xué)與應(yīng)用條Il<lVI〉網(wǎng)

1、查找成功的演示（查找key=21）

1234567891011

0513192137566475808892

▲▲

lowhigh

鄭州航院計(jì)算機(jī)科學(xué)與應(yīng)用條M<l>M

1、查找成功的演示(查找key=21)

1234567891011

0513192137566475808892

▲▲

lowhigh

八

mid

mid=(low+high)/2=(4+5)/2=4取不大于小數(shù)的整數(shù)

鄭州航院計(jì)算機(jī)科學(xué)與應(yīng)用條1Kly區(qū)

1、查找成功的演示（查找key=21）

1234567891011

0513192137566475808892

▲▲

lowhigh

八

mid

key=21==v[mid]=21o查找成功，返回。

鄭州航院計(jì)算機(jī)科學(xué)與應(yīng)用條Il<lVI〉I陽

2、查找不成功的演示（查找key=85）

1234567891011

0513192137566475808892

▲

lowhigh

鄭州航院計(jì)算機(jī)科學(xué)與應(yīng)用條M<l>M

2、查找不成功的演示（查找key=85）

1234567891011

0513192137566475808892

▲

lowhigh

mid

mid=(low+high)/2=(1+11)/2=6

鄭州航院計(jì)算機(jī)科學(xué)與應(yīng)用條DO<l>M

2、查找不成功的演示（查找key=85）

1234567891011

0513192137566475808892

▲

lowhigh

mid

key=85>v[mid]=56。

所以key應(yīng)該處于區(qū)間[mid+1,high]中

鄭州航院計(jì)算機(jī)科學(xué)與應(yīng)用條M<l>M

2、查找不成功的演示（查找key=85）

1234567891011

0513192137566475808892

▲

lowhigh

鄭州航院計(jì)算機(jī)科學(xué)與應(yīng)用條M<l>M

2、查找不成功的演示（查找key=85）

1234567891011

0513192137566475808892

■

▲

lowhigh

mid

mid=(low+high)/2=(7+11)/2=9

鄭州航院計(jì)算機(jī)科學(xué)與應(yīng)用條DO<l>M

2、查找不成功的演示（查找key=85）

1234567891011

0513192137566475808892

■

▲

lowhigh

mid

key=85>v[mid]=80。

所以key應(yīng)該處于區(qū)間[mid+1,high]中

鄭州航院計(jì)算機(jī)科學(xué)與應(yīng)用條M<l>M

2、查找不成功的演示（查找key=85）

1234567891011

0513192137566475808892

■▲

lowhigh

鄭州航院計(jì)算機(jī)科學(xué)與應(yīng)用條M<l>M

2、查找不成功的演示（查找key=85）

1234567891011

0513192137566475808892

■▲

lowhigh

■

mid

?“I/hi㈤id=(low+high)/2=(10+11)/2=10

鄭州航院計(jì)算機(jī)科學(xué)與應(yīng)用條MOO'

2、查找不成功的演示（查找key=85）

V0513192137566475808892

lowhigh

▲

key=85<v[mid]=88。

mid

所以key應(yīng)該處于區(qū)間[low,mid-1]中

鄭州航院計(jì)算機(jī)科學(xué)與應(yīng)用條

2、查找不成功的演示（查找key=85）

1234567891011

0513192137566475808892

highlow

鄭州航院計(jì)算機(jī)科學(xué)與應(yīng)用條M<l>M

2、查找不成功的演示（查找key=85）

1234567891011

0513192137566475808892

highlow

因?yàn)閔ighvlow,查找失敗

鄭州航院計(jì)算機(jī)科學(xué)與應(yīng)用條M<l>M

3、算法實(shí)現(xiàn)

FunctionBSearch(ByRefA()AsInteger,ByVaixAsInteger)AsInteger

Dimmid,low,highAsInteger

low=1:high=UBound(A)

WhileTrue

mid=(low+high)\2

Ifx=A(mid)Then

Returnmid

Elselfx<A(mid)Then

high=mid-1

Else

low=mid+1

EndIf

Iflow>highThen

Return0

EndIf

鄭州北院計(jì)j號L科學(xué)與應(yīng)用條Il<lVI〉IDM

EndFunction

5.6排序

排序是指將一組數(shù)據(jù)元素的無序序列調(diào)整為一個(gè)有序序列。其目的

是便于對數(shù)據(jù)進(jìn)行檢索。

5.6.1選擇排序

鄭州航院計(jì)算機(jī)科學(xué)與應(yīng)用條

567選擇排序

方法1：演示前兩趟

第一趟開始

i指向第一個(gè)位置，j指向i的下一個(gè)位置

12345678

15446167349850

鄭州航院計(jì)算機(jī)科學(xué)與應(yīng)用條

567選擇排序

方法1：

12345678

ou

鄭州航院計(jì)算機(jī)科學(xué)與應(yīng)用條M<l>M

567選擇排序

方法1：

12345678

41546167349850

567選擇排序

方法1：

12345678

鄭州航院計(jì)算機(jī)科學(xué)與應(yīng)用條M<l>M

567選擇排序

方法1：

12345678

11546467349850

鄭州航院計(jì)算機(jī)科學(xué)與應(yīng)用條M<l>M

567選擇排序

方法1：

12345678

11546467349850

鄭州航院計(jì)算機(jī)科學(xué)與應(yīng)用條M<l>M

567選擇排序

方法1：

12345678

鄭州航院計(jì)算機(jī)科學(xué)與應(yīng)用條M<l>M

567選擇排序

方法1：

12345678

鄭州航院計(jì)算機(jī)科學(xué)與應(yīng)用條M<l>M

567選擇排序

方法1：

12345678

ou

鄭州航院計(jì)算機(jī)科學(xué)與應(yīng)用條M<l>M

567選擇排序

方法1：

第二趟

位置后移1位，j指向i的下一個(gè)位置

12345678

11546467349850

鄭州航院計(jì)算機(jī)科學(xué)與應(yīng)用條M<l>M

567選擇排序

方法1：

第二趟

位置后移1位，j指向i的下一個(gè)位置

12345678

11546467349850

鄭州航院計(jì)算機(jī)科學(xué)與應(yīng)用條M<l>M

567選擇排序

方法1：

第二趟

位置后移1位，j指向i的下一個(gè)位置

12345678

11546467349850

鄭州航院計(jì)算機(jī)科學(xué)與應(yīng)用條M<l>M

567選擇排序

方法1：

第二趟

位置后移1位，j指向i的下一個(gè)位置

12345678

14461567349850

鄭州航院計(jì)算機(jī)科學(xué)與應(yīng)用條M<l>M

567選擇排序

方法1：

第二趟

位置后移1位，j指向i的下一個(gè)位置

12345678

14461567349850

鄭州航院計(jì)算機(jī)科學(xué)與應(yīng)用條M<l>M

567選擇排序

方法1：

第二趟

位置后移1位，j指向i的下一個(gè)位置

12345678

14461567349850

鄭州航院計(jì)算機(jī)科學(xué)與應(yīng)用條M<l>M

567選擇排序

方法1：

第二趟

位置后移1位，j指向i的下一個(gè)位置

12345678

14461567349850

鄭州航院計(jì)算機(jī)科學(xué)與應(yīng)用條M<l>M

567選擇排序

方法1：

第二趟

位置后移1位，j指向i的下一個(gè)位置

12345678

鄭州航院計(jì)算機(jī)科學(xué)與應(yīng)用條M<l>M

567選擇排序

方法1：

12345678

鄭州航院計(jì)算機(jī)科學(xué)與應(yīng)用條M<l>M

567選擇排序

方法1：

SubSelectSort(ByRefA()AsInteger)

Dimi,j,tAsInteger

Fori=1ToUBound(A)—1'外層循環(huán)控制趟數(shù)

Forj=i+1ToUBound(A)'從i位置的下一個(gè)位置開始比較

lfA(i)>AQ)Then'若發(fā)現(xiàn)有比A(i)小的，則交換

t=A(i):A(i)=A(j):AO)=t

EndIf

Next

Next

EndSub

鄭州航院計(jì)算機(jī)科學(xué)與應(yīng)用條DO<l>M

5.6.1選擇排序

方法2：

第一趟：從A(1)到上界，選擇一個(gè)最小的和A(1)進(jìn)行交換。

鄭州航院計(jì)算機(jī)科學(xué)與應(yīng)用條

5.6.1選擇排序

方法2：

第一趟：從A(1)到上界，選擇一個(gè)最小的和A(1)進(jìn)行交換。

鄭州航院計(jì)算機(jī)科學(xué)與應(yīng)用條M<l>M

567選擇排序

方法2：

第二趟：從A(2)到上界，選擇一個(gè)最小的和A(2)進(jìn)行交換。

5.6.1選擇排序

方法2：_

第二趟：從A(2)到上界，選擇一個(gè)最小的和A(2)進(jìn)行交換。

12345678

鄭州航院計(jì)算機(jī)科學(xué)與應(yīng)用樂IKIWIATM

567選擇排序

SubSelectSort2(ByRefA()AsInteger)

Dimi,j,min,tAsInteger

Fori=1ToUBound(A)-1

min=i

Forj=i+1ToUBound(A)

IfA(j)<A(min)Then

min=j

EndIf

Next

Ifi<>minThen

t=A(i)

A(i)=A(min)

A(min)=t

EndIf

Next

EndSub

鄭州航院計(jì)算機(jī)科學(xué)與應(yīng)用條ii<iv?/rw

5.6排序

562交換排序

交換排序的基本思想：

兩兩比較待排序數(shù)列中的記錄關(guān)鍵字，并交換不滿足順序要求

的數(shù)據(jù)對，直到全部序列排好序?yàn)橹埂?/p>

最簡單的交換排序方法是冒泡排序。

冒泡排序總共要做n-1輪處理過程，與選擇排序不同的是在每一

輪排序時(shí)將相鄰的數(shù)據(jù)時(shí)進(jìn)行比較，當(dāng)次序不對就交換位置，出了

內(nèi)循環(huán)，最大數(shù)已經(jīng)冒出。一輪排序過程也稱為一次冒泡。

鄭州航院計(jì)算機(jī)科學(xué)與應(yīng)用條M<l>M

562交換排序

冒泡排序演示：

第一趟

i指向第一個(gè)位置，j指向i的下一個(gè)位置

12345678

15446134679850

鄭州航院計(jì)算機(jī)科學(xué)與應(yīng)用條M<l>M

562交換排序

冒泡排序演示:

15446134679850

562交換排序

冒泡排序演示:

12345678

鄭州航院計(jì)算機(jī)科學(xué)與應(yīng)用條M<l>M

562交換排序

冒泡排序演示:

1234567