電通班學(xué)習(xí)-數(shù)據(jù)結(jié)構(gòu)

第一章 緒論一、 數(shù)據(jù)結(jié)構(gòu)為什么要學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)舉例：1）2）3）本館中最短路徑的問題打印文件排隊叫號系統(tǒng)只要有數(shù)據(jù)的地方，就涉及到數(shù)據(jù)怎樣組織、排列的問題，即數(shù)據(jù)結(jié)構(gòu)。同樣的數(shù)據(jù)可以有不同的結(jié)構(gòu)。進一步研究：在某種結(jié)構(gòu)上怎樣進行數(shù)據(jù)處理一、 數(shù)據(jù)結(jié)構(gòu)為什么要學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)研究內(nèi)容：數(shù)據(jù)的不同結(jié)構(gòu)和組織方法在某種結(jié)構(gòu)上進行數(shù)據(jù)處理的不同算法算法的分析和比較

最佳方案二、數(shù)據(jù)結(jié)構(gòu)課程的發(fā)展及其地位數(shù)據(jù)結(jié)構(gòu)（DataStructure）是計算機軟件和計算機應(yīng)用等相關(guān)專業(yè)的一門課程，它所研究的對象是非數(shù)值計算中計算機操作的對象，以及對象之間的關(guān)系和操作等。二、數(shù)據(jù)結(jié)構(gòu)課程的發(fā)展及其地位計算機發(fā)展的初期，由于其價格昂貴，運算速度慢，容量有限，人們使用計算機主要是用于處理數(shù)值問題。其特點是計算量大，數(shù)據(jù)量小，程序設(shè)計者主要精力集中在程序設(shè)計的技巧上，無須重視數(shù)據(jù)結(jié)構(gòu)。二、數(shù)據(jù)結(jié)構(gòu)課程的發(fā)展及其地位隨著計算機技術(shù)的發(fā)展，“非數(shù)值問題”越來越顯得重要。計算機大量應(yīng)用于非數(shù)值計算領(lǐng)域，像工業(yè)領(lǐng)域、商業(yè)企業(yè)和

機構(gòu)的管理等領(lǐng)域。據(jù)統(tǒng)計，處理非數(shù)值問題占用了90%以上的機器時間。二、數(shù)據(jù)結(jié)構(gòu)課程的發(fā)展及其地位這些問題所涉及的數(shù)據(jù)量大，數(shù)據(jù)結(jié)構(gòu)復(fù)雜，數(shù)據(jù)之間的關(guān)系一般無法用數(shù)學(xué)方程式加以描述。解決此類問題的關(guān)鍵已不再是分析數(shù)學(xué)和計算方法，為了對其進行有效處理，必須研究數(shù)據(jù)自身的結(jié)構(gòu)。因而對于數(shù)據(jù)結(jié)構(gòu)的設(shè)計顯得尤為重要。二、數(shù)據(jù)結(jié)構(gòu)課程的發(fā)展及其地位20世紀(jì)60年代，

計算機界首先使用了數(shù)據(jù)結(jié)構(gòu)這一名稱。1968年

著名的計算機

唐·歐·

教授創(chuàng)立了數(shù)據(jù)結(jié)構(gòu)的最初體系，他在《計算機程序設(shè)計技巧》第一卷《基本算法》一書中，全面、系統(tǒng)的闡述了數(shù)據(jù)的邏輯結(jié)構(gòu)和

結(jié)構(gòu)，為數(shù)據(jù)結(jié)構(gòu)奠定了基礎(chǔ)。二、數(shù)據(jù)結(jié)構(gòu)課程的發(fā)展及其地位

人們普遍認(rèn)為程序設(shè)計實質(zhì)上是對實際問題選擇一種好的數(shù)據(jù)結(jié)構(gòu)，加上設(shè)計一個好的算法，而好的算法在很大程度上取決于描述實際問題的數(shù)據(jù)結(jié)構(gòu)。二、數(shù)據(jù)結(jié)構(gòu)課程的發(fā)展及其地位從70年代中期到80年代初期，人們對于數(shù)據(jù)結(jié)構(gòu)的研究逐漸產(chǎn)生了濃厚的，各種版本的數(shù)據(jù)結(jié)構(gòu)著作相繼出現(xiàn)。二、數(shù)據(jù)結(jié)構(gòu)課程的發(fā)展及其地位地位：是三種學(xué)科：數(shù)學(xué)、計算機硬件、

的邊緣學(xué)科，與上述三種學(xué)科都有密切關(guān)系。是一門計算機科學(xué)專業(yè)的 課程不僅是一般程序設(shè)計的基礎(chǔ)，而且是設(shè)計程序編譯系統(tǒng)、計算機操作系統(tǒng)、數(shù)據(jù)庫系統(tǒng)和其他系統(tǒng)程序和大型應(yīng)用程序的基礎(chǔ)因此學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)具有十分重要的意義。1.1

常用術(shù)語、數(shù)據(jù)（Data）：能被計算機輸入、處理和輸出的一切信息。數(shù)據(jù)元素（DataElement）：數(shù)據(jù)整體中相對獨立的單位數(shù)據(jù)記錄：組織數(shù)據(jù)的基本單位。用于把相互有關(guān)系的多個數(shù)據(jù)項組成一條記錄。數(shù)據(jù)處理：其基礎(chǔ)是數(shù)據(jù)結(jié)構(gòu)1.1

常用術(shù)語數(shù)據(jù)結(jié)構(gòu)：雖然至今沒有一個關(guān)于數(shù)據(jù)結(jié)構(gòu)的標(biāo)準(zhǔn)定義，但普遍認(rèn)為數(shù)據(jù)結(jié)構(gòu)應(yīng)當(dāng)包含以下面的內(nèi)容：邏輯結(jié)構(gòu)：數(shù)據(jù)間關(guān)系。邏輯結(jié)構(gòu)是從邏輯關(guān)系上描述數(shù)據(jù)，與具體

無關(guān)，與計算機無關(guān)。因此邏輯結(jié)構(gòu)可以看作是從具體問題抽象出來的數(shù)學(xué)模型。物理結(jié)構(gòu)：邏輯結(jié)構(gòu)在計算機中的

方式。數(shù)據(jù)的運算：是指對數(shù)據(jù)施加的操作。每種邏輯結(jié)構(gòu)都有一個運算的集合。常用的數(shù)據(jù)運算有：查找、排序、 、刪除、更新等操作。常用術(shù)語數(shù)據(jù)結(jié)構(gòu)：綜上所述， 可以將數(shù)據(jù)結(jié)構(gòu)定義為：按某種邏輯關(guān)系組織起來的一批數(shù)據(jù)，按一定的方式到計算機的 器中，并在這些數(shù)據(jù)之上定義一個運算的集合，就稱之為一個數(shù)據(jù)結(jié)構(gòu)。B=（K，R）數(shù)據(jù)結(jié)構(gòu)的表示方法：二元組——集合形式圖示法常用術(shù)語數(shù)據(jù)類型：1)

簡單類型2)

結(jié)構(gòu)類型抽象數(shù)據(jù)類型——類包括數(shù)據(jù)以及數(shù)據(jù)上的操作。數(shù)據(jù)對象——數(shù)據(jù)類型的具體化（常量和變量）算法：在某數(shù)據(jù)結(jié)構(gòu)上解決特定問題的方法。有5個特性。1.2

算法描述舉例1.3

算法評價正確性穩(wěn)健性可讀性時間復(fù)雜度空間復(fù)雜度1.3

算法評價使用絕對運行時間來衡量算法的優(yōu)劣是不科學(xué)的，因為這樣的統(tǒng)計依賴于計算機的軟、硬件環(huán)境等多種綜合因素，不單純反映算法的優(yōu)劣，容易掩蓋算法自身的特性。因此，通常是在不實際運行該算法的前提下，估算當(dāng)問題的規(guī)模擴大時，該算法的時間代價和空間代價。1.3

算法評價時間復(fù)雜度算法運行時間＝一次簡單操作的時間×簡單操作次數(shù)通常把算法中包含簡單操作的次數(shù)叫做該算法的時間復(fù)雜度，用它來衡量一個算法的運行時間性能。當(dāng)問題的規(guī)模為n時，算法的時間復(fù)雜度通常是一個n的函數(shù)f(n)【例】交換i和j的內(nèi)容。Temp=i；i=j；j=temp；以上三條單個語句的頻度均為1，該算法段的執(zhí)行時間是一個與問題規(guī)模n無關(guān)的常數(shù)。算法的時間復(fù)雜度為常數(shù)階，記作f(n)=Ο(1)。如果算法的執(zhí)行時間不隨著問題規(guī)模n的增加而增長，即使算法中有上千條語句,其執(zhí)行時間也不過是一個較大的常數(shù)。此類算法的時間復(fù)雜度是Ο(1)?！纠垦h(huán)語句當(dāng)有若干個循環(huán)語句時，算法的時間復(fù)雜度是由嵌套層數(shù)最多的循環(huán)語句中最內(nèi)層語句的頻度f(n)決定的。x=0；for

（k=1；k<=n

；k++）x=x+1；for

（i=1；i<=n

；i++）for

（j=1；j<=n

；j++）y=y+1；該算法段的時間復(fù)雜度為f(n)=O(n2)int

fact(int

n){if

(n==0)

or

(n==1)return

1;else return

(n*fact(n-1));}以n=3為例,調(diào)用過程如下：fact(3)-fact(2)-fact(1)-fact(2)-fact(3)遞

歸

回

溯【例】遞歸算n法！——遞歸算法如下：【例】遞歸算法

——

n！分析：

f(n)=f(n-1)+O(1)其中O(1)為一次乘法操作.迭代求解過程如下：f(n)=f(n-1)+O(1)=f(n-2)+O(1)+O(1)=f(n-3)+O(1)+O(1)+O(1)……=f(1)+……+O(1)+O(1)+O(1)=n*O(1)=O(n)算法時間復(fù)雜度的計算量級表示時間復(fù)雜度的主要運算規(guī)則如下：（1）加

則：

O

(f(n))+O

(g(n))

=O

(max

(f(n),g(n)

)（2）

乘

則：

O(f(n))

*

O(

g(n))

=O

(

f(n)

*

g(n)

)算法的時間復(fù)雜度還與輸入的初始狀態(tài)有關(guān)。這類算法的時間復(fù)雜度的分析比較復(fù)雜，一般分最好情況（處理最少的情況),

情況(處理最多的情況)和平均情況分別進行討論?！纠吭跀?shù)組a[n]中查找給定值為key的算法：for（int

i=0;i<n;i++）if

(a[i]==key)

return

i;return

-1；此算法的時間復(fù)雜度不僅與問題規(guī)模n有關(guān)，還與數(shù)組a的各元素取值及key的取值有關(guān)：最好情況：a[0]==key，只需比較1次，f(n)=O(1)。情況：若a[n-1]==key或a中沒有與key相等的元素,則需要比較n次，f(n)=O(n)?！?pi

×(i+1))i=0n-11n(1+2+……+n)=

?(n+1)=3.平均情況：∑（a[i]==key的概率×比較次數(shù)）通常假定查找不同元素的概率p是相同的,則算法的平均復(fù)雜度為：若對于查找不同元素的概率p不相同時，其算法復(fù)雜度就只能做近似分析。算法的空間復(fù)雜度算法所占用的

空間包括：算法本身所占空間輸入/輸出數(shù)據(jù)所占空間輔助變量所占空間其中，前兩個空間是計算機運行時所必須的，因此通常把算法執(zhí)行時所需的輔助空間作為分析算法空間復(fù)雜度的依據(jù)。算法的空間復(fù)雜度對于同一個問題，采用不同的算法，所需的輔助

空間往往是不一樣的。常見的空間復(fù)雜度也表示為O(1)、O(n)、O(n2)、O(n3)等。如果所需輔助空間相對于輸入數(shù)據(jù)量（規(guī)模為n）來說是個常數(shù)，即不隨問題規(guī)模大小而改變，則稱這種算法為“就地”進行，空間復(fù)雜度為O(1)算法的復(fù)雜度在一個算法的實現(xiàn)中，時間復(fù)雜度和空間復(fù)雜度往往是相互的。若要減少算法的執(zhí)行時間，就要以犧牲空間為代價；反之，若要節(jié)省空間，就可能要增加算法的執(zhí)行時間。二者很難兼顧。實際應(yīng)用中，要根據(jù)具體情況有所側(cè)重。30數(shù)據(jù)類型空類型void整字符型型int

單字符型char實

型雙精度型double邏輯型bool寬字符型w_char單精度型float結(jié)構(gòu)struct聯(lián)合union枚舉enum數(shù)

組type[

]指

針type*類class非基本數(shù)據(jù)類型數(shù)據(jù)類型基本數(shù)據(jù)類型對象的概念每個對象都有各自的

狀態(tài)和行為特點。對象（Object）由屬性（Attribute）和行為（Action）兩部分組成。屬性是行為是對象靜態(tài)特征的一個數(shù)據(jù)項。對象動態(tài)特征的一個操作。對象是屬性和行為的封裝體。類的概念類（Class）是具有相同屬性和行為的一組對象集合的再抽象。從語言角度來說，類是一種用戶自定義數(shù)據(jù)類型，而對象是具有這種類型的變量。例：下面是一年12個月的數(shù)據(jù)結(jié)構(gòu)的二元組表示方法。B=（K，