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

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

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

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

一個數(shù)據(jù)元素可由若干個數(shù)據(jù)項(DataItem)組成。數(shù)據(jù)項是數(shù)據(jù)的不可分割的最小單位。數(shù)據(jù)項是對客觀事物某一方面特性的數(shù)據(jù)描述。數(shù)據(jù)對象(DataObject)：是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個子集。如字符集合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ù)元素除了“同屬于一個集合”外，沒有其它關(guān)系。②線性結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一對一的關(guān)系。③樹型結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一對多的關(guān)系。④圖狀結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù)元素之間存在多對多的關(guān)系。

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

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

評價一個好的算法有以下幾個標(biāo)準(zhǔn)①

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

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

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

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

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

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

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

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

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

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

例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++;