數(shù)據(jù)結(jié)構(gòu)概述課件

1.1為什么學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)

1.2數(shù)據(jù)結(jié)構(gòu)的有關(guān)概念和術(shù)語(yǔ)

1.3算法和算法描述

1.4算法的時(shí)空效率分析方法

1.5小結(jié)與習(xí)題數(shù)據(jù)結(jié)構(gòu)概述11.1為什么要學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)

研究數(shù)據(jù)的特性、數(shù)據(jù)間的相互關(guān)系及其對(duì)應(yīng)的存儲(chǔ)表示，并利用這些特性、關(guān)系和存儲(chǔ)表示設(shè)計(jì)出相應(yīng)的算法和程序。為什么要學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)？計(jì)算機(jī)處理的數(shù)據(jù)量越來(lái)越大；數(shù)據(jù)的類型越來(lái)越多；數(shù)據(jù)的結(jié)構(gòu)越來(lái)越復(fù)雜。解決一個(gè)問(wèn)題時(shí)幾個(gè)步驟：抽象出一個(gè)適當(dāng)?shù)臄?shù)學(xué)模型，設(shè)計(jì)或選擇一個(gè)解決此類數(shù)學(xué)模型的算法，編寫(xiě)程序進(jìn)行調(diào)試、測(cè)試，直至得到最終的解答。2【例1-1】學(xué)生信息檢索問(wèn)題。學(xué)生信息包括學(xué)號(hào)、姓名、性別和成績(jī)等，一行為一個(gè)記錄，表示一個(gè)學(xué)生的信息（也稱為一個(gè)數(shù)據(jù)元素），一列為一個(gè)屬性。學(xué)

號(hào)姓

名性

別成

績(jī)20050601張

三男51820050602李一寧女49620050603吳

磊女581.5……………20050636梁

磊男529線性關(guān)系:對(duì)線性表的主要操作有查找、修改、插入和刪除等。

3【例1-2】某大學(xué)專業(yè)設(shè)置問(wèn)題。顯然這種關(guān)系用“樹(shù)”型結(jié)構(gòu)來(lái)表示更形象。通常用來(lái)表示結(jié)點(diǎn)的分層組織，結(jié)點(diǎn)之間是一對(duì)多的關(guān)系。對(duì)樹(shù)型結(jié)構(gòu)主要操作有查找、修改、插入和刪除等。**大學(xué)機(jī)械工程系電子工程系計(jì)算機(jī)與信息工程系機(jī)械制造材料科學(xué)電子應(yīng)用電氣自動(dòng)化計(jì)算機(jī)應(yīng)用與維護(hù)計(jì)算機(jī)應(yīng)用與維護(hù)4【例1-3】通信網(wǎng)絡(luò)問(wèn)題。帶圓圈的頂點(diǎn)表示城市，頂點(diǎn)和頂點(diǎn)之間的連線和數(shù)據(jù)表示城市之間的通信線路及其長(zhǎng)度。，各頂點(diǎn)之間是多對(duì)多的關(guān)系，是網(wǎng)狀結(jié)構(gòu)，也稱為圖型結(jié)構(gòu)，操作有：求從一個(gè)頂點(diǎn)到另一個(gè)頂點(diǎn)的最短路徑等。由以上三個(gè)例子可見(jiàn)，描述這類非數(shù)值計(jì)算問(wèn)題的數(shù)學(xué)模型有線性表、樹(shù)、圖等。所有的計(jì)算機(jī)系統(tǒng)軟件和應(yīng)用軟件都要用到各種類型的數(shù)據(jù)結(jié)構(gòu)。

B

CDFEA6045404230408065322651.2數(shù)據(jù)結(jié)構(gòu)的有關(guān)概念和術(shù)語(yǔ)

1.2.1基本概念和術(shù)語(yǔ)1．?dāng)?shù)據(jù)（Data）是描述客觀事物的數(shù)值、字符以及所有能被輸入到計(jì)算機(jī)并能被計(jì)算機(jī)識(shí)別、存儲(chǔ)和處理的符號(hào)的集合?？陀^事物包括數(shù)值數(shù)據(jù)和非數(shù)值數(shù)據(jù)。數(shù)值數(shù)據(jù)：整數(shù)、實(shí)數(shù)或復(fù)數(shù)；非數(shù)值數(shù)據(jù)：字符、文字、圖形、圖像和聲音等。2．?dāng)?shù)據(jù)元素（DataElement）是數(shù)據(jù)的基本單位。在不同的條件下，數(shù)據(jù)元素又可稱為元素、結(jié)點(diǎn)、頂點(diǎn)、記錄等。數(shù)據(jù)項(xiàng)：數(shù)據(jù)結(jié)構(gòu)中討論的最小單位。一個(gè)數(shù)據(jù)元素可由若干個(gè)數(shù)據(jù)項(xiàng)（DataItem）組成。例如，學(xué)生信息表的每一個(gè)數(shù)據(jù)元素就是一個(gè)學(xué)生記錄，它包括學(xué)生的學(xué)號(hào)、姓名、性別、成績(jī)等數(shù)據(jù)項(xiàng)。63．?dāng)?shù)據(jù)對(duì)象（DataObject）是具有相同性質(zhì)數(shù)據(jù)元素的集合。4．?dāng)?shù)據(jù)類型(DataType)

在用高級(jí)語(yǔ)言編寫(xiě)的程序中，每個(gè)變量、常量或表達(dá)式都有一個(gè)它所屬的確定的數(shù)據(jù)類型。5．抽象數(shù)據(jù)類型（AbstractDataType，簡(jiǎn)稱ADT）是指基于邏輯關(guān)系的數(shù)據(jù)類型以及定義在該類型之上的一組操作。ADT抽象數(shù)據(jù)類型名{

數(shù)據(jù)對(duì)象：（數(shù)據(jù)對(duì)象的定義）數(shù)據(jù)關(guān)系：（數(shù)據(jù)關(guān)系的定義）基本操作：（基本操作的定義）}7【例1-4】線性表的抽象數(shù)據(jù)類型可描述如下：ADTLinear_list{數(shù)據(jù)元素所有ai屬于同一數(shù)據(jù)對(duì)象，i=1，2，…，n（n≥1）邏輯結(jié)構(gòu)所有數(shù)據(jù)元素ai存在次序關(guān)系（ai，ai+1），a1無(wú)前驅(qū)，an無(wú)后繼。操作

/*設(shè)L為L(zhǎng)inear_list類型的線性表*/InitList（L）；/*建立一個(gè)空的線性表L*/Length（L）；/*求線性表L的長(zhǎng)度*/GetElement（L，i）；/*取線性表L中的第i個(gè)元素*/Locate（L，x）；/*確定元素x在線性表L中的位置*/Insert（L，i，x）；/*在線性表L中的第i個(gè)位置處插入數(shù)據(jù)元素x*/Delete（L，i）；/*刪除表L中第i個(gè)位置的元素*/……}；/*ADTLinear_list*/81.2.2數(shù)據(jù)結(jié)構(gòu)定義數(shù)據(jù)結(jié)構(gòu)（DataStructure）是指互相之間存在著一種或多種關(guān)系的數(shù)據(jù)元素的集合。數(shù)據(jù)元素之間的關(guān)系稱為結(jié)構(gòu)。數(shù)據(jù)的結(jié)構(gòu)包括邏輯結(jié)構(gòu)和物理結(jié)構(gòu)。（1）邏輯結(jié)構(gòu)：是數(shù)據(jù)元素之間的相互邏輯關(guān)系，它與數(shù)據(jù)的存儲(chǔ)無(wú)關(guān)，是獨(dú)立于計(jì)算機(jī)而存在。數(shù)據(jù)結(jié)構(gòu)是由兩個(gè)集合構(gòu)成的一個(gè)二元組：Data_Structure(D，R))Data_Structure是一種數(shù)據(jù)結(jié)構(gòu)，它由同屬一個(gè)數(shù)據(jù)對(duì)象的數(shù)據(jù)元素的有限集合D和D上二元關(guān)系的有限集合R組成。其中：D={di|1≦i≦n,n≧1}R={rj|1≦j≦m,m≧1}9di表示第i個(gè)數(shù)據(jù)元素，rj表示第j個(gè)關(guān)系。D上二元關(guān)系R是序偶的集合。對(duì)于R中的任一序偶<x,y>(x,y∈D)，x稱為序偶的第一元素，y稱為序偶的第二元素，又稱序偶的第一元素是第二元素的直接前驅(qū)；第二元素為第一個(gè)元素的直接后繼?！纠?-5】樹(shù)型結(jié)構(gòu)中的圓圈代表數(shù)據(jù)元素，帶箭頭的連線表示元素之間的關(guān)系，試用二元組表示法表示其邏輯結(jié)構(gòu)。解：二元組為(D,R)其中，D={A,B,C,E,F,G,H,I,J};R={<A,B>,<A,C>,<A,E>,<B,F>,<B,G>,<E,H>,<E,I>,<E,J>}ABCEFGHIJ10通常有下列四種基本的結(jié)構(gòu)：a.集合結(jié)構(gòu)。集合是元素關(guān)系極為松散的一種結(jié)構(gòu)。b.線性結(jié)構(gòu)。線性結(jié)構(gòu)的邏輯特征是：若結(jié)構(gòu)是非空集，則有且僅有一個(gè)開(kāi)始結(jié)點(diǎn)和一個(gè)終端結(jié)點(diǎn)，并且所有結(jié)點(diǎn)都最多只有一個(gè)直接前驅(qū)和一個(gè)直接后繼。c.樹(shù)型結(jié)構(gòu)。該結(jié)構(gòu)的數(shù)據(jù)元素之間存在著一對(duì)多的關(guān)系。d.圖型結(jié)構(gòu)。該結(jié)構(gòu)的數(shù)據(jù)元素之間存在著多對(duì)多的關(guān)系，圖型結(jié)構(gòu)也稱作網(wǎng)狀結(jié)構(gòu)。（2）物理結(jié)構(gòu)（或存儲(chǔ)結(jié)構(gòu)）是數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的表示（又稱映像），它包括數(shù)據(jù)元素的機(jī)內(nèi)表示和關(guān)系的機(jī)內(nèi)表示。具體實(shí)現(xiàn)的方法有順序、鏈接、索引、散列等多種，數(shù)據(jù)的具體操作與存儲(chǔ)結(jié)構(gòu)有很密切的聯(lián)系。數(shù)據(jù)結(jié)構(gòu)作為一門學(xué)科主要研究數(shù)據(jù)的各種邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)，以及對(duì)數(shù)據(jù)的各種操作。同時(shí)還要考慮執(zhí)行算法時(shí)的時(shí)間和空間效率。111.3算法和算法描述⑴有窮性。一個(gè)算法必須在有窮步之后結(jié)束，即必須在有限時(shí)間內(nèi)完成。⑵確定性。算法的每一步必須有確切的定義，無(wú)二義性。⑶可行性。算法中的每一步都可以通過(guò)已經(jīng)實(shí)現(xiàn)的基本運(yùn)算的有限次執(zhí)行得以實(shí)現(xiàn)。⑷輸入。一個(gè)算法具有零個(gè)或多個(gè)輸入，這些輸入取自特定的數(shù)據(jù)對(duì)象集合。⑸輸出。一個(gè)算法具有一個(gè)或多個(gè)輸出，這些輸出同輸入之間存在某種特定的關(guān)系。1.3.1算法與算法特性算法（Algorithm）是對(duì)特定問(wèn)題求解步驟的一種描述，是指令的有限序列。一個(gè)算法應(yīng)該具有下列特性：12一個(gè)好的算法通常要達(dá)到以下的要求：正確。執(zhí)行結(jié)果應(yīng)當(dāng)滿足預(yù)先規(guī)定的功能和性能要求?？勺x。應(yīng)當(dāng)思路清晰、層次分明、簡(jiǎn)單明了、易讀易懂。健壯。當(dāng)輸入不合法數(shù)據(jù)時(shí)，應(yīng)能作適當(dāng)處理，不至引起嚴(yán)重后果。高效。有效使用存儲(chǔ)空間和有較高的時(shí)間效率。1.3.2算法描述最簡(jiǎn)單的方法是使用自然語(yǔ)言，其優(yōu)點(diǎn)是簡(jiǎn)單且便于人們對(duì)算法的閱讀；缺點(diǎn)是轉(zhuǎn)換成高級(jí)語(yǔ)言困難。類C語(yǔ)言忽略高級(jí)程序設(shè)計(jì)語(yǔ)言中一些嚴(yán)格的語(yǔ)法規(guī)則與描述細(xì)節(jié)，因此它比程序設(shè)計(jì)語(yǔ)言更容易描述和被人理解，比自然語(yǔ)言更接近程序設(shè)計(jì)語(yǔ)言，很容易被轉(zhuǎn)換成高級(jí)語(yǔ)言。13本書(shū)對(duì)所用類C語(yǔ)言作如下約定：1．問(wèn)題的規(guī)模用MAXSIZE#defineMAXSIZE602．預(yù)定義常量和類型：#defineTRUE1#defineFALSE0#defineOK1#defineERROR0#defineOVERFLOW-1typedefintStatus;3．?dāng)?shù)據(jù)結(jié)構(gòu)（存儲(chǔ)結(jié)構(gòu)）的表示用類型定義（typedef）描述。數(shù)據(jù)元素類型約定為ElemType，由用戶在使用該數(shù)據(jù)類型時(shí)自行定義。例1.學(xué)生信息檢索系統(tǒng)中，用一維數(shù)組作存儲(chǔ)n個(gè)學(xué)生的信息，數(shù)組中的數(shù)據(jù)元素有4個(gè)域：學(xué)號(hào)、姓名、性別和成績(jī)：typedefstructstd_info{longintNum;/*學(xué)號(hào)域*/charName[8];/*姓名域*/charSex;/*性別域*/floatScore;/*成績(jī)域*/}ElemType;144．基本操作的算法都用以下形式的函數(shù)描述函數(shù)類型函數(shù)名(函數(shù)參數(shù)表){/*算法說(shuō)明*/語(yǔ)句序列；}/*函數(shù)名*/5．C語(yǔ)言中的常用語(yǔ)句賦值（=）、選擇（if、if…else、switch…case…default）、循環(huán)（for、while、do…while）、結(jié)束（return、break、continue、exit）、輸入和輸出等語(yǔ)句。6．基本運(yùn)算和基本函數(shù)基本運(yùn)算有+、-、*、/、%、->、&&和||等。基本函數(shù)有max、min、abs、fabs、eof等。15

例設(shè)某班級(jí)有n個(gè)學(xué)生，編寫(xiě)算法，查找班級(jí)中成績(jī)最高的學(xué)生，并輸出該學(xué)生的所有信息。分析：，算法依次查看數(shù)組中的元素，并保存當(dāng)前最高成績(jī)及其下標(biāo)。使用類C語(yǔ)言編寫(xiě)：intlargest（ElemTypeS[MAXSIZE]，intn）{floatcurrlarge=0.0;inti,j=0;/*賦初值

*/

for（i=0;i<n;i++）

/*進(jìn)入循環(huán)

*/

if(S[i].Score>currlarge){j=i;currlarge=S[i].Score;}printf(“%10ld%10s%10c%10f\n”,S[j].Num,S[j].name,S[j].Sex,S[j].Score);}/*largest*/typedefstructstd_info{longintNum;charName[8];charSex;floatScore;}ElemType;161.4算法時(shí)空效率分析方法評(píng)價(jià)算法的性能用時(shí)間復(fù)雜度與空間復(fù)雜度來(lái)度量。1、算法的時(shí)間復(fù)雜度算法的時(shí)間復(fù)雜度（Timecomplexity）是指算法轉(zhuǎn)換為程序后(這里仍稱為算法)在計(jì)算機(jī)上從開(kāi)始運(yùn)行到結(jié)束所需要的時(shí)間。運(yùn)行所需要的時(shí)間取決于下列因素：⑴硬件的速度。與硬件的配置高低有關(guān)。⑵書(shū)寫(xiě)程序的語(yǔ)言。語(yǔ)言的級(jí)別越高，其執(zhí)行效率就越低。⑶編譯程序所生成目標(biāo)代碼的質(zhì)量。⑷依據(jù)算法所選用的策略。⑸問(wèn)題的規(guī)模。一般情況下，處理的數(shù)據(jù)量越大，執(zhí)行的時(shí)間相對(duì)也越長(zhǎng)。17通常的做法是：不考慮不確定的情況，而以算法中簡(jiǎn)單操作重復(fù)執(zhí)行的次數(shù)作為算法的時(shí)間度量。為此，一個(gè)特定算法的運(yùn)行時(shí)間長(zhǎng)短就只依賴于問(wèn)題的規(guī)模n，或者說(shuō)它是問(wèn)題規(guī)模n的函數(shù)f(n)?！纠?-7】求累加求和intsum(intb[]，intn）｛intsum=0;/*第1條定義并賦初值語(yǔ)句執(zhí)行1次*/

for（inti=0；i<n；i++）/*3n+2次*/sum+=b[i];/*n次*/returnsum;｝/*返回語(yǔ)句執(zhí)行1次*/18要精確地計(jì)算f(n)是困難的，引入漸進(jìn)時(shí)間復(fù)雜度在數(shù)量上估計(jì)一個(gè)算法的執(zhí)行時(shí)間。算法時(shí)間的度量記作T(n)=Ο(f(n))它表示隨問(wèn)題的規(guī)模n的增大，算法執(zhí)行時(shí)間的增長(zhǎng)率和f(n)相同。使用大Ο記號(hào)，Ο(f(n))稱為算法的漸進(jìn)時(shí)間復(fù)雜度（AsymptoticTimeComplexity），簡(jiǎn)稱時(shí)間復(fù)雜度。例如，一個(gè)程序的實(shí)際執(zhí)行時(shí)間為

T(n)＝2.7n3+3.8n2+5.3。則T(n)＝Ο(n3)。19【例1-8】求下面程序段的時(shí)間復(fù)雜度。

s=0;for(j=1;j<=n;j++)for(x=1,k=1;k<=n;k++){x=x*k;s+=x;}解：該算法中“s=0;”的頻度為1，后面由兩個(gè)“for”語(yǔ)句構(gòu)成了一個(gè)二重循環(huán)結(jié)構(gòu)，其內(nèi)循環(huán)體執(zhí)行的頻度為n2，用最高數(shù)量級(jí)n2的表示，則該程序段的時(shí)間復(fù)雜度為O(n2)。通常將稱Ο(1)為常數(shù)階，Ο(n)為線性階，O(n2)為平方階。算法還可能