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

1、數(shù)據(jù)結(jié)構(gòu)發(fā)展史數(shù)據(jù)結(jié)構(gòu)發(fā)展史張抒菲120081001104一、數(shù)據(jù)結(jié)構(gòu)起源于程序設(shè)計一、數(shù)據(jù)結(jié)構(gòu)起源于程序設(shè)計隨著計算機科學與技術(shù)的不斷發(fā)展，計算機的應(yīng)用領(lǐng)域已不再局限于科學計算，而更多地應(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)）。1968年克努思教授

2、[1]開創(chuàng)了數(shù)據(jù)結(jié)構(gòu)的最初體系，他所著的《計算機程序設(shè)計藝術(shù)》第一卷《基本算法》是第一本較系統(tǒng)地闡述數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)及其操作的著作。70年代初，數(shù)據(jù)結(jié)構(gòu)作為一門獨立的課程開始進入大學課堂。數(shù)據(jù)結(jié)構(gòu)在計算機科學界至今沒有標準的定義。個人根據(jù)各自的理解的不同而有不同的表述方法。例的數(shù)據(jù)元素之間的各種聯(lián)系。這些聯(lián)系可以通過定義相關(guān)的函數(shù)來給出。”他將數(shù)據(jù)對象（dataobject）定義為“一個數(shù)據(jù)對象是實例或值的集合”。數(shù)據(jù)結(jié)構(gòu)在計算

3、機科學界至今沒有標準的定義。個人根據(jù)各自的理解的不同而有不同的表述方法：多關(guān)系。在圖形結(jié)構(gòu)中每個結(jié)點的前驅(qū)結(jié)點數(shù)和后續(xù)結(jié)點數(shù)可以任意多個。數(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)系由存

4、儲單元的鄰接關(guān)系來體現(xiàn)，由此得到的存儲表示稱為順序存儲結(jié)構(gòu)。順序存儲結(jié)構(gòu)是一種最基本的存儲表示方法，通常借助于程序設(shè)計語言中的數(shù)組來實現(xiàn)。鏈接存儲方法：它不要求邏輯上相鄰的結(jié)點在物理位置上亦相鄰，結(jié)點間的邏輯關(guān)系是由附加的指針字段表示的。由此得到的存儲表示稱為鏈式存儲結(jié)構(gòu)，鏈式存儲結(jié)構(gòu)通常借助于程序設(shè)計語言中的指針類型來實現(xiàn)。索引存儲方法：除建立存儲結(jié)點信息外，還建立附加的索引表來標識結(jié)點的地址。散列存儲方法：就是根據(jù)結(jié)點的關(guān)鍵字直接計