1第一頁，共七十二頁，編輯于2023年，星期三什么是數據結構抽象數據類型及面向對象概念算法定義模板算法簡單性能分析與度量第一章數據結構概念第二頁，共七十二頁，編輯于2023年，星期三“學生”表格第三頁，共七十二頁，編輯于2023年，星期三“課程”表格第四頁，共七十二頁，編輯于2023年，星期三學生(學號,姓名,性別,籍貫)課程(課程號,課程名,學分)選課(學號,課程號,成績)

“選課單”包含如下信息

學號課程編號成績時間

學生選課系統中實體構成的網狀關系第五頁，共七十二頁，編輯于2023年，星期三UNIX文件系統的系統結構圖/(root)binlibuseretcmathdsswyintaoxieStack.cppQueue.cppTree.cpp第六頁，共七十二頁，編輯于2023年，星期三數據（data）數據是信息的載體，是描述客觀事物的數、字符、以及所有能輸入到計算機中，被計算機程序識別和處理的符號的集合。數據的分類：數值性數據非數值性數據第七頁，共七十二頁，編輯于2023年，星期三姓名所在院系性別出生日期年月職務業績數據元素(dataelement)數據的基本單位。在計算機程序中常作為一個整體進行考慮和處理。有時一個數據元素可以由若干數據項(DataItem)組成。數據項是具有獨立含義的最小標識單位。數據元素又稱為元素、結點、記錄。第八頁，共七十二頁，編輯于2023年，星期三什么是數據結構定義:由某一數據元素的集合以及該集合中所有數據元素之間的關系組成。記為：Data_Structure={D,R}其中，D是某一數據元素的集合，R是該集合中所有數據元素之間的關系的有限集合。第九頁，共七十二頁，編輯于2023年，星期三例：N個網點之間的連通關系

樹形關系網狀關系156152436243第十頁，共七十二頁，編輯于2023年，星期三數據結構是數據的組織形式包括三個方面：數據元素間的邏輯關系，即數據的邏輯結構；數據元素及其關系在計算機存儲內的表示，即數據的存儲表示；數據的運算，即對數據元素施加的操作。第十一頁，共七十二頁，編輯于2023年，星期三數據的邏輯結構數據的邏輯結構從邏輯關系上描述數據，與數據的存儲無關；數據的邏輯結構可以看作是從具體問題抽象出來的數據模型；數據的邏輯結構與數據元素本身的形式、內容無關；數據的邏輯結構與數據元素的相對存儲位置無關。第十二頁，共七十二頁，編輯于2023年，星期三數據的邏輯結構分類線性結構

線性表非線性結構

樹圖（或網絡）第十三頁，共七十二頁，編輯于2023年，星期三線性結構樹形結構樹二叉樹二叉搜索樹bindevetclibuser14131211234567891031587101199874566231311第十四頁，共七十二頁，編輯于2023年，星期三堆結構

“最大”堆“最小”堆123548711102916410121151236987第十五頁，共七十二頁，編輯于2023年，星期三圖結構網絡結構12543611331814665161921125634第十六頁，共七十二頁，編輯于2023年，星期三數據的存儲結構數據的存儲結構是邏輯結構用計算機語言的實現；數據的存儲結構依賴于計算機語言。順序存儲表示鏈接存儲表示索引存儲表示散列存儲表示主要用于內存的存儲表示主要用于外存(文件)的存儲表示第十七頁，共七十二頁，編輯于2023年，星期三抽象數據類型及面向對象概念數據類型

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

charintfloatdoublevoid

字符型整型浮點型雙精度型無值第十八頁，共七十二頁，編輯于2023年，星期三構造數據類型由基本數據類型或構造數據類型組成。構造數據類型由不同成分類型構成。基本數據類型可以看作是計算機中已實現的數據結構。數據類型就是數據結構，不過它是從編程者的角度來使用的。數據類型是模板，必須定義屬于某種數據類型的變量，才能參加運算。第十九頁，共七十二頁，編輯于2023年，星期三抽象數據類型

(ADTs:AbstractDataTypes)抽象數據類型是由用戶定義，用以表示應用問題的數據模型。特點是：信息隱蔽和數據封裝，使用與實現相分離。抽象數據類型可用（D,S,P）三元組表示，其中，D是數據元素的集合（簡稱數據對象），S是D上的關系集合，P是對D的基本操作集合。

第二十頁，共七十二頁，編輯于2023年，星期三抽象數據類型查找登錄刪除修改

符號表第二十一頁，共七十二頁，編輯于2023年，星期三抽象數據類型的描述其中數據對象、數據之間的關系用偽碼描述；基本操作定義格式為ADT抽象數據類型名{ 數據對象：〈數據對象的定義〉 數據關系：〈數據關系的定義〉 基本操作：〈基本操作的定義〉}ADT抽象數據類型名基本操作名（參數表）前置條件：〈先決條件描述〉后置條件：〈操作結果描述〉第二十二頁，共七十二頁，編輯于2023年，星期三基本操作有兩種參數：賦值參數只為操作提供輸入值；引用參數以&打頭，除可提供輸入值外，還將返回操作結果。“前置條件”描述了操作執行之前數據結構和參數應滿足的先決條件，若不滿足，則操作失敗，并返回相應出錯信息。“后置條件”說明了操作正常完成之后，數據結構的變化狀況和應返回的結果。若前置條件為空，則省略之。第二十三頁，共七十二頁，編輯于2023年，星期三自然數的抽象數據類型定義ADT

NaturalNumberisobjects:一個整數的有序子集合,它開始于0,結束于機器能表示的最大整數(MaxInt)。Function:對于所有的x,y

NaturalNumber;

False,TrueBoolean,+、-、<、==、=等都是可用的服務。

Zero():NaturalNumber

//前置條件：無//后置條件：返回自然數0

第二十四頁，共七十二頁，編輯于2023年，星期三

IsZero(x):Boolean

//前置條件：x為NaturalNumber

//后置條件：if(x==0)then返回True

else返回FalseAdd(x,y):NaturalNumber

//前置條件：x,y為NaturalNumber且x+y≤MaxInt

//后置條件：返回x+ySubtract(x,y):NaturalNumber

//前置條件：x,y為NaturalNumber且x≥y

//后置條件：返回

x-y

第二十五頁，共七十二頁，編輯于2023年，星期三

Equal(x,y):Boolean

//前置條件：x,y為NaturalNumber

//后置條件：

if(x==y)返回Trueelse返回FalseSuccessor(x):NaturalNumber

//前置條件：x為NaturalNumber

//后置條件：if(x==MaxInt)

返回xelse返回x+1end

NaturalNumber第二十六頁，共七十二頁，編輯于2023年，星期三面向對象的概念面向對象=對象＋類＋繼承＋通信對象在應用問題中出現的各種實體、事件、規格說明等。由一組屬性值和在這組值上的一組服務（或稱操作）構成。與C中構造數據類型不同在于：C中的構造數據類型的變量僅涉及屬性值，與操作分離，而C++中的對象則不然。第二十七頁，共七十二頁，編輯于2023年，星期三類(class)，實例(instance)具有相同屬性和服務的對象歸于同一類，形成類。類中的對象為該類的實例。同一類的實例共享類的屬性和類的操作；通過繼承共享其父類的公共的和保護性的屬性和操作；同一類的不同實例有不同的屬性值。第二十八頁，共七十二頁，編輯于2023年，星期三四邊形類及其對象屬性aPoint1aPoint2aPoint3aPoint4服務Draw()move(x,y)contains(aPoint)屬性值屬性值quadrilateral1quadrilateral2(35,10)(50,10)(35,25)(50,25)(45,65)(50,45)(65,66)(60,70)Draw()move(x,y)contains(aPoint)Draw()move(x,y)contains(aPoint)服務服務quadrilateral第二十九頁，共七十二頁，編輯于2023年，星期三繼承派生類（子類）：四邊形，三角形，…基類（父類）：多邊形派生類繼承的特性+特有的特性基類多邊形四邊形三角形六邊形第三十頁，共七十二頁，編輯于2023年，星期三通信消息傳遞C++中消息傳遞的方式：定義：Pointp;voidmove(intΔx,intΔy);使用：p.move(x,y);C中則不同，需使用函數調用方式：定義：Pointp;voidmove(Pointq,intΔx,intΔy);使用：move(p,x,y);

第三十一頁，共七十二頁，編輯于2023年，星期三Draw()move(x,y)contains(aPoint)PolygonreferencePointVerticesPolygon類referencePointVerticesDraw()move(x,y)contains(aPoint)Polygon的子類Quadrilateral類Quadrilateral第三十二頁，共七十二頁，編輯于2023年，星期三算法定義定義：一個有窮的指令集，這些指令為解決某一特定任務規定了一個運算序列特性：輸入有0個或多個輸入輸出有一個或多個輸出(處理結果)確定性每步定義都是確切無歧義的有窮性算法應在執行有窮步后結束有效性每一條運算應足夠基本第三十三頁，共七十二頁，編輯于2023年，星期三事例學習：選擇排序問題明確問題：遞增排序解決方案：逐個選擇最小數據算法框架：

for(inti=0;i<n-1;i++){//n-1趟 從a[i]檢查到a[n-1];

若最小整數在a[k],交換a[i]與a[k];}細化程序：程序SelectSort算法設計

自頂向下，逐步求精

第三十四頁，共七十二頁，編輯于2023年，星期三

voidselectSort(inta[],constintn){

//對n個整數a[0],a[1],…,a[n-1]按遞增順序排序for(inti=0;i<n-1;i++){

intk=i;

//從a[i]查到a[n-1],找最小整數,在a[k]

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

if(a[j]<a[k])k=j;

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

第三十五頁，共七十二頁，編輯于2023年，星期三模板(template)定義

適合多種數據類型的類定義或算法，在特定環境下通過簡單地代換，變成針對具體某種數據類型的類定義或算法。第三十六頁，共七十二頁，編輯于2023年，星期三用模板定義用于排序的數據表類#ifndefDATALIST_H#defineDATALIST_H#include<iostream.h>//K是表項關鍵碼類型template<classK,classE> //E是表項類型classdataList{ private:E*element; intlistSize; voidswap(intm1,intm2);intminKey

(intlow,inthigh);第三十七頁，共七十二頁，編輯于2023年，星期三

public:dataList

(intsize=10):listSize(size),element(new

E[size]){}~dataList(){delete[]element;} voidsort();friendostream&operator<<(ostream&

outStream,dataList<K,E>&outList);friendistream&operator>>(istream&

inStream,dataList<K,E>&inList);};

#endif第三十八頁，共七十二頁，編輯于2023年，星期三類中所有操作作為模板函數的實現template<classK,classE>voiddataList

<K,E>::swap

(intm1,intm2){

//交換由m1,m2為下標的數組元素的值Etemp=element

[m1];

element

[m1]=element

[m2];

element[m2]=temp;};第三十九頁，共七十二頁，編輯于2023年，星期三template<classK,classE>intdataList<K,E>::minKey

(intlow,inthigh){//查找數組Element[low]到Element[high]中具//有最小關鍵碼值的表項，函數返回其位置intmin=low;for(inti=low+1,i<=high,i++) if(element[i]<element[min]) min=i; returnmin;};定義的重載操作第四十頁，共七十二頁，編輯于2023年，星期三template<classK,classE>ostream&operator<<(ostream&outStream,

dataList<K,E>outList){outStream<<“輸出數組內容:\n”;for(inti=0;i<outList.listSize;i++)

outStream<<outList.element[i];

outStream<<endl;ouStream<<“輸出數組當前大小:”<<

outList.listSize<<endl;returnoutStream;}

第四十一頁，共七十二頁，編輯于2023年，星期三

template<classK,classE>istream&

operator>>(istream&inStream,

dataList<K,E>inList){//輸入對象為inList，輸入流對象為inStream

cout<<“輸入數組當前大小:”;

instream>>inList.listSize; cout<<“輸入數組元素值:\n”; for(inti=0;i<inList.listSize;i++){

cout

<<“元素”<<i<<“:”;

inStream>>inList.element[i];}returninStream;}第四十二頁，共七十二頁，編輯于2023年，星期三template<classK,classE>voiddataList<K,E>::sort(){//按非遞減順序對listSize個關鍵碼element[0]到//element[ArraySize-1]排序for(inti=0;i<=listSize-2;i++){intj=minKey(i,listSize-1);if(j!=i)swap(j,i);}}#endif第四十三頁，共七十二頁，編輯于2023年，星期三使用模板的選擇排序算法的主函數

#include<iostream.h>

#include“dataList.h”constintSZ=10;intmain(){

structsick{

//患者

intkey;

char*name[15];intage;

char*address[30];

booloperator<(sick

x){returnkey<x.key;}

};

第四十四頁，共七十二頁，編輯于2023年，星期三dataList<int,sick>TestList(SZ);

cin

>>TestList;

cout

<<TestList<<endl;TestList.Sort();

cout

<<TestList<<endl;

return0;}

定義對象時，代入實際數據類型重載友元操作標準I／O操作消息通信第四十五頁，共七十二頁，編輯于2023年，星期三算法簡單性能分析與度量算法的性能標準算法的后期測試算法的事前估計第四十六頁，共七十二頁，編輯于2023年，星期三算法的性能標準正確性(Correctness)

算法應滿足具體問題的需求。可讀性(Readability)

算法應該容易閱讀。以有利于閱讀者對程序的理解。效率效率指的是算法執行的時間和空間利用率。通常這兩者與問題的規模有關。健壯性(Robustness)

算法應具有容錯處理的功能。當輸入非法數據時，算法應對其作出反應，而不應產生莫名其妙的輸出結果。第四十七頁，共七十二頁，編輯于2023年，星期三算法的后期測試對一個算法要作出全面的分析可分成兩個階段進行，即事前分析和事后測試事前分析要求事前求出該算法的一個時間界限函數。事后測試則要求在算法執行后通過算法執行的時間和實際占用空間的統計資料來分析。事后分析要求在算法中的某些部位插裝時間函數

time

()，測定算法完成某一功能所花費時間。第四十八頁，共七十二頁，編輯于2023年，星期三例如，給出順序搜索(SequenialSearch)算法intseqsearch(inta[],intn,intx){//在a[0],…,a[n-1]中搜索與給定值x相等的元//素，函數返回其位置，失敗返回-1。

inti=0;

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

i++;

if(i==n)return

-1;

returni;}

第四十九頁，共七十二頁，編輯于2023年，星期三

插裝time()的計時程序

doublestart,stop;time(&start);

intk=seqsearch(a,n,x);time(&stop);

doublerunTime=stop-start;

cout<<""<<n<<""<<runTime<<endl;事實上，算法運行時間要受輸入規模、利用編譯程序生成的目標代碼的質量、計算機程序指令系統的品質和速度等制約。第五十頁，共七十二頁，編輯于2023年，星期三算法的事前估計算法的事前估計主要包括時間復雜性和空間復雜性的分析：問題的規模：如：矩陣的階數、圖的結點個數、被分類序列的正整數個數等。時間復雜性：算法所需時間和問題規模的函數，記為T(n)。當n

時的時間復雜性，稱為漸進時間復雜性。空間復雜性：算法所需空間和問題規模的函數。記為S(n)。當n時的時間復雜性，稱為漸進空間復雜性。第五十一頁，共七十二頁，編輯于2023年，星期三空間復雜度度量存儲空間的固定部分

程序指令代碼的空間，常數、簡單變量、定長成分(如數組元素、結構成分、對象的數據成員等)變量所占空間可變部分

尺寸與實例特性有關的成分變量所占空間、引用變量所占空間、遞歸棧所用空間、通過new和delete命令動態使用空間第五十二頁，共七十二頁，編輯于2023年，星期三時間復雜度度量編譯時間運行時間程序步語法上或語義上有意義的一段指令序列；執行時間與問題規模無關；例如：聲明語句：程序步數為0;表達式：程序步數為1第五十三頁，共七十二頁，編輯于2023年，星期三程序步確定方法插入計數全局變量count建表，列出個語句的程序步例以迭代方式求累加和的函數floatsum(floata[],intn){

floats=0.0;

for(inti=0;i<n;i++)s=s+a[i];

returns;}第五十四頁，共七十二頁，編輯于2023年，星期三在求累加和程序中加入count語句floatsum(floata[],intn){float

s=0.0;count++; //count統計執行語句條數

for(inti=0;i<n;i++){count+=2;//針對for語句 s+=a[i]; count++;//針對賦值語句} count+=2; //針對for的最后一次count++; //針對return語句

returns;}

執行結束得程序步數count=3*n+4第五十五頁，共七十二頁，編輯于2023年，星期三程序的簡化形式

voidsum(floata[],intn){for(inti=0;i<n;i++)count+=3;count+=4;}第五十六頁，共七十二頁，編輯于2023年，星期三注意：

一個語句本身的程序步數可能不等于該語句一次執行所具有的程序步數。

例如：賦值語句x=sum(R,n)本身程序步數為1；一次執行對函數sum(R,n)的調用需要的程序步數為3*n+4；一次執行的程序步數為

1+3*n+4=3*n+5第五十七頁，共七十二頁，編輯于2023年，星期三計算累加和程序

程序步數計算工作表格第五十八頁，共七十二頁，編輯于2023年，星期三時間復雜度的漸進表示法例求兩個n階方陣的乘積C=ABvoidMatrixMultiply(intA[n][n],intB[n][n],

intC[n][n]){for(inti=0;i<n;i++)

…2n+2

for(intj=0;j<n;j++){

…n(2n+2)

C[i][j]=0;

…n2

for(intk=0;k<n;k++)

…n2(2n+2)

C[i][j]=C[i][j]+A[i][k]*B[k][j];

…n3

}}3n3+5n2+4n+2第五十九頁，共七十二頁，編輯于2023年，星期三時間復雜度的漸進表示法算法中所有語句的頻度之和是矩陣階數n的函數

T(n)=

3n3+5n2+4n+2一般地，稱n是問題的規模。則時間復雜度T(n)是問題規模n的函數。當n趨于無窮大時，把時間復雜度的數量級（階）稱為算法的漸進時間復雜度

T(n)=O(n3)─大O表示法第六十頁，共七十二頁，編輯于2023年，星期三加法規則針對并列程序段

T(n,m)=T1(n)+T2(m) =O(max(f(n),g(m)))

各種函數的增長趨勢

c<log2n<n<nlog2n<n2<n3<2n<3n<n!第六十一頁，共七十二頁，編輯于2023年，星期三T(n)=T1(n)+T2(n)+T3(n)=O(max(1,n,n2))=O(n2)變量計數for(inti=0;i<n;i++)

for(intj=0;j<n;j++)y++;T1

(n)=O(1)T2(n)=O(n)T3(n)=O(n2)x=0;y=0;for(intk=0;k<n;k++)x++;第六十二頁，共七十二頁，編輯于2023年，星期三乘法規則針對嵌套程序段

T(n,m)=T1(n)*T2(m)

=O(f(n)*g(m))

漸進的空間復雜度

S(n)=O(f(n))兩個并列循環的例子第六十三頁，共七十二頁，編輯于2023年，星期三

voidexam(floatx[][],intm,intn){floatsum[];for(inti=0;i<m;i++){//x中各行

sum[i]=0.0;//數據累加

for(intj=0;j<n;j++) sum[i]+=x[i][j];

}

for(i=0;i<m;i++)//打印各行數據和

cout<<i<<“:”<<sum[i]<<endl;}

漸進時間復雜度為O(max(m*n,m))第六十四頁，共七十二頁，編輯于2023年，星期三起泡排序voidbubbleSort(inta[],intn){

//對表a[]逐趟比較,n是表當前長度

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

for(intj=n-1;j>=i;j--)//n-i次比較

if(a[j-1]>a[j]){

inttmp=a[j-1];a[j-1]=a[j];

a[j]=tmp;

} //一趟比較}}

第六十五頁，共七十二頁，編輯于2023年，星期三漸進時間復雜度O(f(n)*g(n))=

O(n2)

BubblrSort

外層循環

n-1趟內層循環n-i

次比較第六十六頁，共七十二頁，編輯于2023年，星期三有時,算法的時間復雜度不僅依賴于問題規模n，還與輸入實例的初始排列有關。在數組A[n]

中查找給定值k

的算法：

inti=