數(shù)據(jù)結(jié)構(gòu)課件1

課程性質(zhì)

?數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)專業(yè)的專業(yè)基礎(chǔ)課

公共基礎(chǔ)課、專業(yè)基礎(chǔ)課、專業(yè)方向課、專業(yè)選修課

?在教學(xué)計(jì)劃中的地位：核心、承上啟下

前導(dǎo)課：高等數(shù)學(xué)、離散數(shù)學(xué)、程序設(shè)計(jì)語(yǔ)言

后續(xù)課：數(shù)據(jù)庫(kù)、操作系統(tǒng)、編譯原理……

?屬于武術(shù)中的“練功”科目

“練武不練功，到頭一場(chǎng)空”

?考研

學(xué)習(xí)目標(biāo)

/掌握基本的數(shù)據(jù)結(jié)構(gòu)

工具箱一復(fù)用、修改、重組

/培養(yǎng)算法設(shè)計(jì)能力、程序設(shè)計(jì)能力

算法——程序的靈魂

問(wèn)題求解過(guò)程：?jiǎn)栴}-想法-算法一程序

程序設(shè)計(jì)研究的層次：算法一方法學(xué)一語(yǔ)言一工具

,培養(yǎng)算法分析能力

評(píng)價(jià)算法、改進(jìn)算法

學(xué)習(xí)要求

?循序漸進(jìn)，切忌心浮氣躁

提高課外學(xué)習(xí)的時(shí)間和內(nèi)容

理解科學(xué)而不是背誦科學(xué)一讀書

正確對(duì)待考試

?作習(xí)題

華羅庚：“學(xué)數(shù)學(xué)不做習(xí)題等于入寶山而空返”

?作實(shí)驗(yàn)

計(jì)算機(jī)學(xué)科是一門科學(xué)性與工程性并重的學(xué)科,

表現(xiàn)為理論和實(shí)踐緊密結(jié)合的特征。

成績(jī)組成

?平時(shí)成績(jī)

20%：出勤+作業(yè)+報(bào)告

?實(shí)驗(yàn)成績(jī)

10%：出勤+程序+報(bào)告

?期末考試成績(jī)

70%：接近同類學(xué)?？佳兴?/p>

?課程設(shè)計(jì)

成績(jī)：優(yōu)、良、中、及、不及

第1章緒論

本章的基本內(nèi)容是：

?數(shù)據(jù)結(jié)構(gòu)的興起和發(fā)展

?數(shù)據(jù)結(jié)構(gòu)的研究對(duì)象

?數(shù)據(jù)結(jié)構(gòu)的基本概念

?算法及算法分析

數(shù)據(jù)結(jié)構(gòu)的創(chuàng)始人——克努思

1938年出生，25歲畢業(yè)于加州理工

學(xué)院數(shù)學(xué)系，博士畢業(yè)后留校任教，

28歲任副教授。30歲時(shí)，加盟斯坦

福大學(xué)計(jì)算機(jī)系，任教授。從31歲

起，開始出版他的歷史性經(jīng)典巨著：

TheArtofComputerProgramming

他計(jì)劃共寫7卷，然而出版三卷之后,

已震驚世界，使他獲得計(jì)算機(jī)科學(xué)

界的最高榮譽(yù)圖靈獎(jiǎng)，此時(shí)，他年

DonaldEEiuith(僅36歲。

1.1數(shù)據(jù)結(jié)構(gòu)的興起和發(fā)展

@程序設(shè)計(jì)的實(shí)質(zhì)是什么？

數(shù)據(jù)表示：將數(shù)據(jù)存儲(chǔ)在計(jì)算機(jī)中

數(shù)據(jù)處理：處理數(shù)據(jù)，求解問(wèn)題

數(shù)據(jù)結(jié)構(gòu)問(wèn)題起源于程序設(shè)計(jì)

L1數(shù)據(jù)結(jié)構(gòu)的興起和發(fā)展

＞數(shù)據(jù)結(jié)構(gòu)隨著程序設(shè)計(jì)的發(fā)展而發(fā)展

1.無(wú)結(jié)構(gòu)階段

2.結(jié)構(gòu)化階段：數(shù)據(jù)結(jié)構(gòu)+算法=程序

3.面向?qū)ο箅A段：（數(shù)據(jù)結(jié)構(gòu)+算法）=程序

＞數(shù)據(jù)結(jié)構(gòu)的發(fā)展并未終結(jié)

1.2數(shù)據(jù)結(jié)構(gòu)的研究對(duì)象

?計(jì)算機(jī)求解問(wèn)題：

問(wèn)題一抽象出問(wèn)題的模型—求模型的解

?問(wèn)題——數(shù)值問(wèn)題、非數(shù)值問(wèn)題

數(shù)值問(wèn)題一數(shù)學(xué)方程

非數(shù)值問(wèn)題一數(shù)據(jù)結(jié)構(gòu)

1.2數(shù)據(jù)結(jié)構(gòu)的研究對(duì)象

例1學(xué)籍管理問(wèn)題——表結(jié)構(gòu)

?完成什么功能?各表項(xiàng)之間是什么關(guān)系?

學(xué)號(hào)姓名性另1」出生日期政治面貌

0001王軍男1983/09/02團(tuán)員

0002李明男1982/12/25黨員

0003湯曉影女1984/03/26團(tuán)員

???????????????

L2數(shù)據(jù)結(jié)構(gòu)的研究對(duì)象

例2人機(jī)對(duì)弈問(wèn)題——樹結(jié)構(gòu)

?如何實(shí)現(xiàn)對(duì)弈?各格局之間是什么關(guān)系?

1.2數(shù)據(jù)結(jié)構(gòu)的研究對(duì)象

例3教學(xué)計(jì)劃編排問(wèn)題——圖結(jié)構(gòu)

⑦如何表示課程之間的先修關(guān)系？

編號(hào)課程名稱先修課

G高等數(shù)學(xué)無(wú)

計(jì)算機(jī)導(dǎo)論無(wú)

c2

離散數(shù)學(xué)

c3G

程序設(shè)計(jì)

c4

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

c53,4

計(jì)算機(jī)原理CC

C62,4

數(shù)據(jù)庫(kù)原理

C7C49C5,C6

數(shù)據(jù)結(jié)構(gòu)是研究非數(shù)值問(wèn)題中計(jì)

算機(jī)的操作對(duì)象以及它們之間的關(guān)系

和操作的學(xué)科。

1.3數(shù)據(jù)結(jié)構(gòu)的基本概念

數(shù)據(jù)結(jié)構(gòu)的基本概念

數(shù)據(jù)：所有能輸入到計(jì)算機(jī)中并能被計(jì)算機(jī)程序識(shí)

別和處理的符號(hào)集合。

數(shù)值數(shù)據(jù)：整數(shù)、實(shí)數(shù)等

非數(shù)值數(shù)據(jù)：圖形、圖象、聲音、文字等

數(shù)據(jù)元素：數(shù)據(jù)的基本單位，在計(jì)算機(jī)程序中通常

作為一個(gè)整體進(jìn)行考慮和處理。

數(shù)據(jù)對(duì)象:具有相同性質(zhì)的數(shù)據(jù)元素的集合。

1.3數(shù)據(jù)結(jié)構(gòu)的基本概念

數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項(xiàng)之間的關(guān)系

，包含關(guān)系：數(shù)據(jù)是由數(shù)據(jù)元素組成，數(shù)據(jù)

元素是由數(shù)據(jù)項(xiàng)組成。

/數(shù)據(jù)元素是討論數(shù)據(jù)結(jié)構(gòu)時(shí)涉及的最小數(shù)

據(jù)單位，其中的數(shù)據(jù)項(xiàng)一般不予考慮。

1.3數(shù)據(jù)結(jié)構(gòu)的基本概念

數(shù)據(jù)結(jié)構(gòu)的基本概念

數(shù)據(jù)結(jié)構(gòu)：相互之間存在一定關(guān)系的數(shù)據(jù)元素的集合。

按照視點(diǎn)的不同，數(shù)據(jù)結(jié)構(gòu)分為邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)。

A邏輯結(jié)構(gòu)：指數(shù)據(jù)元素之間邏輯關(guān)系的整體。

1

關(guān)聯(lián)方式或鄰接關(guān)系

⑦學(xué)籍管理問(wèn)題中，表項(xiàng)之間的邏輯關(guān)系指的是什么？

您人機(jī)對(duì)弈問(wèn)題中，格局之間的邏輯關(guān)系指的是什么？

⑦教學(xué)計(jì)劃編排問(wèn)題中，課程之間的邏輯關(guān)系指的是什么？

—

數(shù)據(jù)的邏輯結(jié)構(gòu)是從具體問(wèn)題抽象出來(lái)的數(shù)據(jù)模型

1.3數(shù)據(jù)結(jié)構(gòu)的基本概念

數(shù)據(jù)結(jié)構(gòu)的基本概念

數(shù)據(jù)結(jié)構(gòu)：相互之間存在一定關(guān)系的數(shù)據(jù)元素的集合。

按照視點(diǎn)的不同，數(shù)據(jù)結(jié)構(gòu)分為邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)。

A邏輯結(jié)構(gòu)：指數(shù)據(jù)元素之間邏輯關(guān)系的整體。

?存儲(chǔ)結(jié)構(gòu)：又稱為物理結(jié)構(gòu)，是數(shù)據(jù)及其邏輯結(jié)構(gòu)在

計(jì)算機(jī)中的表示。

存儲(chǔ)結(jié)構(gòu)實(shí)質(zhì)上是內(nèi)存分配，

在具體實(shí)現(xiàn)時(shí)，依賴于計(jì)算機(jī)語(yǔ)言。

1.3數(shù)據(jù)結(jié)構(gòu)的基本概念

；「；，、，「卞一

數(shù)據(jù)結(jié)構(gòu)從邏輯上分為四類：一^

⑴集合：數(shù)據(jù)元素之間就是(?

“屬于同一個(gè)集合"；<

L3數(shù)據(jù)結(jié)構(gòu)的基本概念

小卞一

數(shù)據(jù)結(jié)構(gòu)從邏輯上分為四類：

⑴集合：數(shù)據(jù)元素之間就是

“屬于同一個(gè)集合”；

⑵線性結(jié)構(gòu)：數(shù)據(jù)元素之間e―一—ee

存在著一對(duì)一的線性關(guān)系；

1.3數(shù)據(jù)結(jié)構(gòu)的基本概念

數(shù)據(jù)結(jié)構(gòu)的基本概念

數(shù)據(jù)結(jié)構(gòu)從邏輯上分為四類:

⑴集合：數(shù)據(jù)元素之間就是

“屬于同一個(gè)集合”

⑵線性結(jié)構(gòu)：數(shù)據(jù)元素之間

存在著一對(duì)一的線性關(guān)系；

⑶樹結(jié)構(gòu)：數(shù)據(jù)元素之間存在

著一對(duì)多的層次關(guān)系；

L3數(shù)據(jù)結(jié)構(gòu)的基本概念

數(shù)據(jù)結(jié)構(gòu)從邏輯上分為四類：

⑴集合：數(shù)據(jù)元素之間就是

“屬于同一個(gè)集合”；

⑵線性結(jié)構(gòu)：數(shù)據(jù)元素之間

存在著一對(duì)一的線性關(guān)系；

⑶樹結(jié)構(gòu)：數(shù)據(jù)元素之間存在J

著一對(duì)多的層次關(guān)系；/

⑷圖結(jié)構(gòu)：數(shù)據(jù)元素之間存在1

著多對(duì)多的任意關(guān)系。匕二

1.3數(shù)據(jù)結(jié)構(gòu)的基本概念

]

數(shù)據(jù)結(jié)構(gòu)的基本概念例：(bat,cat,eat)

通常有兩種存儲(chǔ)結(jié)構(gòu)：

1.順序存儲(chǔ)結(jié)構(gòu)：用一組連續(xù)起始地址…

的存儲(chǔ)單元依次存儲(chǔ)數(shù)據(jù)元素，>bat

數(shù)據(jù)元素之間的邏輯關(guān)系由元---

素的存儲(chǔ)位置來(lái)表示。__

eat

1.3數(shù)據(jù)結(jié)構(gòu)的基本概念

數(shù)據(jù)結(jié)構(gòu)的基本概念

例：(bat,cat,eat)

通常有兩種存儲(chǔ)結(jié)構(gòu)：

1.順序存儲(chǔ)結(jié)構(gòu)：用一組連續(xù)0200|cat|q

的存儲(chǔ)單元依次存儲(chǔ)數(shù)據(jù)元素，r0325~-

數(shù)據(jù)元素之間的邏輯關(guān)系由元—

素的存儲(chǔ)位置來(lái)表示。產(chǎn)葉

2.鏈接存儲(chǔ)結(jié)構(gòu)：用一組任意0W)—M

的存儲(chǔ)單元存儲(chǔ)數(shù)據(jù)元素，數(shù)------

據(jù)元素之間的邏輯關(guān)系用指針------

來(lái)表示。

eat

7V

1.3數(shù)據(jù)結(jié)構(gòu)的基本概念

邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)之間的關(guān)系

>數(shù)據(jù)的邏輯結(jié)構(gòu)屬于用戶視圖，是面向問(wèn)題的,

反映了數(shù)據(jù)內(nèi)部的構(gòu)成方式；數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)

屬于具體實(shí)現(xiàn)的視圖，是面向計(jì)算機(jī)的。

>一種數(shù)據(jù)的邏輯結(jié)構(gòu)可以用多種存儲(chǔ)結(jié)構(gòu)來(lái)存

儲(chǔ)，而采用不同的存儲(chǔ)結(jié)構(gòu)，其數(shù)據(jù)處理的效

率往往是不同的。

1.3數(shù)據(jù)結(jié)構(gòu)的基本概念

數(shù)據(jù)結(jié)構(gòu)的訪問(wèn)接口

?對(duì)數(shù)據(jù)結(jié)構(gòu)的訪問(wèn)是指對(duì)數(shù)據(jù)的讀取、修改、

加工、處理等操作。

?數(shù)據(jù)結(jié)構(gòu)的基本操作:各種應(yīng)用都能通過(guò)這些

操作實(shí)現(xiàn)對(duì)數(shù)據(jù)結(jié)構(gòu)的各種訪問(wèn)。

基本操作的特性：抽象性、基本性、完備性、一般性

?訪問(wèn)接口:操作的調(diào)用形式與規(guī)范（例如形參

表、返回類型等）。

?數(shù)據(jù)結(jié)構(gòu)的訪問(wèn)接口:數(shù)據(jù)結(jié)構(gòu)基本操作接口

的全體。

1.3數(shù)據(jù)結(jié)構(gòu)的基本概念

抽象數(shù)據(jù)類型

1.數(shù)據(jù)類型(DataType)：一組值的集合以及定義

于這個(gè)值集上的一組操作的總稱。

例如：C++中的整型變量

2.抽象(Abstract):抽出問(wèn)題本質(zhì)的特征而忽略非

本質(zhì)的細(xì)節(jié)。

例如：地圖、駕駛汽車

3.抽象數(shù)據(jù)類型(AbstractDataType,ADT):一個(gè)

數(shù)據(jù)結(jié)構(gòu)以及定義在該結(jié)構(gòu)上的一組操作的總稱。

1.3數(shù)據(jù)結(jié)構(gòu)的基本概念

ADT是對(duì)數(shù)據(jù)類型的進(jìn)一步抽象

ADT的不同視圖

ADT數(shù)據(jù)結(jié)構(gòu)類

■邏輯結(jié)構(gòu)?存儲(chǔ)結(jié)構(gòu)?成員變量

?操作集合>?算法設(shè)計(jì)?成員函數(shù)

⑶使用視圖(b)設(shè)計(jì)視圖(C)實(shí)現(xiàn)視圖

ADT的定義ADT的設(shè)計(jì)ADT的實(shí)現(xiàn)

1.3數(shù)據(jù)結(jié)構(gòu)的基本概念

ADT的定義形式

ADT抽象數(shù)據(jù)類型名

Data

數(shù)據(jù)元素之間邏輯關(guān)系的定義

Operation

操作1

前置條件:執(zhí)行此操作前數(shù)據(jù)所必須的狀態(tài)

輸入:執(zhí)行此操作所需要的輸入

功能:該操作將完成的功能

輸出:執(zhí)行該操作后產(chǎn)生的輸出

后置條件:執(zhí)行該操作后數(shù)據(jù)的狀態(tài)

操作2

操作n

endADT

1.3數(shù)據(jù)結(jié)構(gòu)的基本概念（小結(jié)）

非數(shù)值問(wèn)題

r集合

線性結(jié)構(gòu)

數(shù)據(jù)的邏輯結(jié)構(gòu)

數(shù)r

樹結(jié)構(gòu)

據(jù)

L圖結(jié)構(gòu)

表

示順序存儲(chǔ)

'數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)

鏈?zhǔn)酱鎯?chǔ)

數(shù)據(jù)的操作：插入、刪除、修改、檢索、排序等

1.4算法及算法分析

算法的相關(guān)概念

1.算法(Algorithm):是對(duì)特定問(wèn)題求解步驟的

一種描述，是指令的有限序列。

2.算法的五大特性：

⑴輸入:一個(gè)算法有零個(gè)或多個(gè)輸入。

⑵輸出:一個(gè)算法有一個(gè)或多個(gè)輸出。

⑶有窮性:一個(gè)算法必須總是在執(zhí)行有窮步之后結(jié)束，且

每一步都在有窮時(shí)間內(nèi)完成。

⑷確定性:算法中的每一條指令必須有確切的含義，對(duì)于

相同的輸入只能得到相同的輸出。

⑸可行性:算法描述的操作可以通過(guò)已經(jīng)實(shí)現(xiàn)的基本操作

執(zhí)行有限次來(lái)實(shí)現(xiàn)。

1.4算法及算法分析

例：歐幾里德算法一輾轉(zhuǎn)相除法

求兩個(gè)自然數(shù)股和〃的最大公約數(shù)

mI|y

;］歐幾里德算法］—。

n

1.4算法及算法分析

算法的描述方法——自然語(yǔ)言

優(yōu)點(diǎn)：容易理解

缺點(diǎn)：冗長(zhǎng)、二義性

使用方法：粗線條描述算法思想

注意事項(xiàng)：避免寫成自然段

1.4算法及算法分析

例：歐幾里德算法

①輸入和口；

②求m除以〃的余數(shù)r；

③若r等于0,貝胡為最大公約數(shù)，

算法結(jié)束；否則執(zhí)行第④步；

④將〃的值放在陽(yáng)中，將r的值放

在〃中；

⑤重新執(zhí)行第②步。

1.4算法及算法分析___________

算工的國(guó)道萬(wàn)法一一=

優(yōu)點(diǎn)：流程直觀

缺點(diǎn)：缺少嚴(yán)密性、靈活性

使用方法：描述簡(jiǎn)單算法

注意事項(xiàng)：注意抽象層次

1.4算法及算法分析

例：歐幾里德算法（開夕臺(tái)）

/7

流

r=m%n

程

圖

1.4算法及算法分析___________

算法的描述方法——程序設(shè)計(jì)語(yǔ)言?

優(yōu)點(diǎn)：能由計(jì)算機(jī)執(zhí)行

缺點(diǎn)：抽象性差，對(duì)語(yǔ)言要求高

使用方法：算法需要驗(yàn)證

注意事項(xiàng)：將算法寫成子函數(shù)

1.4算法及算法分析

例：歐幾里德算法

#include<iostream.h>

程intCommonFactor(intm,intn)

序{

設(shè)intr=m%n;

while(r!=0)

計(jì)(

語(yǔ)m=n;

n=r;

言

r=m%n;

}

returnn;

voidmain()

(

cout?CommonFactor(63,54)?endl;

>大公妁數(shù)~licroaoftVxsuolC-H--[最大公為數(shù).cppl

[PlFileEditViewInsertProjectBuildToolsWindowHelp

電晦二!▼口國(guó)皆聃iconstant

!(Globals)(Allglobalmembers二J

?include<iostream.h>

intConnonFactor(intm,intn)

+厚最大公約數(shù)classe

{intr=m%n;

while(r?=0)

<n=n;

n=r;

r=n%n;}

returnn;}

uoidmain()

<cout?ConnonFactor(63,54)?endl;

c、*D:\DocuBentsandSettings\Adainistra

G

Pressanykeytocontinue

L4算法及算法分析

算法的描述方法——偽代碼

偽代碼(Pseudocode)：介于自然語(yǔ)言和

程序設(shè)計(jì)語(yǔ)言之間的方法，它采用某一程序

設(shè)計(jì)語(yǔ)言的基本語(yǔ)法，操作指令可以結(jié)合自

然語(yǔ)言來(lái)設(shè)計(jì)。

優(yōu)點(diǎn)：表達(dá)能力強(qiáng)，抽象性強(qiáng)，容易理解

使用方法：7±2

1.4算法及算法分析

例：歐幾里德算法

1.r=m%n;

偽2.循環(huán)直到r等于0

代2.1m=n;

石馬2.2n=r;

2.3r=m%n;

3.輸出n;

上述偽代碼再具體一些，用C++的函數(shù)來(lái)

描述。請(qǐng)同學(xué)們自行完成！

L4算法及算法分析

算法分析

度量算法效率的方法：

A事后統(tǒng)計(jì)：將算法實(shí)現(xiàn)，測(cè)算其時(shí)間和空間開銷。

缺點(diǎn)：⑴編寫程序?qū)崿F(xiàn)算法將花費(fèi)較多的時(shí)間和精力；

⑵所得實(shí)驗(yàn)結(jié)果依賴于計(jì)算機(jī)的軟硬件等環(huán)境因素。

A事前分析：對(duì)算法所消耗資源的一種估算方法。

1.4算法及算法分析

算法分析

算法分析(AlgorithmAnalysis)：對(duì)算法所需要的

計(jì)算機(jī)資源—時(shí)間和空間進(jìn)行估算。

J時(shí)間復(fù)雜性(TimeComplexity)

\空間復(fù)雜性(SpaceComplexity)

1.4算法及算法分析

算法分析

算法的時(shí)間復(fù)雜度分析

算法的執(zhí)行時(shí)間=每條語(yǔ)句執(zhí)行時(shí)間之和

每條語(yǔ)句執(zhí)行次數(shù)之和單位時(shí)間

基本語(yǔ)句的執(zhí)行次數(shù)執(zhí)行次數(shù)＞＜執(zhí)行一次的時(shí)間

for(i=l;i<=n;i++)指令系統(tǒng)、編譯的代碼質(zhì)量

forO=l;j<=n;j++)

x++;

1.4算法及算法分析

算法分析

問(wèn)題規(guī)模：輸入量的多少。

基本語(yǔ)句：是執(zhí)行次數(shù)與整個(gè)算法的執(zhí)行次數(shù)成

正比的操作指令。

嗎日;5;1++)問(wèn)題規(guī)?！?/p>

for(j=l;j<=n;j++)基本語(yǔ)句：*

x++;

L4算法及算法分析

算法分析——大。符號(hào)

定義若存在兩個(gè)正的常數(shù)C和〃0，對(duì)于任意打三羯,

都有T(")WcX/("),則稱7(〃)=。3("))

?:?當(dāng)問(wèn)題規(guī)模充分大時(shí)在漸近意義下的階

1.4算法及算法分析___________

算法分析——大。符號(hào)’

mml

定理：^A(n)=amn+am_in+...+axn+a^是一個(gè)

陽(yáng)次多項(xiàng)式，則Z(")=0("耀)o

說(shuō)明：在計(jì)算算法時(shí)間復(fù)雜度時(shí)，可以

忽略所有低次塞和最高次塞的系數(shù)。

1.4算法及算法分析

算法分析

例1?5++x;

例1-6for(i=l;i<=n;++i)

++x;

例1-7for(i=l;i<=n;++i)

for(j=l;j<=n;++j)

++x;

例1-8for(i=l;i<=n;++i)

for(j=l;j<=i-l;++j)

++x;

1.4算法及算法分析

算法分析

例1-9for(i=l;i<=n;++i)

for0=1;j<=n;++j)

(

c[i]U]=0;

for(k=l;k<=n;++k)

c[i][j]+=a[i][k]*b[k][j];

}

例1-10for(i=l;i<=n;i=2*i)

++x;

23

0(1)<O(log2n)<O(n)<O(nlog2n)<O(n)<O(n)

<...<O(2n)<O(nl)

1.4算法及算法分析

最好情況、最壞情況、平均情況

例：在一維整型數(shù)組A[n]中順序查找與給定值k相等

的元素（假設(shè)該數(shù)組中有且僅有一個(gè)元素值為k）。

intFind(intA[],intn)

for(i=0;i<n;i++)

if(A[i]==k)break;

returni;

@基本據(jù)句的執(zhí)行次數(shù)是否只和問(wèn)題規(guī)模有關(guān)?

1.4算法及算法分析

最好情況、最壞情況、平均情況

結(jié)論：如果問(wèn)題規(guī)模相同，時(shí)間代價(jià)與輸入數(shù)據(jù)有

關(guān)，則需要分析最好情況、最壞情況、平均情況。

/最好情況：出現(xiàn)概率較大時(shí)分析

/最差情況：實(shí)時(shí)系統(tǒng)

/平均情況：已知輸入數(shù)據(jù)是如何分布的，

通常假設(shè)等概率分布

本章小結(jié)—知識(shí)結(jié)構(gòu)圖

緒論

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