數(shù)據(jù)結(jié)構(gòu)課件：第一章 緒論

1、第一章 緒論 第一節(jié) 數(shù)據(jù)結(jié)構(gòu)討論的范疇算法+數(shù)據(jù)結(jié)構(gòu) = 程序設計 很多數(shù)值計算問題的數(shù)學模型通?？捎靡唤M線性或非線性的代數(shù)方程組或微分方程組來描述，而大量非數(shù)值計算問題的數(shù)學模型正是本門課程要討論的數(shù)據(jù)結(jié)構(gòu)。 例一、求 n 個整數(shù)中的最大值。這似乎不成問題，但如果這些整數(shù)的值有可能達到1012，那么對32位的計算機來說，就存在一個如何表示的問題。例例二、交叉路口的紅綠燈管理。如今十字路口橫豎兩個方向都有三個紅綠燈，分別控制左拐、直行和右拐，那么如何控制這些紅綠燈既使交通不堵塞，又使流量最大呢？例三、煤氣管道的鋪設問題。如右圖需為城市的各小區(qū)之間鋪設煤氣管道，對 n 個小區(qū)只需鋪設 n-1

2、條管線，由于地理環(huán)境不同等因素使各條管線所需投資不同(如圖上所標識)，如何使投資成本最低？什么是數(shù)據(jù)結(jié)構(gòu)?計算機的操作對象的關(guān)系更加復雜，操作形式不再是單純的數(shù)值計算，而更多地是對這些具有一定關(guān)系的數(shù)據(jù)進行組織管理，將此稱為非數(shù)值性處理。數(shù)據(jù)結(jié)構(gòu)是一門討論“描述現(xiàn)實世界實體的數(shù)學模型(非數(shù)值計算)及其上的操作在計算機中如何表示和實現(xiàn)”的學科。 要使計算機能夠更有效地進行這些非數(shù)值性處理，就必須弄清楚這些操作對象的特點，在計算機中的表示方式以及各個操作的具體實現(xiàn)手段。這些就是數(shù)據(jù)結(jié)構(gòu)這門課程研究的主要內(nèi)容。1.2.1 基本概念和術(shù)語 數(shù)據(jù)是所有能被輸入到計算機中，且能被計算機處理的符號(數(shù)字、字

3、符等)的集合，它是計算機操作對象的總稱。 數(shù)據(jù)是個集合，如果用集合的表示方法來寫的話，就是數(shù)據(jù)=x|x是計算機操作的對象數(shù)據(jù)元素是數(shù)據(jù)(集合)中的一個個體，在計算機中通常作為一個整體進行考慮和處理，是數(shù)據(jù)結(jié)構(gòu)中討論的基本單位。兩類數(shù)據(jù)元素 一類是不可分割的“原子”型數(shù)據(jù)元素，如：整數(shù)“5”，字符 “N” 等 另一類是由多個款項構(gòu)成的數(shù)據(jù)元素，其中每個款項被稱為一個“數(shù)據(jù)項”。 例如描述一個學生的信息的數(shù)據(jù)元素可由下列6個數(shù)據(jù)項組成。數(shù)據(jù)項是數(shù)據(jù)結(jié)構(gòu)中討論的最小單位。 在由多個數(shù)據(jù)項構(gòu)成的數(shù)據(jù)元素中必定存在關(guān)鍵字。 關(guān)鍵字指的是能識別一個或多個數(shù)據(jù)元素的數(shù)據(jù)項。若能起唯一識別作用，則稱之為 “主

4、” 關(guān)鍵字，否則稱之為 “次” 關(guān)鍵字。數(shù)據(jù)對象是具有相同特性的數(shù)據(jù)元素的集合，如：整數(shù)、實數(shù)等。它是數(shù)據(jù)的一個子集。 在同一個數(shù)學模型中的數(shù)據(jù)元素必然具有相同特性。 1.2.2 數(shù)據(jù)結(jié)構(gòu)若在特性相同的數(shù)據(jù)元素集合中的數(shù)據(jù)元素之間存在一種或多種特定的關(guān)系，則稱該數(shù)據(jù)元素的集合為數(shù)據(jù)結(jié)構(gòu)“換句話說，數(shù)據(jù)結(jié)構(gòu)是帶“結(jié)構(gòu)”的數(shù)據(jù)元素的集合?！敖Y(jié)構(gòu)”即指數(shù)據(jù)元素之間存在的關(guān)系。數(shù)據(jù)結(jié)構(gòu)是一堆數(shù)據(jù)元素和這些數(shù)據(jù)元素之間的關(guān)系的總和。 例 可以用下述數(shù)據(jù)結(jié)構(gòu)來描述2行3列的矩陣：它是一個含6個數(shù)據(jù)元素a1,a2,a3,a4,a5,a6 的集合，且集合上存在“行關(guān)系”和“列關(guān)系”兩個次序關(guān)系，其中行關(guān)系為，

5、列關(guān)系為，。 意為 x 和 y 之間存在 x領先于y 的次序關(guān)系。例某校一個年級有兩個班，由一個級主任帶班，每個班按所住宿舍分組，他們之間的關(guān)系可如下描述： ，,， 數(shù)據(jù)結(jié)構(gòu)的形式定義 數(shù)據(jù)結(jié)構(gòu)是一個二元組Data_Structures = ( D,S ) 其中：D是數(shù)據(jù)元素的有限集，S是D上關(guān)系的有限集。 按關(guān)系或結(jié)構(gòu)分，數(shù)據(jù)結(jié)構(gòu)可歸結(jié)為以下四類： 數(shù)據(jù)結(jié)構(gòu)的兩個方面 包括數(shù)據(jù)的“邏輯結(jié)構(gòu)”和數(shù)據(jù)的“物理結(jié)構(gòu)”兩個方面 數(shù)據(jù)邏輯結(jié)構(gòu)是對數(shù)據(jù)元素之間存在的邏輯關(guān)系的描述，它可以用一個數(shù)據(jù)元素的集合和定義在此集合上的若干關(guān)系表示。數(shù)據(jù)物理結(jié)構(gòu)是數(shù)據(jù)邏輯結(jié)構(gòu)在計算機中的表示和實現(xiàn)，故又稱數(shù)據(jù)存儲結(jié)

6、構(gòu)。 存儲結(jié)構(gòu) 存儲結(jié)構(gòu)是邏輯結(jié)構(gòu)在存儲器中的映象，它包含數(shù)據(jù)元素的映象和關(guān)系的映象。 有兩種表示方法： 以的有序?qū)槔?即x和y在邏輯上有先后關(guān)系一為“順序映象”。以 “y 相對于 x 的存儲位置” 表示 “y 是x的后繼”，(即x和y在存儲位置上是有先后關(guān)系的)由此得到的數(shù)據(jù)存儲結(jié)構(gòu)為“順序存儲結(jié)構(gòu)”。二為“鏈式映象”。以和x綁定在一起的附加信息(指針)表示后繼關(guān)系， (即x和y在存儲位置上是沒有先后關(guān)系的)這個指針即為 y 的存儲地址，由此得到的數(shù)據(jù)存儲結(jié)構(gòu)為鏈式存儲結(jié)構(gòu)。 1.2.3 數(shù)據(jù)類型和抽象數(shù)據(jù)類型 數(shù)據(jù)類型是一個“值”的集合和定義在此集合上的“一組操作”的總稱。 程序中對變量

7、或常量說明其所屬類型的作用是，對它們加上兩個約束條件：一是可取值的范圍，二是可進行的操作。 抽象數(shù)據(jù)類型（Abstract Data Type 簡稱 ADT）是指一個數(shù)學模型以及定義在此數(shù)學模型上的一組操作。 抽象數(shù)據(jù)類型的形式描述為：ADT = ( D，S，P )其中：D 是數(shù)據(jù)對象，S 是 D 上的關(guān)系集，P 是 D 的基本操作集。 ADT 抽象數(shù)據(jù)類型名 數(shù)據(jù)對象： 數(shù)據(jù)對象的定義 數(shù)據(jù)關(guān)系： 數(shù)據(jù)關(guān)系的定義 基本操作： 基本操作的定義 ADT 抽象數(shù)據(jù)類型名例:抽象數(shù)據(jù)類型復數(shù)的定義ADT Complex 數(shù)據(jù)對象：D = e1,e2 | e1,e2 RealSet 數(shù)據(jù)關(guān)系：R1 =

8、 | e1是復數(shù)的實部，e2是復數(shù)的虛部 基本操作：InitComplex( &Z, v1, v2 )操作結(jié)果：構(gòu)造復數(shù)Z，其實部和虛部分別被賦以參數(shù)v1和v2的值。DestroyComplex( &Z)初始條件：復數(shù)已存在。操作結(jié)果：復數(shù)Z被銷毀。GetReal( Z, &realPart )初始條件：復數(shù)已存在。操作結(jié)果：用 realPart 返回復數(shù)Z的實部值。GetImag( Z, &ImagPart )初始條件：復數(shù)已存在。操作結(jié)果：用 ImagPart 返回復數(shù)Z的虛部值。 Add( z1,z2, &sum )初始條件：z1，z2 是復數(shù)。操作結(jié)果：用sum返回兩個復數(shù)z1，z2的

9、和值。 ADT Complex常見的特殊約定#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define OVERFLOW -1常見的特殊約定賦值參數(shù)只為操作提供輸入值；引用參數(shù)以&打頭， 除可提供輸入值外，還將返回操作結(jié)果。 成組賦值 （變量名1，.，變量名n）=（表達式 1 ， .，表達式n）；結(jié)構(gòu)賦值 結(jié)構(gòu)名1 = 結(jié)構(gòu)名2；結(jié)構(gòu)名 =（值1，值2，.，值n）；條件賦值 變量名 = 條件表達式 ? 表達式1：表達式2；交換賦值 變量名1 變量名2；1.3.1 算法及其設計原則 算法是對問題求解過程的一種描述，是為解決一個或

10、一類問題給出的一個確定的、有限長的操作序列。 算法必須滿足五個重要特性 (1) 有窮性 對于任意一組合法的輸入值，在執(zhí)行有窮步驟之后一定能結(jié)束。即算法中的操作步驟為有限個，且每個步驟都能在有限時間內(nèi)完成。(2) 確定性 對于每種情況下所應執(zhí)行的操作，在算法中都有確切的規(guī)定，使算法的執(zhí)行者或閱讀者都能明確其含義及如何執(zhí)行。并且在任何條件下，算法都只有一條執(zhí)行路徑。表現(xiàn)在對算法中每一步的描述都沒有二義性，只要輸入相同，初始狀態(tài)相同，則無論執(zhí)行多少遍，所得結(jié)果都應該相同。 (3) 可行性 算法中的所有操作都必須足夠基本，都可以通過已經(jīng)實現(xiàn)的基本操作運算有限次實現(xiàn)之。指的是，序列中的每個操作都是可以簡

11、單完成的，其本身不存在算法問題 .(4) 有輸入 (5) 有輸出 算法的評價標準(1) 正確性：要求算法能夠正確地執(zhí)行預先規(guī)定的功能，并達到所期望的性能要求。(2) 可讀性：為了便于理解、測試和修改算法，算法應該具有良好的可讀性。(3) 健壯性：算法中擁有對輸入數(shù)據(jù)、打開文件、讀取文件記錄、分配內(nèi)存空間等操作的結(jié)果檢測，并通過與用戶對話的形式做出相應的處理選擇。(4) 時間與空間效率：算法的時間與空間效率是指將算法變換為程序后，該程序在計算機上運行時所花費的時間及所占據(jù)空間的度量。1.3.3 算法效率的衡量方法 如何估算算法的時間效率？ 和算法執(zhí)行時間相關(guān)的因素有：1）算法所用“策略”；2）算

12、法所解問題的“規(guī)?！?；3）編程所用“語言”；4）“編譯”的質(zhì)量；5）執(zhí)行算法的計算機的速度。 一個算法的執(zhí)行時間可以看成是所有原操作的執(zhí)行時間之和( 原操作(i)的執(zhí)行次數(shù)原操作(i)的執(zhí)行時間 )這種衡量效率的辦法所得出的不是時間量，而是一種增長趨勢的量度。 例: 兩個 n n 的矩陣相乘。 void Mult_matrix( int c, int a, int b， int n)/ a、b 和 c 均為 n 階方陣，且 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 += a

13、i,k*bk,j;/ Mult_matrix算法的時間復雜度為O (n3) 例: 對 n 個整數(shù)進行選擇排序。 void select_sort(int a, int n)/ 將 a 中整數(shù)序列重新排列成自小至大有序的整數(shù)序列。for ( i = 0; i n-1; +i ) j = i; for ( k = i+1; k n; +k )if (ak 1 & change; -i)change = FALSE;for (j=0; j aj+1) w = aj; aj= aj+1; aj+1= w; change = TRUE / bubble_sort算法的時間復雜度為O (n2) 。1.3.4 算法的存儲空間需求 算法的存儲量指的是算法執(zhí)行過程中所需的最大存儲空間。包括以下三部分：(1)輸入數(shù)據(jù)所占空間；(2)程序本身所占