青島理工大學(xué)數(shù)據(jù)結(jié)構(gòu)課件第一章.ppt

《青島理工大學(xué)數(shù)據(jù)結(jié)構(gòu)課件第一章.ppt》由會(huì)員分享，可在線閱讀，更多相關(guān)《青島理工大學(xué)數(shù)據(jù)結(jié)構(gòu)課件第一章.ppt（38頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、數(shù)據(jù)結(jié)構(gòu),主講：計(jì)算機(jī)學(xué)院 張艷 Email:zhangyan1228_ Telephone:15963299081 數(shù)據(jù)結(jié)構(gòu)網(wǎng)上課堂：http://221.0.174.198:58888/datastructure,2,,教 材：嚴(yán)蔚敏等，數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版），清華大學(xué)出版社，2007（配題集） 參考書： 1 殷人昆等，數(shù)據(jù)結(jié)構(gòu)（用面向?qū)ο蠓椒ㄅcC++描述），清華大學(xué)出版社，1999年7月。 2 殷人昆等，數(shù)據(jù)結(jié)構(gòu)習(xí)題解析，清華大學(xué)出版社，2002年4月。 3 李春保，數(shù)據(jù)結(jié)構(gòu)習(xí)題與解析（C語(yǔ)言篇），清華大學(xué)出版社，2001年1月。 4 丁寶康等，數(shù)據(jù)結(jié)構(gòu)自學(xué)考試指導(dǎo)，清華大學(xué)出版社， 20

2、01年5月。,3,主要內(nèi)容和學(xué)習(xí)要點(diǎn),1.1 什么是數(shù)據(jù)結(jié)構(gòu) 1.2 數(shù)據(jù)結(jié)構(gòu)的基本概念和術(shù)語(yǔ) 熟悉各名詞、術(shù)語(yǔ)如數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項(xiàng)、數(shù)據(jù)對(duì)象、數(shù)據(jù)結(jié)構(gòu)的含義，掌握基本概念，特別是數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)之間的關(guān)系。 1.3 抽象數(shù)據(jù)類型的表示和實(shí)現(xiàn) 了解抽象數(shù)據(jù)類型的定義、表示和實(shí)現(xiàn)方法。 1.4 算法和算法分析 理解算法四個(gè)要素的確切含義。掌握計(jì)算語(yǔ)句頻度和估算算法時(shí)間復(fù)雜度的方法。,4,計(jì)算機(jī)是一門研究用計(jì)算機(jī)進(jìn)行信息表示和處理的科學(xué)。這里面涉及到兩個(gè)問題： 信息的表示 信息的處理 而信息的表示和處理又直接關(guān)系到處理信息的程序的效率。隨著計(jì)算機(jī)的普及，信息量的

3、增加，信息范圍的拓寬，使許多系統(tǒng)程序和應(yīng)用程序的規(guī)模很大，結(jié)構(gòu)又相當(dāng)復(fù)雜。因此，為了編寫出一個(gè)“好”的程序，必須分析待處理的對(duì)象的特征及各對(duì)象之間存在的關(guān)系，這就是數(shù)據(jù)結(jié)構(gòu)這門課所要研究的問題。,引言,5,Q1 ： 什么是數(shù)據(jù)結(jié)構(gòu)？ Q2 ：學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)有什么用？ Q3 ：數(shù)據(jù)結(jié)構(gòu)涵蓋的主要內(nèi)容？,討論：,,1.1 什么是數(shù)據(jù)結(jié)構(gòu),6,針對(duì)非數(shù)值計(jì)算的程序設(shè)計(jì)問題，研究計(jì)算機(jī)的操作對(duì)象以及它們之間的關(guān)系和操作。 是介于數(shù)學(xué)、計(jì)算機(jī)硬件和計(jì)算機(jī)軟件三者之間的一門核心課程。,數(shù)據(jù)結(jié)構(gòu)的地位,7,是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合，表示為：,,（數(shù)值或非數(shù)值）,Data_Structu

4、re=（D, R）,或是指同一數(shù)據(jù)元素類型中各元素之間存在的關(guān)系。,,元素有限集,,關(guān)系有限集,,Q1:什么是數(shù)據(jù)結(jié)構(gòu),8,著名計(jì)算機(jī)科學(xué)家、Pascal語(yǔ)言發(fā)明者N.沃思教授提出： 程序 = 算法 + 數(shù)據(jù)結(jié)構(gòu) 也就是說，計(jì)算機(jī)按照程序所描述的算法對(duì)某種結(jié)構(gòu)的數(shù)據(jù)進(jìn)行加工處理。 數(shù)據(jù)結(jié)構(gòu)定義: 是一門研究非數(shù)值計(jì)算的程序設(shè)計(jì)問題中計(jì)算機(jī)的操作對(duì)象以及它們之間的關(guān)系和操作等等的學(xué)科。 非數(shù)值計(jì)算的程序設(shè)計(jì)問題：信息自動(dòng)檢索、計(jì)算機(jī)游戲、多岔路口交通燈的管理。,什么是數(shù)據(jù)結(jié)構(gòu),按書名,按作者名,按分類號(hào),索引表,例1 書目自動(dòng)檢索系統(tǒng),書目文件,例2 人機(jī)對(duì)奕問題,,,,,,

5、,,,,例3 多叉路口交通燈管理問題,,,,,,,,,,,,,,,12,數(shù)據(jù)（data)：所有能輸入到計(jì)算機(jī)中去的描述客觀事物的符號(hào) 是計(jì)算機(jī)處理的信息的某種特定的符號(hào)表示形式。它包括數(shù)值 型數(shù)據(jù)和非數(shù)值型數(shù)據(jù)（如字符、圖象、聲音）。 數(shù)據(jù)元素（data element）：數(shù)據(jù)的基本單位，也稱結(jié)點(diǎn)（node） 或記錄（record）。 數(shù)據(jù)項(xiàng)(data item):有獨(dú)立含義的數(shù)據(jù)最小單位，也稱域(field)。 數(shù)據(jù)對(duì)象(data object)：性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的 一個(gè)子集。,1.2 數(shù)據(jù)結(jié)構(gòu)的基本概念和術(shù)語(yǔ),三者之間的關(guān)系：數(shù)據(jù) 對(duì)象 數(shù)據(jù)元素 數(shù)據(jù)項(xiàng),例：班級(jí)通訊錄

6、個(gè)人記錄 姓名、年齡,13,,數(shù)據(jù)對(duì)象(data object)：性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的 一個(gè)子集。 如大寫字母字符數(shù)據(jù)對(duì)象是集合 C=A,B,C,，Z ； 整數(shù)數(shù)據(jù)對(duì)象是集合 N = 0, 1, 2, 數(shù)據(jù)結(jié)構(gòu)（data structure)：數(shù)據(jù)元素和數(shù)據(jù)元素關(guān)系的集合。,Data_Structure=（D, R）,14,答：計(jì)算機(jī)內(nèi)的數(shù)值運(yùn)算依靠方程式，而非數(shù)值運(yùn)算（如表、樹、圖等）則要依靠數(shù)據(jù)結(jié)構(gòu)。 這是一門研究非數(shù)值計(jì)算的程序設(shè)計(jì)問題中計(jì)算機(jī)的操作對(duì)象以及它們之間的關(guān)系和操作等等的學(xué)科。,程序設(shè)計(jì)實(shí)質(zhì)好算法好結(jié)構(gòu),同樣的數(shù)據(jù)對(duì)象，用不同的數(shù)據(jù)結(jié)構(gòu)來表示，運(yùn)算效率可能

7、有明顯的差異。,Q2：學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)有什么用？,15,,,數(shù)據(jù)的邏輯結(jié)構(gòu),數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu),數(shù)據(jù)的運(yùn)算：檢索、排序、插入、刪除、修改等,,,,,線性結(jié)構(gòu),非線性結(jié)構(gòu),順序結(jié)構(gòu),鏈?zhǔn)浇Y(jié)構(gòu),線性表,棧,隊(duì),樹形結(jié)構(gòu),圖形結(jié)構(gòu),Q3:數(shù)據(jù)結(jié)構(gòu)研究的內(nèi)容：,索引結(jié)構(gòu),散列結(jié)構(gòu),16,集合結(jié)構(gòu)： 僅同屬一個(gè)集合 線性結(jié)構(gòu): 一對(duì)一（1:1) 樹 形結(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ǔ)無關(guān)，是獨(dú)立于計(jì)算機(jī)的。,解釋1：什么叫數(shù)據(jù)的邏輯結(jié)構(gòu)？,17,（1） S=(D, R)

8、 D= a, b, c, d, e, f R=(a,e), (b,c), (c,a), (e,f), (f,d),解： 上述表達(dá)式可用圖形表示為：,b c a e f d,此結(jié)構(gòu)為線性的。,例：用圖形表示下列數(shù)據(jù)結(jié)構(gòu)，并指出它們是屬于線性結(jié)構(gòu)還是非線性結(jié)構(gòu)。,,,,,,18,該結(jié)構(gòu)是非線性的。,解：上述表達(dá)式可用圖形表示為：,（2） S=(D, R) D=di | 1i5 R=(di , dj ), i

9、儲(chǔ)器內(nèi)的表示（或映像）。它依賴于計(jì)算機(jī)。,解釋2：什么叫數(shù)據(jù)的物理結(jié)構(gòu)？,數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)密切相關(guān) 算法設(shè)計(jì) 邏輯結(jié)構(gòu) 算法實(shí)現(xiàn) 存儲(chǔ)結(jié)構(gòu),,,還有索引存儲(chǔ)結(jié)構(gòu)和散列存儲(chǔ)結(jié)構(gòu),1536,元素2,,,,,,1400,元素1,,,,,,1346,元素3,,,,,,,元素4,,,,,,1345,h,鏈?zhǔn)酱鎯?chǔ) 結(jié)構(gòu),,h,22,答：在數(shù)據(jù)的邏輯結(jié)構(gòu)上定義的操作算法。 它在數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)。,最常用的數(shù)據(jù)運(yùn)算有 5 種：,插入、刪除、修改、查找、排序,解釋3：什么是數(shù)據(jù)的運(yùn)算？,23,Q1： 數(shù)據(jù)類型與抽象數(shù)據(jù)類型的區(qū)別？ Q2: 抽象數(shù)據(jù)類型如何定義？ Q3: 抽象數(shù)據(jù)類型如何表示和實(shí)

10、現(xiàn)？,討論：,抽象數(shù)據(jù)類型和偽碼是學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的工具,1.3 抽象數(shù)據(jù)類型,24,數(shù)據(jù)類型（data type）： 一個(gè)值的集合和定義在這個(gè)集合上的一組操作的總稱。如C語(yǔ)言中的整型（短整型2個(gè)字節(jié)表示范圍-3276832767、長(zhǎng)整型4個(gè)字節(jié)）、浮點(diǎn)型（4個(gè)字節(jié)，帶小數(shù)點(diǎn)）、字符型（1個(gè)字節(jié)，用單引號(hào)表示，如a）、雙精度型（8個(gè)字節(jié)） 抽象數(shù)據(jù)類型(ADT: Abstract Data Type)： 由用戶定義，用以表示應(yīng)用問題的數(shù)據(jù)模型。 由基本的數(shù)據(jù)類型組成, 并包括一組相關(guān)的服務(wù)（或稱操作）。 區(qū)別：ADT與數(shù)據(jù)類型實(shí)質(zhì)上是一個(gè)概念，但其特征是使用與實(shí)現(xiàn)分離，實(shí)行封裝和信息隱藏。,

11、Q1： 數(shù)據(jù)類型與抽象數(shù)據(jù)類型的區(qū)別？,25,Q2 抽象數(shù)據(jù)類型如何定義？,抽象數(shù)據(jù)類型可以用以下的三元組來表示： ADT = （D，S，P） 數(shù)據(jù)對(duì)象 D上的關(guān)系集 D上的操作集,ADT抽象數(shù)據(jù)類型名 數(shù)據(jù)對(duì)象： 數(shù)據(jù)關(guān)系： 基本操作 ： ADT抽象數(shù)據(jù)類型名,ADT常用定義格式,,,,26,抽象數(shù)據(jù)類型可以通過固有的數(shù)據(jù)類型（如整型、實(shí)型、字符型等）來表示和實(shí)現(xiàn)。,注1 ：它有些類似C語(yǔ)言中的結(jié)構(gòu)（struct)類型，但增加了相關(guān)的服務(wù)（或操作） 。 注2 ：教材中用類C語(yǔ)言（介于偽碼和C語(yǔ)言之間）作為描述工具。,但上機(jī)時(shí)要用具體語(yǔ)言實(shí)現(xiàn)，如C或C++等,Q3

12、 抽象數(shù)據(jù)類型如何表示和實(shí)現(xiàn)？,27,ADT Complex 數(shù)據(jù)對(duì)象:De1,e2e1,e2RealSet 數(shù)據(jù)關(guān)系:R | e1是實(shí)數(shù)部分,e2 是虛數(shù)部分 基本操作： InitComplex( i

13、)=2n2+n 所以該程序段的時(shí)間復(fù)雜度 T(n)=(n+1)+n+(2n2+2n)+(2n2+n)=4n2+5n+1=O(n2),實(shí)際上,可以用算法中基本操作重復(fù)執(zhí)行的頻度作為度量. 被視為基本操作的一般是最深層循環(huán)內(nèi)的語(yǔ)句,算法的時(shí)間復(fù)雜度的計(jì)算,34,,,例2：矩陣相乘 for(i=1;i<=n;i++) for(j=1;j<=n;j++) cij=0; for(k=1;k<=n;k++) cij=cij+aik*bkj; ,T(n)=O(n3),例3： 設(shè)n為正整數(shù), 分析下列程序段中內(nèi)層循環(huán)語(yǔ)句的程序步數(shù)。,,,for(i=1;i<=n;i++) for(j=1;j<=i

14、;j++) for(k=1;k<=j;k++) x+=y;,T(n)=O(n3),36,算法的存儲(chǔ)量包括: 1輸入數(shù)據(jù)所占空間; 2程序本身所占空間； 3輔助變量所占空間。 若輸入數(shù)據(jù)所占空間只取決與問題本身，和算法無關(guān)，則只需要分析除輸入和程序之外的額外空間。 若所需額外空間相對(duì)于輸入數(shù)據(jù)量來說是常數(shù)，則稱此算法為原地工作。若所需存儲(chǔ)量依賴于特定的輸入，則通常按最壞情況考慮。 空間復(fù)雜度是對(duì)一個(gè)算法在運(yùn)行過程中臨時(shí)占用存儲(chǔ)空間大小的度量，記作：S(n) = O(g(n))表示隨著問題規(guī)模n的增大，算法運(yùn)行所需存儲(chǔ)量的增長(zhǎng)率與g(n)的增長(zhǎng)率相同。,算法的空間復(fù)雜度,37,注意：算法的所有性能之間都存在著或多或少的相互影響，因此，當(dāng)設(shè)計(jì)一個(gè)算法，特別是大型算法時(shí)，要綜合考慮算法的各項(xiàng)性能、算法的使用頻率、算法處理的數(shù)據(jù)量的大小、算法描述語(yǔ)言的特性及算法運(yùn)行的機(jī)器系統(tǒng)環(huán)境等各方面因素，才能設(shè)計(jì)出比較好的算法。,38,作業(yè),習(xí)題集 1.1、1.2、1.3、1.8、1.9、1.10,