數(shù)據(jù)結構與算法 課件 第1章 數(shù)據(jù)結構概述

第1章數(shù)據(jù)結構概述數(shù)據(jù)結構課程主要討論數(shù)據(jù)的表示（數(shù)據(jù)的結構）和數(shù)據(jù)處理的基本方法（算法）。要想成為一個優(yōu)秀的程序設計人員，至少需要以下三個條件：①

能夠熟練地選擇和設計各種數(shù)據(jù)結構和算法。

②至少要能夠熟練地掌握一門程序設計語言。

③熟知所涉及的相關應用領域的知識。1【本章重點】①數(shù)據(jù)結構及相關概念；②數(shù)據(jù)的邏輯結構和存儲結構，二者的關系；③算法及特性；④算法的時間復雜度和空間復雜度的概念。2【本章難點】①抽象數(shù)據(jù)類型的理解和使用；②描述算法的工具；③算法的時間復雜度分析與計算。3【本章內(nèi)容】數(shù)據(jù)結構的基本概念算法習題141.1數(shù)據(jù)結構的基本概念軟件開發(fā)的三個階段（1）分析階段：對問題進行分析，抽象出數(shù)據(jù)模型，形成求解問題的基本思路，確定解決問題的方案；（2）設計階段：將數(shù)據(jù)以及數(shù)據(jù)之間的關系存儲到計算機的內(nèi)存中，設計數(shù)據(jù)處理的算法；（3）實現(xiàn)階段：將算法轉(zhuǎn)換為用某種程序設計語言編寫的程序，并進行測試、修改，直到得到問題的解答。5關于數(shù)據(jù)結構的基本術語數(shù)據(jù)是信息的載體，它是描述客觀事物的數(shù)字、字符以及所有能輸入到計算機中并被計算機程序處理的符號的集合。例如，一個代數(shù)方程的求解程序中所用的數(shù)據(jù)是整數(shù)和實數(shù)；一個編譯程序或文本編輯程序中所使用的數(shù)據(jù)是字符串。隨著計算機應用領域的擴大，數(shù)據(jù)的含義更為廣泛，如圖像、聲音等都可以通過編碼而屬于數(shù)據(jù)的范疇。數(shù)據(jù)元素是數(shù)據(jù)的基本單位。有些情況下，數(shù)據(jù)元素也稱為元素、結點、頂點、記錄。數(shù)據(jù)項是具有獨立含義的，不可再分割的最小標識單位。一個數(shù)據(jù)元素可以由若干個數(shù)據(jù)項組成，6數(shù)據(jù)結構（DataStructure）是數(shù)據(jù)元素之間的相互關系，即數(shù)據(jù)的組織形式。一般來說，數(shù)據(jù)結構所研究的主要內(nèi)容包括以下三個方面：（1）數(shù)據(jù)的邏輯結構——數(shù)據(jù)元素之間的邏輯關系。（2）數(shù)據(jù)的存儲結構——數(shù)據(jù)元素及其關系在計算機中的存儲方式，數(shù)據(jù)的存儲結構又稱為數(shù)據(jù)的物理結構。（3）數(shù)據(jù)的運算——對數(shù)據(jù)施加的操作，即數(shù)據(jù)的運算。7數(shù)據(jù)的邏輯結構（1）集合：數(shù)據(jù)元素之間只是“屬于同一集合”的關系。（2）線性結構：數(shù)據(jù)元素之間存在“一對一”的前后順序關系，除第一個元素和最后一個元素之外，其余元素都有唯一的一個直接前驅(qū)元素和唯一的一個直接后繼元素。（3）樹形結構：數(shù)據(jù)元素之間存在“一對多”的層次關系，除最頂層的元素之外，其余元素都有若干個直接給后繼元素。（4）圖結構：數(shù)據(jù)元素之間存在“多對多”的任意關系，每個元素都有若干個直接前驅(qū)元素和若干個直接后繼元素。8數(shù)據(jù)的存儲結構（1）順序存儲結構

元素之間的邏輯關系由存儲單元的鄰接關系來體現(xiàn)。通常順序存儲結構是借助于程序語言的數(shù)組（又稱為向量）來描述的。

該方法主要應用于線性數(shù)據(jù)結構，非線性的數(shù)據(jù)結構也可以通過某種線性化的方法來實現(xiàn)順序存儲。（2）鏈式存儲結構

通過元素存儲地址的指針表示數(shù)據(jù)元素之間的邏輯關系，即邏輯上相鄰的元素在物理位置上不一定相鄰。通常要借助于程序語言的指針類型來描述它。（3）索引存儲結構

在存儲數(shù)據(jù)元素的同時，還需要有索引表，索引表中的每一項稱為索引項，其一般形式是（關鍵字，地址），關鍵字是能夠唯一標識一個元素的那些數(shù)據(jù)項。（4）散列存儲結構

根據(jù)數(shù)據(jù)元素的關鍵字計算出該元素的存儲地址。又稱為計算尋址的方式。91.2算法算法的定義

算法是對特定問題求解步驟的描述，是指令的有限序列。算法的性質(zhì)（1）輸入性：0至多個輸入。（2）輸出性：1至多個輸出。（3）有窮性:對于合法的輸入值，算法在執(zhí)行有窮步之后結束。（4）確定性:對于相同的輸入執(zhí)行相同的路徑，即對于相同的輸入只能得出相同的輸出。（5）可行性:用于描述算法的操作都是足夠基本的，即算法中描述的操作都是可以通過已經(jīng)實現(xiàn)的基本運算執(zhí)行有限次來實現(xiàn)的。10（1）自然語言

優(yōu)點：容易理解；缺點：不夠嚴謹，容易出現(xiàn)二義性。（2）流程圖

優(yōu)點：直觀易懂；缺點：嚴密性不如程序設計語言，靈活性不如自然語言。（3）程序設計語言

優(yōu)點：描述算法能夠由計算機執(zhí)行；缺點：抽象性差，設計者在設計算法時過于受到程序設計語言的語法規(guī)則限制，往往忽視了算法的正確性和邏輯性。（4）偽代碼

偽代碼是介于自然語言和高級語言之間的方法，例如用類C語言來描述算法。優(yōu)點：重點給出算法的邏輯，并且不受語言的語法規(guī)則限制?！纠浚≒8）用偽代碼描述求兩個正整數(shù)的最大公約數(shù)。11描述算法的工具對算法的評價標準

通常從正確性、易讀性、健壯性和高效性等四個方面評價算法的質(zhì)量。算法的高效性

算法的高效性包括時間特性和空間特性。時間特性是指執(zhí)行算法所需要的計算時間長短。空間特性則是執(zhí)行算法所需要的輔助存儲空間大小。（1）算法時間特性的分析

一個算法所需的計算時間，應當是該算法中每條語句的執(zhí)行時間之和，而每條語句的執(zhí)行時間是該語句的執(zhí)行次數(shù)（稱為頻度）與該語句執(zhí)行一次所需時間的乘積。

我們通過算法的時間復雜度來衡量算法的時間特性。12算法時間復雜度的計算【例1.2】求兩個n階方陣的乘積C＝A×B，其算法如下：＃definen自然數(shù)voidMatrixmlt(intA[n][n],intB[n][n],intC[n][n]){ inti,j,k;

語句頻度

for(i=0;i<n;i++) //語句①

n+1

for(j=0；j<n;j++){ //語句②

n(n+1)

C[i][j]=0; //語句③

n2

for(k=0;k<n;k++)//語句④

n2(n+1) C[i][j]=C[i][j]+A[i][k]*B[k][j];//語句⑤

n3 }}

算法中所有語句的頻度之和為T(n)=2n3+3n2+2n+1。算法的語句頻度之和T(n)是矩陣階數(shù)n的函數(shù)，n是算法求解方陣乘積問題的規(guī)模。13

一般情況下，算法中基本操作重復執(zhí)行的時間是問題規(guī)模n的某個函數(shù)f(n)，算法的時間復雜度記為T(n)=O(f(n))它表示隨問題規(guī)模n的增大，算法執(zhí)行時間的增長率和f(n)的增長率相同，f(n)一般是算法中頻度最大的語句頻度。例如，算法Matrixmlt的時間復雜度是T(n)=O(n3)，這里的f(n)=n3是該算法中語句⑤的頻度。由此可見，當有循環(huán)嵌套時，算法的時間復雜度是由最內(nèi)層語句的頻度f(n)決定的。

計算算法的時間復雜度要考慮問題的規(guī)模。14【例1.3】交換a和b的值。temp=a;a=b;b=temp;

以上三條單個語句的頻度都為1，該算法的執(zhí)行時間是一個與問題規(guī)模n無關的常數(shù)，時間復雜度記作T(n)=O(1)。事實上，只要算法的執(zhí)行時間不隨著問題的規(guī)模增加而增長，即使算法中有成百上千條語句，其時間復雜度也只是O(1)。15【例】在一維數(shù)組A[n]中順序查找值為k的元素，順序查找算法如下：intFind(intA[],intn,intk){ for(i=0;i<n;i++) if(A[i]==k)break; returni;}

算法從A[0]開始查找，如果A[0]的值就等于k，那么比較一次就查找到了，這是最好情況；如果A[n-1]的值等于k，則需要比較n次才能查找到，這是最壞情況；平均情況下需要比較(n+1)/2次。

計算算法的時間復雜度要考慮最壞情況。1617【例1.4】判斷n是否為素數(shù)。voidprime(intn){ inti=2;

while((n%i)!=0&&i<sqrt(n))

i++;

if(i>=sqrt(n))printf("%d是素數(shù)",n);

elseprintf("%d不是素數(shù)",n);}設語句i++；的頻度為f(n)，由i<sqrt(n)可知f(n)<sqrt(n)。時間復雜度應考慮最壞的情況，所以18【例1.5】變量計數(shù)。 i=1；1 while(i<=n)i=i*2;f(n)

由于2f(n)≤n，即f(n)≤log2n，取最大值f(n)=log2n，T(n)=O(f(n))=O(log2n)常見的時間復雜度按數(shù)量級遞增排列：常量階O(1)<對數(shù)階O(log2n)<線性階O(n)<線性對數(shù)階O(nlog2n)<平方階O(n2)<立方階O(n3)<…<k次方階O(nk)<指數(shù)階O(2n)算法的空間復雜度算法的空間復雜度是指在算法執(zhí)行過程中所需要的輔助存儲空間數(shù)量。輔助存儲空間是除算法本身和輸入輸出數(shù)據(jù)所占存儲空間之外，算法運行時臨時開辟的存儲空間，記為：S(n)=O(f(n))

其中n為問題的規(guī)模，分析方法與算法的時間復雜度類似。19算法的易讀性

一個高質(zhì)量的算法除了正確和運行效率高之外，還對算法的易讀性有一定的要求。算法的易讀性主要體現(xiàn)在算法的結構、代碼的書寫格式以及注釋等方面。（1）算法的結構

解決某個較為復雜問題的算法通常也是由一個個模塊組成的，而每個模塊的功能相對獨立。盡可能做到高內(nèi)聚、低耦合。（