數(shù)據(jù)結(jié)構(gòu)教學(xué)課件緒論章

《數(shù)據(jù)結(jié)構(gòu)》田臣通信120112022013年秋季eBack!第一章：緒論2第一章：緒論3ChenTian(田臣)BS/MS/Ph.DinHUST,PostDocinYaleComputerNetworking,DistributedSystems

PublicationsACMSIGCOMMIEEETransactionsonParallelandDistributedSystemsIEEETransactionsonVehicularTechnologyIEEETransactionsonNetworkandServiceManagementInstructor逐一回答。。。數(shù)據(jù)結(jié)構(gòu)講什么內(nèi)容？為什么要學(xué)數(shù)據(jù)結(jié)構(gòu)？教學(xué)目標(biāo)和形式是什么？如何考核？第一章：緒論4《數(shù)據(jù)結(jié)構(gòu)》講什么內(nèi)容？數(shù)據(jù)結(jié)構(gòu)是一門研究程序設(shè)計(jì)問(wèn)題中計(jì)算機(jī)的操作對(duì)象及其關(guān)系和操作的學(xué)科。它主要研究：數(shù)據(jù)的邏輯結(jié)構(gòu)：數(shù)據(jù)之間的邏輯關(guān)系

數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)：數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)中的表示

數(shù)據(jù)的操作算法：插入、刪除、修改、查詢、排序等

第一章：緒論6學(xué)號(hào)姓名性別出生日期二外…10001王軍男1993/09/02法語(yǔ)…20003李明男1992/12/25西語(yǔ)…30006湯曉影女1994/03/26日語(yǔ)……………………例1學(xué)籍管理問(wèn)題——表結(jié)構(gòu)第一章：緒論7為什么要學(xué)《數(shù)據(jù)結(jié)構(gòu)》？能設(shè)計(jì)出合適的程序Ph.DinUSMSinHUST碼工in北京，上海，深圳，廣州。。。數(shù)據(jù)結(jié)構(gòu)課程的地位

針對(duì)非數(shù)值計(jì)算的程序設(shè)計(jì)問(wèn)題，研究計(jì)算機(jī)的操作對(duì)象以及它們之間的關(guān)系和操作。介于數(shù)學(xué)、計(jì)算機(jī)硬件和計(jì)算機(jī)軟件三者之間的一門核心課程。第一章：緒論8學(xué)時(shí)數(shù)：44+12(通信1201-04/4，7，9周一晚9-12/南一樓中213-216)？？教材：嚴(yán)蔚敏等，數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版），清華大學(xué)出版社（配題集）

參考書(shū)：[1]D.E.Knuth,theartofcomputerprogrammingvolume1/fundamentalalgorithms;volume3/sortingandsearching[2]算法＋程序＝數(shù)據(jù)結(jié)構(gòu)沃思著科學(xué)出版社[3]數(shù)據(jù)結(jié)構(gòu)（用面向?qū)ο蠓椒ㄅcＣ＋＋描述）殷人昆清華大學(xué)出版社１９９９教學(xué)目標(biāo)：

掌握數(shù)據(jù)結(jié)構(gòu)和算法的基本概念和技術(shù)

數(shù)組、線性表、棧和隊(duì)列、串、廣義表、樹(shù)和二叉樹(shù)、圖等典型數(shù)據(jù)結(jié)構(gòu)及相關(guān)算法，以及內(nèi)排序、查找等重要技術(shù)

對(duì)于給定問(wèn)題，能夠選擇合適的數(shù)據(jù)結(jié)構(gòu)，并設(shè)計(jì)相應(yīng)的操作算法。9第一章：緒論教學(xué)大綱：第1章緒論第2章線性表第3章棧和隊(duì)列第4章串第5章數(shù)組和廣義表第6章樹(shù)和二叉樹(shù)第7章圖第9章查找第10章排序10教學(xué)大綱第一章：緒論11如何考核？期末考試作業(yè)點(diǎn)名回答問(wèn)題按時(shí)上課，不要睡覺(jué)自己做完每一個(gè)題目，每一個(gè)實(shí)驗(yàn)不懂就問(wèn)第一章：緒論12你需要做的。。。爭(zhēng)取把思路講清楚OfficeHour第一章：緒論13我能為你做的。。。第一章：緒論14第1章緒論1.1什么是數(shù)據(jù)結(jié)構(gòu)1.2基本概念和術(shù)語(yǔ)1.3抽象數(shù)據(jù)類型的表示和實(shí)現(xiàn)1.4算法和算法分析15第一章：緒論1.1什么是數(shù)據(jù)結(jié)構(gòu)16計(jì)算機(jī)求解問(wèn)題步驟

實(shí)際問(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.1什么是數(shù)據(jù)結(jié)構(gòu)17程序設(shè)計(jì)的實(shí)質(zhì)是什么?數(shù)據(jù)表示＋數(shù)據(jù)處理數(shù)據(jù)表示的核心任務(wù)：數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)；數(shù)據(jù)處理的核心任務(wù)：算法設(shè)計(jì)；數(shù)據(jù)結(jié)構(gòu)課程主要討論數(shù)據(jù)表示和數(shù)據(jù)處理的基本問(wèn)題，也就是數(shù)據(jù)結(jié)構(gòu)和算法的設(shè)計(jì)問(wèn)題；數(shù)據(jù)結(jié)構(gòu)問(wèn)題起源于程序設(shè)計(jì)

1.1什么是數(shù)據(jù)結(jié)構(gòu)1.1什么是數(shù)據(jù)結(jié)構(gòu)18例1學(xué)籍管理問(wèn)題——表結(jié)構(gòu)學(xué)號(hào)姓名性別出生日期二外…10001王軍男1993/09/02法語(yǔ)…20003李明男1992/12/25西語(yǔ)…30006湯曉影女1994/03/26日語(yǔ)……………………1.1什么是數(shù)據(jù)結(jié)構(gòu)19例2人機(jī)對(duì)弈問(wèn)題——樹(shù)結(jié)構(gòu)如何實(shí)現(xiàn)對(duì)弈?各格局之間是什么關(guān)系？…………..……..………...……1.1什么是數(shù)據(jù)結(jié)構(gòu)20例3教學(xué)計(jì)劃編排問(wèn)題——圖結(jié)構(gòu)C4,C5,C6數(shù)據(jù)庫(kù)原理C7C2,

C4計(jì)算機(jī)原理C6C3,C4數(shù)據(jù)結(jié)構(gòu)C5C1,C2程序設(shè)計(jì)C4C1離散數(shù)學(xué)C3無(wú)計(jì)算機(jī)導(dǎo)論C2無(wú)高等數(shù)學(xué)C1先修課課程名稱編號(hào)C1C2C3C4C6C5C7如何表示課程之間的先修關(guān)系？1.1什么是數(shù)據(jù)結(jié)構(gòu)21什么是數(shù)據(jù)結(jié)構(gòu)？Data_Structure=（D,S）元素有限集關(guān)系有限集

研究非數(shù)值問(wèn)題中計(jì)算機(jī)的操作對(duì)象以及它們之間的關(guān)系和操作的學(xué)科。相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合，表示為：程序設(shè)計(jì)＝好算法＋好結(jié)構(gòu)同樣的數(shù)據(jù)對(duì)象，用不同的數(shù)據(jù)結(jié)構(gòu)來(lái)表示，運(yùn)算效率可能有明顯的差異。第1章緒論1.1什么是數(shù)據(jù)結(jié)構(gòu)1.2基本概念和術(shù)語(yǔ)1.3抽象數(shù)據(jù)類型的表示和實(shí)現(xiàn)1.4算法和算法分析22第一章：緒論1.2基本概念和術(shù)語(yǔ)23數(shù)據(jù)(data)：所有能輸入到計(jì)算機(jī)中并能被計(jì)算機(jī)程序識(shí)別和處理的符號(hào)集合。

數(shù)值數(shù)據(jù)：整數(shù)、實(shí)數(shù)等非數(shù)值數(shù)據(jù)：圖形、圖象、聲音、文字等數(shù)據(jù)元素(dataelement)：數(shù)據(jù)的基本單位，在計(jì)算機(jī)程序中通常作為一個(gè)整體進(jìn)行考慮和處理。數(shù)據(jù)項(xiàng)(dataitem)：構(gòu)成數(shù)據(jù)元素的不可分割的最小單位。三者之間的關(guān)系：數(shù)據(jù)>數(shù)據(jù)元素

>數(shù)據(jù)項(xiàng)例：班級(jí)通訊錄

>個(gè)人記錄

>姓名、年齡……1.2基本概念和術(shù)語(yǔ)24數(shù)據(jù)結(jié)構(gòu)的主要內(nèi)容1.2基本概念和術(shù)語(yǔ)25集合結(jié)構(gòu)：

僅同屬一個(gè)集合線性結(jié)構(gòu):

一對(duì)一(1:1)樹(shù)結(jié)構(gòu):

一對(duì)多(1:n)

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

多對(duì)多(m:n)非線性線性邏輯結(jié)構(gòu)可細(xì)分為4類：指數(shù)據(jù)元素之間的邏輯關(guān)系。即從邏輯關(guān)系上描述數(shù)據(jù)，它與數(shù)據(jù)的存儲(chǔ)無(wú)關(guān)，是獨(dú)立于計(jì)算機(jī)的。什么叫數(shù)據(jù)的邏輯結(jié)構(gòu)？26（1）

DS=(D,S)D={a,b,c,d,e,f}S={(a,e),(b,c),(c,a),(e,f),(f,d)}解：上述表達(dá)式可用圖形表示為：bcaefd此結(jié)構(gòu)為線性的。例：用圖形表示下列數(shù)據(jù)結(jié)構(gòu)，并指出它們是屬于線性結(jié)構(gòu)還是非線性結(jié)構(gòu)。1.2基本概念和術(shù)語(yǔ)27

d1d5d2d4d3該結(jié)構(gòu)是非線性的。解：上述表達(dá)式可用圖形表示為：（2）

S=(D,R)

D={di|1≤i≤5}

R={(di,dj),i<j}1.2基本概念和術(shù)語(yǔ)28存儲(chǔ)結(jié)構(gòu)亦稱物理結(jié)構(gòu)，是數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)器內(nèi)的表示（或映像）。它依賴于計(jì)算機(jī)。常用的兩種存儲(chǔ)結(jié)構(gòu)：順序、鏈?zhǔn)绞裁唇袛?shù)據(jù)的存儲(chǔ)結(jié)構(gòu)？1.2基本概念和術(shù)語(yǔ)存儲(chǔ)結(jié)構(gòu)兩方面的內(nèi)容（1）數(shù)據(jù)元素自身值的表示（數(shù)據(jù)域）（2）表達(dá)該結(jié)點(diǎn)與其它結(jié)點(diǎn)關(guān)系的域（鏈域）291.2基本概念和術(shù)語(yǔ)數(shù)據(jù)元素之間的關(guān)系在計(jì)算機(jī)中通常有以二種不同的表示方法，對(duì)應(yīng)二種不同的存儲(chǔ)結(jié)構(gòu)順序映象

順序存儲(chǔ)結(jié)構(gòu)非順序映象

鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)這二種存儲(chǔ)結(jié)構(gòu)主要區(qū)別順序存儲(chǔ)結(jié)構(gòu)只需存儲(chǔ)數(shù)據(jù)元素的空間，而數(shù)據(jù)元素間的關(guān)系是借助數(shù)據(jù)元素的相對(duì)位置對(duì)表示的，但要求空間是連續(xù)的。鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)不僅需存儲(chǔ)數(shù)據(jù)元素的空間，而且需存儲(chǔ)元素間關(guān)系的空間，但存儲(chǔ)空間不要求是連續(xù)的。301.2基本概念和術(shù)語(yǔ)存儲(chǔ)結(jié)構(gòu)示例復(fù)數(shù)3.0－2.3i的兩種存儲(chǔ)方式：－2.303023.00300041503023.003000415－2.3

地址內(nèi)容

地址內(nèi)容2字節(jié)順序存儲(chǔ)方式鏈?zhǔn)酱鎯?chǔ)方式借助指示元素存儲(chǔ)地址的指針（Pointer）來(lái)表示數(shù)據(jù)之間的邏輯關(guān)系。

實(shí)部和虛部之間的關(guān)系用值“0415”的指針來(lái)表示(0415是虛部的存儲(chǔ)地址)。2字節(jié)31在數(shù)據(jù)的邏輯結(jié)構(gòu)上定義的操作算法。它在數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)。最常用的數(shù)據(jù)運(yùn)算有5種：插入、刪除、修改、查找、排序什么是數(shù)據(jù)的運(yùn)算？1.2基本概念和術(shù)語(yǔ)第1章緒論1.1什么是數(shù)據(jù)結(jié)構(gòu)1.2基本概念和術(shù)語(yǔ)1.3抽象數(shù)據(jù)類型的表示和實(shí)現(xiàn)1.4算法和算法分析32第一章：緒論1.3抽象數(shù)據(jù)類型的表示和實(shí)現(xiàn)33ADT=AbstractDataType數(shù)據(jù)類型：是一個(gè)值的集合和定義在該值上的一組操作的總稱。抽象數(shù)據(jù)類型：由用戶定義的一個(gè)數(shù)學(xué)模型與定義在該模型上的一組操作，它由基本的數(shù)據(jù)類型構(gòu)成。ADT與數(shù)據(jù)類型實(shí)質(zhì)上是一個(gè)概念，但其特征是使用與實(shí)現(xiàn)分離，實(shí)行封裝和信息隱蔽（獨(dú)立于計(jì)算機(jī)）“抽象”的意義在于數(shù)據(jù)類型的數(shù)學(xué)抽象特性1.3抽象數(shù)據(jù)類型的表示和實(shí)現(xiàn)34抽象數(shù)據(jù)類型的定義ADT=（D，S，P）

數(shù)據(jù)對(duì)象D上的關(guān)系集D上的操作集ADT抽象數(shù)據(jù)類型名{數(shù)據(jù)對(duì)象：<數(shù)據(jù)對(duì)象的定義>數(shù)據(jù)關(guān)系：<數(shù)據(jù)關(guān)系的定義>

基本操作：<基本操作的定義>}ADT抽象數(shù)據(jù)類型名ADT常用定義格式1.3抽象數(shù)據(jù)類型的表示和實(shí)現(xiàn)35抽象數(shù)據(jù)類型如何表示和實(shí)現(xiàn)

抽象數(shù)據(jù)類型可以通過(guò)固有的數(shù)據(jù)類型（如整型、實(shí)型、字符型等）來(lái)表示和實(shí)現(xiàn)。注1

：它有些類似C語(yǔ)言中的結(jié)構(gòu)（struct)類型，但增加了相關(guān)的服務(wù)(或操作)。注2

：教材中用類C語(yǔ)言（介于偽碼和C語(yǔ)言之間）作為描述工具。其描述語(yǔ)法匯總在教材P10-11上。但上機(jī)時(shí)要用具體語(yǔ)言實(shí)現(xiàn)，如C或C++等1.3抽象數(shù)據(jù)類型的表示和實(shí)現(xiàn)36抽象數(shù)據(jù)類型的表示與實(shí)現(xiàn)---

類C語(yǔ)言預(yù)定義常量和類型函數(shù)結(jié)果狀態(tài)代碼#defineTRUE1#defineFALSE0#defineOK1#defineERROR0#defineINFEASIBLE-1#defineOVERFLOW-2函數(shù)的返回類型status，其值是函數(shù)結(jié)果狀態(tài)代碼typedefintstatus;1.3抽象數(shù)據(jù)類型的表示和實(shí)現(xiàn)37抽象數(shù)據(jù)類型的表示與實(shí)現(xiàn)---

類C語(yǔ)言數(shù)據(jù)結(jié)構(gòu)的表示（存儲(chǔ)結(jié)構(gòu)）用類型定義（typedef）描述。數(shù)據(jù)元素的類型約定為ElemType,由用戶在使用該數(shù)據(jù)類型時(shí)自行定義。示例：typedefstructLNode{Elemtypedata;structLNode*next;}Lnode,*LinkList;基本操作的算法都用以下形式的函數(shù)描述函數(shù)類型函數(shù)名（函數(shù)參數(shù)表）{//算法說(shuō)明語(yǔ)句序列} //函數(shù)名1.3抽象數(shù)據(jù)類型的表示和實(shí)現(xiàn)38抽象數(shù)據(jù)類型的表示與實(shí)現(xiàn)---

類C語(yǔ)言賦值語(yǔ)句簡(jiǎn)單賦值 變量名=表達(dá)式串聯(lián)賦值 變量名1=變量名2=·

·

·=變量名k=表達(dá)式;成組賦值（變量名1，變量名2，·

·

·，變量名k）=

（表達(dá)式1，表達(dá)式2，·

·

·，表達(dá)式k）; 結(jié)構(gòu)名=結(jié)構(gòu)名； 結(jié)構(gòu)名=（表達(dá)式1，·

·

·，表達(dá)式k）; 變量名[]=表達(dá)式； 變量名[起始下標(biāo)·

·

·終止下表]= 變量名[起始下標(biāo)·

·

·終止下表]1.3抽象數(shù)據(jù)類型的表示和實(shí)現(xiàn)39抽象數(shù)據(jù)類型的表示與實(shí)現(xiàn)---

類C語(yǔ)言選擇語(yǔ)句條件語(yǔ)句1if(表達(dá)式)語(yǔ)句；條件語(yǔ)句2if(表達(dá)式)語(yǔ)句；else語(yǔ)句；開(kāi)關(guān)語(yǔ)句1switch(表達(dá)式){case值1：語(yǔ)句序列1；break;···case值n;語(yǔ)句序列n;break;default:語(yǔ)句序列n+1;}1.3抽象數(shù)據(jù)類型的表示和實(shí)現(xiàn)40抽象數(shù)據(jù)類型的示例例：定義并實(shí)現(xiàn)復(fù)數(shù)抽象數(shù)據(jù)類型（定義）ADTComplex{數(shù)據(jù)對(duì)象：D={c1,c2|c1,c2R(R為實(shí)數(shù)集）}數(shù)據(jù)關(guān)系：S={<c1,c2>（c1為實(shí)部，c2為虛部）}基本操作：

voidAssign(*A,c1,c2） voidAdd(*A,B) voidMinus(*A,B) voidMultiply(*A,B) voidDivide(*A,B) ...}ADTComplex1.3抽象數(shù)據(jù)類型的表示和實(shí)現(xiàn)41抽象數(shù)據(jù)類型的示例例:定義并實(shí)現(xiàn)復(fù)數(shù)抽象數(shù)據(jù)類型（實(shí)現(xiàn)/類C描述）

typedefItemType double;typedefst