《青島理工大學數(shù)據(jù)結構課件第一章.ppt》由會員分享，可在線閱讀，更多相關《青島理工大學數(shù)據(jù)結構課件第一章.ppt（38頁珍藏版）》請在裝配圖網(wǎng)上搜索。
1、數(shù)據(jù)結構,主講：計算機學院 張艷 Email:zhangyan1228_ Telephone:15963299081 數(shù)據(jù)結構網(wǎng)上課堂：http://221.0.174.198:58888/datastructure,2,,教 材：嚴蔚敏等，數(shù)據(jù)結構（C語言版），清華大學出版社，2007（配題集） 參考書： 1 殷人昆等，數(shù)據(jù)結構（用面向對象方法與C++描述），清華大學出版社，1999年7月。 2 殷人昆等，數(shù)據(jù)結構習題解析，清華大學出版社，2002年4月。 3 李春保，數(shù)據(jù)結構習題與解析（C語言篇），清華大學出版社，2001年1月。 4 丁寶康等，數(shù)據(jù)結構自學考試指導，清華大學出版社， 20
2、01年5月。,3,主要內容和學習要點,1.1 什么是數(shù)據(jù)結構 1.2 數(shù)據(jù)結構的基本概念和術語 熟悉各名詞、術語如數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項、數(shù)據(jù)對象、數(shù)據(jù)結構的含義，掌握基本概念，特別是數(shù)據(jù)的邏輯結構和存儲結構之間的關系。 1.3 抽象數(shù)據(jù)類型的表示和實現(xiàn) 了解抽象數(shù)據(jù)類型的定義、表示和實現(xiàn)方法。 1.4 算法和算法分析 理解算法四個要素的確切含義。掌握計算語句頻度和估算算法時間復雜度的方法。,4,計算機是一門研究用計算機進行信息表示和處理的科學。這里面涉及到兩個問題： 信息的表示 信息的處理 而信息的表示和處理又直接關系到處理信息的程序的效率。隨著計算機的普及，信息量的
3、增加，信息范圍的拓寬，使許多系統(tǒng)程序和應用程序的規(guī)模很大，結構又相當復雜。因此，為了編寫出一個“好”的程序，必須分析待處理的對象的特征及各對象之間存在的關系，這就是數(shù)據(jù)結構這門課所要研究的問題。,引言,5,Q1 ： 什么是數(shù)據(jù)結構？ Q2 ：學習數(shù)據(jù)結構有什么用？ Q3 ：數(shù)據(jù)結構涵蓋的主要內容？,討論：,,1.1 什么是數(shù)據(jù)結構,6,針對非數(shù)值計算的程序設計問題，研究計算機的操作對象以及它們之間的關系和操作。 是介于數(shù)學、計算機硬件和計算機軟件三者之間的一門核心課程。,數(shù)據(jù)結構的地位,7,是相互之間存在一種或多種特定關系的數(shù)據(jù)元素的集合，表示為：,,（數(shù)值或非數(shù)值）,Data_Structu
4、re=（D, R）,或是指同一數(shù)據(jù)元素類型中各元素之間存在的關系。,,元素有限集,,關系有限集,,Q1:什么是數(shù)據(jù)結構,8,著名計算機科學家、Pascal語言發(fā)明者N.沃思教授提出： 程序 = 算法 + 數(shù)據(jù)結構 也就是說，計算機按照程序所描述的算法對某種結構的數(shù)據(jù)進行加工處理。 數(shù)據(jù)結構定義: 是一門研究非數(shù)值計算的程序設計問題中計算機的操作對象以及它們之間的關系和操作等等的學科。 非數(shù)值計算的程序設計問題：信息自動檢索、計算機游戲、多岔路口交通燈的管理。,什么是數(shù)據(jù)結構,按書名,按作者名,按分類號,索引表,例1 書目自動檢索系統(tǒng),書目文件,例2 人機對奕問題,,,,,,
5、,,,,例3 多叉路口交通燈管理問題,,,,,,,,,,,,,,,12,數(shù)據(jù)（data)：所有能輸入到計算機中去的描述客觀事物的符號 是計算機處理的信息的某種特定的符號表示形式。它包括數(shù)值 型數(shù)據(jù)和非數(shù)值型數(shù)據(jù)（如字符、圖象、聲音）。 數(shù)據(jù)元素（data element）：數(shù)據(jù)的基本單位，也稱結點（node） 或記錄（record）。 數(shù)據(jù)項(data item):有獨立含義的數(shù)據(jù)最小單位，也稱域(field)。 數(shù)據(jù)對象(data object)：性質相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的 一個子集。,1.2 數(shù)據(jù)結構的基本概念和術語,三者之間的關系：數(shù)據(jù) 對象 數(shù)據(jù)元素 數(shù)據(jù)項,例：班級通訊錄
6、個人記錄 姓名、年齡,13,,數(shù)據(jù)對象(data object)：性質相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的 一個子集。 如大寫字母字符數(shù)據(jù)對象是集合 C=A,B,C,，Z ； 整數(shù)數(shù)據(jù)對象是集合 N = 0, 1, 2, 數(shù)據(jù)結構（data structure)：數(shù)據(jù)元素和數(shù)據(jù)元素關系的集合。,Data_Structure=（D, R）,14,答：計算機內的數(shù)值運算依靠方程式，而非數(shù)值運算（如表、樹、圖等）則要依靠數(shù)據(jù)結構。 這是一門研究非數(shù)值計算的程序設計問題中計算機的操作對象以及它們之間的關系和操作等等的學科。,程序設計實質好算法好結構,同樣的數(shù)據(jù)對象，用不同的數(shù)據(jù)結構來表示，運算效率可能
7、有明顯的差異。,Q2：學習數(shù)據(jù)結構有什么用？,15,,,數(shù)據(jù)的邏輯結構,數(shù)據(jù)的存儲結構,數(shù)據(jù)的運算：檢索、排序、插入、刪除、修改等,,,,,線性結構,非線性結構,順序結構,鏈式結構,線性表,棧,隊,樹形結構,圖形結構,Q3:數(shù)據(jù)結構研究的內容：,索引結構,散列結構,16,集合結構： 僅同屬一個集合 線性結構: 一對一（1:1) 樹 形結 構: 一對多（1:n) 圖 形 結 構: 多對多 (m:n),非線性,線 性,邏輯結構可細分為4類：,指數(shù)據(jù)元素之間的邏輯關系。即從邏輯關系上描述數(shù)據(jù)，它與數(shù)據(jù)的存儲無關，是獨立于計算機的。,解釋1：什么叫數(shù)據(jù)的邏輯結構？,17,（1） S=(D, R)
8、 D= a, b, c, d, e, f R=(a,e), (b,c), (c,a), (e,f), (f,d),解： 上述表達式可用圖形表示為：,b c a e f d,此結構為線性的。,例：用圖形表示下列數(shù)據(jù)結構，并指出它們是屬于線性結構還是非線性結構。,,,,,,18,該結構是非線性的。,解：上述表達式可用圖形表示為：,（2） S=(D, R) D=di | 1i5 R=(di , dj ), i
9、儲器內的表示（或映像）。它依賴于計算機。,解釋2：什么叫數(shù)據(jù)的物理結構？,數(shù)據(jù)的邏輯結構與存儲結構密切相關 算法設計 邏輯結構 算法實現(xiàn) 存儲結構,,,還有索引存儲結構和散列存儲結構,1536,元素2,,,,,,1400,元素1,,,,,,1346,元素3,,,,,,,元素4,,,,,,1345,h,鏈式存儲 結構,,h,22,答：在數(shù)據(jù)的邏輯結構上定義的操作算法。 它在數(shù)據(jù)的存儲結構上實現(xiàn)。,最常用的數(shù)據(jù)運算有 5 種：,插入、刪除、修改、查找、排序,解釋3：什么是數(shù)據(jù)的運算？,23,Q1： 數(shù)據(jù)類型與抽象數(shù)據(jù)類型的區(qū)別？ Q2: 抽象數(shù)據(jù)類型如何定義？ Q3: 抽象數(shù)據(jù)類型如何表示和實
10、現(xiàn)？,討論：,抽象數(shù)據(jù)類型和偽碼是學習數(shù)據(jù)結構的工具,1.3 抽象數(shù)據(jù)類型,24,數(shù)據(jù)類型（data type）： 一個值的集合和定義在這個集合上的一組操作的總稱。如C語言中的整型（短整型2個字節(jié)表示范圍-3276832767、長整型4個字節(jié)）、浮點型（4個字節(jié)，帶小數(shù)點）、字符型（1個字節(jié)，用單引號表示，如a）、雙精度型（8個字節(jié)） 抽象數(shù)據(jù)類型(ADT: Abstract Data Type)： 由用戶定義，用以表示應用問題的數(shù)據(jù)模型。 由基本的數(shù)據(jù)類型組成, 并包括一組相關的服務（或稱操作）。 區(qū)別：ADT與數(shù)據(jù)類型實質上是一個概念，但其特征是使用與實現(xiàn)分離，實行封裝和信息隱藏。,
11、Q1： 數(shù)據(jù)類型與抽象數(shù)據(jù)類型的區(qū)別？,25,Q2 抽象數(shù)據(jù)類型如何定義？,抽象數(shù)據(jù)類型可以用以下的三元組來表示： ADT = （D，S，P） 數(shù)據(jù)對象 D上的關系集 D上的操作集,ADT抽象數(shù)據(jù)類型名 數(shù)據(jù)對象： 數(shù)據(jù)關系： 基本操作 ： ADT抽象數(shù)據(jù)類型名,ADT常用定義格式,,,,26,抽象數(shù)據(jù)類型可以通過固有的數(shù)據(jù)類型（如整型、實型、字符型等）來表示和實現(xiàn)。,注1 ：它有些類似C語言中的結構（struct)類型，但增加了相關的服務（或操作） 。 注2 ：教材中用類C語言（介于偽碼和C語言之間）作為描述工具。,但上機時要用具體語言實現(xiàn)，如C或C++等,Q3
12、 抽象數(shù)據(jù)類型如何表示和實現(xiàn)？,27,ADT Complex 數(shù)據(jù)對象:De1,e2e1,e2RealSet 數(shù)據(jù)關系:R | e1是實數(shù)部分,e2 是虛數(shù)部分 基本操作： InitComplex( i
13、)=2n2+n 所以該程序段的時間復雜度 T(n)=(n+1)+n+(2n2+2n)+(2n2+n)=4n2+5n+1=O(n2),實際上,可以用算法中基本操作重復執(zhí)行的頻度作為度量. 被視為基本操作的一般是最深層循環(huán)內的語句,算法的時間復雜度的計算,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： 設n為正整數(shù), 分析下列程序段中內層循環(huán)語句的程序步數(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,算法的存儲量包括: 1輸入數(shù)據(jù)所占空間; 2程序本身所占空間； 3輔助變量所占空間。 若輸入數(shù)據(jù)所占空間只取決與問題本身，和算法無關，則只需要分析除輸入和程序之外的額外空間。 若所需額外空間相對于輸入數(shù)據(jù)量來說是常數(shù)，則稱此算法為原地工作。若所需存儲量依賴于特定的輸入，則通常按最壞情況考慮。 空間復雜度是對一個算法在運行過程中臨時占用存儲空間大小的度量，記作：S(n) = O(g(n))表示隨著問題規(guī)模n的增大，算法運行所需存儲量的增長率與g(n)的增長率相同。,算法的空間復雜度,37,注意：算法的所有性能之間都存在著或多或少的相互影響，因此，當設計一個算法，特別是大型算法時，要綜合考慮算法的各項性能、算法的使用頻率、算法處理的數(shù)據(jù)量的大小、算法描述語言的特性及算法運行的機器系統(tǒng)環(huán)境等各方面因素，才能設計出比較好的算法。,38,作業(yè),習題集 1.1、1.2、1.3、1.8、1.9、1.10,
青島理工大學數(shù)據(jù)結構課件第一章.ppt
