第1部分　教學(xué)內(nèi)容指導(dǎo)

第1章　緒論

1.1　知識點分析

1.數(shù)據(jù)

數(shù)據(jù)是信息的載體，是對客觀事物的符號表示。

2.數(shù)據(jù)元素

數(shù)據(jù)元素是對現(xiàn)實世界中某獨立個體的數(shù)據(jù)描述，是數(shù)據(jù)的基本單位。數(shù)據(jù)元素也稱為結(jié)點。

3.數(shù)據(jù)項

數(shù)據(jù)項是數(shù)據(jù)不可分割的、具有獨立意義的最小數(shù)據(jù)單位，是對數(shù)據(jù)元素屬性的描述。

數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項反映了數(shù)據(jù)組織的3個層次，即數(shù)據(jù)可以由若干個數(shù)據(jù)元素組成，數(shù)據(jù)元素又由若干數(shù)據(jù)項組成。

4.數(shù)據(jù)對象

數(shù)據(jù)對象是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個子集。

5.數(shù)據(jù)結(jié)構(gòu)

數(shù)據(jù)結(jié)構(gòu)是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。簡而言之，數(shù)據(jù)結(jié)構(gòu)是指數(shù)據(jù)之間的關(guān)系，即數(shù)據(jù)的組織形式。數(shù)據(jù)結(jié)構(gòu)包括以下三方面：

（1）數(shù)據(jù)的邏輯結(jié)構(gòu)

數(shù)據(jù)元素之間的邏輯關(guān)系，稱為數(shù)據(jù)的邏輯結(jié)構(gòu)。即從邏輯關(guān)系上描述數(shù)據(jù)，它與數(shù)據(jù)的存儲無關(guān)，是獨立于計算機的。

線性結(jié)構(gòu)是指數(shù)據(jù)元素之間存在“一對一”關(guān)系的邏輯結(jié)構(gòu)，非線性結(jié)構(gòu)是指數(shù)據(jù)元素之間存在“一對多”或“多對多”關(guān)系的邏輯結(jié)構(gòu)。

（2）數(shù)據(jù)的存儲結(jié)構(gòu)

數(shù)據(jù)元素及其關(guān)系在計算機存儲器內(nèi)的表示，稱為數(shù)據(jù)的存儲結(jié)構(gòu)，也稱為數(shù)據(jù)的物理結(jié)構(gòu)。數(shù)據(jù)的存儲結(jié)構(gòu)是數(shù)據(jù)的邏輯結(jié)構(gòu)用計算機語言的實現(xiàn)，依賴于計算機語言。

（3）數(shù)據(jù)的運算

數(shù)據(jù)的運算是指對數(shù)據(jù)施加的操作。數(shù)據(jù)的運算是定義在數(shù)據(jù)的邏輯結(jié)構(gòu)上的，而運算的實現(xiàn)則是在存儲結(jié)構(gòu)上進行的。

6.算法的描述和分析

數(shù)據(jù)的運算是通過算法來描述的，對于算法的說明可以使用不同的語言，對同一問題可以有不同的算法。

（1）時間復(fù)雜度

通常，把算法中所包含簡單操作次數(shù)的多少稱為算法的時間復(fù)雜度。但是，當一個算法比較復(fù)雜時，其時間復(fù)雜度的計算會變得相當困難。一般情況下，算法中原操作重復(fù)執(zhí)行的次數(shù)是規(guī)模n的某個函數(shù)f（n），算法的時間復(fù)雜度T（n）的數(shù)量級可記作T（n）=O（f（n））。

算法的時間復(fù)雜度T（n）是該算法的時間消耗，一個算法的時間耗費就是該算法中所有語句的執(zhí)行次數(shù)（頻度）之和。當n→∞時（即當n相當大時），T（n）的數(shù)量級（階），用O表示。由于limT（n）/f（n）=C，C是不為0的常數(shù)，所以T（n）=O（f（n））。其實，f（n）就是T（n）中最高階的一項，是算法中最大的語句頻度。

一般情況下，對于循環(huán)語句只需要考慮循環(huán)體中語句的執(zhí)行次數(shù)，而忽略該語句中循環(huán)頭的部分。有時，循環(huán)體中語句的頻度不僅與問題規(guī)模n有關(guān)，還與輸入實例等其他因素有關(guān)，此時可以用最壞情況下的時間復(fù)雜度作為算法的時間復(fù)雜度。

（2）空間復(fù)雜度

一個程序的空間復(fù)雜度是指程序運行從開始到結(jié)束所需要的存儲空間。類似于算法的時間復(fù)雜度，我們把算法所需存儲空間的量度，記作S（n）=O（f（n））。其中，n為問題的規(guī)模。在進行時間復(fù)雜度分析時，如果所占空間量依賴于特定的輸入，一般都按最壞情況來分析。

程序運行時所需要的存儲空間包括以下兩部分：

①固定部分：主要包括程序代碼、常量、變量、結(jié)構(gòu)體變量等所占的空間。空間與所處理的數(shù)據(jù)大小和個數(shù)無關(guān)，或者說與問題事例的特征無關(guān)。

②可變部分：空間大小與算法在某次執(zhí)行中處理的特定數(shù)據(jù)的大小和規(guī)模有關(guān)。