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

1、題目：數(shù)據(jù)結(jié)構(gòu)發(fā)展史綜述學(xué)院：電子信息專業(yè)：通信工程班級(jí)：122學(xué)號(hào)：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隨著計(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ù)量也越來(lái)越大，這就給程序設(shè)計(jì)帶來(lái)一個(gè)問(wèn)題：應(yīng)如何組織待處理的數(shù)據(jù)以及數(shù)據(jù)之間的關(guān)系(結(jié)構(gòu))。數(shù)據(jù)結(jié)構(gòu)技術(shù)從誕生到現(xiàn)在，在不到半個(gè)世紀(jì)的時(shí)間

2、里，形成了堅(jiān)實(shí)的理論基礎(chǔ)、成熟的商業(yè)產(chǎn)品和廣泛的應(yīng)用領(lǐng)域，吸引越來(lái)越多的研究者加入。數(shù)據(jù)結(jié)構(gòu)的誕生和發(fā)展給計(jì)算機(jī)信息管理帶來(lái)了一場(chǎng)巨大的革命。三十多年來(lái)，它已成為企業(yè)、部門(mén)乃至個(gè)人日常工作、生產(chǎn)和生活的基礎(chǔ)設(shè)施。同時(shí)，隨著應(yīng)用的擴(kuò)展與深入，數(shù)據(jù)結(jié)構(gòu)的數(shù)量和規(guī)模越來(lái)越大，數(shù)據(jù)結(jié)構(gòu)的研究領(lǐng)域也已經(jīng)大大地拓廣和深化了。30年間數(shù)據(jù)結(jié)構(gòu)領(lǐng)域獲得了三次計(jì)算機(jī)圖靈獎(jiǎng)(.Bachman,),更加充分地說(shuō)明了數(shù)據(jù)結(jié)構(gòu)是一個(gè)充滿活力和創(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)、存儲(chǔ)結(jié)構(gòu)（物理

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

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

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

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

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

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

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

10、學(xué)模型。這一階段，在人類的自然語(yǔ)言與計(jì)算機(jī)編程語(yǔ)言之間存在著巨大的鴻溝，程序設(shè)計(jì)屬于面向計(jì)算機(jī)的程序設(shè)計(jì)，設(shè)計(jì)人員關(guān)注的重心是使程序盡可能地被計(jì)算機(jī)接受并按指令正確執(zhí)行，至于程序能否讓人理解并不重要。結(jié)構(gòu)化階段。6080年代，計(jì)算機(jī)開(kāi)始廣泛應(yīng)用于非數(shù)值處理領(lǐng)域，數(shù)據(jù)表示成為程序設(shè)計(jì)的重要問(wèn)題，人們認(rèn)識(shí)到程序設(shè)計(jì)規(guī)范化的重要性，提出了程序結(jié)構(gòu)模塊化，并開(kāi)始注意數(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è)重

11、要的組成部分，一個(gè)軟件系統(tǒng)通常是以一個(gè)或幾個(gè)關(guān)鍵數(shù)據(jù)結(jié)構(gòu)為核心而組織的。隨著軟件系統(tǒng)的規(guī)模越來(lái)越大、復(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ù)中，問(wèn)題世界的相關(guān)實(shí)體被視為一個(gè)對(duì)象，對(duì)象由屬性和方法構(gòu)成，屬性用以描述實(shí)體的狀態(tài)或特征，方法用以改變實(shí)體的狀態(tài)或描述實(shí)體的行為。一組具有相同屬性和方法的對(duì)象的集合抽象為類，每個(gè)具體的對(duì)象都是類的一個(gè)實(shí)例。例如，“教師”

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