數(shù)據(jù)結(jié)構(gòu)研究的內(nèi)容.ppt

1、第一講：數(shù)據(jù)結(jié)構(gòu)及其研究的內(nèi)容Data Structure Curriculum int age; bool sex; char position20; char pos_rank20; char department20; RecordType ;,數(shù)據(jù)在計算機(jī)中表示方式： 順序映像（順序存儲結(jié)構(gòu)）：以相 對的存儲位置表示后繼 關(guān)系。如前述的職工檔案管理程序，所有職工的紀(jì)錄組成一張表，這張表就使一個順序存儲結(jié)構(gòu)。計算機(jī)在為這張表分配存儲空間時分配一個連續(xù)的存儲空間。 非順序映像（鏈?zhǔn)酱鎯Y(jié)構(gòu)）：,鏈?zhǔn)酱鎯Y(jié)構(gòu)里相鄰節(jié)點(diǎn)間的具體存儲位置不是一個順序關(guān)系，查詢節(jié)點(diǎn)需要借助于指針。 在不同的編程環(huán)

2、境中， 存儲結(jié)構(gòu)可有不同的描 述方法。當(dāng)用高級程序 設(shè)計語言進(jìn)行編程時， 通?？捎酶呒壘幊陶Z言 中提供的數(shù)據(jù)類型描述 之。,5、數(shù)據(jù)類型： 在程序設(shè)計時，我們必須先對變量進(jìn)行聲明，不同的數(shù)據(jù)類型他的取值范圍不同，施加其上的操作也不同： 如：整型 （int） 取值范圍：-32768 32767 可行的操作：+，-，*，/，% 對于浮點(diǎn)型來說，不可以進(jìn)行% 操作。,數(shù)據(jù)類型 是一個值的集合和定義在此集合上的一組操作的總稱。 盡管同一個數(shù)據(jù)類型在不同的CPU上處理的方法不同，對程序原來說他們是相同的，程序員可以不考慮具體機(jī)器的實(shí)現(xiàn)方法。也就是說這些數(shù)據(jù)類型僅僅取決于它的邏輯特性，與在計算機(jī)內(nèi)的實(shí)現(xiàn)無

3、關(guān)。在數(shù)學(xué)抽象的角度上看可以稱之為抽象數(shù)據(jù)類型。,抽象數(shù)據(jù)類型： （Abstract Data Type ：ADT） 抽象數(shù)據(jù)類型是指一個數(shù)學(xué)模型以及定義在該模型上的一組操作。 抽象數(shù)據(jù)類型可以用一個三元組來表示：（D，S，P） D是數(shù)據(jù)對象，S是D上的關(guān)系集，P是D的基本的操作集 。,ADT 抽象數(shù)據(jù)類型名 數(shù)據(jù)對象：數(shù)據(jù)對象的定義 數(shù)據(jù)關(guān)系：數(shù)據(jù)關(guān)系的定義 基本操作：基本操作的定義 ADT 抽象數(shù)據(jù)類型名 如：定義復(fù)數(shù)的抽象數(shù)據(jù)類型,ADT Complex 數(shù)據(jù)對象： De1,e2e1,e2RealSet 數(shù)據(jù)關(guān)系： R1 | e1是復(fù)數(shù)的實(shí)數(shù)部分, e2 是復(fù) 數(shù)的虛數(shù)部分 基本操作：

4、AssignComplex( for(int i=0;in;i+) s+=i; 問題的規(guī)模是n,程序的運(yùn)算工作量和n成線性的增長關(guān)系 ，或者說它可以看作是n的函數(shù)f(n)。,隨著規(guī)模的增大，算法執(zhí)行所需要的時間的增長率和f(n)的增長率是相同的。用時間復(fù)雜度來表示算法的時間效率， T (n) = O(f(n) 稱T (n) 為算法的(漸近)時間復(fù)雜度,如何估算時間復(fù)雜度？ 算法 = 控制結(jié)構(gòu) + 原操作 （固有數(shù)據(jù)類型的操作） 算法的執(zhí)行時間 = 原操作的執(zhí)行次數(shù)原操作的執(zhí)行時間,算法的實(shí)行時間和原操作的執(zhí)行次數(shù)是成正比的。從算法中選取一種對于所研究的問題來說是基本操作的原操作，以該基本操作在

5、算法中重復(fù)執(zhí)行的次數(shù)作為算法運(yùn)行時間的衡量準(zhǔn)則。,如上例中，時間復(fù)雜度為O(n) 例： （a） +x;s+=x; （b）for (i=1;i=n;+i) +x;s+=x; （c）for (j=1;j=n;+j) for (k=1;k=n;k+)+x;s+=x; 基本操作： +x;s+=x; a的執(zhí)行次數(shù)：1 時間復(fù)雜度O(1) b的實(shí)行次數(shù)：n 時間復(fù)雜度O(n) c的執(zhí)行次數(shù)：n2 時間復(fù)雜度O(n2),例：兩矩陣相乘 #define n 100 void MatrixMultiply(int Ann,int Bnn,int Cnn) int i,j,k for (i=1;i=n;+i) n+1 for (j=1;j=n;+j) n*(n+1) Cij=0; n2 for (k=1;k=n,k+) n2(