試舉一個數(shù)據(jù)結(jié)構(gòu)的例子敘述其邏輯結(jié)構(gòu)存儲結(jié)構(gòu)運算三個方面的內(nèi)容

1、數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)筆記作者: 網(wǎng)絡(luò)轉(zhuǎn)載 發(fā)布日期: 無 數(shù)據(jù)就是指能夠被計算機識別、存儲和加工處理的信息的載體。 數(shù)據(jù)元素是數(shù)據(jù)的基本單位，有時一個數(shù)據(jù)元素可以由若干個數(shù)據(jù)項組成。數(shù)據(jù)項是具有獨立含義的最小標(biāo)識單位。如整數(shù)這個集合中，10 這個數(shù)就可稱是一個數(shù)據(jù)元素.又比如在一個數(shù)據(jù)庫(關(guān)系式數(shù)據(jù)庫)中，一個記錄可稱為一個數(shù)據(jù)元素，而這個元素中的某一字段就是一個數(shù)據(jù)項。 數(shù)據(jù)結(jié)構(gòu)的定義雖然沒有標(biāo)準(zhǔn)，但是它包括以下三方面內(nèi)容：邏輯結(jié)構(gòu)、

2、存儲結(jié)構(gòu)、和對數(shù)據(jù)的操作。這一段比較重要，我用自己的語言來說明一下，大家看看是不是這樣。 比如一個表(數(shù)據(jù)庫)，我們就稱它為一個數(shù)據(jù)結(jié)構(gòu)，它由很多記錄(數(shù)據(jù)元素)組成，每個元素又包括很多字段(數(shù)據(jù)項)組成。那么這張表的邏輯結(jié)構(gòu)是怎么樣的呢? 我們分析數(shù)據(jù)結(jié)構(gòu)都是從結(jié)點(其實也就是元素、記錄、頂點，雖然在各種情況下所用名字不同，但說的是同一個東東)之間的關(guān)系來分析的，對于這個表中的任一個記錄(結(jié)點)，它只有一個直接前趨，只有一個直接后

3、繼(前趨后繼就是前相鄰后相鄰的意思)，整個表只有一個開始結(jié)點和一個終端結(jié)點，那我們知道了這些關(guān)系就能明白這個表的邏輯結(jié)構(gòu)了。 而存儲結(jié)構(gòu)則是指用計算機語言如何表示結(jié)點之間的這種關(guān)系。如上面的表，在計算機語言中描述為連續(xù)存放在一片內(nèi)存單元中，還是隨機的存放在內(nèi)存中再用指針把它們鏈接在一起，這兩種表示法就成為兩種不同的存儲結(jié)構(gòu)。(注意，在本課程里，我們只在高級語言的層次上討論存儲結(jié)構(gòu)。) 第三個概念就是對數(shù)據(jù)的運算，比如一張表格，我們需

4、要進(jìn)行查找，增加，修改，刪除記錄等工作，而怎么樣才能進(jìn)行這樣的操作呢? 這也就是數(shù)據(jù)的運算，它不僅僅是加減乘除這些算術(shù)運算了，在數(shù)據(jù)結(jié)構(gòu)中，這些運算常常涉及算法問題。 弄清了以上三個問題，就可以弄清數(shù)據(jù)結(jié)構(gòu)這個概念。 -------------------------------------------------------------------------------- 通常我們就將數(shù)據(jù)的邏輯結(jié)構(gòu)簡稱為數(shù)據(jù)結(jié)構(gòu)，數(shù)據(jù)的邏輯結(jié)構(gòu)分

5、兩大類：線性結(jié)構(gòu)和非線性結(jié)構(gòu) (這兩個很容易理解) 數(shù)據(jù)的存儲方法有四種：順序存儲方法、鏈接存儲方法、索引存儲方法和散列存儲方法。 -------------------------------------------------------------------------------- 下一個是難點問題，就是算法的描述和分析，主要是算法復(fù)雜度的分析方法及其運用。 首先了解一下幾個概念。一個是時間復(fù)雜度，一個是漸近時間復(fù)雜度。前者是

6、某個算法的時間耗費，它是該算法所求解問題規(guī)模 n 的函數(shù)，而后者是指當(dāng)問題規(guī)模趨向無窮大時，該算法時間復(fù)雜度的數(shù)量級。 當(dāng)我們評價一個算法的時間性能時，主要標(biāo)準(zhǔn)就是算法的漸近時間復(fù)雜度，因此，在算法分析時，往往對兩者不予區(qū)分，經(jīng)常是將漸近時間復(fù)雜度 T(n)=O(f(n)簡稱為時間復(fù)雜度，其中的 f(n)一般是算法中頻度最大的語句頻度。 此外，算法中語句的頻度不僅與問題規(guī)模有關(guān)，還與輸入實例中各元素的取值相關(guān)。但是我們總是考慮在最壞的

7、情況下的時間復(fù)雜度。以保證算法的運行時間不會比它更長。 常見的時間復(fù)雜度，按數(shù)量級遞增排列依次為：常數(shù)階 O(1)、對數(shù)階 O(log2n)、線性階 O(n)、線性對數(shù)階 O(nlog2n)、平方階 O(n^2)、立方階 O(n^3)、k 次方階 O(n^k)、指數(shù)階 O(2^n)。 時間復(fù)雜度的分析計算請看書本上的例子，然后我們通過做練習(xí)加以領(lǐng)會和鞏固。 數(shù)據(jù)結(jié)構(gòu)習(xí)題一 -------------------------------

8、------------------------------------------------- 1.4 設(shè)三個函數(shù) f,g,h 分別為 f(n)=100n^3+n^2+1000 , g(n)=25n^3+5000n^2 , h(n)=n^1.5+5000nlgn 請判斷下列關(guān)系是否成立： (1) f(n)=O(g(n)) (2) g(n)=O(f(n)) (3) h(n)=O(n^1.5) (4) h(n)=O(nlg

9、n) ◆ (1)成立。 ◇ 這里我們復(fù)習(xí)一下漸近時間復(fù)雜度的表示法 T(n)=O(f(n))，這里的“O“是數(shù)學(xué)符號，它的嚴(yán)格定義是“若 T(n)和 f(n)是定義在正整數(shù)集合上的兩個函數(shù)，則 T(n)=O(f(n))表示存在正的常數(shù) C 和 n0 ,使得當(dāng) n≥n0 時都滿足 0≤T(n)≤C·f(n)?！坝萌菀桌斫獾脑捳f就是這兩個函數(shù)當(dāng)整型自變量 n 趨向于無窮大時，兩者的比值是一個不等于 0 的常數(shù)。這么一來，就好計算

10、了吧。第(1)題中兩個函數(shù)的最高次項都是 n^3,因此當(dāng) n→∞時，兩個函數(shù)的比值是一個常數(shù)，所以這個關(guān)系式是成立的。 ◆ （2）成立。 ◆ （3）成立。 ◆ （4）不成立。 -------------------------------------------------------------------------------- 1.5 設(shè)有兩個算法在同一機器上運行，其執(zhí)行時間分別為 100n^2 和 2^n,要使前者快于后者

11、，n 至少要多大? ◆ 15 ◇ 最簡單最笨的辦法就是拿自然數(shù)去代唄。假定 n 取為 10，則前者的值是 10000，后者的值是 1024,小于前者，那我們就加個 5，用 15 代入得前者為 22500，后者為 32768，已經(jīng)比前者大但相差不多，那我們再減個 1，用 14 代入得，前者為 19600,后者為 16384，又比前者小了，所以結(jié)果得出來就是 n 至少要是 15. -----------------------------

12、--------------------------------------------------- 1.6 設(shè) n 為正整數(shù)，利用大“O“記號，將下列程序段的執(zhí)行時間表示為 n 的函數(shù)。 1.6 設(shè) n 為正整數(shù)，利用大“O“記號，將下列程序段的執(zhí)行時間表示為 n 的函數(shù)。 (1) i=1; k=0 while(i { k=k+10*i;i++; } ◆ T(n)=n-1 ∴ T(n)=O(n) ◇ 這個函數(shù)是按線性階遞增的