算法數(shù)據(jù)結(jié)構(gòu)

1算法與數(shù)據(jù)結(jié)構(gòu)包仲賢409872449@蘭州理工大學(xué)計算機(jī)與通信學(xué)院2教材與參考書1.算法與數(shù)據(jù)結(jié)構(gòu)，張永等2.數(shù)據(jù)結(jié)構(gòu),嚴(yán)蔚敏,吳偉民3.數(shù)據(jù)結(jié)構(gòu)與算法分析（Java版）,APracticalIntroductiontoDataStructuresandAlgorithmAnalysisJavaEditionCliffordA.Shaffer,張銘,劉曉丹譯

電子工業(yè)出版社

2001年1月31.1問題求解分析1.2基本概念和術(shù)語1.3算法和算法分析

1.4抽象數(shù)據(jù)類型的表示與定義41．現(xiàn)實問題的計算機(jī)化----表示問題2．現(xiàn)實問題的處理過程-----程序化問題5例：魔方求解問題一個魔方（magicsquare）就是一個由1到n2的整數(shù)構(gòu)成的n×n的矩陣，其中每行、每列以及兩條對角線上的數(shù)字之和都相等。6求解過程當(dāng)n為奇數(shù)時，Coxeter給出了產(chǎn)生魔方的具體過程：1）.把1放入第一行最中間的方格中；2）.向左上方移動，并按照數(shù)字的遞增順序，把數(shù)字填入空方格；3）.如果移出了魔方，即超越了魔方邊界，則進(jìn)入魔方對邊的對應(yīng)方格中；4）.如果一個方格已被填入數(shù)字，則向下繼續(xù)填寫方格；5）.依據(jù)上述方法，直到全部填寫完畢。71、數(shù)據(jù)結(jié)構(gòu)形式化結(jié)果為：intsquare[MAX_SIZE][MAX_SIZE];

2、將上述的產(chǎn)生魔方的過程算法化，用簡潔的描述方式描述產(chǎn)生魔方的過程，即就是算法描述81）square[0][(size-1)/2]=1;/*把1放入第一行最中間的方格中*/2）for(count=2;count<=size*size;count++){

/*依次放入其后的數(shù)字*/row=(i-1<0)?(size-1):(i-1);/*i=0;j=(size-1)/2;上方*/column=(j-1<0)?(size-1):(j-1);/*左方*/9if(square[row][column])

/*如果方格已被填入數(shù)字，下方*/i=(++i)%size;else{i=row;j=column；}square[i][j]=count;}10本方法:15812417161475232220136432119121092251811111.1問題求解分析1.2基本概念和術(shù)語1.3算法和算法分析1.4抽象數(shù)據(jù)類型的表示與定義

121.2基本概念和術(shù)語一、基本概念二、結(jié)構(gòu)的定義三、數(shù)據(jù)結(jié)構(gòu)的定義四、數(shù)據(jù)結(jié)構(gòu)的分類13一.基本概念數(shù)據(jù)(Data):是對信息的一種符號表示。在計算機(jī)科學(xué)中是指所有能輸入到計算機(jī)中并被計算機(jī)程序處理的符號的總稱。是計算機(jī)操作的對象的總稱。是信息的載體。14數(shù)據(jù)元素(DataElement):是數(shù)據(jù)（集合）中的一個“個體”,是組成數(shù)據(jù)的基本單位,在計算機(jī)程序中通常作為一個整體進(jìn)行考慮和處理。是數(shù)據(jù)結(jié)構(gòu)中討論的基本單位15

數(shù)據(jù)項：是數(shù)據(jù)結(jié)構(gòu)中討論的最小單位（不可分割）。數(shù)據(jù)元素可以是數(shù)據(jù)項的集合（組成數(shù)據(jù)元素的各個項）16數(shù)據(jù)對象(DataObject)：是性質(zhì)相同的數(shù)據(jù)元素的集合。是數(shù)據(jù)的一個子集。例1、整數(shù)的數(shù)據(jù)對象。

例2、英文字符類型的數(shù)據(jù)對象。數(shù)據(jù)對象可以是有限的，也可以是無限的。17學(xué)生信息可包括學(xué)生的學(xué)號、姓名、性別、年齡等數(shù)據(jù)。這些數(shù)據(jù)構(gòu)成學(xué)生情況的描述的數(shù)據(jù)項；包括學(xué)號、姓名、性別、年齡等數(shù)據(jù)項的一組數(shù)據(jù)就構(gòu)成學(xué)生信息的一個數(shù)據(jù)元素。學(xué)生信息數(shù)據(jù)元素的C語言表示方法是：structStudent{longnumber;charname[10];charsex[3];intage;};18二.結(jié)構(gòu)的定義結(jié)構(gòu)（Structure）:數(shù)據(jù)元素之間的相互關(guān)系。如指數(shù)據(jù)在邏輯上的關(guān)系，稱為邏輯結(jié)構(gòu)。如指數(shù)據(jù)在物理上的關(guān)系，稱為物理結(jié)構(gòu)。19三.數(shù)據(jù)結(jié)構(gòu)的定義數(shù)據(jù)結(jié)構(gòu)(DataStructure)1.

描述性定義：是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。2.形式定義20數(shù)據(jù)結(jié)構(gòu)一般包括以下三方面內(nèi)容：1）數(shù)據(jù)元素之間的邏輯關(guān)系，也稱數(shù)據(jù)的邏輯結(jié)構(gòu)2）數(shù)據(jù)元素及其關(guān)系在計算機(jī)存儲器內(nèi)的表示，稱為數(shù)據(jù)的存儲結(jié)構(gòu)（StorageStructure）3）數(shù)據(jù)的運算，即對數(shù)據(jù)施加的操作1.數(shù)據(jù)的運算定義在數(shù)據(jù)的邏輯結(jié)構(gòu)上，每種邏輯結(jié)構(gòu)都有一個運算的集合。2.最常用的檢索、插入、刪除、更新、排序等運算實際上只是在抽象的數(shù)據(jù)上所施加的一系列抽象的操作。21四、數(shù)據(jù)結(jié)構(gòu)的分類1.從邏輯結(jié)構(gòu)角度分

線性結(jié)構(gòu)：線性表、棧、隊列

非線性結(jié)構(gòu)：樹、圖2.從物理結(jié)構(gòu)角度分存儲結(jié)構(gòu)：物理結(jié)構(gòu)。22邏輯結(jié)構(gòu)線性結(jié)構(gòu)樹結(jié)構(gòu)圖結(jié)構(gòu)23四種不同的存儲結(jié)構(gòu)1、順序存儲結(jié)構(gòu):用數(shù)據(jù)元素在存儲器中的相對位置來表示數(shù)據(jù)元素之間的邏輯關(guān)系。2、鏈?zhǔn)酱鎯Y(jié)構(gòu)：在每一個數(shù)據(jù)元素中增加一個存放地址的指針，用此指針來表示數(shù)據(jù)元素之間的邏輯關(guān)系。243、索引存儲方法該方法通常在存儲結(jié)點信息的同時，還建立附加的索引表。4.散列存儲方法根據(jù)結(jié)點的關(guān)鍵字直接計算出該結(jié)點的存儲地址。251.1問題求解分析1.2基本概念和術(shù)語1.3

算法和算法分析

1.4抽象數(shù)據(jù)類型的表示與定義

261.3算法和算法分析一、算法二、算法的描述三、算法分析27一、算法1、算法：是對特定問題求解步驟的一種描述。算法是指令的有限序列，其中每一條指令表示一個或多個操作。

2、算法具有以下五個特性：（1）有窮性（2）確定性（3）可行性（4）輸入(5)輸出

283、算法設(shè)計的要求評價一個好的算法有以下幾個標(biāo)準(zhǔn):(1)正確性(Correctness)(2)可讀性(Readability)(3)健狀性(Robustness)(4)效率與存儲量需求⑴所設(shè)計的程序沒有語法錯誤；⑵所設(shè)計的程序?qū)τ趲捉M輸入數(shù)據(jù)能夠得出滿足要求的結(jié)果；⑶所設(shè)計的程序?qū)τ诰倪x擇的典型、苛刻而帶有刁難性的幾組輸入數(shù)據(jù)能夠得到滿足要求的結(jié)果；⑷程序?qū)τ谝磺泻戏ǖ妮斎霐?shù)據(jù)都能產(chǎn)生滿足要求的結(jié)果。

max:=0；

for（i=1；i<=n；i++）

{scanf("%f",&x);

if(x>max)

max=x;

}29二、算法的描述1、算法、語言、程序的關(guān)系2、設(shè)計實現(xiàn)算法的過程步驟301．算法、語言、程序的關(guān)系1）算法：描述了數(shù)據(jù)對象的元素之間的關(guān)系（包括數(shù)據(jù)邏輯關(guān)系、存貯關(guān)系描述）2）描述算法的工具：（自然語言、框圖或類C語言）3）程序是算法在計算機(jī)中的實現(xiàn)（與所用計算機(jī)及所用語言有關(guān)）312、設(shè)計實現(xiàn)算法過程步驟1）找出與求解有關(guān)的數(shù)據(jù)元素之間的關(guān)系（建立結(jié)構(gòu)關(guān)系）；2）確定在某一數(shù)據(jù)對象上所施加運算；3）考慮數(shù)據(jù)元素的存儲表示；4）選擇描述算法的語言；5）設(shè)計實現(xiàn)求解的算法，并用程序語言加以描述。32三、算法分析1．性能評價對問題規(guī)模n與該算法在運行時所占的空間S與所耗費的時間T給出一個數(shù)量關(guān)系的評價。332．時間與空間數(shù)量關(guān)系計算數(shù)量關(guān)系評價體現(xiàn)在時間——算法編程后在機(jī)器中所耗費時間。數(shù)量關(guān)系評價體現(xiàn)在空間——算法編程后在機(jī)器中所占存儲量。341）關(guān)于算法執(zhí)行時間事先分析和事后測試事先分析

求出該算法的一個時間界限函數(shù)。事后測試

收集此算法的執(zhí)行時間和實際占用空間的統(tǒng)計資料。35語句頻度：是指該語句一個算法中重復(fù)執(zhí)行的次數(shù)。例１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];}362）算法的時間復(fù)雜度:算法的時間度量記作T(n)=O(f(n))稱作算法的漸近時間復(fù)雜度，簡稱時間復(fù)雜度。37例２、{++x;s=0;}例３、for(i=1;i<=n;++i){++x;s+=x;}例４、for(i=1;i<=n;++i)

for(j=1;j<=n;++j){++x;s+=x;}38例５for(i=2;i<=n;++i)for(j=2;j<=i-1;++j){++x;a[i，j]=x;}39例6：Voidbubble-sort(inta[]，intn)for(i=n-1,change=TURE;i>1&&change;--i){change=false;for(j=0;j<i;++j)if(a[j]>a[j+1]){a[j]←→a[j+1];change=TURE}}

40for(i=0;i<n;i++)for(j=0;j<n;j++){c[i][j]=0;//基本語句1for(k=0;k<n;k++) c[i][j]=c[i][j]+a[i][k]*b[k][j];//基本語句2}41

以下六種計算算法時間的多項式是最常用的。其關(guān)系為：

O(1)<O(logn)<O(n)<O(nlogn)<O(n2)<O(n3)指數(shù)時間的關(guān)系為：

O(2n)<O(n!)<O(nn)42有時為了比較兩個同數(shù)量級算法的優(yōu)劣，須突出主項的常數(shù)因子，而將低次項用大“O”記號表示。例如，設(shè)T1(n)=1.39nlgn+100n+256=1.39nlgn+O(n),T2(n)=2.0nlgn-2n=2.0nlgn+O(n)433）、算法的空間復(fù)雜度空間復(fù)雜度:算法所需存儲空間的度量，記作:

S(n)=O(f(n))

其中n為問題的規(guī)模(或大小)44例以魔方為例來看一下實現(xiàn)魔方算法的評價?？臻g復(fù)雜度上，存貯一個nn的魔方，只需要nn的整數(shù)存貯空間，即O（n2）。時間復(fù)雜度上，操作的主要工作來自于兩個for循環(huán)嵌套，所以時間復(fù)雜度是O（n2）。451.1問題求解分析1.2基本概念和術(shù)語1.3算法和算法分析

1.4抽象數(shù)據(jù)類型的表示與定義

461、數(shù)據(jù)類型數(shù)據(jù)類型

是一個值的集合和定義在此集合上的一組操作的總稱。472.抽象數(shù)據(jù)類型（AbstractDataType簡稱ADT）在數(shù)據(jù)結(jié)構(gòu)中我們常用到抽象數(shù)據(jù)類型。ADT是指抽象數(shù)據(jù)的組織和與之相關(guān)的操作。可以看作是數(shù)據(jù)的邏輯結(jié)構(gòu)及其在邏輯結(jié)構(gòu)上定義的操作。ADT抽象數(shù)據(jù)類型名{數(shù)據(jù)對象：<數(shù)據(jù)對象的定義>數(shù)據(jù)關(guān)系：<數(shù)據(jù)關(guān)系的定義>基本操作：<基本操作的定義>}ADT抽象數(shù)據(jù)類型名假定把矩形定義為一種抽象數(shù)據(jù)類型，其數(shù)據(jù)部分包括矩形的長度和寬度，操作部分包括初始化矩形的尺寸、求矩形的周長和求矩形的面積。

4849假定該抽象數(shù)據(jù)類型名用RECtangle（矩形）表示，定義矩形長度和寬度的數(shù)據(jù)用length和width表示，并假定其類型為浮點（float）型。初始化矩形數(shù)據(jù)的函數(shù)名用InitRectangle表示，求矩形周長的函數(shù)名用Circumference表示求矩形面積的函數(shù)名用Area（面積）表示50矩形的ADT（抽象數(shù)據(jù)類型）描述如下：

ADT

RECtangle

is

Data:

一個矩形r，其長度和寬度分別用length和width表示

Operations:

//初始化矩形r的長度和寬度值為len和wid

void

InitRectangle(Rectangle&

r,

float

len,

float

wid);

//求矩形r的周長并返回

float

Circumference(Rectangle&

r);

//求矩形r的面積并返回

float

Area(Rectangle&

r);

end

RECtangle51假定數(shù)據(jù)部分的矩形r是類型名為Rectangle的一個結(jié)構(gòu)對象，該類型的具體定義如下：structRectangle{floatlength,width;};初始化矩形尺寸

voidInitRectangle(Rectangle&r,floatlen,floatwid){ r.length=len;//把len值賦給r的length域

r.width=wid;//把wid值賦給r的width域

}52初始化矩形尺寸

voidInitRectangle(Rectangle&r,floatlen,floatwid){ r.length=len;//把len值賦給r的length域

r.width=wid;//把wid值賦給r的width域

}53求矩形周長

floatCircumference(Rectangle&r){return2*(r.length+r.width);}求矩形面積

float