上傳人：d***

認(rèn)證信息

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

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

IP屬地：貴州

IP屬地：貴州 上傳時(shí)間：2023-01-15 格式：PPTX 頁(yè)數(shù)：71 大?。?15.96KB 積分：36 舉報(bào) 版權(quán)申訴

什么是數(shù)據(jù)結(jié)構(gòu)抽象數(shù)據(jù)類(lèi)型及面向?qū)ο蟾拍顢?shù)據(jù)結(jié)構(gòu)的抽象層次算法定義模板性能分析與度量第一章緒論“學(xué)生”表格“課程”表格

“選課單”包含如下信息

學(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ī))UNIX文件系統(tǒng)的系統(tǒng)結(jié)構(gòu)圖/(root)binlibuseretcmathdsswyintaoxieStack.cppQueue.cppTree.cpp數(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ù)元素又稱(chēng)為元素、結(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,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ù)的組織形式數(shù)據(jù)元素間間的邏輯關(guān)系，即數(shù)據(jù)的的邏輯結(jié)構(gòu)；數(shù)據(jù)元素及及其關(guān)系在在計(jì)算機(jī)存存儲(chǔ)內(nèi)的表表示，即數(shù)數(shù)據(jù)的存儲(chǔ)表示；數(shù)據(jù)的運(yùn)算算，即對(duì)數(shù)數(shù)據(jù)元素施施加的操作。數(shù)據(jù)的邏輯輯結(jié)構(gòu)數(shù)據(jù)的邏輯輯結(jié)構(gòu)從邏輯關(guān)系系上描述數(shù)數(shù)據(jù)，與數(shù)據(jù)的存存儲(chǔ)無(wú)關(guān)；數(shù)據(jù)的邏輯輯結(jié)構(gòu)可以以看作是從具體問(wèn)題題抽象出來(lái)來(lái)的數(shù)據(jù)模模型；數(shù)據(jù)的邏輯輯結(jié)構(gòu)與數(shù)據(jù)元素素本身的形形式、內(nèi)容容無(wú)關(guān)；數(shù)據(jù)的邏輯輯結(jié)構(gòu)與數(shù)數(shù)據(jù)元素的的相對(duì)位置置無(wú)關(guān)。數(shù)據(jù)的邏輯輯結(jié)構(gòu)分類(lèi)類(lèi)線(xiàn)性結(jié)構(gòu)。。線(xiàn)性表非線(xiàn)性結(jié)構(gòu)構(gòu)。樹(shù)圖（或網(wǎng)絡(luò)絡(luò)）線(xiàn)性結(jié)構(gòu)樹(shù)形結(jié)構(gòu)樹(shù)二二叉樹(shù)二二叉搜搜索樹(shù)1413121123456789103158710119987456623131bindevetclibuser1堆結(jié)構(gòu)“最大”堆“最小”堆123548711102916410121151236987圖結(jié)構(gòu)網(wǎng)網(wǎng)絡(luò)結(jié)構(gòu)12564312543611331814665161921數(shù)據(jù)的存儲(chǔ)結(jié)結(jié)構(gòu)數(shù)據(jù)的存儲(chǔ)結(jié)結(jié)構(gòu)是邏輯結(jié)結(jié)構(gòu)用計(jì)算機(jī)機(jī)語(yǔ)言的實(shí)現(xiàn)現(xiàn)；數(shù)據(jù)的存儲(chǔ)結(jié)結(jié)構(gòu)依賴(lài)于計(jì)計(jì)算機(jī)語(yǔ)言。。順序存儲(chǔ)表示示鏈接存儲(chǔ)表示示索引存儲(chǔ)表示示散列存儲(chǔ)表示示主要用于內(nèi)存存的存儲(chǔ)表示示主要用于外存存(文件)的存儲(chǔ)表表示抽象數(shù)據(jù)類(lèi)型型及面向?qū)ο笙蟾拍顢?shù)據(jù)類(lèi)型。定義：一組性質(zhì)相同同的值的集合合,以及定定義于這個(gè)值值集合上的一一組操作的總總稱(chēng)。C語(yǔ)言中的數(shù)據(jù)據(jù)類(lèi)型。charintfloatdoublevoid字符型整型型浮點(diǎn)型雙雙精度型無(wú)無(wú)值構(gòu)造數(shù)據(jù)類(lèi)型型由基本數(shù)據(jù)類(lèi)型型或構(gòu)造數(shù)據(jù)類(lèi)型型組成。構(gòu)造數(shù)據(jù)類(lèi)型型由不同成分類(lèi)型型構(gòu)成?；緮?shù)據(jù)類(lèi)型型可以看作是是計(jì)算機(jī)中已已實(shí)現(xiàn)的數(shù)據(jù)據(jù)結(jié)構(gòu)。數(shù)據(jù)類(lèi)型就是是數(shù)據(jù)結(jié)構(gòu)，，不過(guò)它是從從編程者的角角度來(lái)使用的的。數(shù)據(jù)類(lèi)型是模模板，必須定定義屬于某種種數(shù)據(jù)類(lèi)型的的變量，才能能參加運(yùn)算。。抽象數(shù)據(jù)類(lèi)型型(ADTs:AbstractDataTypes)由用戶(hù)定義，，用以表示應(yīng)應(yīng)用問(wèn)題的數(shù)據(jù)模型。由基本的數(shù)據(jù)類(lèi)類(lèi)型組成,并包包括一組相關(guān)的服服務(wù)（或稱(chēng)操作））。信息隱蔽和數(shù)據(jù)封裝，使用與實(shí)現(xiàn)現(xiàn)相分離。抽象數(shù)據(jù)類(lèi)型型查找登錄錄刪除除修改符號(hào)表表自然數(shù)的抽象象數(shù)據(jù)類(lèi)型定定義ADTNaturalNumberisobjects:一個(gè)整數(shù)的有有序子集合,它開(kāi)始于0,結(jié)束于機(jī)器能能表示的最大大整數(shù)(MaxInt)。Function:對(duì)于所有的x,yNaturalNumber;False,TrueBoolean,+、-、<、==、=等都是可用的的服務(wù)。Zero():NaturalNumber返回自然數(shù)0IsZero(x):if(x==0)返回TrueBooleanelse返回FalseAdd(x,y):if(x+y<=MaxInt)返回x+yNaturalNumberelse返返回MaxIntSubtract(x,y):if(x<y)返回0NaturalNumberelse返返回x-yEqual(x,y):if(x==y)返回TrueBooleanelse返回FalseSuccessor(x):if(x==MaxInt)返回xNaturalNumberelse返返回x+1endNaturalNumber面向?qū)ο蟮母鸥拍蠲嫦驅(qū)ο?對(duì)象＋類(lèi)類(lèi)＋繼承＋通通信對(duì)象在應(yīng)用問(wèn)題中中出現(xiàn)的各種種實(shí)體、事件、規(guī)格說(shuō)明等。由一組屬性值和在這組值上上的一組服務(wù)（或稱(chēng)操作））構(gòu)成。類(lèi)(class)，實(shí)實(shí)例(instance)具有相同屬性和服務(wù)的對(duì)象歸于同同一類(lèi)，形成成類(lèi)。類(lèi)中的對(duì)象為為該類(lèi)的實(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ù)四邊形類(lèi)及其其對(duì)象quadrilateral繼承派生類(lèi)：四邊形，三角角形，…子類(lèi)特化化類(lèi)(特殊化化類(lèi))基類(lèi)：多邊形父類(lèi)泛化化類(lèi)(一般化化類(lèi))通信消息傳遞Draw()move(x,y)contains(aPoint)PolygonreferencePointVerticesPolygon類(lèi)referencePointVerticesDraw()move(x,y)contains(aPoint)Polygon的子類(lèi)Quadrilateral類(lèi)Quadrilateral線(xiàn)性結(jié)構(gòu)直接存取類(lèi)數(shù)組,文件件；順序存取類(lèi)表,棧,隊(duì)隊(duì)列,優(yōu)優(yōu)先隊(duì)列；廣義索引類(lèi)線(xiàn)性索引,搜搜索樹(shù)。非線(xiàn)性結(jié)構(gòu)層次結(jié)構(gòu)類(lèi)樹(shù),二叉樹(shù)樹(shù),堆；群結(jié)構(gòu)類(lèi)集合,圖。。數(shù)據(jù)結(jié)構(gòu)的抽抽象層次算法定義定義：一個(gè)有窮的指指令集，這些指令為為解決某一特特定任務(wù)規(guī)定定了一個(gè)運(yùn)算算序列。特性：輸入有0個(gè)或多個(gè)個(gè)輸入；輸出有一個(gè)或多個(gè)個(gè)輸出(處理理結(jié)果)；確定性每步定義都是是確切無(wú)歧義義的；有窮性算法應(yīng)在執(zhí)行行有窮步后結(jié)結(jié)束；有效性每一條運(yùn)算應(yīng)應(yīng)足夠基本。。事例學(xué)習(xí)：選擇排序問(wèn)題題。明確問(wèn)題：遞增排序。解決方案：逐個(gè)選擇最小小數(shù)據(jù)。算法框架：for(inti=0;i<n-1;i++){//n-1趟從從a[i]檢查查到a[n-1];若若最小整數(shù)數(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;}}模板(template)定義適合多種數(shù)數(shù)據(jù)類(lèi)類(lèi)型的類(lèi)定義義或算法，在特特定環(huán)環(huán)境下下通過(guò)過(guò)簡(jiǎn)單單地代代換，，變成成針對(duì)具具體某某種數(shù)數(shù)據(jù)類(lèi)類(lèi)型的類(lèi)定義義或算法。。用模板板定義義用于于排序序的數(shù)數(shù)據(jù)表表類(lèi)#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(newType[Size]){}~dataList(){delete[]Element;}voidSort();friendostream&operator<<(ostream&outStream,datalist<Type>&outList);friendistream&operator>>(istream&inStream,datalist<Type>&inList);};#endif類(lèi)中中所所有有操操作作作作為為模模板板函函數(shù)數(shù)的的實(shí)實(shí)現(xiàn)現(xiàn)#ifndefSELECTTM_H#defineSELECTTM_H#include“datalist.h””template<classType>voiddataList<Type>::Swap(intm1,intm2){//交交換換由由m1,m2為為下下標(biāo)標(biāo)的的數(shù)數(shù)組組元元素素的的值值Typetemp=Element[m1];Element[m1]=Element[m2];Element[m2]=temp;}template<classType>intdataList<Type>::MaxKey(intlow,inthigh){//查找找數(shù)數(shù)組組Element[low]到Element[high]//中的的最最大大值值，，函函數(shù)數(shù)返返回回其其位位置置intmax=low;for(intk=low+1,k<=high,k++)if(Element[max]<Element[k])max=k;returnmax;}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>istream&operator>>(istream&InStream,dataList<Type>InList){//輸入入對(duì)象為為InList，輸入入流對(duì)象象為InStreamcout<<“錄入數(shù)組組當(dāng)前大大小:”;Instream>>InList.ArraySize;cout<<“錄入數(shù)組組元素值值:\n”;for(inti=0;i<InList.ArraySize;i++){cout<<“元素”<<i<<“:”;InStream>>InList.Element[i];}returnInStream;}template<classType>voiddataList<Type>::Sort(){//按按非遞遞減順順序?qū)?duì)ArraySize個(gè)個(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ù)數(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)準(zhǔn)算法的的后期期測(cè)試試算法的的事前前估計(jì)計(jì)算法的的性能能標(biāo)準(zhǔn)準(zhǔn)正確性性可使用用性可讀性性效率健壯性性算法的的后期期測(cè)試試在算法法中的的某些些部位位插裝裝時(shí)間間函數(shù)數(shù)time()測(cè)定算算法完完成某某一功功能所所花費(fèi)費(fèi)時(shí)間間。順序搜搜索(SequenialSearch)intseqsearch(inta[],intn,intx){//在在a[0],……,a[n-1]中中搜索索xinti=0;while(i<n&&a[i]!=x)i++;if(i==n)return-1;returni;}插裝time()的計(jì)時(shí)時(shí)程序序doublestart,stop;time(&start);intk=seqsearch(a,n,x);time(&stop);doublerunTime=stop-start;cout<<""<<n<<""<<runTime<<endl;算法的的事前前估計(jì)計(jì)空間復(fù)復(fù)雜度度時(shí)間復(fù)復(fù)雜度度空間復(fù)復(fù)雜度度度量量存儲(chǔ)空空間的的固定定部分分程序指指令代代碼的的空間間，常常數(shù)、、簡(jiǎn)單單變量量、定定長(zhǎng)成成分(如數(shù)數(shù)組元元素、、結(jié)構(gòu)構(gòu)成分分、對(duì)對(duì)象的的數(shù)據(jù)據(jù)成員員等)變量量所占占空間間?？勺儾坎糠殖叽缗c與實(shí)例例特性性有關(guān)關(guān)的成成分變變量所所占空空間、、引用用變量量所占占空間間、遞遞歸棧棧所用用空間間、通通過(guò)new和delete命令動(dòng)動(dòng)態(tài)使使用空空間。。時(shí)間復(fù)復(fù)雜度度度量量編譯時(shí)時(shí)間。。運(yùn)行時(shí)時(shí)間。。程序步步。語(yǔ)法上上或語(yǔ)語(yǔ)義上上有意意義的的一段段指令令序列列。執(zhí)行時(shí)時(shí)間與與實(shí)例例特性性無(wú)關(guān)關(guān)。例如：：聲明語(yǔ)語(yǔ)句：程序序步數(shù)數(shù)為0;表達(dá)式式：程序序步數(shù)數(shù)為1。程序步步確定定方法法插入計(jì)計(jì)數(shù)全全局變變量count建表，，列出出個(gè)語(yǔ)語(yǔ)句的的程序序步例以以迭代代方式式求累累加和和的函函數(shù)floatsum(floata[],intn){floats=0.0;for(inti=0;i<n;i++)s+=a[i];returns;}在求累累加和和程序序中加加入count語(yǔ)句floatsum(floata[],intn){floats=0.0;count++;//count統(tǒng)計(jì)執(zhí)執(zhí)行語(yǔ)語(yǔ)句條條數(shù)for(inti=0;i<n;i++){count++;//針對(duì)for語(yǔ)句s+=a[i];count++;}//針對(duì)賦賦值語(yǔ)語(yǔ)句count++;//針對(duì)for的最后后一次次count++;//針對(duì)return語(yǔ)句returns;}執(zhí)行結(jié)束得得程序步步數(shù)count=2*n+3程序的簡(jiǎn)化化形式voidsum(floata[],intn){for(inti=0;i<n;i++)count+=2;count+=3;}注意意：一個(gè)個(gè)語(yǔ)語(yǔ)句句本本身身的的程程序序步步數(shù)數(shù)可可能能不不等等于于該該語(yǔ)語(yǔ)句句一一次次執(zhí)執(zhí)行行所所具具有有的的程程序序步步數(shù)數(shù)。。例如如：：賦賦值值語(yǔ)語(yǔ)句句x=sum(R,n)本身身的的程程序序步步數(shù)數(shù)為為1；；一次次執(zhí)執(zhí)行行對(duì)對(duì)函函數(shù)數(shù)sum(R,n)的調(diào)用需需要的程程序步數(shù)數(shù)為2*n+3；一次執(zhí)行行的程序序步數(shù)為為1+2*n+3=2*n+4計(jì)算累加和程序程序步數(shù)計(jì)算工作表格格時(shí)間復(fù)雜度的的漸進(jìn)表示法法例求兩個(gè)個(gè)n階方陣的的乘積C=ABvoidMatrixMultiply(intA[n][n],intB[n][n],intC[n][n]){for(inti=0;i<n;i++)…n+1for(intj=0;j<n;j++){…n(n+1)C[i][j]=0;…n2for(intk=0;k<n;k++)…n2(n+1)C[i][j]=C[i][j]+A[i][k]*B[k][j];…n3}}2n3+3n2+2n+1時(shí)間復(fù)雜度的的漸進(jìn)表示法法算法中所有有語(yǔ)句的頻頻度之和是是矩陣階數(shù)n的函數(shù)T(n)=2n3+3n2+2n+1一般地，稱(chēng)稱(chēng)n是是問(wèn)題的規(guī)規(guī)模。則時(shí)時(shí)間復(fù)雜度度T(n)是問(wèn)問(wèn)題規(guī)模n的函函數(shù)。當(dāng)n趨于無(wú)無(wú)窮大時(shí)，，把時(shí)間復(fù)復(fù)雜度的數(shù)數(shù)量級(jí)（階階）稱(chēng)為算算法的漸進(jìn)進(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ì)勢(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)乘法規(guī)則針對(duì)嵌套程程序段T(n,m)=T1(n)*T2(m)=O(f(n)*g(m))漸進(jìn)的空間間復(fù)雜度S(n)=O(f(n))兩個(gè)并列循循環(huán)的例子子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ù)數(shù)據(jù)和cout<<i<<““:”<<sum[i]<<endl;}漸進(jìn)進(jìn)時(shí)時(shí)間間復(fù)復(fù)雜雜度度為為O(max(m*n,m))template<classType>//起泡泡排排序序voiddataList<Type>::bubbleSort(){//對(duì)表表逐逐趟趟比比較較,ArraySize是表表當(dāng)當(dāng)前前長(zhǎng)長(zhǎng)度度inti=1;intexchange=1;//當(dāng)exchange為0則停停止止排排序序while(i<ArraySize&&exchange){BubbleExchange(i,exchange);i++;}//一趟趟比比}

template<classType>voiddataList<Type>::BubbleExchange(inti,int&exchange){exchange=0;//假定定元元素素未未交交換換for(intj=ArraySize-1;j>=i;j--)if(Element[j-1]>Element[j]){Swap(j-1,j);//發(fā)生生逆逆序序,交交換換exchange=1;//做““發(fā)發(fā)生生交交換換””標(biāo)標(biāo)志志}}漸進(jìn)進(jìn)時(shí)時(shí)間間復(fù)復(fù)雜雜度度O(f(n)*g(n))=O(n2)BubblrSortn-1趟BubbleExchange()n-i次比比較較有時(shí)時(shí),算算法法的的時(shí)時(shí)間間復(fù)復(fù)雜雜度度不不僅僅依依賴(lài)賴(lài)于于問(wèn)問(wèn)題題規(guī)規(guī)模模n，還還與與輸輸入入實(shí)實(shí)例例的的初初始始排排列列有有關(guān)關(guān)。。在數(shù)數(shù)組組A[n]中查查找找給給定定值值k的算算法法：：inti=n-1;while(i>=0&&A[i]!=k)i--;returni;算法法的的語(yǔ)語(yǔ)句句i--的頻頻度度不不僅僅與與n有關(guān)關(guān)，，還還與與A[]中中各各元元素素的的取取值值，以以及及k的取取值值有關(guān)關(guān)。。例：：設(shè)設(shè)有有兩兩個(gè)個(gè)算算法法在在同同一一機(jī)機(jī)器器上上運(yùn)運(yùn)行行，，其其執(zhí)執(zhí)行行時(shí)時(shí)間間分分別別為為100n2和2n，問(wèn)問(wèn)：：要要使使前前者者快快于于后后者者，，n至少少要要取取多多大大？？解答答：：?jiǎn)栴}題是是找