數(shù)據(jù)結(jié)構(gòu)第一章.ppt

1、數(shù)據(jù)結(jié)構(gòu),2020年8月14日星期五,學(xué)時(shí)數(shù)：48學(xué)時(shí)（16學(xué)時(shí)實(shí)驗(yàn)） 教 材：數(shù)據(jù)結(jié)構(gòu)C語言版嚴(yán)蔚敏、吳偉民 -清華大學(xué)出版社（配題集）,參考書： 1 殷人昆等，數(shù)據(jù)結(jié)構(gòu)（用面向?qū)ο蠓椒ㄅcC+描述），清華 大學(xué)出版社 2數(shù)據(jù)結(jié)構(gòu)C語言篇習(xí)題與解析，李春葆，清華大學(xué)出版社 3 丁寶康等，數(shù)據(jù)結(jié)構(gòu)自學(xué)考試指導(dǎo)，清華大學(xué)出版社,課程介紹,學(xué)習(xí)要求,1、上課認(rèn)真聽講，適當(dāng)做好筆記，按時(shí)交作業(yè)。 2、復(fù)習(xí)和預(yù)習(xí)。 3、課后需要多讀課本和參考書，上網(wǎng)查看相關(guān)內(nèi)容，在理解基本內(nèi)容的基礎(chǔ)上，多看、多做習(xí)題。 4、上機(jī)實(shí)踐。, 1.1 什么是數(shù)據(jù)結(jié)構(gòu) 1.2 基本概念和術(shù)語 1.3 抽象數(shù)據(jù)類型的表示和實(shí)現(xiàn)

2、1.4 算法和算法分析,第1章 緒論,數(shù)據(jù)結(jié)構(gòu)與程序的關(guān)系 思考:下表是10次C語言課程的測驗(yàn)成績，請(qǐng)?jiān)O(shè)計(jì)一個(gè)小程序計(jì)算這10次測驗(yàn)的總分和平均分。,1.1 什么是數(shù)據(jù)結(jié)構(gòu),方法一: void main() int t1,t2,t3,t4,t5,t6,t7,t8,t9,t10; int sum; int average; t1=; t2=; t3=; t4=; t5=; t6=; . sum=t1+.t10; average=sum/10; ,方法二: void main() int t10=80,.; int sum; int average; int i; sum=0; for (i=0;

3、i10;i+) sum+=ti; average=sum/10; ,哪種方法好? 為什么?,如何選擇最佳的數(shù)據(jù)結(jié)構(gòu)來解決程序問題是為什么需要學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的重要原因。 數(shù)據(jù)結(jié)構(gòu)主要研究數(shù)據(jù)的邏輯結(jié)構(gòu),在計(jì)算機(jī)中的存儲(chǔ)結(jié)構(gòu)以及對(duì)數(shù)據(jù)進(jìn)行各種非數(shù)值運(yùn)算的方法和算法。,數(shù)據(jù)結(jié)構(gòu)示例A 線性表,1.1 什么是數(shù)據(jù)結(jié)構(gòu),數(shù)據(jù)結(jié)構(gòu)示例B樹,1.1 什么是數(shù)據(jù)結(jié)構(gòu),1.許卓群，張乃孝，楊冬青，唐世渭，數(shù)據(jù)結(jié)構(gòu)，國防科技大學(xué)計(jì)算機(jī)研究所，1985年 “按某種邏輯關(guān)系組織起來的一批數(shù)據(jù)，按一定的存儲(chǔ)表示方式把它存儲(chǔ)在計(jì)算機(jī)的存儲(chǔ)器中，并在這些數(shù)據(jù)上定義了一個(gè)運(yùn)算的集合，就叫做一個(gè)數(shù)據(jù)結(jié)構(gòu)?！?特點(diǎn)：從三個(gè)方面來看

4、數(shù)據(jù)結(jié)構(gòu)。,2.李春葆，數(shù)據(jù)結(jié)構(gòu)（C語言篇）習(xí)題與解析，清華大學(xué)出版社，2000年 “數(shù)據(jù)結(jié)構(gòu)是指同一數(shù)據(jù)元素類中各數(shù)據(jù)元素之間存在的關(guān)系。數(shù)據(jù)結(jié)構(gòu)又可以分為下述三個(gè)組成部分，它們分別是數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)和數(shù)據(jù)的運(yùn)算?！?特點(diǎn)：明確強(qiáng)調(diào)“關(guān)系”，且細(xì)分“關(guān)系”。,1.1 什么是數(shù)據(jù)結(jié)構(gòu),3.黃國瑜，葉乃菁，數(shù)據(jù)結(jié)構(gòu)，清華大學(xué)出版社，2001年 “在程序語言中，“數(shù)據(jù)類型”是指程序語言中變量所能表示并存儲(chǔ)的數(shù)據(jù)種類，“數(shù)據(jù)實(shí)體”則是指在一種數(shù)據(jù)類型中的所有可能元素的集合。而“數(shù)據(jù)結(jié)構(gòu)”，大致上說來，就是數(shù)據(jù)實(shí)體中元素之間的關(guān)系，包括數(shù)據(jù)的表示法和運(yùn)算?！?特點(diǎn)：指出“關(guān)系”為表示法和

5、運(yùn)算。,4.陳慧南，數(shù)據(jù)結(jié)構(gòu)C語言描述，西安電子科技大學(xué)出版社，2003年 “從數(shù)學(xué)概念上講，一個(gè)數(shù)據(jù)結(jié)構(gòu)是由數(shù)據(jù)元素依據(jù)某種邏輯聯(lián)系組織起來的。 研究數(shù)據(jù)結(jié)構(gòu)是為了解決應(yīng)用問題，所以討論數(shù)據(jù)結(jié)構(gòu)必須同時(shí)討論在數(shù)據(jù)結(jié)構(gòu)上執(zhí)行的相關(guān)運(yùn)算及其算法才有意義?！?特點(diǎn)：從邏輯聯(lián)系入手，兼顧其它方面。,1.1 什么是數(shù)據(jù)結(jié)構(gòu),數(shù)據(jù)結(jié)構(gòu)要解決的問題,1 數(shù)值問題 例 已知：游泳池的長len和寬wide，求面積area 建模型： 問題涉及的對(duì)象： 游泳池的長len 寬wide，面積area； 對(duì)象之間的關(guān)系： area=lenwide,設(shè)計(jì)求解問題的方法 編程 main ( ) int len, wide

6、,area ;scanf (“%d %d%n”, ,2 非數(shù)值問題 例 已知班級(jí)學(xué)生情況，如下表1_1，要求分班按入學(xué)成績排列順序。 表1_1： 學(xué)號(hào) 姓名 性別 出生日期 籍貫 入學(xué)成績 所在班級(jí) 082001 楊潤生 男 82/06/01 廣州 561 00計(jì)算機(jī)1 082031 石磊 男 83/12/21 汕頭 512 00計(jì)算機(jī)1 082053 李梅 女 83/02/23 陽江 532 00計(jì)算機(jī)2 082064 馬耀先 男 82/07/12 廣州 509 00計(jì)算機(jī)2,計(jì)算機(jī)內(nèi)的數(shù)值運(yùn)算依靠方程式，而非數(shù)值運(yùn)算則要依靠數(shù)據(jù)結(jié)構(gòu)。,同樣的數(shù)據(jù)對(duì)象，用不同的數(shù)據(jù)結(jié)構(gòu)來表示，運(yùn)算效率可能有

7、明顯的差異。,程序設(shè)計(jì)實(shí)質(zhì) = 好算法 + 好結(jié)構(gòu),學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)課程的用處,1.1 什么是數(shù)據(jù)結(jié)構(gòu),本書討論的典型數(shù)據(jù)結(jié)構(gòu)包括：線性表、堆棧、隊(duì)列、數(shù)組、串、樹、二叉樹和圖。,是介于數(shù)學(xué)、計(jì)算機(jī)硬件和計(jì)算機(jī)軟件三者之間的一門核心課程,數(shù)學(xué),硬件,軟件,數(shù)據(jù)結(jié)構(gòu)課程的地位,1.1 什么是數(shù)據(jù)結(jié)構(gòu),數(shù)據(jù)-是對(duì)客觀事物的符號(hào)表示，在計(jì)算機(jī)科學(xué)中是指所有（Data） 能輸入到計(jì)算機(jī)中并被計(jì)算機(jī)程序處理 的符號(hào)的總 稱(整數(shù)、實(shí)數(shù)、字符串、圖像、聲音等)。,數(shù)據(jù)元素-是數(shù)據(jù)的基本單位，具有完整確定的實(shí)際意義， （Data Element） 在計(jì)算機(jī)程序中通常作為一個(gè)整體進(jìn)行考慮和 處理(又稱記錄、結(jié)點(diǎn)等

8、)。,數(shù)據(jù)項(xiàng)- 一個(gè)數(shù)據(jù)元素可由若干個(gè)數(shù)據(jù)項(xiàng)組成， 是數(shù)據(jù)的 （Data Item） 不可分割的最小單位(又稱字段等)。,三者之間的關(guān)系：數(shù)據(jù)數(shù)據(jù)元素?cái)?shù)據(jù)項(xiàng),例：學(xué)生檔案個(gè)人記錄姓名、性別、籍貫,1.2 基本概念和術(shù)語,數(shù)據(jù)對(duì)象（Data Object）-是性質(zhì)相同的數(shù)據(jù)元素的集合， 是數(shù)據(jù)的一個(gè)子集。,數(shù)據(jù)結(jié)構(gòu)（Data Structure）-是相互之間存在一種或多種 特定關(guān)系的數(shù)據(jù)元素的集合。,表示為： Data_Structure = ( D, S ),元素有限集,關(guān)系有限集,例1：用數(shù)據(jù)結(jié)構(gòu)表示一周中的七天。,Data_Structure=(D,S),其中， D= S= ,Mon,Tu

9、e, Wen, Thu, Fri, Sat, Sun,1.2 基本概念和術(shù)語,（1）Data_Structure=(D,S)，其中， D= 01，02，03，04，05 S= ,（2） S=(D, R) D= a, b, c, d, e, f R= , , , , ,解: 上述表達(dá)式可用圖形表示為：,a,e,b,c,f,d,例2：將下述表達(dá)式用圖形的形式表示出來,集合結(jié)構(gòu),線性結(jié)構(gòu),1.2 基本概念和術(shù)語,（3） Data_Structure=(D,S),其中， D= 01，02，03，04，05 ，06，07 S=(01,02)，(01,03)，(01,04)，(02,05)，(02,06)

10、，(03,07) ,（4） S=(D,R) D=di | 1i5, 1j5 R=, ij,01,02,03,04,05,06,07,樹形結(jié)構(gòu),圖狀結(jié)構(gòu),1.2 基本概念和術(shù)語,邏輯結(jié)構(gòu)-數(shù)據(jù)元素之間的邏輯關(guān)系，即結(jié)構(gòu)中定義的“關(guān)系”。,邏輯結(jié)構(gòu)可細(xì)分為4類：,集合結(jié)構(gòu) 線性結(jié)構(gòu) 樹形結(jié)構(gòu) 圖狀結(jié)構(gòu),一對(duì)一關(guān)系,一對(duì)多關(guān)系,多對(duì)多關(guān)系,1.2 基本概念和術(shù)語,物理結(jié)構(gòu)-也稱存儲(chǔ)結(jié)構(gòu)，是數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)存 儲(chǔ)器內(nèi)的表示（映像）。,順序映像 非順序映像,特點(diǎn)是借助元素在存儲(chǔ)器中的相對(duì)位置來表示數(shù)據(jù)元素之間的邏輯關(guān)系。,特點(diǎn)是借助指示元素存儲(chǔ)地址的指針表示數(shù)據(jù)元素之間的邏輯關(guān)系。,例：復(fù)數(shù) 3.

11、0-2.3i 的存儲(chǔ)形式,算法的設(shè)計(jì)取決于選定的數(shù)據(jù)（邏輯）結(jié)構(gòu) 算法的實(shí)現(xiàn)依賴于采用的存儲(chǔ)結(jié)構(gòu),-順序存儲(chǔ)結(jié)構(gòu),-鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu),1.2 基本概念和術(shù)語,數(shù)據(jù)類型-是一個(gè)值的集合和定義在這個(gè)值集上的一組操作 的總稱。,抽象數(shù)據(jù)類型由用戶定義，用以表示應(yīng)用問題的數(shù)據(jù)模型。它由基本的數(shù)據(jù)類型組成，并包含一組相關(guān)的操作。,抽象數(shù)據(jù)類型可用ADT=（D，S，P）三元組表示,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),例：給出自然數(shù)（Natural Number）的抽

12、象數(shù)據(jù)類型定義。,IsZero(x) : Boolean if (x=0) 返回True else 返回False Add (x, y) : NaturalNumber if (x+y=MaxInt)返回 x+y else 返回MaxInt Subtract (x, y) : NaturalNumber if (x y) 返回 0 else 返回 x - y Equal (x, y) : Boolean if (x=y) 返回True else 返回 False,ADT NaturalNumber ,NaturalNumber,數(shù)據(jù)對(duì)象:,數(shù)據(jù)關(guān)系:,數(shù)據(jù)操作:,一個(gè)整數(shù)的有序子集合,它開始于

13、0, 結(jié)束于機(jī)器能表示的最大整數(shù)。,1.3 抽象數(shù)據(jù)類型的表示與實(shí)現(xiàn),一、算法：,算法是對(duì)特定問題求解步驟的一種描述，它是指令的有限序列，其中每一條指令表示一個(gè)或多個(gè)操作。,二、算法的5個(gè)特性： 有窮性、確定性、可行性、輸入和輸出,三、算法設(shè)計(jì)的要求： 正確性、可讀性、健壯性、效率與低存儲(chǔ)需求,時(shí)間復(fù)雜度,空間復(fù)雜度,1.4 算法和算法分析,時(shí)間復(fù)雜度：,一個(gè)算法花費(fèi)的時(shí)間與算法中語句的執(zhí)行次數(shù)成正比例，哪個(gè)算法中語句執(zhí)行次數(shù)多，它花費(fèi)時(shí)間就多。一個(gè)算法中語句的執(zhí)行次數(shù)稱為語句頻度或時(shí)間頻度，記為T(n)。,算法中基本操作重復(fù)執(zhí)行的次數(shù)是問題規(guī)模n的某個(gè)函數(shù)，算法的時(shí)間量度記作 T（n）=O（

14、f（n） 隨著問題規(guī)模的增大，算法執(zhí)行時(shí)間的增長率和f（n）的增長率相同，稱為算法的漸近時(shí)間復(fù)雜度，簡稱時(shí)間復(fù)雜度。,1.4 算法和算法分析,從算法中選取一種對(duì)于所研究的問題來說是 基本操作 的原操作，以該基本操作 在算法中重復(fù)執(zhí)行的次數(shù) 作為算法運(yùn)行時(shí)間的衡量準(zhǔn)則。,算法的時(shí)間復(fù)雜度由嵌套最深層語句的頻度決定,1.4 算法和算法分析,時(shí)間復(fù)雜度,一般沒有必要精確地計(jì)算出算法的時(shí)間復(fù)雜度,只要大致計(jì)算出相應(yīng)的數(shù)量級(jí)即可。,3n+2=O(n) 因?yàn)?3n+24n 當(dāng) n2時(shí) 6*2n+n2=O(2n) 因?yàn)?*2n+n2 7*2n 當(dāng) n4,例：,漸進(jìn)符號(hào)（O）的定義：當(dāng)且僅當(dāng)存在一個(gè)正的常數(shù)

15、C，使得對(duì)所有的 n n0 ，有 f(n) Cg(n)，則： f(n) = O(g(n), +x;s=0;, for(i=1;i=n;+i) +x;s+=x;, for(j=1;j=n;+j) for(k=1;k=n;+k) +x;s+=x;,O （1）,O （n）,O （n2）,算法的時(shí)間復(fù)雜度由嵌套最深的語句的頻度決定的, i=1; while(i=n) i=i*2;,O （log2n）,1.4 算法和算法分析,1.4 算法和算法分析,算法分析應(yīng)用舉例,算法中基本操作重復(fù)執(zhí)行的次數(shù)是問題規(guī)模n的某個(gè)函數(shù)，其時(shí)間量度記作 T(n)=O(f(n)，稱作算法的漸近時(shí)間復(fù)雜度(Asymptotic

16、 Time complexity)，簡稱時(shí)間復(fù)雜度。 一般地，常用最深層循環(huán)內(nèi)的語句中的原操作的執(zhí)行頻度(重復(fù)執(zhí)行的次數(shù))來表示。 “O”的定義： 若f(n)是正整數(shù)n的一個(gè)函數(shù)，則 O(f(n)表示 M0 ，使得當(dāng)n n0時(shí)，| f(n) | M | f(n0) | 。 表示時(shí)間復(fù)雜度的階有： O(1) ：常量時(shí)間階 O (n)：線性時(shí)間階 O(n) ：對(duì)數(shù)時(shí)間階 O(nn) ：線性對(duì)數(shù)時(shí)間階,O (nk)： k2 ，k次方時(shí)間階 例 兩個(gè)n階方陣的乘法 for(i=1，i=n; +i) for(j=1; j=n; +j) cij=0 ; for(k=1; k=n; +k) cij+=aik

17、*bkj ; 由于是一個(gè)三重循環(huán)，每個(gè)循環(huán)從1到n，則總次數(shù)為： nnn=n3時(shí)間復(fù)雜度為T(n)=O(n3) 例 +x; s=0 ; 將x自增看成是基本操作，則語句頻度為，即時(shí)間復(fù)雜度為(1) 。,如果將s=0也看成是基本操作，則語句頻度為，其時(shí)間復(fù)雜度仍為(1)，即常量階。 例 for(i=1; i=n; +i) +x; s+=x ; 語句頻度為：2n，其時(shí)間復(fù)雜度為：O(n) ，即為線性階。 例 for(i=1; i=n; +i) for(j=1; j=n; +j) +x; s+=x ; 語句頻度為：2n2 ，其時(shí)間復(fù)雜度為：O(n2) ，即為平方階。,定理：若A(n)=a m n m

18、+a m-1 n m-1 +a1n+a0是一個(gè)m次多項(xiàng)式，則A(n)=O(n m) 例 for(i=2;i=n;+i) for(j=2;j=i-1;+j) +x; ai,j=x; 語句頻度為： 1+2+3+n-2=(1+n-2) (n-2)/2 =(n-1)(n-2)/2 =n2-3n+2 時(shí)間復(fù)雜度為O(n2)，即此算法的時(shí)間復(fù)雜度為平方階。 一個(gè)算法時(shí)間為O(1)的算法，它的基本運(yùn)算執(zhí)行的次數(shù)是固定的。因此，總的時(shí)間由一個(gè)常數(shù)（即零次多項(xiàng)式）來限界。而一個(gè)時(shí)間為O(n2)的算法則由一個(gè)二次多項(xiàng)式來限界。,以下六種計(jì)算算法時(shí)間的多項(xiàng)式是最常用的。其關(guān)系為： O(1)O(n)O(n)O(nn)O(n2)O(n3) 指數(shù)時(shí)間的關(guān)系為： O(2n)O(n!)O(nn) 當(dāng)n取得很大時(shí)，指數(shù)時(shí)間算法和多項(xiàng)式時(shí)間算法在所需時(shí)間上非常懸殊。因此，只要有人能將現(xiàn)有指數(shù)時(shí)間算法中的