《數(shù)據(jù)結(jié)構(gòu)(c語(yǔ)言版)習(xí)題集》算法設(shè)計(jì)題第一章

數(shù)據(jù)結(jié)構(gòu)第一章串講+習(xí)題答案+復(fù)習(xí)要點(diǎn)作者名：不詳來(lái)源：網(wǎng)友提供06年6月8日

本章的重點(diǎn)是了解數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)、數(shù)據(jù)的運(yùn)算三方面的概念及相互關(guān)系，難點(diǎn)是算法復(fù)雜度的分析方法。需要達(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)的兩大類邏輯結(jié)構(gòu)和四種常用的存儲(chǔ)表示方法。需要達(dá)到<領(lǐng)會(huì)>層次的內(nèi)容有算法、算法的時(shí)間復(fù)雜度和空間復(fù)雜度、最壞的和平均時(shí)間復(fù)雜度等概念，算法描述和算法分析的方法、對(duì)一般的算法要能分析出時(shí)間復(fù)雜度。對(duì)于基本概念，仔細(xì)看書就能夠理解，這里簡(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ù)就可稱是一個(gè)數(shù)據(jù)元素.又比如在一個(gè)數(shù)據(jù)庫(kù)(關(guān)系式數(shù)據(jù)庫(kù))中，一個(gè)記錄可稱為一個(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ù))，我們就稱它為一個(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)稱為數(shù)據(jù)結(jié)構(gòu)，數(shù)據(jù)的邏輯結(jié)構(gòu)分兩大類：線性結(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)稱為時(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)看書本上的例子，然后我們通過(guò)做練習(xí)加以領(lǐng)會(huì)和鞏固。數(shù)據(jù)結(jié)構(gòu)習(xí)題一1.1簡(jiǎn)述下列概念：數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)類型、數(shù)據(jù)結(jié)構(gòu)、邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)、線性結(jié)構(gòu)、非線性結(jié)構(gòu)?！魯?shù)據(jù)：指能夠被計(jì)算機(jī)識(shí)別、存儲(chǔ)和加工處理的信息載體?！魯?shù)據(jù)元素：就是數(shù)據(jù)的基本單位，在某些情況下，數(shù)據(jù)元素也稱為元素、結(jié)點(diǎn)、頂點(diǎn)、記錄。數(shù)據(jù)元素有時(shí)可以由若干數(shù)據(jù)項(xiàng)組成?！魯?shù)據(jù)類型：是一個(gè)值的集合以及在這些值上定義的一組操作的總稱?！魯?shù)據(jù)結(jié)構(gòu)：指的是數(shù)據(jù)之間的相互關(guān)系，即數(shù)據(jù)的組織形式。一般包括三個(gè)方面的內(nèi)容:數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)和數(shù)據(jù)的運(yùn)算?！暨壿嫿Y(jié)構(gòu)：指各數(shù)據(jù)元素之間的邏輯關(guān)系?！舸鎯?chǔ)結(jié)構(gòu)：就是數(shù)據(jù)的邏輯結(jié)構(gòu)用計(jì)算機(jī)語(yǔ)言的實(shí)現(xiàn)?！艟€性結(jié)構(gòu)：數(shù)據(jù)邏輯結(jié)構(gòu)中的一類，它的特征是若結(jié)構(gòu)為非空集，則該結(jié)構(gòu)有且只有一個(gè)開(kāi)始結(jié)點(diǎn)和一個(gè)終端結(jié)點(diǎn)，并且所有結(jié)點(diǎn)都最多只有一個(gè)直接前趨和一個(gè)直接后繼。線性表就是一個(gè)典型的線性結(jié)構(gòu)?！舴蔷€性結(jié)構(gòu)：數(shù)據(jù)邏輯結(jié)構(gòu)中的另一大類，它的邏輯特征是一個(gè)結(jié)點(diǎn)可能有多個(gè)直接前趨和直接后繼。1.2試舉一個(gè)數(shù)據(jù)結(jié)構(gòu)的例子、敘述其邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)、運(yùn)算三個(gè)方面的內(nèi)容?！衾缬幸粡垖W(xué)生成績(jī)表，記錄了一個(gè)班的學(xué)生各門課的成績(jī)。按學(xué)生的姓名為一行記成的表。這個(gè)表就是一個(gè)數(shù)據(jù)結(jié)構(gòu)。每個(gè)記錄(有姓名，學(xué)號(hào)，成績(jī)等字段)就是一個(gè)結(jié)點(diǎn)，對(duì)于整個(gè)表來(lái)說(shuō)，只有一個(gè)開(kāi)始結(jié)點(diǎn)(它的前面無(wú)記錄)和一個(gè)終端結(jié)點(diǎn)(它的后面無(wú)記錄)，其他的結(jié)點(diǎn)則各有一個(gè)也只有一個(gè)直接前趨和直接后繼(它的前面和后面均有且只有一個(gè)記錄)。這幾個(gè)關(guān)系就確定了這個(gè)表的邏輯結(jié)構(gòu)。那么我們?cè)鯓影堰@個(gè)表中的數(shù)據(jù)存儲(chǔ)到計(jì)算機(jī)里呢?用高級(jí)語(yǔ)言如何表示各結(jié)點(diǎn)之間的關(guān)系呢?是用一片連續(xù)的內(nèi)存單元來(lái)存放這些記錄(如用數(shù)組表示)還是隨機(jī)存放各結(jié)點(diǎn)數(shù)據(jù)再用指針進(jìn)行鏈接呢?這就是存儲(chǔ)結(jié)構(gòu)的問(wèn)題，我們都是從高級(jí)語(yǔ)言的層次來(lái)討論這個(gè)問(wèn)題的。(所以各位趕快學(xué)C語(yǔ)言吧)。最后，我們有了這個(gè)表(數(shù)據(jù)結(jié)構(gòu))，肯定要用它，那么就是要對(duì)這張表中的記錄進(jìn)行查詢，修改，刪除等操作，對(duì)這個(gè)表可以進(jìn)行哪些操作以及如何實(shí)現(xiàn)這些操作就是數(shù)據(jù)的運(yùn)算問(wèn)題了。1.3常用的存儲(chǔ)表示方法有哪幾種?常用的存儲(chǔ)表示方法有四種:

◆順序存儲(chǔ)方法：它是把邏輯上相鄰的結(jié)點(diǎn)存儲(chǔ)在物理位置相鄰的存儲(chǔ)單元里，結(jié)點(diǎn)間的邏輯關(guān)系由存儲(chǔ)單元的鄰接關(guān)系來(lái)體現(xiàn)。由此得到的存儲(chǔ)表示稱為順序存儲(chǔ)結(jié)構(gòu)。

◆鏈接存儲(chǔ)方法：它不要求邏輯上相鄰的結(jié)點(diǎn)在物理位置上亦相鄰，結(jié)點(diǎn)間的邏輯關(guān)系是由附加的指針字段表示的。由此得到的存儲(chǔ)表示稱為鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。

◆索引存儲(chǔ)方法：除建立存儲(chǔ)結(jié)點(diǎn)信息外，還建立附加的索引表來(lái)標(biāo)識(shí)結(jié)點(diǎn)的地址。

◆散列存儲(chǔ)方法：就是根據(jù)結(jié)點(diǎn)的關(guān)鍵字直接計(jì)算出該結(jié)點(diǎn)的存儲(chǔ)地址。1.4設(shè)三個(gè)函數(shù)f,g,h分別為f(n)=100n^3+n^2+1000,g(n)=25n^3+5000n^2,h(n)=n^1.5+5000nlgn請(qǐng)判斷下列關(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(nlgn)◆(1)成立。

這里我們復(fù)習(xí)一下漸近時(shí)間復(fù)雜度的表示法T(n)=O(f(n))，這里的"O"是數(shù)學(xué)符號(hào)，它的嚴(yán)格定義是"若T(n)和f(n)是定義在正整數(shù)集合上的兩個(gè)函數(shù)，則T(n)=O(f(n))表示存在正的常數(shù)C和n0,使得當(dāng)n≥n0時(shí)都滿足0≤T(n)≤C·f(n)。"用容易理解的話說(shuō)就是這兩個(gè)函數(shù)當(dāng)整型自變量n趨向于無(wú)窮大時(shí)，兩者的比值是一個(gè)不等于0的常數(shù)。這么一來(lái)，就好計(jì)算了吧。第(1)題中兩個(gè)函數(shù)的最高次項(xiàng)都是n^3,因此當(dāng)n→∞時(shí)，兩個(gè)函數(shù)的比值是一個(gè)常數(shù)，所以這個(gè)關(guān)系式是成立的?！簦?）成立?！簦?）成立?！簦?）不成立。1.5設(shè)有兩個(gè)算法在同一機(jī)器上運(yùn)行，其執(zhí)行時(shí)間分別為100n^2和2^n,要使前者快于后者，n至少要多大?◆15

最簡(jiǎn)單最笨的辦法就是拿自然數(shù)去代唄。假定n取為10，則前者的值是10000，后者的值是1024,小于前者，那我們就加個(gè)5，用15代入得前者為22500，后者為32768，已經(jīng)比前者大但相差不多，那我們?cè)贉p個(gè)1，用14代入得，前者為19600,后者為16384，又比前者小了，所以結(jié)果得出來(lái)就是n至少要是15.1.6設(shè)n為正整數(shù)，利用大"O"記號(hào)，將下列程序段的執(zhí)行時(shí)間表示為n的函數(shù)。(1)i=1;k=0

while(i

{k=k+10*i;i++;

}◆T(n)=n-1

∴T(n)=O(n)

這個(gè)函數(shù)是按線性階遞增的(2)i=0;k=0;

do{

k=k+10*i;i++;

}

while(i<>◆T(n)=n

∴T(n)=O(n)

這也是線性階遞增的(3)i=1;j=0;

while(i+j<=n)

{

if(i

elsei++;

}◆T(n)=n/2

∴T(n)=O(n)

雖然時(shí)間函數(shù)是n/2,但其數(shù)量級(jí)仍是按線性階遞增的。(4)x=n;//n>1

while(x>=(y+1)*(y+1))

y++;◆T(n)=n1/2

∴T(n)=O(n1/2)

最壞的情況是y=0，那么循環(huán)的次數(shù)是n1/2次，這是一個(gè)按平方根階遞增的函數(shù)。(5)x=91;y=100;

while(y>0)

if(x>100)

{x=x-10;y--;}

elsex++;◆T(n)=O(1)

這個(gè)程序看起來(lái)有點(diǎn)嚇人，總共循環(huán)運(yùn)行了1000次，但是我們看到n沒(méi)有?沒(méi)。這段程序的運(yùn)行是和n無(wú)關(guān)的，就算它再循環(huán)一萬(wàn)年，我們也不管他，只是一個(gè)常數(shù)階的函數(shù)。1.7算法的時(shí)間復(fù)雜度僅與問(wèn)題的規(guī)模相關(guān)嗎?◆No,事實(shí)上，算法的時(shí)間復(fù)雜度不僅與問(wèn)題的規(guī)模相關(guān)，還與輸入實(shí)例中的元素取值等相關(guān)，但在最壞的情況下，其時(shí)間復(fù)雜度就是只與求解問(wèn)題的規(guī)模相關(guān)的。我們?cè)谟懻摃r(shí)間復(fù)雜度時(shí)，一般就是以最壞情況下的時(shí)間復(fù)雜度為準(zhǔn)的。1.8按增長(zhǎng)率由小至大的順序排列下列各函數(shù)：2^100,(2/3)^n，(3/2)^n，n^n,,n!，2^n，lgn,n^lgn,n^(3/2)，√n

分析如下：2^100是常數(shù)階；(2/3)^n和(3/2)^n是指數(shù)階,其中前者是隨n的增大而減小的；n^n是指數(shù)方階；√n是方根階,n!就是n(n-1)(n-2)...就相當(dāng)于n次方階；2^n是指數(shù)階，lgn是對(duì)數(shù)階,n^lgn是對(duì)數(shù)方階,n^(3/2)是3/2次方階。根據(jù)以上分析按增長(zhǎng)率由小至大的順序可排列如下：◆(2/3)^n<2^100<lgn<√n<n^(3/2)<n^lgn<(3/2)^n<2^n<n!<n^n1.9有時(shí)為了比較兩個(gè)同數(shù)量級(jí)算法的優(yōu)劣，須突出主項(xiàng)的常數(shù)因子，而將低次項(xiàng)用大"O"記號(hào)表示。例如，設(shè)T1(n)=1.39nlgn+100n+256=1.39nlgn+O(n),T2(n)=2.0nlgn-2n=2.0lgn+O(n),這兩個(gè)式子表示，當(dāng)n足夠大時(shí)T1(n)優(yōu)于T2(n)，因?yàn)榍罢叩某?shù)因子小于后者。請(qǐng)用此方法表示下列函數(shù)，并指出當(dāng)n足夠大時(shí)，哪一個(gè)較優(yōu)，哪一個(gè)較劣?函數(shù)大"O"表示優(yōu)劣(1)T1(n)=5n^2-3n+60lgn◆5n^2+O(n)◆較差(2)T2(n)=3n^2+1000n+3lgn◆3n^2+O(n)◆其次(3)T3(n)=8n^2+3lgn◆8n^2+O(lgn)◆最差(4)T4(n)=1.5n^2+6000nlgn◆1.5n^2+O(nlgn)◆最優(yōu)第一章概論復(fù)習(xí)要點(diǎn)本章的復(fù)習(xí)要點(diǎn)是：數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)結(jié)構(gòu)(包括邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu))以及數(shù)據(jù)類型的概念、數(shù)據(jù)的邏輯結(jié)構(gòu)分為哪兩大類，及其邏輯特征、數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)可用的四種基本存儲(chǔ)方法。時(shí)間復(fù)雜度與漸近時(shí)間復(fù)雜度的概念，如何求算法的時(shí)間復(fù)雜度?？赡艹龅念}目有選擇題、填空題或簡(jiǎn)答題。如：.........是數(shù)據(jù)的基本單位，.........是具有獨(dú)立含義的最小標(biāo)識(shí)單位。什么是數(shù)據(jù)結(jié)構(gòu)?什么是數(shù)據(jù)類型?數(shù)據(jù)的............與數(shù)據(jù)的存儲(chǔ)無(wú)關(guān)，它是獨(dú)立于計(jì)算機(jī)的。數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)包括順序存儲(chǔ)結(jié)構(gòu)、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu).......................、...........................設(shè)n為正整數(shù)，利用大O記號(hào)，將該程序段的執(zhí)行時(shí)間表示為n的函數(shù)，則下列程序段的時(shí)間復(fù)雜度可表示為：(....)

x=91;y=100;

while(y>10)

if(x>100){x=x-10;y--;}

elsex++;

A.O(1)B.O(x)C.O(y)D.O(n)等等。數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)總結(jié)第一章概論作者名：不詳來(lái)源：網(wǎng)友提供06年6月8日

第一章概論

1.1基本概念和術(shù)語(yǔ)

數(shù)據(jù)是信息的載體,能被計(jì)算機(jī)識(shí)別、存儲(chǔ)和加工處理。

數(shù)據(jù)元素是數(shù)據(jù)的基本單位，可由若干個(gè)數(shù)據(jù)項(xiàng)組成，數(shù)據(jù)項(xiàng)是具有獨(dú)立含義的最小標(biāo)識(shí)單位。

數(shù)據(jù)結(jié)構(gòu)包括：1）數(shù)據(jù)的邏輯結(jié)構(gòu)，從邏輯關(guān)系上描述數(shù)據(jù)，與數(shù)據(jù)存儲(chǔ)無(wú)關(guān)，獨(dú)立于計(jì)算機(jī)；

2）數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)，是邏輯結(jié)構(gòu)用計(jì)算機(jī)語(yǔ)言的實(shí)現(xiàn)，依賴于計(jì)算機(jī)語(yǔ)言。

3）數(shù)據(jù)的運(yùn)算，定義在邏輯結(jié)構(gòu)上，每種邏輯結(jié)構(gòu)都有一個(gè)運(yùn)算集合。常用的：檢索/插入/刪除/更新/排序。

數(shù)據(jù)類型是一個(gè)值的集合及在值上定義的一組操作的總稱。分為原子類型和結(jié)構(gòu)類型。

抽象數(shù)據(jù)類型是抽象數(shù)據(jù)的組織和與之相關(guān)的操作。其優(yōu)點(diǎn)是將數(shù)據(jù)和操作封裝在一起實(shí)現(xiàn)了信息隱藏。

ADT是在概念層上描述問(wèn)題；類是在實(shí)現(xiàn)層上描述問(wèn)題；在應(yīng)用層上操作對(duì)象（類的實(shí)例）解決問(wèn)題。

數(shù)據(jù)的邏輯結(jié)構(gòu)有：1）線性結(jié)構(gòu)，若結(jié)構(gòu)是非空集則僅有一個(gè)開(kāi)始和終端結(jié)點(diǎn)，并且所有結(jié)點(diǎn)最多只有一個(gè)直接前趨和后繼。

2）非線性結(jié)構(gòu)，一個(gè)結(jié)點(diǎn)可能有多個(gè)直接前趨和后繼。

數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)有：1）順序存儲(chǔ)，把邏輯相鄰的結(jié)點(diǎn)存儲(chǔ)在物理上相鄰的存儲(chǔ)單元內(nèi)。

2）鏈接存儲(chǔ)，結(jié)點(diǎn)間的邏輯關(guān)系由附加指針字段表示。

3）索引存儲(chǔ)，存儲(chǔ)結(jié)點(diǎn)信息的同時(shí)，建立附加索引表，有稠密索引和稀疏索引。

4）散列存儲(chǔ)，按結(jié)點(diǎn)的關(guān)鍵字直接計(jì)算出存儲(chǔ)地址。

1.2學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的意義

程序設(shè)計(jì)的實(shí)質(zhì)是選擇一個(gè)好的數(shù)據(jù)結(jié)構(gòu)，設(shè)計(jì)一個(gè)好的算法。算法取決于描述實(shí)際問(wèn)題的數(shù)據(jù)結(jié)構(gòu)。

1.3算法的描述和分析

算法是任意一個(gè)良定義的計(jì)算過(guò)程，以一個(gè)或多個(gè)值輸入，并產(chǎn)生一個(gè)或多個(gè)值輸出。是用來(lái)解決一個(gè)計(jì)算問(wèn)題的工具。

問(wèn)題的輸入實(shí)例是滿足問(wèn)題陳述中所給出的限制、為計(jì)算該問(wèn)題的解所需要的所有輸入構(gòu)成。

評(píng)價(jià)算法的好壞是：1）算法是正確的；2）要考慮算法所耗的時(shí)間、存儲(chǔ)空間（輔助存儲(chǔ)）、易于理解，編碼，調(diào)試。

算法所耗時(shí)間是每條語(yǔ)句執(zhí)行時(shí)間之和，每條語(yǔ)句的執(zhí)行時(shí)間是該語(yǔ)句執(zhí)行次數(shù)與執(zhí)行時(shí)間的乘積。

算法求解問(wèn)題的輸入量稱問(wèn)題的規(guī)模。算法的時(shí)間復(fù)雜度T(n)是該算法的時(shí)間耗費(fèi)，是求解問(wèn)題規(guī)模n的函數(shù)。當(dāng)問(wèn)題規(guī)模趨向無(wú)窮大時(shí)，把T(n)的數(shù)量階稱算法的漸進(jìn)時(shí)間復(fù)雜度，記為O(n)。

常見(jiàn)的時(shí)間復(fù)雜度排列為：常數(shù)階、對(duì)數(shù)階、線性階、線性對(duì)數(shù)階、平方階、立方階、K次方階、指數(shù)階。

算法的空間復(fù)雜度S(n)是該算法的空間耗費(fèi)，是求解問(wèn)題規(guī)模n的函數(shù)。算法的漸進(jìn)空間復(fù)雜度簡(jiǎn)稱空間復(fù)雜度。

算法的時(shí)間復(fù)雜度和空間復(fù)雜度合稱算法的復(fù)雜度。

附結(jié)二:第一章概論

*************************************************************************************

數(shù)據(jù)就是指能夠被計(jì)算機(jī)識(shí)別、存儲(chǔ)和加工處理的信息的載體。

數(shù)據(jù)元素是數(shù)據(jù)的基本單位，可以由若干個(gè)數(shù)據(jù)項(xiàng)組成。數(shù)據(jù)項(xiàng)是具有獨(dú)立含義的最小標(biāo)識(shí)單位。

*************************************************************************************

數(shù)據(jù)結(jié)構(gòu)的定義：·邏輯結(jié)構(gòu)：從邏輯結(jié)構(gòu)上描述數(shù)據(jù)，獨(dú)立于計(jì)算機(jī)?！ぞ€性結(jié)構(gòu)：一對(duì)一關(guān)系。

·線性結(jié)構(gòu)：多對(duì)多關(guān)系。

·存儲(chǔ)結(jié)構(gòu)：是邏輯結(jié)構(gòu)用計(jì)算機(jī)語(yǔ)言的實(shí)現(xiàn)。·順序存儲(chǔ)結(jié)構(gòu)：如數(shù)組。

·鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)：如鏈表。

·索引存儲(chǔ)結(jié)構(gòu)：·稠密索引：每個(gè)結(jié)點(diǎn)都有索引項(xiàng)。

·稀疏索引：每組結(jié)點(diǎn)都有索引項(xiàng)。

·散列存儲(chǔ)結(jié)構(gòu)：如散列表。

·數(shù)據(jù)運(yùn)算?！?duì)數(shù)據(jù)的操作。定義在邏輯結(jié)構(gòu)上，每種邏輯結(jié)構(gòu)都有一個(gè)運(yùn)算集合。

·常用的有：檢索、插入、刪除、更新、排序。

*************************************************************************************

數(shù)據(jù)類型：是一個(gè)值的集合以及在這些值上定義的一組操作的總稱。·原子類型：由語(yǔ)言提供。

·結(jié)構(gòu)類型：由用戶借助于描述機(jī)制定義，是導(dǎo)出類型。

抽象數(shù)據(jù)類型ADT：·是抽象數(shù)據(jù)的組織和與之的操作。相當(dāng)于在概念層上描述問(wèn)題。

·優(yōu)點(diǎn)是將數(shù)據(jù)和操作封裝在一起實(shí)現(xiàn)了信息隱藏。

*************************************************************************************

程序設(shè)計(jì)的實(shí)質(zhì)是對(duì)實(shí)際問(wèn)題選擇一種好的數(shù)據(jù)結(jié)構(gòu)，設(shè)計(jì)一個(gè)好的算法。算法取決于數(shù)據(jù)結(jié)構(gòu)。

*************************************************************************************

算法是一個(gè)良定義的計(jì)算過(guò)程，以一個(gè)或多個(gè)值輸入，并以一個(gè)或多個(gè)值輸出。

評(píng)價(jià)算法的好壞的因素：·算法是正確的；

·執(zhí)行算法的時(shí)間；

·執(zhí)行算法的存儲(chǔ)空間（主要是輔助存儲(chǔ)空間）；

·算法易于理解、編碼、調(diào)試。

*************************************************************************************

時(shí)間復(fù)雜度：是某個(gè)算法的時(shí)間耗費(fèi)，它是該算法所求解問(wèn)題規(guī)模n的函數(shù)。

漸近時(shí)間復(fù)雜度：是指當(dāng)問(wèn)題規(guī)模趨向無(wú)窮大時(shí)，該算法時(shí)間復(fù)雜度的數(shù)量級(jí)。

評(píng)價(jià)一個(gè)算法的時(shí)間性能時(shí)，主要標(biāo)準(zhǔn)就是算法的漸近時(shí)間復(fù)雜度。

算法中語(yǔ)句的頻度不僅與問(wèn)題規(guī)模有關(guān)，還與輸入實(shí)例中各元素的取值相關(guā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)。

空間復(fù)雜度：是某個(gè)算法的空間耗費(fèi)，它是該算法所求解問(wèn)題規(guī)模n的函數(shù)。

算法的時(shí)間復(fù)雜度和空間復(fù)雜度合稱算法復(fù)雜度。嚴(yán)蔚敏《數(shù)據(jù)結(jié)構(gòu)(c語(yǔ)言版)習(xí)題集》算法設(shè)計(jì)題第一章答案

第一章緒論1.16voidprint_descending(intx,inty,intz)//按從大到小順序輸出三個(gè)數(shù)

{

scanf("%d,%d,%d",&x,&y,&z);

if(x<y)x<->y;//<->為表示交換的雙目運(yùn)算符,以下同

if(y<z)y<->z;

if(x<y)x<->y;//冒泡排序

printf("%d%d%d",x,y,z);

}//print_descending1.17Statusfib(intk,intm,int&f)//求k階斐波那契序列的第m項(xiàng)的值f

{

inttempd;

if(k<2||m<0)returnERROR;

if(m<k-1)f=0;

elseif(m==k-1)f=1;

else

{

for(i=0;i<=k-2;i++)temp[i]=0;

temp[k-1]=1;//初始化

for(i=k;i<=m;i++)//求出序列第k至第m個(gè)元素的值

{

sum=0;

for(j=i-k;j<i;j++)sum+=temp[j];

temp[i]=sum;

}

f=temp[m];

}

returnOK;

}//fib

分析:通過(guò)保存已經(jīng)計(jì)算出來(lái)的結(jié)果,此方法的時(shí)間復(fù)雜度僅為O(m^2).如果采用遞歸編程(大多數(shù)人都會(huì)首先想到遞歸方法),則時(shí)間復(fù)雜度將高達(dá)O(k^m).1.18typedefstruct{

char*sport;

enum{male,female}gender;

charschoolname;//校名為'A','B','C','D'或'E'

char*result;

intscore;

}resulttype;typedefstruct{

intmalescore;

intfemalescore;

inttotalscore;

}scoretype;voidsummary(resulttyperesult[])//求各校的男女總分和團(tuán)體總分,假設(shè)結(jié)果已經(jīng)儲(chǔ)存在result[]數(shù)組中

{

scoretypescore;

i=0;

while(result[i].sport!=NULL)

{

switch(result[i].schoolname)

{

case'A':

score[0].totalscore+=result[i].score;

if(result[i].gender==0)score[0].malescore+=result[i].score;

elsescore[0].femalescore+=result[i].score;

bre