數(shù)據(jù)結構 （C語言版）課件：第一章 緒 論

1、數(shù)據(jù)結構 （C語言版）開設本課程的必要性以及課程的特點計算機專業(yè)(或相關)重要的專業(yè)基礎課之一。主要培養(yǎng)學生分析數(shù)據(jù)、組織數(shù)據(jù)的能力，告訴學生如何編寫效率高、結構好的程序;需要有關“程序設計語言”和“離散數(shù)學”的知識作為課程的基礎;實踐性較強。第一章 緒 論1.1 數(shù)據(jù)結構討論的范疇1.2 基本概念1.3 算法和算法的量度1.1 數(shù)據(jù)結構討論的范疇Niklaus Wirth Algorithm + Data Structures = Programs程序設計:算法: 數(shù)據(jù)結構: 為計算機處理問題編制 一組指令集 處理問題的策略問題的數(shù)學模型 結構靜力分析計算 例如: 數(shù)值計算的程序設計問題 線

2、性代數(shù)方程組 環(huán)流模式方程 (球面坐標系)全球天氣預報 非數(shù)值計算的程序設計問題例一: 求一組(n個)整數(shù)中的最大值算法: ?模型：？基本操作是“比較兩個數(shù)的大小”取決于整數(shù)值的范圍例二：計算機對弈算法：?模型：?對弈的規(guī)則和策略棋盤及棋盤的格局例三：鋪設城市的煤氣管道算法：?模型：?如何規(guī)劃使得總投資花費最少？圖概括地說， 數(shù)據(jù)結構是一門討論“描述現(xiàn)實世界實體的數(shù)學模型(非數(shù)值計算)及其上的操作在計算機中如何表示和實現(xiàn)”的學科。1.2 基本概念一、數(shù)據(jù)與數(shù)據(jù)結構二、數(shù)據(jù)類型三、抽象數(shù)據(jù)類型一、數(shù)據(jù)與數(shù)據(jù)結構 所有能被輸入到計算機中，且能被計算機處理的符號(數(shù)值、字符等)的集合。數(shù)據(jù):是計算機

3、操作的對象的總稱。 是計算機處理的信息的某種特定的符號表示形式。 是數(shù)據(jù)（集合）中的一個“個體”,在計算機中通常作為一個整體進行考慮和處理。是數(shù)據(jù)結構中討論的基本單位。數(shù)據(jù)元素:如:整數(shù)“5”,字符“N”等。 -是不可分割的“原子” 其中每個款項稱為一個“數(shù)據(jù)項”它是數(shù)據(jù)結構中討論的最小單位數(shù)據(jù)元素也可以由若干款項構成。例如：描述一個學生的數(shù)據(jù)元素稱之為組合項年 月 日姓 名學 號班 號性別出生日期入學成績原子項數(shù)據(jù)結構：帶結構的數(shù)據(jù)元素的集合有一個特性相同的數(shù)據(jù)元素的集合，如果在數(shù)據(jù)元素之間存在一種或多種特定的關系，則稱為一個數(shù)據(jù)結構。指的是數(shù)據(jù)元素之間存在的關系例如，可以用三個 4 位的十

4、進制數(shù)表示一個含 12 位數(shù)的十進制數(shù)。3214,6587,9345 a1(3214),a2(6587),a3(9345)則在數(shù)據(jù)元素 a1、a2 和 a3 之間存在著“次序”關系 a1,a2、a2,a33214，6587，9345 a1 a2 a3 6587，3214，9345 a2 a1 a3例如:又例，在2行3列的二維數(shù)組a1, a2, a3, a4, a5, a6中六個元素之間存在兩個關系:行的次序關系:列的次序關系:row = ,col = , a1 a3 a5 a2 a4 a6 a1 a2 a3a4 a5 a6 a1 a2 a3 a4 a5 a6 在一維數(shù)組 a1, a2, a3,

5、 a4, a5, a6 的 6 個數(shù)據(jù)元素之間存在如下的次序關系:| i=1, 2, 3, 4, 5 數(shù)據(jù)結構是相互之間存在著某種邏輯關系的數(shù)據(jù)元素的集合?？梢?，不同的“關系”構成不同的“結構”再例，從關系或結構分，數(shù)據(jù)結構可歸結為以下四類:線性結構樹形結構圖狀結構集合結構數(shù)據(jù)結構包括“邏輯結構” 和“物理結構”兩個方面(層次):邏輯結構 是對數(shù)據(jù)元素之間的邏輯關系的描述，它可以應一個數(shù)據(jù)元素的集合和定義在此集合上的若干關系來表示;物理結構 是邏輯結構在計算機中的表示和實現(xiàn)，故又稱“存儲結構” 。數(shù)據(jù)結構的形式定義描述為:數(shù)據(jù)結構是一個二元組 Data_Structures = (D, S)其

6、中:D 是數(shù)據(jù)元素的有限集， S 是 D上關系的有限集。例如:定義 “班集體”為一個數(shù)據(jù)結構Class = (D, S)D = a, b1,bn, c1,cn, d1,dn S = R1, R2 R1 = , R2 = , , | j = 2, 3, , n 數(shù)據(jù)的存儲結構 邏輯結構在存儲器中的映象“數(shù)據(jù)元素”的映象 ？“關系”的映象 ？數(shù)據(jù)元素的映象方法：用二進制位(bit)的位串表示數(shù)據(jù)元素(321)10 = (501)8 = (101000001)2 A = (101)8 = (001000001)2關系的映象方法：（表示x, y的方法）順序映象以相對的存儲位置表示后繼關系例如:令 y

7、的存儲位置和 x 的存儲位置之間差一個常量 C而 C 是一個隱含值，整個存儲結構中只含數(shù)據(jù)元素本身的信息 x y鏈式映象以附加信息(指針)表示后繼關系需要用一個和 x 在一起的附加信息指示 y 的存儲位置y x在不同的編程環(huán)境中，存儲結構可有不同的描述方法，當用高級程序設計語言進行編程時，通常可用高級編程語言中提供的數(shù)據(jù)類型描述之。例如: 以三個帶有次序關系的整數(shù)表示一個長整數(shù)時，可利用 C 語言中提供的整數(shù)數(shù)組類型， typedef int Long_int 3定義長整數(shù)為:typedef struct int y; / 年號 Year int m; / 月號 Month int d; /

8、日號 Day DateType; / 日期類型定義“日期”為:定義“學生”為:typedef struct char id8; / 學號 char name16; / 姓名 char sex; / 性別M/F:男/女 DateType bdate; / 出生日期 Student; / 學生類型二、數(shù)據(jù)類型 在用高級程序語言編寫的程序中，必須對程序中出現(xiàn)的每個變量、常量或表達式，明確說明它們所 屬的數(shù)據(jù)類型。例如，C 語言中提供的基本數(shù)據(jù)類型有:整型 int浮點型 float字符型 char邏輯型 bool （ C+語言）雙精度型 double實型（ C+語言） 數(shù)據(jù)類型 是一個 值的集合和定義

9、在此集合上的 一組操作的總稱。 不同類型的變量，其所能取的值的范圍不同，所能進行的操作不同。三、抽象數(shù)據(jù)類型 (Abstract Data Type 簡稱ADT) 是指一個數(shù)學模型以及定義在此數(shù)學模型上的一組操作例如:“整數(shù)”是一個抽象數(shù)據(jù)類型。 其數(shù)學特性和具體的計算機或語言無關。 “抽象”的意義在于強調數(shù)據(jù)類型的數(shù)學特性。抽象數(shù)據(jù)類型還包括用戶在設計軟件系統(tǒng)時自己定義的數(shù)據(jù)類型。在構造軟件系統(tǒng)的各個相對獨立的模塊時，定義一組數(shù)據(jù)和施與這些數(shù)據(jù)之上的一組操作，并在模塊內部給出它們的表示和實現(xiàn)細節(jié)，在模塊外部使用的只是抽象的數(shù)據(jù)和抽象的操作。例如，定義抽象數(shù)據(jù)類型“復數(shù)” 數(shù)據(jù)對象： De1,

10、e2e1,e2RealSet 數(shù)據(jù)關系： R1 | e1是復數(shù)的實數(shù)部分, | e2 是復數(shù)的虛數(shù)部分 ADT Complex 基本操作： AssignComplex( &Z, v1, v2 )操作結果：構造復數(shù) Z,其實部和虛部 分別被賦以參數(shù) v1 和 v2 的值。 DestroyComplex( &Z)操作結果：復數(shù)Z被銷毀。 GetReal( Z, &realPart )初始條件：復數(shù)已存在。操作結果：用realPart返回復數(shù)Z的實部值。 GetImag( Z, &ImagPart )初始條件：復數(shù)已存在。操作結果：用ImagPart返回復數(shù)Z的虛部值。 Add( z1,z2, &s

11、um )初始條件：z1, z2是復數(shù)。操作結果：用sum返回兩個復數(shù)z1, z2 的 和值。 ADT Complex假設:z1和z2是上述定義的復數(shù)則 Add(z1, z2, z3) 操作的結果z3 = z1 + z2即為用戶企求的結果ADT 有兩個重要特征:數(shù)據(jù)抽象 用ADT描述程序處理的實體時，強調的是其本質的特征、其所能完成的功能以及它和外部用戶的接口（即外界使用它的方法）數(shù)據(jù)封裝 將實體的外部特性和其內部實現(xiàn)細節(jié)分離，并且對外部用戶隱藏其內部實現(xiàn)細節(jié)抽象數(shù)據(jù)類型的描述方法抽象數(shù)據(jù)類型可用（D，S，P）三元組表示其中，D 是數(shù)據(jù)對象， S 是 D 上的關系集， P 是對 D 的基本操作集

12、。 ADT 抽象數(shù)據(jù)類型名 數(shù)據(jù)對象：數(shù)據(jù)對象的定義 數(shù)據(jù)關系：數(shù)據(jù)關系的定義 基本操作：基本操作的定義 ADT 抽象數(shù)據(jù)類型名其中基本操作的定義格式為:基本操作名（參數(shù)表） 初始條件：初始條件描述 操作結果：操作結果描述 賦值參數(shù) 只為操作提供輸入值；引用參數(shù) 以&打頭，除可提供輸入值外，還將返回操作結果。初始條件 描述了操作執(zhí)行之前數(shù)據(jù)結構和參數(shù)應滿足的條件，若不滿足，則操作失敗，并返回相應出錯信息。操作結果 說明了操作正常完成之后，數(shù)據(jù)結構的變化狀況和應返回的結果。若初始條件為空，則省略之。抽象數(shù)據(jù)類型的表示和實現(xiàn) 抽象數(shù)據(jù)類型需要通過固有數(shù)據(jù)類型(高級編程語言中已實現(xiàn)的數(shù)據(jù)類型)來實現(xiàn)

13、。例如，對以上定義的復數(shù)typedef struct float realpart； float imagpart；complex；/ -存儲結構的定義/ -基本操作的函數(shù)原型說明void Assign( complex &Z, float realval, float imagval )；/ 構造復數(shù) Z,其實部和虛部分別被賦以參數(shù) / realval 和 imagval 的值float GetReal( cpmplex Z )； / 返回復數(shù) Z 的實部值float Getimag( cpmplex Z )； / 返回復數(shù) Z 的虛部值void add( complex z1, compl

14、ex z2, complex &sum )； / 以 sum 返回兩個復數(shù) z1, z2 的和 / -基本操作的實現(xiàn)void add( complex z1, complex z2, complex &sum ) / 以 sum 返回兩個復數(shù) z1, z2 的和 sum.realpart = z1.realpart + z2.realpart; sum.imagpart = z1.imagpart + z2.imagpart; 其它省略 1.3 算法和算法的衡量一、算法二、算法設計的原則三、算法效率的衡量方法和準則四、算法的存儲空間需求 算法是為了解決某類問題而規(guī)定的一個有限長的操作序列。一個

15、算法必須滿足以下五個重要特性：1有窮性 2確定性 3可行性4有輸入 5有輸出一、算法1有窮性 對于任意一組合法輸入值，在執(zhí)行有窮步驟之后一定能結束，即：算法中的每個步驟都能在有限時間內完成； 2確定性 對于每種情況下所應執(zhí)行的操作，在算法中都有確切的規(guī)定，使算法的執(zhí)行者或閱讀者都能明確其含義及如何執(zhí)行。并且在任何條件下，算法都只有一條執(zhí)行路徑；3可行性 算法中的所有操作都必須足夠基本，都可以通過已經實現(xiàn)的基本操作運算有限次實現(xiàn)之；4有輸入 作為算法加工對象的量值，通常體現(xiàn)為算法中的一組變量。有些輸入量需要在算法執(zhí)行過程中輸入，而有的算法表面上可以沒有輸入，實際上已被嵌入算法之中； 5有輸出 它

16、是一組與“輸入”與確定關系的量值，是算法進行信息加工后得到的結果，這種確定關系即為算法的功能。二、算法設計的原則設計算法時，通常應考慮達到以下目標：1正確性2. 可讀性3健壯性4高效率與低存儲量需求1正確性 首先，算法應當滿足以特定的“規(guī)格說明”方式給出的需求。 其次，對算法是否“正確”的理解可以有以下四個層次：a程序中不含語法錯誤；b程序對于幾組輸入數(shù)據(jù)能夠得出滿足要求的結果； c程序對于精心選擇的、典型、苛刻且?guī)в械箅y性的幾組輸入數(shù)據(jù)能夠得出滿足要求的結果；通常以第 c 層意義的正確性作為衡量一個算法是否合格的標準。 d程序對于一切合法的輸入數(shù)據(jù)都能得出滿足要求的結果；2. 可讀性 算法主

17、要是為了人的閱讀與交流，其次才是為計算機執(zhí)行。因此算法應該易于人的理解；另一方面，晦澀難讀的程序易于隱藏較多錯誤而難以調試；3健壯性 當輸入的數(shù)據(jù)非法時，算法應當恰當?shù)刈鞒龇从郴蜻M行相應處理，而不是產生莫名奇妙的輸出結果。并且，處理出錯的方法不應是中斷程序的執(zhí)行，而應是返回一個表示錯誤或錯誤性質的值，以便在更高的抽象層次上進行處理。4高效率與低存儲量需求 通常，效率指的是算法執(zhí)行時間；存儲量指的是算法執(zhí)行過程中所需的最大存儲空間。兩者都與問題的規(guī)模有關。三、算法效率的 衡量方法和準則通常有兩種衡量算法效率的方法: 事后統(tǒng)計法事前分析估算法缺點：1。必須執(zhí)行程序 2。其它因素掩蓋算法本質和算法執(zhí)

18、行時間相關的因素：1算法選用的策略2問題的規(guī)模3編寫程序的語言4編譯程序產生的機器代碼的質量5計算機執(zhí)行指令的速度 一個特定算法的“運行工作量”的大小，只依賴于問題的規(guī)模（通常用整數(shù)量n表示），或者說，它是問題規(guī)模的函數(shù)。 假如，隨著問題規(guī)模 n 的增長，算法執(zhí)行時間的增長率和 f(n) 的增長率相同，則可記作：T (n) = O(f(n)稱T (n) 為算法的(漸近)時間復雜度如何估算 算法的時間復雜度？算法 = 控制結構 + 原操作 （固有數(shù)據(jù)類型的操作）算法的執(zhí)行時間 =原操作(i)的執(zhí)行次數(shù)原操作(i)的執(zhí)行時間 算法的執(zhí)行時間 與 原操作執(zhí)行次數(shù)之和 成正比 從算法中選取一種對于所研究的問題來說是 基本操作 的原操作，以該基本操作 在算法中重復執(zhí)行的次數(shù) 作為算法運行時間的衡量準則。例一兩個矩陣相乘void mult(int a, int b, int& c ) / 以二維數(shù)組存儲矩陣元素，c 為 a 和 b 的乘積 for (i=1; i=n; +i) for (j=1; j=n; +j) ci,j = 0; for (