數(shù)據(jù)結構 緒論課件

數(shù)據(jù)結構信息科學與技術學院范紅E-mail:ccfanhong@163.com

1數(shù)據(jù)結構教材及參考書目：數(shù)據(jù)結構（C語言版）嚴蔚敏等編清華大學出版社數(shù)據(jù)結構習題集（C語言版）嚴蔚敏等編清華大學出版社數(shù)據(jù)結構C++語言描述劉衛(wèi)東等譯清華大學出版社2數(shù)據(jù)結構預備知識：C語言程序設計的基本技術離散數(shù)學概率論3數(shù)據(jù)結構第一章緒論第六章樹與二叉樹第二章線性表第七章圖第三章棧和隊列第八章動態(tài)存儲管理第四章串

第九章查找第五章數(shù)組與廣義表第十章內(nèi)部排序5第一章緒論目的：了解數(shù)據(jù)結構的背景掌握一些基本概念和術語掌握抽象數(shù)據(jù)類型的定義、表示與實現(xiàn)描述算法的類C語言掌握算法分析的一些基本方法6第一章緒論重點：有關數(shù)據(jù)結構的基本概念和術語掌握抽象數(shù)據(jù)類型ADT的定義、表示與實現(xiàn)熟悉類C語言的書寫規(guī)范理解算法五個要素的確切含義掌握估算時間復雜度的方法，了解空間復雜度的度量方法7第一章緒論難點：抽象數(shù)據(jù)類型ADT的表示與實現(xiàn)算法復雜度的分析方法8一、數(shù)據(jù)結構形成和發(fā)展背景計算機是一門研究用計算機進行信息表示和處理的科學兩個問題：

1）信息的表示和組織：直接關系到處理信息的程序的效率；

2）信息的處理：面向系統(tǒng)程序和應用程序的大規(guī)模和復雜結構1.1什么是數(shù)據(jù)結構10二、數(shù)據(jù)結構1、用計算機解決問題的步驟：具體問題—建立數(shù)學模型—設計算法—編制程序—測試和調(diào)整—最終答案建立數(shù)學模型（關鍵）：分析問題、提取操作對象、找出對象間關系，對此用數(shù)學語言加以描述算法設計：利用建立的數(shù)學模型，根據(jù)具體問題，設計出解決問題的方法1.1什么是數(shù)據(jù)結構12二、數(shù)據(jù)結構2、數(shù)據(jù)結構主要關心的：結構中各元素之間邏輯關系（數(shù)學模型）

線性結構：如圖書館的書目索引

樹形結構：見后面例子

圖形結構：見后面例子結構中各元素的存儲方式結構具有的行為特征（其上的操作）在計算機中的表示和實現(xiàn)

1.1什么是數(shù)據(jù)結構14例1.圖書館的書目檢索系統(tǒng)自動化問題（線性結構）圖書館的一本圖書由書名、作者、出版社等數(shù)據(jù)來描述，根據(jù)需要我們選擇其中的若干項組成一個數(shù)據(jù)元素來對應一本書圖書館的編目表反映了書與書之間的關系，是數(shù)據(jù)元素之間的結構。當然我們還應注意到書是具體地放在某個書架上的，它是編目表的物理實現(xiàn)圖書館從兩方面管理圖書：物理的藏書和邏輯的編目表。這就是圖書館的結構。和圖書館一樣計算機管理數(shù)據(jù)，也有兩個方面：即物理的存儲和邏輯的關系1.1什么是數(shù)據(jù)結構151.1什么是數(shù)據(jù)結構16例2：下棋問題1.1什么是數(shù)據(jù)結構17例3.多叉路口交通燈的管理（圖結構）11112223344111.1什么是數(shù)據(jù)結構18數(shù)據(jù)結構是一門研究非數(shù)值計算的程序設計問題中計算機的操作對象以及它們之間相互關系和操作等的學科對這種結構定義相應的運算，而且確保經(jīng)過這些運算后所得到的新結構仍然是原來的結構類型1.1什么是數(shù)據(jù)結構20二、數(shù)據(jù)結構

NiklausWirth：

Algorithms+DataStructures=Programs

程序設計:為計算機處理問題編制一組指令集算法：處理問題的策略數(shù)據(jù)結構：問題的數(shù)學模型1.1什么是數(shù)據(jù)結構211.2基本概念和術語數(shù)據(jù)：數(shù)據(jù)是信息的載體，是描述客觀事物的數(shù)、字符以及所有能輸入到計算機中，被計算機程序識別和處理的符號的集合數(shù)值性數(shù)據(jù)/非數(shù)值性數(shù)據(jù)數(shù)據(jù)元素：數(shù)據(jù)基本單位，通常作為一個整體來考慮，如：“樹”中的一個棋盤格局；學生信息表，一個數(shù)據(jù)元素（記錄）含若干個數(shù)據(jù)項等數(shù)據(jù)項是數(shù)據(jù)的不可分割的最小單位231.2基本概念和術語數(shù)據(jù)對象：數(shù)據(jù)的子集。具有相同性質(zhì)的數(shù)據(jù)成員（數(shù)據(jù)元素）的集合。數(shù)據(jù)對象可以是有限的，也可以是無限的整數(shù)數(shù)據(jù)對象:N={0,1,2,…}英文字符類型的數(shù)據(jù)對象:{A，B，C，D，E，F(xiàn)，…}

學生數(shù)據(jù)對象：數(shù)據(jù)表數(shù)據(jù)、數(shù)據(jù)元素和數(shù)據(jù)對象之間的關系：

數(shù)據(jù)數(shù)據(jù)元素數(shù)據(jù)項241.2基本概念和術語數(shù)據(jù)結構與數(shù)據(jù)對象之間的區(qū)別和聯(lián)系？數(shù)據(jù)對象僅僅是數(shù)據(jù)元素的集合，不涉及這些元素之間的關系描述數(shù)據(jù)結構不僅要描述數(shù)據(jù)對象，而且要描述元素彼此之間的關系261.2基本概念和術語數(shù)據(jù)結構描述

Data-Structure=(D,S)

D——數(shù)據(jù)集；S——關系集例：復數(shù)的數(shù)據(jù)結構定義如下：

Complex=(C，R)

其中：C是含兩個實數(shù)的集合﹛C1，C2﹜，分別表示復數(shù)的實部和虛部。R={P}，P是定義在集合上的一種關系{〈C1，C2〉}271.2基本概念和術語數(shù)據(jù)結構描述

Data-Structure=(D,S)D——數(shù)據(jù)集；S——關系集例：學科研究課題小組

Group=(P,R)

其中：P={T,G1,G2,…Gn,S11,S12,…Snm}R={R1,R2}R1={<T,Gi>|i=1,2,3}R2={<Gi,Sij>|i=1,2,3,j=1,2}28301.2基本概念和術語數(shù)據(jù)的物理（存儲）結構物理結構：數(shù)據(jù)結構中數(shù)據(jù)元素間的關系在存儲器中的存儲方法（表現(xiàn)和實現(xiàn)）物理結構中的基本定義：

1）位：二進制中的一位；信息表示的最小單位

2）元素（結點）：由若干位組合起來形成的一個位串，可看成是數(shù)據(jù)元素在計算機中的映象

3）數(shù)據(jù)域：當數(shù)據(jù)元素由若干數(shù)據(jù)項組成時，位串中對應于各個數(shù)據(jù)項的子位串311.2基本概念和術語按照物理結構的不同分為：1）順序存儲結構：利用在存儲器中的物理關系來表示邏輯關系。邏輯上相鄰的數(shù)據(jù)元素存儲在物理位置上相毗鄰的存儲單元里，元素的關系由存儲單元的鄰接關系來體現(xiàn)2）鏈式存儲結構：數(shù)據(jù)元素可以在計算機內(nèi)任意位置上存放（它不要求邏輯上相鄰的元素在物理位置上也相鄰)，用在存儲器中附加指針的方式來表示邏輯關系。將數(shù)據(jù)元素存放的存儲單元分為兩個部分，分別存放數(shù)據(jù)和指針，稱為數(shù)據(jù)域和指針域321.2基本概念和術語數(shù)據(jù)的邏輯結構和物理結構的關系：邏輯結構只抽象地描述數(shù)據(jù)元素邏輯關系（簡稱數(shù)據(jù)結構）物理結構是一個邏輯結構映像到計算機中所得到的存儲表示算法的設計：取決于選定的數(shù)據(jù)邏輯結構算法的實現(xiàn)：依賴于采用的存儲結構331.2基本概念和術語數(shù)據(jù)類型用以刻畫（程序）操作對象的特性。一個值的集合（整型變量）+該集合上定義的一組操作(不體現(xiàn)值間關系)（加、減等操作）類型明顯或隱含地規(guī)定了：在程序執(zhí)行期間變量或表達式所有可能的取值范圍以及在這些值上允許進行的操作341.2基本概念和術語抽象數(shù)據(jù)類型：數(shù)據(jù)結構+定義在此結構上的一組操作（和其在計算機上的表示和實現(xiàn)無關）。不再局限于前述各處理器中已定義并實現(xiàn)的數(shù)據(jù)類型，還包括用戶自定義的數(shù)據(jù)類型351.2基本概念和術語抽象數(shù)據(jù)類型1）一個含抽象數(shù)據(jù)類型的軟件模塊包含：定義、表示和實現(xiàn)2）三元組表示（D,S,P）

D：數(shù)據(jù)對象，S：D上的關系集，P：D上的基本操作集361.2基本概念和術語抽象數(shù)據(jù)類型定義：

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

數(shù)據(jù)對象：<數(shù)據(jù)對象定義>

數(shù)據(jù)關系：<數(shù)據(jù)關系定義>

基本操作：<基本操作定義>}ADT抽象數(shù)據(jù)類型名其中：1）數(shù)據(jù)對象和數(shù)據(jù)關系的定義用偽碼表示；371.2基本概念和術語抽象數(shù)據(jù)類型定義：2）基本操作的定義：基本操作名（參數(shù)表）初始條件：（初始條件描述）操作結果：（操作結果描述）基本操作有兩種參數(shù)：

賦值參數(shù)：為操作提供輸入值

引用參數(shù)：以&打頭，除提供輸入值外，還將返回操作結果381.2基本概念和術語抽象數(shù)據(jù)類型定義：2）基本操作的定義：

初始條件：描述了操作執(zhí)行之前數(shù)據(jù)結構和參數(shù)應滿足的條件，若不滿足，則操作失敗，并返回相應出錯信息

操作結果：說明了操作正常完成之后，數(shù)據(jù)結構的變化狀況和應返回的結果。若初始條件為空，則省略之391.2基本概念和術語抽象數(shù)據(jù)類型三元組的定義:（P9，例1-6）ADTTriplet{

數(shù)據(jù)對象：D={e1,e2,e3|e1,e2,e3ElemSet}

數(shù)據(jù)關系：R1={<e1,e2>,<e2,e3>}

基本操作：

InitTriplet(&T)

DestroyTriplet(&T) Get(T,i,&e) Put(&T,i,e) …}ADTTriplet401.3抽象數(shù)據(jù)類型的表示與實現(xiàn)可以通過固有數(shù)據(jù)類型表示和實現(xiàn)，即利用處理器中已存在的數(shù)據(jù)類型來說明新的結構，用已經(jīng)實現(xiàn)的操作來組合新的操作利用類C語言（C語言的一個核心子集）作為描述工具類C語言描述：P10-13

typedef

數(shù)據(jù)類型定義

ElemType

數(shù)據(jù)元素類型

Status函數(shù)結果狀態(tài)的整數(shù)描述與運算&&,或運算||41類C語言描述：P10-13

內(nèi)存的動態(tài)分配與釋放指針變量=new數(shù)據(jù)類型

delete指針變量基本操作的算法：函數(shù)描述函數(shù)結果主要狀態(tài)代碼：

TURE,OK=1FALSE,ERROR=0OVERFLOW=-21.3抽象數(shù)據(jù)類型的表示與實現(xiàn)42類C語言描述：P10-13

幾組特殊的賦值形式：交換賦值，數(shù)組賦值，條件賦值選擇語句：條件語句，開關語句循環(huán)語句：for,while,do-while

輸入和輸出語句：三種結束語句return,break,exit

注釋：基本函數(shù)：max,min,abs,eof,eoln1.3抽象數(shù)據(jù)類型的表示與實現(xiàn)43例1-7抽象數(shù)據(jù)類型Triplet的表示和實現(xiàn)（P11-13）基本操作的函數(shù)原型：

StatusInitTriplet(Triplet&T,ElemTypev1,ElemTypev2,ElemTypev3);//操作結果：構造了三元組T，e1,e2和e3被賦以參數(shù)v1,v2,v3的值

StatusDestroyTriplet(Triplet&T)；

//操作結果：三元組T被銷毀。

StatusGet(TripletT,inti,ElemType&e);//初始條件：三元組T已存在，1i3//操作結果：用e返回T的第i元的值。1.3抽象數(shù)據(jù)類型的表示與實現(xiàn)44例1-7抽象數(shù)據(jù)類型Triplet的表示和實現(xiàn)（P11-13）基本操作的實現(xiàn)：

StatusInitTriplet(Triplet&T,ElemTypev1,ElemTypev2,ElemTypev3){//構造三元組T，依此置T的三個元素的初值為v1,v2,v3 T=(ElemType*)malloc(3*sizeof(ElemType));if(!T)exit(OVERFLOW);T[0]=v1;T[1]=v2;T[2]=v3;returnOK;}1.3抽象數(shù)據(jù)類型的表示與實現(xiàn)45例1-7抽象數(shù)據(jù)類型Triplet的表示和實現(xiàn)（P11-13）基本操作的實現(xiàn)：

StatusDestroyTriplet(Triplet&T){//銷毀三元組T free(T);T=null;returnOK;}StatusGet(TripletT,inti,ElemType&e){//1i3,用e返回T的第i元的值。

if(i<1||i>3)returnERROR;e=T[i-1];returnOK;}1.3抽象數(shù)據(jù)類型的表示與實現(xiàn)46例：復數(shù)抽象數(shù)據(jù)類型示例ADTComplex{ 數(shù)據(jù)對象：D={c1,c2|c1,c2R(R為實數(shù)集）} 數(shù)據(jù)關系：S={<c1,c2>（c1為實部，c2為虛部）} 基本操作： voidAssign(&A,c1,c2） voidAdd(&A,B) voidMinus(&A,B) voidMultiply(&A,B) voidDivide(&A,B) ...}ADTComplex1.3抽象數(shù)據(jù)類型的表示與實現(xiàn)471.4算法和算法分析算法：對特定問題求解步驟的一種描述，它是指令的有限序列，其中每一條指令表示一個或多個操作算法的五個重要特性：

1）有窮性：一個算法必須總是在執(zhí)行有窮步之后結束，且每一步都在有窮時間內(nèi)完成

2）確定性：算法中每一條指令必須有確切的含義，不存在二義性。且算法只有一個入口和一個出口481.4算法和算法分析算法的五個重要特性：

3）可行性：一個算法是可行的。即算法描述的操作都是可以通過已經(jīng)實現(xiàn)的基本運算執(zhí)行有限次來實現(xiàn)的

4）輸入：一個算法有零個或多個輸入，這些輸入取自于某個特定的對象集合

5）輸出：一個算法有一個或多個輸出，這些輸出是同輸入有著某些特定關系的量491.4算法和算法分析算法設計的要求：

1）正確性：算法應滿足具體問題的需求

a）程序不含語法錯誤；b）程序?qū)τ谝话爿斎霐?shù)據(jù)的正確性；c）程序?qū)τ诳量?、刁難輸入數(shù)據(jù)的正確性；d）程序?qū)τ谝磺泻戏ㄝ斎霐?shù)據(jù)的正確性

2）可讀性：算法應該好讀。以有利于人對程序的理解

3）健壯性：算法應具有容錯處理。當輸入非法數(shù)據(jù)時，算法應對其作出反應，而不是產(chǎn)生莫名其妙的輸出結果501.4算法和算法分析算法設計的要求：

4）效率與低存儲量需求

效率：算法執(zhí)行時間

存儲量需求：算法執(zhí)行過程中所需要的最大存儲空間

一般，這兩者與問題的規(guī)模有關511.4算法和算法分析算法效率的度量算法執(zhí)行時間的度量方法：1）事后統(tǒng)計的方法：收集此算法的執(zhí)行時間和實際占用空間的統(tǒng)計資料缺陷：a）必須先運行依據(jù)算法編制的程序；b）依賴于計算機的硬件、軟件等環(huán)境因素2）事前分析估算的方法：求出該算法的一個時間界限函數(shù)算法運行所消耗的時間取決于：a）依據(jù)的算法選用何種策略；b）問題的規(guī)模；c）書寫程序的語言；d）編譯程序所產(chǎn)生的機器代碼的質(zhì)量；e）機器執(zhí)行指令的速度521.4算法和算法分析算法的時間度量1）原操作：基本操作2）算法的時間度量：原操作重復執(zhí)行的次數(shù)3）算法的漸近時間復雜度：原操作重復執(zhí)行的次數(shù)是問題規(guī)模n的某個函數(shù)f(n)T(n)=O(f(n))4）頻度：原操作重復執(zhí)行的次數(shù)531.4算法和算法分析算法的時間度量常見的時間復雜度：

1）O(1)常量階2）O(n)線性階

3）O(n2)平方階4）O(n3)立方階

5）O(logn)對數(shù)階6）O(2n)指數(shù)階541.4算法和算法分析算法的時間度量六種常用計算算法時間的多項式的關系為：

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

O(2n)<O(n!)<O(nn)

當n取得很大時，指數(shù)時間算法和多項式時間算法在所需時間上非常懸殊。因此，若能將現(xiàn)有指數(shù)時間算法中的任何一個算法化簡為多項式時間算法，那就取得了一個偉大的成就551.4算法和算法分析算法的時間度量例1.{++x;s=0;}將x自增看成是基本操作，則語句頻度為１，即時間復雜度為Ｏ(1)如果將s=0也看成是基本操作，則語句頻度為1，其時間復雜度仍為Ｏ(1)，即常量階例2.for(i=1;i<=n;++i){++x;s+=x;}

語句頻度為：n

其時間復雜度為：O(n)

即時間復雜度為線性階561.4算法和算法分析算法的時間度量例3.for(i=1;i<=n;++i)

for(j=1;j<=n;++j){++x;s+=x;}

語句頻度為：n2

其時間復雜度為：O(n2)

即時間復雜度為平方階。571.4算法和算法分析算法的時間度量例4.兩個N*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]; /*原操作*/ }問題規(guī)模：n原操作：c[i][j]+=a[i][k]*b[k][j];基本操作重復執(zhí)行的次數(shù)：f(n)=n3該算法時間度量記作T(n)=O(f(n))=O(n3)時間復雜度：O(n3)581.4算法和算法分析算法的時間度量在難以精確計算基本操作執(zhí)行次數(shù)的情況下，只需求出它關于n的增長率或階即可。例

for(i=2;i<=n;++i)for(j=2;j<=i-1;++j){++x;a[i][j]=x;}591.4算法和算法分析算法的時間度量當基本操作執(zhí)行次數(shù)隨問題的輸入數(shù)據(jù)集變化時，計算平均時間復雜度或最壞情況下的上界。例有的情況下，算法中基本操作重復執(zhí)行的次數(shù)還隨問題的輸入數(shù)據(jù)集的不同而不同（冒泡排序法）voidBubble_Sort(inta[],intn){for(i=n-1,change=TRUE;i>=1&&change;--i) {change=FALSE; for(j=0;j<i;j++)

if(a[j]>a[j+1]) {a[j]>a[j+1];change=TRUE;}