1.1數(shù)據(jù)結(jié)構(gòu)的研究對(duì)象1.2數(shù)據(jù)結(jié)構(gòu)的發(fā)展概況1.3抽象數(shù)據(jù)型(ADT)1.4逐步求精的程序設(shè)計(jì)方法第1章緒論1.1數(shù)據(jù)結(jié)構(gòu)的研究對(duì)象1.1.1基本概念和術(shù)語1.1.2四種基本的邏輯結(jié)構(gòu)1.1.3四種基本的存儲(chǔ)結(jié)構(gòu)1.1.4數(shù)據(jù)結(jié)構(gòu)的研究對(duì)象1.1.1基本概念和術(shù)語一.客觀世界與計(jì)算機(jī)世界的關(guān)系

客觀世界

概念世界

機(jī)器世界映象抽象映象實(shí)現(xiàn)(邏輯模型)映象模擬

客觀世界與計(jì)算機(jī)的關(guān)系計(jì)算機(jī)科學(xué)是研究信息表示和信息處理的科學(xué)。信息在計(jì)算機(jī)內(nèi)是用數(shù)據(jù)表示的。用計(jì)算機(jī)解決實(shí)際問題的實(shí)質(zhì)可以用下圖表示：程序=數(shù)據(jù)結(jié)構(gòu)+算法程序=對(duì)象+行為例1書目自動(dòng)檢索系統(tǒng)線性表二.什么是數(shù)據(jù)結(jié)構(gòu)登錄號(hào)：書名：作者名：分類號(hào)：出版單位：出版時(shí)間：價(jià)格：書目卡片按書名按作者名按分類號(hào)索引表書目文件例2人機(jī)對(duì)奕問題樹……..……..…...…...…...…...例4多叉路口交通燈管理問題CEDABABACADBABCBDDADBDCEAEBECED圖數(shù)據(jù)結(jié)構(gòu)：數(shù)據(jù)結(jié)構(gòu)指的是數(shù)據(jù)元素之間的相互關(guān)系，這種關(guān)系是抽象的，即并不涉及數(shù)據(jù)元素的具體內(nèi)容。是數(shù)據(jù)元素及其相互間的關(guān)系的數(shù)學(xué)描述。三.基本概念和術(shù)語1.數(shù)據(jù)（data）數(shù)據(jù)是用于描述客觀事物的數(shù)值、字符，以及一切可以輸入到計(jì)算機(jī)中的并由計(jì)算機(jī)程序加以處理的符號(hào)的集合。其范圍隨著計(jì)算機(jī)技術(shù)的發(fā)展而不斷發(fā)展。2.數(shù)據(jù)元素（dataelement）數(shù)據(jù)元素是數(shù)據(jù)的基本單位，在計(jì)算機(jī)程序中通常作為一個(gè)整體進(jìn)行考慮和處理。3.數(shù)據(jù)項(xiàng)（dataitem）是數(shù)據(jù)的不可分割的最小單位，一個(gè)數(shù)據(jù)元素可由若干個(gè)數(shù)據(jù)項(xiàng)組成。4.數(shù)據(jù)對(duì)象（dataobject）性質(zhì)相同的元素的集合叫做數(shù)據(jù)對(duì)象。5.結(jié)點(diǎn)（node）數(shù)據(jù)元素在機(jī)內(nèi)的位串表示，即數(shù)據(jù)元素在計(jì)算機(jī)內(nèi)的映象。6.域/字段（field）當(dāng)數(shù)據(jù)元素由若干個(gè)數(shù)據(jù)項(xiàng)組成時(shí)，位串中對(duì)應(yīng)于各個(gè)數(shù)據(jù)項(xiàng)的子串稱為域/字段，是數(shù)據(jù)元素中數(shù)據(jù)項(xiàng)在計(jì)算機(jī)中的映象。7.信息表（informationtable）計(jì)算機(jī)程序所作用的一組數(shù)據(jù)通常稱為信息表，是數(shù)據(jù)對(duì)象在計(jì)算機(jī)中的映象。數(shù)據(jù)的邏輯結(jié)構(gòu)：數(shù)據(jù)結(jié)構(gòu)中描述的是數(shù)據(jù)元素之間的抽象關(guān)系(邏輯關(guān)系)，稱為邏輯結(jié)構(gòu)。數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)/物理結(jié)構(gòu)：數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的表示（實(shí)現(xiàn)/映象）稱為存儲(chǔ)結(jié)構(gòu)/物理結(jié)構(gòu)。三.數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)元素之間的關(guān)系（邏輯結(jié)構(gòu)）在計(jì)算機(jī)中有兩種基本的表示方法：順序映象(表示)和非順序映象(表示)，從而導(dǎo)致兩種不同的存儲(chǔ)結(jié)構(gòu)：順序結(jié)構(gòu)和鏈?zhǔn)浇Y(jié)構(gòu)。順序映象（表示）的特點(diǎn)是借助數(shù)據(jù)元素在存儲(chǔ)器中的相對(duì)位置來表示數(shù)據(jù)元素之間的邏輯關(guān)系。非順序映象（表示）的特點(diǎn)是借助指示數(shù)據(jù)元素存儲(chǔ)地址的指針來表示數(shù)據(jù)元素之間的邏輯關(guān)系。1.1.2四種基本的邏輯結(jié)構(gòu)4.集合結(jié)構(gòu)結(jié)構(gòu)中的數(shù)據(jù)元素之間除了“屬于同一個(gè)集合”的關(guān)系之外，別無其他關(guān)系。關(guān)系比較松散，可用其他結(jié)構(gòu)來表示。1.線性結(jié)構(gòu)結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一個(gè)對(duì)一個(gè)的關(guān)系，即線性關(guān)系，每個(gè)元素至多有一個(gè)直接前驅(qū)和后繼。2.樹型結(jié)構(gòu):結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一個(gè)對(duì)多個(gè)的關(guān)系，即層次關(guān)系，即每一層上的元素可能與下層的多個(gè)元素相關(guān)，而至多與上層的一個(gè)元素相關(guān)。3.網(wǎng)狀/圖型結(jié)構(gòu)結(jié)構(gòu)中的數(shù)據(jù)元素之間存在多個(gè)對(duì)多個(gè)的關(guān)系，即任意關(guān)系，任何元素之間都可能有關(guān)系。一般將邏輯結(jié)構(gòu)分為線性結(jié)構(gòu)（1）和非線性結(jié)構(gòu)（2，3，4）兩種。1.1.3四種基本的存儲(chǔ)方式1.順序存儲(chǔ)方式該方法把邏輯上相鄰的結(jié)點(diǎn)存儲(chǔ)在物理位置上相鄰的存儲(chǔ)單元里，結(jié)點(diǎn)間的邏輯關(guān)系由存儲(chǔ)單元的鄰接關(guān)系來體現(xiàn)。由此得到的存儲(chǔ)表示稱為順序存儲(chǔ)結(jié)構(gòu)（SequentialStorageStructure），通常借助程序語言的數(shù)組描述。該方法主要應(yīng)用于線性的數(shù)據(jù)結(jié)構(gòu)。非線性的數(shù)據(jù)結(jié)構(gòu)也可通過某種線性化的方法實(shí)現(xiàn)順序存儲(chǔ)。借助元素在存儲(chǔ)器中的相對(duì)位置來表示數(shù)據(jù)元素間的邏輯關(guān)系1.1.3四種基本的存儲(chǔ)方式該方法不要求邏輯上相鄰的結(jié)點(diǎn)在物理位置上亦相鄰，結(jié)點(diǎn)間的邏輯關(guān)系由附加的指針字段表示。由此得到的存儲(chǔ)表示稱為鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)（LinkedStorageStructure）,通常借助于程序語言的指針類型描述。借助指示元素存儲(chǔ)地址的指針表示數(shù)據(jù)元素間的邏輯關(guān)系。2.鏈?zhǔn)酱鎯?chǔ)方式1.1.3四種基本的存儲(chǔ)方式3.索引存儲(chǔ)方式該方法通常在儲(chǔ)存結(jié)點(diǎn)信息的同時(shí)，還建立附加的索引表。索引表由若干索引項(xiàng)組成。若每個(gè)結(jié)點(diǎn)在索引表中都有一個(gè)索引項(xiàng)，則該索引表稱之為稠密索引（DenseIndex）。若一組結(jié)點(diǎn)在索引表中只對(duì)應(yīng)一個(gè)索引項(xiàng)，則該索引表稱為稀疏索引(SpareIndex)。索引項(xiàng)的一般形式是：

(關(guān)鍵字、地址)

關(guān)鍵字是能唯一標(biāo)識(shí)一個(gè)結(jié)點(diǎn)的那些數(shù)據(jù)項(xiàng)。稠密索引中索引項(xiàng)的地址指示結(jié)點(diǎn)所在的存儲(chǔ)位置；稀疏索引中索引項(xiàng)的地址指示一組結(jié)點(diǎn)的起始存儲(chǔ)位置。1.1.3四種基本的存儲(chǔ)方式該方法的基本思想是：根據(jù)結(jié)點(diǎn)的關(guān)鍵字直接計(jì)算出該結(jié)點(diǎn)的存儲(chǔ)地址。4.散列存儲(chǔ)方式四種基本存儲(chǔ)方法，既可單獨(dú)使用，也可組合起來對(duì)數(shù)據(jù)結(jié)構(gòu)進(jìn)行存儲(chǔ)映像。

同一邏輯結(jié)構(gòu)采用不同的存儲(chǔ)方法，可以得到不同的存儲(chǔ)結(jié)構(gòu)選擇何種存儲(chǔ)結(jié)構(gòu)來表示相應(yīng)的邏輯結(jié)構(gòu)，視具體要求而定，主要考慮操作的方便及算法的時(shí)空要求。

數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)密切相關(guān) 算法設(shè)計(jì) 邏輯結(jié)構(gòu) 算法實(shí)現(xiàn) 存儲(chǔ)結(jié)構(gòu) 1.1.4數(shù)據(jù)結(jié)構(gòu)的研究對(duì)象數(shù)據(jù)結(jié)構(gòu)的研究對(duì)象(研究?jī)?nèi)容)1.數(shù)據(jù)對(duì)象的結(jié)構(gòu)形式,各種數(shù)據(jù)結(jié)構(gòu)的性質(zhì)(邏輯結(jié)構(gòu));2.數(shù)據(jù)對(duì)象和”關(guān)系”在計(jì)算機(jī)中的表示(物理結(jié)構(gòu)/存儲(chǔ)結(jié)構(gòu));3.數(shù)據(jù)結(jié)構(gòu)上定義的基本操作(算法)及其實(shí)現(xiàn);4.算法的效率;5.數(shù)據(jù)結(jié)構(gòu)的應(yīng)用,如數(shù)據(jù)分類,檢索等.

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

數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)的操作：檢索、排序、插入、刪除、修改等

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

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

順序存儲(chǔ)

鏈?zhǔn)酱鎯?chǔ)線性表?xiàng)ｊ?duì)列樹形結(jié)構(gòu)圖形結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)與算法的四個(gè)方面：

散列存儲(chǔ)

索引存儲(chǔ)時(shí)間和空間效率數(shù)據(jù)結(jié)構(gòu)與算法的應(yīng)用1.2數(shù)據(jù)結(jié)構(gòu)的發(fā)展概況1.程序設(shè)計(jì)方法學(xué)的發(fā)展極大地促進(jìn)了數(shù)據(jù)結(jié)構(gòu)的發(fā)展2.數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)科學(xué)中的地位(1)計(jì)算機(jī)科學(xué)及其應(yīng)用的發(fā)展時(shí)數(shù)據(jù)結(jié)構(gòu)成為獨(dú)立學(xué)科.(2)以數(shù)據(jù)為中心的程序設(shè)計(jì)方法推動(dòng)了數(shù)據(jù)結(jié)構(gòu)的發(fā)展.面向過程的程序設(shè)計(jì)的特點(diǎn)是以程序?yàn)橹行?側(cè)重于建立程序,程序在簡(jiǎn)單的數(shù)據(jù)結(jié)構(gòu)上進(jìn)行復(fù)雜的運(yùn)算,軟件設(shè)計(jì)的主要工作就是設(shè)計(jì)求解問題的過程.注重于程序設(shè)計(jì)技巧,適合于數(shù)值計(jì)算.結(jié)構(gòu)化特別是面向?qū)ο蟮某绦蛟O(shè)計(jì)以數(shù)據(jù)(結(jié)構(gòu))為中心，系統(tǒng)采用復(fù)雜的數(shù)據(jù)結(jié)構(gòu)來描述系統(tǒng)狀態(tài)，程序圍繞數(shù)據(jù)結(jié)構(gòu)進(jìn)行加工。這種編程語言更適合于非數(shù)值計(jì)算。(1)是計(jì)算機(jī)科學(xué)的一門專業(yè)基礎(chǔ)和核心課程。(2)是學(xué)習(xí)、設(shè)計(jì)和實(shí)現(xiàn)操作系統(tǒng)、編譯系統(tǒng)、數(shù)據(jù)庫系統(tǒng)和其它應(yīng)用系統(tǒng)的重要基礎(chǔ)。1.3抽象數(shù)據(jù)型(ADT)1.3.1抽象數(shù)據(jù)型的定義1.3.2數(shù)據(jù)型,數(shù)據(jù)結(jié)構(gòu)和ADT1.3.3抽象數(shù)據(jù)型的規(guī)格1.3.4抽象數(shù)據(jù)型的實(shí)現(xiàn)1.3.5多層次抽象技術(shù)1.3.6多層次抽象技術(shù)1.3.1抽象數(shù)據(jù)型的定義一.抽象數(shù)據(jù)型的定義1.定義:是一個(gè)數(shù)學(xué)模型和在該模型上定義的操作集合的總稱。

注:

ADT是程序設(shè)計(jì)語言中數(shù)據(jù)類型概念的進(jìn)一步推廣和進(jìn)一步抽象。

ADTint=({x|x

Z}，{+,-,*,/,%,

,==})2.ADT的優(yōu)點(diǎn)使用者只要知道這些操作的用途就可以編程序；至于這些操作是怎樣實(shí)現(xiàn)的，以及整型數(shù)在內(nèi)存中是如何表示的，并不影響使用者所編程序的編碼形式。二.抽象數(shù)據(jù)型的實(shí)現(xiàn)1.抽象型實(shí)現(xiàn)的含義就是將ADT轉(zhuǎn)換成程序設(shè)計(jì)語言的說明語句，加上對(duì)應(yīng)于該ADT中的每個(gè)操作的函數(shù)。換句話說，就是用適當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)來表示ADT中的數(shù)學(xué)模型,并用一組函數(shù)來實(shí)現(xiàn)該模型上的各種操作。2.注意事項(xiàng)

(1)同一數(shù)學(xué)模型上定義不同的操作集，則它們代表不同的ADT;(2)把ADT的描述與用某種程序設(shè)計(jì)語言實(shí)現(xiàn)ADT加以區(qū)別，這是大型程序設(shè)計(jì)中當(dāng)前的發(fā)展趨勢(shì)。如下圖所示:三.抽象數(shù)據(jù)型圖示ADT規(guī)格描述ADT實(shí)現(xiàn)語法描述語義描述數(shù)據(jù)結(jié)構(gòu)

(表示)操作(算法)的實(shí)現(xiàn)(函數(shù))抽象數(shù)據(jù)型(ADT)圖示1.3.2數(shù)據(jù)型、數(shù)據(jù)結(jié)構(gòu)和ADT1.三個(gè)概念的各自含義及相互關(guān)系(1)各自含義數(shù)據(jù)型是該類型變量的存儲(chǔ)格式和所有可能取值的集合;數(shù)據(jù)結(jié)構(gòu)則是抽象數(shù)據(jù)型中數(shù)學(xué)模型的表示;抽象數(shù)據(jù)型是一個(gè)數(shù)學(xué)模型及在該模型上定義的操作集的總稱。(2)相互關(guān)系數(shù)據(jù)型是根據(jù)數(shù)據(jù)結(jié)構(gòu)分類的,同類型的數(shù)據(jù)元素的數(shù)據(jù)結(jié)構(gòu)相同數(shù)據(jù)結(jié)構(gòu)是ADT中數(shù)學(xué)模型的表示；ADT是數(shù)據(jù)類型的進(jìn)一步推廣和進(jìn)一步抽象。2.信息聚集的三種方式數(shù)組、結(jié)構(gòu)（體）和文件1.3.3抽象數(shù)據(jù)型的規(guī)格描述一.ADT的規(guī)格描述

即ADT的形式化描述，包括語法規(guī)格和語義規(guī)格描述規(guī)格描述必須具有:(1)完整性:要能反映所定義的抽象數(shù)據(jù)型的全部特性(2)統(tǒng)一性:應(yīng)是一個(gè)前后協(xié)調(diào)的整體，不應(yīng)自相矛盾(3)通用性:所定義的抽象數(shù)據(jù)型應(yīng)適用于盡量廣泛的對(duì)象(4)獨(dú)立性:應(yīng)盡可能不依賴于程序語言(1)是程序操作/算法實(shí)現(xiàn)的依據(jù);(2)是作為與程序并存的文檔,用于程序的調(diào)試和維護(hù)。二.規(guī)格描述的作用三.規(guī)格描述原則1.3.3抽象數(shù)據(jù)型的規(guī)格描述四.ADT的規(guī)格描述方法1.語法規(guī)格描述

就是給出所指定的操作的名稱以及輸入輸出類型；2.語義規(guī)格描述

給出符合語法規(guī)定的表達(dá)式的語義,即表達(dá)形式所起的作用是什么或者效果是什么或者是讓程序作什么(但不涉及“怎么做”)3.ADT規(guī)格描述方法

首先描述它的定義域;

然后描述各個(gè)操作及其作用(給予法和語義規(guī)格描述)四.ADT的規(guī)格描述方法4.規(guī)格描述舉例（ADT棧）

語法規(guī)格描述部分：typeStack[Elementype];NEWSTACK()→Stack,PUSH(Elementtype,Stack)→Stack,POP(Stack)→Stack∪{UNDEFINED},TOP(Stack)→Elementtype∪{UNDEFINED},EMPTY(Stack)→Boolean;語法部分給出所指定的操作的名稱以及輸入輸出類型

首先，ADT棧是同類單元Elementtype的集合;

然后，用語法和語義規(guī)格來描述各個(gè)操作及其作用，并且體現(xiàn)ADT棧的“后進(jìn)先出LIFO”的特征。4.規(guī)格描述舉例（ADT棧）

語義規(guī)格描述部分：declarestk:Stack,elm:Elementtype;POP(NEWSTACK)=NEWSTACK,//UNDEFINEDPOP(PUSH(elm,stk))=stk,TOP(NEWSTACK)=UNDEFINED,TOP(PUSH(elm,stk))=elm,EMPTY(NEWSTACK)=TRUE,EMPTY(PUSH(elm,stk))=FALSE;語義部分主要有一組等式組成，嚴(yán)格規(guī)定了各種操作的功能及相互關(guān)系5.注意事項(xiàng)

(1)對(duì)于同一ADT，在同樣語法定義之下可以有不同語義定義;(2)不同的語義定義，將影響ADT的實(shí)現(xiàn)，因此要做到語義定義和實(shí)現(xiàn)的協(xié)調(diào)一致。1.3.4抽象數(shù)據(jù)型實(shí)現(xiàn)一.ADT的實(shí)現(xiàn)原則(1)應(yīng)符合規(guī)格描述的定義；

(2)應(yīng)有盡可能好的通用性；

(3)應(yīng)盡可能具有良好的獨(dú)立性，在結(jié)構(gòu)上應(yīng)成為獨(dú)立的模塊；將內(nèi)部細(xì)節(jié)屏蔽起來。二.ADT的實(shí)現(xiàn)舉例（ADT棧的帶頭結(jié)點(diǎn)的鏈?zhǔn)綄?shí)現(xiàn)）1)數(shù)據(jù)結(jié)構(gòu)描述enumboolean{FALSE,TRUE};structnode{ elementtypeval; node*next;};//結(jié)點(diǎn)的”型”typedefnode*stack;//棧的”型”二.ADT的實(shí)現(xiàn)舉例（ADT棧的帶頭結(jié)點(diǎn)的鏈?zhǔn)綄?shí)現(xiàn)）2)基本操作的實(shí)現(xiàn)stackNEWSTACK(){stacks;s=newnode；/*s=(node*)malloc(sizeof(node));*/s->next=NULL；

returns;}valnext

s2)基本操作的實(shí)現(xiàn)voidPUSH(elm,stk)elementtypeelm;stackstk;{stacks;s=newnode;s->val=elm;s->next=stk->next;stk->next=s;}valnextselmvalnextstk

dba二.ADT的實(shí)現(xiàn)舉例（ADT棧的帶頭結(jié)點(diǎn)的鏈?zhǔn)綄?shí)現(xiàn)）2)基本操作的實(shí)現(xiàn)voidPOP(stk)stackstk;{stacks;if(stk->next){

/*stk->next!=NULL*/s=stk->next;stk->next=s->next;deletes;/*free(s)*/}}svalnextevalnextstk

dba二.ADT的實(shí)現(xiàn)舉例（ADT棧的帶頭結(jié)點(diǎn)的鏈?zhǔn)綄?shí)現(xiàn)）2)基本操作的實(shí)現(xiàn)elementtypeTOP(stk)stackstk;{if(stk->next)return(stk->next->val)；elsereturnNULLELE;}二.ADT的實(shí)現(xiàn)舉例（ADT棧的帶頭結(jié)點(diǎn)的鏈?zhǔn)綄?shí)現(xiàn)）2)基本操作的實(shí)現(xiàn)booleanEMPTY(stk)stackstk;{if(stk->next)returnFALSE;elsereturnTRUE;}二.ADT的實(shí)現(xiàn)舉例（ADT棧的帶頭結(jié)點(diǎn)的鏈?zhǔn)綄?shí)現(xiàn)）三.抽象數(shù)據(jù)型的應(yīng)用-數(shù)制轉(zhuǎn)換

是計(jì)算機(jī)實(shí)現(xiàn)計(jì)算的基本問題.方法:除留余數(shù)法.例如對(duì)輸入的任意非負(fù)十進(jìn)制整數(shù),打印輸出與其等值的八進(jìn)制數(shù).voidmain(){stackS=NEWSTACK();cin>>n;while(n){PUSH(n%8,S);n/=8;}while(!EMPTY(S)){cout<<TOP(S);POP(S);}}1.3.5多層次抽象技術(shù)1.逐層抽象方法

對(duì)于較復(fù)雜的數(shù)據(jù)類型，先將較簡(jiǎn)單、較基本的數(shù)據(jù)類型抽象出來,給出定義；再用已定義的數(shù)據(jù)類型去定義更復(fù)雜的數(shù)據(jù)類型,完成對(duì)后者的抽象。就是說，用已定義的類型來表述正要定義的類型的定義域，并用前者的操作來表述后者的操作這就是所謂逐層抽象的方法。

逐層抽象實(shí)質(zhì)是用已知的簡(jiǎn)單數(shù)據(jù)類型定義更復(fù)雜的數(shù)據(jù)類型。2.優(yōu)點(diǎn)

(1)由于在定義高層數(shù)據(jù)類型時(shí)不必考慮低層數(shù)據(jù)類型及其操作的內(nèi)部細(xì)節(jié),因而對(duì)復(fù)雜數(shù)據(jù)類型進(jìn)行抽象可以簡(jiǎn)化許多瑣事。

(2)多層次抽象化通?？梢圆捎米缘紫蛏系姆绞竭M(jìn)行，先抽象出最基本的數(shù)據(jù)類型，然后利用它們定義上一層數(shù)據(jù)類型，如此逐層向上，直至到達(dá)最高層的數(shù)據(jù)類型為止,這樣可以防止低層次倒過來引用高層數(shù)據(jù)類型，保證整個(gè)系統(tǒng)的有序?qū)哟谓Y(jié)構(gòu)。

多層次抽象化的最終目的是建立最高層的數(shù)據(jù)類型，因此低層應(yīng)該服從高層的要求。自底向上方式是底層的抽象帶有一定的盲目性，在抽象過程中，可能從高層返回低層作修正，也就是不得不穿插一些自頂向下的過程。3.缺點(diǎn)1.3.6抽象數(shù)據(jù)型的優(yōu)點(diǎn)

采用抽象數(shù)據(jù)型的方法進(jìn)行軟件（特別是大型軟件）系統(tǒng)的設(shè)計(jì)，具有許多明顯的優(yōu)點(diǎn)：

首先，它降低了軟件設(shè)計(jì)的復(fù)雜性。

其次，抽象數(shù)據(jù)型可提高程序的可讀性和可維護(hù)性。

第三，由于抽象數(shù)據(jù)型的使用降低了程序的復(fù)雜度，使程序的各部分相對(duì)分離，因而程序的正確性容易得到保證。

第四，有利于軟件重用。1.4逐步求精的程序設(shè)計(jì)方法1.4.1如何求解一個(gè)問題一.算法的定義1.計(jì)算能由一個(gè)給定的計(jì)算模型機(jī)械地執(zhí)行的規(guī)則(或步驟)序列稱為該計(jì)算模型的一個(gè)計(jì)算.注:

一個(gè)計(jì)算機(jī)程序是一個(gè)計(jì)算(計(jì)算模型是計(jì)算機(jī));

計(jì)算可能永遠(yuǎn)不停止—不是算法.2.算法是一個(gè)滿足下列條件的一個(gè)計(jì)算：(1)有窮性/終止性：總是在執(zhí)行有窮步后停止;(2)確定性：每一步必須有嚴(yán)格的定義和確定的動(dòng)作;(3)能行性：每個(gè)動(dòng)作都能被精確地機(jī)械執(zhí)行;(4)輸入：有0個(gè)和多個(gè)滿足約束條件的輸入;(5)輸出：有一個(gè)或多個(gè)滿足約束條件的結(jié)果.3.算法的逐步求精就是對(duì)用自然語言等描述的算法逐步細(xì)致化、精確化和形式化，追求的目標(biāo)是把算法變成可以執(zhí)行的程序。二.求解問題的一般過程

1.模型化：對(duì)實(shí)際問題進(jìn)行分析，選擇適當(dāng)?shù)臄?shù)學(xué)模型來描述問題，即模型化;

2.確定算法：根據(jù)模型，找出解決問題的方法(算法);

3.逐步求精：就是對(duì)用自然語言等描述的算法逐步細(xì)致化、精確化和形式化，這一階段可能包括多步求精。當(dāng)逐步求精到某一步時(shí)，根據(jù)程序中所使用的數(shù)據(jù)形式，定義若干ADT，并且用ADT中的操作代替對(duì)應(yīng)的非形式語句；

4.ADT的實(shí)現(xiàn)：對(duì)每個(gè)ADT，選擇適當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)表示數(shù)學(xué)模型，并用相應(yīng)的函數(shù)實(shí)現(xiàn)每個(gè)操作。1.4.2算法逐步求精例1.4.2交叉路口的交通安全管理問題問題描述：

一個(gè)具有多有多條通路的交叉路口,當(dāng)允許某些通路上的車輛在交叉路口“拐彎”時(shí),必須對(duì)其他一些通路上的車輛加以限制,不允許同時(shí)在交叉路口“拐彎”,以免發(fā)生碰撞.所有這些可能的“拐彎”組成一個(gè)集合.DCBAE圖1.5一個(gè)交叉路口基本要求：

把這個(gè)集合分成盡可能少的組,使得每組中所有的“拐彎”都能同時(shí)進(jìn)行而不發(fā)生碰撞.這樣,每組對(duì)應(yīng)一個(gè)指揮燈,因而實(shí)現(xiàn)了用盡可能少的指揮燈完成交叉路口的管理.有5條組成的交叉路口,其中有2條路是單行道,把從一條路到另一條路的通路稱為“拐彎”,有的“拐彎”可以同時(shí)通過,有些“拐彎”不能同時(shí)通過,共有13個(gè)“拐彎”.要求:(1)設(shè)置一組交通燈,實(shí)現(xiàn)安全管理(2)使交通燈的數(shù)目最少.例1.4.2的求解過程1.模型化：(1)用圖作為交叉路口的數(shù)學(xué)模型;(2)每個(gè)“拐彎”對(duì)應(yīng)圖中的一個(gè)頂點(diǎn);(3)若兩個(gè)“拐彎”不能同時(shí)進(jìn)行,則用用一條邊把這兩個(gè)“拐彎”所對(duì)應(yīng)的兩個(gè)結(jié)點(diǎn)連接起來，并且說這兩個(gè)頂點(diǎn)是相鄰的。ABACADBADCEDBCBDEADADBEBECDCBAE

一個(gè)交叉路口2.確定算法：(1)窮舉法;(2)試探法(3)貪心法“貪心”算法的思想是首先用第一種顏色對(duì)圖中盡可能多的頂點(diǎn)著色(盡可能多表現(xiàn)出“貪心”)然后用第二種顏色對(duì)余下的頂點(diǎn)中盡可能多的頂點(diǎn)著色如此等等，直至所有的頂點(diǎn)都著完色。ABACADBADCEDBCBDEADADBEBEC當(dāng)用一種新顏色對(duì)余下的頂點(diǎn)著色時(shí)我們采取下列步驟:（1）選取某個(gè)未著色的頂點(diǎn)，并且用新顏色對(duì)它著色。（2）掃描所有未著色的頂點(diǎn)集，對(duì)其中的每個(gè)頂點(diǎn)，確定它是否與已著新顏色的任何頂點(diǎn)相鄰。若不相鄰，則用新顏色對(duì)它著色。用C語言描述的"貧心"算法如下:voidgreedy(G,newclr)GRAPHG;SETnewclr;/*類型GRAPH和SET有待具體說明*//*本程序把G中可以著同一色的頂點(diǎn)放入newclr*/{(1)newclr=

(2)while(G中有未著色的頂點(diǎn)v)(3)if(v不與newclr中的任何頂點(diǎn)相鄰){(4)對(duì)v著色；(5)將v放入newclr；}};其中，G是被著色的圖，newclr的初值為空，算法執(zhí)行的結(jié)果形成可以著相同顏色的頂點(diǎn)的集合newclr。只要重復(fù)調(diào)用greedy算法，直到圖中的所有頂點(diǎn)都被著色為止，即可求出問題的解。3.逐步求精：第一步求精：

voidgreedy(G,newclr)GRAPHG;SETnewclr;/*類型GRAPH和SET有待具體說明*/{intfound;(1)newclr=

;(2)while(G中有未著色的頂點(diǎn)v){(3.1)found=0;/*found的初值為false*/(3.2)for(newclr中的每一個(gè)頂點(diǎn)w）(3.3)if(v與w相鄰)(3.4)found=1;(3.5)if(found==0){/*v與newclr中的任何頂點(diǎn)都不相鄰*/(4)對(duì)v著色；(5)將v放入newclr；

}}};3.逐步求精：第二步求精：

voidgreedy(GRAPHG,SETnewclr){intfound;newclr=%;v=G中第一個(gè)未著色的頂點(diǎn)；

while(v!=0){/*G中還有未著色的頂點(diǎn)v*/found=0;w=newclr中的第一個(gè)頂點(diǎn)；

while(w!=0){/*newclr中的頂點(diǎn)還沒取盡*/if(v與w相鄰)found=1;w=newclr中的下個(gè)頂點(diǎn)；

};if(found==0){

對(duì)v著色；將v放入newclr；

};v=G中下一個(gè)未著色的頂點(diǎn)；

}};3.逐步求精：第三步求精：由上一步求精的結(jié)果可見，算法中大部分操作都?xì)w結(jié)為對(duì)圖和集合的操作。設(shè)G和S分別是抽象數(shù)據(jù)型GRAPH和SET的實(shí)例，我們?cè)贕上規(guī)定如下操作：

(1)FIRSTG(G)返回G中的第一個(gè)未加標(biāo)記的（未著色的）元素；若G中沒有這樣的元素存在，則返回NULL。

(2)EDGE(v,w,G)若v和w在G中相鄰，則返回true，否則返回false (3)MARK(v,G)標(biāo)記G中的元素v。

(4)ADDG(v,G)將元素v放入G中。

(5)NEXTG(G)返回G中下一個(gè)未標(biāo)記得元素，若G中沒有這樣的元素存在，則返回NUL。在S上規(guī)定如下操作：

(1)MAKENULL(S)將集合S置空。

(2)FIRSTS(S)返回S中的第一個(gè)元素；若S為空集，則返回NULL。

(3)NEXTS(S)返回S中的下一個(gè)元素；若S中沒有下一個(gè)元素，則返回NULL。

(4)ADDS(v,S)將v放入S中。3.逐步求精：第三步求精：voidgreedy(GRAPH

G,SETnewclr)/*類型GRAPH和SET有待說明*/{intfound;elementtypev,w;/*elementtype可以自定義*/MAKENULL(newclr);v=FIRSTG(G);while(v!=NULL){found=0;w=FIRSTS(newclr);while(w!=NULL){if(EDGE(v,w,G))found=1;w=NEXTS(newclr);}v=NEXTG(G);}}4.ADT的實(shí)現(xiàn)：按上述函數(shù)，最后一步工作就是給出類型elementtype的定義和實(shí)現(xiàn)抽象數(shù)據(jù)型GRAPH及SET。此后，上述函數(shù)就是可執(zhí)的程序了。1.5本書采用的類語言描述一、關(guān)于本書采用的類語言描述：

①結(jié)構(gòu)類型說明

②輸入輸出約定(cin>>v,cout<<v)

③new和delete

④引入引用類型二、關(guān)于引用類型：

所謂的引用就是給變量(對(duì)象)起個(gè)別名.換句話說,就是這個(gè)“別名”和原來的變量(對(duì)象)共用一個(gè)地址.

無論對(duì)原變量(對(duì)象)或?qū)ζ湟玫男薷?其實(shí)都是對(duì)同一地址內(nèi)容進(jìn)行修改,因而變量和對(duì)它的引用總具有相同的值.C++用引用運(yùn)算符&來定義一個(gè)引用類型.如,intnum=50;int&ref=num;//類型名&引用名=同類型變量的值

num=num+30;//num、ref均為80ref=ref+10;//num、ref均為901.引用與函數(shù)參數(shù)----引用調(diào)用舉例#include<iostream.h>voidSwap(int&a,int&b);//(int,int)(int*,int*)voidmain(){ intx(5),y(10);//C++的初始化形式<=>x=5 cout<<"x="<<x<<"y="<<y<<endl; Swap(x,y);//(x,y)(&x,&y) cout<<"x="<<x<<"y="<<y<<endl;}voidSwap(int&a,int&b);//(inta,intb)(int*a,int*b){ intt; t=a;a=b;b=t；

t=*a;*a=*b;*b=t;}2.返回引用的函數(shù)

是可以使該函數(shù)出現(xiàn)在運(yùn)算符的左邊(其他情況一個(gè)函數(shù)不能成為賦值表達(dá)式的左值).函數(shù)返回一個(gè)引用的主要目的返回引用的函數(shù)舉例#include<iostream.h>inta[]={2,4,6,8,10,12};int&index(inti);voidmain(){ index(3)=16;//a[3]=16 cout<<index(3)<<endl;//16 cout<<a[3]<<endl;//16}//函數(shù)的返回值為對(duì)數(shù)組元素的引用int&index(inti){ returna[i];}教學(xué)目的和內(nèi)容：了解分析和評(píng)價(jià)算法的一些基本準(zhǔn)則掌握算法時(shí)間復(fù)雜性分析方法第2章算法評(píng)價(jià)和復(fù)雜性分析2.1算法及其性能評(píng)價(jià)準(zhǔn)則2.2算法時(shí)間復(fù)雜性分析方法2.1算法及其性能評(píng)價(jià)準(zhǔn)則算法（Algorithm）：是對(duì)特定問題求解步驟的一種描述，它是指令（規(guī)則）的有限序列，其中每一條指令表示一個(gè)或多個(gè)操作。算法的特征：

①有窮性、②確定性、③能行性、④輸入、

⑤輸出算法描述：

①自然語言；②類語言*；③程序設(shè)計(jì)語言；一、算法、算法的特征和算法描述常用的算法設(shè)計(jì)方法：

①遞歸法（Recursion）、②分治法(Divide-andConquer)、

③貪心法(Greedy)、④動(dòng)態(tài)規(guī)劃(DynamicProgramming)、

⑤搜索與遍歷、⑥回溯（Backtracking）、⑦解空間局部搜索

⑧近似算法(Approximation)、⑨在線算法（On-Line）等1.正確性(Correctness)正確性的含義：是指對(duì)于一切合法的輸入數(shù)據(jù)經(jīng)有限時(shí)間或有限步后均可得到正確（滿足規(guī)格說明要求）的結(jié)果；算法包括兩方面的內(nèi)容：①解決問題的方法；②實(shí)現(xiàn)這一方法的一系列指令(語句、步驟)算法的正確性證明：①需要一組相關(guān)的引理和定理，確認(rèn)一個(gè)算法所使用的方法和公式的正確性；②在證明一系列的語句確實(shí)做了符合規(guī)定的動(dòng)作。算法的正確性的嚴(yán)格的形式化證明還未取得突破，還是一項(xiàng)令人生畏的工作。只有那些比較簡(jiǎn)單的算法，其正確性才能被形式化證明。

2.1算法及其性能評(píng)價(jià)準(zhǔn)則二、“好”的算法的標(biāo)準(zhǔn)2.時(shí)間復(fù)雜性(TimeComplexity)如何計(jì)算和比較算法的執(zhí)行時(shí)間：⑴實(shí)驗(yàn)測(cè)量法（實(shí)際執(zhí)行時(shí)間、執(zhí)行指令的條數(shù)）

優(yōu)點(diǎn)：精確

缺點(diǎn)：必須先運(yùn)行根據(jù)算法編制的的程序；所得的時(shí)間統(tǒng)計(jì)量依賴于計(jì)算機(jī)的硬件、軟件等環(huán)境因素，容易掩蓋算法本身的優(yōu)劣。2.1算法及其性能評(píng)價(jià)準(zhǔn)則二、“好”的算法的標(biāo)準(zhǔn)2.1算法及其性能評(píng)價(jià)準(zhǔn)則二、“好”的算法的標(biāo)準(zhǔn)⑵事前分析(估計(jì))法高級(jí)語言編寫的程序在計(jì)算機(jī)上運(yùn)行時(shí)間取決于下列因素：

①依據(jù)的算法本身選擇何種策略

②問題的規(guī)模（輸入的規(guī)模，輸入的大?。Ｈ缜笏?cái)?shù)問題

③程序設(shè)計(jì)語言：算法的實(shí)現(xiàn)語言級(jí)別越高，執(zhí)行效率越低

④編譯程序產(chǎn)生的機(jī)器代碼的質(zhì)量

⑤及其執(zhí)行指令的速度③④⑤表明用絕對(duì)的時(shí)間單位衡量一個(gè)算法的效率是不適合的算法的時(shí)間復(fù)雜性①認(rèn)為一個(gè)特定的算法執(zhí)行時(shí)間(“運(yùn)行工作量”的大小)，只依賴于問題的規(guī)模，即算法執(zhí)行時(shí)間是問題規(guī)模的函數(shù)2.1算法及其性能評(píng)價(jià)準(zhǔn)則二、“好”的算法的標(biāo)準(zhǔn)②由于算法的執(zhí)行時(shí)間由組成算法的控制結(jié)構(gòu)（順序、分支和循環(huán)）和基本操作的綜合效果，因此從算法中選擇對(duì)于研究問題來說是基本的操作（基本運(yùn)算）,把算法的基本操作的重復(fù)執(zhí)行的次數(shù)作為算法的時(shí)間度量③通常，我們并不關(guān)心T(n)的具體值，而是關(guān)心它的增長(zhǎng)率,即T(n)隨問題規(guī)模n（是一個(gè)整數(shù)）的增大的變化趨勢(shì)（界限）④算法的復(fù)雜性定義算法中基本操作重復(fù)執(zhí)行的次數(shù)是問題規(guī)模n的某個(gè)函數(shù)f（n），算法的時(shí)間度量記作T（n）=O（f（n））。它表示隨問題規(guī)模n的增大，算法執(zhí)行時(shí)間的增長(zhǎng)率不會(huì)超過f（n），稱為算法的漸進(jìn)時(shí)間復(fù)雜性，簡(jiǎn)稱時(shí)間復(fù)雜性。2.1算法及其性能評(píng)價(jià)準(zhǔn)則二、“好”的算法的標(biāo)準(zhǔn)3.空間復(fù)雜性(SpaceComplexity)算法的空間復(fù)雜性是指算法在執(zhí)行過程中的存儲(chǔ)量需求一個(gè)算法的存儲(chǔ)量需求除了存放算法本身所有的指令、常數(shù)、變量和輸入數(shù)據(jù)外，還包括對(duì)數(shù)據(jù)進(jìn)行操作的工作單元和存儲(chǔ)實(shí)現(xiàn)計(jì)算所需信息的輔助空間算法的存儲(chǔ)量需求與輸入的規(guī)模、表示方式、算法采用的數(shù)據(jù)結(jié)構(gòu)、算法的設(shè)計(jì)以及輸入數(shù)據(jù)的性質(zhì)有關(guān)算法的執(zhí)行的不同時(shí)刻，其空間需求可能是不同的算法的空間復(fù)雜性是指算法在執(zhí)行過程中的最大存儲(chǔ)量需求空間復(fù)雜性的漸進(jìn)表示----空間復(fù)雜度

T（n）=O（f（n））其中，n為問題的輸入規(guī)模2.1算法及其性能評(píng)價(jià)準(zhǔn)則二、“好”的算法的標(biāo)準(zhǔn)4.可讀性(Readability)可讀性好的算法有助于設(shè)計(jì)者和和他人閱讀、理解、修改和重用晦澀難懂的算法不容易隱藏錯(cuò)誤，而且還增加了閱讀…難度可讀性好的算法，常常也具有簡(jiǎn)單性5.健壯性(Robustness)當(dāng)輸入數(shù)據(jù)非法時(shí)，能作出適當(dāng)?shù)姆磻?yīng)（如對(duì)輸入數(shù)據(jù)進(jìn)行語法檢查，提出修改輸入建議并提供重新輸入的機(jī)會(huì)），避免異常出錯(cuò)6.一個(gè)好的算法還應(yīng)該具有靈活性（Flexibility）、可重用性(Reuseabale)和自適應(yīng)性(Adaptability)等2.2算法時(shí)間復(fù)雜性分析方法一、算法的時(shí)間復(fù)雜性

定義2.1設(shè)一個(gè)領(lǐng)域問題的輸入的規(guī)模為n，Dn是該領(lǐng)域問題的所有輸入集合，任意一個(gè)輸入I∈Dn是P（I）是I出現(xiàn)的概率，ΣI∈DnP（I）=1，T（I）是（解決該領(lǐng)域問題的）算法在輸入I下所執(zhí)行的基本運(yùn)算的次數(shù)。稱

E（n）=ΣI∈Dn{P（I）*T（I）}為該算法的期望復(fù)雜性（平均時(shí)間復(fù)雜性）稱

W（n）=maxI∈Dn

{T（I）}為該算法的最壞時(shí)間復(fù)雜性舉例2.2算法時(shí)間復(fù)雜性分析方法一、算法的時(shí)間復(fù)雜性

例2.1A是一個(gè)由n個(gè)不同元素的實(shí)數(shù)數(shù)組，給出求其最大和最小元素的算法和時(shí)間復(fù)雜性voidSM(doubleA[],intn,doublemax,doublemin){doublemax,min;max=min=A[0];for(k=1;k<=n-1;k++){if(A[k]>max)max=A[k];if(A[k]<min)min=A[k];}}容易看出，算法SM對(duì)大小位n的數(shù)組需要2（n-1）比較，若算法SM的基本運(yùn)算是元素比較，則復(fù)雜性為2（n-1）2.2算法時(shí)間復(fù)雜性分析方法一、算法的時(shí)間復(fù)雜性

例2.2A是一個(gè)由n個(gè)不同元素的實(shí)數(shù)數(shù)組，給出確定給定實(shí)數(shù)K是否在A中的算法及其時(shí)間復(fù)雜性intSK(doubleA[],intn,doubleK){intj=1;while(j<=n){if(A[j]==K)break;elsej++;}returnj;//若j≤n，則K在A中，否則(j=n+1)K不在A中}2.2算法時(shí)間復(fù)雜性分析方法一、算法的時(shí)間復(fù)雜性算法SK的基本運(yùn)算是元素與K的比較假定q表示K在A中的概率，有假設(shè)K等于A的每個(gè)元素有相同的概率。令Dn={I1,I2,…In,In+1}，其中Ij(1≤j≤n)表示K==A[j]的任意輸入，In表示K不是A中元素的任意一個(gè)輸入，由上述說明有：當(dāng)0≤j≤n時(shí)，P（Ij）=q/n，T（Ij）=j，P（In+1）=1-q，T（In+1）=n算法SK的期望復(fù)雜性和最壞復(fù)雜性為

E（n）=Σj∈Dn{P（Ij）*T（Ij）}=Σj=1,…n+1[(q/n)*j]+(1-q)*n=1/2(n+1)q+(1-q)n=1/2(n+1)(K在A中，q=1)W（n）=max{T（Ij）|1≤j≤n

}=n2.2算法時(shí)間復(fù)雜性分析方法二、函數(shù)階的比較

定義2.2設(shè)f（n）、T（n）是整數(shù)集到實(shí)數(shù)集上的函數(shù)，稱函數(shù)f（n）是T（n）增長(zhǎng)率的上界，當(dāng)且僅當(dāng)存在一個(gè)正常數(shù)C和整數(shù)n0

，使得對(duì)任意的n≥n0

時(shí)，有

T(n)≤Cf(n)記作：

T（n）=O（f（n））此時(shí)也稱T（n）的階至多為f（n））*一個(gè)算法的時(shí)間復(fù)雜性為O（f（n）），表明它的基本操作次數(shù)至多是f（n）的某個(gè)常數(shù)倍例2.1設(shè)函數(shù)T（n）=3n5+4n2+1，證明：T（n）=О（n5）證明：f（n）=n5.取n0=0,C=8,則當(dāng)n≥n0時(shí)有

T（n）=3n5+4n2+1≤8n5=C

f（n）證畢2.2算法時(shí)間復(fù)雜性分析方法二、函數(shù)階的比較

定義2.3設(shè)f（n）、T（n）是整數(shù)集到實(shí)數(shù)集上的函數(shù)，稱函數(shù)f（n）是T（n）增長(zhǎng)率的下界，當(dāng)且僅當(dāng)存在一個(gè)正常數(shù)C和整數(shù)n0

，使得對(duì)任意的n≥n0

時(shí)，有

T(n)≥Cf(n)記作：

T（n）=Ω（f（n））此時(shí)也稱T（n）的階至少為f（n））*一個(gè)算法的時(shí)間復(fù)雜性為Ω

（f（n）），表明它的基本操作次數(shù)至少是f（n）的某個(gè)常數(shù)倍例2.3

設(shè)函數(shù)T（n）=3n5+4n2+1，證明：T（n）=Ω

（n5）證明：f（n）=n5.取n0=0,C=1,則當(dāng)n≥n0時(shí)有

T（n）=3n5+4n2+1≥1n5=Cf（n）證畢2.2算法時(shí)間復(fù)雜性分析方法

定理2.1若

A（n）=amnm+…+a1n+a0(am#0)

是關(guān)于n的m次多項(xiàng)式，則

A（n）=О（nm）

*此定理說明，時(shí)間復(fù)雜性僅取決于多項(xiàng)式的最高次冪，而與最高次冪的系數(shù)和其他低次項(xiàng)無關(guān)О（1）表示時(shí)間復(fù)雜性為常數(shù)常見的時(shí)間復(fù)雜性及其比較

О（1）<О（㏒㏒n）<О（㏒n）<О（n）<О（n㏒n）<О（n2）<О（n3）<О（2n）程序運(yùn)行時(shí)間比較T（n）=O（f（n））T(n)n01000200030005101520252nn3100n5n2logn2100△n△T(n)2.2算法時(shí)間復(fù)雜性分析方法2.2算法時(shí)間復(fù)雜性分析方法三、時(shí)間復(fù)雜性的運(yùn)算法則

設(shè)T1(n)=O(f(n))，T2(n)=O(g(n))，則加法規(guī)則：T1(n)+T2(n)=O(max{f(n),g(n)})乘法規(guī)則：T1(n)+T2(n)=O(f(n)·g(n))例2.4：

①s=0;

→f(n)=1;T2(n)=O(f(n))=O(1)

常量階

②for(i=1;i<=n;++i){++x;s+=x;}

→f(n)=3n+1;T1(n)=O(f(n))=O(n)

線性階

③for(i=1;i<=n;++i)for(j=1;j<=n;++j){++x;s+=x;}

→f(n)=3n2+2n+1;T3(n)=O(f(n))=O(n2)

平方階

④for(i=1;i<=n;++i)for(j=1;j<=n;++j){c[i][j]=0;for(k=1;k<=n;++k)c[i][j]+=a[i][k]*b[k][j];}→f(n)=2n3+3n2+2n+1;T4(n)=O(f(n))=O(n3)

立方階2.2算法時(shí)間復(fù)雜性分析方法例2.5：

⑤longfact

(intn)

{if(n==0)||(n==1)return(1);elsereturn(n*fact(n–1));}T(n)=C當(dāng)n=0,n=1G+T(n–1)當(dāng)n>1T(n)=G+f(n–1)T(n–1)=G

+f(n–2)T(n–2)=G

+f(n–3)……T(2)=G

+f(1)+T(1)=CT(n)=G（n-1）+C

取f(n)=n∴T(n)=O(f(n))=O(n)2.2算法時(shí)間復(fù)雜性分析方法2.2算法時(shí)間復(fù)雜性分析方法㏑㏒≤≥≠ОΩθ作業(yè)：1.p28例2.1.52.A是一個(gè)由n個(gè)不同元素的實(shí)數(shù)數(shù)組，給出求其最大和最小元素的遞歸算法和時(shí)間復(fù)雜性3.1抽象數(shù)據(jù)型線性表3.2線性表的實(shí)現(xiàn)3.3棧（Stack）3.4隊(duì)列（Queue）3.5串（String）3.6數(shù)組（Array）3.7廣義表（GeneralizedList）第三章線性表知識(shí)點(diǎn)：線性表的邏輯結(jié)構(gòu)和各種存儲(chǔ)表示方法定義在邏輯結(jié)構(gòu)上的各種基本運(yùn)算（操作）在各種存儲(chǔ)結(jié)構(gòu)上如何實(shí)現(xiàn)這些基本運(yùn)算各種基本運(yùn)算的時(shí)間復(fù)雜性重點(diǎn)：熟練掌握順序表和單鏈表上實(shí)現(xiàn)的各種算法及相關(guān)的時(shí)間復(fù)雜性分析難點(diǎn)：使用本章所學(xué)的基本知識(shí)設(shè)計(jì)有效算法解決與線性表相關(guān)的應(yīng)用問題3.1抽象數(shù)據(jù)型線性表[定義]

線性表是由n(n≥0)個(gè)相同類型的元素組成的有序序列。記為：

(a1,a2,a3,……ai-1,ai,ai+1,……an)①n為線性表中元素個(gè)數(shù)，稱為線性表的長(zhǎng)度；當(dāng)n=0時(shí)，為空表，記為（）。②ai為線性表中的元素，類型定義為elementtype，元素同構(gòu)③a1為表中第1個(gè)元素，無前驅(qū)元素；an為表中最后一個(gè)元素，無后繼元素；對(duì)于…ai-1,ai,ai+1…(1<i<n)，稱ai-1為ai的直接前驅(qū)，ai+1為ai的

直接后繼。(位置概念?。芫€性表是有限的，也是有序的，不能有缺項(xiàng)。邏輯特征：3.1抽象數(shù)據(jù)型線性表線性表LIST=(D,R)D={ai|ai

∈Elementset,i=1,2,…,n,n≥0}R={H}H={<ai-1,ai>|ai-1,ai

∈D,i=2,…,n}操作：設(shè)L的型為L(zhǎng)IST線性表實(shí)例，x的型為elementtype的元素實(shí)例，p為位置變量。所有操作描述為：

①INSERT(x,p,L)②LOCATE(x,L)③RETRIEVE(p,L)④DELETE(p,L)⑤PREVIOUS(p,L),NEXT(p,L)⑥MAKENULL(L)⑦FIRST(L)數(shù)學(xué)模型3.1抽象數(shù)據(jù)型線性表舉例：設(shè)計(jì)函數(shù)DELEVAL（LIST&L,elementtyped)，其功能為刪除L中所有值為d的元素。

voidDELEVAL(LIST&L,elementtyped){

positionp;p=FIRST(L);while(p!=END(L))

{if(same(RETRIEVE(p,L),d))DELETE(p,L);elsep=NEXT(p,L);

}

}3.2線性表的實(shí)現(xiàn)問題：確定數(shù)據(jù)結(jié)構(gòu)（存儲(chǔ)結(jié)構(gòu)）實(shí)現(xiàn)型LIST，并在此基礎(chǔ)上實(shí)現(xiàn)各個(gè)基本操作。存儲(chǔ)結(jié)構(gòu)的三種方式：

①連續(xù)的存儲(chǔ)空間（數(shù)組）→靜態(tài)存儲(chǔ)

②非連續(xù)存儲(chǔ)空間——指針（鏈表）→動(dòng)態(tài)存儲(chǔ)

③游標(biāo)（連續(xù)存儲(chǔ)空間+動(dòng)態(tài)管理思想）→靜態(tài)鏈表3.2.1指針和游標(biāo)指針：地址量，其值為另一存儲(chǔ)空間的地址；游標(biāo)：整型指示量，其值為數(shù)組的下標(biāo)，用以表示指定元素的“地址”或“位置”（所在的數(shù)組下標(biāo)）3.2.2線性表的數(shù)組實(shí)現(xiàn)

第1個(gè)元素第2個(gè)元素

……

最后1個(gè)元素……012maxlength-1last表空單元圖3-1線性表的數(shù)組實(shí)現(xiàn)存儲(chǔ)池容量

……第i個(gè)元素1≤i≤last順序表：把線性表的元素邏輯順序依次存放在數(shù)組的連續(xù)單元內(nèi)，再用一個(gè)整型量表示最后一個(gè)元素所在單元的下標(biāo)。特點(diǎn)：

元素之間的邏輯關(guān)系（相繼/相鄰關(guān)系）用物理上的相鄰關(guān)系來表示（用物理上的連續(xù)性刻畫邏輯上的相繼性）；是一種隨機(jī)存儲(chǔ)結(jié)構(gòu)，也就是可以隨機(jī)存取表中的任意元素，其存儲(chǔ)位置可由一個(gè)簡(jiǎn)單直觀的公式來表示。3.2.2線性表的數(shù)組實(shí)現(xiàn)

第1個(gè)元素第2個(gè)元素

……

最后1個(gè)元素……012maxlength-1last表空單元圖3-1線性表的數(shù)組實(shí)現(xiàn)存儲(chǔ)池容量

……第i個(gè)元素1≤i≤last類型定義：#definemaxlength100structLIST{elementtypeelements[maxlength];intlast;};位置類型：typedefintposition;線性表L：LISTL;表示：L.elements[p]//L的第p個(gè)元素L.lastL的長(zhǎng)度，最后元素的位置3.2.2線性表的數(shù)組實(shí)現(xiàn)操作：①插入voidINSERT(elementtypex,positionp,LIST&L){positionq;if(L.last>=maxlength–1)error(“表滿”)；

elseif((p>L.last+1)||(p<1))error(“指定位置不存在”)；

else{

for(q=L.last;q>=p;q--)

L.elements[q+1]=L.elements[q];L.last=L.last+1;L.elements[p]=x;

}

}

//時(shí)間復(fù)雜性：O(n)

第1個(gè)元素第2個(gè)元素

……

最后1個(gè)元素……012maxlength-1last表空單元圖線性表的數(shù)組實(shí)現(xiàn)存儲(chǔ)池容量

……第i個(gè)元素1≤i≤lastpositionLOCATE(elementtypex,LISTL){positionq;for(q=1;q<=L.last;q++)if(L.elements[q]==x)return(q);return(L.last+1);}//時(shí)間復(fù)雜性：O(n)3.2.2線性表的數(shù)組實(shí)現(xiàn)③elementtypeRETRIEVE(positionp,LISTL){if(p>L.last)error(“指定元素不存在”);elsereturn(L.elements[p]);}//時(shí)間復(fù)雜性：O(1)

第1個(gè)元素第2個(gè)元素

……

最后1個(gè)元素……012maxlength-1last表空單元圖線性表的數(shù)組實(shí)現(xiàn)存儲(chǔ)池容量

……第i個(gè)元素1≤i≤last④voidDELETE(positionp,LIST&L){positionq;if((p>L.last)||(p<1))error(“指定位置不存在”)；

else{L.last=L.last–1;for(q=p;q<=L.last;q++)L.elements[q]=L.elements[q+1];}}//時(shí)間復(fù)雜性：O(n)3.2.2線性表的數(shù)組實(shí)現(xiàn)⑤positionPREVIOUS(positionp,LISTL){if((p<=1)||(p>L.last))error(“前驅(qū)元素不存在”);elsereturn(p–1);}//時(shí)間復(fù)雜性：O(1)

第1個(gè)元素第2個(gè)元素

……

最后1個(gè)元素……012maxlength-1last表空單元圖線性表的數(shù)組實(shí)現(xiàn)存儲(chǔ)池容量

……第i個(gè)元素1≤i≤last⑧positionEND(LISTL){return(L.last+1);}//O(1)⑦positionFIRST(LISTL){return(1);}//復(fù)雜性：O(1)positionNEXT(positionp,LISTL){if((p<1)||(p>=L.last))error(“前驅(qū)元素不存在”);elsereturn(p+1);}//時(shí)間復(fù)雜性：O(1)⑥positionMAKENULL(LIST&L){L.last=0;return(L.last+1);}//時(shí)間復(fù)雜性：O(1)3.2.2線性表的數(shù)組實(shí)現(xiàn)

第1個(gè)元素第2個(gè)元素

……

最后1個(gè)元素……012maxlength-1last表空單元圖3-1線性表的數(shù)組實(shí)現(xiàn)存儲(chǔ)池容量

……第i個(gè)元素1≤i≤last3.2.3線性表的指針實(shí)現(xiàn)結(jié)點(diǎn)型elementnext結(jié)點(diǎn)信息下一結(jié)點(diǎn)地址celltypeLISTheader;positionp,q;a1a2a3an∧…h(huán)eaderqp單鏈表：一個(gè)線性表由若干個(gè)結(jié)點(diǎn)組成，每個(gè)結(jié)點(diǎn)均含有兩個(gè)域：存放元素的信息域和存放其后繼結(jié)點(diǎn)的指針域，這樣就形成一個(gè)單向鏈接式存儲(chǔ)結(jié)構(gòu)，簡(jiǎn)稱單向鏈表或單向線性鏈表。結(jié)構(gòu)特點(diǎn)：邏輯次序和物理次序不一定相；元素之間的邏輯關(guān)系用指針表；需要額外空間存儲(chǔ)元素之間的關(guān)系非隨機(jī)存儲(chǔ)結(jié)構(gòu)3.2.3線性表的指針實(shí)現(xiàn)類型定義：structcelltype{elementtypeelement;celltype*next;};/*結(jié)點(diǎn)型*/LISTheader;positionp,q;a1a2a3an∧…h(huán)eaderqpa2:(*p).element;q:(*p).next;a2:p→element;q:p→next;記法:結(jié)點(diǎn)型elementnext結(jié)點(diǎn)信息下一結(jié)點(diǎn)地址celltype/*線性表的型*/typedefcelltype*LIST;/*位置型*/typedefcelltype*position;操作討論3.2.3線性表的指針實(shí)現(xiàn)插入元素:pa1xheaderqai-1aixpqan∧x∧qp(a)表頭插入元素(b)中間插入元素(c)表尾插入元素q=newcelltype;q→element=x;q→next=p→next;p→next=q;或:temp=p→next;p→next=newcelltype;p→next→element=x;p→next→next=temp;討論表頭結(jié)點(diǎn)的作用:表頭結(jié)點(diǎn)的引入使得在任意位置的插入和刪除操作的代碼統(tǒng)一，而不必對(duì)不同情況分別進(jìn)行處理操作討論3.2.3線性表的指針實(shí)現(xiàn)刪除元素:q=p→next;p→next=q→next;deleteq;或：q=p→next;p→next=p→next→next;deleteq;討論結(jié)點(diǎn)ai的位置pa1header(a)刪除第一個(gè)元素a2qpai-1aipq(b)刪除中間元素ai+1an∧an-1qp(c)刪除表尾元素∧3.2.3線性表的指針實(shí)現(xiàn)①positionEND(LIST){positionq;q=L;while(q→next!=NULL)q=q→next;return(q);}//時(shí)間復(fù)雜性：O(n)②voidINSERT(elementtypex,positionp,LIST&L){positionq;q=newcelltype;q→element=x;q→next=p→next;p→next=q;}//時(shí)間復(fù)雜性：O(1)Lqa1a2a3an∧…操作操作：③positionLOCATE(elementtypex,LISTL){positionp;p=L;while(p→next!=NULL)if(p→next→element==x)returnp;