數據結構-使用c語言朱戰(zhàn)立

1、教材：朱戰(zhàn)立編著，數據結構——使用C語言（第3版），西安交通大學出版社，2003年,數 據 結 構,2,學時數：70（50學時授課＋20學時上機） 教材：朱戰(zhàn)立編著，數據結構（使用C語言）第3版，西 安交通大學出版社 ，2003年參考書：[1]嚴蔚敏等，數據結構（C語言版），清華大學出版社[2] 數據結構學習指導與典型題解，朱戰(zhàn)立等編著，西安交通大學出版社 ，2002年,3,內 容 安 排,4,1、上課認

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

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

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

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

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

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

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

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

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

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

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

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

14、D={ a, b, c, d, e, f } R={(a,e), (b,c), (c,a), (e,f), (f,d)},解： 上述表達式可用圖形表示為：,b c a e f d,此結構為線性的。,,,,,,例：用圖形表示下列數據結構，并指出它們是屬于線性結構還是非線性結構。,26,d1 d5

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

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

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

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

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

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

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

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

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

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

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

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

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

28、勢 時間復雜度的數量級 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)。,時間復雜度的求解,,算法1.1的時間復雜度void sort( ElemType S[MAXSIZE]，int n) ／*對數組S中的n個數據

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),有的情況下，算法中基本操作重復執(zhí)行的次數還隨問題的輸入數據集不同而不同。例如：Void bub

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

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

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