概論ds01introcol任課教員

統(tǒng) 學(xué)會(huì)合理地組織數(shù)據(jù),有效地表示數(shù)據(jù),有效地處理數(shù)據(jù)

l} Page期中期末

l} Page發(fā)現(xiàn)，則者和被者本次作業(yè)或上機(jī)題

l} Page所有作業(yè)和上機(jī)作業(yè)都必須在指定的期限（5）得–20分

l} Page1 2)每次作業(yè)，都在作業(yè)本或電子稿的word文 34算法中直接使用的函數(shù)、過(guò)程先寫ADT，5注意算法格式(層次嵌套、不同功能塊之間

l} Page學(xué)號(hào) 1.readme.txt文件， 的.dsw,.dsp文件，rc 3.上機(jī)

l} Page

l} Page ，2004年7月。、譯,《數(shù)據(jù)結(jié)構(gòu)與算法分析》(C++第二版)，電子工業(yè)，2002年。（用1998年的

l} Page，Vol3.國(guó)防工業(yè) ThomasH.Cormen,CharlesE.LeisersonRonaldLRivestCliffordPress.高等教育影印。WilliamFord，《DataStructurewith

l} Page

l} Page1.21.31.41.5

l} Page

l} Pagel}Page(dataR）來(lái)表示：(K，R)

l} Page 的各類親屬關(guān)系就是一組關(guān)系R,其中如母系血緣關(guān)系r

l} Page在計(jì)算機(jī)中一般使用1個(gè)字節(jié)到4個(gè)字節(jié)來(lái)整數(shù)圍和精度是有限的。機(jī)器一般使用4個(gè)字節(jié)到8個(gè)字節(jié)來(lái)存

l} Page 1表示ASCII

l} Page為w_char類型（widecharacter）。

l} Page由于機(jī)器的指令系統(tǒng)一般采用32bit或64bit的地址長(zhǎng)

l} Page

l} Page

l} Page線性結(jié)構(gòu)（linear樹(shù)型結(jié)構(gòu)（tree圖結(jié)構(gòu)（graph

l} Page它的關(guān)系r是一種線性關(guān)系，或稱為‘前后關(guān)系’，有時(shí)

l} Page

l} Page構(gòu)的結(jié)構(gòu)

l} Page先明確數(shù)據(jù)結(jié)點(diǎn)，及其主要關(guān)系這是一種自頂向下

l} Page 計(jì)算機(jī)的主

l} Page 映射，對(duì)于數(shù)據(jù)邏輯結(jié)構(gòu)（K,r）,其中r∈R每一個(gè)關(guān)系元組（j1j2）∈r（其中j1j2∈K是結(jié)點(diǎn)），亦即j1,j2的邏輯后繼關(guān)系應(yīng)映射為單元的地址順序關(guān)系（或指針的地址指向關(guān)系）

l} Page

l} Page順序結(jié)構(gòu)稱為緊湊結(jié)構(gòu)，其緊湊性是指它

l} Page

l} Page 一部分存放結(jié)點(diǎn)本身的數(shù)據(jù)，稱為

l} Page

l} Page

l} Page Y：ZD，把結(jié)點(diǎn)的整數(shù)索引值z(mì)∈Z映射到結(jié)點(diǎn)的地址d∈D。它稱為索引函數(shù)，一般而言它并不象數(shù)組那樣，是簡(jiǎn)

l} Page 始址(元素S[i]

l} Page

l} Page

l} Page數(shù)h:SZ，

l} Page

l} Page

l} Page

l} Page

l} Page需要準(zhǔn)確地給出該數(shù)據(jù)結(jié)構(gòu)Λ的組成元素的取值類型

l} Page

l} Page

l} Page classvector 面附加＃include{//1. //vector<double>v(100);用

l} Page//2.用名 //3.ELEMintmaxLength;intcurrenSize;

印

Pagevector<ELEM>v; vector<ELEM>v(k);//創(chuàng)建一個(gè)長(zhǎng)度為k的向量vector<ELEM>v(k,value)創(chuàng)建一個(gè)長(zhǎng)度為k的向量intsize(); //函數(shù)v.size()將返回整數(shù)，向量的當(dāng)前長(zhǎng)度}

l} Page te<classclassmatrix//二維矩陣類模板matrix，模板參數(shù) 面附加//<vector>以及＃include{//1.//用matrix<double>M(100);一個(gè)浮點(diǎn)的k×k的矩//M程序中創(chuàng)建一個(gè)二維矩陣就可以用這樣的語(yǔ)句其中double

l} Page//2.用名 //用整型變量i表示下標(biāo)，用 //M[i]＝M[j]；可以將矩陣的第j行拷貝到第i//3.typedefvector<ELEM>Mrow;typedefvector<Mrow>Mmatrix;Mmatrixamatrix;intmaxLength;

l} PageMmatrix<ELEM>m; Mmatrix<ELEM>m(k);//創(chuàng)建一個(gè)k×k的二維矩陣int }

l} Page1.4

l} Page 若干明確無(wú)誤的指令動(dòng)作，是一個(gè)有限的指令集。其結(jié)果應(yīng)具有確

l} Page

l} Page根據(jù)計(jì)算理論(theoryofcomputation)，存在著一類問(wèn)題雖然能夠被準(zhǔn)確定義，但卻不存在能夠解決該(computationalcomplexitytheory)，理論上存在一大類難解問(wèn)題，它們雖然存在著求解算法，但是在算法的計(jì)算時(shí)間上，都是組合型的求解算法

l} Page 的時(shí)間開(kāi)銷不能約束在n的k階多項(xiàng)式數(shù)量范圍內(nèi)。根據(jù)計(jì)算復(fù)雜性理論，難解問(wèn)題的定義就是它的求解意正整數(shù)）。比較常見(jiàn)的難解問(wèn)題有：圖論中的求最優(yōu)巡游路徑問(wèn)題，判定命題邏輯是否為恒真等

l} Page

l} Page 需占用的單元數(shù)量，字節(jié)數(shù)）。

l} Page 算法的漸進(jìn)分析就是要估計(jì)，當(dāng)數(shù)據(jù)規(guī)模n逐從數(shù)量級(jí)大小的比較來(lái)考慮，當(dāng)n增大到一定值以后，資源開(kāi)銷的計(jì)算中影響最大的就是n的冪次最高的項(xiàng)，其他的常數(shù)項(xiàng)和低冪次

l} Page ratenfi￥T(n)＝O(F(n)

l} Page矩陣求和（matrix_additionvoidmatrix_addition(double**M1,double**M2,int{k×kfor(inti=0;i<k;for(intj=0j<k;j++)//M1[i][j]=M1[i][j]+M2[i][j]}

l} Page矩陣求和（matrix_additionM1M2的尺寸 一次，需要p?r時(shí)間，其中p是一個(gè)常數(shù)倍數(shù)

l} Page矩陣求和（matrix_addition考慮到兩重嵌套的for循環(huán)，一共執(zhí)行k×k遍，因此，這個(gè)程序的時(shí)間開(kāi)銷的漸進(jìn)估計(jì)式可以寫為T(n＝p?rn＋C。其中C是一個(gè)不隨n而變化的常數(shù)，代表那些由此看出，矩陣加法的時(shí)間開(kāi)銷是和問(wèn)題規(guī)模n成正比為ratenfi￥T(n＝O(n，即F(n)=n

l} Page F(n 常數(shù)函數(shù)，不依賴于F(n)log F(nnn而增長(zhǎng)=ratenfi￥=F(nn2

l} Page F(n)= 如函數(shù)H(n)，令H(1)=1且H(n)=2H(n-1)那么通過(guò)遞推可以計(jì)算出H(n)=2(n-1)

l} Page的條件分支而遇到。計(jì)、和Theta（Q希塔）估計(jì)等三種方法

l} Pagedoubleabs_biggest(double**M,intdoublecurrent_big=0;//臨時(shí) for(inti=0;i<k;i++)for(intj=0j<k;j++){//doubletempfabs(M[i][j]);if(temp>current_big)current_bigtemp; }

l} Page 的情況下，每一次判斷(temp)>

l} Page對(duì)于時(shí)間開(kāi)銷，一般不注意算法的‘最好估計(jì)’。特別是處理應(yīng)急，計(jì)算機(jī)系統(tǒng)必須在規(guī)定的響應(yīng)時(shí)間內(nèi)做完緊急處理。這時(shí)，估計(jì)是唯一

l} Page很多算法使用的數(shù)據(jù)結(jié)構(gòu)是靜態(tài)的結(jié)構(gòu)，即

l} Page使用動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)算法的空間是

l} Page機(jī)的運(yùn)行時(shí)間，通過(guò)增大時(shí)間開(kāi)銷來(lái)?yè)Q取空間

l} Page稱Q希塔估計(jì)。它是前面討論的大O表示的擴(kuò)展?jié)u進(jìn)估計(jì)式F(n)，稱F(n)為T(n)的一個(gè)漸進(jìn)Q希塔正整數(shù)n>n0有下列兩不等式同時(shí)成立：|T(n)|C1F(n)|T(n)|<C2

l} Page開(kāi)銷T(n)的希塔估計(jì)，或稱Q估計(jì)

l}