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

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

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

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

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

著名的計(jì)算機(jī)

唐·歐·

教授創(chuàng)立了數(shù)據(jù)結(jié)構(gòu)的最初體系，他在《計(jì)算機(jī)程序設(shè)計(jì)技巧》第一卷《基本算法》一書中，全面、系統(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è)計(jì)實(shí)質(zhì)上是對(duì)實(shí)際問(wèn)題選擇一種好的數(shù)據(jù)結(jié)構(gòu)，加上設(shè)計(jì)一個(gè)好的算法，而好的算法在很大程度上取決于描述實(shí)際問(wèn)題的數(shù)據(jù)結(jié)構(gòu)。二、數(shù)據(jù)結(jié)構(gòu)課程的發(fā)展及其地位從70年代中期到80年代初期，人們對(duì)于數(shù)據(jù)結(jié)構(gòu)的研究逐漸產(chǎn)生了濃厚的，各種版本的數(shù)據(jù)結(jié)構(gòu)著作相繼出現(xiàn)。二、數(shù)據(jù)結(jié)構(gòu)課程的發(fā)展及其地位地位：是三種學(xué)科：數(shù)學(xué)、計(jì)算機(jī)硬件、

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

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

常用術(shù)語(yǔ)數(shù)據(jù)結(jié)構(gòu)：雖然至今沒(méi)有一個(gè)關(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ù)，與具體

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

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

簡(jiǎn)單類型2)

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

算法描述舉例1.3

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

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

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

歸

回

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

——

n！分析：

f(n)=f(n-1)+O(1)其中O(1)為一次乘法操作.迭代求解過(guò)程如下：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)算法時(shí)間復(fù)雜度的計(jì)算量級(jí)表示時(shí)間復(fù)雜度的主要運(yùn)算規(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)

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

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

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

(a[i]==key)

return

i;return

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

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

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

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

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

單字符型char實(shí)

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

組type[

]指

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

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