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

1、教材：朱戰(zhàn)立編著，數(shù)據(jù)結(jié)構(gòu)——使用C語(yǔ)言（第3版），西安交通大學(xué)出版社，2003年,數(shù) 據(jù) 結(jié) 構(gòu),2,學(xué)時(shí)數(shù)：70（50學(xué)時(shí)授課＋20學(xué)時(shí)上機(jī)） 教材：朱戰(zhàn)立編著，數(shù)據(jù)結(jié)構(gòu)（使用C語(yǔ)言）第3版，西 安交通大學(xué)出版社 ，2003年參考書：[1]嚴(yán)蔚敏等，數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版），清華大學(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ī)分兩部分：平時(shí)成績(jī)（包括出勤和上機(jī)實(shí)驗(yàn)）占20%，期末成績(jī)占80%。3、課后需要多讀課文和參考書，上網(wǎng)查看相關(guān)內(nèi)容，在理解基本內(nèi)容的基礎(chǔ)上，多看、多做習(xí)題。4、上機(jī)實(shí)驗(yàn)十分重要，一定要在上機(jī)前做好充分準(zhǔn)備，多采用不同的數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)和不同的實(shí)現(xiàn)算法解決一個(gè)問(wèn)題。,對(duì)學(xué)生的幾點(diǎn)要求,5,第1章　緒　論,討論5個(gè)問(wèn)題：,1.1 數(shù)據(jù)結(jié)構(gòu)的基本概念1.2 抽象數(shù)據(jù)類型和軟件構(gòu)造方法1.4 算法和

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

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

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

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

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

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

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

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

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

12、都不影響其外部的使用。(6)抽象數(shù)據(jù)元素：抽象定義的、沒有實(shí)際含義的數(shù)據(jù)元素。,21,22,2、基本術(shù)語(yǔ) (續(xù)）,(7)數(shù)據(jù)結(jié)構(gòu)：是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合?；虬凑找欢ㄟ壿嬯P(guān)系組織，并按一定存儲(chǔ)方法存儲(chǔ)的數(shù)據(jù)的集合，且需要定義一系列運(yùn)算。邏輯結(jié)構(gòu)、存儲(chǔ)結(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)： 僅同屬一個(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ǔ)無(wú)關(guān)，是獨(dú)立于計(jì)算機(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)亦稱存儲(chǔ)結(jié)構(gòu)，是數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)

16、存儲(chǔ)器內(nèi)的表示（或映像）。它依賴于計(jì)算機(jī)。,存儲(chǔ)結(jié)構(gòu)可分為4大類：,例：復(fù)數(shù)3.0－2.3i 的兩種存儲(chǔ)方式：,順序、鏈?zhǔn)?、索引、散?,法1：地址 內(nèi)容,法2：地址 內(nèi)容,,2字節(jié),解釋2：什么叫數(shù)據(jù)的物理結(jié)構(gòu)？,28,答：在數(shù)據(jù)的邏輯結(jié)構(gòu)上定義的操作算法。它在數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)上實(shí)現(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)與存儲(chǔ)結(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={，,,,,}.試畫出對(duì)應(yīng)的圖形并說(shuō)明屬于哪種邏輯結(jié)構(gòu).,32,,將上述關(guān)系改為r={，,,,,}.試畫出對(duì)應(yīng)的圖形并說(shuō)明屬于哪種邏輯結(jié)構(gòu).,33,34,1.4 什么是抽象數(shù)據(jù)類型,1 數(shù)據(jù)類型與抽象數(shù)據(jù)類型的區(qū)別？2 抽象數(shù)據(jù)類型如何定義？3 抽象數(shù)據(jù)類型如何表示和實(shí)現(xiàn)？,討論：

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

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

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

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

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

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

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

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

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

28、勢(shì) 時(shí)間復(fù)雜度的數(shù)量級(jí) O (1) < O (log2n) < O (n )< O( nlog2n) < O (n2) < O (n3) < O (2n) < O (3n) < O (n!),例如在下列三個(gè)程序段中：(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;基本語(yǔ)句均為 x=x+1;程序段(a) 中頻度為1，則T(n)= O(1)；程序段(b)中頻度為n，則T(n)= O(n)；程序段(c)中頻度為n2，則T(n)= O(n2)。,時(shí)間復(fù)雜度的求解,,算法1.1的時(shí)間復(fù)雜度void sort( ElemType S[MAXSIZE]，int n) ／*對(duì)數(shù)組S中的n個(gè)數(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語(yǔ)句的執(zhí)行頻度為： n+(n-1)+(n-2)+…+3+2+1=n*(n+1)/2∴ T(n)= O(n2),加法規(guī)則 (針對(duì)并列程序段 ) T(n, m) = T1 (n) + T2 (m) = O(max (f (n), g (m

32、))) 乘法規(guī)則 (針對(duì)嵌套程序段) 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ù)還隨問(wèn)題的輸入數(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 平均時(shí)間復(fù)雜

34、度為:O(n2),50,空間復(fù)雜度度量（Space Complexity）,空間是指執(zhí)行算法所需用的存儲(chǔ)空間存儲(chǔ)空間的固定部分程序指令代碼的空間，常數(shù)、簡(jiǎn)單變量、定長(zhǎng)成分(如數(shù)組元素、結(jié)構(gòu)成員等)變量所占的空間可變部分遞歸棧所用的空間、通過(guò)malloc( )和free( ) 等函數(shù)動(dòng)態(tài)使用的空間與問(wèn)題規(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ì)算機(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)、存儲(chǔ)結(jié)構(gòu)和基本運(yùn)算 。數(shù)據(jù)結(jié)構(gòu)描述工具——抽象數(shù)據(jù)類型和C語(yǔ)言。算法效率——時(shí)間效率和空間效率 。,53,作業(yè)：,①課本P25 1.2，1.3，1.4，1.7，1.10，1.11 題。② 建議獨(dú)立完成輔導(dǎo)材料——第1章自測(cè)卷。③ 復(fù)習(xí)C語(yǔ)言，重點(diǎn)是結(jié)構(gòu)類型、指針和