數(shù)據(jù)結(jié)構(gòu)-使用c語言朱戰(zhàn)立

1、教材：朱戰(zhàn)立編著，數(shù)據(jù)結(jié)構(gòu)——使用C語言（第3版），西安交通大學(xué)出版社，2003年,數(shù) 據(jù) 結(jié) 構(gòu),2,學(xué)時數(shù)：70（50學(xué)時授課＋20學(xué)時上機(jī)） 教材：朱戰(zhàn)立編著，數(shù)據(jù)結(jié)構(gòu)（使用C語言）第3版，西 安交通大學(xué)出版社 ，2003年參考書：[1]嚴(yán)蔚敏等，數(shù)據(jù)結(jié)構(gòu)（C語言版），清華大學(xué)出版社[2] 數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)指導(dǎo)與典型題解，朱戰(zhàn)立等編著，西安交通大學(xué)出版社 ，2002年,3,內(nèi) 容 安 排,4,1、上課認(rèn)

2、真聽講，適當(dāng)做好筆記。2、考試成績分兩部分：平時成績（包括出勤和上機(jī)實驗）占20%，期末成績占80%。3、課后需要多讀課文和參考書，上網(wǎng)查看相關(guān)內(nèi)容，在理解基本內(nèi)容的基礎(chǔ)上，多看、多做習(xí)題。4、上機(jī)實驗十分重要，一定要在上機(jī)前做好充分準(zhǔn)備，多采用不同的數(shù)據(jù)存儲結(jié)構(gòu)和不同的實現(xiàn)算法解決一個問題。,對學(xué)生的幾點要求,5,第1章　緒　論,討論5個問題：,1.1 數(shù)據(jù)結(jié)構(gòu)的基本概念1.2 抽象數(shù)據(jù)類型和軟件構(gòu)造方法1.4 算法和

3、算法的時間復(fù)雜度1.5 算法書寫規(guī)范,6,1.1 數(shù)據(jù)結(jié)構(gòu)的基本概念,1、舉例 建立一個學(xué)生檔案系統(tǒng)。學(xué)生表包括學(xué)號、姓名、性別、籍貫。要求：查找“王紅”是否存在。解決的方法步驟：如何記錄所有學(xué)生記錄（及選擇何種邏輯數(shù)據(jù)結(jié)構(gòu)）？選擇何種存儲結(jié)構(gòu)？若把所有記錄依次存儲在一個數(shù)組中——采用順序存儲結(jié)構(gòu)若采用指針鏈表——采用鏈?zhǔn)酱鎯Y(jié)構(gòu),7,為什么要學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)？什么是程序、軟件？ N.沃思（Nik

4、laus Wirth)教授提出： 程序=算法+數(shù)據(jù)結(jié)構(gòu)以上公式說明了如下兩個問題：（1）數(shù)據(jù)上的算法決定如何構(gòu)造和組織數(shù)據(jù)（算法→數(shù)據(jù)結(jié)構(gòu)）。（2）算法的選擇依賴于作為基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)→算法）。 軟件=程序+文檔（軟件工程的觀點）,8,電子計算機(jī)的主要用途：?早期： 主要用于數(shù)值計算。?后來： 處理逐漸擴(kuò)大到非數(shù)值計算領(lǐng)域（能處理多種復(fù)雜的具有一定結(jié)構(gòu)關(guān)系的數(shù)據(jù)）。,數(shù)值計算

5、解決問題的一般步驟：數(shù)學(xué)模型→選擇計算機(jī)語言→編出程序→測試→最終解答。數(shù)值計算的關(guān)鍵是：如何得出數(shù)學(xué)模型（方程）？程序設(shè)計人員比較關(guān)注程序設(shè)計的技巧。非數(shù)值計算問題： 數(shù)據(jù)元素之間的相互關(guān)系一般無法用數(shù)學(xué)方程加以描述,10,例1.1 電話號碼查詢問題：（1）按順序存儲方式：須遍歷表（2）按姓氏索引方式：索引 要寫出好的查找算法，取決于這張表的結(jié)構(gòu)及存儲方式。 電話號碼表的結(jié)構(gòu)和存儲方式

6、決定了查找（算法）的效率。,,?非數(shù)值計算問題：,11,例1.2 田徑賽的時間安排問題（無向圖的著色問題） ：設(shè)有六個比賽項目，規(guī)定每個選手至多可參加三個項目，有五人報名參加比賽（如下表所示）設(shè)計比賽日程表，使得在盡可能短的時間內(nèi)完成比賽。,,?非數(shù)值計算問題：,12,（1）設(shè)用如下六個不同的代號代表不同的項目：跳高 跳遠(yuǎn) 標(biāo)槍 鉛球 100米 200米A B C

7、 D E F（2）用頂點代表比賽項目不能同時進(jìn)行比賽的項目之間連上一條邊。（3）某選手比賽的項目必定有邊相連（不能同時比賽）。,,?非數(shù)值計算問題 ----田徑賽的時間安排問題解法,13,只需安排四個單位時間進(jìn)行比賽,14,非數(shù)值計算問題： 主要考慮的是設(shè)計出合適的數(shù)據(jù)結(jié)構(gòu)及相應(yīng)的算法。即：首先要考慮對相關(guān)的各種信息如何表示、組織和存儲？因此，可以認(rèn)為：數(shù)據(jù)結(jié)構(gòu)是

8、一門研究非數(shù)值計算的程序設(shè)計問題中計算機(jī)的操作對象以及它們之間的關(guān)系和操作的學(xué)科。,15,數(shù)據(jù)結(jié)構(gòu)課程的形成和發(fā)展：形成階段：60年代初期，“數(shù)據(jù)結(jié)構(gòu)”有關(guān)的內(nèi)容散見于操作系統(tǒng)、編譯原理和表處理語言等課程。1968年，“數(shù)據(jù)結(jié)構(gòu)”被列入美國一些大學(xué)計算機(jī)科學(xué)系的教學(xué)計劃。發(fā)展階段：數(shù)據(jù)結(jié)構(gòu)的概念不斷擴(kuò)充，包括了網(wǎng)絡(luò)、集合代數(shù)論、關(guān)系等“離散數(shù)學(xué)結(jié)構(gòu)”的內(nèi)容。70年代后期，我國高校陸續(xù)開設(shè)該課程。,16,,,,17,數(shù)據(jù)結(jié)構(gòu)課程

9、的地位,它是計算機(jī)專業(yè)及相關(guān)專業(yè)的核心課程之一，是計算機(jī)及相關(guān)專業(yè)的重要骨干基礎(chǔ)課程。 它針對非數(shù)值計算的程序設(shè)計問題，研究計算機(jī)的操作對象以及它們之間的關(guān)系和操作。即其研究目的是研究有效地組織和處理非數(shù)值類型數(shù)據(jù)的理論、技術(shù)和方法。,18,《數(shù)據(jù)結(jié)構(gòu)課程》所處的地位：,19,數(shù)據(jù)結(jié)構(gòu)的核心研究內(nèi)容,數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)及它們之間的關(guān)系和相應(yīng)的基本操作運(yùn)算的定義和實現(xiàn)。本書圍繞數(shù)據(jù)結(jié)構(gòu)的三種基本結(jié)構(gòu)：線性結(jié)構(gòu)（第2-

10、5章）、樹形結(jié)構(gòu)（第7章）和圖形結(jié)構(gòu)（第8章）展開討論，研究解決如下問題：一個具體問題的邏輯數(shù)據(jù)結(jié)構(gòu)是什么？適宜選用什么樣的存儲結(jié)構(gòu)？采用什么樣的操作實現(xiàn)算法效率更高？,20,2、基本術(shù)語,(1)數(shù)據(jù)：所有能被計算機(jī)識別、存儲和處理的符號的集合（包括數(shù)字、字符、聲音、圖像等信息 ）。(2)數(shù)據(jù)元素:是數(shù)據(jù)的基本單位，具有完整確定的實際意義。在計算機(jī)程序中通常作為一個整體進(jìn)行考慮和處理。一個數(shù)據(jù)元素可由若干個數(shù)據(jù)項組成。(3)數(shù)據(jù)項:

11、構(gòu)成數(shù)據(jù)元素的項目。它是數(shù)據(jù)不可分割的最小單位。(4)數(shù)據(jù)類型：指一個類型和定義在這個類型上的操作集合。例：C語言（基本類型：整型、浮點型、字符型等構(gòu)造類型：數(shù)組、結(jié)構(gòu)、聯(lián)合、指針、枚舉等）,(5)抽象數(shù)據(jù)類型（Abstruct Data Type，簡稱ADT）：是指一個數(shù)學(xué)模型以及定義在該模型上的一組操作。抽象數(shù)據(jù)類型的定義取決于它的一組邏輯特性，而與其在計算機(jī)內(nèi)部如何表示和實現(xiàn)無關(guān)。即不論其內(nèi)部結(jié)構(gòu)如何變化，只要它的數(shù)學(xué)特性不變，

12、都不影響其外部的使用。(6)抽象數(shù)據(jù)元素：抽象定義的、沒有實際含義的數(shù)據(jù)元素。,21,22,2、基本術(shù)語 (續(xù)）,(7)數(shù)據(jù)結(jié)構(gòu)：是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合?；虬凑找欢ㄟ壿嬯P(guān)系組織，并按一定存儲方法存儲的數(shù)據(jù)的集合，且需要定義一系列運(yùn)算。邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)和運(yùn)算合稱為三要素。表示為： Data_Structure=（D, R） 其中，D—元素有限集，R—關(guān)系有限集,23,,,,

13、,,,,,,數(shù)據(jù)結(jié)構(gòu)涵蓋的內(nèi)容,24,集合結(jié)構(gòu)： 僅同屬一個集合線性結(jié)構(gòu): 一對一（1:1) 樹 結(jié) 構(gòu): 一對多（1:n) 圖 結(jié) 構(gòu): 多對多 (m:n),,非線性,線 性,,邏輯結(jié)構(gòu)可細(xì)分為4類：,答：指數(shù)據(jù)元素之間的邏輯關(guān)系。即從邏輯關(guān)系上描述數(shù)據(jù)，它與數(shù)據(jù)的存儲無關(guān)，是獨(dú)立于計算機(jī)的。,解釋1： 什么叫數(shù)據(jù)的邏輯結(jié)構(gòu)？,25,（1） S=(D, R)

14、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)。,26,d1 d5

15、 d2 d4 d3,,,,,,,,,,,該結(jié)構(gòu)是非線性的。,解：上述表達(dá)式可用圖形表示為：,（2） S=(D, R) D={di | 1≤i≤5} R={(di , dj ), i<j},27,答：物理結(jié)構(gòu)亦稱存儲結(jié)構(gòu)，是數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機(jī)

16、存儲器內(nèi)的表示（或映像）。它依賴于計算機(jī)。,存儲結(jié)構(gòu)可分為4大類：,例：復(fù)數(shù)3.0－2.3i 的兩種存儲方式：,順序、鏈?zhǔn)?、索引、散?,法1：地址 內(nèi)容,法2：地址 內(nèi)容,,2字節(jié),解釋2：什么叫數(shù)據(jù)的物理結(jié)構(gòu)？,28,答：在數(shù)據(jù)的邏輯結(jié)構(gòu)上定義的操作算法。它在數(shù)據(jù)的存儲結(jié)構(gòu)上實現(xiàn)。,最常用的數(shù)據(jù)運(yùn)算有 5 種：,插入、刪除、修改、查找、排序,解釋3：什么是數(shù)據(jù)的運(yùn)算？,練習(xí)1、設(shè)有數(shù)據(jù)邏輯結(jié)構(gòu)為：li

17、ne=(D,R);其中D={01，02，03，04，05，06}；R={r}；r={，,,,}.試分析該數(shù)據(jù)結(jié)構(gòu)屬于哪種邏輯結(jié)構(gòu)。01->02->05->04->06->03線性結(jié)構(gòu),29,2、設(shè)有數(shù)據(jù)邏輯結(jié)構(gòu)為tree={D,R},其中D={01,02,03,04,05,06,07,08};R={r}；r={,,,,,,}.試分析該數(shù)據(jù)結(jié)構(gòu)屬于哪種邏輯結(jié)構(gòu).樹型,30,作業(yè),什么是邏

18、輯結(jié)構(gòu)與存儲結(jié)構(gòu)，他們之間的關(guān)系如何？,31,,設(shè)有數(shù)據(jù)邏輯結(jié)構(gòu)為：line=(D,R);其中D={a，b，c，d，e，f,g}；R={r}；r={，,,,,}.試畫出對應(yīng)的圖形并說明屬于哪種邏輯結(jié)構(gòu).,32,,將上述關(guān)系改為r={，,,,,}.試畫出對應(yīng)的圖形并說明屬于哪種邏輯結(jié)構(gòu).,33,34,1.4 什么是抽象數(shù)據(jù)類型,1 數(shù)據(jù)類型與抽象數(shù)據(jù)類型的區(qū)別？2 抽象數(shù)據(jù)類型如何定義？3 抽象數(shù)據(jù)類型如何表示和實現(xiàn)？,討論：

19、,,35,1 數(shù)據(jù)類型與抽象數(shù)據(jù)類型的區(qū)別,數(shù)據(jù)類型：是一個值的集合和定義在該值上的一組操作的總稱。,抽象數(shù)據(jù)類型：由用戶定義，用以表示應(yīng)用問題的數(shù)據(jù)模型。它由基本的數(shù)據(jù)類型構(gòu)成，并包括一組相關(guān)的服務(wù)（或稱操作）,它與數(shù)據(jù)類型實質(zhì)上是一個概念，但其特征是使用與實現(xiàn)分離，實行封裝和信息隱蔽（獨(dú)立于計算機(jī)）,,36,2 抽象數(shù)據(jù)類型如何定義,抽象數(shù)據(jù)類型可以用以下的三元組來表示： ADT = （D，R，P）,AD

20、T抽象數(shù)據(jù)類型名{ 數(shù)據(jù)對象： 數(shù)據(jù)關(guān)系： 基本操作 ： } ADT抽象數(shù)據(jù)類型名,ADT常用定義格式,,,,,數(shù)據(jù)對象,D上的關(guān)系集,D上的操作集,37,1.4.3 抽象數(shù)據(jù)類型如何表示和實現(xiàn),抽象數(shù)據(jù)類型可以通過固有的數(shù)據(jù)類型（如整型、實型、字符型等）來表示和實現(xiàn)。 （參看課本P28，線性表的抽象數(shù)據(jù)類型，思考用具體C語言如何實現(xiàn)）,注意：上機(jī)時要必須用具體語言實現(xiàn)

21、，如C或C++等,隊列的抽象數(shù)據(jù)類型定義ADT Queue{數(shù)據(jù)對象：D={ai|ai∈ElemSet, i=1,2, …,n, n≥0}數(shù)據(jù)關(guān)系：R1={|ai-1,ai∈D, i=1,2, …,n }           約定a1為隊列頭，an為隊列尾。  基本操作：   

22、 InitQueue( &Q )      操作結(jié)果：構(gòu)造一個空隊列Q。    DestroyQueue ( &Q )      初始條件：隊列Q已存在。      操作結(jié)果：銷毀隊列Q。 QueueLength( Q

23、)      初始條件：隊列Q已存在。      操作結(jié)果：返回Q的數(shù)據(jù)元素個數(shù)，即隊列的長度。,38,39,1.5 算法效率的度量,1 什么是算法？如何評判算法的好壞？2 時間復(fù)雜度和空間復(fù)雜度如何表示？3 計算舉例,討論：,40,1 什么是算法？如何評判一個算法的好壞？,常用時間復(fù)雜度來衡量

24、,算法的基本特性：,算法評價指標(biāo)：,有窮性、確定性、可行性、必有輸出,正確性、可讀性、健壯性、高效率與低存儲量需求(見課本P20),常用空間復(fù)雜度來衡量,,,好的程序設(shè)計：好算法＋好結(jié)構(gòu),算法：是對特定問題求解步驟的一種描述，它是指令的有限序列，是一系列輸入轉(zhuǎn)換為輸出的計算步驟。,有窮性：一個算法必須總是(對任何合法的輸入值)在執(zhí)行有窮步之后結(jié)束，且每一步都可在有窮時間內(nèi)完成。確定性：每條指令必須有確切的含義可行性：算法是能行得通的

25、必有輸出,41,正確性：算法應(yīng)當(dāng)滿足具體問題的需求可讀性：算法的可讀性有利于人們對算法的理解健壯性：當(dāng)輸入數(shù)據(jù)非法時，算法也能適當(dāng)?shù)刈龀龇磻?yīng)或進(jìn)行處理，而不會產(chǎn)生莫名其妙的結(jié)果。效率與低存儲需求：時間短，存儲空間少（兩者不能兼得）,42,1.3.3 算法效率的度量,求解同一個問題,可以有許多不同的算法,究竟如何評價這些算法的好壞呢? 顯然,選用的算法首先應(yīng)該是“正確的”.此外,主要考慮如下三點: (1) 執(zhí)行算法所消

26、耗的時間; (2) 執(zhí)行算法所消耗的存儲空間,其中主要考慮輔助存儲空間. (3) 算法應(yīng)該易于理解,易于編碼,易于調(diào)試等.,43,時間復(fù)雜度 (time complexity),語句頻度(Frequency Count) 語句重復(fù)執(zhí)行的次數(shù)語句的執(zhí)行時間 語句頻度×執(zhí)行一次所需時間算法的執(zhí)行時間 所有語句執(zhí)行時間的總和算法的漸近時間復(fù)雜度(asymptotic time complexity)，簡稱時間復(fù)雜度

27、 因為語句的執(zhí)行時間取決于機(jī)器的硬件速度、指令類型、以及編譯所產(chǎn)生的代碼質(zhì)量，所以將算法中基本操作的最大語句頻度作為算法執(zhí)行時間的量度，它是問題規(guī)模n 的某個函數(shù) f (n),44,時間復(fù)雜度表示法 記作T(n)=O(f (n)) （稱為大O表示法)，表示隨問題規(guī)模n 的增大，算法執(zhí)行時間的增長率和f(n) 的增長率相同。時間復(fù)雜度往往不是精確的執(zhí)行次數(shù)，而是估算的數(shù)量級，它著重體現(xiàn)的是隨著問題規(guī)模n的增大，算法執(zhí)行時間的變化趨

28、勢 時間復(fù)雜度的數(shù)量級 O (1) < O (log2n) < O (n )< O( nlog2n) < O (n2) < O (n3) < O (2n) < O (3n) < O (n!),例如在下列三個程序段中：(a) x=x+1；(b) for(i=1;i<=n;i++) x=x+1;(c) for(j=1;j<=n;j++)

29、 for(k=1;k<=n;k++) x=x+1;基本語句均為 x=x+1;程序段(a) 中頻度為1，則T(n)= O(1)；程序段(b)中頻度為n，則T(n)= O(n)；程序段(c)中頻度為n2，則T(n)= O(n2)。,時間復(fù)雜度的求解,,算法1.1的時間復(fù)雜度void sort( ElemType S[MAXSIZE]，int n) ／*對數(shù)組S中的n個數(shù)據(jù)

30、按由大到小的順序排序并輸出,n<MAXSIZE */ { for (i=1;i<n;i++) for(j=i；j<=n；j++) if( S[i]．score＜S[j]．score) { t=S[i]；S[i]=S[j]；S[j]=t；} for(i=1；i<=n； i++) prin

31、tf(“%8d%8d%8d\n”,i,S[i].no,S[i].score); }/*sort*/∵算法中if語句的執(zhí)行頻度為： n+(n-1)+(n-2)+…+3+2+1=n*(n+1)/2∴ T(n)= O(n2),加法規(guī)則 (針對并列程序段 ) T(n, m) = T1 (n) + T2 (m) = O(max (f (n), g (m

32、))) 乘法規(guī)則 (針對嵌套程序段) T (n, m) = T1 (n) * T2 (m) = O(f (n)*g (m))算法1.1中既有并列程序段又有嵌套程序段 并列程序段： T(n) = O(max(n2,n))= O(n2) 嵌套程序段： T(n) = O(f (n)*g (n))= O(n2),有的情況下，算法中基本操作重復(fù)執(zhí)行的次數(shù)還隨問題的輸入數(shù)據(jù)集不同而不同。例如：Void bub

33、ble-sort(int a[ ]，int n) for(i=1;ia[j+1]) { flag=1; a[j] ←→a[j+1]; } } },分析算法復(fù)雜度：最好情況：0次最壞情況：1+2+3+…+n-1=n(n-1)/2 平均時間復(fù)雜

34、度為:O(n2),50,空間復(fù)雜度度量（Space Complexity）,空間是指執(zhí)行算法所需用的存儲空間存儲空間的固定部分程序指令代碼的空間，常數(shù)、簡單變量、定長成分(如數(shù)組元素、結(jié)構(gòu)成員等)變量所占的空間可變部分遞歸棧所用的空間、通過malloc( )和free( ) 等函數(shù)動態(tài)使用的空間與問題規(guī)模 n 的函數(shù)關(guān)系表示為： S（n）= O（ f(n)）,52,本章小結(jié),數(shù)據(jù)結(jié)構(gòu)課程—— 數(shù)據(jù)結(jié)構(gòu)＋算法＝程序，

35、涉及數(shù)學(xué)、計算機(jī)硬件和軟件。數(shù)據(jù)結(jié)構(gòu)定義——指互相有關(guān)聯(lián)的數(shù)據(jù)元素的集合，可用data_Structure=(D,R)表示。數(shù)據(jù)結(jié)構(gòu)內(nèi)容——數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)和基本運(yùn)算 。數(shù)據(jù)結(jié)構(gòu)描述工具——抽象數(shù)據(jù)類型和C語言。算法效率——時間效率和空間效率 。,53,作業(yè)：,①課本P25 1.2，1.3，1.4，1.7，1.10，1.11 題。② 建議獨(dú)立完成輔導(dǎo)材料——第1章自測卷。③ 復(fù)習(xí)C語言，重點是結(jié)構(gòu)類型、指針和