數據結構第一章概論.ppt

1,數據結構,C語言版,2, 教材 數據結構 （ C語言版） 嚴蔚敏 吳偉民 清華大學出版社, 參考教材 1 數據結構 （ C語言版） 劉清 王瓊 電子工業(yè)出版社 2 數據結構題集 （ C語言版） 嚴蔚敏 吳偉民 清華大學出版社,3,教學內容（總學時64, 其中有12學時實驗） 第一章 緒論 （6學時） 第二章 線性表 （8學時） 第三章 棧和隊列 （8學時） 第六章 樹 （10學時） 第七章 圖 （8學時） 第九章 查找 （4學時） 第十章 排序（6學時） 總復習 （2學時） 共計52學時,考核 平時成績10%實驗20%考試成績70%,4,課程特點及教學方法,難度大 綜合性強 必須要有C語言基礎 關于教學的幾個新觀念 教學過程以學生為主體, 教師為主導 學生由知識技能的被動接受者向知識技能的主動探求者轉變,。教學目標為使學生在知識、能力、素質方面協(xié)調發(fā)展 能力包括自學能力、知識運用能力、動手能力、創(chuàng)新能力、發(fā)現問題能力、分析問題和解決問題能力以及可持續(xù)發(fā)展能力,5,1.1 本課研究的問題 1.2 什么是數據結構 1.3 數據結構的基本概念和術語 1.4 數據結構的分類與表示 1.5 算法與算法分析,第一章 緒 論,6,計算機的發(fā)展 軟件 硬件 應用領域,數據處理的種類和能力, 數據,數值數據,非數值數據,數 (整數,實數) 字符 字符串 文字 圖形 圖象 聲音,數據：客觀對象的符號表示 數學中的整數、實數， 課程名，地名、書名,1.1 本課程研究的問題,1.1 本課程研究的問題,7, 數值問題與非數值問題,1）數值問題 已知：游泳池的長len和寬wide，求面積area,設計 求解問題的方法 編程, 建模型： 問題涉及的對象：游泳池的長len 寬wide，面積area； 對象之間的關系：area=lenwide,1.1 本課程研究的問題,main ( ) int len, wide ,area ; scanf (“%d %d%n”, ,8,在這類文檔管理的數學模型中, 計算機處理的對象之間通常存在著一種最簡單的線性關系 , 這類數學模型稱為線性模型,1.1 本課程研究的問題,9,1.1 本課程研究的問題,迷宮問題： 在迷宮中，每走到一處，接下來可走的通路有三條。計算機處理的這類對象之間通常不存在線性關系。若把從迷宮入口處到出口的過程中所有可能的通路都畫出，則可得一棵“樹”,10,數據結構的研究問題： 非數值數據之間的結構關系， 及如何表示，如何存儲，如何處理。 本課程討論的問題： 應用中常用的幾種數據間的結構關系， 及如何表示,如何存儲，如何處理。,1.1 本課程研究的問題,11,數據結構是一門研究數據組織、存儲和運算的一般方法的學科。,1.2 什么是數據結構,1.2 什么是數據結構,整數(1,2)、實數(1.1,1.2) 字符串(Beijing)、 圖形、聲音。,計算機管理圖書問題 在圖書館里有各種卡片：有按書名編排的、 有按作者編排的、有按分類編排 如何將查詢圖書的這些信息存入計算機中 既要考慮查詢時間短，又要考慮節(jié)省空間,最簡單的辦法之一是建立一張表， 每一本書的信息在表中占一行，如,數據元素在 計算機中的表示,如何將0,1,2,3,4,5,6,7,8,9這10個數存放在 計算機中能最快地達到你所需要的目的？ 目的不同，最佳的存儲方方法就不同。 從大到小排列：9,8,7,6,5,4,3,2,1,0 輸出偶數：0,2,4,6,8,1,3,5,7,9,對數據結構中的節(jié)點進行 操作處理 (插入、刪除、修改、查找、排序),程序算法數據結構,12,13 數據結構的有關概念,1.3 數據結構的有關概念,數據（data)所有能輸入到計算機中去的描述客觀事物的符號。例如：學號，姓名，班名都是數據。 數據元素（data element）數據的基本單位，也稱節(jié)點（node）或記錄（record） 。 數據項（data item）有獨立含義的數據最小單位，也稱域(field) 數據結構（data structure)數據元素和數據元素關系的集合。例如: 所有班名相同的記錄集合,13,對每種數據結構，主要討論如下兩方面的問題： 1） 數據的邏輯結構，數據結構的基本操作； 2） 數據的存儲結構，數據結構基本操作的實現；,數據的邏輯結構： 數據之間的結構關系，是具體關系的抽象。,數據結構的基本操作： 指對數據結構的加工處理,數據的存儲結構 (物理結構)： 數據結構在計算機內存中的表示,數據結構基本操作的實現： 基本操作在計算機上的實現（方法),13 數據結構的有關概念,14,某班學生基本情況登記表，記錄了每個學生的學號 姓名 專業(yè) 政治 面貌 ，表中的記錄是按學生的學號順序排列的。,學號 姓名 專業(yè) 政治面藐 001 王洪 計算機 黨員 002 孫文 計算機 團員 003 謝軍 計算機 團員 004 李輝 計算機 團員 005 沈祥福 計算機 黨員 006 余斌 計算機 團員 007 鞏力 計算機 團員 008 孔令輝 計算機 團員,學生基本情況登記表的圖示,學生間學號順序關系 是一種線性結構關系,一 常用的數據結構,1） 集合 2） 線性結構 3） 樹結構 4） 圖結構 5）其它復雜結構,例,1.4 數據結構的分類與表示,14 數據結構的分類與表示,15,家族的族譜 假設某家族有10個成員A， B， C， D， E， F， G， H，I， J，他們之間的血緣關系可以用如下圖表示。,14 數據結構的分類與表示,例,16,多叉路口交通燈管理問題,例,14 數據結構的分類與表示,17,數據結構的表示,1、圖示表示 圖示表示是由頂點和邊構成的圖，其中頂點表示數據 ，邊表示數據之間的結構關系；,學生基本情況表的圖示表示,家族樹的圖示表示,14 數據結構的分類與表示,18,學生基本情況表的二元組表示（D，S）,2、二元組表示 二元組表示是用一個二元組（D，S）表示數據結構， 其中 D 是數據元素集合，S 是 D 上關系的集合。,D = 001，002，003，004，005，006，007，008 S = R R= , , ,家族樹的二元組表示（D，S）,D = A，B，C，D，E，F，G，H，I，J S = R R = A,B, ,14 數據結構的分類與表示,19,1、數據的邏輯結構,2、數據的存儲結構,3、數據的運算：檢索、排序、插入、刪除、修改等。,A線性結構,B非線性結構,A 順序存儲,B 鏈式存儲,線性表,棧,隊,樹形結構,圖形結構,數據結構的三個方面,數據結構可描述為 Group=（D，R）,(亦稱物理結構),14 數據結構的分類與表示,20,數據的邏輯結構只抽象反映數據元素的邏輯關系 數據的存儲（物理）結構數據的邏輯結構在計算機存儲器中的實現,數據結構側重于解決問題的策略和方法，即研究算法。 它不但要求給出問題的一種算法，還要求算法的時空效率高、算法結構和可讀性好、容易驗證等等。,14 數據結構的分類與表示,21,3、抽象數據結構描述：,有限個數據 元素的集合,是D上 關系的有限集,14 數據結構的分類與表示,有限個節(jié)點間 關系的集合,Group=（D , S , R）,ADT（Abstract Data Type），即抽象數據類型，是指一個數學模型及定義在該模型上的一組操作（運算）。ADT只考慮數據的邏輯結構,22,ADT的定義可以用一個三元組表示。其中D是數據對象，S是D上的關系集，R是對D的基本操作集?？梢圆捎靡韵赂袷蕉xADT： ADT 抽象數據類型名 數據對象： 數據關系： 基本操作： ADT 抽象數據類型名 其中，數據對象和數據關系的定義可以用形式化偽碼描述，基本操作的定義格式為： 基本操作名（參數表） 初始條件： 操作結果：,23,ADT的定義與數據結構的定義有著明顯的差別，它將基本操作與數據對象和數據關系在形式上封裝在一起，并以此來建模。大多數的抽象數據類型是由用戶自行設計和實現的。,例: 用ADT表示復數Complex。,ADT Complex 數據對象：D= ，R 數據關系： e1是實數，e是虛數 基本操作：主要加、減、乘、除等操作,24,GetReal(z) 初始條件：復數z已經存在。 操作結果：返回復數z的實部值。,GetImage (z) 初始條件：復數z已經存在。 操作結果：返回復數z的虛部值。,Add(z1, z2) 初始條件：z1,z2均為復數。 操作結果：返回復數z1和z2的和,Minus (z1, z2) 初始條件：z1,z2均為復數。 操作結果：返回復數z1減z2的差 。,Multiply (z1, z2) 初始條件：z1,z2均為復數。 操作結果：返回復數z1和z2的積,Multiply (z1, z2) 初始條件：z1,z2均為復數。 操作結果：返回復數z1除以z2的商,InitComplex(&z, v1,v2) 初始條件：無。 操作結果：構造復數z，其實部和虛部分別賦以參數v1和v2的值, ADT Complex,25,例： 采用前面定義的抽象數據類型Complex所提供的各種操作函數，編制一個算法（C語言），用以計算復數： z=（(8-6i)(4+3i)）/（2+6i）-(3+3i)的值。,分析：為簡單起見，不妨假定ADT Complex中的所有操作函數已經實現，只要遵守ADT Complex中的約定即可。,26,算法： Complex z1, z2, z3, z4, z5;設置參數 InitComplex( ,抽象數據類型需要用具體的數據類型來實現。采用什么樣的數據結構表示數學模型，要服從于方便有效地實現該抽象數據類型上定義的大多數操作。,27,1.5 算法與算法分析,一 、算法的概念 算法 ：是解決某一特定問題的具體步驟的描述，是指令的有限序列,算法的描述：采用C語言描述,15 算法與算法分析,算法的基本特征： 1）輸入：0個或多個輸入； 2）輸出：1個或多個輸出； 3）有窮性：算法必須在有限步內結束； 4）確定性：組成算法的操作必須清晰無二義性。 5）可行性：組成算法的操作必須能夠在計算機上實現。,28,算法的評價衡量算法優(yōu)劣的標準 正確性(correctness)：不含語法錯誤 可讀性(readability)：便于維護 健壯性(robustness)：見錯性好 效率與低存儲量,算法效率用依據該算法編制的程序在計算機上執(zhí) 行所消耗的時間來度量,29,例,試編寫算法：輸入一個正整數，并判斷是否為素數,一般使用結構化程序設計方法解決問題。常用的是逐步求精和分而治之的設計方法，用來開發(fā)軟件系統(tǒng)。一般情況下，采用分而治之將問題逐步化小，直到達到人們能夠理解的程度，再用逐步求精找出算法，因而多把它們結合使用。,1、逐步求精方法把程序設計分為二步：第一步，只考慮“做什么”，即對問題進行分析，給出解決問題的思路；第二步，再考慮“如何去做”，給出具體代碼。,30,2、分而治之的方法： 1)把問題分成兩個或多個更小的問題； 2)分別解決每個小問題； 3)把各小問題的解答組合起來，即可得到原問題的解答。小問題通常與原問題相似，可以遞歸地使用分而治之策略來解決。,31,算法：int input(） /判斷X是否為素數/ flog=1; i=2; while ( i= X-1 ) and ( flog=1 ) if ( X % i = =0) flog=0; i+; return ( flog ),本題用逐步求精方法完成： 1、第一步：分析所提出的問題，設計程序的結構 2、第二步：對 “素數”進一步求精，設置一個標志參數flog 3、第三步：對 “x 是一個素數”進一步求精，根據素數定義用i2,.,X，除以X，flog=0表示能除盡，為1則不能 4、第四步: 對“x不能被j整除”進一步求精，根據flog的值，判斷X是否為素數,32,15 算法與算法分析,C語言程序： Main（） int x, flog, i; flog=1; scanf( “%d”, x ); for ( i =2, i=x-1, i+ ) if ( x % i = =0 ) flog=0 ,break if ( flog ) printf (“是一個素數”) else printf (“非素數”） ,33,例,試給你一個裝有16個硬幣的袋子。16個硬幣中有一個是偽造的，并且那個偽造的硬幣比真的硬幣要輕一些。你的任務是找出這個偽造的硬幣。為了幫助你完成這一任務，提供一架天平用于找出偽幣。,第一種方法：逐步求精方法；兩個進行比較，找 出較輕者，最多需要8次比較。,第二種方法：分而治之方 ；把16硬幣看成一個大 的問題。,34,16,8輕,4輕,2輕,35,15 算法與算法分析,二、算法時間復雜度T（n） 本課程采用以求解問題的基本操作（原操作）的執(zhí)行次數作為算法時間的度量。,算法的時間復雜度 一般來說，設算法中基本操作的執(zhí)行次數是問題規(guī)模n的某個函數f(n)，算法的時間復雜度記作： T(n) = O(f(n) 語句重復執(zhí)行的次數稱為語句的頻度,36,一個算法的時間復雜度（Time Complexity，簡稱為時間復雜性）T(n)是該算法的時間耗費，是該算法所求解問題規(guī)模n的函數。當問題的規(guī)模n趨向無窮大時，時間復雜度T(n)的數量級(階)稱為算法的漸進時間復雜度。,例,求兩個 n 階矩陣的乘法CAB的算法，寫出算法中帶標號語句的頻度，并求該算法的時間復雜度,37,15 算法與算法分析,For ( i = 1; i=n; i+ ) (1) For (j = 1; j=n; j+ ) (2) x=0; (3) For (k = 1; k= n; k+ ) (4) c i j += a i k * b k j ; (5) c i j = x; (6) ,該算法主體是一個三重循環(huán)，先以標號（2）的語句說明其頻度：對于固定的i、j從1變到n,指令j+需執(zhí)行n+1步，而相對于外循環(huán)(1),i從1變到超過n，內循環(huán)重復n次，故(2)的執(zhí)行頻度為n(n+1),(1) n+1,(2) n(n+1),(3) n2,(4) n2(n+1),(5) n3,(6) n2,標號語句的頻度分別為：,算法時間復雜度為所有語句的頻度之和： T(n) = n+1+n(n+1)+n2+n2(n+1)+n3+n2 =2 n3 +4 n2 +2n+1 O(n3),38,15 算法與算法分析,有些算法，基本操作執(zhí)行次數與問題的輸入數據有關，這時可考慮 （1） 算法平均時間復雜度 （2） 算法在最壞情況下的時間復雜度,例,指出下列算法的時間復雜度： Void prume(int n) int i=2; While( ( x % i) ,39,算法:是一個有窮規(guī)則的集合，其中之規(guī)則確定了一個解決某一特定類型問題的運算序列。 算法具有五個特點：有窮性、確定性、輸入、輸出和能行性。 算法的正確性判定是:一個比較復雜的問題，對于簡單的算法，可以采用窮舉法或程序正確性證明等方法來確定算法的正確性；而對于復雜的算法，人們不可能采用窮舉法或程序正確性證明來驗證算法的正確性，只能說明算法在給定的測試下沒有錯誤發(fā)生，而不能說明算法是正確的。,40,算法分析: 評價一個算法的好壞主要是從算法的時間復雜度和算法的空間復雜度兩個方面來考察。 算法的時間復雜度和空間復雜度是兩個相互矛盾的性能指標，一個算法要么其所占存儲空間較小，要么其運行時間較短，兩者性能均好的算法往往難以找到。,41,本章節(jié)的重點 1數據結構及其表示。數據結構包括數據的邏輯結構和物理結構，數據呈現給用戶是其邏輯結構，其物理存儲對用戶是透明的。為了有效地處理數據，數據結構必須給出數據集上操作的統(tǒng)一接口，而不管其存儲結構。 2ADT是一種描述數據結構的常用工具，它能很好地描述數據的邏輯結構和其上的操作。在用ADT描述數據結構時，可以不考慮其存儲結構。,42,3結構化程序設計方法是一種典型的程序設計方 法。由于結構化程序設計方法將問題劃分成一個個的相互獨立又相互聯(lián)系的子問題，解決子問題相對容易，而且子問題的正確性也易于保證，因此結構化程序設計方法是數據結構中采用的一種典型設計方法。 4算法。算法是實現結構化程序設計方法的基礎，一個子問題可以用一個算法來實現，將各個子問題的算法有機地結合起來就構成了整個問題的實現算法。,43,例,設有數據邏輯結構為： D（K R） K（K1，K2，K3，K9） RK1，K3， K1，K8， K2，K3， K2，K4， K2，K5， K3，K9 ，K5，K6 K8，K9 ，K9，K7 ，K4，K7 ，K4，K6 畫出這個邏輯結構的圖示，并確定相對于關系R，哪些結點是開始結點，哪些結點是終端結點？,開始結點：是指無前趨的結點，,終端結點：是指無后續(xù)的結點，,只有K1和K2。,只有K6和K7。,14 數據結構的分類與表示,44,已知m，n均為正整數，試用ADT描述求m和n的最小公倍數的算法。,例,算法的步驟如下： （1）計算r(m*n)； （2）若m等于n，則輸出最小公倍數r/m，算法結束； （3）若m大于n，計算m(m-n；否則計算n(n-m； （4）轉（2）。,分析：題設雖只要描述其求兩個正整數的最小公倍數，為了ADT描述的方便，我們可以針對整個正整數集來討論。 ADT是一種描述數據結構的常用工具，針對具體問題，只要按照ADT的描述規(guī)范實現就可以了。,45,下面是其ADT描述： ADT Positive_Int 數據對象：Dx | x是正整數 基本操作： LCM(x1, x2) 初始條件：要求x1和x2都是正整數。 操作結果：返回x1和x2的最小公倍數。 ADT Positive_Int;,46,基本操作LCM的C語言形式的具體實現為： int LCM( int x1, int x2 ) /* 求正整數x1和x2的最小公倍數 */ int r = x1 * x2; /* 存放x1和x2的積 */ if( x1 x2 ) x1 = x1 x2; else x2 = x2 x1; return r / x1; /* 返回正整數x1和x2的最小公倍數 */ ,47,作 業(yè) 1、寫出下題算法，并求出其時間復雜度。(C語言） 100元買100支筆, 其中鋼筆 3元/支, 圓珠筆 2元/支, 鉛筆 0.5元/支，用C語言編程輸出可能的各種組合方案。 2、有一個老板有一袋金塊。每個月將有兩名雇員會因其優(yōu)異的表現分別被獎勵一個金塊。按規(guī)矩，排名第一的雇員將得到袋中最重的金塊，排名第二的雇員將得到袋中最輕的金塊。根據這種方式，除非有新的金塊加入袋中，否則第一名雇員所得到的金塊總是比第二名雇員所得到的金塊重。如果有新的金塊周期性的加入袋中，則每個月都必須找出最輕和最重的金塊。假設有一架天平，請你設計一個算法用最少的比較次數找出最輕和最重的金塊。,48,算法的時間復雜度為O (N3),49,# define N 100 Void scheme( ) int i, j; for (i=0; i=N/3; i+) for (j=0; j=(N-3*i)/2; j+) if (3*i+2*j+0.5*(N-i-j)= =N) printf(“%d, %d, %dn%”, i, j, N-i-j); 時間復雜度為O(N2 ),解法2,50,線性結構,A , B , C , ，X ,Y , Z,學 生 成 績 表,線性表結點間是以線性關系聯(lián)結,A1， A2 Ai-1， Ai， Ai+1， An,A