資料課件說明教案d

第1章緒論第2

頁第1章緒論

1.1什么是數(shù)據(jù)結構

1.2基本概念和術語

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

1.4算法和算法分析第3

頁1.1什么是數(shù)據(jù)結構處理數(shù)據(jù)的種類數(shù)據(jù)數(shù)值數(shù)據(jù)非數(shù)值數(shù)據(jù)數(shù)值（整數(shù)，實數(shù)）

文本圖象聲音影像數(shù)據(jù)：所有能輸入到計算機中，并能被其存儲、加工、處理的符號的集合。數(shù)據(jù)就是客觀對象的符號表示。

程序數(shù)據(jù)（Data）信息（Information）8,12,22,33,8,12,22第4

頁1.1什么是數(shù)據(jù)結構數(shù)值問題例1：已知游泳池的長len和寬width，求面積area。建立模型

涉及的對象：游泳池的長len，寬width，面積area

對象之間的關系：area=len×width設計求解問題的方法編程 intmain() { intlen,width,area;

scanf(”%d%d”,&len,&width);

area=len*width;

printf(”area=%d\n”,area);

return0;}第5

頁1.1什么是數(shù)據(jù)結構非數(shù)值問題 例2：已知學生選課情況，安排課程考試的日程，要求在盡可能短的時間內完成考試。學生選課情況表姓名選修課1 選修課2選修課3 楊潤生算法分析（A）形式語言（B）計算機網(wǎng)絡（E）

石磊計算機圖形學（C）模式識別（D）

魏慶濤計算機圖形學（C）計算機網(wǎng)絡（E）人工智能（F）

馬耀先模式識別（D）人工智能（F）算法分析（A）

齊硯生形式語言（B）人工智能（F）第6

頁1.1什么是數(shù)據(jù)結構學生選課情況表姓名選修課1 選修課2選修課3 楊潤生算法分析（A）形式語言（B）計算機網(wǎng)絡（E）

石磊計算機圖形學（C）模式識別（D）

魏慶濤計算機圖形學（C）計算機網(wǎng)絡（E）人工智能（F）

馬耀先模式識別（D）人工智能（F）算法分析（A）

齊硯生形式語言（B）人工智能（F）◆建立模型

問題涉及的對象：課程

課程之間的關系：同一學生選修的課程之間有某種“沖突”關系。要求：同一個學生選修的課程不能安排在同一時間內進行考試。

第7

頁1.1什么是數(shù)據(jù)結構學生選課情況表姓名選修課1 選修課2選修課3 楊潤生算法分析（A）形式語言（B）計算機網(wǎng)絡（E）

石磊計算機圖形學（C）模式識別（D）

魏慶濤計算機圖形學（C）計算機網(wǎng)絡（E）人工智能（F）

馬耀先模式識別（D）人工智能（F）算法分析（A）

齊硯生形式語言（B）人工智能（F）DEFCBA頂點：表示課程同一學生選修的課程用一條邊連接有邊連接的課程不能安排在同一時間考試第8

頁DEFCBA1.1什么是數(shù)據(jù)結構設計求解問題的方法 課程考試可用圖的著色法求解問題。 每一種顏色代表一個考試時間，著上相同顏色的頂點是可以安排在同一時間考試的課程； 用盡可能少的顏色為圖的頂點著色，相鄰的頂點著上不同的顏色。ACEFBD如下是一種考試日程：1:算法分析(A)計算機圖形學(C)2:形式語言(B)模式識別人工智能（D)3:計算機網(wǎng)絡(E)4:人工智能(F)第9

頁1.1什么是數(shù)據(jù)結構解題流程：設：G表示課程關系圖，V是圖G中所有尚未著色的頂點集合，NEW表示可以用新顏色著色的頂點集合，Day表示考試的天數(shù)。I.

InputData：II.

ProcessData：III.

OutputInformation：Day初始化：day=1;V={圖中所有頂點的集合}；判斷V是否非空？

yes:初始化NEW為空集合；著色:V中取一點，找出所有與之“不相鄰”的頂點； 將這些頂點加入NEW;

從V中去掉這些頂點。

day=day+1；返回判斷V是否非空。 no:循環(huán)結束第10

頁1.1什么是數(shù)據(jù)結構數(shù)值問題與非數(shù)值問題的比較數(shù)值問題*對象：len,wide,area

——用數(shù)值表示*對象之間的關系：area=lenwide

——用方程或函數(shù)表示*數(shù)據(jù)存儲：可用程序設計語言中的實型變量存儲數(shù)據(jù)*問題求解方法：某種數(shù)值計算方法求解

非數(shù)值問題*對象：課程——用課程名表示*對象之間的關系：課程間有“沖突”關系*數(shù)據(jù)存儲：要保存數(shù)據(jù)及數(shù)據(jù)之間的關系*問題求解方法不能用數(shù)值表示課程之間的這種關系不能用方程或函數(shù)表示第11

頁1.1什么是數(shù)據(jù)結構什么是數(shù)據(jù)結構？

數(shù)據(jù)結構是一門研究非數(shù)值問題中計算機的操作對象以及它們之間的關系和操作的學科。數(shù)據(jù)結構所研究的問題 非數(shù)值數(shù)據(jù)之間的結構關系，及如何表示，如何存儲，如何處理。第12

頁1.1什么是數(shù)據(jù)結構1968年美國D.E.Knuth教授出版：TheArtofComputerProgramming《計算機程序設計技巧》開創(chuàng)了數(shù)據(jù)結構的最初體系。計劃共寫7卷，然而出版三卷之后，已震驚世界，獲得計算機科學界的最高榮譽圖靈獎，年僅36歲。1938年出生，25歲畢業(yè)于加州理工學院數(shù)學系，博士畢業(yè)后留校任教，28歲任副教授。30歲時，加盟斯坦福大學計算機系，任教授。第13

頁1.1什么是數(shù)據(jù)結構數(shù)據(jù)結構隨著程序設計的發(fā)展而發(fā)展無結構階段結構化階段：數(shù)據(jù)結構＋算法＝程序面向對象階段：(數(shù)據(jù)結構＋算法)＝程序

數(shù)據(jù)結構的發(fā)展并未終結研究的范圍不斷擴展，算法不斷更新描述手段、使用語言不斷更新第14

頁1.2基本概念和術語數(shù)據(jù)(data)：客觀對象的符號表示。數(shù)據(jù)元素(dataelement)：數(shù)據(jù)的基本單位，在計算機程序中作為一個整體考慮和處理，通常具有完整確定的實際意義。(節(jié)點、頂點、記錄)數(shù)據(jù)項(dataitem)：數(shù)據(jù)不可分割的最小標識單位。一個數(shù)據(jù)元素可由若干數(shù)據(jù)項組成，通常不具有完整確定的實際意義。(字段)0001劉建國男19491001工程師0002黃紅女19650506助工0003張華女19461118高工……………第15

頁1.2基本概念和術語數(shù)據(jù)結構(datastructure)：相互之間存在一種或多種特定關系的、具有相同特征的數(shù)據(jù)元素的集合。

數(shù)據(jù)結構：帶有結構和操作的數(shù)據(jù)元素集合。

結構：數(shù)據(jù)元素之間的關系；

操作：對數(shù)據(jù)的加工處理。

Data_Structure=(D,S) D:數(shù)據(jù)元素集合；S：D的關系集合第16

頁1.2基本概念和術語數(shù)據(jù)結構討論兩方面問題： 1)數(shù)據(jù)的邏輯結構：從具體問題抽象出來的數(shù)據(jù)模型，反映了事物的組成及事物之間的邏輯關系。 2)數(shù)據(jù)的存儲結構(也稱為物理結構)：解決各種邏輯結構在計算機中的物理存儲和表示。第17

頁1.2基本概念和術語：數(shù)據(jù)的邏輯結構數(shù)據(jù)的邏輯結構：數(shù)據(jù)之間的結構關系，是具體關系的抽象。有四種類型：集合：數(shù)據(jù)元素間除“同屬于一個集合”外，無其它關系線性結構：一個對一個，如線性表/棧/隊列樹形結構：一個對多個，如樹圖狀結構：多個對多個，如圖第18

頁1.2基本概念和術語：數(shù)據(jù)的邏輯結構線性結構 學生基本情況登記表，記錄了每個學生的學號、姓名、專業(yè)、政治面貌。按學生的學號順序排列。

001003002004006005008007學生間學號順序關系是一種線性結構關系線性結構：除第一個元素和最后一個元素外，其他元素都有且僅有一個直接前趨，有且僅有一個直接后繼。學號姓名 專業(yè)政治面貌001 王洪 計算機黨員002孫文計算機團員003 謝軍 計算機團員004 李輝 計算機團員005 沈祥福計算機黨員006 余斌 計算機團員

007 鞏力 計算機團員

008 孔令輝計算機團員第19

頁1.2基本概念和術語：數(shù)據(jù)的邏輯結構樹形結構 假設某家族有10個成員A、B、C、D、E、F、G、H、I、J，他們之間的血緣關系可以用圖表示。JIACBDHGFE樹形結構：每一個元素只有一個直接前趨，有0個或多個直接后繼。第20

頁1.2基本概念和術語：數(shù)據(jù)的邏輯結構圖形結構 工程進度圖。圖形結構：每一個元素可以有0個或多個直接前趨，有0個或多個直接后繼。

V1

V0

V2

V3

V4

V5

V6第21

頁1.2基本概念和術語：數(shù)據(jù)的邏輯結構數(shù)據(jù)邏輯結構的表示方法：圖示表示 圖示表示是由頂點和邊構成的圖，其中頂點表示數(shù)據(jù)，邊表示數(shù)據(jù)之間的結構關系。二元組表示 二元組表示是用一個二元組（D，S）表示數(shù)據(jù)結構，其中D是數(shù)據(jù)元素集合，S是D上關系的集合。第22

頁1.2基本概念和術語：數(shù)據(jù)的邏輯結構例：學生基本情況表的二元組表示（D，S）

001003002004006005008007D={001，002，003，004，005，006，007，008}S={R}R={<001,002>,<002,003>,<003,004>,<004,005>,<005,006>,<006,007>,<007,008>}第23

頁1.2基本概念和術語：數(shù)據(jù)的邏輯結構例：家族樹的二元組表示（D，S）

D={A，B，C，D，E，F(xiàn)，G，H，I，J}S={R}R={<A,B>,<A,C>,<A,D>,<B,E>,<B,F>,<C,G>,<D,H>,<D,I>,<D,J>}JIACBDHGFE第24

頁1.2基本概念和術語：數(shù)據(jù)的存儲結構數(shù)據(jù)的存儲結構 存儲結構在計算機中的表示實質是內存分配。具體實現(xiàn)時要依賴于計算機語言。常見的數(shù)據(jù)存儲結構順序存儲方式鏈式存儲方式索引方式散列方式第25

頁1.2基本概念和術語：數(shù)據(jù)的存儲結構順序存儲結構： 借助元素在存儲器中的相對位置來表示數(shù)據(jù)元素之間的邏輯關系。例如，用一維數(shù)組存儲線性結構。元素n……..元素i……..元素2元素1L0L0+mL0+(i-1)*mL0+（n-1)*m存儲地址存儲內容Loc(元素i)=L0+（i-1)*m第26

頁1.2基本概念和術語：數(shù)據(jù)的存儲結構鏈式存儲結構:借助指示元素存儲地址的指針來表示數(shù)據(jù)元素之間的邏輯關系。例如，用鏈表(指針)存儲線性結構。1536元素21400元素11386元素3∧元素41345P存儲地址存儲內容指針

1345元素1

1400

1386元素4

∧

…….

……..

…….

1400元素2

1536

…….

……..

…….

1536元素3

1386第27

頁1.2基本概念和術語邏輯結構與存儲結構的關系：數(shù)據(jù)的邏輯結構屬于用戶視圖，是面向問題的，反映了數(shù)據(jù)內部的構成方式；數(shù)據(jù)的存儲結構屬于具體實現(xiàn)的視圖，是面向計算機的。一種數(shù)據(jù)的邏輯結構可以用多種存儲結構來存儲；而采用不同的存儲結構，其數(shù)據(jù)處理的效率往往是不同的。算法的設計取決于所選定的邏輯結構，算法的實現(xiàn)則依賴于采用的存儲結構。第28

頁1.3抽象數(shù)據(jù)類型基于高級程序語言的數(shù)據(jù)類型可以用來描述數(shù)據(jù)的存儲結構。數(shù)據(jù)類型：值的集合+相應的一組操作。抽象數(shù)據(jù)類型，簡稱ADT(AbstractDataType)：定義了一組操作的數(shù)學抽象模型。是一種描述用戶與數(shù)據(jù)之間接口的抽象模型。它由三個不可分割的部分組成的三元組：ADT抽象數(shù)據(jù)類型名{ 數(shù)據(jù)對象D：<數(shù)據(jù)對象的定義> 數(shù)據(jù)關系S：<數(shù)據(jù)關系的定義> 數(shù)據(jù)操作P：<基本操作的定義>}第29

頁1.3抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型使用的目的在于隱藏運算實現(xiàn)的細節(jié)和內部數(shù)據(jù)結構。抽象數(shù)據(jù)類型所要包括的操作由設計者根據(jù)需要確定。抽象數(shù)據(jù)類型的定義僅取決于它的一組邏輯特性，而與其在計算機內部如何表示和實現(xiàn)無關，即不論其內部結構如何變化，只要它的數(shù)學特性不變，都不影響其外部的使用。第30

頁1.3抽象數(shù)據(jù)類型ADTList{

數(shù)據(jù)對象：D={a1,a2,...,ai-1,ai,ai+1,…,an}

數(shù)據(jù)關系：R={<a1,a2>,<a2,a3>,…,<an-1,an>}

基本操作：<基本操作的定義>

InitList(&L)

操作結果：構造一個空的線性表L；

DetroyList(&L)

初始條件：線性表已存在 操作結果：銷毀線性表L

ClearList(&L)

初始條件：線性表已存在 操作結果：將L重置為空表

ListEmpty(L)

初始條件：線性表已存在 操作結果：若L為空表返回TRUE，否則返回FALSE…}第31

頁1.4算法與算法分析 算法（algorithm）是為了解決某類問題而規(guī)定的一系列有限長的操作序列。 一個算法必須滿足以下五個重要特性：有窮性、確定性、可行性、輸入和輸出。有窮性：算法必須在有限步內結束；每一步有限完成。確定性：算法的操作清晰無二義性?？尚行裕核惴ǖ牟僮鞅仨毮軌驅崿F(xiàn)。輸入：有0個或多個輸入。輸出：有1個或多個輸出。第32

頁1.4算法與算法分析“好”算法的標準： 正確性，可讀性，健壯性，高效率與低存儲。評價算法的度量：程序所用算法運行時所要花費的時間代價程序中使用的數(shù)據(jù)結構占有的空間代價 算法的時間復雜度：算法的時間效率 算法的空間復雜度：算法的空間效率第33

頁1.4算法與算法分析評價算法效率的方法“未雨綢繆”——事前分析估算法：

對算法所需要的計算機資源——時間和空間進行估算。“亡羊補牢”——事后統(tǒng)計法：

通過上機運行，測試算法花費的時間。算法的平均執(zhí)行時間，算法的最大執(zhí)行時間。缺點：

1)必須編寫、執(zhí)行程序

2）其它因素掩蓋算法本質第34

頁1.4算法與算法分析影響算法時間效率的因素：算法選用的策略問題的規(guī)模編寫程序的語言編譯程序產生的機器代碼的質量計算機運行速度

第35

頁1.4算法與算法分析算法分析算法的復雜性與其所求解的問題規(guī)模直接有關，因此通常將問題規(guī)模n

作為一個參照量，求算法的時間開銷與n的關系f(n)。算法的漸近分析就是f(n)的增長趨勢。f(n)的函數(shù)關系一般較復雜，計算時只考慮可以顯著影響函數(shù)量級的部分（即：n的冪次最高的項，其他的常數(shù)項和低冪次項忽略不計），結果為原函數(shù)的一個近似值。這種分析是一種不精確估計，提供對于算法資源開銷進行評估的簡單化模型。第36

頁1.4算法與算法分析：算法的時間復雜度大O表示法 若存在兩個正的常數(shù)c和n0，對于任意n≥n0，都有T(n)≤c×f(n)，則稱T(n)=O(f(n))。n0問題規(guī)模n執(zhí)行次數(shù)n0之前的情況無關緊要T(n)c×f(n)T(n)為算法的漸近時間復雜度，簡稱算法時間復雜度。第37

頁1.4算法與算法分析：算法的時間復雜度大O表示法的運算規(guī)則單位時間簡單布爾或算術運算簡單I/O函數(shù)返回加法規(guī)則：f1(n)+f2(n)=Ｏ(max(f1(n),f2(n)))順序結構，if結構，switch結構乘法規(guī)則：f1(n)·f2(n)=Ｏ(f1(n)·f2(n))for,while,do-while結構第38

頁1.4算法與算法分析：算法的時間復雜度算法由控制語句和原操作（預定義數(shù)據(jù)類型的操作）組成，算法時間取決于兩者的綜合效果。例：n階矩陣相乘算法

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];}第39

頁1.4算法與算法分析：算法的時間復雜度例：n階矩陣相乘算法

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]；}T(n)=n+2n2+2n3

T(n)=O(n3)

說明：在計算算法時間復雜度時，可以忽略所有低次冪和最高次冪的系數(shù)。第40

頁2nn2nlognnLognfn2nn2nlognnlognΟ(1)＜Ο(log2n)＜Ο(n)＜Ο(nlog2n)＜Ο(n2)＜Ο(n3)＜…＜Ο(2n)＜Ο(n!)第41

頁1.4算法與算法分析：算法的時間復雜度例：在一維整型數(shù)組A[n]中順序查找與給定值k相等的元素（假設該數(shù)組中有且僅有一個元素值為k）。

intFind(intA[],intn){f