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

數(shù)據(jù)結(jié)構(gòu)與數(shù)據(jù)庫第一頁，共42頁數(shù)據(jù)結(jié)構(gòu)與數(shù)據(jù)庫全文共42頁，當(dāng)前為第1頁。第一部分

數(shù)據(jù)結(jié)構(gòu)第二頁，共42頁數(shù)據(jù)結(jié)構(gòu)與數(shù)據(jù)庫全文共42頁，當(dāng)前為第2頁。教材《數(shù)據(jù)結(jié)構(gòu)（c語言版）》，嚴(yán)蔚敏等編著,清華大學(xué)出版社，1997《數(shù)據(jù)結(jié)構(gòu)題集（c語言版）》，嚴(yán)蔚敏等編著,清華大學(xué)出版社，1999第三頁，共42頁數(shù)據(jù)結(jié)構(gòu)與數(shù)據(jù)庫全文共42頁，當(dāng)前為第3頁。參考書《數(shù)據(jù)結(jié)構(gòu)(第二版)》，唐策善、黃劉生編著，中國(guó)科大出版社，2001

"DataStructureswithC++",WilliawFordetal.,PrenticeHallInc.,1996."DataStructures&ProgramDesigninC,2ndEd.",RobertKruseetal.,PrenticeHallInc.,1997.

第四頁，共42頁數(shù)據(jù)結(jié)構(gòu)與數(shù)據(jù)庫全文共42頁，當(dāng)前為第4頁。什么是數(shù)據(jù)結(jié)構(gòu)基本概念和術(shù)語抽象數(shù)據(jù)類型算法分析性能分析與度量第一章緒論第五頁，共42頁數(shù)據(jù)結(jié)構(gòu)與數(shù)據(jù)庫全文共42頁，當(dāng)前為第5頁。學(xué)生成績(jī)表格第六頁，共42頁數(shù)據(jù)結(jié)構(gòu)與數(shù)據(jù)庫全文共42頁，當(dāng)前為第6頁。選課單學(xué)號(hào)課程號(hào)時(shí)間成績(jī)20001DS2000SX20002001,22000,9788720002ART2000DS20002002,22001,2689020003SX2000DS20002000,92001,2877820004SX2000ART20002000,92002,28976第七頁，共42頁數(shù)據(jù)結(jié)構(gòu)與數(shù)據(jù)庫全文共42頁，當(dāng)前為第7頁。UNIX文件系統(tǒng)結(jié)構(gòu)圖/rootbinlibuseretcmathdsswyintaoxieStack.cppQueue.cppTree.cpp第八頁，共42頁數(shù)據(jù)結(jié)構(gòu)與數(shù)據(jù)庫全文共42頁，當(dāng)前為第8頁。綜上，描述這類非數(shù)值計(jì)算問題的數(shù)學(xué)模型不是數(shù)學(xué)方程,而是樹、表和圖之類的數(shù)據(jù)結(jié)構(gòu)。因此從廣義上講，數(shù)據(jù)結(jié)構(gòu)描述現(xiàn)實(shí)世界實(shí)體的數(shù)學(xué)模型及其上的操作在計(jì)算機(jī)中的表示和實(shí)現(xiàn).第九頁，共42頁數(shù)據(jù)結(jié)構(gòu)與數(shù)據(jù)庫全文共42頁，當(dāng)前為第9頁。信息？數(shù)據(jù)？知識(shí)？

？第十頁，共42頁數(shù)據(jù)結(jié)構(gòu)與數(shù)據(jù)庫全文共42頁，當(dāng)前為第10頁。基本概念和術(shù)語數(shù)據(jù)(Data)是信息的載體，是描述客觀事物的數(shù)、字符、以及所有能輸入到計(jì)算機(jī)中，被計(jì)算機(jī)程序識(shí)別和處理的符號(hào)的集合。

數(shù)值性數(shù)據(jù)非數(shù)值性數(shù)據(jù)第十一頁，共42頁數(shù)據(jù)結(jié)構(gòu)與數(shù)據(jù)庫全文共42頁，當(dāng)前為第11頁。數(shù)據(jù)元素（DataElement）數(shù)據(jù)的基本單位。在計(jì)算機(jī)程序中常作為一個(gè)整體進(jìn)行考慮和處理。有時(shí)一個(gè)數(shù)據(jù)元素可以由若干數(shù)據(jù)項(xiàng)(DataItem)組成。數(shù)據(jù)項(xiàng)是數(shù)據(jù)的不可分割的最小單位。數(shù)據(jù)元素又稱為元素、結(jié)點(diǎn)、記錄第十二頁，共42頁數(shù)據(jù)結(jié)構(gòu)與數(shù)據(jù)庫全文共42頁，當(dāng)前為第12頁。數(shù)據(jù)項(xiàng)(DataItem)

學(xué)號(hào)姓名出生日期年月日籍貫?zāi)昙?jí)系別宿舍號(hào)第十三頁，共42頁數(shù)據(jù)結(jié)構(gòu)與數(shù)據(jù)庫全文共42頁，當(dāng)前為第13頁。數(shù)據(jù)對(duì)象(DataObject)具有相同性質(zhì)的數(shù)據(jù)元素的集合。整數(shù)數(shù)據(jù)對(duì)象N={0,1,2,…}字母字符數(shù)據(jù)對(duì)象

C={‘A’,‘B’,‘C’,…‘F’}第十四頁，共42頁數(shù)據(jù)結(jié)構(gòu)與數(shù)據(jù)庫全文共42頁，當(dāng)前為第14頁。數(shù)據(jù)結(jié)構(gòu)（DataStructure）形式定義：

某一數(shù)據(jù)對(duì)象的所有數(shù)據(jù)成員之間的關(guān)系。記為：

Data_Structure={D,S}

其中，D是某一數(shù)據(jù)對(duì)象，S是該對(duì)象中所有數(shù)據(jù)成員之間的關(guān)系的有限集合。第十五頁，共42頁數(shù)據(jù)結(jié)構(gòu)與數(shù)據(jù)庫全文共42頁，當(dāng)前為第15頁。序偶:

一般來說，兩個(gè)具有固定次序的客體組成一個(gè)序偶，常常表示兩個(gè)客體之間的關(guān)系。記作<x,y>。其中的x和y分別稱為第一元素和第二元素。如：“中國(guó)地處亞洲”表示為<中國(guó)，亞洲>序偶具有確定的次序。

<x,y>=<u,v>,iffx=u,y=v第一元素本身也可是一序偶。這樣，序偶的概念可推廣到n元組。

如:三元組可定義為一序偶<<x,y>,z>第十六頁，共42頁數(shù)據(jù)結(jié)構(gòu)與數(shù)據(jù)庫全文共42頁，當(dāng)前為第16頁。關(guān)系：任一序偶的集合確定了一個(gè)二元關(guān)系R，R中任一序偶<x,y>可記做xRy。例如，在實(shí)數(shù)中關(guān)系>

可記作

>={<x,y>|x,y是實(shí)數(shù)且x>y}

數(shù)據(jù)結(jié)構(gòu)的一個(gè)例子（例1.5)Group=(P,R)

第十七頁，共42頁數(shù)據(jù)結(jié)構(gòu)與數(shù)據(jù)庫全文共42頁，當(dāng)前為第17頁。四類基本結(jié)構(gòu)集合線性結(jié)構(gòu)樹形結(jié)構(gòu)網(wǎng)狀結(jié)構(gòu)第十八頁，共42頁數(shù)據(jù)結(jié)構(gòu)與數(shù)據(jù)庫全文共42頁，當(dāng)前為第18頁。數(shù)據(jù)的邏輯結(jié)構(gòu)從邏輯關(guān)系上描述數(shù)據(jù)，與數(shù)據(jù)的存儲(chǔ)無關(guān)；從具體問題抽象出來的數(shù)據(jù)模型；與數(shù)據(jù)元素本身的形式、內(nèi)容無關(guān)；與數(shù)據(jù)元素的相對(duì)位置無關(guān)。第十九頁，共42頁數(shù)據(jù)結(jié)構(gòu)與數(shù)據(jù)庫全文共42頁，當(dāng)前為第19頁。數(shù)據(jù)的邏輯結(jié)構(gòu)分類線性結(jié)構(gòu)

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

樹圖（或網(wǎng)絡(luò)）第二十頁，共42頁數(shù)據(jù)結(jié)構(gòu)與數(shù)據(jù)庫全文共42頁，當(dāng)前為第20頁。bindevetclibuser2114131211234678910315871011998745662313155線性結(jié)構(gòu)樹形結(jié)構(gòu)

樹二叉樹二叉排序樹第二十一頁，共42頁數(shù)據(jù)結(jié)構(gòu)與數(shù)據(jù)庫全文共42頁，當(dāng)前為第21頁。堆結(jié)構(gòu)123548711102916125643125436113318146651921圖結(jié)構(gòu)網(wǎng)絡(luò)結(jié)構(gòu)第二十二頁，共42頁數(shù)據(jù)結(jié)構(gòu)與數(shù)據(jù)庫全文共42頁，當(dāng)前為第22頁。數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的表示（又稱映象）。包括數(shù)據(jù)元素的表示和關(guān)系的表示。數(shù)據(jù)元素的表示:位串（元素、結(jié)點(diǎn)）關(guān)系的表示

順序映象非順序映象第二十三頁，共42頁數(shù)據(jù)結(jié)構(gòu)與數(shù)據(jù)庫全文共42頁，當(dāng)前為第23頁。抽象數(shù)據(jù)類型（AbstractDataType）數(shù)據(jù)類型

定義：一個(gè)值的集合和定義在這個(gè)值集上的一組操作的總稱。C語言中的基本數(shù)據(jù)類型

intcharfloatdoublevoid整型字符型浮點(diǎn)型雙精度型無值第二十四頁，共42頁數(shù)據(jù)結(jié)構(gòu)與數(shù)據(jù)庫全文共42頁，當(dāng)前為第24頁。抽象數(shù)據(jù)類型是指一個(gè)數(shù)學(xué)模型以及定義在此數(shù)學(xué)模型上的一組操作數(shù)據(jù)結(jié)構(gòu)+定義在此數(shù)據(jù)結(jié)構(gòu)上的一組操作=抽象數(shù)據(jù)類型例如：矩陣+（求轉(zhuǎn)置、加、乘、 求逆、求特征值） 構(gòu)成一個(gè)矩陣的抽象數(shù)據(jù)類型第二十五頁，共42頁數(shù)據(jù)結(jié)構(gòu)與數(shù)據(jù)庫全文共42頁，當(dāng)前為第25頁。抽象數(shù)據(jù)類型的描述抽象數(shù)據(jù)類型可用（D，S，P）三元組表示 其中，D是數(shù)據(jù)對(duì)象，S是D上的關(guān)系集，P是對(duì)D的基本操作集。

ADT抽象數(shù)據(jù)類型名{

數(shù)據(jù)對(duì)象：〈數(shù)據(jù)對(duì)象的定義〉

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

基本操作：〈基本操作的定義〉 }ADT抽象數(shù)據(jù)類型名第二十六頁，共42頁數(shù)據(jù)結(jié)構(gòu)與數(shù)據(jù)庫全文共42頁，當(dāng)前為第26頁。其中,數(shù)據(jù)對(duì)象、數(shù)據(jù)關(guān)系用偽碼描述；基本操作定義格式為 基本操作名（參數(shù)表） 初始條件：〈初始條件描述〉

操作結(jié)果：〈操作結(jié)果描述〉基本操作有兩種參數(shù)：賦值參數(shù)只為操作提供輸入值；引用參數(shù)以&打頭，除可提供輸入值外，還將返回操作結(jié)果。“初始條件”描述了操作執(zhí)行之前數(shù)據(jù)結(jié)構(gòu)和參數(shù)應(yīng)滿足的條件，若不滿足，則操作失敗，并返回相應(yīng)出錯(cuò)信息?！安僮鹘Y(jié)果”說明了操作正常完成之后，數(shù)據(jù)結(jié)構(gòu)的變化狀況和應(yīng)返回的結(jié)果。若初始條件為空，則省略之。第二十七頁，共42頁數(shù)據(jù)結(jié)構(gòu)與數(shù)據(jù)庫全文共42頁，當(dāng)前為第27頁。抽象數(shù)據(jù)類型的表示和實(shí)現(xiàn)

抽象數(shù)據(jù)類型可以通過固有數(shù)據(jù)類型(高級(jí)編程語言中已實(shí)現(xiàn)的數(shù)據(jù)類型)來實(shí)現(xiàn)抽象數(shù)據(jù)類型類class數(shù)據(jù)對(duì)象數(shù)據(jù)成員基本操作成員函數(shù)(方法)在C++中，類的成分(數(shù)據(jù)成員和成員函數(shù))可以有三種訪問級(jí)別Private私有成分（只允許類的成員函數(shù)進(jìn)行訪問）

protected保護(hù)成分（只允許類的成員函數(shù)及其子孫類進(jìn)行訪問）public公有成分（允許類的成員函數(shù)、類的實(shí)例及其子孫類、子孫類的實(shí)例進(jìn)行訪問）第二十八頁，共42頁數(shù)據(jù)結(jié)構(gòu)與數(shù)據(jù)庫全文共42頁，當(dāng)前為第28頁。算法和算法分析定義：為了解決某類問題而規(guī)定的一個(gè)有限長(zhǎng)的操作序列。特性：有窮性算法在執(zhí)行有窮步后能結(jié)束確定性每步定義都是確切、無歧義可行性每一條運(yùn)算應(yīng)足夠基本輸入有0個(gè)或多個(gè)輸入輸出有一個(gè)或多個(gè)輸出第二十九頁，共42頁數(shù)據(jù)結(jié)構(gòu)與數(shù)據(jù)庫全文共42頁，當(dāng)前為第29頁。算法設(shè)計(jì)例子：

選擇排序問題：遞增排序解決方案：逐個(gè)選擇最小數(shù)據(jù)算法框架：

for(inti=0;i<n-1;i++){

//n-1趟 從a[i]檢查到a[n-1];

若最小整數(shù)在a[k],交換a[i]與a[k];}細(xì)化：SelectSort第三十頁，共42頁數(shù)據(jù)結(jié)構(gòu)與數(shù)據(jù)庫全文共42頁，當(dāng)前為第30頁。voidselectSort(inta[],intn){

//對(duì)n個(gè)整數(shù)a[0],a[1],…,a[n-1]按遞增順序排序

for(inti=0;i<n-1;i++){ intk=i;

for(intj=i+1;j<n;j++)

if(a[j]<a[k])k=j;//從a[i]查到a[n-1],找最小整數(shù),在a[k]

inttemp=a[i];a[i]=a[k];a[k]=temp;}}

第三十一頁，共42頁數(shù)據(jù)結(jié)構(gòu)與數(shù)據(jù)庫全文共42頁，當(dāng)前為第31頁。性能分析與度量算法的性能標(biāo)準(zhǔn)正確性可讀性健壯性效率（時(shí)間、空間）第三十二頁，共42頁數(shù)據(jù)結(jié)構(gòu)與數(shù)據(jù)庫全文共42頁，當(dāng)前為第32頁。算法的事后統(tǒng)計(jì)（后期測(cè)試）在算法中的某些部位插裝時(shí)間函數(shù)time

(),

測(cè)定算法完成某一功能所花費(fèi)時(shí)間

doublestart,stop;

time(&start);

intk=seqsearch(a,n,x);

time(&stop);

doublerunTime=stop-start;printf(”%d%d\n",n,runTime);第三十三頁，共42頁數(shù)據(jù)結(jié)構(gòu)與數(shù)據(jù)庫全文共42頁，當(dāng)前為第33頁。intseqsearch(inta[],intn,intx){//在a[0],…,a[n-1]中搜索x

inti=0;

while(i<n&&a[i]!=x)

i++;

if(i==n)return

-1;

returni;}

第三十四頁，共42頁數(shù)據(jù)結(jié)構(gòu)與數(shù)據(jù)庫全文共42頁，當(dāng)前為第34頁。算法的事前估計(jì)時(shí)間復(fù)雜度度量運(yùn)行時(shí)間=算法中每條語句執(zhí)行時(shí)間之和。每條語句執(zhí)行時(shí)間=該語句的執(zhí)行次數(shù)（頻度）*語句執(zhí)行一次所需時(shí)間。語句執(zhí)行一次所需時(shí)間取決于機(jī)器的指令性能和速度和編譯所產(chǎn)生的代碼質(zhì)量，很難確定。設(shè)每條語句執(zhí)行一次所需時(shí)間為單位時(shí)間，則一個(gè)算法的運(yùn)行時(shí)間就是該算法中所有語句的頻度之和。第三十五頁，共42頁數(shù)據(jù)結(jié)構(gòu)與數(shù)據(jù)庫全文共42頁，當(dāng)前為第35頁。舉例1矩陣相乘算法

for(i=1;i<=n;++i)//n+1for(j=1;j<=n;++j){//n(n+1)c[i][j]=0;//n2for(k=1;k<=n;++k)//n2(n+1)c[i][j]+=a[i][k]*b[k][j];//n3}

則算法執(zhí)行時(shí)間T(n)為所有語句的頻度之和。

T(n)=n+1+n(n+1)+…+n3

=2n3

+3n2+2n+1第三十六頁，共42頁數(shù)據(jù)結(jié)構(gòu)與數(shù)據(jù)庫全文共42頁，當(dāng)前為第36頁。漸進(jìn)時(shí)間復(fù)雜度

引入“O”記號(hào)，以體現(xiàn)隨問題規(guī)模n的增長(zhǎng)率。

T(n)=n+1+n(n+1)+…+n3

=2n3

+3n2+2n+1＝O(n3)，其中n3

為增長(zhǎng)最快的項(xiàng)。最壞時(shí)間復(fù)雜度vs.平均時(shí)間復(fù)雜度

有時(shí)算法基本操作重復(fù)執(zhí)行次數(shù)還隨問題的輸入數(shù)據(jù)集不同而不同（如一些排序算法）。這時(shí)可分析最壞時(shí)間復(fù)雜度（最壞情況下的時(shí)間復(fù)雜度）和平均時(shí)間復(fù)雜度（平均情況下的時(shí)間復(fù)雜度）第三十七頁，共42頁數(shù)據(jù)結(jié)構(gòu)與數(shù)據(jù)庫全文共42頁，當(dāng)前為第37頁。

估計(jì)算法時(shí)間的通常做法：

根據(jù)問題（或算法類型），從算法中選取一種原操作（指固有數(shù)據(jù)類型的操作）作為基本操作。其重復(fù)執(zhí)行次數(shù)應(yīng)與算法執(zhí)行時(shí)間成正比；一般為最深層循環(huán)內(nèi)的語句中的原操作；用該基本操作重復(fù)執(zhí)行的次數(shù)作為算法的時(shí)間度量。即統(tǒng)計(jì)包含該操作的所有語句的頻度之和。如：上例中選取乘法為基本操作；算法執(zhí)行時(shí)間T(n)則正比于乘法所在語句的頻度n3,記為T