本章主要介紹以下內(nèi)容

《本章主要介紹以下內(nèi)容》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、第1章緒論本章主要介紹以下內(nèi)容1、數(shù)據(jù)結(jié)構(gòu)中涉及的基本概念、術(shù)語及所研究的主要內(nèi)容2、本教材使用的描述工具本章重點(diǎn)和難點(diǎn)：1、數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)類型、ADT、算法等重要概念?！　　∮糜?jì)算機(jī)求解任何問題都離不開程序設(shè)計(jì)，而程序設(shè)計(jì)的實(shí)質(zhì)是數(shù)據(jù)表示和數(shù)據(jù)處理。數(shù)據(jù)要能被計(jì)算機(jī)處理，首先必須能夠存儲(chǔ)在計(jì)算機(jī)的內(nèi)存中，這項(xiàng)任務(wù)稱為數(shù)據(jù)表示，數(shù)據(jù)表示的核心任務(wù)是數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)；一個(gè)實(shí)際問題的求解必須滿足各項(xiàng)處理要求，這項(xiàng)任務(wù)稱為數(shù)據(jù)處理，數(shù)據(jù)處理的核心任務(wù)是算法設(shè)計(jì)。數(shù)據(jù)結(jié)構(gòu)課程主要討論數(shù)據(jù)表示和數(shù)據(jù)處理的基本問題。本章將概括地介紹數(shù)據(jù)結(jié)構(gòu)的基本

2、概念、基本思想和基本方法。1.1數(shù)據(jù)結(jié)構(gòu)的興起和發(fā)展　　　數(shù)據(jù)結(jié)構(gòu)起源于程序設(shè)計(jì)。隨著計(jì)算機(jī)科學(xué)與技術(shù)的不斷發(fā)展，計(jì)算機(jī)的應(yīng)用領(lǐng)域已不再局限于科學(xué)計(jì)算，而更多地應(yīng)用于控制、管理等非數(shù)值處理領(lǐng)域。與此相應(yīng)，計(jì)算機(jī)處理的數(shù)據(jù)也由純粹的數(shù)值發(fā)展到字符、表格、圖形、圖象、聲音等具有一定結(jié)構(gòu)的數(shù)據(jù)，處理的數(shù)據(jù)量也越來越大，這就給程序設(shè)計(jì)帶來一個(gè)問題：應(yīng)如何組織待處理的數(shù)據(jù)以及數(shù)據(jù)之間的關(guān)系（結(jié)構(gòu)）?！　　?968年克努思教授[1]開創(chuàng)了數(shù)據(jù)結(jié)構(gòu)的最初體系，他所著的《計(jì)算機(jī)程序設(shè)計(jì)藝術(shù)》第一卷《基本算法》是第一本較系統(tǒng)地闡述數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲(chǔ)

3、結(jié)構(gòu)及其操作的著作。70年代初，數(shù)據(jù)結(jié)構(gòu)作為一門獨(dú)立的課程開始進(jìn)入大學(xué)課堂?！　　?shù)據(jù)結(jié)構(gòu)隨著程序設(shè)計(jì)的發(fā)展而發(fā)展。程序設(shè)計(jì)經(jīng)歷了三個(gè)階段：無結(jié)構(gòu)階段、結(jié)構(gòu)化階段和面向?qū)ο箅A段，相應(yīng)地，數(shù)據(jù)結(jié)構(gòu)的發(fā)展也經(jīng)歷了三個(gè)階段：⑴無結(jié)構(gòu)階段?！　　?0~60年代，計(jì)算機(jī)的應(yīng)用主要針對(duì)科學(xué)計(jì)算，程序設(shè)計(jì)技術(shù)以機(jī)器語言/匯編語言為主，程序處理的數(shù)據(jù)是純粹的數(shù)值，數(shù)據(jù)之間的關(guān)系主要是數(shù)學(xué)公式或數(shù)學(xué)模型。這一階段，在人類的自然語言與計(jì)算機(jī)編程語言之間存在著巨大的鴻溝，程序設(shè)計(jì)屬于面向計(jì)算機(jī)的程序設(shè)計(jì)，設(shè)計(jì)人員關(guān)注的重心是使程序盡可能地被計(jì)算機(jī)接受并按

4、指令正確執(zhí)行，至于程序能否讓人理解并不重要。⑵結(jié)構(gòu)化階段?！　　?0~80年代，計(jì)算機(jī)開始廣泛應(yīng)用于非數(shù)值處理領(lǐng)域，數(shù)據(jù)表示成為程序設(shè)計(jì)的重要問題，人們認(rèn)識(shí)到程序設(shè)計(jì)規(guī)范化的重要性，提出了程序結(jié)構(gòu)模塊化，并開始注意數(shù)據(jù)表示與操作的結(jié)構(gòu)化。數(shù)據(jù)結(jié)構(gòu)及抽象數(shù)據(jù)類型就是在這種情況下形成的。數(shù)據(jù)結(jié)構(gòu)概念的引入，對(duì)程序設(shè)計(jì)的規(guī)范化起到了重大作用。圖靈[2]獎(jiǎng)獲得者沃思[3]給出了一個(gè)著名的公式：數(shù)據(jù)結(jié)構(gòu)+算法=程序。從這個(gè)公式可以看到，數(shù)據(jù)結(jié)構(gòu)和算法是構(gòu)成程序的兩個(gè)重要的組成部分，一個(gè)軟件系統(tǒng)通常是以一個(gè)或幾個(gè)關(guān)鍵數(shù)據(jù)結(jié)構(gòu)為核心而組織的?！　?/p>

5、　隨著軟件系統(tǒng)的規(guī)模越來越大、復(fù)雜性不斷增加，人們不得不對(duì)結(jié)構(gòu)化技術(shù)重新評(píng)價(jià)。由于軟件系統(tǒng)的實(shí)現(xiàn)依賴于關(guān)鍵數(shù)據(jù)結(jié)構(gòu)，如果這些關(guān)鍵數(shù)據(jù)結(jié)構(gòu)的一個(gè)或幾個(gè)有所改變，則涉及到整個(gè)系統(tǒng)，甚至導(dǎo)致整個(gè)系統(tǒng)徹底崩潰。⑶面向?qū)ο箅A段。　　　面向?qū)ο蠹夹g(shù)（首先是面向?qū)ο蟪绦蛟O(shè)計(jì)）始于80年代初，是目前最流行的程序設(shè)計(jì)技術(shù)。在面向?qū)ο蠹夹g(shù)中，問題世界的相關(guān)實(shí)體被視為一個(gè)對(duì)象，對(duì)象由屬性和方法構(gòu)成，屬性用以描述實(shí)體的狀態(tài)或特征，方法用以改變實(shí)體的狀態(tài)或描述實(shí)體的行為。一組具有相同屬性和方法的對(duì)象的集合抽象為類，每個(gè)具體的對(duì)象都是類的一個(gè)實(shí)例。例如，“教師

6、”是一個(gè)類，“王老師”、“李老師”等對(duì)象都是“教師”類的實(shí)例。　　　由于對(duì)象（類）將密切相關(guān)的屬性（數(shù)據(jù)）和方法（操作）定義為一個(gè)整體，從而實(shí)現(xiàn)了封裝和信息隱藏。使用類時(shí)，無需了解其內(nèi)部的實(shí)現(xiàn)細(xì)節(jié)，一旦數(shù)據(jù)（結(jié)構(gòu)）修改了，只需修改類內(nèi)部的局部代碼，軟件系統(tǒng)的其余部分無需修改?！　　?shù)據(jù)結(jié)構(gòu)主要強(qiáng)調(diào)兩個(gè)方面的內(nèi)容：①數(shù)據(jù)之間的關(guān)系；②針對(duì)這些關(guān)系的基本操作。這兩個(gè)方面實(shí)際上蘊(yùn)涵著面向?qū)ο蟮乃枷耄侯愔攸c(diǎn)描述實(shí)體的狀態(tài)與行為，而數(shù)據(jù)結(jié)構(gòu)重點(diǎn)描述數(shù)據(jù)之間的關(guān)系及其基本操作，數(shù)據(jù)及其相互關(guān)系構(gòu)成了對(duì)實(shí)體狀態(tài)的描述，針對(duì)數(shù)據(jù)元素之間關(guān)系的操作構(gòu)

7、成了對(duì)實(shí)體行為的描述。由此可見，類與數(shù)據(jù)結(jié)構(gòu)之間具有對(duì)應(yīng)關(guān)系，如圖1-1所示?！　　　皵?shù)據(jù)結(jié)構(gòu)+算法=程序”這個(gè)公式在軟件開發(fā)的進(jìn)程中曾產(chǎn)生了深遠(yuǎn)的影響，但是，它并沒有強(qiáng)調(diào)數(shù)據(jù)結(jié)構(gòu)與解決問題的算法是一個(gè)整體，因此有人主張將它修改為“（數(shù)據(jù)結(jié)構(gòu)+算法）=程序”，以體現(xiàn)面向?qū)ο蟮乃枷??！　　≈档米⒁獾氖?，?shù)據(jù)結(jié)構(gòu)的發(fā)展并未終結(jié)。一方面，數(shù)據(jù)結(jié)構(gòu)將繼續(xù)隨著程序設(shè)計(jì)的發(fā)展而發(fā)展；另一方面，面向各專門領(lǐng)域的數(shù)據(jù)結(jié)構(gòu)得到研究和發(fā)展，各種實(shí)用的高級(jí)數(shù)據(jù)結(jié)構(gòu)被研究出來，各種空間數(shù)據(jù)結(jié)構(gòu)也在探索中。[1]克努思（Donald.E.Knuth，1938

8、年生）從小就是個(gè)優(yōu)秀的學(xué)生，多次獲得學(xué)業(yè)成就獎(jiǎng)。1963年擔(dān)任加利福尼亞理工學(xué)院的教師，1968年擔(dān)任斯坦福大學(xué)教授。1992年為集中精力寫作而榮譽(yù)退休，保留教授頭銜。他特別感興趣的是為《計(jì)算機(jī)程序設(shè)計(jì)藝術(shù)》叢書完成新卷并更新舊卷。這