數(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è)計(jì)一、數(shù)據(jù)結(jié)構(gòu)起源于程序設(shè)計(jì)隨著計(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ù)量也越來越大，這就給程序設(shè)計(jì)帶來一個(gè)問題：應(yīng)如何組織待處理的數(shù)據(jù)以及數(shù)據(jù)之間的關(guān)系（結(jié)構(gòu)）。1968年克努思教授

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

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

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