上傳人：p***

認證信息

認證類型：個人認證

認證主體：歐**（實名認證）

IP屬地：廣東

IP屬地：廣東 上傳時間：2023-08-04 格式：PPTX 頁數(shù)：48 大?。?65.66KB 積分：25 舉報 版權(quán)申訴

抽象數(shù)據(jù)類型與面向?qū)ο蟾拍钍裁词菙?shù)據(jù)結(jié)構(gòu)抽象數(shù)據(jù)類型及面向?qū)ο蟾拍顢?shù)據(jù)結(jié)構(gòu)的抽象層次算法定義模板性能分析與度量“課程”表格

“選課單”包含如下信息

學(xué)號課程編號成績時間

學(xué)生選課系統(tǒng)中實體構(gòu)成的網(wǎng)狀關(guān)系學(xué)生(學(xué)號,姓名,性別,籍貫)課程(課程號,課程名,學(xué)分)選課(學(xué)號,課程號,成績)數(shù)據(jù)（data）數(shù)據(jù)是信息的載體，是描述客觀事物的數(shù)、字符、以及所有能輸入到計算機中，被計算機程序識別和處理的符號的集合。數(shù)值性數(shù)據(jù)；非數(shù)值性數(shù)據(jù)。數(shù)據(jù)元素(dataelement)數(shù)據(jù)的基本單位。在計算機程序中常作為一個整體進行考慮和處理。有時一個數(shù)據(jù)元素可以由若干數(shù)據(jù)項(DataItem)組成。數(shù)據(jù)項是具有獨立含義的最小標(biāo)識單位。數(shù)據(jù)元素又稱為元素、結(jié)點、記錄。什么是數(shù)據(jù)結(jié)構(gòu)定義:由某一數(shù)據(jù)對象及該對象中所有數(shù)據(jù)成員之間的關(guān)系組成。記為：Data_Structure={D,R}其中，D是某一數(shù)據(jù)對象，R是該對象中所有數(shù)據(jù)成員之間的關(guān)系的有限集合。N個網(wǎng)點之間的連通關(guān)系

樹形關(guān)系網(wǎng)狀關(guān)系152436152436數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)從邏輯關(guān)系上描述數(shù)據(jù)，與數(shù)據(jù)的存儲無關(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ù)元素的相對位置無關(guān)。數(shù)據(jù)的邏輯結(jié)構(gòu)分類線性結(jié)構(gòu)。線性表非線性結(jié)構(gòu)。樹圖（或網(wǎng)絡(luò)）線性結(jié)構(gòu)樹形結(jié)構(gòu)樹二叉樹二叉搜索樹1413121123456789103158710119987456623131bindevetclibuser1圖結(jié)構(gòu)網(wǎng)絡(luò)結(jié)構(gòu)12564312543611331814665161921構(gòu)造數(shù)據(jù)類型由基本數(shù)據(jù)類型或構(gòu)造數(shù)據(jù)類型組成。構(gòu)造數(shù)據(jù)類型由不同成分類型構(gòu)成?；緮?shù)據(jù)類型可以看作是計算機中已實現(xiàn)的數(shù)據(jù)結(jié)構(gòu)。數(shù)據(jù)類型就是數(shù)據(jù)結(jié)構(gòu)，不過它是從編程者的角度來使用的。數(shù)據(jù)類型是模板，必須定義屬于某種數(shù)據(jù)類型的變量，才能參加運算。抽象數(shù)據(jù)類型

(ADTs:AbstractDataTypes)由用戶定義，用以表示應(yīng)用問題的數(shù)據(jù)模型。由基本的數(shù)據(jù)類型組成,并包括一組相關(guān)的服務(wù)（或稱操作）。信息隱蔽和數(shù)據(jù)封裝，使用與實現(xiàn)相分離。自然數(shù)的抽象數(shù)據(jù)類型定義ADTNaturalNumberisobjects:一個整數(shù)的有序子集合,它開始于0,結(jié)束于機器能表示的最大整數(shù)(MaxInt)。Function:對于所有的x,y

NaturalNumber;

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

Zero():NaturalNumber

返回自然數(shù)0IsZero(x):if(x==0)返回True

Booleanelse返回FalseAdd(x,y):if(x+y<=MaxInt)返回x+y

NaturalNumberelse返回MaxIntSubtract(x,y):if(x<y)返回0

NaturalNumberelse返回x-yEqual(x,y):if(x==y)返回TrueBooleanelse返回FalseSuccessor(x):if(x==MaxInt)返回xNaturalNumberelse返回x+1endNaturalNumber類(class)，實例(instance)具有相同屬性和服務(wù)的對象歸于同一類，形成類。類中的對象為該類的實例。屬性aPoint1aPoint2aPoint3aPoint4服務(wù)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)服務(wù)服務(wù)四邊形類及其對象quadrilateralDraw()move(x,y)contains(aPoint)PolygonreferencePointVerticesPolygon類referencePointVerticesDraw()move(x,y)contains(aPoint)Polygon的子類Quadrilateral類Quadrilateral線性結(jié)構(gòu)直接存取類數(shù)組,文件；順序存取類表,棧,隊列,優(yōu)先隊列；廣義索引類線性索引,搜索樹。非線性結(jié)構(gòu)層次結(jié)構(gòu)類樹,二叉樹,堆；群結(jié)構(gòu)類集合,圖。數(shù)據(jù)結(jié)構(gòu)的抽象層次事例學(xué)習(xí)：選擇排序問題。明確問題：遞增排序。解決方案：逐個選擇最小數(shù)據(jù)。算法框架：

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

若最小整數(shù)在a[k],交換a[i]與a[k];}細化程序：程序SelectSort

算法設(shè)計自頂向下，逐步求精

voidselectSort(inta[],constintn){

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

intk=i;

//從a[i]查到a[n-1],找最小整數(shù),在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;}}

用模板定義用于排序的數(shù)據(jù)表類#ifndefDATALIST_H#defineDATALIST_H#include<iostream.h>template<classType> classdataList{ private:Type*Element; intArraySize; voidSwap(intm1,intm2);intMaxKey

(intlow,inthigh);

public:dataList

(intsize=10):ArraySize(size),Element(new

Type[Size]){}~dataList(){delete[]Element;} voidSort(); friendostream&operator<<(ostream&

outStream,datalist<Type>&outList);friendistream&operator>>(istream&

inStream,datalist<Type>&inList);};#endif類中所有操作作為模板函數(shù)的實現(xiàn)#ifndefSELECTTM_H #defineSELECTTM_H

#include“datalist.h”template<classType>voiddataList

<Type>::Swap

(intm1,intm2){//交換由m1,m2為下標(biāo)的數(shù)組元素的值Typetemp=Element

[m1];

Element

[m1]=Element

[m2];

Element[m2]=temp;}template<classType>ostream&operator<<(ostream&OutStream,

dataList<Type>OutList){OutStream<<“數(shù)組內(nèi)容:\n”;for(inti=0;i<OutList.ArraySize;i++)

OutStream<<OutList.Element[i]<<‘’;

OutStream<<endl;

OuStream<<“數(shù)組當(dāng)前大小:”<<

OutList.ArraySize<<endl;returnOutStream;}

template<classType>voiddataList<Type>::Sort(){//按非遞減順序?qū)rraySize個關(guān)鍵碼//Element[0]到Element[ArraySize-1]排序for(inti=ArraySize-1;i>0;i--){intj=MaxKey(0,i);if(j!=i)swap(j,i);}}#endif使用模板的選擇排序算法的主函數(shù)

#include“selecttm.h”constintSIZE=10;intmain(){dataList<int>TestList(SIZE);

cin>>TestList;

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

cout<<TestList<<endl;

return0;}

性能分析與度量算法的性能標(biāo)準算法的后期測試算法的事前估計算法的后期測試在算法中的某些部位插裝時間函數(shù)

time

()測定算法完成某一功能所花費時間。順序搜索(SequenialSearch)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;}

插裝time()的計時程序

doublestart,stop;time(&start);

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

doublerunTime=stop-start;

cout<<""<<n<<""<< runTime<<endl;空間復(fù)雜度度量存儲空間的固定部分

程序指令代碼的空間，常數(shù)、簡單變量、定長成分(如數(shù)組元素、結(jié)構(gòu)成分、對象的數(shù)據(jù)成員等)變量所占空間?？勺儾糠?/p>

尺寸與實例特性有關(guān)的成分變量所占空間、引用變量所占空間、遞歸棧所用空間、通過new和delete命令動態(tài)使用空間。

程序步確定方法插入計數(shù)全局變量count

建表，列出個語句的程序步例以迭代方式求累加和的函數(shù)floatsum(floata[],intn){

floats=0.0;

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

returns;}在求累加和程序中加入count語句floatsum(floata[],intn

){

程序的簡化形式

voidsum(floata[],intn){for(inti=0;i<n;i++)count+=2;count+=3;}注意：

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

例如：賦值語句x=sum(R,n)

本身的程序步數(shù)為1；

一次執(zhí)行對函數(shù)sum(R,n)的調(diào)用需要的程序步數(shù)為2*n+3；

一次執(zhí)行的程序步數(shù)為 1+2*n+3=2*n+4計算累加和程序

程序步數(shù)計算工作表格時間復(fù)雜度的漸進表示法算法中所有語句的頻度之和是矩陣階數(shù)n的函數(shù)T(n)=2n3+3n2+2n+1一般地，稱n是問題的規(guī)模。則時間復(fù)雜度T(n)是問題規(guī)模n的函數(shù)。當(dāng)n趨于無窮大時，把時間復(fù)雜度的數(shù)量級（階）稱為算法的漸進時間復(fù)雜度T(n)=O(n3)----大O表示法時間復(fù)雜度的漸進表示法加法規(guī)則針對并列程序段

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

各種函數(shù)的增長趨勢

c<log2n<n<nlog2n<n2<n3<2n<3n<n!變量計數(shù)x=0;y=0;for(intk=0;k<n;k++)x++;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)T(n)=T1(n)+T2(n)+T3(n)=O(max(1,n,n2))=O(n2)

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

sum[i]=0.0;//數(shù)據(jù)累加for(intj=0;j<n;j++) sum[i]+=x[i][j];

}

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

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

漸進時間復(fù)雜度為O(max(m*n,m))

template<classType>//起泡排序voiddataList<Type>::bubbleSort(){//對表逐趟比較,ArraySize是表當(dāng)前長度

inti=1;

intexchange=1;

//當(dāng)exchange為0則停止排序

while(i<ArraySize&&exchange){

BubbleExchange(i,exchange);

i++;

} //一趟比較}

漸進時間復(fù)雜度O(f(n)*g(n))=

O(n2)

BubblrSortn-1趟BubbleExchange()n-i次比較有時,算法的時間復(fù)雜度不僅依賴于問題規(guī)模n，還與輸入實例的初始排列有關(guān)。在數(shù)組A[n]中查找給定值k的算法：inti=n-1;