數(shù)據(jù)結(jié)構(gòu)(嚴(yán)蔚敏)精第1章課件

第一章緒論2007年9月5日星期三.頁(yè)【課前思考】你過(guò)去是否聽(tīng)說(shuō)過(guò)"數(shù)據(jù)結(jié)構(gòu)"？你知道數(shù)據(jù)結(jié)構(gòu)是一門(mén)討論什么內(nèi)容的學(xué)科嗎？同學(xué)們見(jiàn)過(guò)《算法+數(shù)據(jù)結(jié)構(gòu)=程序設(shè)計(jì)》這本書(shū)吧，它正好說(shuō)明數(shù)據(jù)結(jié)構(gòu)的實(shí)質(zhì)是討論程序設(shè)計(jì)的方法。通過(guò)這門(mén)課的學(xué)習(xí)，同學(xué)們將掌握非數(shù)值計(jì)算程序設(shè)計(jì)中用的基本方法和技巧。2007年9月5日星期三.【學(xué)習(xí)目標(biāo)】熟悉各名詞、術(shù)語(yǔ)的含義，掌握基本概念。理解算法五個(gè)要素的確切含義。掌握計(jì)算語(yǔ)句頻度和估算算法時(shí)間復(fù)雜度的方法?！局攸c(diǎn)和難點(diǎn)】本章討論的都是一些基本概念，因此沒(méi)有難點(diǎn)，重點(diǎn)在于了解有關(guān)數(shù)據(jù)結(jié)構(gòu)的各個(gè)名詞和術(shù)語(yǔ)的含義，以及語(yǔ)句頻度和時(shí)間復(fù)雜度、空間復(fù)雜度的估算

。【知識(shí)點(diǎn)】數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)類型、抽象數(shù)據(jù)類型、算法及其設(shè)計(jì)原則、時(shí)間復(fù)雜度、空間復(fù)雜度。2007年9月5日星期三.【學(xué)習(xí)指南】1.熟悉各名詞、術(shù)語(yǔ)的含義，掌握基本概念，特別是數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)之間的關(guān)系。分清哪些是邏輯結(jié)構(gòu)的性質(zhì)，哪些是存儲(chǔ)結(jié)構(gòu)的性質(zhì)。

2.了解抽象數(shù)據(jù)類型的定義、表示和實(shí)現(xiàn)方法。

3.熟悉類C語(yǔ)言的書(shū)寫(xiě)規(guī)范，特別要注意值調(diào)用和引用調(diào)用的區(qū)別，輸入、輸出的方式以及錯(cuò)誤處理方式。

4.理解算法五個(gè)要素的確切含義和對(duì)算法正確性的理解。

5.掌握計(jì)算語(yǔ)句頻度和估算算法時(shí)間復(fù)雜度的方法。2007年9月5日星期三.1.1數(shù)據(jù)結(jié)構(gòu)討論的范疇1.2基本概念1.3算法和算法的量度2007年9月5日星期三.1.1

數(shù)據(jù)結(jié)構(gòu)討論的范疇NiklausWirth：

Algorithm

+DataStructures=Programs程序設(shè)計(jì):算法:數(shù)據(jù)結(jié)構(gòu):為計(jì)算機(jī)處理問(wèn)題編制一組指令集

處理問(wèn)題的策略問(wèn)題的數(shù)學(xué)模型2007年9月5日星期三.結(jié)構(gòu)靜力分析計(jì)算例如:數(shù)值計(jì)算的程序設(shè)計(jì)問(wèn)題─━線性代數(shù)方程組─━環(huán)流模式方程(球面坐標(biāo)系)全球天氣預(yù)報(bào)2007年9月5日星期三.非數(shù)值計(jì)算的程序設(shè)計(jì)問(wèn)題例一:求一組(n個(gè))整數(shù)中的最大值算法:?模型：？基本操作是“比較兩個(gè)數(shù)的大小”取決于整數(shù)值的范圍2007年9月5日星期三.例二：計(jì)算機(jī)對(duì)弈算法：?模型：?對(duì)弈的規(guī)則和策略棋盤(pán)及棋盤(pán)的格局2007年9月5日星期三.例三：足協(xié)的數(shù)據(jù)庫(kù)管理算法：?模型：?需要管理的項(xiàng)目？如何管理？用戶界面？各種表格2007年9月5日星期三.概括地說(shuō)：

數(shù)據(jù)結(jié)構(gòu)是一門(mén)討論“描述現(xiàn)實(shí)世界實(shí)體的數(shù)學(xué)模型(非數(shù)值計(jì)算)及其上的操作在計(jì)算機(jī)中如何表示和實(shí)現(xiàn)”的學(xué)科。2007年9月5日星期三.1.2基本概念一、數(shù)據(jù)與數(shù)據(jù)結(jié)構(gòu)二、數(shù)據(jù)類型三、抽象數(shù)據(jù)類型2007年9月5日星期三.一、數(shù)據(jù)與數(shù)據(jù)結(jié)構(gòu)所有能被輸入到計(jì)算機(jī)中，且能被計(jì)算機(jī)處理的符號(hào)的集合。數(shù)據(jù):是計(jì)算機(jī)操作的對(duì)象的總稱。是計(jì)算機(jī)處理的信息的某種特定的符號(hào)表示形式。2007年9月5日星期三.是數(shù)據(jù)（集合）中的一個(gè)“個(gè)體”數(shù)據(jù)元素:是數(shù)據(jù)結(jié)構(gòu)中討論的基本單位數(shù)據(jù)對(duì)象是性質(zhì)相同的數(shù)據(jù)元素的集合是數(shù)據(jù)的子集2007年9月5日星期三.

數(shù)據(jù)項(xiàng)：是數(shù)據(jù)結(jié)構(gòu)中討論的最小單位數(shù)據(jù)元素可以是數(shù)據(jù)項(xiàng)的集合例如：描述一個(gè)運(yùn)動(dòng)員的數(shù)據(jù)元素可以是稱之為組合項(xiàng)2007年9月5日星期三.數(shù)據(jù)結(jié)構(gòu)：帶結(jié)構(gòu)的數(shù)據(jù)元素的集合假設(shè)用三個(gè)4位的十進(jìn)制數(shù)表示一個(gè)含

12位數(shù)的十進(jìn)制數(shù)。3214,6587,9345

─

a1(3214),a2(6587),a3(9345)則在數(shù)據(jù)元素a1、a2和a3之間存在著“次序”關(guān)系

a1,a2

、

a2,a3

3214，6587，9345a1a2a36587，3214，9345a2a1a3≠例如:2007年9月5日星期三.又例，在2行3列的二維數(shù)組{a1,a2,a3,a4,a5,a6}中六個(gè)元素之間存在兩個(gè)關(guān)系:行的次序關(guān)系:列的次序關(guān)系:row={<a1,a2>,<a2,a3>,<a4,a5>,<a5,a6>}col={<a1,a4>,<a2,a5>,<a3,a6>}

a1a3a5

a2a4a6a1a2a3a4a5a6 數(shù)據(jù)結(jié)構(gòu)：帶結(jié)構(gòu)的數(shù)據(jù)元素的集合2007年9月5日星期三.再例，在一維數(shù)組{a1,a2,a3,a4,a5,a6}的數(shù)據(jù)元素之間存在如下的次序關(guān)系:{<ai,ai+1>|i=1,2,3,4,5}

或者說(shuō)，數(shù)據(jù)結(jié)構(gòu)是相互之間存在著某種關(guān)系的數(shù)據(jù)元素的集合。數(shù)據(jù)結(jié)構(gòu)：帶結(jié)構(gòu)的數(shù)據(jù)元素的集合可見(jiàn)，不同的“關(guān)系”構(gòu)成不同的“結(jié)構(gòu)”2007年9月5日星期三.數(shù)據(jù)結(jié)構(gòu)包括以下幾個(gè)方面：數(shù)據(jù)元素之間的邏輯關(guān)系，即邏輯結(jié)構(gòu)數(shù)據(jù)元素及其關(guān)系在計(jì)算機(jī)存儲(chǔ)器中的存儲(chǔ)方式，即數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)施加在該數(shù)據(jù)上的操作，即數(shù)據(jù)的運(yùn)算2007年9月5日星期三.數(shù)據(jù)的邏輯結(jié)構(gòu)可歸結(jié)為以下四類:線性結(jié)構(gòu)樹(shù)形結(jié)構(gòu)圖狀結(jié)構(gòu)集合結(jié)構(gòu)2007年9月5日星期三.數(shù)據(jù)結(jié)構(gòu)的形式定義為:數(shù)據(jù)結(jié)構(gòu)是一個(gè)二元組Data_Structures=(D,S)其中:D是數(shù)據(jù)元素的有限集，

S是D上關(guān)系的有限集。2007年9月5日星期三.數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)(物理結(jié)構(gòu))

——邏輯結(jié)構(gòu)在存儲(chǔ)器中的映象“數(shù)據(jù)元素”的映象？“關(guān)系”的映象？2007年9月5日星期三.數(shù)據(jù)元素的映象方法：用二進(jìn)制位(bit)的位串表示數(shù)據(jù)元素(321)10=(501)8=(101000001)22007年9月5日星期三.關(guān)系的映象方法：（表示

x,y

的方法）順序映象(順序存儲(chǔ)方法)以相對(duì)的存儲(chǔ)位置表示后繼關(guān)系例如:令y的存儲(chǔ)位置和x的存儲(chǔ)位置之間差一個(gè)常量C而C是一個(gè)隱含值，整個(gè)存儲(chǔ)結(jié)構(gòu)中只含數(shù)據(jù)元素本身的信息xy2007年9月5日星期三.鏈?zhǔn)接诚?鏈?zhǔn)酱鎯?chǔ)方法)需要用一個(gè)和x在一起的附加信息指示y的存儲(chǔ)位置yx

不要求在邏輯上相鄰的結(jié)點(diǎn)在物理位置上也相鄰，結(jié)點(diǎn)間的邏輯關(guān)系由附加的指針字段表示。2007年9月5日星期三.索引存儲(chǔ)方法

存儲(chǔ)結(jié)點(diǎn)信息的同時(shí)，建立附加的索引表。索引表中的每一項(xiàng)稱為索引項(xiàng)，索引項(xiàng)的一般形式是關(guān)鍵字與地址。散列(或哈希)存儲(chǔ)方法

根據(jù)結(jié)點(diǎn)的關(guān)鍵字通過(guò)散列函數(shù)直接計(jì)算出一個(gè)值，并將這個(gè)值作為該結(jié)點(diǎn)的存儲(chǔ)地址。2007年9月5日星期三.在不同的編程環(huán)境中，存儲(chǔ)結(jié)構(gòu)可有不同的描述方法。當(dāng)用高級(jí)程序設(shè)計(jì)語(yǔ)言進(jìn)行編程時(shí)，通?？捎酶呒?jí)編程語(yǔ)言中提供的數(shù)據(jù)類型描述之。2007年9月5日星期三.例如:以三個(gè)帶有次序關(guān)系的整數(shù)表示一個(gè)長(zhǎng)整數(shù)時(shí)，可利用C語(yǔ)言中提供的整數(shù)數(shù)組類型。

typedefintLong_int[3]定義長(zhǎng)整數(shù)為:2007年9月5日星期三.二、數(shù)據(jù)類型

在用高級(jí)程序語(yǔ)言編寫(xiě)的程序中，必須對(duì)程序中出現(xiàn)的每個(gè)變量、常量或表達(dá)式，明確說(shuō)明它們所屬的數(shù)據(jù)類型。2007年9月5日星期三.例如，C語(yǔ)言中提供的基本數(shù)據(jù)類型有:整型int浮點(diǎn)型float字符型char邏輯型bool（C++語(yǔ)言）雙精度型double實(shí)型（C++語(yǔ)言）2007年9月5日星期三.數(shù)據(jù)類型

是一個(gè)值的集合和定義在此集合上的一組操作的總稱。

不同類型的變量，其所能取的值的范圍不同，所能進(jìn)行的操作不同。2007年9月5日星期三.三、抽象數(shù)據(jù)類型

(AbstractDataType簡(jiǎn)稱ADT)是指一個(gè)數(shù)學(xué)模型以及定義在此數(shù)學(xué)模型上的一組操作。2007年9月5日星期三.例如，抽象數(shù)據(jù)類型復(fù)數(shù)的定義：

數(shù)據(jù)對(duì)象：

D＝{e1,e2｜e1,e2∈RealSet}

數(shù)據(jù)關(guān)系：

R1＝{<e1,e2>|e1是復(fù)數(shù)的實(shí)數(shù)部分

|e2是復(fù)數(shù)的虛數(shù)部分}ADTComplex{2007年9月5日星期三.基本操作：

AssignComplex(&Z,v1,v2)操作結(jié)果：構(gòu)造復(fù)數(shù)Z,其實(shí)部和虛部分別被賦以參數(shù)v1和v2的值。

DestroyComplex(&Z)操作結(jié)果：復(fù)數(shù)Z被銷毀。

GetReal(Z,&realPart)初始條件：復(fù)數(shù)已存在。操作結(jié)果：用realPart返回復(fù)數(shù)Z的實(shí)部值。2007年9月5日星期三.

GetImag(Z,&ImagPart)初始條件：復(fù)數(shù)已存在。操作結(jié)果：用ImagPart返回復(fù)數(shù)Z的虛部值。

Add(z1,z2,&sum)初始條件：z1,z2是復(fù)數(shù)。操作結(jié)果：用sum返回兩個(gè)復(fù)數(shù)z1,z2的和值。}ADTComplex2007年9月5日星期三.假設(shè):z1和z2是上述定義的復(fù)數(shù)則Add(z1,z2,z3)操作的結(jié)果z3=z1+z2即為用戶企求的結(jié)果2007年9月5日星期三.ADT有兩個(gè)重要特征:數(shù)據(jù)抽象

用ADT描述程序處理的實(shí)體時(shí)，強(qiáng)調(diào)的是其本質(zhì)的特征、其所能完成的功能以及它和外部用戶的接口（即外界使用它的方法）。數(shù)據(jù)封裝

將實(shí)體的外部特性和其內(nèi)部實(shí)現(xiàn)細(xì)節(jié)分離，并且對(duì)外部用戶隱藏其內(nèi)部實(shí)現(xiàn)細(xì)節(jié)。2007年9月5日星期三.抽象數(shù)據(jù)類型的描述方法抽象數(shù)據(jù)類型可用（D，S，P）三元組表示。其中：D是數(shù)據(jù)對(duì)象；

S是D上的關(guān)系集；P是對(duì)D的基本操作集。2007年9月5日星期三.ADT

抽象數(shù)據(jù)類型名{數(shù)據(jù)對(duì)象：〈數(shù)據(jù)對(duì)象的定義〉

數(shù)據(jù)關(guān)系：〈數(shù)據(jù)關(guān)系的定義〉

基本操作：〈基本操作的定義〉}ADT抽象數(shù)據(jù)類型名其中基本操作的定義格式為:基本操作名（參數(shù)表）

初始條件：〈初始條件描述〉

操作結(jié)果：〈操作結(jié)果描述〉

2007年9月5日星期三.賦值參數(shù)只為操作提供輸入值。引用參數(shù)以&打頭，除可提供輸入值外，還將返回操作結(jié)果。初始條件描述了操作執(zhí)行之前數(shù)據(jù)結(jié)構(gòu)和參數(shù)應(yīng)滿足的條件，若不滿足，則操作失敗，并返回相應(yīng)出錯(cuò)信息。操作結(jié)果說(shuō)明了操作正常完成之后，數(shù)據(jù)結(jié)構(gòu)的變化狀況和應(yīng)返回的結(jié)果。若初始條件為空，則省略之。2007年9月5日星期三.抽象數(shù)據(jù)類型的表示和實(shí)現(xiàn)抽象數(shù)據(jù)類型需要通過(guò)固有數(shù)據(jù)類型(高級(jí)編程語(yǔ)言中已實(shí)現(xiàn)的數(shù)據(jù)類型)來(lái)實(shí)現(xiàn)。例如，對(duì)以上定義的復(fù)數(shù)。2007年9月5日星期三.typedefstruct{

floatrealpart；

floatimagpart；}complex；//-----存儲(chǔ)結(jié)構(gòu)的定義//-----基本操作的函數(shù)原型說(shuō)明void

Assign(complex&Z,

floatrealval,floatimagval)；//構(gòu)造復(fù)數(shù)Z,其實(shí)部和虛部分別被賦以參數(shù)//realval和imagval的值2007年9月5日星期三.float

GetReal(cpmplexZ)；//返回復(fù)數(shù)Z的實(shí)部值float

Getimag(cpmplexZ)；//返回復(fù)數(shù)Z的虛部值voidadd(complexz1,complexz2,complex&sum)；

//以sum返回兩個(gè)復(fù)數(shù)z1,z2的和2007年9月5日星期三.//-----基本操作的實(shí)現(xiàn)voidadd(complexz1,complexz2,complex&sum){

//以sum返回兩個(gè)復(fù)數(shù)z1,z2的和

sum.realpart=z1.realpart+z2.realpart;sum.imagpart=z1.imagpart+z2.imagpart;}

{其它省略}2007年9月5日星期三.1.4算法和算法分析一、算法二、算法設(shè)計(jì)的原則三、算法效率的衡量方法和準(zhǔn)則四、算法的存儲(chǔ)空間需求2007年9月5日星期三.

算法是為了解決某類問(wèn)題而規(guī)定的一個(gè)有限長(zhǎng)的操作序列。一個(gè)算法必須滿足以下五個(gè)重要特性：1．有窮性

2．確定性3．可行性4．有輸入5．有輸出一、算法2007年9月5日星期三.1．有窮性對(duì)于任意一組合法輸入值，在執(zhí)行有窮步驟之后一定能結(jié)束，即：算法中的每個(gè)步驟都能在有限時(shí)間內(nèi)完成。

2．確定性

對(duì)于每種情況下所應(yīng)執(zhí)行的操作，在算法中都有確切的規(guī)定，使算法的執(zhí)行者或閱讀者都能明確其含義及如何執(zhí)行。并且在任何條件下，算法都只有一條執(zhí)行路徑。2007年9月5日星期三.3．可行性算法中的所有操作都必須足夠基本，都可以通過(guò)已經(jīng)實(shí)現(xiàn)的基本操作運(yùn)算有限次實(shí)現(xiàn)之。4．有輸入作為算法加工對(duì)象的量值，通常體現(xiàn)為算法中的一組變量。有些輸入量需要在算法執(zhí)行過(guò)程中輸入，而有的算法表面上可以沒(méi)有輸入，實(shí)際上已被嵌入算法之中。2007年9月5日星期三.

5．有輸出它是一組與“輸入”有確定關(guān)系的量值，是算法進(jìn)行信息加工后得到的結(jié)果，這種確定關(guān)系即為算法的功能。2007年9月5日星期三.二、算法設(shè)計(jì)的原則設(shè)計(jì)算法時(shí)，通常應(yīng)考慮達(dá)到以下目標(biāo)：1．正確性2.可讀性3．健壯性4．高效率與低存儲(chǔ)量需求2007年9月5日星期三.1．正確性

首先，算法應(yīng)當(dāng)滿足以特定的“規(guī)格說(shuō)明”方式給出的需求。

其次，對(duì)算法是否“正確”的理解可以有以下四個(gè)層次：a．程序中不含語(yǔ)法錯(cuò)誤；b．程序?qū)τ趲捉M輸入數(shù)據(jù)能夠得出滿足要求的結(jié)果；2007年9月5日星期三.c．程序?qū)τ诰倪x擇的、典型、苛刻且?guī)в械箅y性的幾組輸入數(shù)據(jù)能夠得出滿足要求的結(jié)果；通常以第c層意義的正確性作為衡量一個(gè)算法是否合格的標(biāo)準(zhǔn)。

d．程序?qū)τ谝磺泻戏ǖ妮斎霐?shù)據(jù)都能得出滿足要求的結(jié)果；2007年9月5日星期三.2.可讀性

算法主要是為了人的閱讀與交流，其次才是為計(jì)算機(jī)執(zhí)行，因此算法應(yīng)該易于人的理解；另一方面，晦澀難讀的程序易于隱藏較多錯(cuò)誤而難以調(diào)試。解決可讀性的方法：1.程序結(jié)構(gòu)清晰,層次分明2.變量名命名規(guī)范易懂3.提供程序注釋2007年9月5日星期三.3．健壯性

當(dāng)輸入的數(shù)據(jù)非法時(shí)，算法應(yīng)當(dāng)恰當(dāng)?shù)刈鞒龇从郴蜻M(jìn)行相應(yīng)處理，而不是產(chǎn)生莫名奇妙的輸出結(jié)果。并且，處理出錯(cuò)的方法不應(yīng)是中斷程序的執(zhí)行，而應(yīng)是返回一個(gè)表示錯(cuò)誤或錯(cuò)誤性質(zhì)的值，以便在更高的抽象層次上進(jìn)行處理。2007年9月5日星期三.4．高效率與低存儲(chǔ)量需求

通常，效率指的是算法執(zhí)行時(shí)間；存儲(chǔ)量指的是算法執(zhí)行過(guò)程中所需的最大存儲(chǔ)空間，兩者都與問(wèn)題的規(guī)模有關(guān)。2007年9月5日星期三.三、算法效率的衡量方法和準(zhǔn)則通常有兩種衡量算法效率的方法:

事后統(tǒng)計(jì)法事前分析估算法缺點(diǎn)：1．必須執(zhí)行程序2．其它因素掩蓋算法本質(zhì)2007年9月5日星期三.和算法執(zhí)行時(shí)間相關(guān)的因素：1．算法選用的策略2．問(wèn)題的規(guī)模3．編寫(xiě)程序的語(yǔ)言4．編譯程序產(chǎn)生的機(jī)器代碼的質(zhì)量5．計(jì)算機(jī)執(zhí)行指令的速度2007年9月5日星期三.一個(gè)特定算法的“運(yùn)行工作量”的大小，只依賴于問(wèn)題的規(guī)模（通常用整數(shù)量n表示），或者說(shuō)，它是問(wèn)題規(guī)模的函數(shù)。2007年9月5日星期三.

假如，隨著問(wèn)題規(guī)模n的增長(zhǎng)，算法執(zhí)行時(shí)間的增長(zhǎng)率和f(n)的增長(zhǎng)率相同，則可記作：T(n)=O(f(n))稱T(n)為算法的(漸近)時(shí)間復(fù)雜度。2007年9月5日星期三.如何估算算法的時(shí)間復(fù)雜度？2007年9月5日星期三.算法=控制結(jié)構(gòu)+原操作（固有數(shù)據(jù)類型的操作）算法的執(zhí)行時(shí)間

=原操作(i)的執(zhí)行次數(shù)×原操作(i)的執(zhí)行時(shí)間

算法的執(zhí)行時(shí)間

與

原操作執(zhí)行次數(shù)之和

成正比

2007年9月5日星期三.

從算法中選取一種對(duì)于所研究的問(wèn)題來(lái)說(shuō)是基本操作

的原操作，以該基本操作在算法中重復(fù)執(zhí)行的次數(shù)作為算法運(yùn)行時(shí)間的衡量準(zhǔn)則。2007年9月5日星期三.例一兩個(gè)矩陣相乘voidmult(inta[],intb[],int&c[]){

//以二維數(shù)組存儲(chǔ)矩陣元素，c為a和b的乘積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];

}//for}//mult基本操作:

乘法操作時(shí)間復(fù)雜度:

O(n3)2007年9月5日星期三.例二選擇排序voidselect_sort(int&a[],intn){

//將a中整數(shù)序列重新排列成自小至大有序的整數(shù)序列。

}//select_sort基本操作:

比較(數(shù)據(jù)元素)操作時(shí)間復(fù)雜度:

O(n2)j=i;//

選擇第i個(gè)最小元素for(k=i+1;k<n;++k)

if(a[k]<a[j])j=k;for(i=0;i<n-1;++i){if(j!=i)a[j]←→a[i]}2007年9月5日星期三.例三起泡排序voidbubble_sort(int&a[],intn){

//將a中整數(shù)序列重新排列成自小至大有序的整數(shù)序列。for

(i=n-1,change=TRUE;i>1&&change;--i)}//bubble_sort基本操作:

賦值操作時(shí)間復(fù)雜度:

O(n2){

change=FALSE;

//change為元素進(jìn)行交換標(biāo)志

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

if(a[j]>a[j+1])

{

a[j]←→a[j+1];

change=TRUE;}}//一趟起泡2007年9月5日星期三.四、算法的存儲(chǔ)空間需求算法的空間復(fù)雜度定義為:

表示隨著問(wèn)題規(guī)模n的增大，算法運(yùn)行所需存儲(chǔ)量的增長(zhǎng)率與g(n)的增長(zhǎng)率相同。S(n)=O(g(n))2007年9月5日星期三.算法的存儲(chǔ)量包括:1．輸入數(shù)據(jù)所占空間2．程序本身所占空間3．輔助變量所占空間2007年9月5日星期三.

若輸入數(shù)據(jù)所占空間只取決于問(wèn)題本身，和算法無(wú)關(guān)，則只需要分析除輸入和程序之外的輔助變量所占額外空間。

若所需額外空間相對(duì)于輸入數(shù)據(jù)量來(lái)說(shuō)是常數(shù)，則稱此算法為原地工作。

若所需存儲(chǔ)量依賴于特定的輸入，則通常按最壞情況考慮。2007年9月5日星期三.

本章是為以后各章討論的內(nèi)容作基本知識(shí)的準(zhǔn)備，介紹數(shù)據(jù)結(jié)構(gòu)和算法等基本概念。

數(shù)據(jù)是計(jì)算機(jī)操作對(duì)象的總稱，它是計(jì)算機(jī)處理的符號(hào)的集合，集合中的個(gè)體為一個(gè)數(shù)據(jù)元素。數(shù)據(jù)元素可以是不可分割的原子，也可以由若干數(shù)據(jù)項(xiàng)合成，因此在數(shù)據(jù)結(jié)構(gòu)中討論的基本單位是數(shù)據(jù)元素，而最小單位是數(shù)據(jù)項(xiàng)。

【本章小結(jié)】2007年9月5日星期三.數(shù)據(jù)結(jié)構(gòu)是由若干特性相同的數(shù)據(jù)元素構(gòu)成的集合，且在集合上存在一種或多種關(guān)系。由關(guān)系不同可將數(shù)據(jù)結(jié)構(gòu)分為四類：線性結(jié)構(gòu)、樹(shù)形結(jié)構(gòu)、圖狀結(jié)構(gòu)和集合結(jié)構(gòu)。數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是數(shù)據(jù)邏輯結(jié)構(gòu)在計(jì)算機(jī)中的映象，由關(guān)系的兩種映象方法可得到兩類存儲(chǔ)結(jié)構(gòu)：一類是順序存儲(chǔ)結(jié)構(gòu)，它以數(shù)據(jù)元素相對(duì)的存儲(chǔ)位置表示關(guān)系，則存儲(chǔ)結(jié)構(gòu)中只包含數(shù)據(jù)元素本身的信息；另一類是鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，它以附加的指針信息（后繼元素的存儲(chǔ)地址）表示關(guān)系。2007年9月5日星期三.數(shù)據(jù)結(jié)構(gòu)的操作是和數(shù)據(jù)結(jié)構(gòu)本身密不可分的，兩者作為一個(gè)整體可用抽象數(shù)據(jù)類型進(jìn)行描述。抽象數(shù)據(jù)類型是一個(gè)數(shù)學(xué)模型以及定義在該模型上的一組操作，因此它和高級(jí)程序設(shè)計(jì)語(yǔ)言中的數(shù)據(jù)類型具有相同含義，而抽象數(shù)據(jù)類型的范疇更廣，它不局限于現(xiàn)有程序設(shè)計(jì)語(yǔ)言中已經(jīng)實(shí)現(xiàn)的數(shù)據(jù)類型（它們通常被稱為固有數(shù)據(jù)類型），但抽象數(shù)據(jù)類型需要借用固有數(shù)據(jù)類型表示并實(shí)現(xiàn)。抽象數(shù)據(jù)類型的三大要素為數(shù)據(jù)對(duì)象、數(shù)據(jù)關(guān)系和基本操作，同時(shí)數(shù)據(jù)抽象和數(shù)據(jù)封裝是抽象數(shù)據(jù)類型的兩個(gè)重要特性.

算法是進(jìn)行程序設(shè)計(jì)的另一不可缺少的要素。算法是對(duì)問(wèn)題求解的一種描述，是為解決一個(gè)或一類問(wèn)題給出的一種確定規(guī)則的描述。一個(gè)完整的算法應(yīng)該具有下列五個(gè)要素：有窮性、確定性、可行性、有輸入和有輸出。一個(gè)正確的算法應(yīng)對(duì)苛刻且?guī)в械箅y性的輸入數(shù)據(jù)也能得出正確的結(jié)果，并且對(duì)不正確的輸入也能作出正確的反映。2007年9月5日星期三.算法的時(shí)間復(fù)雜度是比較不同算法效率的一種準(zhǔn)則，算法時(shí)間復(fù)雜度的估算基于算法中基本操作的重復(fù)執(zhí)行次數(shù)，或處于最深層循環(huán)內(nèi)的語(yǔ)句的頻度。算法空間復(fù)雜度可作為算法所需存儲(chǔ)量的一種量度，它主要取決于算法的輸入量和輔助變量所占空間，若算法的輸入僅取決于問(wèn)題本身而和算法無(wú)關(guān)，則算法空間復(fù)雜度的估算只需考察算法中所用輔助變量所占空間，若算法的空間復(fù)雜度為常量級(jí)，則稱該算法為原地工作的算法。