需要達(dá)到 <識(shí)記> 層次的基本概念和術(shù)語(yǔ)有：數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項(xiàng)、數(shù)據(jù)結(jié)構(gòu)。特別是數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)及數(shù)據(jù)運(yùn)算的含義及其相互關(guān)系。數(shù)據(jù)結(jié)構(gòu)的兩大類(lèi)邏輯結(jié)構(gòu)和四種常用的存儲(chǔ)表示方法。
需要達(dá)到 <領(lǐng)會(huì)> 層次的內(nèi)容有算法、算法的時(shí)間復(fù)雜度和空間復(fù)雜度、壞的和平均時(shí)間復(fù)雜度等概念，算法描述和算法分析的方法、對(duì)一般的算法要能分析出時(shí)間復(fù)雜度。
對(duì)于基本概念，仔細(xì)看書(shū)就能夠理解，這里簡(jiǎn)單提一下：
數(shù)據(jù)就是指能夠被計(jì)算機(jī)識(shí)別、存儲(chǔ)和加工處理的信息的載體。
數(shù)據(jù)元素是數(shù)據(jù)的基本單位，有時(shí)一個(gè)數(shù)據(jù)元素可以由若干個(gè)數(shù)據(jù)項(xiàng)組成。數(shù)據(jù)項(xiàng)是具有獨(dú)立含義的小標(biāo)識(shí)單位。如整數(shù)這個(gè)集合中，10這個(gè)數(shù)就可稱(chēng)是一個(gè)數(shù)據(jù)元素.又比如在一個(gè)數(shù)據(jù)庫(kù)(關(guān)系式數(shù)據(jù)庫(kù))中，一個(gè)記錄可稱(chēng)為一個(gè)數(shù)據(jù)元素，而這個(gè)元素中的某一字段就是一個(gè)數(shù)據(jù)項(xiàng)。
數(shù)據(jù)結(jié)構(gòu)的定義雖然沒(méi)有標(biāo)準(zhǔn)，但是它包括以下三方面內(nèi)容： 邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)、和對(duì)數(shù)據(jù)的操作 。這一段比較重要，我用自己的語(yǔ)言來(lái)說(shuō)明一下，大家看看是不是這樣。
比如一個(gè) 表 ( 數(shù)據(jù)庫(kù) )，我們就稱(chēng)它為一個(gè)數(shù)據(jù)結(jié)構(gòu)，它由很多 記錄 ( 數(shù)據(jù)元素 )組成，每個(gè)元素又包括很多 字段 ( 數(shù)據(jù)項(xiàng) )組成。那么這張表的邏輯結(jié)構(gòu)是怎么樣的呢? 我們分析數(shù)據(jù)結(jié)構(gòu)都是從 結(jié)點(diǎn) (其實(shí)也就是元素、記錄、頂點(diǎn)，雖然在各種情況下所用名字不同，但說(shuō)的是同一個(gè)東東)之間的關(guān)系來(lái)分析的，對(duì)于這個(gè)表中的任一個(gè)記錄(結(jié)點(diǎn))，它只有一個(gè) 直接前趨 ，只有一個(gè) 直接后繼 (前趨后繼就是前相鄰后相鄰的意思)，整個(gè)表只有一個(gè) 開(kāi)始結(jié)點(diǎn) 和一個(gè) 終端結(jié)點(diǎn) ，那我們知道了這些關(guān)系就能明白這個(gè)表的邏輯結(jié)構(gòu)了。
而 存儲(chǔ)結(jié)構(gòu) 則是指用 計(jì)算機(jī)語(yǔ)言 如何表示結(jié)點(diǎn)之間的這種關(guān)系。如上面的表，在計(jì)算機(jī)語(yǔ)言中描述為連續(xù)存放在一片內(nèi)存單元中，還是隨機(jī)的存放在內(nèi)存中再用指針把它們鏈接在一起，這兩種表示法就成為兩種不同的存儲(chǔ)結(jié)構(gòu)。( 注意，在本課程里，我們只在高級(jí)語(yǔ)言的層次上討論存儲(chǔ)結(jié)構(gòu)。 )
第三個(gè)概念就是對(duì) 數(shù)據(jù)的運(yùn)算 ，比如一張表格，我們需要進(jìn)行查找，增加，修改，刪除記錄等工作，而怎么樣才能進(jìn)行這樣的操作呢? 這也就是數(shù)據(jù)的運(yùn)算，它不僅僅是加減乘除這些算術(shù)運(yùn)算了，在數(shù)據(jù)結(jié)構(gòu)中，這些運(yùn)算常常涉及算法問(wèn)題。
弄清了以上三個(gè)問(wèn)題，就可以弄清數(shù)據(jù)結(jié)構(gòu)這個(gè)概念。
通常我們就將數(shù)據(jù)的 邏輯結(jié)構(gòu) 簡(jiǎn)稱(chēng)為 數(shù)據(jù)結(jié)構(gòu) ，數(shù)據(jù)的邏輯結(jié)構(gòu)分兩大類(lèi)： 線性結(jié)構(gòu) 和 非線性結(jié)構(gòu) (這兩個(gè)很容易理解)
數(shù)據(jù)的存儲(chǔ)方法有四種： 順序存儲(chǔ)方法 、 鏈接存儲(chǔ)方法 、 索引存儲(chǔ)方法和散列存儲(chǔ)方法 。
下一個(gè)是 難點(diǎn) 問(wèn)題，就是算法的描述和分析，主要是 算法復(fù)雜度 的分析方法及其運(yùn)用。
首先了解一下幾個(gè)概念。一個(gè)是 時(shí)間復(fù)雜度 ，一個(gè)是 漸近時(shí)間復(fù)雜度 。前者是某個(gè)算法的時(shí)間耗費(fèi)，它是該算法所求解問(wèn)題 規(guī)模 n的函數(shù)，而后者是指當(dāng)問(wèn)題規(guī)模趨向無(wú)窮大時(shí)，該算法 時(shí)間復(fù)雜度的數(shù)量級(jí)。
當(dāng)我們?cè)u(píng)價(jià)一個(gè)算法的時(shí)間性能時(shí)，主要標(biāo)準(zhǔn)就是 算法的漸近時(shí)間復(fù)雜度 ，因此， 在算法分析時(shí)，往往對(duì)兩者不予區(qū)分，經(jīng)常是將漸近時(shí)間復(fù)雜度t(n)=o(f(n)簡(jiǎn)稱(chēng)為時(shí)間復(fù)雜度，其中的f(n)一般是算法中頻度大的語(yǔ)句頻度 。
此外，算法中語(yǔ)句的頻度 不僅與問(wèn)題規(guī)模有關(guān)，還與輸入實(shí)例中各元素的取值相關(guān) 。但是我們總是考慮在壞的情況下的時(shí)間復(fù)雜度。以保證算法的運(yùn)行時(shí)間不會(huì)比它更長(zhǎng)。
常見(jiàn)的時(shí)間復(fù)雜度，按數(shù)量級(jí)遞增排列依次為： 常數(shù)階o(1) 、 對(duì)數(shù)階o(log2n) 、 線性階o(n) 、 線性對(duì)數(shù)階o(nlog2n) 、 平方階o(n^2)、立方階o(n^3) 、 k次方階o(n^k) 、 指數(shù)階o(2^n) 。
時(shí)間復(fù)雜度的分析計(jì)算請(qǐng)看書(shū)本上的例子，然后我們通過(guò)做練習(xí)加以領(lǐng)會(huì)和鞏固。
需要達(dá)到 <領(lǐng)會(huì)> 層次的內(nèi)容有算法、算法的時(shí)間復(fù)雜度和空間復(fù)雜度、壞的和平均時(shí)間復(fù)雜度等概念，算法描述和算法分析的方法、對(duì)一般的算法要能分析出時(shí)間復(fù)雜度。
對(duì)于基本概念，仔細(xì)看書(shū)就能夠理解，這里簡(jiǎn)單提一下：
數(shù)據(jù)就是指能夠被計(jì)算機(jī)識(shí)別、存儲(chǔ)和加工處理的信息的載體。
數(shù)據(jù)元素是數(shù)據(jù)的基本單位，有時(shí)一個(gè)數(shù)據(jù)元素可以由若干個(gè)數(shù)據(jù)項(xiàng)組成。數(shù)據(jù)項(xiàng)是具有獨(dú)立含義的小標(biāo)識(shí)單位。如整數(shù)這個(gè)集合中，10這個(gè)數(shù)就可稱(chēng)是一個(gè)數(shù)據(jù)元素.又比如在一個(gè)數(shù)據(jù)庫(kù)(關(guān)系式數(shù)據(jù)庫(kù))中，一個(gè)記錄可稱(chēng)為一個(gè)數(shù)據(jù)元素，而這個(gè)元素中的某一字段就是一個(gè)數(shù)據(jù)項(xiàng)。
數(shù)據(jù)結(jié)構(gòu)的定義雖然沒(méi)有標(biāo)準(zhǔn)，但是它包括以下三方面內(nèi)容： 邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)、和對(duì)數(shù)據(jù)的操作 。這一段比較重要，我用自己的語(yǔ)言來(lái)說(shuō)明一下，大家看看是不是這樣。
比如一個(gè) 表 ( 數(shù)據(jù)庫(kù) )，我們就稱(chēng)它為一個(gè)數(shù)據(jù)結(jié)構(gòu)，它由很多 記錄 ( 數(shù)據(jù)元素 )組成，每個(gè)元素又包括很多 字段 ( 數(shù)據(jù)項(xiàng) )組成。那么這張表的邏輯結(jié)構(gòu)是怎么樣的呢? 我們分析數(shù)據(jù)結(jié)構(gòu)都是從 結(jié)點(diǎn) (其實(shí)也就是元素、記錄、頂點(diǎn)，雖然在各種情況下所用名字不同，但說(shuō)的是同一個(gè)東東)之間的關(guān)系來(lái)分析的，對(duì)于這個(gè)表中的任一個(gè)記錄(結(jié)點(diǎn))，它只有一個(gè) 直接前趨 ，只有一個(gè) 直接后繼 (前趨后繼就是前相鄰后相鄰的意思)，整個(gè)表只有一個(gè) 開(kāi)始結(jié)點(diǎn) 和一個(gè) 終端結(jié)點(diǎn) ，那我們知道了這些關(guān)系就能明白這個(gè)表的邏輯結(jié)構(gòu)了。
而 存儲(chǔ)結(jié)構(gòu) 則是指用 計(jì)算機(jī)語(yǔ)言 如何表示結(jié)點(diǎn)之間的這種關(guān)系。如上面的表，在計(jì)算機(jī)語(yǔ)言中描述為連續(xù)存放在一片內(nèi)存單元中，還是隨機(jī)的存放在內(nèi)存中再用指針把它們鏈接在一起，這兩種表示法就成為兩種不同的存儲(chǔ)結(jié)構(gòu)。( 注意，在本課程里，我們只在高級(jí)語(yǔ)言的層次上討論存儲(chǔ)結(jié)構(gòu)。 )
第三個(gè)概念就是對(duì) 數(shù)據(jù)的運(yùn)算 ，比如一張表格，我們需要進(jìn)行查找，增加，修改，刪除記錄等工作，而怎么樣才能進(jìn)行這樣的操作呢? 這也就是數(shù)據(jù)的運(yùn)算，它不僅僅是加減乘除這些算術(shù)運(yùn)算了，在數(shù)據(jù)結(jié)構(gòu)中，這些運(yùn)算常常涉及算法問(wèn)題。
弄清了以上三個(gè)問(wèn)題，就可以弄清數(shù)據(jù)結(jié)構(gòu)這個(gè)概念。
通常我們就將數(shù)據(jù)的 邏輯結(jié)構(gòu) 簡(jiǎn)稱(chēng)為 數(shù)據(jù)結(jié)構(gòu) ，數(shù)據(jù)的邏輯結(jié)構(gòu)分兩大類(lèi)： 線性結(jié)構(gòu) 和 非線性結(jié)構(gòu) (這兩個(gè)很容易理解)
數(shù)據(jù)的存儲(chǔ)方法有四種： 順序存儲(chǔ)方法 、 鏈接存儲(chǔ)方法 、 索引存儲(chǔ)方法和散列存儲(chǔ)方法 。
下一個(gè)是 難點(diǎn) 問(wèn)題，就是算法的描述和分析，主要是 算法復(fù)雜度 的分析方法及其運(yùn)用。
首先了解一下幾個(gè)概念。一個(gè)是 時(shí)間復(fù)雜度 ，一個(gè)是 漸近時(shí)間復(fù)雜度 。前者是某個(gè)算法的時(shí)間耗費(fèi)，它是該算法所求解問(wèn)題 規(guī)模 n的函數(shù)，而后者是指當(dāng)問(wèn)題規(guī)模趨向無(wú)窮大時(shí)，該算法 時(shí)間復(fù)雜度的數(shù)量級(jí)。
當(dāng)我們?cè)u(píng)價(jià)一個(gè)算法的時(shí)間性能時(shí)，主要標(biāo)準(zhǔn)就是 算法的漸近時(shí)間復(fù)雜度 ，因此， 在算法分析時(shí)，往往對(duì)兩者不予區(qū)分，經(jīng)常是將漸近時(shí)間復(fù)雜度t(n)=o(f(n)簡(jiǎn)稱(chēng)為時(shí)間復(fù)雜度，其中的f(n)一般是算法中頻度大的語(yǔ)句頻度 。
此外，算法中語(yǔ)句的頻度 不僅與問(wèn)題規(guī)模有關(guān)，還與輸入實(shí)例中各元素的取值相關(guān) 。但是我們總是考慮在壞的情況下的時(shí)間復(fù)雜度。以保證算法的運(yùn)行時(shí)間不會(huì)比它更長(zhǎng)。
常見(jiàn)的時(shí)間復(fù)雜度，按數(shù)量級(jí)遞增排列依次為： 常數(shù)階o(1) 、 對(duì)數(shù)階o(log2n) 、 線性階o(n) 、 線性對(duì)數(shù)階o(nlog2n) 、 平方階o(n^2)、立方階o(n^3) 、 k次方階o(n^k) 、 指數(shù)階o(2^n) 。
時(shí)間復(fù)雜度的分析計(jì)算請(qǐng)看書(shū)本上的例子，然后我們通過(guò)做練習(xí)加以領(lǐng)會(huì)和鞏固。