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

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

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

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

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

？第十頁，共42頁數(shù)據(jù)結(jié)構(gòu)與數(shù)據(jù)庫全文共42頁，當前為第10頁?；靖拍詈托g語數(shù)據(jù)(Data)是信息的載體，是描述客觀事物的數(shù)、字符、以及所有能輸入到計算機中，被計算機程序識別和處理的符號的集合。

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

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

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

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

Data_Structure={D,S}

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

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

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

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

可記作

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

//對n個整數(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頁，當前為第31頁。性能分析與度量算法的性能標準正確性可讀性健壯性效率（時間、空間）第三十二頁，共42頁數(shù)據(jù)結(jié)構(gòu)與數(shù)據(jù)庫全文共42頁，當前為第32頁。算法的事后統(tǒng)計（后期測試）在算法中的某些部位插裝時間函數(shù)time

(),

測定算法完成某一功能所花費時間

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頁，當前為第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頁，當前為第34頁。算法的事前估計時間復雜度度量運行時間=算法中每條語句執(zhí)行時間之和。每條語句執(zhí)行時間=該語句的執(zhí)行次數(shù)（頻度）*語句執(zhí)行一次所需時間。語句執(zhí)行一次所需時間取決于機器的指令性能和速度和編譯所產(chǎn)生的代碼質(zhì)量，很難確定。設每條語句執(zhí)行一次所需時間為單位時間，則一個算法的運行時間就是該算法中所有語句的頻度之和。第三十五頁，共42頁數(shù)據(jù)結(jié)構(gòu)與數(shù)據(jù)庫全文共42頁，當前為第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í)行時間T(n)為所有語句的頻度之和。

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

=2n3

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

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

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

=2n3

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

為增長最快的項。最壞時間復雜度vs.平均時間復雜度

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

估計算法時間的通常做法：

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