考研輔導(dǎo)之?dāng)?shù)據(jù)結(jié)構(gòu)

考研輔導(dǎo)之?dāng)?shù)據(jù)結(jié)構(gòu)第1章序言

數(shù)據(jù)(Data)：是客觀事物的符號(hào)表示。在計(jì)算機(jī)科學(xué)中指的是所有能輸入到計(jì)算機(jī)中并被計(jì)算機(jī)程序處理的符號(hào)的總稱。

數(shù)據(jù)元素(DataElement)：是數(shù)據(jù)的基本單位，在程序中通常作為一個(gè)整體來進(jìn)行考慮和處理。

一個(gè)數(shù)據(jù)元素可由若干個(gè)數(shù)據(jù)項(xiàng)(DataItem)組成。數(shù)據(jù)項(xiàng)是數(shù)據(jù)的不可分割的最小單位。數(shù)據(jù)項(xiàng)是對(duì)客觀事物某一方面特性的數(shù)據(jù)描述。數(shù)據(jù)對(duì)象(DataObject)：是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個(gè)子集。如字符集合C={‘A’,’B’,’C,…}。數(shù)據(jù)結(jié)構(gòu)(DataStructure)：是指相互之間具有(存在)一定聯(lián)系(關(guān)系)的數(shù)據(jù)元素的集合。元素之間的相互聯(lián)系(關(guān)系)稱為邏輯結(jié)構(gòu)。數(shù)據(jù)元素之間的邏輯結(jié)構(gòu)有四種基本類型，如圖1-3所示。①集合：結(jié)構(gòu)中的數(shù)據(jù)元素除了“同屬于一個(gè)集合”外，沒有其它關(guān)系。②線性結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一對(duì)一的關(guān)系。③樹型結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一對(duì)多的關(guān)系。④圖狀結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù)元素之間存在多對(duì)多的關(guān)系。

數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)內(nèi)存中的存儲(chǔ)包括數(shù)據(jù)元素的存儲(chǔ)和元素之間的關(guān)系的表示。元素之間的關(guān)系在計(jì)算機(jī)中有兩種不同的表示方法：順序表示和非順序表示。由此得出兩種不同的存儲(chǔ)結(jié)構(gòu)：順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。順序存儲(chǔ)結(jié)構(gòu)：用數(shù)據(jù)元素在存儲(chǔ)器中的相對(duì)位置來表示數(shù)據(jù)元素之間的邏輯結(jié)構(gòu)(關(guān)系)。鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)：在每一個(gè)數(shù)據(jù)元素中增加一個(gè)存放另一個(gè)元素地址的指針(pointer)，用該指針來表示數(shù)據(jù)元素之間的邏輯結(jié)構(gòu)(關(guān)系)。數(shù)據(jù)結(jié)構(gòu)的三個(gè)組成部分：邏輯結(jié)構(gòu)：數(shù)據(jù)元素之間邏輯關(guān)系的描述D_S=（D，S）存儲(chǔ)結(jié)構(gòu)：數(shù)據(jù)元素在計(jì)算機(jī)中的存儲(chǔ)及其邏輯關(guān)系的表現(xiàn)稱為數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)或物理結(jié)構(gòu)。數(shù)據(jù)操作：對(duì)數(shù)據(jù)要進(jìn)行的運(yùn)算。算法(Algorithm)：是對(duì)特定問題求解方法(步驟)的一種描述，是指令的有限序列，其中每一條指令表示一個(gè)或多個(gè)操作。算法具有以下五個(gè)特性①有窮性：一個(gè)算法必須總是在執(zhí)行有窮步之后結(jié)束，且每一步都在有窮時(shí)間內(nèi)完成。②

確定性：算法中每一條指令必須有確切的含義。不存在二義性。且算法只有一個(gè)入口和一個(gè)出口。③可行性：一個(gè)算法是能行的。即算法描述的操作都可以通過已經(jīng)實(shí)現(xiàn)的基本運(yùn)算執(zhí)行有限次來實(shí)現(xiàn)。④輸入：一個(gè)算法有零個(gè)或多個(gè)輸入，這些輸入取自于某個(gè)特定的對(duì)象集合。⑤輸出：一個(gè)算法有一個(gè)或多個(gè)輸出，這些輸出是同輸入有著某些特定關(guān)系的量。

評(píng)價(jià)一個(gè)好的算法有以下幾個(gè)標(biāo)準(zhǔn)①

正確性(Correctness)：算法應(yīng)滿足具體問題的需求。②可讀性(Readability)：算法應(yīng)容易供人閱讀和交流?？勺x性好的算法有助于對(duì)算法的理解和修改。③

健壯性(Robustness)：算法應(yīng)具有容錯(cuò)處理。當(dāng)輸入非法或錯(cuò)誤數(shù)據(jù)時(shí)，算法應(yīng)能適當(dāng)?shù)刈鞒龇磻?yīng)或進(jìn)行處理，而不會(huì)產(chǎn)生莫名其妙的輸出結(jié)果。④

通用性(Generality)：算法應(yīng)具有一般性，即算法的處理結(jié)果對(duì)于一般的數(shù)據(jù)集合都成立。⑤

效率與存儲(chǔ)量需求：效率指的是算法執(zhí)行的時(shí)間；存儲(chǔ)量需求指算法執(zhí)行過程中所需要的最大存儲(chǔ)空間。一般地，這兩者與問題的規(guī)模有關(guān)。算法中基本操作重復(fù)執(zhí)行的次數(shù)是問題規(guī)模n的某個(gè)函數(shù)，其時(shí)間量度記作T(n)=O(f(n))，稱作算法的漸近時(shí)間復(fù)雜度(AsymptoticTimecomplexity)，簡稱時(shí)間復(fù)雜度。一般地，常用最深層循環(huán)內(nèi)的語句中的原操作的執(zhí)行頻度(重復(fù)執(zhí)行的次數(shù))來表示?！癘”的定義：若f(n)是正整數(shù)n的一個(gè)函數(shù)，則O(f(n))表示

M≥0，使得當(dāng)n≥n0時(shí)，|f(n)|≤M

|f(n0)|。表示時(shí)間復(fù)雜度的階有：

O(1)：常量時(shí)間階O(n)：線性時(shí)間階

O(㏒n)：對(duì)數(shù)時(shí)間階O(n㏒n)：線性對(duì)數(shù)時(shí)間階

O(nk)：k≥2，k次方時(shí)間階例１兩個(gè)n階方陣的乘法for(i=1，i<=n;++i)for(j=1;j<=n;++j){c[i][j]=0;for(k=1;k<=n;++k)c[i][j]+=a[i][k]*b[k][j];}由于是一個(gè)三重循環(huán)，每個(gè)循環(huán)從1到n，則總次數(shù)為：n×n×n=n3時(shí)間復(fù)雜度為T(n)=O(n3)例２for(i=0;i<n;i++){++x;s=0;}將x自增看成是基本操作，則語句頻度為１，即時(shí)間復(fù)雜度為Ｏ(1)。如果將s=0也看成是基本操作，則語句頻度為２，其時(shí)間復(fù)雜度仍為Ｏ(1)，即常量階。例３for(i=1;i<=n;++i){++x;s+=x;}語句頻度為：2n，其時(shí)間復(fù)雜度為：O(n)，即為線性階。例４for(i=1;i<=n;++i)for(j=1;j<=n;++j){++x;s+=x;}語句頻度為：2n2，其時(shí)間復(fù)雜度為：O(n2)，即為平方階。例５for(i=2;i<=n;++i)for(j=2;j<=i-1;++j){++x;a[i,j]=x;}語句頻度為：1+2+3+…+n-2=(1+n-2)×(n-2)/2=(n-1)(n-2)/2=n2-3n+2∴時(shí)間復(fù)雜度為O(n2)，即此算法的時(shí)間復(fù)雜度為平方階。以下六種計(jì)算算法時(shí)間的多項(xiàng)式是最常用的。其關(guān)系為：

O(1)<O(㏒n)<O(n)<O(n㏒n)<O(n2)<O(n3)指數(shù)時(shí)間的關(guān)系為：O(2n)<O(n!)<O(nn)當(dāng)n取得很大時(shí)，指數(shù)時(shí)間算法和多項(xiàng)式時(shí)間算法在所需時(shí)間上非常懸殊。因此，只要有人能將現(xiàn)有指數(shù)時(shí)間算法中的任何一個(gè)算法化簡為多項(xiàng)式時(shí)間算法，那就取得了一個(gè)偉大的成就。

例6X=2;while（x<n/2）x=x*2AO(logn)BO(n)CO(nlogn)DO(n^2)A例7Inty=0;while(n>=(y+1)*(y+1))Y++;