數(shù)據(jù)結(jié)構(gòu)-嚴(yán)蔚敏

上課前需要說(shuō)明的幾個(gè)問(wèn)題：1.任課教師：焦賢沛聯(lián)系電話：838166562.交流信箱：jxp1972@163.com3.關(guān)于數(shù)據(jù)結(jié)構(gòu)課程：教材、重要性、時(shí)間安排（64+32）、考試1精選ppt第一章緒論2精選ppt1.1數(shù)據(jù)結(jié)構(gòu)討論的范疇1.2基本概念1.3算法和算法的量度3精選ppt1.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é)模型4精選ppt結(jié)構(gòu)靜力分析計(jì)算例如:數(shù)值計(jì)算的程序設(shè)計(jì)問(wèn)題─━線性代數(shù)方程組─━環(huán)流模式方程(球面坐標(biāo)系)全球天氣預(yù)報(bào)5精選ppt

【例1-1】圖書(shū)目錄表

由于表中每條記錄（表示每一本書(shū)）的登錄號(hào)各不相同，所以可用登錄號(hào)來(lái)唯一地標(biāo)識(shí)每條記錄（一本圖書(shū)）。在計(jì)算機(jī)的數(shù)據(jù)管理中，能唯一地標(biāo)識(shí)一條記錄的數(shù)據(jù)項(xiàng)被稱(chēng)為關(guān)鍵字。因?yàn)槊勘緢D書(shū)的登錄排列位置有先后次序，所以在表中會(huì)按登錄號(hào)形成一種次序關(guān)系，即整個(gè)二維表就是圖書(shū)數(shù)據(jù)的一個(gè)線性序列。這種關(guān)系被稱(chēng)為線性結(jié)構(gòu)。

非數(shù)值計(jì)算的程序設(shè)計(jì)問(wèn)題6精選ppt返回返回7精選ppt

描述磁盤(pán)目錄和文件結(jié)構(gòu)時(shí)，假設(shè)每個(gè)磁盤(pán)包括一個(gè)根目錄（root）和若干個(gè)一級(jí)子目錄，每個(gè)一級(jí)子目錄中又包含若干個(gè)二級(jí)子目錄….這種關(guān)系很像自然界中的樹(shù)，所以稱(chēng)為目錄樹(shù)。如左圖所示?！纠?-2】磁盤(pán)目錄結(jié)構(gòu)和文件管理系統(tǒng)

在這種結(jié)構(gòu)中，目錄和目錄以及目錄和文件之間呈現(xiàn)出一對(duì)多的非線性關(guān)系。即根root有多個(gè)下屬（也稱(chēng)為后代），每一后代又有屬于自己的后代；而任一個(gè)子目錄或文件都只有一個(gè)唯一的上級(jí)（也稱(chēng)為雙親）。稱(chēng)這種數(shù)學(xué)模型為樹(shù)型數(shù)據(jù)結(jié)構(gòu)。8精選ppt【例1-3】教學(xué)計(jì)劃編排問(wèn)題

假如一個(gè)教學(xué)計(jì)劃中包含許多課程。在課程之間，有些必須按規(guī)定的先后次序排課，如：學(xué)C6課程必須先學(xué)C3課，學(xué)C3課程必須先學(xué)C1課。這些課程之間存在先修和后續(xù)的關(guān)系。在這種結(jié)構(gòu)中，表示課程的數(shù)據(jù)之間呈現(xiàn)多對(duì)多的非線性關(guān)系，稱(chēng)這類(lèi)數(shù)學(xué)模型為圖形結(jié)構(gòu)。9精選ppt圖結(jié)構(gòu)還有：多岔路口交通燈的控制和管理、煤氣管道的鋪設(shè)造價(jià)等。

數(shù)據(jù)結(jié)構(gòu)是一門(mén)討論“描述現(xiàn)實(shí)世界實(shí)體的數(shù)學(xué)模型(非數(shù)值計(jì)算)及其上的操作在計(jì)算機(jī)中如何表示和實(shí)現(xiàn)”的學(xué)科。概括地說(shuō)：10精選ppt1.2基本概念一、數(shù)據(jù)與數(shù)據(jù)結(jié)構(gòu)二、數(shù)據(jù)類(lèi)型三、抽象數(shù)據(jù)類(lèi)型11精選ppt一、數(shù)據(jù)與數(shù)據(jù)結(jié)構(gòu)所有能被輸入到計(jì)算機(jī)中，且能被計(jì)算機(jī)處理的符號(hào)的集合。數(shù)據(jù):是計(jì)算機(jī)操作的對(duì)象的總稱(chēng)。是計(jì)算機(jī)處理的信息的某種特定的符號(hào)表示形式。12精選ppt是數(shù)據(jù)（集合）中的一個(gè)“個(gè)體”數(shù)據(jù)元素:是數(shù)據(jù)結(jié)構(gòu)中討論的基本單位13精選ppt

數(shù)據(jù)項(xiàng)：是數(shù)據(jù)結(jié)構(gòu)中討論的最小單位數(shù)據(jù)元素可以是數(shù)據(jù)項(xiàng)的集合例如：描述一個(gè)學(xué)生的數(shù)據(jù)元素可以是稱(chēng)之為組合項(xiàng)14精選ppt數(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,a33214，6587，9345a1a2a36587，3214，9345a2a1a3≠例如:15精選ppt又例，在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ù)元素的集合16精選ppt再例，在一維數(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)”17精選ppt數(shù)據(jù)的邏輯結(jié)構(gòu)可歸結(jié)為以下四類(lèi):線性結(jié)構(gòu)樹(shù)形結(jié)構(gòu)圖狀結(jié)構(gòu)集合結(jié)構(gòu)18精選ppt數(shù)據(jù)結(jié)構(gòu)的形式定義為:數(shù)據(jù)結(jié)構(gòu)是一個(gè)二元組Data_Structures=(D,S)其中:D是數(shù)據(jù)元素的有限集，

S是D上關(guān)系的有限集。19精選ppt數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)

——邏輯結(jié)構(gòu)在存儲(chǔ)器中的映象“數(shù)據(jù)元素”的映象？“關(guān)系”的映象？20精選ppt數(shù)據(jù)元素的映象方法：用二進(jìn)制位(bit)的位串表示數(shù)據(jù)元素(321)10=(501)8=(101000001)2A=(101)8=(001000001)221精選ppt關(guān)系的映象方法：（表示x,y的方法）順序映象以相對(duì)的存儲(chǔ)位置表示后繼關(guān)系例如:令y的存儲(chǔ)位置和x的存儲(chǔ)位置之間差一個(gè)常量C而C是一個(gè)隱含值，整個(gè)存儲(chǔ)結(jié)構(gòu)中只含數(shù)據(jù)元素本身的信息xy22精選ppt鏈?zhǔn)接诚笠愿郊有畔?指針)表示后繼關(guān)系需要用一個(gè)和x在一起的附加信息指示y的存儲(chǔ)位置yx23精選ppt在不同的編程環(huán)境中，存儲(chǔ)結(jié)構(gòu)可有不同的描述方法。當(dāng)用高級(jí)程序設(shè)計(jì)語(yǔ)言進(jìn)行編程時(shí)，通?？捎酶呒?jí)編程語(yǔ)言中提供的數(shù)據(jù)類(lèi)型描述之。24精選ppt例如:以三個(gè)帶有次序關(guān)系的整數(shù)表示一個(gè)長(zhǎng)整數(shù)時(shí)，可利用C語(yǔ)言中提供的整數(shù)數(shù)組類(lèi)型。typedefintLong_int[3]；定義長(zhǎng)整數(shù)為:25精選ppt二、數(shù)據(jù)類(lèi)型

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

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

不同類(lèi)型的變量，其所能取的值的范圍不同，所能進(jìn)行的操作不同。28精選ppt三、抽象數(shù)據(jù)類(lèi)型

(AbstractDataType簡(jiǎn)稱(chēng)ADT)是指一個(gè)數(shù)學(xué)模型以及定義在此數(shù)學(xué)模型上的一組操作。29精選ppt例如，抽象數(shù)據(jù)類(lèi)型復(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{30精選ppt基本操作：

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

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

GetReal(Z,&realPart)初始條件：復(fù)數(shù)已存在。操作結(jié)果：用realPart返回復(fù)數(shù)Z的實(shí)部值。31精選ppt

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的和值。}ADTComplex32精選ppt假設(shè):z1和z2是上述定義的復(fù)數(shù)則Add(z1,z2,z3)操作的結(jié)果z3=z1+z2即為用戶(hù)企求的結(jié)果33精選pptADT有兩個(gè)重要特征:數(shù)據(jù)抽象

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

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

S是D上的關(guān)系集；P是對(duì)D的基本操作集。35精選pptADT

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

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

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

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

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

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

floatrealpart；

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

Assign(complex&Z,

floatrealval,floatimagval)；//構(gòu)造復(fù)數(shù)Z,其實(shí)部和虛部分別被賦以參數(shù)//realval和imagval的值39精選pptfloat

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

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

//以sum返回兩個(gè)復(fù)數(shù)z1,z2的和40精選ppt//-----基本操作的實(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;}

{其它省略}41精選ppt1.3算法和算法的衡量一、算法二、算法設(shè)計(jì)的原則三、算法效率的衡量方法和準(zhǔn)則四、算法的存儲(chǔ)空間需求42精選ppt

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

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

2．確定性

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

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

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

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

d．程序?qū)τ谝磺泻戏ǖ妮斎霐?shù)據(jù)都能得出滿(mǎn)足要求的結(jié)果；49精選ppt2.可讀性

算法主要是為了人的閱讀與交流，其次才是為計(jì)算機(jī)執(zhí)行，因此算法應(yīng)該易于人的理解；另一方面，晦澀難讀的程序易于隱藏較多錯(cuò)誤而難以調(diào)試。50精選ppt3．健壯性

當(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)行處理。51精選ppt4．高效率與低存儲(chǔ)量需求

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

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

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

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

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

與

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

成正比

58精選ppt

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

的原操作，以該基本操作在算法中重復(fù)執(zhí)行的次數(shù)作為算法運(yùn)行時(shí)間的衡量準(zhǔn)則。59精選ppt例一兩個(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)60精選ppt例二選擇排序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]}61精選ppt例三起泡排序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;}}//一趟起泡62精選ppt四、算法的存儲(chǔ)空間需求算法的空間復(fù)雜度定義為:

表示隨著問(wèn)題規(guī)模n的增大，算法運(yùn)行所需存儲(chǔ)量的增長(zhǎng)率與g(n)的增長(zhǎng)率相同。S(n)=