數(shù)據(jù)結構發(fā)展史

1、數(shù)據(jù)結構發(fā)展史張抒菲 120081001104一、數(shù)據(jù)結構起源于程序設計隨著計算機科學與技術的不斷發(fā)展，計算機的應用領域已不再局限于科學計算，而更多地應用于控制、管理等非數(shù)值處理領域。與此相應，計算機處理的數(shù)據(jù)也由純粹的數(shù)值發(fā)展到字符、表格、圖形、圖象、聲音等具有一定結構的數(shù)據(jù)，處理的數(shù)據(jù)量也越來越大，這就給程序設計帶來一個問題：應如何組織待處理的數(shù)據(jù)以及數(shù)據(jù)之間的關系(結構).1968年克努思教授?！块_創(chuàng)了數(shù)據(jù)結構的最初體系，他所著的計算機程序設計藝術第一卷基本算法是第一本較系統(tǒng)地闡述數(shù)據(jù)的邏輯結構和存儲結構及其操作的著作。70年代初，數(shù)據(jù)結構作為一門獨立的課程開始進入大學課堂。數(shù)據(jù)結構在計

2、算機科學界至今沒有標準的定義。個人根據(jù)各自的理解的不同而有不同的表述方法。例的數(shù)據(jù)元素之間的各種聯(lián)系。這些聯(lián)系可以通過定義相關的函遨來給出?！彼麑?shù)據(jù)對象(dataobject)定義為“一個數(shù)據(jù)對象是實例或值的集合”。數(shù)據(jù)結構在計算機科學界至今沒有標準的定義。個人根據(jù)各自的理解的不同而有不同的表述方法：SamjSahni在他的數(shù)據(jù)結構、算法與應用一書中稱：“數(shù)據(jù)結構是數(shù)據(jù)對象,以及存在于該對象的實例和組成實QiffOrd A.Shaffer在數(shù)據(jù)結構與算法分析一書中的定義是：“數(shù)據(jù)結構是ADT （抽象數(shù)據(jù)類型AbStraCtDataTVPe）的物理實現(xiàn)?！盠ObertL.Kruse在數(shù)據(jù)結構與

3、程序設計一書中，將一個數(shù)據(jù)結構的設計過程分成抽象層、數(shù)據(jù)結構層和實現(xiàn)層。其中，抽象層是指抽象數(shù)據(jù)類型層，它討論數(shù)據(jù)的邏輯結控及其運算，數(shù)據(jù)結構層和實現(xiàn)層討論一個數(shù)據(jù)結構的表示和在計算機內的存儲細節(jié)以及運算的實現(xiàn)。數(shù)據(jù)結構是指同一數(shù)據(jù)元素類中各數(shù)據(jù)元素之間存在的關系。數(shù)據(jù)結構分別為邏輯結構、存儲結構（物理結構）和數(shù)據(jù)的運算。數(shù)據(jù)的邏輯結構是對數(shù)據(jù)之間關系的描述，有時就把邏輯結構簡稱為數(shù)據(jù)結構。邏輯結構形式地定義為（K, R）（或（D, S）,其中，K是數(shù)據(jù)元素的有限集，R是K上的關系的有限集。數(shù)據(jù)元素相互之間的關系稱為結構。有四類基本結構：集合、線性結構、樹形結構、圖狀結構（網狀結構）o樹形結構

4、和圖形結拉全稱為非線性結構。集合結構中的數(shù)據(jù)元素除了同屬于一種類型外，別無其它關系。線性結構中元素之間存在一對一關系，樹形結構中元素之間存在一對多關系，圖形結構中元素之間存在多對多關系。在圖形結構中每個結點的前驅結點數(shù)和后續(xù)結點數(shù)可以任意多個。數(shù)據(jù)結構在計算機中的表示（映像）稱為數(shù)據(jù)的物理（存儲）結構。它包括數(shù)據(jù)元素的表示和關系的表示。數(shù)據(jù)元素之間的關系有兩種不同的表示方法：順序映象和非順序映象，并由此得到兩種不同的存儲結構：順序存儲結構和鏈式存儲結構。順序存儲方法:它是把邏輯上相鄰的結點存儲在物理位置相鄰的理儲堂元里，結點間的邏輯關系由存儲單元的鄰接關系來體現(xiàn)，由此得到的存儲表示稱為順序存儲

5、結構。順序存儲結構是一種最基本的存儲表示方法，通常借助于程序設計語言中的數(shù)組來實現(xiàn)。鏈接存儲方法：它不要求邏輯上相鄰的結點在物理位置上亦相鄰，結點間的邏輯關系是由附加的搟i字段表示的。由此得到的存儲表示稱為鏈式存儲結構，鏈式存儲結構通常借助于程序設計語言中的指針類型來實現(xiàn)。索也存儲方法：除建立存儲結點信息外，還建立附加的索引表來標識結點的地址.散列存儲方法:就是根據(jù)結點的關鍵字直接計算出該結點的存儲地址。數(shù)據(jù)結構中，邏輯上（邏輯結構：數(shù)據(jù)元素之間的邏輯關系）可以把數(shù)據(jù)結構分成線性結構和非線性結構。線性結構的順序存儲結構是一種隨機在理的存儲結構，線性表的鏈式存儲結構是一種順序存取的存儲結構。線性

6、表若采用鏈式存儲表示時所有結點之間的存儲單元地址可連續(xù)可不連續(xù)。邏輯結構與數(shù)據(jù)元素本身的形式、內容、相對位置、所含結點個數(shù)都無關。自從美國唐歐克努特教授用匯編語言編寫的計算機程序設計技巧第一卷基本算法問世以來，已經出現(xiàn)了用PaSCa1、Java、C、C+、C#等語言編寫的數(shù)據(jù)結構方面的書?？傮w說來，這些語言基本上分為面向過程的語言和面向對象的語言兩大類，也出現(xiàn)過采用兩種語言描述數(shù)據(jù)結構的書籍，如C和C+語言描述，但作者實際上是按照C+語言描述。同時采用面向過程和面向對象語言描述數(shù)據(jù)結構，目前國內基本上是空白。對于同一種數(shù)據(jù)結構與算法，同時采用面向過程和面向對象語言進行描述，可以從中更深刻理解這

7、兩種思想的不同，這對于深刻理解計算機語言和思想有著重要的作用。C語言是現(xiàn)在最流行的面向過程的語言，在業(yè)界使用非常廣泛。而C#語言作為微軟在新一代開發(fā)平臺（NED上推出的、完全面向對象的語言，憑著其簡潔、高效、模板、標準化的特性，使得C#語言像程序設計語言中的一件藝術品，也吸引著越來越多的開發(fā)人員。當然，C#語言也吸收了 C語言的一些東西，如語法等，所以，在有些方面，C#與C是相似的。二、數(shù)據(jù)結構題著程序設計的發(fā)展而發(fā)展。程序設計經歷了三個階段：無結構階段、結構化階段和面向對象階段，相應地，數(shù)據(jù)結構的發(fā)展也經歷了三個階段：算法+數(shù)據(jù)結構=程序郁向對象階段應用領域：更多地應用于非數(shù)值處理;（算法+

8、數(shù):據(jù)結構）=程序數(shù)據(jù)結構隨著程序設計的發(fā)展而發(fā)展。程序設計羥濟了三個階梟：無結構階段、結為化階段列而向對象齡段，相應地，敵澧結溝的發(fā)展也涇歷了三個階段：無結構階段。40-60年代，計算機的應用主要針刀再學計算,程序設計技術以機器語言/ ：絹語言為主，程序處理的數(shù)據(jù)是絕猝的數(shù)值，數(shù)理之間的關系主要是稅學公式或數(shù)學模幽。這一種段，在人類的自然語言與計算機絹程語言之間存在著巨大的淹溝,程洋設計崽干而向計算機的程序設計,設計人員關注的重心使程序盡可能,也被計算TlL受并按指令正確執(zhí)行，至于程序能否讓人理解并不重要。結均化階段。6。3。年代，計算機開始廣泛應用于非數(shù)值處理領域，數(shù)據(jù)表示成為序沒計的重妄

9、問題，大任認識到程.?設計規(guī)范化的重要性,提盅了程序結構模塊化,并訐始注意數(shù)據(jù)表示與攜策的結枸化。數(shù)據(jù)結1¾及拄象類&就是在這種情況下形成的。數(shù)有結狗艷念為引入,對程序設計的規(guī)范化起到了重大作用。IS靈建獎獲得者沃思P給出了一個著名的公式：數(shù)據(jù)結構+算法二程序。從這個公式可以看到，數(shù)據(jù)結構和算法是構成程序的兩個重要的組成部分，一個軟件系統(tǒng)通常是以一個或幾個關鍵數(shù)據(jù)結構為核心而組織的。隨著軟件系統(tǒng)的規(guī)模越來越大、復雜性不斷增加，人們不得不對結構化技術重新評價。由于軟件系統(tǒng)的實現(xiàn)依賴于關鍵數(shù)據(jù)結構，如果這些關鍵數(shù)據(jù)結構的一個或幾個有所改變，則涉及到整個系統(tǒng)，甚至導致整個系統(tǒng)徹底崩

10、潰。（3）面向對象階段。面向對象技術（首先是面向對象程序設計）始于80年代初,是目前最流行的程序設計技術。在面向對象技術中，問題世界的相關實體被視為一個對象，對象由屬性和方法構成，屬性用以描述實體的狀態(tài)或特征，方法用以改變實體的狀態(tài)或描述實體的行為。一組具有相同屬性和方法的對象的集合抽象為類，每個具體的對象都是類的一個實例。例如，“教師”是一個類，“王老師”、“李老師”等對象都是“教師”類的實例。由于對象（類）將密切相關的屬性（數(shù)據(jù)）和方法（操作）定義為一個整體，從而實現(xiàn)了封裝和信息隱藏。使用類時，無需了解其內部的實現(xiàn)細節(jié)，一旦數(shù)據(jù)（結構）修改了，只需修改類內部的局部代碼，軟件系統(tǒng)的其余部分無

11、需修改。數(shù)據(jù)結構主要強調兩個方面的內容：數(shù)據(jù)之間的關系； 針對這些關系的基本操作。這兩個方面實際上蘊涵著面向對象的思想：類重點描述實體的狀態(tài)與行為，而數(shù)據(jù)結構重點描述數(shù)據(jù)之間的關系及其基本操作，數(shù)據(jù)及其相互關系構成了對實體狀態(tài)的描述，針對數(shù)據(jù)元素之間關系的操作構成了對實體行為的描述。由此可見，類與數(shù)據(jù)結構之間具有對應關系，如圖1-1所示。囪1-1類和數(shù)據(jù)結構之間的對應關系“數(shù)據(jù)結構+算法二程序”這個公式在軟件開發(fā)的進程中曾產生了深遠的影響，但是，它并沒有強調數(shù)據(jù)結構與解決問題的算法是一個整體，因此有人主張將它修改為“（數(shù)據(jù)結構+算法）=程序”，以體現(xiàn)面向對象的思想。值得注意的是，數(shù)據(jù)結構的發(fā)展

12、并未終結。一方面，數(shù)據(jù)結構將繼續(xù)隨著程序設計的發(fā)展而發(fā)展；另一方面，面向各專門領域的數(shù)據(jù)結構得到研究和發(fā)展，各種實用的高級數(shù)據(jù)結構被研究出來,各種空間數(shù)據(jù)結構也在探索中。三、數(shù)據(jù)結構的發(fā)展并未終結。1.數(shù)據(jù)結構將繼續(xù)隨著程序設計的發(fā)展而發(fā)展；2,面向各專門領域的數(shù)據(jù)結構得到研究和發(fā)展，各種空間數(shù)據(jù)結構也在探索中1克努思（DonaldEKnuth , 1938年生）從小就是個優(yōu)秀的學生，多次獲得學業(yè)成就獎。1963年擔任加利福尼亞理工學院的教師，1968年擔任斯坦福大學教授。1992年為集中精力寫作而榮譽退休，保留教授頭銜。他特別感興趣的是為計算機程序設計藝術叢書完成新卷并更新舊卷。這套叢書是1962年他還是研究生時以編譯程序為中心開始寫作的，對計算機科學的發(fā)展產生了深遠的影響。從某種意義上說，克努思就意味著計算機程序設計藝術，也就意味著數(shù)據(jù)結構和算法這一類問題的答案。2圖靈（AJan.Mathison.Turing 1912-1954 ）出生于倫敦，24 歲提出圖靈機理論（這一理論奠定了整個現(xiàn)代計算機的理論基礎），31歲參與COLOSSUS的研制，33歲設想仿真系統(tǒng)，35歲提出自動程序設計概念，38歲發(fā)表論文計算機能思考嗎？，論證了人工智能的可能性，被人們推崇為人工智能