數(shù)據(jù)結構課件1

課程性質

?數(shù)據(jù)結構是計算機專業(yè)的專業(yè)基礎課

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

?在教學計劃中的地位：核心、承上啟下

前導課：高等數(shù)學、離散數(shù)學、程序設計語言

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

?屬于武術中的“練功”科目

“練武不練功，到頭一場空”

?考研

學習目標

/掌握基本的數(shù)據(jù)結構

工具箱一復用、修改、重組

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

算法——程序的靈魂

問題求解過程：問題-想法-算法一程序

程序設計研究的層次：算法一方法學一語言一工具

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

評價算法、改進算法

學習要求

?循序漸進，切忌心浮氣躁

提高課外學習的時間和內容

理解科學而不是背誦科學一讀書

正確對待考試

?作習題

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

?作實驗

計算機學科是一門科學性與工程性并重的學科,

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

成績組成

?平時成績

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

?實驗成績

10%：出勤+程序+報告

?期末考試成績

70%：接近同類學校考研水平

?課程設計

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

第1章緒論

本章的基本內容是：

?數(shù)據(jù)結構的興起和發(fā)展

?數(shù)據(jù)結構的研究對象

?數(shù)據(jù)結構的基本概念

?算法及算法分析

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

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

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

28歲任副教授。30歲時，加盟斯坦

福大學計算機系，任教授。從31歲

起，開始出版他的歷史性經典巨著：

TheArtofComputerProgramming

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

已震驚世界，使他獲得計算機科學

界的最高榮譽圖靈獎，此時，他年

DonaldEEiuith(僅36歲。

1.1數(shù)據(jù)結構的興起和發(fā)展

@程序設計的實質是什么？

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

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

數(shù)據(jù)結構問題起源于程序設計

L1數(shù)據(jù)結構的興起和發(fā)展

＞數(shù)據(jù)結構隨著程序設計的發(fā)展而發(fā)展

1.無結構階段

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

3.面向對象階段：（數(shù)據(jù)結構+算法）=程序

＞數(shù)據(jù)結構的發(fā)展并未終結

1.2數(shù)據(jù)結構的研究對象

?計算機求解問題：

問題一抽象出問題的模型—求模型的解

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

數(shù)值問題一數(shù)學方程

非數(shù)值問題一數(shù)據(jù)結構

1.2數(shù)據(jù)結構的研究對象

例1學籍管理問題——表結構

?完成什么功能?各表項之間是什么關系?

學號姓名性另1」出生日期政治面貌

0001王軍男1983/09/02團員

0002李明男1982/12/25黨員

0003湯曉影女1984/03/26團員

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

L2數(shù)據(jù)結構的研究對象

例2人機對弈問題——樹結構

?如何實現(xiàn)對弈?各格局之間是什么關系?

1.2數(shù)據(jù)結構的研究對象

例3教學計劃編排問題——圖結構

⑦如何表示課程之間的先修關系？

編號課程名稱先修課

G高等數(shù)學無

計算機導論無

c2

離散數(shù)學

c3G

程序設計

c4

數(shù)據(jù)結構CC

c53,4

計算機原理CC

C62,4

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

C7C49C5,C6

數(shù)據(jù)結構是研究非數(shù)值問題中計

算機的操作對象以及它們之間的關系

和操作的學科。

1.3數(shù)據(jù)結構的基本概念

數(shù)據(jù)結構的基本概念

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

別和處理的符號集合。

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

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

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

作為一個整體進行考慮和處理。

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

1.3數(shù)據(jù)結構的基本概念

數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項之間的關系

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

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

/數(shù)據(jù)元素是討論數(shù)據(jù)結構時涉及的最小數(shù)

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

1.3數(shù)據(jù)結構的基本概念

數(shù)據(jù)結構的基本概念

數(shù)據(jù)結構：相互之間存在一定關系的數(shù)據(jù)元素的集合。

按照視點的不同，數(shù)據(jù)結構分為邏輯結構和存儲結構。

A邏輯結構：指數(shù)據(jù)元素之間邏輯關系的整體。

1

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

⑦學籍管理問題中，表項之間的邏輯關系指的是什么？

您人機對弈問題中，格局之間的邏輯關系指的是什么？

⑦教學計劃編排問題中，課程之間的邏輯關系指的是什么？

—

數(shù)據(jù)的邏輯結構是從具體問題抽象出來的數(shù)據(jù)模型

1.3數(shù)據(jù)結構的基本概念

數(shù)據(jù)結構的基本概念

數(shù)據(jù)結構：相互之間存在一定關系的數(shù)據(jù)元素的集合。

按照視點的不同，數(shù)據(jù)結構分為邏輯結構和存儲結構。

A邏輯結構：指數(shù)據(jù)元素之間邏輯關系的整體。

?存儲結構：又稱為物理結構，是數(shù)據(jù)及其邏輯結構在

計算機中的表示。

存儲結構實質上是內存分配，

在具體實現(xiàn)時，依賴于計算機語言。

1.3數(shù)據(jù)結構的基本概念

；「；，、，「卞一

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

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

“屬于同一個集合"；<

L3數(shù)據(jù)結構的基本概念

小卞一

數(shù)據(jù)結構從邏輯上分為四類：

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

“屬于同一個集合”；

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

存在著一對一的線性關系；

1.3數(shù)據(jù)結構的基本概念

數(shù)據(jù)結構的基本概念

數(shù)據(jù)結構從邏輯上分為四類:

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

“屬于同一個集合”

⑵線性結構：數(shù)據(jù)元素之間

存在著一對一的線性關系；

⑶樹結構：數(shù)據(jù)元素之間存在

著一對多的層次關系；

L3數(shù)據(jù)結構的基本概念

數(shù)據(jù)結構從邏輯上分為四類：

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

“屬于同一個集合”；

⑵線性結構：數(shù)據(jù)元素之間

存在著一對一的線性關系；

⑶樹結構：數(shù)據(jù)元素之間存在J

著一對多的層次關系；/

⑷圖結構：數(shù)據(jù)元素之間存在1

著多對多的任意關系。匕二

1.3數(shù)據(jù)結構的基本概念

]

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

通常有兩種存儲結構：

1.順序存儲結構：用一組連續(xù)起始地址…

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

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

素的存儲位置來表示。__

eat

1.3數(shù)據(jù)結構的基本概念

數(shù)據(jù)結構的基本概念

例：(bat,cat,eat)

通常有兩種存儲結構：

1.順序存儲結構：用一組連續(xù)0200|cat|q

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

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

素的存儲位置來表示。產葉

2.鏈接存儲結構：用一組任意0W)—M

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

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

來表示。

eat

7V

1.3數(shù)據(jù)結構的基本概念

邏輯結構和存儲結構之間的關系

>數(shù)據(jù)的邏輯結構屬于用戶視圖，是面向問題的,

反映了數(shù)據(jù)內部的構成方式；數(shù)據(jù)的存儲結構

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

>一種數(shù)據(jù)的邏輯結構可以用多種存儲結構來存

儲，而采用不同的存儲結構，其數(shù)據(jù)處理的效

率往往是不同的。

1.3數(shù)據(jù)結構的基本概念

數(shù)據(jù)結構的訪問接口

?對數(shù)據(jù)結構的訪問是指對數(shù)據(jù)的讀取、修改、

加工、處理等操作。

?數(shù)據(jù)結構的基本操作:各種應用都能通過這些

操作實現(xiàn)對數(shù)據(jù)結構的各種訪問。

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

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

表、返回類型等）。

?數(shù)據(jù)結構的訪問接口:數(shù)據(jù)結構基本操作接口

的全體。

1.3數(shù)據(jù)結構的基本概念

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

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

于這個值集上的一組操作的總稱。

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

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

本質的細節(jié)。

例如：地圖、駕駛汽車

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

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

1.3數(shù)據(jù)結構的基本概念

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

ADT的不同視圖

ADT數(shù)據(jù)結構類

■邏輯結構?存儲結構?成員變量

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

⑶使用視圖(b)設計視圖(C)實現(xiàn)視圖

ADT的定義ADT的設計ADT的實現(xiàn)

1.3數(shù)據(jù)結構的基本概念

ADT的定義形式

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

Data

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

Operation

操作1

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

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

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

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

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

操作2

操作n

endADT

1.3數(shù)據(jù)結構的基本概念（小結）

非數(shù)值問題

r集合

線性結構

數(shù)據(jù)的邏輯結構

數(shù)r

樹結構

據(jù)

L圖結構

表

示順序存儲

'數(shù)據(jù)的存儲結構

鏈式存儲

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

1.4算法及算法分析

算法的相關概念

1.算法(Algorithm):是對特定問題求解步驟的

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

2.算法的五大特性：

⑴輸入:一個算法有零個或多個輸入。

⑵輸出:一個算法有一個或多個輸出。

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

每一步都在有窮時間內完成。

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

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

⑸可行性:算法描述的操作可以通過已經實現(xiàn)的基本操作

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

1.4算法及算法分析

例：歐幾里德算法一輾轉相除法

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

mI|y

;］歐幾里德算法］—。

n

1.4算法及算法分析

算法的描述方法——自然語言

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

缺點：冗長、二義性

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

注意事項：避免寫成自然段

1.4算法及算法分析

例：歐幾里德算法

①輸入和口；

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

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

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

④將〃的值放在陽中，將r的值放

在〃中；

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

1.4算法及算法分析___________

算工的國道萬法一一=

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

缺點：缺少嚴密性、靈活性

使用方法：描述簡單算法

注意事項：注意抽象層次

1.4算法及算法分析

例：歐幾里德算法（開夕臺）

/7

流

r=m%n

程

圖

1.4算法及算法分析___________

算法的描述方法——程序設計語言?

優(yōu)點：能由計算機執(zhí)行

缺點：抽象性差，對語言要求高

使用方法：算法需要驗證

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

1.4算法及算法分析

例：歐幾里德算法

#include<iostream.h>

程intCommonFactor(intm,intn)

序{

設intr=m%n;

while(r!=0)

計(

語m=n;

n=r;

言

r=m%n;

}

returnn;

voidmain()

(

cout?CommonFactor(63,54)?endl;

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

[PlFileEditViewInsertProjectBuildToolsWindowHelp

電晦二!▼口國皆聃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ōu)點：表達能力強，抽象性強，容易理解

使用方法：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ù)來

描述。請同學們自行完成！

L4算法及算法分析

算法分析

度量算法效率的方法：

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

缺點：⑴編寫程序實現(xiàn)算法將花費較多的時間和精力；

⑵所得實驗結果依賴于計算機的軟硬件等環(huán)境因素。

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

1.4算法及算法分析

算法分析

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

計算機資源—時間和空間進行估算。

J時間復雜性(TimeComplexity)

\空間復雜性(SpaceComplexity)

1.4算法及算法分析

算法分析

算法的時間復雜度分析

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

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

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

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

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

x++;

1.4算法及算法分析

算法分析

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

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

正比的操作指令。

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

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

x++;

L4算法及算法分析

算法分析——大。符號

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

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

?:?當問題規(guī)模充分大時在漸近意義下的階

1.4算法及算法分析___________

算法分析——大。符號’

mml

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

陽次多項式，則Z(")=0("耀)o

說明：在計算算法時間復雜度時，可以

忽略所有低次塞和最高次塞的系數(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ù)組中有且僅有一個元素值為k）。

intFind(intA[],intn)

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

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

returni;

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

1.4算法及算法分析

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

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

關，則需要分析最好情況、最壞情況、平均情況。

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

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

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

通常假設等概率分布

本章小結—知識結構圖

緒論

數(shù)據(jù)結構算法