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

數(shù)據(jù)結(jié)構(gòu)東南大學計算機學院xx1謝謝欣賞2019-9-5數(shù)據(jù)結(jié)構(gòu)東南大學計算機學院xx1謝謝欣賞2019-9-5課程說明2謝謝欣賞2019-9-5課程說明2謝謝欣賞2019-9-5教材殷人昆,《數(shù)據(jù)結(jié)構(gòu)——用面向?qū)ο蠓椒ㄅcC++描述（第2版）》,清華大學出版社,2007參考書目金遠平，《數(shù)據(jù)結(jié)構(gòu)C++描述》，清華大學出版社，2005W.FordandW.Topp,DataStructureswithC++,清華大學出版社（影印版）,19973謝謝欣賞2019-9-5教材殷人昆,《數(shù)據(jù)結(jié)構(gòu)——用面向?qū)ο蠓椒ㄅcC++描述（第2版數(shù)據(jù)結(jié)構(gòu)的重要性計算機核心課程許多課程的基礎(chǔ)考研、找工作須復(fù)習的一門課4操作系統(tǒng)

軟件工程編譯原理人工智能圖形學數(shù)據(jù)庫數(shù)據(jù)結(jié)構(gòu)●●●●●●謝謝欣賞2019-9-5數(shù)據(jù)結(jié)構(gòu)的重要性計算機核心課程4操作系統(tǒng)

軟件工程編譯原理人本章主要內(nèi)容數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的存儲結(jié)構(gòu)抽象數(shù)據(jù)類型算法定義算法性能分析與度量5謝謝欣賞2019-9-5本章主要內(nèi)容數(shù)據(jù)結(jié)構(gòu)的基本概念5謝謝欣賞2019-9-5數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)數(shù)據(jù)元素數(shù)據(jù)結(jié)構(gòu)6謝謝欣賞2019-9-5數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)6謝謝欣賞2019-9-5數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)信息的載體（殷人昆）信息的一種符號表示（嚴蔚敏）描述事物的符號記錄（維基）在計算機科學中，數(shù)據(jù)指能輸入到計算機中并被計算機程序識別和處理的符號的集合。7謝謝欣賞2019-9-5數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)7謝謝欣賞2019-9-5數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)數(shù)據(jù)元素數(shù)據(jù)的基本單位。在計算機程序中常作為一個整體進行考慮和處理。如學生組成班級，學生是數(shù)據(jù)元素，班級是學生集合。8謝謝欣賞2019-9-5數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)8謝謝欣賞2019-9-5數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)數(shù)據(jù)元素數(shù)據(jù)結(jié)構(gòu)某一數(shù)據(jù)元素集合中數(shù)據(jù)元素之間的關(guān)系。形式化定義：Data_Structure={D,R}D是數(shù)據(jù)元素的集合；R是數(shù)據(jù)元素之間關(guān)系的有限集合。9謝謝欣賞2019-9-5數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)9謝謝欣賞2019-9-5數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)元素及其之間的抽象關(guān)系集合線狀結(jié)構(gòu)樹狀結(jié)構(gòu)圖或網(wǎng)狀結(jié)構(gòu)10謝謝欣賞2019-9-5數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)元素及其之間的抽象關(guān)系10謝謝欣賞2019數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)元素及其之間的抽象關(guān)系集合線狀結(jié)構(gòu)樹狀結(jié)構(gòu)圖或網(wǎng)狀結(jié)構(gòu)11謝謝欣賞2019-9-5數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)元素及其之間的抽象關(guān)系11謝謝欣賞2019數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)元素及其之間的抽象關(guān)系集合線狀結(jié)構(gòu)樹狀結(jié)構(gòu)圖或網(wǎng)狀結(jié)構(gòu)12謝謝欣賞2019-9-5數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)元素及其之間的抽象關(guān)系12謝謝欣賞2019數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)元素及其之間的抽象關(guān)系集合線狀結(jié)構(gòu)樹狀結(jié)構(gòu)圖或網(wǎng)狀結(jié)構(gòu)13謝謝欣賞2019-9-5數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)元素及其之間的抽象關(guān)系13謝謝欣賞2019數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)元素及其之間的抽象關(guān)系集合線狀結(jié)構(gòu)樹狀結(jié)構(gòu)圖或網(wǎng)狀結(jié)構(gòu)14115437121768圖結(jié)構(gòu)網(wǎng)狀結(jié)構(gòu)謝謝欣賞2019-9-5數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)元素及其之間的抽象關(guān)系1411543712數(shù)據(jù)的存儲結(jié)構(gòu)數(shù)據(jù)及其邏輯結(jié)構(gòu)在計算機中的表示，實質(zhì)上是存儲器的分配順序存儲結(jié)構(gòu)鏈接存儲結(jié)構(gòu)索引存儲結(jié)構(gòu)散列存儲結(jié)構(gòu)15謝謝欣賞2019-9-5數(shù)據(jù)的存儲結(jié)構(gòu)數(shù)據(jù)及其邏輯結(jié)構(gòu)在計算機中的表示，實質(zhì)上是存儲數(shù)據(jù)的存儲結(jié)構(gòu)數(shù)據(jù)及其邏輯結(jié)構(gòu)在計算機中的表示，實質(zhì)上是存儲器的分配順序存儲結(jié)構(gòu)鏈接存儲結(jié)構(gòu)索引存儲結(jié)構(gòu)散列存儲結(jié)構(gòu)16存儲（bat,cat,eat）起始地址bat…cateat…謝謝欣賞2019-9-5數(shù)據(jù)的存儲結(jié)構(gòu)數(shù)據(jù)及其邏輯結(jié)構(gòu)在計算機中的表示，實質(zhì)上是存儲數(shù)據(jù)的存儲結(jié)構(gòu)數(shù)據(jù)及其邏輯結(jié)構(gòu)在計算機中的表示，實質(zhì)上是存儲器的分配順序存儲結(jié)構(gòu)鏈接存儲結(jié)構(gòu)索引存儲結(jié)構(gòu)散列存儲結(jié)構(gòu)17存儲（bat,cat,eat）bat0200cat0320…0320eat∧……02000256謝謝欣賞2019-9-5數(shù)據(jù)的存儲結(jié)構(gòu)數(shù)據(jù)及其邏輯結(jié)構(gòu)在計算機中的表示，實質(zhì)上是存儲數(shù)據(jù)的存儲結(jié)構(gòu)數(shù)據(jù)及其邏輯結(jié)構(gòu)在計算機中的表示，實質(zhì)上是存儲器的分配順序存儲結(jié)構(gòu)鏈接存儲結(jié)構(gòu)索引存儲結(jié)構(gòu)散列存儲結(jié)構(gòu)18文件名1地址1文件2文件名2地址2文件名3地址3文件3文件1地址2地址3地址1??????謝謝欣賞2019-9-5數(shù)據(jù)的存儲結(jié)構(gòu)數(shù)據(jù)及其邏輯結(jié)構(gòu)在計算機中的表示，實質(zhì)上是存儲數(shù)據(jù)的存儲結(jié)構(gòu)數(shù)據(jù)及其邏輯結(jié)構(gòu)在計算機中的表示，實質(zhì)上是存儲器的分配順序存儲結(jié)構(gòu)鏈接存儲結(jié)構(gòu)索引存儲結(jié)構(gòu)散列存儲結(jié)構(gòu)19｛100，400，500，800，900｝129834567100400500800900hash(key)=key/100謝謝欣賞2019-9-5數(shù)據(jù)的存儲結(jié)構(gòu)數(shù)據(jù)及其邏輯結(jié)構(gòu)在計算機中的表示，實質(zhì)上是存儲抽象數(shù)據(jù)類型數(shù)據(jù)類型：一組值的集合以及一組相關(guān)的操作基本數(shù)據(jù)類型C語言中int、float、double+、-、*、/、%、<、>、<=、>=、==、!=、=構(gòu)造數(shù)據(jù)類型20Typedefstruct{doubledata[100];intlength;}DataList;謝謝欣賞2019-9-5抽象數(shù)據(jù)類型數(shù)據(jù)類型：一組值的集合以及一組相關(guān)的操作20Ty抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型：由用戶定義，表示問題的數(shù)據(jù)模型由其他數(shù)據(jù)類型組成，并包括一組相關(guān)操作三大特征信息隱藏、數(shù)據(jù)封裝、使用與實現(xiàn)分離21classCircle{//對象:幾何圓floatr;//圓的半徑public:Circle(floatr);//構(gòu)造函數(shù)，創(chuàng)建一個半徑為r的對象實例floatCircumference();//返回該實例的周長floatArea();//返回該實例的面積};謝謝欣賞2019-9-5抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型：由用戶定義，表示問題的數(shù)據(jù)模型21抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型三大特征信息隱藏：把所有數(shù)據(jù)和操作分為公有和私有，可減少接口復(fù)雜性，從而減少出錯機會。數(shù)據(jù)封裝：把數(shù)據(jù)和操作封裝在一起，從語義上更加完整。使用與實現(xiàn)相分離：使用者只能通過接口上的操作來訪問數(shù)據(jù)，一旦將來修改數(shù)據(jù)結(jié)構(gòu)，可以使得修改局部化，提高系統(tǒng)靈活性。22謝謝欣賞2019-9-5抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型三大特征22謝謝欣賞2019-9-5抽象數(shù)據(jù)類型作業(yè)：二維向量的抽象數(shù)據(jù)類型數(shù)據(jù)類型操作：加、減、點乘、叉乘23謝謝欣賞2019-9-5抽象數(shù)據(jù)類型作業(yè)：二維向量的抽象數(shù)據(jù)類型23謝謝欣賞2019算法定義是對特定問題求解步驟的一種描述，是指令的有限序列。算法五大特性輸入：有0個或多個輸入輸出：有1個或多個輸出有限性：算法有限步結(jié)束，指令有限時間完成確定性：每條指令有確切含義可行性：每個運算可由計算機有限條指令完成24謝謝欣賞2019-9-5算法定義是對特定問題求解步驟的一種描述，是指令的有限序列。2算法定義算法舉例“百錢買百雞”問題：公雞每只5錢，母雞每只3錢，小雞3只1錢，100錢買100只雞，問各種雞可買多少只?令公雞母雞小雞分別為x,y,z只25例：for(x=0;x<=100;x++){ for(y=0;y<=100;y++){ for(z=0;z<=100;z++){if(x+y+z==100&&5*x+3*y+z/3==100&&z%3==0){printf(“%d,%d,%d”,x,y,z);}}}謝謝欣賞2019-9-5算法定義算法舉例25例：for(x=0;x<=100;x++算法定義算法舉例歐幾里德算法——輾轉(zhuǎn)相除法求兩個自然數(shù)m和n的最大公約數(shù)26輸入:m,n輸出:m和n的最大公約數(shù)r=m%n;循環(huán)直到r等于0{m=n;n=r;r=m%n;}輸出n謝謝欣賞2019-9-5算法定義算法舉例26輸入:m,n謝謝欣賞2019-9-5算法性能分析與度量算法效率的評價方法：事后統(tǒng)計將算法實現(xiàn)，統(tǒng)計其時間和空間開銷事前分析對算法所消耗時間和空間資源的一種估算方法算法效率的分析時間復(fù)雜度空間復(fù)雜度27time(&start); algorithm();time(&stop); runTime=stop-start;謝謝欣賞2019-9-5算法性能分析與度量算法效率的評價方法：27time(&st算法性能分析與度量算法的時間復(fù)雜度28算法的運行時間=每條語句執(zhí)行時間之和執(zhí)行次數(shù)×執(zhí)行一次的時間例：for(i=0;i<n;i++){ for(j=0;j<n;j++){ c[i][j]=0;for(k=0;k<n;k++){c[i][j]=c[i][j]+a[i][k]*b[k][j];}}}指令系統(tǒng)、代碼質(zhì)量有關(guān)每條語句執(zhí)行次數(shù)之和基本語句執(zhí)行次數(shù)謝謝欣賞2019-9-5算法性能分析與度量算法的時間復(fù)雜度28算法的運行時間=每算法性能分析與度量算法的時間復(fù)雜度算法的運行時間可表示為基本語句執(zhí)行次數(shù)，它是問題規(guī)模的一個函數(shù)稱這個函數(shù)的漸進階為算法的時間復(fù)雜度29問題規(guī)模：n基本語句：c[i][j]=0c[i][j]=c[i][j]+a[i][k]*b[k][j]時間復(fù)雜度:O(n3)例：for(i=0;i<n;i++){ for(j=0;j<n;j++){ c[i][j]=0;for(k=0;k<n;k++){c[i][j]=c[i][j]+a[i][k]*b[k][j];}}}謝謝欣賞2019-9-5算法性能分析與度量算法的時間復(fù)雜度29問題規(guī)模：n例：for算法性能分析與度量算法的時間復(fù)雜度大O表示法：若存在兩個正的常數(shù)c和n0，對于任意n≥n0，都有T(n)≤c×f(n)，則稱T(n)=O(f(n))30n0問題規(guī)模n執(zhí)行次數(shù)n0之前的情況無關(guān)緊要T(n)c×f(n)表示當問題規(guī)模充分大時在漸進意義下的階謝謝欣賞2019-9-5算法性能分析與度量算法的時間復(fù)雜度30n0問題規(guī)模n執(zhí)行次數(shù)算法性能分析與度量算法的時間復(fù)雜度大O表示法：若存在兩個正的常數(shù)c和n0，對于任意n≥n0，都有T(n)≤c×f(n)，則稱T(n)=O(f(n))例1：T(n)=3n+2當n≥2時，3n+2≤3n+n=4n因此T(n)=O(n)31謝謝欣賞2019-9-5算法性能分析與度量算法的時間復(fù)雜度31謝謝欣賞2019-9-算法性能分析與度量算法的時間復(fù)雜度大O表示法：若存在兩個正的常數(shù)c和n0，對于任意n≥n0，都有T(n)≤c×f(n)，則稱T(n)=O(f(n))例2：T(n)=10n2+4n+2當n≥2時，10n2+4n+2≤10n2+5n又有當n≥5時，10n2+5n≤10n2+n2=11n2因此T(n)=O(n2)32謝謝欣賞2019-9-5算法性能分析與度量算法的時間復(fù)雜度32謝謝欣賞2019-9-算法性能分析與度量算法的時間復(fù)雜度大O表示法：若存在兩個正的常數(shù)c和n0，對于任意n≥n0，都有T(n)≤c×f(n)，則稱T(n)=O(f(n))作業(yè)：求解T(n)=amnm+am-1nm-1+???a2n2+a1n+a0，并給出證明過程33謝謝欣賞2019-9-5算法性能分析與度量算法的時間復(fù)雜度33謝謝欣賞2019-9-算法性能分析與度量算法的時間復(fù)雜度T(n)=O(f(n))若存在兩個正的常數(shù)c和n0，對于任意n≥n0，都有T(n)≤c×f(n)，則稱T(n)=O(f(n))給出算法復(fù)雜度的上界，不可能比c*f(n)更大例：T(n)=6*2n+n2當n≥4時，6*2n+n2≤6*2n+2n=7*2n因此T(n)=O(2n)34謝謝欣賞2019-9-5算法性能分析與度量算法的時間復(fù)雜度34謝謝欣賞2019-9-算法性能分析與度量算法的時間復(fù)雜度T(n)=Ω(f(n))若存在c>0，和正整數(shù)n0≥1，使得當n≥n0時，有T(n)≥c*f(n)成立。給出算法復(fù)雜度的下界，不可能比c*f(n)更小例：T(n)=3n3+2n2，取c=3，n0=1，f(n)=n3，則當n≥n0(=1)時，有3n3+2n2≥3n3，∴T(n)=Ω(n3)35謝謝欣賞2019-9-5算法性能分析與度量算法的時間復(fù)雜度35謝謝欣賞2019-9-算法性能分析與度量算法的時間復(fù)雜度T(n)=

(f(n