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

1算法與數(shù)據(jù)結(jié)構(gòu)包仲賢409872449@蘭州理工大學(xué)計(jì)算機(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)實(shí)問題的計(jì)算機(jī)化----表示問題2．現(xiàn)實(shí)問題的處理過程-----程序化問題5例：魔方求解問題一個(gè)魔方（magicsquare）就是一個(gè)由1到n2的整數(shù)構(gòu)成的n×n的矩陣，其中每行、每列以及兩條對(duì)角線上的數(shù)字之和都相等。6求解過程當(dāng)n為奇數(shù)時(shí)，Coxeter給出了產(chǎn)生魔方的具體過程：1）.把1放入第一行最中間的方格中；2）.向左上方移動(dòng)，并按照數(shù)字的遞增順序，把數(shù)字填入空方格；3）.如果移出了魔方，即超越了魔方邊界，則進(jìn)入魔方對(duì)邊的對(duì)應(yīng)方格中；4）.如果一個(gè)方格已被填入數(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):是對(duì)信息的一種符號(hào)表示。在計(jì)算機(jī)科學(xué)中是指所有能輸入到計(jì)算機(jī)中并被計(jì)算機(jī)程序處理的符號(hào)的總稱。是計(jì)算機(jī)操作的對(duì)象的總稱。是信息的載體。14數(shù)據(jù)元素(DataElement):是數(shù)據(jù)（集合）中的一個(gè)“個(gè)體”,是組成數(shù)據(jù)的基本單位,在計(jì)算機(jī)程序中通常作為一個(gè)整體進(jìn)行考慮和處理。是數(shù)據(jù)結(jié)構(gòu)中討論的基本單位15

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

例2、英文字符類型的數(shù)據(jù)對(duì)象。數(shù)據(jù)對(duì)象可以是有限的，也可以是無限的。17學(xué)生信息可包括學(xué)生的學(xué)號(hào)、姓名、性別、年齡等數(shù)據(jù)。這些數(shù)據(jù)構(gòu)成學(xué)生情況的描述的數(shù)據(jù)項(xiàng)；包括學(xué)號(hào)、姓名、性別、年齡等數(shù)據(jù)項(xiàng)的一組數(shù)據(jù)就構(gòu)成學(xué)生信息的一個(gè)數(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ì)算機(jī)存儲(chǔ)器內(nèi)的表示，稱為數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)（StorageStructure）3）數(shù)據(jù)的運(yùn)算，即對(duì)數(shù)據(jù)施加的操作1.數(shù)據(jù)的運(yùn)算定義在數(shù)據(jù)的邏輯結(jié)構(gòu)上，每種邏輯結(jié)構(gòu)都有一個(gè)運(yùn)算的集合。2.最常用的檢索、插入、刪除、更新、排序等運(yùn)算實(shí)際上只是在抽象的數(shù)據(jù)上所施加的一系列抽象的操作。21四、數(shù)據(jù)結(jié)構(gòu)的分類1.從邏輯結(jié)構(gòu)角度分

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

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

算法和算法分析

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

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

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

283、算法設(shè)計(jì)的要求評(píng)價(jià)一個(gè)好的算法有以下幾個(gè)標(biāo)準(zhǔn):(1)正確性(Correctness)(2)可讀性(Readability)(3)健狀性(Robustness)(4)效率與存儲(chǔ)量需求⑴所設(shè)計(jì)的程序沒有語法錯(cuò)誤；⑵所設(shè)計(jì)的程序?qū)τ趲捉M輸入數(shù)據(jù)能夠得出滿足要求的結(jié)果；⑶所設(shè)計(jì)的程序?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è)計(jì)實(shí)現(xiàn)算法的過程步驟301．算法、語言、程序的關(guān)系1）算法：描述了數(shù)據(jù)對(duì)象的元素之間的關(guān)系（包括數(shù)據(jù)邏輯關(guān)系、存貯關(guān)系描述）2）描述算法的工具：（自然語言、框圖或類C語言）3）程序是算法在計(jì)算機(jī)中的實(shí)現(xiàn)（與所用計(jì)算機(jī)及所用語言有關(guān)）312、設(shè)計(jì)實(shí)現(xiàn)算法過程步驟1）找出與求解有關(guān)的數(shù)據(jù)元素之間的關(guān)系（建立結(jié)構(gòu)關(guān)系）；2）確定在某一數(shù)據(jù)對(duì)象上所施加運(yùn)算；3）考慮數(shù)據(jù)元素的存儲(chǔ)表示；4）選擇描述算法的語言；5）設(shè)計(jì)實(shí)現(xiàn)求解的算法，并用程序語言加以描述。32三、算法分析1．性能評(píng)價(jià)對(duì)問題規(guī)模n與該算法在運(yùn)行時(shí)所占的空間S與所耗費(fèi)的時(shí)間T給出一個(gè)數(shù)量關(guān)系的評(píng)價(jià)。332．時(shí)間與空間數(shù)量關(guān)系計(jì)算數(shù)量關(guān)系評(píng)價(jià)體現(xiàn)在時(shí)間——算法編程后在機(jī)器中所耗費(fèi)時(shí)間。數(shù)量關(guān)系評(píng)價(jià)體現(xiàn)在空間——算法編程后在機(jī)器中所占存儲(chǔ)量。341）關(guān)于算法執(zhí)行時(shí)間事先分析和事后測(cè)試事先分析

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

收集此算法的執(zhí)行時(shí)間和實(shí)際占用空間的統(tǒng)計(jì)資料。35語句頻度：是指該語句一個(gè)算法中重復(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）算法的時(shí)間復(fù)雜度:算法的時(shí)間度量記作T(n)=O(f(n))稱作算法的漸近時(shí)間復(fù)雜度，簡稱時(shí)間復(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

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

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

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

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

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

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

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

是一個(gè)值的集合和定義在此集合上的一組操作的總稱。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ù)對(duì)象：<數(shù)據(jù)對(duì)象的定義>數(shù)據(jù)關(guān)系：<數(shù)據(jù)關(guān)系的定義>基本操作：<基本操作的定義>}ADT抽象數(shù)據(jù)類型名假定把矩形定義為一種抽象數(shù)據(jù)類型，其數(shù)據(jù)部分包括矩形的長度和寬度，操作部分包括初始化矩形的尺寸、求矩形的周長和求矩形的面積。

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

ADT

RECtangle

is

Data:

一個(gè)矩形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的一個(gè)結(jié)構(gòu)對(duì)象，該類型的具體定義如下：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