1算法與數據結構包仲賢409872449@蘭州理工大學計算機與通信學院2教材與參考書1.算法與數據結構，張永等2.數據結構,嚴蔚敏,吳偉民3.數據結構與算法分析（Java版）,APracticalIntroductiontoDataStructuresandAlgorithmAnalysisJavaEditionCliffordA.Shaffer,張銘,劉曉丹譯

電子工業出版社

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

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

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

/*依次放入其后的數字*/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])

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

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

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

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

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

線性結構：線性表、棧、隊列

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

算法和算法分析

1.4抽象數據類型的表示與定義

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

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

283、算法設計的要求評價一個好的算法有以下幾個標準:(1)正確性(Correctness)(2)可讀性(Readability)(3)健狀性(Robustness)(4)效率與存儲量需求⑴所設計的程序沒有語法錯誤；⑵所設計的程序對于幾組輸入數據能夠得出滿足要求的結果；⑶所設計的程序對于精心選擇的典型、苛刻而帶有刁難性的幾組輸入數據能夠得到滿足要求的結果；⑷程序對于一切合法的輸入數據都能產生滿足要求的結果。

max:=0；

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

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

if(x>max)

max=x;

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

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

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

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

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

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

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

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

1.4抽象數據類型的表示與定義

461、數據類型數據類型

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

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

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假定數據部分的矩形r是類型名為Rectangle的一個結構對象，該類型的具體定義如下：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