《數據結構》(C語言版)第一章-緒論

1、數據結構教材: 數據結構（C語言版） 嚴蔚敏 吳偉民 編著 清華大學出版社計算機科學與技術學院12開設本課程的背景： 數據結構是計算機相關專業(yè)的一門重要的專業(yè)基礎課。它主要研究計算機加工對象的邏輯結構、在計算機中的存儲結構以及實現各種基本操作的算法。3本課程講述的主要內容： 分別講述數據結構的基本概念、線性表、棧和隊列、串、數組和廣義表、樹和二叉樹、圖、查找、排序等內容。4數據結構在計算機科學中的地位 數據結構是計算機軟件和計算機應用專業(yè)的核心課程之一，由于在計算機系統(tǒng)軟件和應用軟件中都要用到各種數據結構，要想更有效地使用計算機，就必須學習數據結構的有關知識。 程序設計的實質是對實際問題選擇一

2、種好的數據結構，加之設計一個好的算法，而好的算法在很大程度上取決于描述實際問題的數據結構。結構運算邏輯結構存儲結構+數據結構數據結構算法+程序瑞士計算機科學家沃思(N.Wirth)教授提出： 結構運算邏輯結構存儲結構+數據結構數據結構算法+程序瑞士計算機科學家沃思(N.Wirth)教授提出： 5數據結構在軟件從業(yè)人員的知識與技能結構中的地位編程語言解決問題的思想6 任何受過專業(yè)訓練的程序員，對“數據結構”這門課程中涉及到的各種數據結構都不會陌生，但是在實際的編程工作中，大部分的數據結構都不會用到，而且也永遠都不會用到。雖然如此，深入地理解基本數據結構的概念和實現細節(jié)，仍然是每個程序員的任務。這

3、不僅僅是因為，掌握這些知識將有利于更加正確和靈活地應用它們，而且也是因為，對于語言背后的實現細節(jié)的求知欲是一個優(yōu)秀程序員的素質。 -摘自最基礎的數據結構7 1.1 什么是數據結構第一章 緒論1.3 算法和算法分析1.2 基本概念和術語81.1 什么是數據結構程序設計: 為計算機處理問題編制 一組指令集。 算法: 處理問題的策略。數據結構: 問題的數學模型。 程序 = 算法 + 數據結構 91.2 基本概念和術語一、數據與數據結構二、數據類型三、抽象數據類型10數據（data)：所有能被輸入到計算機中，且被計算機處理的符號的集合 ，是計算機操作的對象的總稱。數據元素（data element）：

4、是數據（集合）中的一個“個體”，是數據的基本單位，由若干個數據項組成，也稱結點、元素、頂點或記錄。一、數據與數據結構11 數據項：是數據結構中討論的最小單位。例如：描述一個學生基本信息的數據元素可以是稱之為組合項學號姓名性別專業(yè)班級出生日期籍貫年月日12數據結構(data structure)：是指互相之間存在著一種或多種關系的數據元素的集合?；蛘哒f，數據結構是帶結構的數據元素的集合。13集合結構：數據元素間 “同屬于一個集合”數據的邏輯結構可歸結為以下四類:線性結構：一個對一個樹形結構：一個對多個圖狀結構：多個對多個14數據的邏輯結構：只抽象反映數據元素的邏輯關系。數據的存儲結構：邏輯結構在

5、存儲器中的映象。15關系的映象方法：（表示x, y的方法）1、順序映象以相對的存儲位置表示后繼關系。例如:令 y 的存儲位置和 x 的存儲位置之間差一個常量 C。 而 C 是一個隱含值，整個存儲結構中只含數據元素本身的信息 x y162、鏈式映象以附加信息(指針)表示后繼關系。 需要用一個和 x 在一起的附加信息指示 y 的存儲位置。y x17二、數據類型 在用高級程序語言編寫的程序中，必須對程序中出現的每個變量、常量或表達式，明確說明它們所屬的數據類型。18例：C語言中，提供int, char, float等基本數據類型，數組、結構體、共用體、枚舉等構造數據類型指針、空(void)類型等。用

6、戶也可用typedef 自己定義數據類型typedef struct int num; char name20; float score; STUDENT;STUDENT stu1,stu2, *p;19 數據類型 是一個 值的集合和定義在此集合上的 一組操作的總稱。 不同類型的變量，其所能取的值的范圍不同，所能進行的操作不同。20數據類型可以分為兩類: 一類是原子類型。另一類是結構類型。引入數據類型的目的： 從硬件的角度看，是作為解釋計算機內存中信息含義的一種手段。 對使用數據類型的用戶來說，實現了信息的隱蔽，即將一切用戶不必了解的細節(jié)都封裝在類型中。21三、抽象數據類型 (Abstract

7、 Data Type 簡稱ADT)ADT定義： 指一個數學模型以及定義在該模型上的一組操作。 “抽象”的意義在于數據類型的數學抽象特性。22 例如：矩陣 +（求轉置、加、乘、求逆、求特征值） 構成一個矩陣的抽象數據類型。 23ADT 抽象數據類型名 數據對象：數據對象的定義 數據關系：數據關系的定義 基本操作：基本操作的定義 ADT 抽象數據類型名其中基本操作的定義格式為:基本操作名（參數表） 初始條件：初始條件描述 操作結果：操作結果描述 24賦值參數:只為操作提供輸入值。引用參數:以&打頭，除可提供輸入值外，還將返回操作結果。初始條件:描述了操作執(zhí)行之前數據結構和參數應滿足的條件，若不滿足

8、，則操作失敗，并返回相應出錯信息。操作結果:說明了操作正常完成之后，數據結構的變化狀況和應返回的結果。若初始條件為空，則省略之。25例如，抽象數據類型復數的定義： 數據對象： De1,e2e1,e2RealSet 數據關系： R1 | e1是復數的實數部分 | e2 是復數的虛數部分 ADT Complex 26基本操作： AssignComplex( &Z, v1, v2 ) 操作結果：構造復數 Z,其實部和虛部 分別被賦以參數 v1 和 v2 的值。 DestroyComplex( &Z) 操作結果：復數Z被銷毀。 GetReal( Z, &realPart ) 初始條件：復數已存在。 操

9、作結果：用realPart返回復數Z的實部值。27 GetImag( Z, &ImagPart ) 初始條件：復數已存在。 操作結果：用ImagPart返回復數Z的虛部值。 Add( z1,z2, &sum ) 初始條件：z1, z2是復數。 操作結果：用sum返回兩個復數z1, z2 的 和值。 ADT Complex28假設:z1和z2是上述定義的復數則 Add(z1, z2, z3) 操作的結果z3 = z1 + z2即為用戶所求的結果29ADT 有兩個重要特征:數據抽象： 用ADT描述程序處理的實體時，強調的是其本質的特征、其所能完成的功能以及它和外部用戶的接口（即外界使用它的方法）。

10、數據封裝： 將實體的外部特性和其內部實現細節(jié)分離，并且對外部用戶隱藏其內部實現細節(jié)。30ADT的表示和實現： 抽象數據類型需要通過固有數據類型(高級編程語言中已實現的數據類型)來實現。例如，對以上定義的復數。31typedef struct float realpart； float imagpart；complex；/ -存儲結構的定義/ -基本操作的函數原型說明void Assign( complex &Z, float realval, float imagval )； / 構造復數 Z,其實部和虛部分別被賦以 /參數 realval 和 imagval 的值32float GetRea

11、l( complex Z )； / 返回復數 Z 的實部值float Getimag( complex Z )； / 返回復數 Z 的虛部值void add( complex z1, complex z2, complex &sum )； / 以 sum 返回兩個復數 z1, z2 的和 33/ -基本操作的實現void add( complex z1, complex z2, complex &sum ) / 以 sum 返回兩個復數 z1, z2 的和 sum.realpart = z1.realpart + z2.realpart; sum.imagpart = z1.imagpart

12、+ z2.imagpart; 其它省略 34一、算法的定義二、算法設計的原則三、算法效率的衡量方法和準則四、算法的存儲空間需求1.3 算法和算法分析35 算法是對特定問題求解步驟的描述，是指令的有限序列。1.有窮性 2.確定性 3.可行性4.有輸入 5.有輸出一、算法的定義一個算法必須滿足以下五個重要特性：361.有窮性：對于任意一組合法輸入值，在執(zhí)行有窮步驟之后一定能結束，即算法中的每個步驟都能在有限時間內完成。 2.確定性：對于每種情況下所應執(zhí)行的操作，在算法中都有確切的規(guī)定，使算法的執(zhí)行者或閱讀者都能明確其含義及如何執(zhí)行。并且在任何條件下，算法都只有一條執(zhí)行路徑。373.可行性：算法中的

13、所有操作都必須足夠基本，都可以通過已經實現的基本操作運算有限次實現之。4.有輸入：有零個或多個輸入，取自特定的對象集合。5.有輸出：有一個或多個輸出，是算法進行信息加工后得到的結果。38二、算法設計的原則 設計算法時，通常應考慮達到以下目標：1正確性2. 可讀性3健壯性4高效率與低存儲量需求391.正確性：在合理的數據輸入下，能在有限的運算時間內得到正確結果。對算法是否“正確”的理解可以有以下四個層次： a程序中不含語法錯誤； b程序對于幾組輸入數據能夠得出滿足要求的結果； c程序對于精心選擇的、典型、苛刻切帶有刁難性的幾組輸入數據能夠得出滿足要求的結果； d程序對于一切合法的輸入數據都能得出

14、滿足要求的結果；402.可讀性：易于人對算法的理解；另一方面，晦澀難讀的程序易于隱藏較多錯誤而難以調試；3.健壯性：當輸入的數據非法時，算法應當恰當地作出反映或進行相應處理，而不是產生莫名奇妙的輸出結果。并且，處理出錯的方法不應是中斷程序的執(zhí)行，而應是返回一個表示錯誤或錯誤性質的值，以便在更高的抽象層次上進行處理。414.高效率與低存儲量需求： 效率指的是算法執(zhí)行時間。 存儲量指的是算法執(zhí)行過程中所需的最大存儲空間。 兩者都與問題的規(guī)模有關。42三、算法效率的衡量方法和準則P1543 從算法中選取一種對于所研究的問題來說是 基本操作 的原操作，以該基本操作 在算法中重復執(zhí)行的次數 作為算法運行

15、時間的衡量準則。44void mult(int a, int b, int& c ) / 以二維數組存儲矩陣元素，c 為 a 和 b 的乘積 for (i=1; i=n; +i) for (j=1; j=n; +j) ci,j = 0; for (k=1; k=n; +k) ci,j += ai,k*bk,j; /for /mult基本操作: 乘法操作時間復雜度: O(n3)例1 兩個矩陣相乘45例2 +x; s=0;T(n)=(1) T(n)= O(n)例3 for (i=1; i=n; +i) +x; s+=x;例4 for( i=2; i=n; +i ) for( j=2; j=i-1;

16、 +j ) +x; ai,j=x; T(n)= O(n2)46 T(n)= O(log2n)例5 int n=8, count=0; for (int i=1; i=n; i*=2) count+;例6 int n=8, count=0;for (int i=1; i=n; i*=2) for (int j=1; j=n; j+) count+; T(n)= O(nlog2n)47時間復雜度隨n變化情況的比較時間復雜度n=8(23)n=10n=100n=1000O(1)1111O(log2n)33.3226.6449.966O(n)8101001000O(nlog2n)2433.22664.49966O(n2)6410010000106(1)(log2n)(n)(n2)(n3)(2n) 48 change = FALSE; / change 為元素進行交換標志 for (j=0; j aj+1) aj aj+1; change = TRUE ; / 一趟起泡void bubble_sort(int& a, int n)