1、 1學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)課的目的與內(nèi)容 2什么是數(shù)據(jù)結(jié)構(gòu) 3抽象數(shù)據(jù)類(lèi)型及面向?qū)ο蟾拍?4算法定義 5模板 6性能分析與度量第 1 章序言1學(xué)習(xí)本課程的目的和內(nèi)容)介紹常用的數(shù)據(jù)結(jié)構(gòu)和算法 用什么樣的數(shù)據(jù)結(jié)構(gòu)來(lái)描述你要解的問(wèn)題： 線性表、樹(shù)、圖 解以上問(wèn)題的數(shù)據(jù)結(jié)構(gòu)已不是整型，浮點(diǎn)型，布爾型，雙精度型（數(shù)值計(jì)算用到的數(shù)據(jù)基本類(lèi)型），而是表，樹(shù)，圖等非數(shù)值型的數(shù)據(jù)結(jié)構(gòu)及其操作。因此數(shù)據(jù)結(jié)構(gòu)是一門(mén)研究非數(shù)值性程序設(shè)計(jì)中計(jì)算機(jī)操作的對(duì)象以及它們之間的關(guān)系和操作的學(xué)科。)前趨課程編譯原理：用棧實(shí)現(xiàn)表達(dá)式的計(jì)算與遞歸過(guò)程操作系統(tǒng)：用隊(duì)列實(shí)現(xiàn)作業(yè)調(diào)度數(shù)據(jù)庫(kù)：用+樹(shù)組織與存取外存儲(chǔ)器上的大量數(shù)據(jù))算法分析的基本方法

2、算法好壞的區(qū)分標(biāo)準(zhǔn)：運(yùn)行速度（時(shí)間），所占空間，精確度等例：排序 a1, a2, a3, ,an-1, an比較次數(shù):n-1+n-2+2+1=n*(n-1)/2當(dāng)n趨向無(wú)窮大時(shí), 運(yùn)算時(shí)間與 n2 成正比,記作O(n2 )4 )鞏固所學(xué)的C+2什么是數(shù)據(jù)結(jié)構(gòu))數(shù)據(jù)(data)描述客觀事物的數(shù)，字符，以及所有能輸入計(jì)算機(jī)的，并被計(jì)算機(jī)程序識(shí)別和處理的符號(hào)集合或者說(shuō)數(shù)據(jù)是計(jì)算機(jī)化的信息 )數(shù)據(jù)結(jié)構(gòu)(data structure)由某一數(shù)據(jù)對(duì)象及該對(duì)象中所有數(shù)據(jù)成員之間的關(guān)系組成，記為：Data_Structure=D,R 是某一數(shù)據(jù)對(duì)象，R是該對(duì)象中所有數(shù)據(jù)成員之間的關(guān)系的有限集合線性結(jié)構(gòu)：非線性

3、結(jié)構(gòu)： 從不同的角度看，數(shù)據(jù)結(jié)構(gòu)涉及三個(gè)方面： 數(shù)據(jù)的邏輯結(jié)構(gòu)-從用戶(hù)視圖看是面向問(wèn)題的 數(shù)據(jù)的物理結(jié)構(gòu)-從具體實(shí)現(xiàn)視圖看，是面向計(jì)算機(jī)的(順序，拉鏈) 相關(guān)操作及實(shí)現(xiàn)例：學(xué)生表線性表，順序存儲(chǔ)，增、刪、改 邏輯 物理 操作3抽象數(shù)據(jù)類(lèi)型及面向?qū)ο? 數(shù)據(jù)類(lèi)型(data type) 包括一個(gè)值集和定義在其上的一個(gè)操作集 如：int值集： ,-2,-1,0,1,2, 操作集：， 程序設(shè)計(jì)語(yǔ)言都提供了一組固有的數(shù)據(jù)類(lèi)型： 原子數(shù)據(jù)類(lèi)型：值是單個(gè)不可分的如int, float, char等 結(jié)構(gòu)數(shù)據(jù)類(lèi)型：由已有的數(shù)據(jù)類(lèi)型構(gòu)造新的數(shù)據(jù)類(lèi)型 如結(jié)構(gòu)類(lèi)型 姓名，年齡，性別 初等項(xiàng)) 抽象數(shù)據(jù)類(lèi)型(ADTs

4、: Abstract Data Types) 抽象：是一種信息隱蔽的方法例如：int x; float x,y; x=735; x=x*y+3.0;整型數(shù)賦值的抽象浮點(diǎn)數(shù)運(yùn)算的抽象 而且抽象可以一層層提高，由低層抽象定義更高級(jí)的數(shù)據(jù)模型抽象,如表，隊(duì)列，圖，甚至窗口，管理器等。抽象數(shù)據(jù)類(lèi)型：提供組織和設(shè)計(jì)程序的一種新方法思想：將數(shù)據(jù)類(lèi)型的使用與它的內(nèi)部表示（機(jī)內(nèi)存儲(chǔ)），實(shí)現(xiàn)（機(jī)內(nèi)操作的實(shí)現(xiàn)）分開(kāi)更確切地說(shuō)：把一個(gè)數(shù)據(jù)類(lèi)型的內(nèi)部表示及在這個(gè)類(lèi)型上的操作實(shí)現(xiàn)封裝到一個(gè)程序模塊中，用戶(hù)不必知道細(xì)節(jié) 抽象數(shù)據(jù)類(lèi)型的特征是使用和實(shí)現(xiàn)分離，實(shí)行封裝 和信息隱蔽 優(yōu)點(diǎn)： 從使用者來(lái)看，只要了解該抽象數(shù)據(jù)類(lèi)型

5、的規(guī)格說(shuō)明，就可以利用其公共界面中的服務(wù)來(lái)使用這個(gè)類(lèi)型，而不必關(guān)心其物理實(shí)現(xiàn)從實(shí)現(xiàn)者的角度看：把抽象數(shù)據(jù)類(lèi)型的物理實(shí)現(xiàn)封裝起來(lái)，有利于編碼、測(cè)試，也有利于擴(kuò)充、修改ADT NaturalNunber is objects: 一個(gè)整數(shù)的有序子集合,它開(kāi)始于0,結(jié)束 于機(jī)器能表示的最大整數(shù)(MAXINT)。 Function: Zero( ):NaturalNumber IsZero(x):Boolean Add(x,y):NaturalNumber Equal(x,y):Boolean Successor(x):NaturalNumber Subtract(x,y):NaturalNumber

6、end NaturalNumber）面向?qū)ο蟮母拍蠲嫦驅(qū)ο髮?duì)象類(lèi)繼承通信 對(duì)象： 指各種實(shí)體，事件，規(guī)格說(shuō)明，由一組屬性值（確定對(duì)象的狀態(tài)）和在這組值上的一組操作構(gòu)成 例如：定義一個(gè)矩形對(duì)象： 屬性：左上角坐標(biāo), 右下角坐標(biāo), 邊線顏色, 內(nèi)部顏色 操作：move(x,y); SetEdgeColor(c); SetInnerColor(c); 類(lèi)：具有相同屬性和操作的對(duì)象構(gòu)成同一個(gè)類(lèi)對(duì)類(lèi)而言，其中的每一個(gè)對(duì)象稱(chēng)為該類(lèi)的一個(gè)實(shí) 例(instance)，不同的實(shí)例具有不同的屬性值繼承： 基類(lèi)（父類(lèi)）-把各派生類(lèi)中的共同部分（屬性和操作）集中到基類(lèi)中 派生類(lèi)（子類(lèi)）-只保留自己特有的屬性和服務(wù)例：

7、基類(lèi)-多邊形派生類(lèi)-四邊形，三角形等通信：各個(gè)類(lèi)對(duì)象間通過(guò)消息進(jìn)行通信消息：一個(gè)類(lèi)的對(duì)象要求另一個(gè)類(lèi)的對(duì)象執(zhí)行某個(gè)操作的指令 4） 用于描述數(shù)據(jù)結(jié)構(gòu)的語(yǔ)言：C+、Java 4. 算法定義算法(Algorithm)：解一個(gè)問(wèn)題的一個(gè)運(yùn)算序列（有窮指令集）特性：(1)有窮性，(2)確定性， (3)一個(gè)初始動(dòng)作（輸入），(4)序列終止：?jiǎn)栴}有解或無(wú)解（輸出）程序：與算法十分類(lèi)似但不完全一樣(1)算法可有多種描述方法：語(yǔ)言，圖形，表格等而程序一定是用機(jī)器可執(zhí)行的語(yǔ)言寫(xiě)的(2)程序不滿(mǎn)足有窮性如在正常情況下永遠(yuǎn)運(yùn)行下去例：把n個(gè)整數(shù)用選擇排序的方法由小到大排列void SelectSort(int a,

8、 const int n) for (int i=0; in-1; i+)int k = i;/k中存放每趟比較最小元素的下標(biāo)for (int j=i+1; jn; j +)if (aj ak) k = j;int temp=ai; ai=ak; ak=temp;a0, a1, , an-15. 模板(template)C+中引入模板的目的是為了實(shí)現(xiàn)軟件的復(fù)用，可利用以前開(kāi)發(fā)完成的數(shù)據(jù)結(jié)構(gòu)或算法模塊，有選擇地組裝到新的軟件中,積木式的開(kāi)發(fā)方法.)具體做法：用模板寫(xiě)出適合多種數(shù)據(jù)類(lèi)型的類(lèi)定義或算法，然后在特定環(huán)境下通過(guò)簡(jiǎn)單代換，把它變?yōu)獒槍?duì)具體某種數(shù)據(jù)類(lèi)型的類(lèi)定義或算法類(lèi)模板的說(shuō)明形式：temp

9、late class className再對(duì)比一下選擇排序的C+函數(shù)過(guò)程：(1).有兩個(gè)參數(shù)：數(shù)組a為整型（浮點(diǎn)型要另外說(shuō)明），大小為整型量n，現(xiàn)在變?yōu)轭?lèi)，這兩個(gè)參數(shù)就作為類(lèi)的兩個(gè)私有成員變量(2).為了使選擇排序不但適用于int型，而且適用于其它類(lèi)型，因此在類(lèi)模板說(shuō)明中，用-表示(3).再把選擇排序中用到的一些操作：如交換兩下標(biāo)元素的內(nèi)容，求最小值（也可為求最大值），輸入和輸出分別作為類(lèi)的成員函數(shù)或友元函數(shù)放在類(lèi)中# ifndef DATALIST_H# define DATALIST_H# include template class datalist private: Type * El

10、ement; int ArraySize; void Swap(const int mark1,const int mark2); int MaxKey (const int low,const int high); public: datalist(int size=10):ArraySize(size),Element(new TypeSize) dataList( )delete Element; void Sort( ); friend ostream& operator (ostream& outStream,const datalist& outList); friend istr

11、eam&operator (istream& inStream,const datalist& inlist); ; # endif 所有操作的實(shí)現(xiàn)在頭文件selecttm.h中 對(duì)類(lèi)模板中的成員函數(shù)的說(shuō)明形式：template 返回類(lèi)型 classname:成員函數(shù)名(形式參數(shù)表)/成員函數(shù)定義體 作用域區(qū)分符 # ifndef SELECTTM-H# define SELECTTM-H# include “datalist.h”template void datalist :Swap(const int mark1,const int mark2) Type temp=Elementmar

12、k1; Elementmark1=Elementmark2; Elementmark2=temp;templateint dataList:MaxKey(const int low,const int high) int max=low; for(int k=low+1;k=high;k+) if (ElementmaxElementk) max=k; return max; template ostream& operator(ostream& OutStream,const dataList& OutList) OutStream“Array Contents:n”; for(int i=

13、0; iOutList.ArraySize; i+) OutStreamOutList.Elementi ; OutStreamendl; OutStream“Array Current Size:” OutList.ArraySizeendl; return OutStream; templateistream&operator(istream&InStream,const dataList&InList) coutInList.ArraySize; cout“Enter array element:n”; for(int i=0; iInList.ArraySize; i+) cout“E

14、lement”iInList.Elementi; return InStream; templatevoid dataList:sort( ) for( int i=ArraySize-1; i0; i-) int j=Maxkey(0,i); if (j!=i) Swap(j,i); # endif對(duì)模板類(lèi)執(zhí)行實(shí)例化：# include “selecttm.h”const int SIZE=10; int main( ) dataList Testlist(SIZE); cinTestlist; cout“Testing selection Sort:n”Testlistendl; Test

15、List.Sort( ); cout“After sorting: n”TestListendl; return 0; 6. 性能分析與度量)算法的性能標(biāo)準(zhǔn)正確性可使用性可讀性效率時(shí)間代價(jià)（主要討論的）空間代價(jià))時(shí)間復(fù)雜度度量程序步(program step)是指在語(yǔ)法上或語(yǔ)義上有意義的一段指令序列 注釋?zhuān)悍菆?zhí)行語(yǔ)句，程序步數(shù)為0聲明語(yǔ)句：程序步數(shù)為0表達(dá)式：如不包含函數(shù)調(diào)用，則程序步數(shù)為 如有函數(shù)調(diào)用，則包括調(diào)用的步數(shù)賦值語(yǔ)句：=程序步數(shù)同表達(dá)式循環(huán)語(yǔ)句：while do . do while 一次執(zhí)行的程序步數(shù)等于的程序步數(shù) for (;) 第一次執(zhí)行的步數(shù)與的程序步數(shù)之和 后續(xù)執(zhí)行的程序

16、步數(shù)與的程序步數(shù)之和switch語(yǔ)句：switch() case 條件1： case 條件2： 等于自己的程序步數(shù)+它前面所有條件的程序步數(shù) default： if-then語(yǔ)句：if () ；表達(dá)式的步數(shù)語(yǔ)句的步數(shù)else ； 表達(dá)式的步數(shù)語(yǔ)句的步數(shù)函數(shù)執(zhí)行語(yǔ)句：一般為動(dòng)態(tài)存儲(chǔ)管理語(yǔ)句：new，delete 為轉(zhuǎn)移語(yǔ)句：為以上面所舉的選擇排序?yàn)槔篺or (int i=0; in-1; i+) int k = i;for (int j=i+1; jn; j +) if (aj ak) k = j;int temp=ai; ai=ak; ak=temp;總的執(zhí)行步數(shù) +5n-5記作 T(n)=

17、 +5n-5，當(dāng)n 時(shí)，T(n)/ 常數(shù)( 1 )故T(n)=O( ) ,稱(chēng)為算法的時(shí)間復(fù)雜度(time complexity).數(shù)量級(jí)程序執(zhí)行的步數(shù)(頻度)nn-12+3+n= ( +n-2)/21+2+n-1=( -n)/23(n-1)漸進(jìn)表示法對(duì)有n個(gè)元素的數(shù)組，如果采用順序查找方法，而且假設(shè)每一個(gè)元素的查找概率相等則其查找成功的平均比較次數(shù)為：T(n)=(1+2+n)/n=(1/n)*n*(n+1)/2=(n+1)/2=O(n)一般而言要全面分析一個(gè)算法： 算法在最壞情況下的時(shí)間代價(jià) 算法在最好情況下的時(shí)間代價(jià) 算法在平均情況下的時(shí)間代價(jià) 時(shí)間復(fù)雜度的數(shù)量級(jí)有：O(n), O( n2

18、), O(n3 ), O( 2n ), O(log2n) ,O(n*log2n ) 線性 平方階 立方階指數(shù)階 對(duì)數(shù)階 時(shí)間復(fù)雜度主要在算法的循環(huán)程序段中： 單個(gè)循環(huán) 并列的循環(huán) 嵌套并列 O(n)O(n)O(m)O(n)T(n,m)=T1(m)+T2(n) =O(max(f(n),g(m)O(m*n)O(m)O(max(m*n,m) =O(m*n)3). 空間復(fù)雜度的度量 考慮漸進(jìn)的空間復(fù)雜度，即用O(n)方式來(lái)表示。 算法分析例子：1-8 1)for (int i=1; i=n; i+) for (int j=1; j=n; j+) cij = 0.0; for ( int k = 1; k=n; k+) cij = cij +