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

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

主講人：譚定英“算法＋數(shù)據(jù)結(jié)構(gòu)＝程序〞程序就是在數(shù)據(jù)的某些特定的結(jié)構(gòu)和表示的根底上對(duì)于算法的描述。算法與數(shù)據(jù)結(jié)構(gòu)是程序設(shè)計(jì)中相輔相成、不可分割的兩個(gè)方面。抽象數(shù)據(jù)類(lèi)型有一定行為〔操作〕的抽象〔數(shù)學(xué)〕類(lèi)型。抽象出數(shù)據(jù)類(lèi)型的使用要求，而把它的具體表示方式和運(yùn)算的實(shí)現(xiàn)細(xì)節(jié)都隱藏起來(lái)。支持?jǐn)?shù)據(jù)類(lèi)型的實(shí)現(xiàn)與使用別離的原那么，是一種十分有效的對(duì)問(wèn)題進(jìn)行抽象與分解的思維工具。是面向?qū)ο蠹夹g(shù)與方法的主要理論根底。數(shù)據(jù)結(jié)構(gòu)“數(shù)據(jù)結(jié)構(gòu)是抽象數(shù)據(jù)類(lèi)型的物理實(shí)現(xiàn)〞。解決：1〕如何具體表示抽象數(shù)據(jù)類(lèi)型中的數(shù)學(xué)模型；2〕如何具體實(shí)現(xiàn)抽象數(shù)據(jù)類(lèi)型中操作。學(xué)習(xí)目的理解數(shù)據(jù)結(jié)構(gòu)和算法的概念；掌握設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)與算法的主要原理和方法；比較不同數(shù)據(jù)結(jié)構(gòu)和算法的特點(diǎn)。提高學(xué)生使用計(jì)算機(jī)解決問(wèn)題的能力。第一章緒論

本章重點(diǎn)：理解從問(wèn)題到程序的主要過(guò)程；體會(huì)抽象數(shù)據(jù)類(lèi)型、數(shù)據(jù)結(jié)構(gòu)和算法在問(wèn)題求解過(guò)程中的作用；了解數(shù)據(jù)結(jié)構(gòu)的主要概念和分類(lèi)；了解算法的概念和主要設(shè)計(jì)、分析方法。

1.1從問(wèn)題到程序

用計(jì)算機(jī)解決〔一種〕實(shí)際問(wèn)題，就是在計(jì)算機(jī)中建立一個(gè)解決問(wèn)題的模型。程序是使用程序設(shè)計(jì)語(yǔ)言精確描述的實(shí)現(xiàn)模型，它是問(wèn)題求解的一個(gè)可以在計(jì)算機(jī)上運(yùn)行的模型。程序中描述的數(shù)據(jù)用來(lái)表示問(wèn)題中涉及的對(duì)象，程序中描述的過(guò)程表示了對(duì)于數(shù)據(jù)的處理算法；通過(guò)接受〔具體〕實(shí)際問(wèn)題的輸入，經(jīng)過(guò)程序的運(yùn)行，便可以得到實(shí)際問(wèn)題的一個(gè)解。問(wèn)題求解〔1〕分析階段。

弄清用戶的需求是什么，設(shè)計(jì)者根據(jù)它進(jìn)行深入分析，使用標(biāo)準(zhǔn)說(shuō)明語(yǔ)言〔或數(shù)學(xué)語(yǔ)言等工具〕給出系統(tǒng)的需求模型〔或數(shù)學(xué)模型〕。

問(wèn)題求解〔2〕設(shè)計(jì)階段〔本課討論的重點(diǎn)〕。建立求解系統(tǒng)的實(shí)現(xiàn)模型，重點(diǎn)是算法的設(shè)計(jì)和數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)。對(duì)于大型的復(fù)雜的系統(tǒng)，還包括抽象數(shù)據(jù)類(lèi)型或者模塊的設(shè)計(jì)。一般而言，設(shè)計(jì)過(guò)程需要從粗到細(xì)，經(jīng)過(guò)屢次精化才能完成。

問(wèn)題求解〔3〕編碼階段。

根據(jù)設(shè)計(jì)的要求，采用適當(dāng)?shù)某绦蛟O(shè)計(jì)語(yǔ)言〔C語(yǔ)言、C++語(yǔ)言或Java語(yǔ)言〕，編寫(xiě)出可執(zhí)行的程序。

問(wèn)題求解〔4〕測(cè)試和維護(hù)。發(fā)現(xiàn)和排除在前幾個(gè)階段中產(chǎn)生的錯(cuò)誤，經(jīng)測(cè)試通過(guò)的程序便可投入運(yùn)行，在運(yùn)行過(guò)程中還可能發(fā)現(xiàn)隱含的錯(cuò)誤和問(wèn)題，因此還必須在使用中不斷維護(hù)和完善。

1.1.1問(wèn)題分析與抽象

為了能正確地解決問(wèn)題，必須首先深刻地理解需要解決的問(wèn)題。只有在深刻地認(rèn)識(shí)了這個(gè)問(wèn)題以后，才能著手確定這個(gè)問(wèn)題的解決方法。

信號(hào)燈問(wèn)題：為這個(gè)路口設(shè)計(jì)一個(gè)平安有效的交通信號(hào)燈的管理系統(tǒng)。信號(hào)燈問(wèn)題－分析

分析所有車(chē)輛的行駛路線的沖突問(wèn)題。這個(gè)問(wèn)題可以歸結(jié)為對(duì)車(chē)輛的可能行駛方向作某種分組，對(duì)分組的要求：使任一個(gè)組中各個(gè)方向行駛的車(chē)輛可以同時(shí)平安行駛而不發(fā)生碰撞。信號(hào)燈問(wèn)題－分析可以確定13個(gè)可能通行方向：A→B，A→C，A→D，B→A，B→C，B→D，D→A，D→B，D→C，E→A，E→B，E→C，E→D。

交叉路口行駛沖突的抽象〔不能同時(shí)行駛的用線連接〕信號(hào)燈問(wèn)題－抽象要求將圖1.2中的結(jié)點(diǎn)分組，使有線相連(互相沖突)的結(jié)點(diǎn)不在同一個(gè)組里。

這個(gè)問(wèn)題的解有許多“可行解〞。我們希望能夠設(shè)計(jì)一個(gè)最正確〔分組數(shù)最少〕的方案。稱(chēng)作“最優(yōu)解〞。

著色問(wèn)題－經(jīng)典問(wèn)題把上圖中的一個(gè)結(jié)點(diǎn)理解為一個(gè)國(guó)家，結(jié)點(diǎn)之間的連線看作兩國(guó)有共同邊界，上述問(wèn)題就變成著名的“著色問(wèn)題〞：即求出〔最少〕要幾種顏色可將圖中所有國(guó)家著色，使得任意兩個(gè)相鄰的國(guó)家顏色都不相同。

1.1.2程序的設(shè)計(jì)與實(shí)現(xiàn)

一個(gè)問(wèn)題的解決可以有許多方法，由于使用的工具是計(jì)算機(jī)，所以在選擇方法時(shí)必須充分考慮到計(jì)算機(jī)的特點(diǎn)和條件，才能找到比較巧妙的方法，比較快而且準(zhǔn)確地計(jì)算出需要的結(jié)果。選擇算法－窮舉法具體做法：從分為1、2、3…組開(kāi)始考察，逐個(gè)列舉出所有可能的著色方案，檢查這樣的分組方案是否滿足要求。首先滿足要求的分組，自然是問(wèn)題的最優(yōu)解。

窮舉法的分析這類(lèi)窮舉法對(duì)結(jié)點(diǎn)少的問(wèn)題(稱(chēng)為“規(guī)模小的〞問(wèn)題)還可以用；對(duì)規(guī)模大的問(wèn)題，由于求解時(shí)間會(huì)隨著實(shí)際問(wèn)題規(guī)模的增長(zhǎng)而指數(shù)性上升，使計(jì)算機(jī)無(wú)法承受。

貪心法先用一種顏色給盡可能多的結(jié)點(diǎn)上色；然后用另一種顏色在未著色結(jié)點(diǎn)中給盡可能多的結(jié)點(diǎn)上色；如此反復(fù)直到所有結(jié)點(diǎn)都著色為止。

貪心法的一個(gè)解(1)紅色：ABACADBADCED

(2)藍(lán)色：BCBDEA

(3)綠色：DADB

(4)白色：EBEC

抽象數(shù)據(jù)類(lèi)型的選擇為了便于給出上述算法的實(shí)現(xiàn)，可以按照抽象數(shù)據(jù)類(lèi)型的觀點(diǎn)，先把被處理的對(duì)象加以抽象。在著色問(wèn)題中具體解決：使用什么抽象數(shù)據(jù)類(lèi)型來(lái)表示地圖，以及使用什么樣的抽象數(shù)據(jù)類(lèi)型表示一組國(guó)家等。

抽象數(shù)據(jù)類(lèi)型的選擇使用一個(gè)圖〔圖是圖論研究的對(duì)象，也是一種重要的抽象數(shù)據(jù)類(lèi)型。〕表示地圖。使用國(guó)名〔圖中結(jié)點(diǎn)名〕的集合表示國(guó)家的分組。假設(shè)需要著色的圖是G，G中所有結(jié)點(diǎn)的集合記為G.V，集合V1存放圖中所有未被著色的結(jié)點(diǎn)，集合NEW存放可以用某顏色著色的所有結(jié)點(diǎn)。貪心法的描述

從V1中找出可用新顏色著色的結(jié)點(diǎn)集的工作可以用下面的偽碼描述：

置NEW為空集合;

for每個(gè)vV1do

ifv與NEW中所有結(jié)點(diǎn)間都沒(méi)有邊

從V1中去掉v;將v參加NEW;這個(gè)偽碼如果能執(zhí)行，集合NEW中就得到一組可以用新顏色著色的結(jié)點(diǎn)。著色程序可以反復(fù)調(diào)用這段偽碼，直到V1為空，每次調(diào)用選擇一種新顏色，這段偽碼執(zhí)行的次數(shù)就是需要的不同顏色個(gè)數(shù)。

假設(shè)〔ADT〕集合和圖支持下面行為：判斷元素v是否屬于集合V1表示為v

V1；從集合V1中去掉一個(gè)元素v表示為remove(V1,v)；向集合NEW里增加一個(gè)元素v用add(NEW,v)表示，判斷集合V1是否空集合表示為isEmpty(V1)

檢查結(jié)點(diǎn)v與結(jié)點(diǎn)集合NEW中各結(jié)點(diǎn)之間在圖G中是否有邊連接，用函數(shù)notAdjacentWith(NEW,v,G)表示。

抽象的著色算法intcolorUp(GraphG){ intcolor=0;//記錄使用的顏色數(shù) setV1=G.V;//V1初始化為圖G的結(jié)點(diǎn)集V setNEW; while(!isEmpty(V1)) { NEW={}; while(v

V1.notAdjacentWith(NEW,v,G)) { add(NEW,v);remove(V1,v); } ++color; } returncolor;//返回使用的顏色數(shù)}數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)如果集合和圖是程序設(shè)計(jì)語(yǔ)言中預(yù)定義的類(lèi)型，那么colorUp中用到的remove(V1,v)和add(NEW,v)等就應(yīng)該是語(yǔ)言中預(yù)定義的內(nèi)部函數(shù)，該程序就幾乎可以直接上機(jī)運(yùn)行。否那么程序員需要自己用語(yǔ)言所提供的〔類(lèi)型〕機(jī)制實(shí)現(xiàn)這些抽象數(shù)據(jù)類(lèi)型〔集合、圖等〕，這些正是數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)要討論的內(nèi)容。算法的精化在數(shù)據(jù)結(jié)構(gòu)確定以后，算法的描述可以進(jìn)一步根據(jù)設(shè)計(jì)的數(shù)據(jù)結(jié)構(gòu)進(jìn)行精化。如果這個(gè)問(wèn)題仍然是個(gè)比較復(fù)雜的問(wèn)題，就還需要選擇算法，也可能存在需要新抽象數(shù)據(jù)類(lèi)型和數(shù)據(jù)結(jié)構(gòu)。經(jīng)過(guò)這種反復(fù)的精化過(guò)程，最后將算法中所有局部都細(xì)化為能用程序設(shè)計(jì)語(yǔ)言描述的成分，得到的就是我們希望的程序。1.2抽象數(shù)據(jù)類(lèi)型

抽象數(shù)據(jù)類(lèi)型的概念最早出現(xiàn)在20世紀(jì)70年代，它是面向?qū)ο蠓椒ǖ闹匾碚摳住１緯?shū)在內(nèi)容的組織中僅僅使用了抽象數(shù)據(jù)類(lèi)型的概念，而沒(méi)有嚴(yán)格采用面向?qū)ο蟮某绦蛟O(shè)計(jì)語(yǔ)言的描述機(jī)制〔例如class〕。根本概念－類(lèi)型類(lèi)型〔type〕是一組值〔或者對(duì)象〕的集合。例如：布爾作為一種類(lèi)型是由真〔true〕和假〔false〕兩個(gè)值組成的集合；布爾向量也可以作為一種類(lèi)型，它的每個(gè)值是一個(gè)由true或false構(gòu)成的向量。根本概念－數(shù)據(jù)類(lèi)型數(shù)據(jù)類(lèi)型〔datatype〕通常是指在計(jì)算機(jī)〔語(yǔ)言〕中可以使用的一個(gè)類(lèi)型，它不但包括這個(gè)類(lèi)型的值的集合，還包括定義在這個(gè)類(lèi)型上的一組操作。例如：整數(shù)作為一個(gè)數(shù)據(jù)類(lèi)型是指在計(jì)算機(jī)上所能表示的〔不是數(shù)學(xué)意義上任意大小的〕所有整數(shù)和語(yǔ)言中定義的對(duì)于這些整數(shù)的全部操作〔整數(shù)的加、減、乘、除、取余等〕。根本概念－抽象數(shù)據(jù)類(lèi)型抽象數(shù)據(jù)類(lèi)型〔AbstractDataType簡(jiǎn)稱(chēng)為ADT〕可以定義作具有一定行為(操作)的抽象〔數(shù)學(xué)〕類(lèi)型。它不關(guān)心類(lèi)型中值的具體表示方式和數(shù)據(jù)類(lèi)型中定義的各種操作的具體實(shí)現(xiàn)方法，是所有可能的值的具體表示和各種操作的具體實(shí)現(xiàn)的抽象。意義和作用〔1〕抽象數(shù)據(jù)類(lèi)型的實(shí)質(zhì)是抽象出了數(shù)據(jù)類(lèi)型的使用要求，而把它的具體表示方式和運(yùn)算的實(shí)現(xiàn)細(xì)節(jié)都隱藏起來(lái)。抽象數(shù)據(jù)類(lèi)型僅僅規(guī)定了數(shù)據(jù)類(lèi)型應(yīng)該具有的行為〔操作〕。一旦抽象數(shù)據(jù)類(lèi)型被正確實(shí)現(xiàn)，就好似程序設(shè)計(jì)語(yǔ)言中所提供的數(shù)據(jù)類(lèi)型那樣，可以被自由使用。意義和作用〔2〕抽象數(shù)據(jù)類(lèi)型支持?jǐn)?shù)據(jù)類(lèi)型的實(shí)現(xiàn)與使用別離的原那么，允許獨(dú)立地考慮數(shù)據(jù)類(lèi)型的外部接口和內(nèi)部的實(shí)現(xiàn)。這使應(yīng)用程序只要按抽象數(shù)據(jù)類(lèi)型的接口統(tǒng)一其使用界面；可以不管其是否已經(jīng)實(shí)現(xiàn)，也不管它是如何實(shí)現(xiàn)的。對(duì)于系統(tǒng)的分解、設(shè)計(jì)、維護(hù)和修改均十分有利。

例1－抽象數(shù)據(jù)類(lèi)型圓

ADTCircleis

operations area 計(jì)算圓的面積 circumference 計(jì)算圓的周長(zhǎng) getRadius 獲取圓的半徑 setRadius 設(shè)置圓的半徑endADTCircle例2－集合抽象數(shù)據(jù)類(lèi)型ADTSetis

Operations isEmpty 判斷集合是否是空集合 add 給集合增加一個(gè)元素 remove 刪除集合中的一個(gè)元素 isIn 判斷一個(gè)元素是否在當(dāng)前集合中end

ADTSet1.3數(shù)據(jù)結(jié)構(gòu)關(guān)于數(shù)據(jù)結(jié)構(gòu)的研究，可以追溯到1972年C.A.R.Hoare奠基性的論文《數(shù)據(jù)結(jié)構(gòu)筆記》；而現(xiàn)代計(jì)算機(jī)所大量采用的根本數(shù)據(jù)結(jié)構(gòu)，最早的系統(tǒng)論述應(yīng)歸功于1973年D.E.Knuth的名著《計(jì)算機(jī)程序設(shè)計(jì)技巧》的問(wèn)世。為了學(xué)習(xí)和研究的方便，計(jì)算機(jī)科學(xué)家把常用的數(shù)據(jù)進(jìn)行分類(lèi)，總結(jié)出許多典型的數(shù)據(jù)結(jié)構(gòu)。什么是數(shù)據(jù)結(jié)構(gòu)〔通?！晨梢园褦?shù)據(jù)結(jié)構(gòu)理解為：計(jì)算機(jī)中表示〔存儲(chǔ)〕的、具有一定〔邏輯〕關(guān)系和行為的一組數(shù)據(jù)。其中的每個(gè)數(shù)據(jù)(元素)稱(chēng)為這個(gè)結(jié)構(gòu)的一個(gè)結(jié)點(diǎn)?！哺鶕?jù)面向?qū)ο蟮挠^點(diǎn)〕可以把數(shù)據(jù)結(jié)構(gòu)理解成為抽象數(shù)據(jù)類(lèi)型的物理實(shí)現(xiàn)。主要解決兩個(gè)問(wèn)題：如何具體表示抽象數(shù)據(jù)類(lèi)型中的數(shù)學(xué)模型；如何給出抽象數(shù)據(jù)類(lèi)型中需要操作的實(shí)現(xiàn)。數(shù)據(jù)結(jié)構(gòu)三要素：邏輯結(jié)構(gòu):指數(shù)學(xué)模型中的根本元素〔結(jié)點(diǎn)〕和元素之間的相互關(guān)系。存儲(chǔ)結(jié)構(gòu):指數(shù)學(xué)模型的具體表示方式，包括結(jié)點(diǎn)的表示和關(guān)系的表示。操作:指抽象數(shù)據(jù)類(lèi)型關(guān)心的各種行為在存儲(chǔ)結(jié)構(gòu)上的具體實(shí)現(xiàn)〔算法〕。例子－集合從集合抽象數(shù)據(jù)類(lèi)型的定義出發(fā)，將討論它的實(shí)現(xiàn)——集合數(shù)據(jù)結(jié)構(gòu)：根據(jù)數(shù)學(xué)的概念，集合中的元素是各不相同而且無(wú)序的〔邏輯結(jié)構(gòu)〕；將介紹使用順序表、單鏈表、散列表等等許多不同的集合表示方法〔存儲(chǔ)結(jié)構(gòu)〕；并且在這些不同的表示根底上，給出各自的行為實(shí)現(xiàn)算法〔操作〕。1.3.2數(shù)據(jù)結(jié)構(gòu)的分類(lèi)主要根據(jù)邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)進(jìn)行分類(lèi)

邏輯結(jié)構(gòu)B=<K，R>K是結(jié)點(diǎn)的有窮集合，R是K上的一個(gè)關(guān)系。K上的一個(gè)關(guān)系就是K上的一些二元組組成的集合K上的二元組是K中元素的有序?qū)?假設(shè)k,k’K,<k,k’>R，那么稱(chēng)k為k’的前驅(qū)，k’為k的后繼。沒(méi)有前驅(qū)的結(jié)點(diǎn)稱(chēng)為開(kāi)始結(jié)點(diǎn)，沒(méi)有后繼的結(jié)點(diǎn)稱(chēng)為終端結(jié)點(diǎn)。

K上不同的二元組集合構(gòu)成不同的關(guān)系。邏輯結(jié)構(gòu)的概念按邏輯結(jié)構(gòu)分類(lèi)

根據(jù)R的特點(diǎn)可以將數(shù)據(jù)結(jié)構(gòu)分為以下三類(lèi)：線性結(jié)構(gòu)：K中每個(gè)結(jié)點(diǎn)最多只有一個(gè)前驅(qū)和一個(gè)后繼的結(jié)構(gòu)。樹(shù)形結(jié)構(gòu)：K中每個(gè)結(jié)點(diǎn)最多只有一個(gè)前驅(qū)，但可有多個(gè)后繼的結(jié)構(gòu)。復(fù)雜結(jié)構(gòu)：K中結(jié)點(diǎn)的前驅(qū)、后繼結(jié)點(diǎn)個(gè)數(shù)都不作限制的結(jié)構(gòu)。*集合：它可以看成R為空的情況，即結(jié)點(diǎn)之間沒(méi)有任何關(guān)系。

按邏輯結(jié)構(gòu)分類(lèi)舉例

線性結(jié)構(gòu)舉例樹(shù)形結(jié)構(gòu)舉例

復(fù)雜結(jié)構(gòu)舉例

存儲(chǔ)結(jié)構(gòu)的概念存儲(chǔ)結(jié)構(gòu):數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)中的存儲(chǔ)(表示)。通常包括結(jié)點(diǎn)的表示和關(guān)系的表示。同一種邏輯結(jié)構(gòu)，可以采用不同的表示方式。例如，線性表既可以用順序〔一維數(shù)組〕的方式來(lái)表示〔順序表〕，也可以用鏈接的方式〔使用指針〕來(lái)表示〔單鏈表或雙鏈表〕。存儲(chǔ)結(jié)構(gòu)的設(shè)計(jì)目標(biāo)，是使用比較少的空間記錄邏輯結(jié)構(gòu)的必要信息，還能夠有效實(shí)現(xiàn)(抽象數(shù)據(jù)類(lèi)型中)要求的操作。根據(jù)存儲(chǔ)結(jié)構(gòu)分類(lèi)：順序表示：用一個(gè)連續(xù)的空間，順序存放數(shù)據(jù)結(jié)構(gòu)中的各個(gè)結(jié)點(diǎn)?！步Y(jié)點(diǎn)的關(guān)系需要另外存儲(chǔ)或者隱含其中〕鏈接表示：結(jié)點(diǎn)的存放位置是任意的，結(jié)點(diǎn)之間的關(guān)系通過(guò)與結(jié)點(diǎn)關(guān)聯(lián)的指針〔或者引用〕方式顯式表達(dá)出來(lái)。散列表示：又稱(chēng)為關(guān)鍵碼——地址轉(zhuǎn)換法。即選擇適當(dāng)?shù)纳⒘小搽s湊〕函數(shù)，根據(jù)關(guān)鍵碼的值將結(jié)點(diǎn)映射到給定的存儲(chǔ)空間〔散列表〕中。索引表示：索引與散列一樣，都給出一種從關(guān)鍵碼到存儲(chǔ)地址的映射方法。不同的是，散列法的映射是通過(guò)函數(shù)定義；而索引法是通過(guò)建立輔助的索引結(jié)構(gòu)解決。1.3.3結(jié)點(diǎn)與結(jié)構(gòu)在數(shù)據(jù)結(jié)構(gòu)的討論中重點(diǎn)研究的是“結(jié)構(gòu)〞，而把組成結(jié)構(gòu)的那些元素抽象成一個(gè)“結(jié)點(diǎn)〞。結(jié)點(diǎn)是數(shù)據(jù)結(jié)構(gòu)中的根本單位，在實(shí)際應(yīng)用中一個(gè)結(jié)點(diǎn)可以是一個(gè)字符、一個(gè)整數(shù)〔初等類(lèi)型〕，也可以是一個(gè)結(jié)構(gòu)〔組合類(lèi)型〕。1.3.4外存數(shù)據(jù)的組織

簡(jiǎn)單介紹常用的外存設(shè)備及其特點(diǎn)，討論文件的結(jié)構(gòu)和處理。掌握這些知識(shí)，對(duì)于理解涉及到外存上的數(shù)據(jù)結(jié)構(gòu)〔例如B/B+樹(shù)〕與算法〔例如歸并排序〕會(huì)有幫助.根本概念文件是邏輯記錄的集合。邏輯記錄〔簡(jiǎn)稱(chēng)記錄〕是應(yīng)用程序需要進(jìn)行內(nèi)外存交換的邏輯單位。每個(gè)記錄可以包含假設(shè)干數(shù)據(jù)項(xiàng)，其中能夠唯一標(biāo)識(shí)該記錄的數(shù)據(jù)項(xiàng)稱(chēng)為關(guān)鍵碼。對(duì)外存的數(shù)據(jù)必須按頁(yè)塊存取。頁(yè)塊又稱(chēng)物理記錄，是內(nèi)存與外存進(jìn)行交換的物理單位。外存設(shè)備目前廣泛使用的外存儲(chǔ)器有磁帶、磁盤(pán)、光盤(pán)和優(yōu)盤(pán)等。其中以磁帶和磁盤(pán)最具代表性。

外存的存取外存儲(chǔ)器上的邏輯記錄的地址由兩局部表示：邏輯記錄所在物理記錄的地址；邏輯記錄在物理記錄內(nèi)的相對(duì)位置。節(jié)省外存的存取時(shí)間的關(guān)鍵在于減少訪外的次數(shù)。由于緩沖區(qū)的大小受到內(nèi)存容量的限制，所以減少訪外次數(shù)的有效方法是精心設(shè)計(jì)文件的結(jié)構(gòu)，使外存中存放的記錄，相互關(guān)聯(lián)，以便于處理。1.4算法本課是以數(shù)據(jù)結(jié)構(gòu)為主線，算法為輔線組織內(nèi)容。因?yàn)槊糠N數(shù)據(jù)結(jié)構(gòu)上的操作，都需要一定算法。對(duì)于不同存儲(chǔ)結(jié)構(gòu)的選擇與評(píng)價(jià)，算法的好壞起著決定的因素。所有算法的實(shí)現(xiàn)也都需要數(shù)據(jù)結(jié)構(gòu)的支持。算法與數(shù)據(jù)結(jié)構(gòu)是程序設(shè)計(jì)的兩大支柱。它們相輔相成，互相依賴。

什么是算法算法是由有窮規(guī)那么構(gòu)成〔為解決某一類(lèi)問(wèn)題〕的運(yùn)算序列。算法可以有假設(shè)干輸入(初始值或條件)；算法通常又有假設(shè)干個(gè)輸出(計(jì)算結(jié)果〕。算法應(yīng)該具有有窮性。一個(gè)算法必須在執(zhí)行了有窮步之后結(jié)束。算法應(yīng)該具有確定性。算法的每一步，必須有確切的定義。算法應(yīng)該具有可行性。算法中的每個(gè)動(dòng)作，原那么上都是能夠由機(jī)器或人準(zhǔn)確完成的。算法的正確性如果一個(gè)算法以一組滿足初始條件的輸入開(kāi)始，那么該算法的執(zhí)行一定終止，并且在終止時(shí)得到滿足要求的〔輸出〕結(jié)果。算法設(shè)計(jì)的方法貪心法分治法回溯法動(dòng)態(tài)規(guī)劃法分枝界限法貪心法根本思想是：當(dāng)追求的目標(biāo)是一個(gè)問(wèn)題的最優(yōu)解時(shí)，設(shè)法把對(duì)整個(gè)問(wèn)題的求解工作分成假設(shè)干步驟來(lái)完成。在其中的每一個(gè)階段都選擇從局部看是最優(yōu)的方案，以期望通過(guò)各階段的局部最優(yōu)選擇到達(dá)整體的最優(yōu)。算法1.1解著色問(wèn)題時(shí)就是采用的貪心法。貪心法實(shí)際上不能保證都成功地產(chǎn)生一個(gè)全局性最優(yōu)解，但是通常可以得到一個(gè)可行的較優(yōu)解?！才e例〕分治法根本思想是:把一個(gè)規(guī)模較大的問(wèn)題分成兩個(gè)或多個(gè)較小的與原問(wèn)題相似的子問(wèn)題。首先對(duì)子問(wèn)題進(jìn)行求解，然后設(shè)法把子問(wèn)題的解合并起來(lái)，得出整個(gè)問(wèn)題的解，即對(duì)問(wèn)題分而治之。如果一個(gè)子問(wèn)題的規(guī)模仍然比較大，不能很容易地求得解，就可以對(duì)這個(gè)子問(wèn)題重復(fù)地應(yīng)用分治策略。二分法檢索就是用分治策略的典型例子?；厮莘ǜ舅枷胧?有一些問(wèn)題，需要通過(guò)徹底搜索所有可能情況尋找一個(gè)滿足某些預(yù)定條件的最優(yōu)解。由于徹底搜索的運(yùn)算量通常非常大，所以采取一步一步向前試探，當(dāng)有多種選擇時(shí)可以任意選擇一種，只要目前可行就繼續(xù)向前，一旦發(fā)現(xiàn)問(wèn)題或失敗就后退，回到上一步重新選擇，借助于回溯技巧和中間增加判斷，這樣常?？梢源蟠蟮販p少搜索時(shí)間。常見(jiàn)的迷宮問(wèn)題以及八皇后問(wèn)題都可以用回溯方法來(lái)解決。動(dòng)態(tài)規(guī)劃法與分治法相似都是把一個(gè)大問(wèn)題分解為假設(shè)干較小的子問(wèn)題，通過(guò)求解子問(wèn)題而得到原問(wèn)題的解。不同點(diǎn)是：分治法每次分解的子問(wèn)題數(shù)目比較少，子問(wèn)題之間界限清楚，處理的過(guò)程通常是自頂向下進(jìn)行；動(dòng)態(tài)規(guī)劃法分解的子問(wèn)題可能比較多，而且子問(wèn)題相互包含，為了重用已經(jīng)計(jì)算的結(jié)果，要把計(jì)算的中間結(jié)果全部保存起來(lái)，通常是自底向上進(jìn)行。在帶權(quán)圖中，求所有結(jié)點(diǎn)之間最短路徑的Floyd算法〔見(jiàn)第9章〕就屬于動(dòng)態(tài)規(guī)劃法。分枝界限法與回溯法相似，也是一種在表示問(wèn)題解空間的樹(shù)上進(jìn)行系統(tǒng)搜索的方法。所不同的是，回溯法使用了深度優(yōu)先策略，而分枝界限法一般采用廣度優(yōu)先策略或者采用最大收益〔或最小損耗〕策略，并且利用最優(yōu)解屬性的的上下界來(lái)控制搜索的分枝。最后一章，在討論背包問(wèn)題時(shí)，介紹了一個(gè)用分枝界限法設(shè)計(jì)的算法。1.4.3算法的精化實(shí)現(xiàn)一個(gè)算法，就是要把設(shè)計(jì)者頭腦中的算法思想轉(zhuǎn)化成計(jì)算機(jī)中可以執(zhí)行的程序。對(duì)于一個(gè)比較復(fù)雜的算法，其實(shí)現(xiàn)的過(guò)程往往需要經(jīng)過(guò)屢次細(xì)化才能完成。習(xí)慣上，把這個(gè)過(guò)程稱(chēng)為算法的精化。排序問(wèn)題假設(shè)有n≥1個(gè)不同的整數(shù)a0，a1，…，an-1，要求把這些整數(shù)從大到小進(jìn)行排序。排序算法可以明確地用下面的輸入和輸出關(guān)系來(lái)描述其功能：輸入：是含n個(gè)元素的整數(shù)數(shù)組，記為a，其中的元素依次為：a[0],a[1],…,a[n-1]。輸出：是輸入數(shù)組a中元素重新排列，記為a'，其中的元素依次為：a'[0],a'[1],…,a'[n-1]，滿足a'[i]≥a'[i+1]，對(duì)所有的0≤i<n-1都成立直接選擇排序的思想1從a中選出一個(gè)最大的整數(shù)放到一個(gè)空的數(shù)組a'中，作為a'中的第一個(gè)元素。2從a中剩下的元素中再選出最大的整數(shù)放到a'中，接在前一個(gè)已放入元素的后面。反復(fù)執(zhí)行步驟2，直到a中所有整數(shù)都放到排好序的數(shù)組a'中。第一步精化:將排序后的數(shù)據(jù)仍然存儲(chǔ)在排序前的數(shù)組里1從a[0]到a[n-1]中選出最大整數(shù)，設(shè)為a[j]，把a(bǔ)[0]與a[j]進(jìn)行交換。2從a[1]到a[n-1]中選出最大整數(shù)，設(shè)為a[j]，把a(bǔ)[1]與a[j]進(jìn)行交換。…………n從a[n-1]到a[n-1]中選出最大整數(shù)，設(shè)為a[j]，把a(bǔ)[n-1]與a[j]進(jìn)行交換〔因?yàn)閖=n-1,故這步可省〕。第二步精化:把上面執(zhí)行n次重復(fù)的工作，精化成一個(gè)循環(huán)。i以1為步長(zhǎng)，從0到n-2，循環(huán)執(zhí)行：(1)從a[i]到a[n-1]中選出最大的整數(shù)，設(shè)為a[j]。(2)把a(bǔ)[i]與a[j]進(jìn)行交換。第三步精化循環(huán)i以1為步長(zhǎng)，從0到n-2，執(zhí)行(1)j←i(2)循環(huán)k以1為步長(zhǎng)，從i+1到n-1，執(zhí)行：

假設(shè)a[k]>a[j]，那么j←k(3)t←a[i]；a[i]←a[j]；a[j]←t使用C語(yǔ)言的函數(shù)形式描述的算法voidsortIntArray(int[]a，intn){ inti,j,k,t; for(i=0;i<n-1;i=i+1){ j=i;/*把a(bǔ)[i]作為最大整數(shù)的初值*/ for(k=i+1;k<n-1;k=k+1)/*從a[i]到a[n-1]中選出最大整數(shù)*/ if(a[k]>a[j]) j=k; t=a[i];a[i]=a[j];a[j]=t; }}1.4.4算法分析分析一個(gè)算法主要是看這個(gè)算法的執(zhí)行需要花費(fèi)多少機(jī)器資源。在進(jìn)行算法分析時(shí)人們最關(guān)心的就是運(yùn)行算法所要花費(fèi)的時(shí)間和算法中使用的各種數(shù)據(jù)占有的空間。在文獻(xiàn)中習(xí)慣稱(chēng)之為算法的時(shí)間代價(jià)和空間代價(jià)。根本概念算法的空間代價(jià)(或稱(chēng)空間復(fù)雜性)：當(dāng)被解決問(wèn)題的規(guī)模(以某種單位計(jì)算)由1增至n時(shí)，解該問(wèn)題的算法所需占用的空間也以某種單位由f(1)增至f(n)，這時(shí)我們稱(chēng)該算法的空間代價(jià)是f(n)。算法的時(shí)間代價(jià)(或稱(chēng)時(shí)間復(fù)雜性)：當(dāng)問(wèn)題規(guī)模以某種單位由1增至n時(shí)，對(duì)應(yīng)算法所消耗的時(shí)間也以某種單位由g(1)增至g(n)，這時(shí)我們稱(chēng)該算法的時(shí)間代價(jià)是g(n)。問(wèn)題的規(guī)模、

空間單位和時(shí)間單位問(wèn)題的規(guī)模一般可以根據(jù)問(wèn)題本身的提法確定。例如對(duì)n個(gè)記錄進(jìn)行排序，這里n即可以作為問(wèn)題的規(guī)模?？臻g單位和時(shí)間單位沒(méi)有統(tǒng)一的規(guī)定，通常取算法描述中的初等數(shù)據(jù)占用的空間和根本操作消耗的時(shí)間為單位。大O表示法在描述算法分析的結(jié)果時(shí)，人們通常采用大O表示法：說(shuō)某個(gè)算法的時(shí)間代價(jià)(或者空間代價(jià))為O(f(n))，如果存在正的常數(shù)c和n0，當(dāng)問(wèn)題的規(guī)模n≥n0后，該算法的時(shí)間(或空間)代價(jià)T(n)≤c·f(n)。這時(shí)也稱(chēng)該算法的時(shí)間(或空間)代價(jià)的增長(zhǎng)率為f(n)。最壞情況下代價(jià)的數(shù)量級(jí)每個(gè)算法的實(shí)際運(yùn)行時(shí)的代價(jià)并不是固定不變的。由于不同的輸入?yún)?shù)，可能使一個(gè)算法的實(shí)際代價(jià)出現(xiàn)很大差異。要全面分析一個(gè)算法，應(yīng)該考慮它在最壞情況下的代價(jià)、最好情況下的代價(jià)和平均情況下的代價(jià)等。本書(shū)不是專(zhuān)門(mén)討論算法分析的教材，所以在分析算法時(shí)主要考慮它們?cè)谧顗那闆r下的代價(jià)，而且僅僅要求計(jì)算它們的數(shù)量級(jí)。大O表示法說(shuō)某個(gè)算法的時(shí)間代價(jià)(或者空間代價(jià))為O(f(n))，如果存在正的常數(shù)c和n0，當(dāng)問(wèn)題的規(guī)模n≥n0后，該算法的時(shí)間(或空間)代價(jià)T(n)≤c·f(n)。也稱(chēng)該算法的時(shí)間(或空間)代價(jià)的增長(zhǎng)率為f(n)。例如，如果有T(n)=3n3，很容易證明T(n)=O(n3)。當(dāng)然我們也可以證明T(n)=O(n4)。但從分析的精度來(lái)看，前一結(jié)論給出的是上確界(上界中最小的)，后者給出的僅是一般上界中的一個(gè)。計(jì)算規(guī)那么1)加法規(guī)那么T(n)=T1(n)+T2(n)=O(f1(n))+O(f2(n))=O(max(f1(n),f2(n)))2)乘法規(guī)那么T(n)=T1(n)×T2(n)=O(f1(n))×O(f2(n))=O(f1(n)×f2(n))

對(duì)于大O表示法，以非零正常數(shù)c形成的復(fù)雜性度量O(c)都居于同一個(gè)量級(jí)，人們習(xí)慣把它們統(tǒng)一記為O(1)。c<log2n<