第3章3 4算法和數(shù)據(jù)結(jié)構(gòu)

3.4

算法和數(shù)據(jù)結(jié)構(gòu)算法數(shù)據(jù)結(jié)構(gòu)3.4.1

算法1.

什么是算法？算法是解決問題的方法與步驟例：有三個(gè)硬幣，其中一個(gè)是

偽造的，另兩個(gè)是真的，偽幣

與真幣重量略有不同。現(xiàn)在提

供一座天平，如何找出偽幣呢？分析：方法明確而有序按提供的條件進(jìn)行操作任何人均可仿照進(jìn)行(共享智能)開始C是偽幣B是偽幣A是偽幣A＝B？A＝C？是否否是關(guān)于算法的三方面問題如何確定算法（算法設(shè)計(jì)）？如何表示算法（算法表示）？如何使算法更有效（算法分析）？計(jì)算機(jī)算法的4個(gè)基本要求目的：完成某個(gè)特定的信息處理任務(wù)必須滿足的性質(zhì)：①確定性：算法中每一步操作的含義必須清楚明確，無二義性②能行性：算法中有待實(shí)現(xiàn)的操作都是計(jì)算機(jī)可執(zhí)行的，即必須在計(jì)算機(jī)的能力范圍之內(nèi)，且在有限時(shí)間內(nèi)能夠完成③有窮性：算法在執(zhí)行了有限步操作后必須結(jié)束④輸出：算法結(jié)束后至少產(chǎn)生一個(gè)輸出計(jì)算機(jī)中處處是算法！例1：Word程序如何在文檔中查找用戶指定的詞語？例2：在Word文檔的表格中如何將表格內(nèi)容排序？

例3：如何把一幅彩色圖片轉(zhuǎn)換為灰度(黑白)圖片？

例4：Windows如何在硬盤中找到用戶指定的文件？例5：媒體播放器如何把MP3文件轉(zhuǎn)換成動(dòng)聽的音樂？例6：搜索引擎如何在WWW網(wǎng)中找到用戶需要的網(wǎng)頁？算法是計(jì)算機(jī)軟件的靈魂計(jì)算機(jī)的通用性是因?yàn)樗苓\(yùn)行各種各樣的程序，而程序之所以能解決問題，是因?yàn)樗w現(xiàn)了正確的算法算法所解決的是一類問題而不是一個(gè)特定的問題，例如排序(sort)

：可以是表格內(nèi)容的排序，也可以是文件夾中

文件的排序，可以按數(shù)字或文字排序，也可以按日期排序，等等查找(search)：可以在文檔中查找某個(gè)單詞或在硬盤中查找某個(gè)文件，也可在Web上查找某個(gè)網(wǎng)頁，等等開發(fā)計(jì)算機(jī)應(yīng)用的核心是：根據(jù)實(shí)際問題給出解題的算法，然后再將該算法在計(jì)算機(jī)上實(shí)現(xiàn)(即開發(fā)成為軟件)注意：不是所有的問題的解決都可以用算法表示2.

算法設(shè)計(jì)舉例計(jì)算機(jī)求解問題的方法和步驟確定并理解問題；尋找解決問題的方法與步驟，并將其表示成算法(Algorithm)

；使用某種程序設(shè)計(jì)語言描述該算法(編程),并進(jìn)行調(diào)試；運(yùn)行程序，獲得問題的解答；進(jìn)行評(píng)估，改進(jìn)算法和程序例:

數(shù)據(jù)交換已知數(shù)據(jù)A，B。且A=5，B=4。請(qǐng)?jiān)O(shè)計(jì)算法將A,B交換，使得A=4，B=5。算法設(shè)計(jì)：例：對(duì)整數(shù)進(jìn)行排序問題：任給一組(n個(gè))整數(shù)，將它們從小到大進(jìn)行排序粗略的思路：①從所有整數(shù)中選一個(gè)最小的，作為已排序的第一個(gè)數(shù)②從剩下未排序整數(shù)中選最小的數(shù)，添加到已排序整數(shù)的后面③反復(fù)執(zhí)行步驟②，直到所有整數(shù)都處理完畢進(jìn)一步細(xì)化：把待排序的整數(shù)放在一個(gè)數(shù)組A中，每個(gè)整數(shù)是數(shù)組A中的一個(gè)元素：A[1],

A[2],A[3],

···],

A[n],排好序的元素在A的前面部分，無序的元素留在后面，每“循環(huán)”一次，有序部分增加1個(gè)元素，無序部分減少1個(gè)元素每次“循環(huán)”只需在數(shù)組的無序元素部分選出最小的數(shù)反復(fù)進(jìn)行n-1次即可得到排序后的結(jié)果“直接選擇排序”算法舉例第6次循環(huán)后，排序結(jié)束數(shù)組的初態(tài)，全部是未排序元素在未排序元素中確定最小數(shù)位置與首元素交換，第1次循環(huán)結(jié)束在未排序元素中確定最小數(shù)位置與首元素交換，第3次循環(huán)結(jié)束4

9

3

7

8

2

54

9

3

7

8

2

52

9

3

7

8

4

52

9

3

7

8

4

52

3

9

7

8

4

52

3

9

7

8

4

52

3

4

7

8

9

52

3

4

5

7

8

9與首元素交換，第2次循環(huán)結(jié)束在未排序元素中確定最小數(shù)位置“直接選擇排序”算法的描述將原始數(shù)據(jù)放在數(shù)組A中；設(shè)置i的初值為1，循環(huán)執(zhí)行下列操作，直到i=n

：整數(shù)的位置，設(shè)為j

；{

確定A[i]到A[n]中最小交換A[i]和[j]

；i

=

i

+1}原始數(shù)據(jù)放在數(shù)組A中；令i=1確定A[i]到A[n]中最小整數(shù)的位置,設(shè)為jA[i]和A[j]交換位置i

=

i

+

1i

=

n

?結(jié)束開始用偽代碼表示算法用流程圖表示算法直接選擇排序的c語言程序void

sort(int

A[],int

n)

/*

sort函數(shù)有2個(gè)參數(shù):整型數(shù)組A和數(shù)組元素個(gè)數(shù)n

*/{int

i,

j,

t,

k

;/*

定義4個(gè)整型變量*//*

重復(fù)執(zhí)行n-1次，每次增加1個(gè)已排序的數(shù)*//*在未排序整數(shù)中確定最小數(shù)for(

i=0

;

i<n-1;i++)

{j

=

i;for

(k=i+1;k<n

;k++) if

(A[k]<A[j]) j

=

k;的位置*/t=A[i];A[i]=A[j];

A[j]=t;

/*

把未排序數(shù)中的最小數(shù)交換到未排序數(shù)的首位*/}}3.

算法的表示算法的表示方法文字說明流程圖表示偽代碼（一種介于自然語言和程序設(shè)計(jì)語言之間的文字和符號(hào)表達(dá)工具）自然語言描述“比較Ａ與Ｂ的重量，若Ａ＝Ｂ，則Ｃ是偽造的；否則再比較Ａ與Ｃ的重量，若Ａ＝Ｃ，則Ｂ是偽造的；否則Ａ是偽造的?！比秉c(diǎn)：容易產(chǎn)生歧義，很難“精確”地進(jìn)行表達(dá)敘述冗長，很難清楚地表達(dá)算法的邏輯流程算法的流程圖表示流程圖由結(jié)點(diǎn)和有向邊構(gòu)成，它描述了算法所執(zhí)行操作的順序及執(zhí)行操作的條件流程圖符號(hào)：比文字描述簡明，但當(dāng)算

法比較復(fù)雜時(shí)，理解困難，容易產(chǎn)生錯(cuò)誤端點(diǎn)符處理判斷預(yù)定義功能原始數(shù)據(jù)放在數(shù)組A中；令i=1確定A[i]到A[n]中最小整數(shù)的位置,設(shè)為jA[i]和A[j]交換位置i

=

i

+

1i

=

n

?結(jié)束開始求最大公約數(shù)的偽代碼表示算法3：輾轉(zhuǎn)相除法求最大公約數(shù)BEGINinput

m,n;

/*輸入正整數(shù)m和n*/do{r←m

mod

n;m

←

n; n

←

r;}

while

r≠0;print

m；/*輸出最大公約數(shù)*/ENDYNr不等于0?輸出m的值輸入正整數(shù)m和n開始結(jié)束r←m被n除的余數(shù)m

←

n; n←

r4.

算法分析算法分析的基本內(nèi)容正確性：給定有效輸入后，經(jīng)過有限時(shí)間的計(jì)算，產(chǎn)生正確 的輸出結(jié)果一個(gè)問題的解決往往有多種不同算法.算法的好壞,除了考慮 其正確性,還要考慮以下因素:(1).執(zhí)行算法所要占用的計(jì)算機(jī)資源,包括時(shí)間資源和空間資源兩個(gè)方面:時(shí)間：運(yùn)行該算法所需要的時(shí)間的數(shù)量級(jí)表示空間：除原始數(shù)據(jù)之外，額外占用的存儲(chǔ)空間的大小(2)

算法是否容易理解，是否容易驗(yàn)證其正確性，程序是否容易調(diào)試;簡單的算法效率不一定高，要在保證一定效率的前提下力求算法簡單4.

小結(jié)3.4.2

數(shù)據(jù)結(jié)構(gòu)1.什么是數(shù)據(jù)結(jié)構(gòu)？數(shù)據(jù)結(jié)構(gòu)研究如何在計(jì)算機(jī)中表示被處理的對(duì)象及對(duì)象之間的關(guān)系，即如何組織數(shù)據(jù)。例如：選擇排序中，未排序整數(shù)和已排序整數(shù)如何表示？排序算法中，排序的對(duì)象若不是整數(shù)而是姓名如何表示？是文件夾中的文件名又如何表示？是表格中的“行”又如何表示？Word文檔中插入的表格和圖片如何表示？Windows操作系統(tǒng)中菜單如何表示？對(duì)話框如何表示？窗口如何表示？計(jì)算機(jī)下棋時(shí)，棋盤和棋局如何表示？精心設(shè)計(jì)的數(shù)據(jù)結(jié)構(gòu)可使算法獲得更高的時(shí)間效率或空間效率數(shù)據(jù)結(jié)構(gòu)包含的內(nèi)容數(shù)據(jù)的抽象(邏輯)結(jié)構(gòu)，即數(shù)據(jù)結(jié)構(gòu)中包括哪些元素，相互之 間有什么關(guān)系等。例如：數(shù)據(jù)的物理(存儲(chǔ))結(jié)構(gòu)，即數(shù)據(jù)的抽象結(jié)構(gòu)如何在實(shí)際的存儲(chǔ) 器中予以實(shí)現(xiàn)，數(shù)據(jù)元素如何表示，相互關(guān)系如何表示等定義在數(shù)據(jù)結(jié)構(gòu)上的一組運(yùn)算(操作)及其實(shí)現(xiàn)方法2.數(shù)據(jù)的邏輯結(jié)構(gòu)線性結(jié)構(gòu)網(wǎng)狀結(jié)構(gòu)樹形結(jié)構(gòu)集合結(jié)構(gòu)舉例：線性表(Liner-List)定義：若干個(gè)相同類型的數(shù)據(jù)元素組成的一個(gè)有限序列，其中每個(gè)數(shù)據(jù)元素可由多個(gè)數(shù)據(jù)項(xiàng)組成。表中有且僅有一個(gè)開始元素和一個(gè)結(jié)束元素，且所有元素都最多只有一個(gè)直接前趨和一個(gè)直接后繼例：考生成績登記表(table)數(shù)據(jù)元素已經(jīng)排了序的線性表稱為有序線性表，簡稱有序表34681張雷64834682王寧682準(zhǔn)考證號(hào) 姓名 總分表中的每一行是1個(gè)數(shù)據(jù)元素每個(gè)數(shù)據(jù)元素包含3個(gè)數(shù)據(jù)項(xiàng)準(zhǔn)考證號(hào)、姓名、總分開始元素結(jié)束元素前趨元素34683周光明588：

34684

李霞霞

61534685錢欣608素

……

……

……34700趙剛658后繼元線性表的運(yùn)算(操作)增加1個(gè)新的數(shù)據(jù)元素刪除1個(gè)指定數(shù)據(jù)元素查找指定的數(shù)據(jù)元素最高分考生最低分考生將表中的數(shù)據(jù)元素排序?qū)Ρ碇械臄?shù)據(jù)進(jìn)行計(jì)算計(jì)算平均分···34681張雷64834682王寧68234683周光明58834684李霞霞61534685錢欣608………………34700趙剛658準(zhǔn)考證號(hào)姓名總分3.數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)利用地址指針來表示元素之間的邏輯關(guān)系a1a2低地址鏈接表存儲(chǔ)結(jié)構(gòu)：高地址順序存儲(chǔ)結(jié)構(gòu)：借助數(shù)據(jù)元素在存儲(chǔ)器中的相對(duì)位置來表示數(shù)據(jù)元素之間的邏輯關(guān)系a2是a1的后繼元素a1a2a2是a1的后繼元素假設(shè)下面的有序表中姓名已按拼音排序例：線性表的實(shí)現(xiàn)方法之1程紅李軍劉林劉建平王曉林張小明使用數(shù)組實(shí)現(xiàn)，在內(nèi)存中順序存放元素：010

016

022

028

034

040

046程紅李軍劉林劉建平馬

明王曉林張小明如果要在表中加一個(gè)姓名:馬明，結(jié)果為：010

016

022

028

034

040

046分析：尋找指定的數(shù)據(jù)元素很容易插入元素或刪除元素很不方便程

紅李

軍劉

林劉建平王曉林張小明內(nèi)存地址線性表的實(shí)現(xiàn)方法之22種實(shí)現(xiàn)方法的對(duì)比：演示數(shù)組實(shí)現(xiàn)的空間開銷少；存取指定元素的速度比較塊鏈表實(shí)現(xiàn)時(shí)插入/刪除指定元素的速度快，表的長度不受限制第n個(gè)考生準(zhǔn)考證號(hào)、姓名、…∧第1個(gè)考生準(zhǔn)考證號(hào)、姓名、…Link第2個(gè)考生準(zhǔn)考證號(hào)、姓名、…Link使用鏈接表(linked

list)實(shí)現(xiàn)：數(shù)據(jù)元素在內(nèi)存中可不按順序存放，它們之間的順序用

“指針”來表示指針實(shí)際上就是后繼數(shù)據(jù)元素的地址第3個(gè)考生準(zhǔn)考證號(hào)、姓名、…Link樹(Tree)“樹”是一種與線性表不同的數(shù)據(jù)結(jié)構(gòu)，在樹中各數(shù)據(jù)元素之間的邏輯關(guān)系具有層次性層次1層次2層次3層次4根結(jié)點(diǎn)葉結(jié)點(diǎn)葉結(jié)點(diǎn)葉結(jié)點(diǎn)(樹的一般形式)葉結(jié)點(diǎn)(二叉樹)根結(jié)點(diǎn)葉結(jié)點(diǎn)葉結(jié)點(diǎn)葉結(jié)點(diǎn)樹的數(shù)組實(shí)現(xiàn)H-1S0D0L1Y1A2數(shù)組下標(biāo)012345說明：每個(gè)數(shù)組元素有2個(gè)數(shù)據(jù)項(xiàng)：一項(xiàng)是樹的節(jié)點(diǎn)的數(shù)據(jù)元素，另一項(xiàng)是該節(jié)點(diǎn)的父節(jié)點(diǎn)所在的數(shù)組元素下