數(shù)據(jù)結(jié)構(gòu)發(fā)展史

1、題目：數(shù)據(jù)結(jié)構(gòu)發(fā)展史綜述學(xué)院：電子信息專業(yè)：通信工程班級：122學(xué)號：31學(xué)生姓名：吳敏2014年3月15日前言3第二章數(shù)據(jù)結(jié)構(gòu)主要研究什么？6第三章數(shù)據(jù)結(jié)構(gòu)的史源7第四章數(shù)據(jù)結(jié)構(gòu)的飛速發(fā)展8第五章數(shù)據(jù)結(jié)構(gòu)發(fā)展的三階段9第六章數(shù)據(jù)結(jié)構(gòu)的前景11隨著計算機科學(xué)與技術(shù)的不斷發(fā)展，計算機的應(yīng)用領(lǐng)域已不再局限于科學(xué)計算，而更多地應(yīng)用于控制、管理等非數(shù)值處理領(lǐng)域。與此相應(yīng)，計算機處理的數(shù)據(jù)也由純粹的數(shù)值發(fā)展到字符、表格、圖形、圖象、聲音等具有一定結(jié)構(gòu)的數(shù)據(jù)，處理的數(shù)據(jù)量也越來越大，這就給程序設(shè)計帶來一個問題：應(yīng)如何組織待處理的數(shù)據(jù)以及數(shù)據(jù)之間的關(guān)系(結(jié)構(gòu))。數(shù)據(jù)結(jié)構(gòu)技術(shù)從誕生到現(xiàn)在，在不到半個世紀的時間

2、里，形成了堅實的理論基礎(chǔ)、成熟的商業(yè)產(chǎn)品和廣泛的應(yīng)用領(lǐng)域，吸引越來越多的研究者加入。數(shù)據(jù)結(jié)構(gòu)的誕生和發(fā)展給計算機信息管理帶來了一場巨大的革命。三十多年來，它已成為企業(yè)、部門乃至個人日常工作、生產(chǎn)和生活的基礎(chǔ)設(shè)施。同時，隨著應(yīng)用的擴展與深入，數(shù)據(jù)結(jié)構(gòu)的數(shù)量和規(guī)模越來越大，數(shù)據(jù)結(jié)構(gòu)的研究領(lǐng)域也已經(jīng)大大地拓廣和深化了。30年間數(shù)據(jù)結(jié)構(gòu)領(lǐng)域獲得了三次計算機圖靈獎(.Bachman,),更加充分地說明了數(shù)據(jù)結(jié)構(gòu)是一個充滿活力和創(chuàng)新精神的領(lǐng)域。就讓我們沿著歷史的軌跡，追溯一下數(shù)據(jù)結(jié)構(gòu)的發(fā)展歷程。第一章什么是數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)是指同一數(shù)據(jù)元素類中各數(shù)據(jù)元素之間存在的關(guān)系。數(shù)據(jù)結(jié)構(gòu)分別為邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)（物理

3、結(jié)構(gòu)）和數(shù)據(jù)的運算。數(shù)據(jù)的邏輯結(jié)構(gòu)是對數(shù)據(jù)之間關(guān)系的描述，有時就把邏輯結(jié)構(gòu)簡稱為數(shù)據(jù)結(jié)構(gòu)。邏輯結(jié)構(gòu)形式地定義為（K,R）（或（D,S）,其中，K是數(shù)據(jù)元素的有限集，R是K上的關(guān)系的有限集。數(shù)據(jù)結(jié)構(gòu)是在整個計算機科學(xué)與技術(shù)領(lǐng)域上廣泛被使用的術(shù)語。它用來反映一個數(shù)據(jù)的內(nèi)部構(gòu)成，即一個數(shù)據(jù)由那些成分數(shù)據(jù)構(gòu)成，以什么方式構(gòu)成，呈什么結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)有邏輯上的數(shù)據(jù)結(jié)構(gòu)和物理上的數(shù)據(jù)結(jié)構(gòu)之分。邏輯上的數(shù)據(jù)結(jié)構(gòu)反映成分數(shù)據(jù)之間的邏輯關(guān)系，而物理上的數(shù)據(jù)結(jié)構(gòu)反映成分數(shù)據(jù)在計算機內(nèi)部的存儲安排。數(shù)據(jù)結(jié)構(gòu)是數(shù)據(jù)存在的形式。數(shù)據(jù)結(jié)構(gòu)信息的一種組織方式，其目的是為了提高算法的效率，它通常與一組算法的集合相對應(yīng)，通過這組

4、算法集合可以對數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)進行某種操作。數(shù)據(jù)結(jié)構(gòu)在計算機中的表示（映像）稱為數(shù)據(jù)的物理（存儲）結(jié)構(gòu)。它包括數(shù)據(jù)元素的表示和關(guān)系的表示。數(shù)據(jù)元素之間的關(guān)系有兩種不同的表示方法：順序映象和非順序映象，并由此得到兩種不同的存儲結(jié)構(gòu)：順序存儲結(jié)構(gòu)和鏈式存儲結(jié)構(gòu)。順序存儲方法：它是把邏輯上相鄰的結(jié)點存儲在物理位輅相鄰的存儲單元里，結(jié)點間的邏輯關(guān)系由存儲單元的鄰接關(guān)系來體現(xiàn)，由此得到的存儲表示稱為順序存儲結(jié)構(gòu)。順序存儲結(jié)構(gòu)是一種最基本的存儲表示方法，通常借助于程序設(shè)計語言中的數(shù)組來實現(xiàn)。鏈接存儲方法：它不要求邏輯上相鄰的結(jié)點在物理位輅上亦相鄰，結(jié)點間的邏輯關(guān)系是由附加的指針字段表示的。由此得到的存儲表

5、示稱為鏈式存儲結(jié)構(gòu)，鏈式存儲結(jié)構(gòu)通常借助于程序設(shè)計語言中的指針類型來實現(xiàn)。索引存儲方法：除建立存儲結(jié)點信息外，還建立附加的索引表來標識結(jié)點的地址。散列存儲方法：就是根據(jù)結(jié)點的關(guān)鍵字直接計算出該結(jié)點的存儲地址。第二章數(shù)據(jù)結(jié)構(gòu)主要研究什么?數(shù)據(jù)結(jié)構(gòu)作為一門學(xué)科主要研究數(shù)據(jù)的各種邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)，以及對數(shù)據(jù)的各種操作。因此，主要有三個方面的內(nèi)容：數(shù)據(jù)的邏輯結(jié)構(gòu)；數(shù)據(jù)的物理存儲結(jié)構(gòu)；對數(shù)據(jù)的操作（或算法）。通常，算法的設(shè)計取決于數(shù)據(jù)的邏輯結(jié)構(gòu)，算法的實現(xiàn)取決于數(shù)據(jù)的物理存儲結(jié)構(gòu)。其具體的最主要內(nèi)容有以下幾點：1.數(shù)據(jù)的各種邏輯結(jié)構(gòu)和物理結(jié)構(gòu)，以及他們之間的相應(yīng)關(guān)系2,并對每種結(jié)構(gòu)定義相適應(yīng)的各種運算

6、3 .設(shè)計出相應(yīng)的算法4 .分析算法的效率第三章數(shù)據(jù)結(jié)構(gòu)的史源1968年在美國開設(shè)。它隨著大型程序的出現(xiàn)而出現(xiàn)。“數(shù)據(jù)結(jié)構(gòu)”作為一門獨立的課程在國外是從1968年才開始設(shè)立的。1968年美國唐？歐?克努特教授開創(chuàng)了數(shù)據(jù)結(jié)構(gòu)的最初體系，他所著的計算機程序設(shè)計技巧第一卷基本算法是第一本較系統(tǒng)地闡述數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)及其操作的著作。“數(shù)據(jù)結(jié)構(gòu)”在計算機科學(xué)中是一門綜合性的專業(yè)基礎(chǔ)課。數(shù)據(jù)結(jié)構(gòu)是介于數(shù)學(xué)、計算機硬件和計算機軟件三者之間的一門核心課程。數(shù)據(jù)結(jié)構(gòu)這一門課的內(nèi)容不僅是一般程序設(shè)計(特別是非數(shù)值性程序設(shè)。1968年克努思教授開創(chuàng)了數(shù)據(jù)結(jié)構(gòu)的最初體系，他所著的計算機程序設(shè)計藝術(shù)第一卷基本算

7、法是第一本較系統(tǒng)地闡述數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)及其操作的著作。70年代初，數(shù)據(jù)結(jié)構(gòu)作為一門獨立的課程開始進入大學(xué)課堂。數(shù)據(jù)結(jié)構(gòu)在計算機科學(xué)界至今沒有標準的定義。個人根據(jù)各自的理解的不同而有不同的表述方法。例的數(shù)據(jù)元素之間的各種聯(lián)系。這些聯(lián)系可以通過定義相關(guān)的函數(shù)來給出?！彼麑?shù)據(jù)對象(dataobject)定義為“一個數(shù)據(jù)對象是實例或值的集合”。數(shù)據(jù)結(jié)構(gòu)在計算機科學(xué)界至今沒有標準的定義。個人根據(jù)各自的理解的不同而有不同的表述方法。SartajSahni在他的數(shù)據(jù)結(jié)構(gòu)、算法與應(yīng)用一書中稱：“數(shù)據(jù)結(jié)構(gòu)是數(shù)據(jù)對象，以及存在于該對象的實例和組成實Clifford在數(shù)據(jù)結(jié)構(gòu)與算法分析一書中的定義是：“數(shù)

8、據(jù)結(jié)構(gòu)的物理實現(xiàn)是ADT（抽象數(shù)據(jù)類型AbstractDataType）第四章數(shù)據(jù)結(jié)構(gòu)的飛速發(fā)展自從美國唐歐克努特教授用匯編語言編寫的計算機程序設(shè)計技巧第一卷基本算法問世以來，已經(jīng)出現(xiàn)了用Pascal、Java、C、C+C懈語言編寫的數(shù)據(jù)結(jié)構(gòu)方面的書。總體說來，這些語言基本上分為面向過程的語言和面向?qū)ο蟮恼Z言兩大類，也出現(xiàn)過采用兩種語言描述數(shù)據(jù)結(jié)構(gòu)的書籍，如C和C+畸言描述，但作者實際上是按照C+畸言描述。同時采用面向過程和面向?qū)ο笳Z言描述數(shù)據(jù)結(jié)構(gòu)，目前國內(nèi)基本上是空白。對于同一種數(shù)據(jù)結(jié)構(gòu)與算法，同時采用面向過程和面向?qū)ο笳Z言進行描述，可以從中更深刻理解這兩種思想的不同，這對于深刻理解計算機語

9、言和思想有著重要的作用。C語言是現(xiàn)在最流行的面向過程的語言，在業(yè)界使用非常廣泛。而C虢言作為微軟在新一代開發(fā)平臺（.NET）上推出的、完全面向?qū)ο蟮恼Z言，憑著其簡潔、高效、模板、標準化的特性，使得C貂言像程序設(shè)計語言中的一件藝術(shù)品，也吸引著越來越多的開發(fā)人員。當然，C#WC是相似的。第五章數(shù)據(jù)結(jié)構(gòu)發(fā)展的三階段數(shù)據(jù)結(jié)構(gòu)隨著程序設(shè)計的發(fā)展而發(fā)展。程序設(shè)計經(jīng)歷了三個階段：無結(jié)構(gòu)階段、結(jié)構(gòu)化階段和面向?qū)ο箅A段，相應(yīng)地，數(shù)據(jù)結(jié)構(gòu)的發(fā)展也經(jīng)歷了三個階段：無結(jié)構(gòu)階段。4060年代，計算機的應(yīng)用主要針對科學(xué)計算，程序設(shè)計技術(shù)以機器語言/匯編語言為主，程序處理的數(shù)據(jù)是純粹的數(shù)值，數(shù)據(jù)之間的關(guān)系主要是數(shù)學(xué)公式或數(shù)

10、學(xué)模型。這一階段，在人類的自然語言與計算機編程語言之間存在著巨大的鴻溝，程序設(shè)計屬于面向計算機的程序設(shè)計，設(shè)計人員關(guān)注的重心是使程序盡可能地被計算機接受并按指令正確執(zhí)行，至于程序能否讓人理解并不重要。結(jié)構(gòu)化階段。6080年代，計算機開始廣泛應(yīng)用于非數(shù)值處理領(lǐng)域，數(shù)據(jù)表示成為程序設(shè)計的重要問題，人們認識到程序設(shè)計規(guī)范化的重要性，提出了程序結(jié)構(gòu)模塊化，并開始注意數(shù)據(jù)表示與操作的結(jié)構(gòu)化。數(shù)據(jù)結(jié)構(gòu)及抽象數(shù)據(jù)類型就是在這種情況下形成的。數(shù)據(jù)結(jié)構(gòu)概念的引入，對程序設(shè)計的規(guī)范化起到了重大作用。圖靈2獎獲得者沃思3給出了一個著名的公式：數(shù)據(jù)結(jié)構(gòu)+算法=程序。從這個公式可以看到，數(shù)據(jù)結(jié)構(gòu)和算法是構(gòu)成程序的兩個重

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

12、是一個類，“王老師”、“李老師”等對象都是“教師”類的實例。由于對象（類）將密切相關(guān)的屬性（數(shù)據(jù)）和方法（操作）定義為一個整體，從而實現(xiàn)了封裝和信息隱藏。使用類時，無需了解其內(nèi)部的實現(xiàn)細節(jié)，一旦數(shù)據(jù)（結(jié)構(gòu)）修改了，只需修改類內(nèi)部的局部代碼，軟件系統(tǒng)的其余部分無需修改。第六章數(shù)據(jù)結(jié)構(gòu)的前景1 .數(shù)據(jù)結(jié)構(gòu)將繼續(xù)隨著程序設(shè)計的發(fā)展而發(fā)展；2 .面向各專門領(lǐng)域的數(shù)據(jù)結(jié)構(gòu)得到研究和發(fā)展，各種空間數(shù)據(jù)結(jié)構(gòu)也在探索中。一般認為，一個數(shù)據(jù)結(jié)構(gòu)是由數(shù)據(jù)元素依據(jù)某種邏輯聯(lián)系組織起來的。對數(shù)據(jù)元素間邏輯關(guān)系的描述稱為數(shù)據(jù)的邏輯結(jié)構(gòu)；數(shù)據(jù)必須在計算機內(nèi)存儲，數(shù)據(jù)的存儲結(jié)構(gòu)是數(shù)據(jù)結(jié)構(gòu)的實現(xiàn)形式，是其在計算機內(nèi)的表示；此外討論一個數(shù)據(jù)結(jié)構(gòu)必須同時討論在該類數(shù)據(jù)上執(zhí)行的運算才有意義。一個邏輯數(shù)據(jù)結(jié)構(gòu)可以有多種存儲結(jié)構(gòu)，且各種存儲結(jié)構(gòu)影響數(shù)據(jù)處理的效率。在許多類型的程序的設(shè)計中，數(shù)據(jù)結(jié)構(gòu)的選擇是一個基本的設(shè)計考慮因素。許多大型系統(tǒng)的構(gòu)造經(jīng)驗表明，系統(tǒng)實現(xiàn)的困難程度和系統(tǒng)構(gòu)造的質(zhì)量