【2012四川大學(xué)-數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計(jì)】第1講-緒論

緒論

數(shù)據(jù)結(jié)構(gòu)與算法分析

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

NiklausWirth

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

處理問題的策略問題的數(shù)學(xué)模型“學(xué)生”表格UNIX文件系統(tǒng)的系統(tǒng)結(jié)構(gòu)圖/(root)binlibuseretcmathdsswyintaoxieStack.cppQueue.cppTree.cpp“課程”表格

“選課單”包含如下信息

學(xué)號(hào)課程編號(hào)成績(jī)時(shí)間

學(xué)生選課系統(tǒng)中實(shí)體構(gòu)成的網(wǎng)狀關(guān)系學(xué)生(學(xué)號(hào),姓名,性別,籍貫)課程(課程號(hào),課程名,學(xué)分)選課(學(xué)號(hào),課程號(hào),成績(jī))數(shù)據(jù)結(jié)構(gòu)的特點(diǎn)

綜上三個(gè)例子可見，描述這類非數(shù)值計(jì)算問題的數(shù)學(xué)模型不再是數(shù)學(xué)方程，而是諸如表、樹和圖之類的數(shù)據(jù)結(jié)構(gòu).因此簡(jiǎn)單說來，數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計(jì)算的程序設(shè)計(jì)問題中計(jì)算機(jī)的操作對(duì)象以及它們之間的關(guān)系和操作等等的學(xué)科.數(shù)據(jù)〔data〕數(shù)據(jù)是信息的載體，是描述客觀事物的數(shù)、字符、以及所有能輸入到計(jì)算機(jī)中，被計(jì)算機(jī)程序識(shí)別和處理的符號(hào)的集合數(shù)值性數(shù)據(jù)非數(shù)值性數(shù)據(jù)數(shù)據(jù)元素(dataelement)數(shù)據(jù)的根本單位。在計(jì)算機(jī)程序中常作為一個(gè)整體進(jìn)行考慮和處理有時(shí)一個(gè)數(shù)據(jù)元素可以由假設(shè)干數(shù)據(jù)項(xiàng)(DataItem)組成。數(shù)據(jù)項(xiàng)是具有獨(dú)立含義的最小標(biāo)識(shí)單位數(shù)據(jù)元素又稱為元素、結(jié)點(diǎn)、記錄數(shù)據(jù)對(duì)象(dataobject)數(shù)據(jù)的子集。具有相同性質(zhì)的數(shù)據(jù)成員〔數(shù)據(jù)元素〕的集合整數(shù)數(shù)據(jù)對(duì)象N={0,1,2,…}學(xué)生數(shù)據(jù)對(duì)象什么是數(shù)據(jù)結(jié)構(gòu)定義:由某一數(shù)據(jù)對(duì)象及該對(duì)象中所有數(shù)據(jù)成員之間的關(guān)系組成記為：Data_Structure={D,S}

其中，D

是某一數(shù)據(jù)對(duì)象，S是該對(duì)象中所有數(shù)據(jù)成員之間的關(guān)系的有限集合數(shù)據(jù)結(jié)構(gòu)是數(shù)據(jù)的組織形式數(shù)據(jù)元素間的邏輯關(guān)系，即數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)元素及其關(guān)系在計(jì)算機(jī)存儲(chǔ)內(nèi)的表示，即數(shù)據(jù)的存儲(chǔ)表示(結(jié)構(gòu))數(shù)據(jù)的運(yùn)算，即對(duì)數(shù)據(jù)元素施加的操作數(shù)據(jù)類型的構(gòu)成結(jié)構(gòu)算法數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)從邏輯關(guān)系上描述數(shù)據(jù)，與數(shù)據(jù)的存儲(chǔ)無關(guān)數(shù)據(jù)的邏輯結(jié)構(gòu)可以看作是從具體問題抽象出來的數(shù)據(jù)模型數(shù)據(jù)的邏輯結(jié)構(gòu)與數(shù)據(jù)元素本身的形式、內(nèi)容無關(guān)數(shù)據(jù)的邏輯結(jié)構(gòu)與數(shù)據(jù)元素的相對(duì)位置無關(guān)數(shù)據(jù)的邏輯結(jié)構(gòu)分類線性結(jié)構(gòu)線性表,堆棧,隊(duì)列,串非線性結(jié)構(gòu)樹,二叉樹圖〔或網(wǎng)絡(luò)〕,廣義表數(shù)據(jù)的邏輯結(jié)構(gòu)可歸結(jié)為以下四類線性結(jié)構(gòu)樹形結(jié)構(gòu)圖狀結(jié)構(gòu)集合結(jié)構(gòu)數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是邏輯結(jié)構(gòu)用計(jì)算機(jī)語言的實(shí)現(xiàn)數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)依賴于計(jì)算機(jī)語言順序存儲(chǔ)表示鏈接存儲(chǔ)表示順序存貯〔向量存貯〕所有元素存放在一片連續(xù)的存貯單元中，邏輯上相鄰的元素存放到計(jì)算機(jī)內(nèi)存仍然相鄰

鏈?zhǔn)酱尜A

所有元素存放在可以不連續(xù)的存貯單元中，但元素之間的關(guān)系可以通過地址確定，邏輯上相鄰的元素存放到計(jì)算機(jī)內(nèi)存后不一定是相鄰的數(shù)據(jù)類型數(shù)據(jù)類型

定義：一組性質(zhì)相同的值的集合,以及定義于這個(gè)值集合上的一組操作的總稱C語言中的數(shù)據(jù)類型

charintfloatdoublevoid

字符型整型浮點(diǎn)型雙精度型無值

構(gòu)造數(shù)據(jù)類型由不同成分類型構(gòu)成根本數(shù)據(jù)類型可以看作是計(jì)算機(jī)中已實(shí)現(xiàn)的數(shù)據(jù)結(jié)構(gòu)抽象數(shù)據(jù)類型

(ADTs:AbstractDataTypes)由用戶定義，用以表示應(yīng)用問題的數(shù)據(jù)模型由根本的數(shù)據(jù)類型組成,并包括一組相關(guān)的效勞〔或稱操作〕信息隱蔽和數(shù)據(jù)封裝，使用與實(shí)現(xiàn)相別離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é)抽象數(shù)據(jù)類型的描述方法抽象數(shù)據(jù)類型從形式上可用〔D，R，O〕三元組表示其中：D是數(shù)據(jù)對(duì)象R是D上的關(guān)系集O是對(duì)D的根本操作集一般采用如下格式描述ADT抽象數(shù)據(jù)類型名{數(shù)據(jù)對(duì)象：〈數(shù)據(jù)對(duì)象的定義〉數(shù)據(jù)關(guān)系：〈數(shù)據(jù)關(guān)系的定義〉根本操作：〈根本操作的定義〉}ADT抽象數(shù)據(jù)類型名根本操作的定義格式根本操作名〔參數(shù)表〕初始條件：〈初始條件描述〉操作結(jié)果：〈操作結(jié)果描述〉賦值參數(shù)只為操作提供輸入值引用參數(shù)以&打頭，除可提供輸入值外，還將返回操作結(jié)果初始條件描述了操作執(zhí)行之前數(shù)據(jù)結(jié)構(gòu)和參數(shù)應(yīng)滿足的條件，假設(shè)不滿足，那么操作失敗，并返回相應(yīng)出錯(cuò)信息操作結(jié)果說明了操作正常完成之后，數(shù)據(jù)結(jié)構(gòu)的變化狀況和應(yīng)返回的結(jié)果。假設(shè)初始條件為空,那么省略之抽象數(shù)據(jù)類型的表示和實(shí)現(xiàn)

抽象數(shù)據(jù)類型需要通過固有數(shù)據(jù)類型(高級(jí)編程語言中已實(shí)現(xiàn)的數(shù)據(jù)類型)來實(shí)現(xiàn)例如，抽象數(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{根本操作：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í)部值

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的和值

}ADTComplex算法

算法是為了解決某類問題而規(guī)定的一個(gè)有限長(zhǎng)的操作序列算法定義算法特性有窮性確定性可行性有輸入有輸出有窮性

對(duì)于任意一組合法輸入值，在執(zhí)行有窮步驟之后一定能結(jié)束，即：算法中的每個(gè)步驟都能在有限時(shí)間內(nèi)完成確定性對(duì)于每種情況下所應(yīng)執(zhí)行的操作，在算法中都有確切的規(guī)定，使算法的執(zhí)行者或閱讀者都能明確其含義及如何執(zhí)行。并且在任何條件下，算法都只有一條執(zhí)行路徑可行性算法中的所有操作都必須足夠根本，都可以通過已經(jīng)實(shí)現(xiàn)的根本操作運(yùn)算有限次實(shí)現(xiàn)之有輸入作為算法加工對(duì)象的量值，通常表達(dá)為算法中的一組變量。有些輸入量需要在算法執(zhí)行過程中輸入，而有的算法外表上可以沒有輸入，實(shí)際上已被嵌入算法之中有輸出

它是一組與“輸入”有確定關(guān)系的量值，是算法進(jìn)行信息加工后得到的結(jié)果，這種確定關(guān)系即為算法的功能算法描述方法

用自然語言描述算法用我們?nèi)粘Ｉ钪械淖匀徽Z言〔可以是中文形式，也可以是英文形式〕也可以描述算法用流程圖描述算法

一個(gè)算法可以用流程圖的方式來描述，輸入輸出、判斷、處理分別用不同的框圖表示，用箭頭表示流程的流向。這是一種描述算法的較好方法，目前在一些高級(jí)語言程序設(shè)計(jì)中仍然采用。也有其他的圖形輔助工具用其它方式描述算法

我們還可以用數(shù)學(xué)語言或約定的符號(hào)語言來描述算法

用C++描述算法

在本課中，我們將采用類C++來描述算法,所有算法的描述都用C＋＋中的函數(shù)形式算法和程序的關(guān)系算法著重表達(dá)思路和方法，程序著重表達(dá)計(jì)算機(jī)的實(shí)現(xiàn)程序不一定滿足有窮性〔死循環(huán)〕，另外，程序中的指令必須是機(jī)器可執(zhí)行的，算法中的指令無此限制一個(gè)算法假設(shè)用計(jì)算機(jī)語言來書寫，它就可以是一個(gè)程序算法設(shè)計(jì)原那么正確性閱讀性健壯性算法評(píng)價(jià)標(biāo)準(zhǔn)時(shí)間特性(時(shí)間復(fù)雜度T(n)

)空間特性(空間復(fù)雜度S(n)

)一個(gè)特定算法的“運(yùn)行工作量”的大小，只依賴于問題的規(guī)?！餐ǔＳ谜麛?shù)量n表示〕，或者說，它是問題規(guī)模的函數(shù)。假設(shè)，隨著問題規(guī)模n的增長(zhǎng)，算法執(zhí)行時(shí)間的增長(zhǎng)率和f(n)的增長(zhǎng)率相同，那么可記作：T(n)=O(f(n))稱T(n)為算法的(漸近)時(shí)間復(fù)雜度。如何估算算法的時(shí)間復(fù)雜度？算法=控制結(jié)構(gòu)+原操作〔固有數(shù)據(jù)類型的操作〕算法的執(zhí)行時(shí)間

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

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

與

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

成正比

從算法中選取一種對(duì)于所研究的問題來說是根本操作的原操作，以該根本操作在算法中重復(fù)執(zhí)行的次數(shù)作為算法運(yùn)行時(shí)間的衡量準(zhǔn)那么。例一兩個(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)例二選擇排序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]}例三起泡排序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;}}//一趟起泡四、算法的存儲(chǔ)空間需求算法的空間復(fù)雜度定義為:

表示隨著問題規(guī)模n的增大，算法運(yùn)行所需存儲(chǔ)量的增長(zhǎng)率與g(n)的增長(zhǎng)率相同。S(n)=O(g(n))面向?qū)ο蟮母拍蠲嫦驅(qū)ο?對(duì)象＋類＋繼承＋通信對(duì)象由一組屬性值和在這組值上的一組效勞〔或稱操作〕構(gòu)成類(class)，實(shí)例(instance)具有相同屬性和效勞的對(duì)象歸于同一類，形成類類中的對(duì)象為該類的實(shí)例繼承

派生類：四邊形，三角形，…

子類特化類(特殊化類)

基類：多邊形

父類泛化類(一般化