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

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

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

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

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

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

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

6、”是一個類，“王老師”、“李老師”等對象都是“教師”類的實例?！　　∮捎趯ο螅悾⒚芮邢嚓P的屬性（數(shù)據(jù)）和方法（操作）定義為一個整體，從而實現(xiàn)了封裝和信息隱藏。使用類時，無需了解其內(nèi)部的實現(xiàn)細節(jié)，一旦數(shù)據(jù)（結構）修改了，只需修改類內(nèi)部的局部代碼，軟件系統(tǒng)的其余部分無需修改。　　　數(shù)據(jù)結構主要強調兩個方面的內(nèi)容：①數(shù)據(jù)之間的關系；②針對這些關系的基本操作。這兩個方面實際上蘊涵著面向對象的思想：類重點描述實體的狀態(tài)與行為，而數(shù)據(jù)結構重點描述數(shù)據(jù)之間的關系及其基本操作，數(shù)據(jù)及其相互關系構成了對實體狀態(tài)的描述，針對數(shù)據(jù)元素之間關系的操作構

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

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