【2012四川大學-數(shù)據(jù)結構與算法設計】第1講-緒論

緒論

數(shù)據(jù)結構與算法分析

數(shù)據(jù)結構討論的范疇

NiklausWirth

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

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

“選課單”包含如下信息

學號課程編號成績時間

學生選課系統(tǒng)中實體構成的網(wǎng)狀關系學生(學號,姓名,性別,籍貫)課程(課程號,課程名,學分)選課(學號,課程號,成績)數(shù)據(jù)結構的特點

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

其中，D

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

鏈式存貯

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

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

charintfloatdoublevoid

字符型整型浮點型雙精度型無值

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

(ADTs:AbstractDataTypes)由用戶定義，用以表示應用問題的數(shù)據(jù)模型由根本的數(shù)據(jù)類型組成,并包括一組相關的效勞〔或稱操作〕信息隱蔽和數(shù)據(jù)封裝，使用與實現(xiàn)相別離ADT有兩個重要特征數(shù)據(jù)抽象用ADT描述程序處理的實體時，強調的是其本質的特征、其所能完成的功能以及它和外部用戶的接口〔即外界使用它的方法〕數(shù)據(jù)封裝將實體的外部特性和其內部實現(xiàn)細節(jié)別離，并且對外部用戶隱藏其內部實現(xiàn)細節(jié)抽象數(shù)據(jù)類型的描述方法抽象數(shù)據(jù)類型從形式上可用〔D，R，O〕三元組表示其中：D是數(shù)據(jù)對象R是D上的關系集O是對D的根本操作集一般采用如下格式描述ADT抽象數(shù)據(jù)類型名{數(shù)據(jù)對象：〈數(shù)據(jù)對象的定義〉數(shù)據(jù)關系：〈數(shù)據(jù)關系的定義〉根本操作：〈根本操作的定義〉}ADT抽象數(shù)據(jù)類型名根本操作的定義格式根本操作名〔參數(shù)表〕初始條件：〈初始條件描述〉操作結果：〈操作結果描述〉賦值參數(shù)只為操作提供輸入值引用參數(shù)以&打頭，除可提供輸入值外，還將返回操作結果初始條件描述了操作執(zhí)行之前數(shù)據(jù)結構和參數(shù)應滿足的條件，假設不滿足，那么操作失敗，并返回相應出錯信息操作結果說明了操作正常完成之后，數(shù)據(jù)結構的變化狀況和應返回的結果。假設初始條件為空,那么省略之抽象數(shù)據(jù)類型的表示和實現(xiàn)

抽象數(shù)據(jù)類型需要通過固有數(shù)據(jù)類型(高級編程語言中已實現(xiàn)的數(shù)據(jù)類型)來實現(xiàn)例如，抽象數(shù)據(jù)類型復數(shù)的定義：數(shù)據(jù)對象：D＝{e1,e2｜e1,e2∈RealSet}數(shù)據(jù)關系：R1＝{<e1,e2>|e1是復數(shù)的實數(shù)局部|e2是復數(shù)的虛數(shù)局部}ADTComplex{根本操作：AssignComplex(&Z,v1,v2)操作結果：構造復數(shù)Z,其實部和虛局部別被賦以參數(shù)v1和v2的值

DestroyComplex(&Z)操作結果：復數(shù)Z被銷毀

GetReal(Z,&realPart)

初始條件：復數(shù)已存在

操作結果：用realPart返回復數(shù)Z的實部值

GetImag(Z,&ImagPart)初始條件：復數(shù)已存在操作結果：用ImagPart返回復數(shù)Z的虛部值

Add(z1,z2,&sum)初始條件：z1,z2是復數(shù)操作結果：用sum返回兩個復數(shù)z1,z2的和值

}ADTComplex算法

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

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

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

用自然語言描述算法用我們日常生活中的自然語言〔可以是中文形式，也可以是英文形式〕也可以描述算法用流程圖描述算法

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

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

用C++描述算法

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

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

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

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

算法的執(zhí)行時間

與

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

成正比

從算法中選取一種對于所研究的問題來說是根本操作的原操作，以該根本操作在算法中重復執(zhí)行的次數(shù)作為算法運行時間的衡量準那么。例一兩個矩陣相乘voidmult(inta[],intb[],int&c[]){

//以二維數(shù)組存儲矩陣元素，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根本操作:乘法操作時間復雜度:

O(n3)例二選擇排序voidselect_sort(int&a[],intn){

//將a中整數(shù)序列重新排列成自小至大有序的整數(shù)序列。

}//select_sort根本操作:比較(數(shù)據(jù)元素)操作時間復雜度:

O(n2)j=i;//

選擇第i個最小元素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根本操作:賦值操作時間復雜度:

O(n2){

change=FALSE;

//change為元素進行交換標志

for(j=0;j<i;++j)

if(a[j]>a[j+1])

{

a[j]←→a[j+1];

change=TRUE;}}//一趟起泡四、算法的存儲空間需求算法的空間復雜度定義為:

表示隨著問題規(guī)模n的增大，算法運行所需存儲量的增長率與g(n)的增長率相同。S(n)=O(g(n))面向對象的概念面向對象=對象＋類＋繼承＋通信對象由一組屬性值和在這組值上的一組效勞〔或稱操作〕構成類(class)，實例(instance)具有相同屬性和效勞的對象歸于同一類，形成類類中的對象為該類的實例繼承

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

子類特化類(特殊化類)

基類：多邊形

父類泛化類(一般化