全國計算機等級考試三級數(shù)據(jù)庫考點分析之數(shù)據(jù)結(jié)構(gòu)算法[1]

字號:

第二章 數(shù)據(jù)結(jié)構(gòu)算法
     2.1基本概率
     考點1數(shù)據(jù)結(jié)構(gòu)的基本概念
     1.數(shù)據(jù)
     在計算機系統(tǒng)中,數(shù)據(jù)不僅包含了通常的數(shù)值概念,還有更廣泛的含義我們把采用計算機對客觀事物進行識別、存儲和加工所做的描述,統(tǒng)稱為數(shù)據(jù)。簡言之,數(shù)據(jù)就是計算機化的信息
     數(shù)據(jù)的基本單位是數(shù)據(jù)元素。數(shù)據(jù)元素可由一個或多個數(shù)據(jù)項組成。數(shù)據(jù)項是數(shù)據(jù)的不可分割的最小單位,又稱為關(guān)鍵碼,其值能夠確定一個數(shù)據(jù)元素的數(shù)據(jù)項。
     2.數(shù)據(jù)結(jié)構(gòu)
     數(shù)據(jù)結(jié)構(gòu)包括3個方面的內(nèi)容:數(shù)據(jù)之間的邏輯關(guān)系、數(shù)據(jù)在計算機中的存儲方式,以及在這些數(shù)據(jù)上定義的運算的集合。
     (l)數(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é)構(gòu)是線性表,最典型的非線性結(jié)構(gòu)是樹型結(jié)構(gòu)。
     (2)數(shù)據(jù)的存儲結(jié)構(gòu)。數(shù)據(jù)的存儲結(jié)構(gòu)實現(xiàn)了數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機內(nèi)的存儲問題,存儲結(jié)構(gòu)又稱為物理結(jié)構(gòu)。存儲結(jié)構(gòu)分為順序存儲結(jié)構(gòu)與鏈式存儲結(jié)構(gòu)。
     (3)數(shù)據(jù)的運算。數(shù)據(jù)的各種邏輯結(jié)構(gòu)都有相對應(yīng)的運算,每一種邏輯結(jié)構(gòu)都有一個運算的集合。數(shù)據(jù)運算主要包括查找(檢索)、排序、插人、更新及刪除等。
    考點2主要的數(shù)據(jù)存儲方式
     實現(xiàn)數(shù)據(jù)的邏輯結(jié)構(gòu)到計算機存儲器的映像有多種不同的方式。順序存儲結(jié)構(gòu)和鏈式存儲結(jié)構(gòu)是兩種最主要的存儲方式。
     1.順序存儲結(jié)構(gòu)
     順序存儲結(jié)構(gòu)是將邏輯上相鄰的數(shù)據(jù)元素存儲在物理上相鄰的存儲單元里,節(jié)點之間的關(guān)系由存儲單元的相鄰關(guān)系來決定,它主要用于存儲線性結(jié)構(gòu)的數(shù)據(jù)。順序存儲結(jié)構(gòu)的主要特點如下。
     (1)由于節(jié)點之間的關(guān)系由物理上的相鄰關(guān)系決定,所以節(jié)點中沒有鏈接信息域,只有自身的信息域,存儲密度大,空間利用率高。
     (2)數(shù)據(jù)結(jié)構(gòu)中第i個節(jié)點的存儲地址乙可由下述公式計算求得:
     L¬i=L¬0+(i-1)×K
     L¬0為第一個節(jié)點存儲地址,左為每個節(jié)點所占的存儲單元數(shù)。
     (3)插人、刪除運算會引起相應(yīng)節(jié)點的大量移動各節(jié)點的物理地址是相鄰的,每一次插人、刪除運算會引起相應(yīng)節(jié)點物理地址的重新排列。
     2.鏈式存儲結(jié)構(gòu)
     鏈式存儲結(jié)構(gòu)打破了計算機存儲單元的連續(xù)性,可以將邏輯上相鄰的兩個數(shù)據(jù)元素存放在物理上不相鄰的存儲單元中鏈式存儲結(jié)構(gòu)的每個節(jié)點中至少有一個節(jié)點域,來體現(xiàn)數(shù)據(jù)之間邏輯上的聯(lián)系。
     鏈式存儲結(jié)構(gòu)的主要特點包括以下幾個方面。
     (1)節(jié)點中除自身信自、外,還有表示鏈接信息的指針域,因此比順序存儲結(jié)構(gòu)的存儲密度小,存儲空間利用率低。
     (2):羅輯上相鄰的節(jié)點物理上不一定相鄰,可用于線性表、樹、圖等多種邏輯結(jié)構(gòu)的存儲表示。
     (3)插人、刪除等操作靈活方便,不需要大量移動節(jié)點,只需將節(jié)點的指針值修改即可。
    考點3算法設(shè)計與分析
     在計算機領(lǐng)域,一個算法實質(zhì)上是針對所處理問題的需要,在數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)的基礎(chǔ)上施加的一種運算,它是解決特定問題的方法。一個算法所占用的計算機資源包括時間代價和空間代價兩個方面
     時間代價的含義是:當問題的規(guī)模以某種單位由1增至n時,解決該問題的算法運行時所耗費的時間也以某種單位由f( 1)增至f(n),則稱該算法的時間代價為f(n)。
     空間代價的含義是:當問題的規(guī)模以某種單位由1增至n時,解決該問題的算法實現(xiàn)時所占用的空間也以某種單位由到g(1)增至g(n),則稱該算法的空間代價為g(n)。
    2.2線性表
     線性表的邏輯結(jié)構(gòu)是由n個數(shù)據(jù)元素組成的一個有限序列。線性表中所包含元素的個數(shù)叫線性表的長度.它是可變的.可同線性表中增加或刪除元素。線性表包括順序表、鏈表、散列表和串等。
     線性表的基本運算有:置表空、求表長、讀表元素、插人、刪除及檢索等操作。
    考點4順序表和一維數(shù)組
     線性表的順序存儲是線性表的一種最簡單的存儲結(jié)構(gòu)。其存儲方法是:在內(nèi)存中為線性表開辟一塊連續(xù)的存儲空間,該存儲空間所包含的存儲單元數(shù)要大于或等于線性表的長度,讓線性表的第一個元素存儲在這個存儲空間的第一個單元中,第二個元素存儲在第二個單元中,其他元素依次類推。一般情況下,若長度為n的順序表,在任何位置土插入或刪除的概率相等,元素移動的平均次數(shù)均為n/2。