中國計量學院數(shù)據(jù)結(jié)構(gòu)第1章 緒論

1、數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)信息工程學院曾憲庭課時安排：講授40學時上機24學時考核平時及實驗30%，期末考試70%教材：數(shù)據(jù)結(jié)構(gòu) 嚴蔚敏 清華大學出版社參考書：數(shù)據(jù)結(jié)構(gòu) 唐策善 高等教育出版社1 緒論緒論1.1 什么是數(shù)據(jù)結(jié)構(gòu)什么是數(shù)據(jù)結(jié)構(gòu)1.2 基本概念和術(shù)語基本概念和術(shù)語1.3 抽象數(shù)據(jù)類型的表示與實現(xiàn)抽象數(shù)據(jù)類型的表示與實現(xiàn)1.4 算法和算法分析算法和算法分析31.1 什么是數(shù)據(jù)結(jié)構(gòu)什么是數(shù)據(jù)結(jié)構(gòu)u是計算機存儲、組織數(shù)據(jù)的方式是計算機存儲、組織數(shù)據(jù)的方式精心選擇的數(shù)據(jù)結(jié)構(gòu)可以帶來更高的運精心選擇的數(shù)據(jù)結(jié)構(gòu)可以帶來更高的運行效率或者存儲效率行效率或者存儲效率u由若干數(shù)據(jù)元素依據(jù)某種關(guān)系組織由若干數(shù)據(jù)

2、元素依據(jù)某種關(guān)系組織起來起來41.2 基本概念和術(shù)語基本概念和術(shù)語u數(shù)據(jù)數(shù)據(jù)l數(shù)據(jù)元素數(shù)據(jù)元素數(shù)據(jù)的基本單位，數(shù)據(jù)中的一個數(shù)據(jù)的基本單位，數(shù)據(jù)中的一個“個體個體”由若干個由若干個數(shù)據(jù)項數(shù)據(jù)項組成組成l數(shù)據(jù)對象數(shù)據(jù)對象性質(zhì)相同的數(shù)據(jù)元素的集合性質(zhì)相同的數(shù)據(jù)元素的集合u結(jié)構(gòu)結(jié)構(gòu)數(shù)據(jù)元素之間的關(guān)系數(shù)據(jù)元素之間的關(guān)系5u邏輯結(jié)構(gòu)邏輯結(jié)構(gòu)對數(shù)據(jù)元素間邏輯關(guān)系的描述對數(shù)據(jù)元素間邏輯關(guān)系的描述u物理結(jié)構(gòu)物理結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)在計算機中的實現(xiàn)，又稱數(shù)據(jù)結(jié)構(gòu)在計算機中的實現(xiàn)，又稱存儲結(jié)構(gòu)存儲結(jié)構(gòu)u如無特殊說明，一般所說的數(shù)據(jù)結(jié)構(gòu)，如無特殊說明，一般所說的數(shù)據(jù)結(jié)構(gòu)，是指邏輯結(jié)構(gòu)是指邏輯結(jié)構(gòu)u算法的設(shè)計取決于數(shù)據(jù)結(jié)構(gòu)，而

3、算法的算法的設(shè)計取決于數(shù)據(jù)結(jié)構(gòu)，而算法的實現(xiàn)依賴于采用的存儲結(jié)構(gòu)實現(xiàn)依賴于采用的存儲結(jié)構(gòu)67數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)可歸結(jié)為以下四類四類: :線性線性結(jié)構(gòu)樹形樹形結(jié)構(gòu)圖圖/ /網(wǎng)狀網(wǎng)狀結(jié)構(gòu)集合集合結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)的形式定義數(shù)據(jù)結(jié)構(gòu)的形式定義u二元組二元組uData_Structures = (D, S)u其中: D 是數(shù)據(jù)元素的有限集數(shù)據(jù)元素的有限集，u S 是 D上關(guān)系的有限集關(guān)系的有限集8數(shù)據(jù)結(jié)構(gòu)的形式定義數(shù)據(jù)結(jié)構(gòu)的形式定義復數(shù)復數(shù)9 C C是含兩個實數(shù)的集合：是含兩個實數(shù)的集合： C Cc1,c2c1,c2RealSet R R是定義在集合是定義在集合C C上的關(guān)系的集合：上的關(guān)系的集合： R |

4、c1是復數(shù)的實部 | c2 是復數(shù)的虛部 Complex = ( C, R )u數(shù)據(jù)類型數(shù)據(jù)類型描述操作對象的特性描述操作對象的特性C語言：語言：int char float double u抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型Abstract Data Type (ADT)一個數(shù)學模型及定義在該模型上的一組操作一個數(shù)學模型及定義在該模型上的一組操作10u抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型實際上就是對某種數(shù)據(jù)結(jié)構(gòu)的定義實際上就是對某種數(shù)據(jù)結(jié)構(gòu)的定義 它定義了一個數(shù)據(jù)的邏輯結(jié)構(gòu)以及在此結(jié)構(gòu)它定義了一個數(shù)據(jù)的邏輯結(jié)構(gòu)以及在此結(jié)構(gòu)上的一組算法或操作上的一組算法或操作 11抽象數(shù)據(jù)類型的表示抽象數(shù)據(jù)類型的表示u三元組三元組

5、 ( D, S, P )D：數(shù)據(jù)對象：數(shù)據(jù)對象S：D上的關(guān)系集上的關(guān)系集P：對：對D的基本操作集的基本操作集12抽象數(shù)據(jù)類型的表示抽象數(shù)據(jù)類型的表示ADT 抽象數(shù)據(jù)類型名抽象數(shù)據(jù)類型名 數(shù)據(jù)對象：數(shù)據(jù)對象：用偽碼描述用偽碼描述數(shù)據(jù)關(guān)系：數(shù)據(jù)關(guān)系：用偽碼描述用偽碼描述基本操作：基本操作： ADT 抽象數(shù)據(jù)類型名抽象數(shù)據(jù)類型名13抽象數(shù)據(jù)類型的表示抽象數(shù)據(jù)類型的表示基本操作的定義格式：基本操作的定義格式：基本操作名（參數(shù)表）基本操作名（參數(shù)表）初始條件：初始條件：操作結(jié)果：操作結(jié)果：14抽象數(shù)據(jù)類型的表示抽象數(shù)據(jù)類型的表示引用參數(shù)：引用參數(shù)：變量名前加變量名前加 &除了提供輸入值外，還能返回操除了

6、提供輸入值外，還能返回操作結(jié)果作結(jié)果15復數(shù)復數(shù)的抽象數(shù)據(jù)類型定義16 數(shù)據(jù)對象：數(shù)據(jù)對象： De1, e2e1, e2RealSet 數(shù)據(jù)關(guān)系：數(shù)據(jù)關(guān)系： R1 | e1是復數(shù)的實數(shù)部分 | e2 是復數(shù)的虛數(shù)部分 ADT Complex 17基本操作：基本操作： Assign ( &Z, realval, imagval )操作結(jié)果：構(gòu)造復數(shù) Z,其實部和虛部 分別賦以參數(shù)realval和imagval的值 Destroy ( &Z)操作結(jié)果：復數(shù)Z被銷毀。 GetReal( Z, &realPart )初始條件：復數(shù)Z已存在。操作結(jié)果：用realPart返回復數(shù)Z的實部值。18 GetI

7、mag( Z, &ImagPart )初始條件：復數(shù)已存在。操作結(jié)果：用ImagPart返回復數(shù)Z的虛部值。 Add( z1, z2, &sum )初始條件：z1, z2是復數(shù)。操作結(jié)果：用sum返回復數(shù)z1與z2 的和。 ADT Complex19假設(shè):z1和z2是上述定義的復數(shù)則 Add(z1, z2, z3) 操作的結(jié)果z3 = z1 + z21.3 抽象數(shù)據(jù)類型的表示與實現(xiàn)抽象數(shù)據(jù)類型的表示與實現(xiàn)u抽象數(shù)據(jù)類型需要通過固有數(shù)據(jù)類型固有數(shù)據(jù)類型來實現(xiàn)2021typedef struct complex float realpart； float imagpart；complex；/ -存

8、儲結(jié)構(gòu)的定義存儲結(jié)構(gòu)的定義void Assign( complex &Z, float realval, float imagval )；/ 構(gòu)造復數(shù) Z,其實部和虛部分別賦以參數(shù) / realval 和 imagval 的值22float GetReal( complex Z )； / 返回復數(shù) Z 的實部值float GetImag( complex Z )； / 返回復數(shù) Z 的虛部值void add( complex z1, complex z2, complex &sum )； / 以 sum 返回兩個復數(shù) z1, z2 的和 23/ -基本操作的實現(xiàn)基本操作的實現(xiàn)void add(

9、 complex z1, complex z2, complex &sum ) / 以 sum 返回兩個復數(shù) z1, z2 的和 sum.realpart = z1.realpart + z2.realpart; sum.imagpart = z1.imagpart + z2.imagpart; 1.4 算法和算法分析算法和算法分析u算法算法(algorithm)對特定問題求解步驟的一種描述是指令的有限序列u算法特性算法特性有窮性、確定性、可行性、輸入、輸出有窮性、確定性、可行性、輸入、輸出24算法設(shè)計的要求算法設(shè)計的要求u正確性正確性不含語法錯誤不含語法錯誤對于某種輸入數(shù)據(jù)能夠得出滿足要求的

10、結(jié)果對于某種輸入數(shù)據(jù)能夠得出滿足要求的結(jié)果對于精心選擇的典型、苛刻而帶有刁難性的對于精心選擇的典型、苛刻而帶有刁難性的輸入數(shù)據(jù)能夠得出滿足要求的結(jié)果輸入數(shù)據(jù)能夠得出滿足要求的結(jié)果對于一切合法的輸入數(shù)據(jù)都能得出滿足要求對于一切合法的輸入數(shù)據(jù)都能得出滿足要求的結(jié)果的結(jié)果25算法設(shè)計的要求算法設(shè)計的要求u可讀性可讀性u健壯性健壯性當輸入數(shù)據(jù)非法時，程序也能適當?shù)刈龀龇串斴斎霐?shù)據(jù)非法時，程序也能適當?shù)刈龀龇磻?yīng)或精心處理，而不會產(chǎn)生莫名其妙的輸出應(yīng)或精心處理，而不會產(chǎn)生莫名其妙的輸出結(jié)果結(jié)果u效率與低存儲量需求效率與低存儲量需求26算法效率的度量算法效率的度量u1. 事后統(tǒng)計事后統(tǒng)計必須執(zhí)行程序依賴于計

11、算機的硬件和軟件等環(huán)境因素，可能會掩蓋算法本身的優(yōu)劣27算法效率的度量算法效率的度量u程序執(zhí)行時間取決與如下因素時間取決與如下因素算法選用的策略算法選用的策略問題的規(guī)模問題的規(guī)模編寫程序的語言編寫程序的語言編譯程序產(chǎn)生的機器代碼的質(zhì)量編譯程序產(chǎn)生的機器代碼的質(zhì)量計算機執(zhí)行指令的速度計算機執(zhí)行指令的速度28同一個算法用不同的語言、或不同同一個算法用不同的語言、或不同的編譯程序、或不同的計算機上運的編譯程序、或不同的計算機上運行時，效率是不相同的行時，效率是不相同的算法效率的度量算法效率的度量u2. 事前分析估算事前分析估算一個算法的一個算法的“運行工作量運行工作量”的大小，只依賴的大小，只依賴于

12、于問題的規(guī)模問題的規(guī)模（通常用整數(shù)（通常用整數(shù)n表示），或者表示），或者說，它是問題規(guī)模的函數(shù)。說，它是問題規(guī)模的函數(shù)。時間復雜度時間復雜度f(n)： 基本操作基本操作的重復執(zhí)行次數(shù)的重復執(zhí)行次數(shù)T(n) = O ( f(n) ) 隨著隨著n的增大，執(zhí)行次數(shù)的增大，執(zhí)行次數(shù)T(n)的增長率和的增長率和f(n)的增長率相同，則的增長率相同，則f(n)稱為稱為 f(n)其實是其實是T(n)的數(shù)量級的數(shù)量級29int sum = 0;for (i=1; i=n; i+) sum += i;基本操作：基本操作： 加法加法T(n) = n = O(n)30 for (i=1; i=n; i+)for (

13、j=1; j=n; j+) cij = 0;for (k=1; k=n; k+)cij += aik * bkj; 基本操作：基本操作： 乘法乘法T(n) = n3 = O(n3)31int sum(int n)int s;s = 100*200;for (int i=1; i=n; i+)s += i;return s;32O（n）void f1(int a , int n)for (int i=0; in; i+)ai = 0;for (int i=0; in; i+)for (int j=0; jn; j+)ai += aj + i + j;33O（n2）遞歸遞歸階乘階乘long fac

14、torial(int n)if( n = 1 )return 1;elsereturn n * factorial( n - 1 );34O（n）關(guān)于時間復雜度的討論關(guān)于時間復雜度的討論u一般情況，對一個問題只需選擇一種基一般情況，對一個問題只需選擇一種基本操作來討論算法的時間復雜度；本操作來討論算法的時間復雜度；u但有時，也需要同時考慮幾種基本操作，但有時，也需要同時考慮幾種基本操作，甚至可以對不同操作賦予不同的權(quán)值，甚至可以對不同操作賦予不同的權(quán)值，以反映不同操作所需的相對時間，便于以反映不同操作所需的相對時間，便于綜合比較不同的算法綜合比較不同的算法35關(guān)于時間復雜度的討論關(guān)于時間復雜度的討論u同樣的算法對不同的數(shù)據(jù)，其時間復雜同樣的算法對不同的數(shù)據(jù)，其時間復雜度可能會不同，所以可采用如下度量方度可能會不同，所以可采用如下度量方法法u平均時間復雜度平均時間復雜度有時各種輸入數(shù)據(jù)集出現(xiàn)的概率難以確定，有時各種輸入數(shù)據(jù)集出現(xiàn)的概率難以確定，很難計算很難計算u最壞情況下的時間復雜度最壞情況下的時間復雜度更可行、更常用更可行