上傳人：p***

認(rèn)證信息

認(rèn)證類型：個(gè)人認(rèn)證

認(rèn)證主體：歐**（實(shí)名認(rèn)證）

IP屬地：廣東

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

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

“選課單”包含如下信息

學(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ù)（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ù)據(jù)項(xiàng)(DataItem)組成。數(shù)據(jù)項(xiàng)是具有獨(dú)立含義的最小標(biāo)識(shí)單位。數(shù)據(jù)元素又稱為元素、結(jié)點(diǎn)、記錄。什么是數(shù)據(jù)結(jié)構(gòu)定義:由某一數(shù)據(jù)對(duì)象及該對(duì)象中所有數(shù)據(jù)成員之間的關(guān)系組成。記為：Data_Structure={D,R}其中，D是某一數(shù)據(jù)對(duì)象，R是該對(duì)象中所有數(shù)據(jù)成員之間的關(guān)系的有限集合。N個(gè)網(wǎng)點(diǎn)之間的連通關(guān)系

樹(shù)形關(guān)系網(wǎng)狀關(guān)系152436152436數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)從邏輯關(guān)系上描述數(shù)據(jù)，與數(shù)據(jù)的存儲(chǔ)無(wú)關(guān)；數(shù)據(jù)的邏輯結(jié)構(gòu)可以看作是從具體問(wèn)題抽象出來(lái)的數(shù)據(jù)模型；數(shù)據(jù)的邏輯結(jié)構(gòu)與數(shù)據(jù)元素本身的形式、內(nèi)容無(wú)關(guān)；數(shù)據(jù)的邏輯結(jié)構(gòu)與數(shù)據(jù)元素的相對(duì)位置無(wú)關(guān)。數(shù)據(jù)的邏輯結(jié)構(gòu)分類線性結(jié)構(gòu)。線性表非線性結(jié)構(gòu)。樹(shù)圖（或網(wǎng)絡(luò)）線性結(jié)構(gòu)樹(shù)形結(jié)構(gòu)樹(shù)二叉樹(shù)二叉搜索樹(shù)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ù)類型可以看作是計(jì)算機(jī)中已實(shí)現(xiàn)的數(shù)據(jù)結(jié)構(gòu)。數(shù)據(jù)類型就是數(shù)據(jù)結(jié)構(gòu)，不過(guò)它是從編程者的角度來(lái)使用的。數(shù)據(jù)類型是模板，必須定義屬于某種數(shù)據(jù)類型的變量，才能參加運(yùn)算。抽象數(shù)據(jù)類型

(ADTs:AbstractDataTypes)由用戶定義，用以表示應(yīng)用問(wèn)題的數(shù)據(jù)模型。由基本的數(shù)據(jù)類型組成,并包括一組相關(guān)的服務(wù)（或稱操作）。信息隱蔽和數(shù)據(jù)封裝，使用與實(shí)現(xiàn)相分離。自然數(shù)的抽象數(shù)據(jù)類型定義ADTNaturalNumberisobjects:一個(gè)整數(shù)的有序子集合,它開(kāi)始于0,結(jié)束于機(jī)器能表示的最大整數(shù)(MaxInt)。Function:對(duì)于所有的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)，實(shí)例(instance)具有相同屬性和服務(wù)的對(duì)象歸于同一類，形成類。類中的對(duì)象為該類的實(shí)例。屬性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ù)四邊形類及其對(duì)象quadrilateralDraw()move(x,y)contains(aPoint)PolygonreferencePointVerticesPolygon類referencePointVerticesDraw()move(x,y)contains(aPoint)Polygon的子類Quadrilateral類Quadrilateral線性結(jié)構(gòu)直接存取類數(shù)組,文件；順序存取類表,棧,隊(duì)列,優(yōu)先隊(duì)列；廣義索引類線性索引,搜索樹(shù)。非線性結(jié)構(gòu)層次結(jié)構(gòu)類樹(shù),二叉樹(shù),堆；群結(jié)構(gòu)類集合,圖。數(shù)據(jù)結(jié)構(gòu)的抽象層次事例學(xué)習(xí)：選擇排序問(wèn)題。明確問(wèn)題：遞增排序。解決方案：逐個(gè)選擇最小數(shù)據(jù)。算法框架：

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

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

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

voidselectSort(inta[],constintn){

//對(duì)n個(gè)整數(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ù)的實(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個(gè)關(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)準(zhǔn)算法的后期測(cè)試算法的事前估計(jì)算法的后期測(cè)試在算法中的某些部位插裝時(shí)間函數(shù)

time

()測(cè)定算法完成某一功能所花費(fèi)時(shí)間。順序搜索(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()的計(jì)時(shí)程序

doublestart,stop;time(&start);

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

doublerunTime=stop-start;

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

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

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

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

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

floats=0.0;

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

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

){

程序的簡(jiǎn)化形式

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

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

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

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

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

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

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

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

各種函數(shù)的增長(zhǎng)趨勢(shì)

c<log2n<n<nlog2n<n2<n3<2n<3n<n!變量計(jì)數(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;}

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

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

inti=1;

intexchange=1;

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

while(i<ArraySize&&exchange){

BubbleExchange(i,exchange);

i++;

} //一趟比較}

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

O(n2)

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