1緒論1.1數(shù)據(jù)結(jié)構(gòu)的研究?jī)?nèi)容1.2數(shù)據(jù)結(jié)構(gòu)的基本概念與術(shù)語1.3算法與算法分析1.4在線題目求解1緒論學(xué)習(xí)目標(biāo)1.記憶和理解數(shù)據(jù)結(jié)構(gòu)的基本概念和術(shù)語。2.記憶和理解算法的含義及其特性。3.初步學(xué)會(huì)算法分析的方法。4.理解如何更好地提高算法的時(shí)間、空間效率。1.1數(shù)據(jù)結(jié)構(gòu)的研究?jī)?nèi)容數(shù)據(jù)結(jié)構(gòu)主要研究非數(shù)值計(jì)算問題，重點(diǎn)考慮如何合理地組織數(shù)據(jù)，如何高效地處理數(shù)據(jù)。算法+數(shù)據(jù)結(jié)構(gòu)=程序算法：處理問題的策略數(shù)據(jù)結(jié)構(gòu)：?jiǎn)栴}的數(shù)學(xué)模型程序：為實(shí)現(xiàn)特定目標(biāo)或解決特定問題而用程序設(shè)計(jì)語言編寫的指令序列對(duì)于非數(shù)值計(jì)算程序設(shè)計(jì)問題，首先要考慮操作對(duì)象在計(jì)算機(jī)中的組織方式。1.1數(shù)據(jù)結(jié)構(gòu)的研究?jī)?nèi)容例1.1.1學(xué)生信息管理問題本例的數(shù)據(jù)模型為線性表。除了第一個(gè)和最后一個(gè)學(xué)生，其他每個(gè)學(xué)生的前一個(gè)位置和后一位置都有且僅有一個(gè)學(xué)生，是一種“一對(duì)一”的線性關(guān)系。1.1數(shù)據(jù)結(jié)構(gòu)的研究?jī)?nèi)容例1.1.2對(duì)弈問題本例的數(shù)據(jù)模型為樹結(jié)構(gòu)。對(duì)弈問題的局勢(shì)變化是一種“一對(duì)多”的關(guān)系，可用“樹”結(jié)構(gòu)表達(dá)。在樹結(jié)構(gòu)中，一個(gè)父結(jié)點(diǎn)可能有多個(gè)孩子結(jié)點(diǎn)，而每個(gè)結(jié)點(diǎn)最多只有一個(gè)父結(jié)點(diǎn)。1.1數(shù)據(jù)結(jié)構(gòu)的研究?jī)?nèi)容例1.1.3最短路徑問題問題描述：要求從始發(fā)城市（如1）到目的城市（如2）的行車距離盡可能短。本例的數(shù)據(jù)模型為圖結(jié)構(gòu)。任一個(gè)城市都可能與其他多個(gè)城市之間有直達(dá)道路，即任意兩個(gè)頂點(diǎn)之間是一種“多對(duì)多”的關(guān)系，這是一種“圖”結(jié)構(gòu)。1.1數(shù)據(jù)結(jié)構(gòu)的研究?jī)?nèi)容可見，非數(shù)值計(jì)算問題的數(shù)學(xué)模型是線性表、樹和圖等數(shù)據(jù)結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)主要研究非數(shù)值計(jì)算程序設(shè)計(jì)問題中的操作對(duì)象以及它們之間的關(guān)系和操作。1.2數(shù)據(jù)結(jié)構(gòu)的基本概念與術(shù)語基本概念數(shù)據(jù)：客觀事物的符號(hào)表示，是所有能輸入到計(jì)算機(jī)中并能被計(jì)算機(jī)程序處理的符號(hào)的總稱。數(shù)據(jù)可分為數(shù)值型數(shù)據(jù)（如整數(shù)、實(shí)數(shù)等）和非數(shù)值型數(shù)據(jù)（如字符串、圖形、圖像、聲音和動(dòng)畫等）。數(shù)據(jù)元素：數(shù)據(jù)的基本單位，也稱元素或記錄，在計(jì)算機(jī)中通常作為一個(gè)整體考慮。例如，表1-1中的每條學(xué)生記錄都是一個(gè)數(shù)據(jù)元素。數(shù)據(jù)項(xiàng)：組成數(shù)據(jù)元素的、有獨(dú)立含義的、不可分割的最小單位。例如，表1-1中的學(xué)生學(xué)號(hào)、姓名和專業(yè)都是數(shù)據(jù)項(xiàng)。1.2數(shù)據(jù)結(jié)構(gòu)的基本概念與術(shù)語基本概念數(shù)據(jù)對(duì)象：相同特性的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個(gè)子集。例如，表1-1的學(xué)生信息表及英文字母子集S={'A','B','C','D','E','F'}都是數(shù)據(jù)對(duì)象。數(shù)據(jù)結(jié)構(gòu)（DataStructure）：相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合?；蛘哒f，數(shù)據(jù)結(jié)構(gòu)是帶“結(jié)構(gòu)”的數(shù)據(jù)元素的集合，其中，“結(jié)構(gòu)”是指數(shù)據(jù)元素之間存在的關(guān)系。

數(shù)據(jù)結(jié)構(gòu)的三要素：邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)及相應(yīng)的算法。1.2數(shù)據(jù)結(jié)構(gòu)的基本概念與術(shù)語邏輯結(jié)構(gòu)邏輯結(jié)構(gòu)是指數(shù)據(jù)元素間抽象化的相互關(guān)系，與數(shù)據(jù)的存儲(chǔ)無關(guān)，獨(dú)立于計(jì)算機(jī)，是從具體問題抽象出來的數(shù)學(xué)模型。從邏輯結(jié)構(gòu)而言，數(shù)據(jù)結(jié)構(gòu)可歸結(jié)為線性結(jié)構(gòu)和非線性結(jié)構(gòu)，其中非線性結(jié)構(gòu)主要包括樹結(jié)構(gòu)和圖結(jié)構(gòu)，如圖1-3所示。1.2數(shù)據(jù)結(jié)構(gòu)的基本概念與術(shù)語存儲(chǔ)結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)也稱物理結(jié)構(gòu)，是數(shù)據(jù)元素及其關(guān)系在計(jì)算機(jī)存儲(chǔ)器中的存儲(chǔ)方式。存儲(chǔ)結(jié)構(gòu)可分為順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。順序存儲(chǔ)結(jié)構(gòu)借助元素在存儲(chǔ)器中的相對(duì)位置來表示數(shù)據(jù)元素間的邏輯關(guān)系，一般采用數(shù)組表示，如圖1-4所示。1.2數(shù)據(jù)結(jié)構(gòu)的基本概念與術(shù)語存儲(chǔ)結(jié)構(gòu)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)借助指示元素存儲(chǔ)地址的指針來表示數(shù)據(jù)元素間的邏輯關(guān)系，一般采用鏈表表示。帶頭結(jié)點(diǎn)的單鏈表如圖1-5所示，頭結(jié)點(diǎn)的地址設(shè)為5000，存放在頭指針head中；4個(gè)元素相應(yīng)結(jié)點(diǎn)的地址分別假設(shè)為2000、3000、4000、1000。對(duì)于單鏈表，后一個(gè)元素對(duì)應(yīng)結(jié)點(diǎn)的地址存儲(chǔ)在前一個(gè)結(jié)點(diǎn)的指針域，即前一個(gè)結(jié)點(diǎn)的指針域指向后一個(gè)結(jié)點(diǎn)。1.3算法與算法分析算法的定義及特性算法是為解決某類問題而規(guī)定的一個(gè)有限長(zhǎng)的操作序列（步驟）。一個(gè)算法必須滿足有窮性、確定性、可行性、有輸入、有輸出等五個(gè)特性。有窮性：算法的步驟有限，且每個(gè)步驟都能在有限時(shí)間內(nèi)完成。確定性：算法的每個(gè)步驟都有確切規(guī)定，不會(huì)產(chǎn)生二義性?？尚行裕褐杆惴ㄖ械拿總€(gè)步驟都是可行的，不會(huì)無法實(shí)現(xiàn)。有輸入：一個(gè)算法有0個(gè)或多個(gè)輸入。有輸出：一個(gè)算法有1個(gè)或多個(gè)輸出，表示算法進(jìn)行信息加工后得到的結(jié)果。因算法通常以函數(shù)描述，故算法的輸出經(jīng)常以函數(shù)的返回值或引用類型的形參表示。1.3算法與算法分析算法的評(píng)價(jià)從正確性、可讀性、健壯性、高效性等方面評(píng)價(jià)算法。正確性：算法能在有限運(yùn)行時(shí)間內(nèi)得到正確的結(jié)果?？梢酝ㄟ^精心設(shè)定測(cè)試數(shù)據(jù)的方法表明算法的正確性?？勺x性：算法容易為人閱讀和理解。通過添加適當(dāng)?shù)淖⑨屨Z句并合理縮排代碼可以提升算法的可讀性。健壯性：算法在遇到非法輸入時(shí)也能正常結(jié)束而不會(huì)崩潰?？梢酝ㄟ^對(duì)非法輸入進(jìn)行特判來提高算法的健壯性。高效性：時(shí)間高效性是指算法執(zhí)行效率高，可用時(shí)間復(fù)雜度衡量；空間高效性是指算法所占存儲(chǔ)空間節(jié)省，可用空間復(fù)雜度衡量。時(shí)間復(fù)雜度和空間復(fù)雜度是衡量算法優(yōu)劣的兩個(gè)主要指標(biāo)。1.3算法與算法分析算法的時(shí)間復(fù)雜度分析算法的時(shí)間效率度量涉及兩個(gè)相關(guān)術(shù)語，即問題規(guī)模和語句頻度。問題規(guī)模：算法求解問題輸入量的多少，是問題大小的本質(zhì)表示，一般用整數(shù)n表示。若輸入量與多個(gè)整數(shù)相關(guān)，則可用多個(gè)整數(shù)（如n、m等）表示問題規(guī)模。語句頻度：一條語句的重復(fù)執(zhí)行次數(shù)。一個(gè)算法的執(zhí)行時(shí)間可用該算法中所有語句的頻度之和來度量?；菊Z句：語句頻度最大的語句?？捎没菊Z句的頻度衡量一個(gè)算法的時(shí)間復(fù)雜度。1.3算法與算法分析算法的時(shí)間復(fù)雜度分析若計(jì)算基本語句的頻度得到問題規(guī)模n的函數(shù)f(n)，則算法的（漸近）時(shí)間復(fù)雜度T(n)如下：上式表示隨著問題規(guī)模n的增長(zhǎng)，算法執(zhí)行時(shí)間的增長(zhǎng)率和函數(shù)f(n)的增長(zhǎng)率相同。如何分析一個(gè)算法的時(shí)間復(fù)雜度：先找出其中的基本語句，再取其頻度函數(shù)f(n)的數(shù)量級(jí)（僅需最高次冪項(xiàng)并忽略其系數(shù)）用符號(hào)O表示。常見時(shí)間復(fù)雜度：常數(shù)階O(1)、對(duì)數(shù)階O(log2n)、線性階O(n)、線性對(duì)數(shù)階O(nlog2n)、平方階O(n2)、立方階O(n3)、k次方階O(nk)、指數(shù)階O(2n)等。1.3算法與算法分析例1.3.1分析兩個(gè)n階方陣相乘算法的時(shí)間復(fù)雜度找出基本語句為“c[i][j]+=a[i][k]*b[k][j];”，計(jì)算其頻度為n3，因此算法mult的時(shí)間復(fù)雜度為O(n3)。//以二維數(shù)組存儲(chǔ)矩陣元素，c為a和b的乘積，N、n分別方陣的最大大小和實(shí)際大小voidmult(inta[][N],intb[][N],intc[][N],intn){

for(inti=1;i<=n;i++){

for(intj=1;j<=n;j++){

c[i][j]=0;

for(intk=1;k<=n;k++){

c[i][j]+=a[i][k]*b[k][j];

}

}

}}1.3算法與算法分析例1.3.2分析選擇排序的時(shí)間復(fù)雜度//n個(gè)數(shù)據(jù)存放在a數(shù)組中，按升序排序voidselect_sort(inta[],intn){

for(inti=0;i<n-1;++i){

j=i;

for(intk=i+1;k<n;++k){

if(a[k]<a[j])j=k;

}

swap(a[j],a[i]);

}}找出基本語句為“if(a[k]<a[j])j=k;”，計(jì)算其頻度為

，因此算法select_sort的時(shí)間復(fù)雜度為O(n2)。1.3算法與算法分析例1.3.3分析以下代碼段的時(shí)間復(fù)雜度找出基本語句為“i*=2;”，計(jì)算其頻度為log2n，因此以上代碼段的時(shí)間復(fù)雜度為O(log2n)。inti=1;while(i<=n){

i*=2;}1.3算法與算法分析算法的空間復(fù)雜度分析算法的（漸近）空間復(fù)雜度S(n)如下：表示隨著問題規(guī)模n的增大，算法運(yùn)行所需存儲(chǔ)量的增長(zhǎng)率與某個(gè)函數(shù)g(n)的增長(zhǎng)率相同。算法的空間復(fù)雜度分析通常僅需考慮輔助存儲(chǔ)空間即可。若算法所需的輔助存儲(chǔ)空間相對(duì)于輸入數(shù)據(jù)量來說是常數(shù)，則稱該算法為原地工作，相應(yīng)的空間復(fù)雜度表示為O(1)。常見空間復(fù)雜度有O(1)、O(log2n)、O(n)等。1.3算法與算法分析例1.3.4分析逆置數(shù)組元素的空間復(fù)雜度算法reverse1使用一個(gè)長(zhǎng)度為n的輔助數(shù)組b，因此空間復(fù)雜度為O(n)。//算法reverse1voidreverse1(inta[],intn){

int*b=newint[n];

for(inti=n-1;i>=0;i--){

b[n-1-i]=a[i];

}

for(inti=0;i<n;i++){

a[i]=b[i];

}}1.3算法與算法分析例1.3.4分析逆置數(shù)組元素的空間復(fù)雜度算法reverse2僅使用一個(gè)輔助變量t，因此空間復(fù)雜度為O(1)。//算法reverse2voidreverse2(inta[],intn){

for(inti=0;i<n/2;i++){

intt=a[i];

a[i]=a[n-1-i];

a[n-1-i]=t;

}}1.4在線題目求解例1.4.1最大子列和問題

給定K個(gè)整數(shù)組成的序列{N1,N2,...,NK}，“連續(xù)子列”被定義為{Ni,Ni+1,...,Nj}，其中1≤i≤j≤K。“最大子列和”則被定義為所有連續(xù)子列元素的和中最大者。例如給定序列{-2,11,-4,13,-5,-2}，其連續(xù)子列{11,-4,13}有最大的和20?，F(xiàn)要求編寫程序，計(jì)算給定整數(shù)序列的最大子列和。輸入:

輸入第1行給出正整數(shù)K(≤100000)；第2行給出K個(gè)整數(shù)，其間以空格分隔。輸出:

在一行中輸出最大子列和。如果序列中所有整數(shù)皆為負(fù)數(shù)，則輸出0。輸出樣例:20輸入樣例:6-211-413-5-21.4在線題目求解例1.4.1最大子列和問題最大子列和也稱為最大子段和或最大子序列和，暴力求解方法是窮舉所有以i為起始位置，以j為終止位置的子序列，并求得其中的最大和值。對(duì)于同一個(gè)題目，不同求解方法的效率可能差別很大。如何有效提高算法的時(shí)間效率和空間效率是學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)需要重點(diǎn)關(guān)注的問題。下面給出三種不同時(shí)間復(fù)雜度的最大子列和求解算法。1.4在線題目求解例1.4.1最大子列和問題算法maxSum1采用三重循環(huán)求最大子段和，以O(shè)(n)的時(shí)間復(fù)雜度求一個(gè)子序列和，總的時(shí)間復(fù)雜度為O(n3)。intmaxSum1(inta[],intn){

//

三重循環(huán)，時(shí)間復(fù)雜度為立方階

intmax=0;

//

最大和

for(inti=0;i<n;i++){

for(intj=i;j<n;j++){

intsum=0;

//

a[i]~a[j]的和

for(intk=i;k<=j;k++){//

O(n)時(shí)間求一個(gè)子序列和

sum+=a[k];

}

if(sum>max){

max=sum;

}

}

}

returnmax;}1.4在線題目求解例1.4.1最大子列和問題算法maxSum2采用二重循環(huán)求最大子段和，以O(shè)(1)的時(shí)間復(fù)雜度求一個(gè)子序列和，總的時(shí)間復(fù)雜度為O(n2)。intmaxSum2(inta[],intn){

//

二重循環(huán)，時(shí)間復(fù)雜度為平方階

intmax=0;

//

最大和

f