第1章緒論數(shù)值計算非數(shù)值計算數(shù)據(jù)結(jié)構(gòu)表達(dá)了數(shù)據(jù)結(jié)構(gòu)與算法的聯(lián)系及其在程序中的地位程序就是在數(shù)據(jù)的某些特定的結(jié)構(gòu)和表示的基礎(chǔ)上對于算法的描述算法與數(shù)據(jù)結(jié)構(gòu)是程序設(shè)計中相輔相成、不可分割的兩個方面程序=數(shù)據(jù)結(jié)構(gòu)+算法研究數(shù)據(jù)的特性以及數(shù)據(jù)之間的關(guān)系1.1數(shù)據(jù)結(jié)構(gòu)線性表例1書目檢索系統(tǒng)書目文件按書名按分類號高等數(shù)學(xué)0理論力學(xué)0線性代數(shù)0………002,…001,003,……索引表登錄號：書名：作者名：分類號：位：間：單時價格：書目卡片back例2

人機(jī)對奕問題樹……..……..…...…...…...…...back例3-1

交通問題圖結(jié)構(gòu)back課程代號課程名稱先修棵C1程序設(shè)計基礎(chǔ)無C2離散數(shù)學(xué)C1C3數(shù)據(jù)結(jié)構(gòu)C1,C2C4匯編語言C1C5語言的設(shè)計和分析C3,C4C6計算機(jī)原理C11C7編譯原理C3.C5C8操作系統(tǒng)C3,C6C9高等數(shù)學(xué)無C10線性代數(shù)C9C11普通物理C9C12數(shù)值分析C1,C9,C10C1C3C4C2C5C6C7C8C9C10C11C12例3-2

教學(xué)計劃編排問題圖數(shù)據(jù)結(jié)構(gòu):是研究非數(shù)值計算的程序設(shè)計問題中計算機(jī)的操作對象以及它們之間關(guān)系和運算的一門學(xué)科。研究目的尋求有效的組織和處理非數(shù)值數(shù)據(jù)的理論技術(shù)和方法，這類數(shù)據(jù)具有量大且具有一定內(nèi)在邏輯關(guān)系的特點。研究內(nèi)容結(jié)構(gòu)以及相應(yīng)包括三個方面：數(shù)據(jù)的邏輯結(jié)構(gòu)，的基本操作運算的定義

。數(shù)據(jù)結(jié)構(gòu)的研究目的和研究內(nèi)容1.2

基本概念和術(shù)語數(shù)據(jù)（data）：對客觀事物的符號表示，在計算機(jī)科學(xué)中是所有能輸入到計算機(jī)中并能被計算機(jī)程序處理的符號的總稱。數(shù)據(jù)元素(data

element)：數(shù)據(jù)的基本單位，在計算機(jī)程序中通常作為一個整體進(jìn)行考慮和處理。也稱節(jié)點（node）或記錄（record）一個數(shù)據(jù)元素可由若干個數(shù)據(jù)項（data

item）組成。1.2返回數(shù)據(jù)元素數(shù)據(jù)項：有獨立含義的數(shù)據(jù)最小單位，也稱域(field)1.2

基本概念和術(shù)語數(shù)據(jù)對象(data

object)：是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個子集。數(shù)據(jù)結(jié)構(gòu)（DataStructure）：簡稱DS，是數(shù)據(jù)元素和數(shù)據(jù)元素關(guān)系的集合。1.2返回數(shù)據(jù)項個數(shù)和類型均相同1.21.2

基本概念和術(shù)語數(shù)據(jù)結(jié)構(gòu)的形式化定義：Data-Structure=(D,

S)D：數(shù)據(jù)元素的有限集

S:是D上關(guān)系的有限集(邏輯結(jié)構(gòu))數(shù)據(jù)結(jié)構(gòu)中的“關(guān)系”描述的是數(shù)據(jù)元

間的邏輯關(guān)系，因此又稱為邏輯結(jié)構(gòu)。數(shù)據(jù)的邏輯結(jié)構(gòu)通常分為四種基本類型：集合結(jié)構(gòu)線性結(jié)構(gòu)樹結(jié)構(gòu)二元組圖結(jié)構(gòu)（網(wǎng)狀結(jié)構(gòu)）非線性結(jié)構(gòu)在集合結(jié)構(gòu)中的數(shù)據(jù)元 間僅存在“同屬于一個集合”的關(guān)系。如下圖所示。1.2(1)集合圖1-1

集合結(jié)構(gòu)(2)線性結(jié)構(gòu)元

間是一一對應(yīng)的關(guān)系，首元素?zé)o前趨，尾元素?zé)o后繼，其他元素都只有一個前驅(qū)和后繼。圖1-2 線性結(jié)構(gòu)【例】Linear=(D,R)D={1,2,3,4}R={<1,2>,<2,3>,<3,4>}1

2

3

41.2click元間存在一對多的關(guān)系，其中只有一個元素沒有前驅(qū)，稱為根。其他元素只有一個前驅(qū)，但可以有多個后繼。如右圖1-3所示。【例】Tree=(D,R)D={a,b,c,d,e,f}R={<a,b>,<a,c>,<a,d>,<b,e>,<b,f>}acb

def1.2(3)樹型結(jié)構(gòu)圖1-3 樹形結(jié)構(gòu)click間都可以繼。元

間存在多對多的關(guān)系，任何元存在關(guān)系。【例】Graph=(D,R)D={1,2,3,4}R={<1,2>,<1,3>,<2,4>,<3,4>,<3,2>}13

24(4)圖型結(jié)構(gòu)在圖形結(jié)構(gòu)中，每個結(jié)點可以有多個前驅(qū)和任意個后1.2樹和圖也稱為非線性結(jié)構(gòu)click集合線性結(jié)構(gòu)非線性結(jié)構(gòu)—般線性表線性表推廣特殊線性表樹型結(jié)構(gòu)圖型結(jié)構(gòu)線性表棧和隊列串?dāng)?shù)組廣義表樹二叉樹有向圖無向圖數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)②鏈?zhǔn)降刂返闹羔槺硎緮?shù)據(jù)結(jié)構(gòu)——借助指示元素元素間的邏輯關(guān)系③索引存貯結(jié)構(gòu)④散列存貯結(jié)構(gòu)數(shù)據(jù)的

結(jié)構(gòu)是數(shù)據(jù)及其邏輯結(jié)構(gòu)在計算機(jī)內(nèi)存中的方式，又稱物理結(jié)構(gòu)。①順序

結(jié)構(gòu)——借助元素在

器中的相對位置來表示數(shù)據(jù)元素間的邏輯關(guān)系5．

結(jié)構(gòu)1.2Lo元素1Lo+m元素2Lo+(i-1)*m……..元素iLo+（n-1)*m……..元素n地址內(nèi)容Loc(元素i)=Lo+(i-1)*m順序元素2元素1元素3∧元素4h地址內(nèi)容指針1345元素114001346元素4∧…….……..…….1400元素21536…….……..…….1536元素31346鏈?zhǔn)浇Y(jié)構(gòu)是邏輯關(guān)系的映象與元素本身映象，是數(shù)據(jù)結(jié)構(gòu)的實現(xiàn)邏輯結(jié)構(gòu)是數(shù)據(jù)結(jié)構(gòu)的抽象邏輯結(jié)構(gòu)與結(jié)構(gòu)的關(guān)系算法設(shè)計 邏輯結(jié)構(gòu)算法實現(xiàn)

結(jié)構(gòu)邏輯結(jié)構(gòu)結(jié)構(gòu)

運算集合數(shù)據(jù)結(jié)構(gòu)的研究內(nèi)容6．?dāng)?shù)據(jù)類型(data

type)高級編程語言中對應(yīng)一個值集（相同性質(zhì)）和該值集上的一組操作。如：字符類型、整數(shù)類型等。按值的不同特性分為：原子類型：值不可分解。如整形、實型、字符型等。結(jié)構(gòu)類型：值由若干成分按某種結(jié)構(gòu)組成，可分解。如：數(shù)組，結(jié)構(gòu)體，聯(lián)合體、類。1.2返回7．抽象數(shù)據(jù)類型（

Data

Type---ADT）抽象數(shù)據(jù)類型是指一個數(shù)學(xué)模型以及在該模型上定義的一組操作的集合。表示方法三元組的形式（D，S，P）ADT

抽象數(shù)據(jù)類型名{數(shù)據(jù)對象：<數(shù)據(jù)對象的定義>數(shù)據(jù)關(guān)系：<數(shù)據(jù)關(guān)系的定義>基本操作：<基本操作的定義>}ADT

抽象數(shù)據(jù)類型名1.2返回應(yīng)用舉例----ADT

Triplet（P9）ADT

Triplet{數(shù)據(jù)對象：D＝{e1,e2,e3|

e1,e2,e3∈ElemSet}數(shù)據(jù)關(guān)系：R＝{<e1,e2>,<e2,e3>}基本操作：InitTriplet(&T,v1,v2,v3)DestroyTriplet(&T)Put(&T,

i

,e)Get(T,

i

,&e)IsAscending(T)IsDescending(T)Max(T,&e)Min(T,&e)}

ADT

Triplet本書選用類C語言作為描述算法的工具。簡單說明類C語言的語法結(jié)構(gòu)（書P10）(1)預(yù)定義常量和類型：//函數(shù)結(jié)果狀態(tài)代碼#defineTRUE1#defineFALSE0#defineOK1#defineERROR0#defineINFEASIBLE—1#defineOVERFLOW—2//Status是函數(shù)的類型，其值是函數(shù)結(jié)果狀態(tài)代碼typedef

int

Status；1.3

抽象數(shù)據(jù)類型的表示與實現(xiàn)算法的表示：自然語言表示算法流程圖表示法（3）N-S框圖表示法偽代碼表示法程序設(shè)計語言表示法(2)數(shù)據(jù)結(jié)構(gòu)的表示(結(jié)構(gòu))用類型定義(typedef)描述。數(shù)據(jù)元素類型約定為ElemType，由用戶在使用該數(shù)據(jù)類型時自行定義。(3)基本操作的算法都用以下形式的函數(shù)描述：函數(shù)類型函數(shù)名(函數(shù)參數(shù)表){//算法說明語句序列}

//函數(shù)名除了函數(shù)的參數(shù)需要說明類型外，算法中使用的輔助變量可以不作變量說明，必要時對其作用給予注釋。當(dāng)函數(shù)返回值為函數(shù)結(jié)果狀態(tài)代碼時，函數(shù)定義為Status類型。為了便于算法描述，除了值調(diào)用方式外，增添了C++語言的

調(diào)用的參數(shù)傳遞方式。在形參表中，以&打頭的參數(shù)即為

參數(shù)。(4)賦值語句有簡單賦值串聯(lián)賦值成組賦值變量名=表達(dá)式；變量名1

=變量名2

=

…

=

變量名k =

表達(dá)式；(變量名1，…，變量名k)=(表達(dá)式1，…，表達(dá)式k)；結(jié)構(gòu)名=結(jié)構(gòu)名；結(jié)構(gòu)名=(值1，…，值k)；變量名[]=表達(dá)式；變量名[起始下標(biāo)..終止下標(biāo)]=變量名[起始下標(biāo)..終止下標(biāo)]變量名→變量名；變量名=條件表達(dá)式？表達(dá)式T:表達(dá)式F交換賦值條件賦值(5)選擇語句有條件語句1條件語句2if(表達(dá)式)語句；if(表達(dá)式)語句；else語句；switch(表達(dá)式){case值1

：語句序列1；break;….case值n

：語句序列n；break：default

：語句序列n+1；}switch

{case

條件1

：語句序列1；break;….case

條件n：語句序列n；break：default

：語句序列n+1；}開關(guān)語句1開關(guān)語句2(6)循環(huán)語句有for語句while語句for(賦初值表達(dá)式序列；條件；修改表達(dá)式序列）語句；while(條件)語句；do-while語句do{語句序列；}while(條件)；(7)結(jié)束語句有函數(shù)結(jié)束浯句return表達(dá)式return；break；exit(異常代碼);case結(jié)束語句異常結(jié)束語句(8)輸入和輸出語句有輸入語句輸出語句scanf([格式串]，變量1，…，變量n)；printf([格式串]，表達(dá)式1，…，表達(dá)式n);通常省略格式串。注釋單行注釋//文字序列邏輯運算約定與運算﹠﹠或運算︱︳非運算！1.3

#define

OK

1#define

ERROR

0typedef

int

ElemType;typedef

int

Status;typedef

ElemType

Triplet[3];Status

Get(Triplet

T,int

i,ElemType

&e){//1≤i≤3，用e返回T的第i元的值。

int

b;if

(i<1

||i>3)

return

ERROR;b=T[i-1];e=b;

return

OK;}

//

Get2020/11/27struct card

{int

num;]0echar

name[20char

author[1char

publishfloat

price;};typedef

struct card{int

num;char

name[20];char

author[10];char

publisher[30];float

price;}

ElemType;

,

*lbk;ElemType

a;lbkb;例1-7

抽象數(shù)據(jù)類型Triplet的表示與實現(xiàn)//-----采用動態(tài)分配的順序

結(jié)構(gòu)-------typedef

ElemType

*Triplet;

//由InitTriplet分配三個元素

空間一、基本操作的函數(shù)原型說明Status

InitTriplet(Triplet

&

emType

v1,ElemType

v2,ElemType

v3);//操作結(jié)果：構(gòu)造了三元組T，元素e1，e2和e3分別被賦以參數(shù)v1，v2和v3的值。Status

DestroyTriplet(Triplet&T);//操作結(jié)果：三元組T被銷毀。1.3一、基本操作的函數(shù)原型說明（續(xù)）Status

Get(Triplet

T,int

i,ElemType

&e);//初始條件：三元組T已存在，1≤i≤3。//操作結(jié)果：用e返回T的第i元的值。Status

Put(Triplet

&T,int

i,ElemType

e);//初始條件：三元組T已存在，1≤i≤3。//操作結(jié)果：改變T的第i元的值為e。Status

IsAscending(Triplet

T);//初始條件：三元組T已存在。//操作結(jié)果：如果T的三個元素按升序排列，則返回1，否則返回0。1.31.3一、基本操作的函數(shù)原型說明（續(xù)）Status

IsDescending(Triplet

T);//初始條件：三元組T已存在。//操作結(jié)果：如果T的三個元素按降序排列，則返回1，否則返回0。Status

Max(Triplet

emType

&e);//初始條件：三元組T已存在。//操作結(jié)果：用e返回T的三個元素中的最大值。Status

Min(Triplet

emType

&e);//初始條件：三元組T已存在。//操作結(jié)果：用e返回T的三個元素中的最小值例1-7（續(xù)）1.3空間失敗if(!T)exit(OVERFLOW);//分配T[0]=v1;

T[1]=v2;

T[2]=v3;return

OK;}

//

InitTriplet二、基本操作的實現(xiàn)---構(gòu)造三元組Status

InitTriplet(Triplet

&

emType

v1,ElemType

v2,ElemType

v3){//構(gòu)造三元組T，依次置T的三個元素的初值為v1，v2和v3。T=(ElemType

*)malloc(3

*sizeof(ElemType));//分配3個元素的

空間例1-7（續(xù)）1.3Status

DestroyTriplet(Triplet

&T){

free(T);

T=NULL;return

OK;}//

DestroyTriplet//銷毀三元組T。例1-7（續(xù)）二、基本操作的實現(xiàn)---銷毀三元組1.3if

(i<1

||i>3)

return

ERROR;return

Ok;}

//

Put二、基本操作的實現(xiàn)---為三元組某元素賦值Status

Put(Triplet

&T,int

i,ElemType

e){//1≤i≤3，置T的第i元的值為e。T[i-1]=e;例1-7（續(xù)）1.3二、基本操作的實現(xiàn)---三元組元素升/降序排列Status

IsAscending(Triplet

T){//如果T的三個元素按升序排列，則返回1，否則返回0。return

(T[0]<=T[1])

&&

(T[1]<=T[2]);}

//

IsAscendingStatus

IsDescending(Triplet

T){//如果T的三個元素按降序排列，則返回1，否則返回0。return

(T[0]>=T[1])

&&

(T[1]>=T[2]);}

//

IsDescending例1-7（續(xù)）1.3二、基本操作的實現(xiàn)（續(xù)）---求最大最小值Status

Max(Triplet

emType

&e){//用e返回T的三個元素中的最大值。e=(T[0]>=T[1])?((T[0]>=T[2])?T[0]:T[2]):((T[1]>=T[2])?T[1]:T[2]);return

OK;}

//

MaxStatus

Min(Triplet

emType

&e){//用e返回T的三個元素中的最小值。e=(T[0]<=T[1])?((T[0]<=T[2])?T[0]:T[2]):((T[1]<=T[2])?T[1]:T[2]);return

OK;}

//

Min例1-7（續(xù)）1.4

算法和算法分析1.4.1算法1、算法的定義：是解決問題的步驟和方法。即為解決某一特定類型問題的有限運算序列。1.4.1算法1.4

算法和算法分析2、算法的特征輸入：零個輸入和多個輸入輸出：一個或多個輸出有窮性：不會死循環(huán)可行性：新的操作必須是基本操作的有限組合確定性：無二義性，相同輸入必須有相同的執(zhí)行結(jié)果1.4.1算法1.4.2、算法設(shè)計的要求評價一個算法一般從4個方面進(jìn)行：正確性，必須利用數(shù)據(jù)進(jìn)行算法測試可讀性，必須為算法增加豐富的注釋信息健壯性(Robustness)，必須利用

數(shù)據(jù)對算法進(jìn)

試高效性，時間復(fù)雜度和空間復(fù)雜度都盡量的低。時間復(fù)雜度是對算法速度的衡量；空間復(fù)雜度是對算法占用內(nèi)存量的衡量。時間復(fù)雜度和空間復(fù)雜度是一對，可以相互轉(zhuǎn)化。1.4.2算法設(shè)計的要求1.4.3

算法效率的度量1、算法運行時間的度量：度量算法執(zhí)行時間通常有兩種方法：事后統(tǒng)計的方法事前分析估算的方法1.4.3算法效率的度量使用時間單位衡量算法的效率是不合適的。1.4.3

算法效率的度量分析：不是針對實際執(zhí)行時間的精確地算出算法執(zhí)行具體時間，而是針對算法中語句的執(zhí)行次數(shù)做出估計，從中得到算法執(zhí)行時間的信息。語句頻度定義：語句頻度是指該語句在一個算法中重復(fù)執(zhí)行的次數(shù)。例如：兩個矩陣相乘算法語句

for（i=0；i<n;i++）for

（j=0；j<n;j++）{c[i][j]=0;for

(k=0;k<

n;

k++)對應(yīng)的語句頻度1234nn2n2n3n3c[i][j]=c[i][j]+a[i][k]*b[k][j];}總執(zhí)行次數(shù)：Tn=2n3+2n2

+nback算法的時間復(fù)雜度假如，隨著問題規(guī)模n

的增長，算法執(zhí)行時間的增長率和f(n)

的增長率相同，則可記作：T

(n)=O(f(n))稱T

(n)為算法的(漸近)時間復(fù)雜度，簡稱時間復(fù)雜度。一般情況下，隨n的增大較慢的算法為最優(yōu)算法。為了便于比較同一問題的不同算法，通常的做法是，從算法中選取一種對于研究問題（或算法類型）來說是基本操作的原操作，以該基本操作重復(fù)執(zhí)行的次數(shù)作為算法的時間量度。clickTn=2n3+2n2

+n時間復(fù)雜度的計算：程序頻度時間復(fù)雜度例1：{++x;s=0;}1O(1)常量階例2：for(i=1;i<=n;++i)nO(n)線性階例3：{++x;s+=x;}for(j=1;j<=n;++j)for(k=1;k<=n;++k){++x;s+=x;}n2O(n2)平方階T(n)=O(f(n))1.4.3算法效率的度量for（j=1，j〈=i；j++）w=w*j；for

（i=1，i〈=n；i++）{w=1；f=f+w；}return；}【例】

計算f=1！+2！+3！+…+n！，用C語言描述。void

factorsum（n）int

n；{int

i，j；int

f，w；f=0；

整個算法所作的乘法操作總數(shù)是：1+2+3+…n=n(n+1)/2。T(n)=O(n2)定理：若T(n)=a

m

n

m

+a

m-1

n

m-1

+…+a1n+a0是一個m次多項式，則T(n)=O(n

m)程序運行時間比較

T（n）=O（f（n））常見函數(shù)的時間復(fù)雜度按數(shù)量遞增排列及增長率：O(1)<O(logn)<O(n)<O(nlogn)<O(n2)<O(n3)<…

O(nk)

<O(2n)T(n)n01000200030005

1020252nn3100n5n2logn21001