世紀高等院校規(guī)劃教材數(shù)據(jù)結構c語言版(編輯修改稿)
2024-08-14 00:59 本頁面
【文章內(nèi)容簡介】 簡稱 ADT） ADT是指一個數(shù)學模型以及定義在該模型上的一組的操作 。 可以看作是數(shù)據(jù)的邏輯結構及其在邏輯結構上定義的操作 。 抽象數(shù)據(jù)類型的定義僅取決于它的一組邏輯特性 ， 而與其在計算機內(nèi)部如何表示和實現(xiàn)無關 。 2022/8/15 13 數(shù)據(jù)結構 (Data Structure) 數(shù)據(jù)結構是研究數(shù)據(jù)元素 （ Data Element） 之間抽象化的相互關系 （ 邏輯結構 ） 和這種關系在計算機中的存儲表示 （ 物理結構 ） ，并對這種結構定義相適應的運算 ， 設計出相應的算法 。 數(shù)據(jù)結構主要指邏輯結構和物理結構。 1. 邏輯結構： 數(shù)據(jù)之間的相互關系稱為邏輯結構。通常分為 4 類基本結構： 集合 結構中的數(shù)據(jù)元素除了同屬于一種類型外，別無其它關系。 線性結構 結構中的數(shù)據(jù)元素之間存在一對一的關系。 樹型結構 結構中的數(shù)據(jù)元素之間存在一對多的關系。 圖狀結構或網(wǎng)狀結構 結構中的數(shù)據(jù)元素之間存在多對多的關系。 2022/8/15 14 在表 11所示的表格中 ， 由 7個結點 (數(shù)據(jù)元素 )組成 ， 每個數(shù)據(jù)元素又包括 6個數(shù)據(jù)項 (字段 )。 各結點之間在邏輯上有一種線性關系 ， 它指出了 7個結點在表中的排列順序 。 這張表的邏輯結構就是數(shù)據(jù)元素 (或是結點 、 記錄 )之間的關系 。對于表中的任一個結點 (記錄 )， 都只有一個前驅結點 ， 也只有一個后繼結點 ， 整個表只有一個開始結點和一個終端結點 。 此表的邏輯結構是線性的 。 2022/8/15 15 四類數(shù)據(jù)基本結構的示意圖： (a)集合結構 (b)線性結構 (c)樹型結構 (d)圖形結構 由以上例子可見，描述這類非數(shù)值計算問題的數(shù)學模型和方法不再是數(shù)學方程，而是諸如線性表、樹和圖之類的數(shù)據(jù)結構。 2022/8/15 16 數(shù)據(jù)對象可以是有限的，也可以是無限的。 數(shù)據(jù)結構不同于數(shù)據(jù)類型，也不同于數(shù)據(jù)對象，它不僅要描述數(shù)據(jù)類型的數(shù)據(jù)對象，而且要描述數(shù)據(jù)對象各元素之間的相互關系。 2022/8/15 17 2. 存儲結構： 數(shù)據(jù) 結構 在計算機中的存儲表示稱為數(shù)據(jù)的存儲結構 。 它包括數(shù)據(jù)元素的表示和關系的表示 。 表 11所示的表格數(shù)據(jù)在計算機中可以有多種存儲表示： 數(shù)據(jù)既可以存放在一塊連續(xù)的內(nèi)存單元中 ， 通過元素在存儲器中的位置來表示它們之間的邏輯關系 （ 順序 ） ； 也可以隨機分布在內(nèi)存中的不同位置 ， 通過指針元素表示數(shù)據(jù)元素之間的邏輯關系 （ 鏈式 ） 。 這兩種不同的表示方法對應有四種不同的存儲結構 （ 亦稱方式 ） ： 順序 存儲結構 、 鏈式 存儲結構 、 索引 存儲結構和 散列 存儲結構 。 2022/8/15 18 (1)順序存儲結構是把邏輯上相鄰的結點存儲在物理上相鄰的存儲單元里 ， 結點之間的邏輯關系由存儲單元位置的鄰接關系來體現(xiàn) 。 優(yōu)點：占用較少的存儲空間； 缺點：由于只能使用相鄰的一整塊存儲單元 ， 因此可能產(chǎn)生較多的碎片現(xiàn)象 。 順序存儲結構通常借助程序語言中的數(shù)組來描述 。 順序存儲結構主要應用于線性的數(shù)據(jù)結構。 2022/8/15 19 (2) 鏈式存儲 結構 將結點所占的存儲單元分為兩部分，一部分存放結點本身的信息，另一部分存放結點的后繼結點地址，結點間的邏輯關系由附加的指針字段表示。 鏈式存儲結構常借助于程序語言的指針類型描述。 優(yōu)點 ： 不會出現(xiàn)碎片現(xiàn)象，充分利用所有的存儲單元； 缺點 ：
黨政相關相關推薦
鄂ICP備17016276號-1