數(shù)據(jù)結(jié)構(gòu) 1_緒 (2)

1、1數(shù)數(shù) 據(jù)據(jù) 結(jié)結(jié) 構(gòu)構(gòu)2第第 1 1 章章 緒論緒論3本章目錄本章目錄1.1數(shù)據(jù)結(jié)構(gòu)的相關(guān)概念數(shù)據(jù)結(jié)構(gòu)的相關(guān)概念 1.2數(shù)據(jù)類(lèi)型和抽象數(shù)據(jù)類(lèi)型數(shù)據(jù)類(lèi)型和抽象數(shù)據(jù)類(lèi)型 1.3算法與算法分析算法與算法分析 41.1 1.1 基本概念基本概念1. 1. 數(shù)據(jù)結(jié)構(gòu)歷史沿革數(shù)據(jù)結(jié)構(gòu)歷史沿革2. 2. 數(shù)據(jù)結(jié)構(gòu)研究范疇數(shù)據(jù)結(jié)構(gòu)研究范疇3. 3. 數(shù)據(jù)結(jié)構(gòu)基本概念數(shù)據(jù)結(jié)構(gòu)基本概念4. 4. 基本的邏輯結(jié)構(gòu)基本的邏輯結(jié)構(gòu)5. 5. 基本的物理結(jié)構(gòu)基本的物理結(jié)構(gòu)5數(shù)據(jù)結(jié)構(gòu)歷史沿革數(shù)據(jù)結(jié)構(gòu)歷史沿革6數(shù)據(jù)結(jié)構(gòu)的發(fā)展數(shù)據(jù)結(jié)構(gòu)的發(fā)展7數(shù)據(jù)結(jié)構(gòu)的發(fā)展階段數(shù)據(jù)結(jié)構(gòu)的發(fā)展階段8數(shù)據(jù)結(jié)構(gòu)研究對(duì)象數(shù)據(jù)結(jié)構(gòu)研究對(duì)象9數(shù)值計(jì)算的程

2、序設(shè)計(jì)問(wèn)題數(shù)值計(jì)算的程序設(shè)計(jì)問(wèn)題10非數(shù)值計(jì)算問(wèn)題：非數(shù)值計(jì)算問(wèn)題：學(xué)籍管理問(wèn)題學(xué)籍管理問(wèn)題11非數(shù)值計(jì)算問(wèn)題：非數(shù)值計(jì)算問(wèn)題：家庭成員的關(guān)系家庭成員的關(guān)系12如何實(shí)現(xiàn)對(duì)弈如何實(shí)現(xiàn)對(duì)弈?各格局之間是什么關(guān)系？各格局之間是什么關(guān)系？.非數(shù)值計(jì)算問(wèn)題：非數(shù)值計(jì)算問(wèn)題：人機(jī)對(duì)弈問(wèn)題人機(jī)對(duì)弈問(wèn)題13C1C2C3C4C6C5C7如何表示課程之間的先修關(guān)系？如何表示課程之間的先修關(guān)系？非數(shù)值計(jì)算問(wèn)題：非數(shù)值計(jì)算問(wèn)題：教學(xué)計(jì)劃編排問(wèn)題教學(xué)計(jì)劃編排問(wèn)題14圖 1-2 煤氣管道的鋪設(shè)示意圖 以上煤氣管道線(xiàn)之間構(gòu)成了網(wǎng)狀結(jié)構(gòu)，結(jié)構(gòu)中的數(shù)據(jù)以上煤氣管道線(xiàn)之間構(gòu)成了網(wǎng)狀結(jié)構(gòu)，結(jié)構(gòu)中的數(shù)據(jù)元素之間存在多對(duì)多的關(guān)系。元素

3、之間存在多對(duì)多的關(guān)系。非數(shù)值計(jì)算問(wèn)題：非數(shù)值計(jì)算問(wèn)題：煤氣管道的鋪設(shè)煤氣管道的鋪設(shè)15非數(shù)值計(jì)算問(wèn)題：非數(shù)值計(jì)算問(wèn)題： 多叉路口的交通燈設(shè)置多叉路口的交通燈設(shè)置16計(jì)算機(jī)處理問(wèn)題的一般過(guò)程計(jì)算機(jī)處理問(wèn)題的一般過(guò)程 問(wèn)題數(shù)學(xué)模型建模實(shí)現(xiàn)求精機(jī)外表示機(jī)外表示處理要求處理要求邏輯結(jié)構(gòu)邏輯結(jié)構(gòu)基本運(yùn)算基本運(yùn)算存儲(chǔ)結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)算法算法17數(shù)據(jù)結(jié)構(gòu)研究范疇數(shù)據(jù)結(jié)構(gòu)研究范疇18表表1-1數(shù)據(jù)結(jié)構(gòu)課程內(nèi)容體系數(shù)據(jù)結(jié)構(gòu)課程內(nèi)容體系19數(shù)據(jù)結(jié)構(gòu)地位數(shù)據(jù)結(jié)構(gòu)地位20有關(guān)概念和術(shù)語(yǔ)有關(guān)概念和術(shù)語(yǔ)21數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項(xiàng)之間的關(guān)系數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項(xiàng)之間的關(guān)系22數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)23典型邏輯結(jié)構(gòu)典型邏輯結(jié)構(gòu)2. 線(xiàn)

4、性表：數(shù)據(jù)元素之間存數(shù)據(jù)元素之間存在著一對(duì)一的線(xiàn)性關(guān)系；在著一對(duì)一的線(xiàn)性關(guān)系；3. 樹(shù)：數(shù)據(jù)元素之間存在數(shù)據(jù)元素之間存在著一對(duì)多的層次關(guān)系著一對(duì)多的層次關(guān)系A(chǔ)BCDEFGHIJMKL4. 圖：數(shù)據(jù)元素之間存在數(shù)據(jù)元素之間存在 著多對(duì)多的任意關(guān)系。著多對(duì)多的任意關(guān)系。BACDFE1. 集合：數(shù)據(jù)元素之間就是數(shù)據(jù)元素之間就是 “ “屬于同一個(gè)集合屬于同一個(gè)集合”24數(shù)據(jù)結(jié)構(gòu)的形式定義數(shù)據(jù)結(jié)構(gòu)的形式定義25 數(shù)組的形式定義數(shù)組的形式定義例：一維數(shù)組，A6=a1, a2, a3, a4, a5, a6R= | i=1, 2, 3, 4, 5D= a1, a2, a3, a4, a5, a6例：二維數(shù)組

5、D=a1, a2, a3, a4, a5, a6 R=row,col row = , col = , 26存儲(chǔ)結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)1. 1. 順序存儲(chǔ)順序存儲(chǔ)2. 2. 鏈?zhǔn)酱鎯?chǔ)鏈?zhǔn)酱鎯?chǔ)3. 3. 散列存儲(chǔ)散列存儲(chǔ)4. 4. 索引存儲(chǔ)索引存儲(chǔ)272829其它存儲(chǔ)方法其它存儲(chǔ)方法散列存儲(chǔ)散列存儲(chǔ)索引存儲(chǔ)索引存儲(chǔ)30邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)之間的關(guān)系邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)之間的關(guān)系311.2 1.2 數(shù)據(jù)類(lèi)型數(shù)據(jù)類(lèi)型1. 1. 數(shù)據(jù)類(lèi)型數(shù)據(jù)類(lèi)型2. 2. 抽象數(shù)據(jù)類(lèi)型抽象數(shù)據(jù)類(lèi)型32數(shù)據(jù)類(lèi)型數(shù)據(jù)類(lèi)型33C C 語(yǔ)言中提供的基本數(shù)據(jù)類(lèi)型語(yǔ)言中提供的基本數(shù)據(jù)類(lèi)型34typedef struct int y; / 年號(hào)

6、Year int m; / 月號(hào) Month int d; / 日號(hào) Day DateType; / 日期類(lèi)型定義定義“日期日期”為:定義定義“學(xué)生學(xué)生”為:typedef struct char id8; / 學(xué)號(hào) char name16; / 姓名 char sex; / 性別M/F:男/女 DateType bdate; / 出生日期 Student; / 學(xué)生類(lèi)型結(jié)構(gòu)類(lèi)型結(jié)構(gòu)類(lèi)型35抽象數(shù)據(jù)類(lèi)型抽象數(shù)據(jù)類(lèi)型36ADTADT是對(duì)數(shù)據(jù)類(lèi)型的進(jìn)一步抽象是對(duì)數(shù)據(jù)類(lèi)型的進(jìn)一步抽象 ADT邏輯結(jié)構(gòu)邏輯結(jié)構(gòu)操作集合操作集合數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)算法設(shè)計(jì)算法設(shè)計(jì)類(lèi)類(lèi)成員變量成員變量成員函數(shù)成

7、員函數(shù)a. 使用視圖使用視圖 b. 設(shè)計(jì)視圖設(shè)計(jì)視圖 c. 實(shí)現(xiàn)視圖實(shí)現(xiàn)視圖 ADT的定義的定義 ADT的設(shè)計(jì)的設(shè)計(jì) ADT的實(shí)現(xiàn)的實(shí)現(xiàn)ADTADT的不同視圖的不同視圖37抽象數(shù)據(jù)類(lèi)型的形式化描述抽象數(shù)據(jù)類(lèi)型的形式化描述38ADTADT描述描述操操作作說(shuō)說(shuō)明明39抽象數(shù)據(jù)類(lèi)型復(fù)數(shù)的定義抽象數(shù)據(jù)類(lèi)型復(fù)數(shù)的定義40復(fù)數(shù)的復(fù)數(shù)的ADTADT定義舉例定義舉例41C+C+實(shí)現(xiàn)的復(fù)數(shù)類(lèi)型實(shí)現(xiàn)的復(fù)數(shù)類(lèi)型Class complex private: float realpart; float imagpart; public: complex(float real,float imag)/構(gòu)造函數(shù) compl

8、ex();/析構(gòu)函數(shù) float GetReal();/返回復(fù)數(shù)的實(shí)部 float GetImag();/返回復(fù)數(shù)的虛部 .421.3 1.3 算法和算法分析算法和算法分析1.1.算法算法2.2.算法描述算法描述3.3.算法分析算法分析43算算 法法44算法特性算法特性45算法與程序算法與程序46算法設(shè)計(jì)要求算法設(shè)計(jì)要求47算法描述l 自然語(yǔ)言l 流程圖l 程序設(shè)計(jì)語(yǔ)言l 類(lèi)程序設(shè)計(jì)語(yǔ)言l 偽代碼48mnr例：求兩個(gè)自然數(shù)例：求兩個(gè)自然數(shù) mm 和和 n n 的的最大公約數(shù)最大公約數(shù)49 輸入輸入m 和和n； 求求m除以除以n的余數(shù)的余數(shù)r； 若若r等于等于0 0，則，則n為最大公約數(shù)，算法結(jié)

9、束；為最大公約數(shù)，算法結(jié)束；否則執(zhí)行第步；否則執(zhí)行第步； 將將n的值放在的值放在m中，將中，將r的值放在的值放在n中；中； 重新執(zhí)行第步。重新執(zhí)行第步。歐幾里德算法：歐幾里德算法：自然語(yǔ)言描述描述50優(yōu)點(diǎn)：容易理解優(yōu)點(diǎn)：容易理解缺點(diǎn)：冗長(zhǎng)、二義性缺點(diǎn)：冗長(zhǎng)、二義性使用方法：粗線(xiàn)條描述算法思想使用方法：粗線(xiàn)條描述算法思想 注意事項(xiàng)：避免寫(xiě)成自然段注意事項(xiàng)：避免寫(xiě)成自然段自然語(yǔ)言描述的特點(diǎn)自然語(yǔ)言描述的特點(diǎn)51N開(kāi)始輸入m和n r=m % nr=0m=n；n=r 輸出n結(jié)束Y歐幾里德算法：流程圖歐幾里德算法：流程圖52流程圖描述的特點(diǎn)流程圖描述的特點(diǎn)53#include void main( )

10、coutCommonFactor(63, 54) endl;歐幾里德算法：程序設(shè)計(jì)語(yǔ)言歐幾里德算法：程序設(shè)計(jì)語(yǔ)言5455優(yōu)點(diǎn)：能由計(jì)算機(jī)執(zhí)行優(yōu)點(diǎn)：能由計(jì)算機(jī)執(zhí)行 缺點(diǎn)：抽象性差，對(duì)語(yǔ)言要求高缺點(diǎn)：抽象性差，對(duì)語(yǔ)言要求高使用方法：算法需要驗(yàn)證使用方法：算法需要驗(yàn)證注意事項(xiàng)：將算法寫(xiě)成子函數(shù)注意事項(xiàng)：將算法寫(xiě)成子函數(shù)程序設(shè)計(jì)語(yǔ)言描述特點(diǎn)程序設(shè)計(jì)語(yǔ)言描述特點(diǎn)56偽代碼偽代碼（Pseudocode）：偽代碼是自然語(yǔ)）：偽代碼是自然語(yǔ)言和程序設(shè)計(jì)語(yǔ)言組成的混合結(jié)構(gòu)，它比自言和程序設(shè)計(jì)語(yǔ)言組成的混合結(jié)構(gòu)，它比自然語(yǔ)言更精確。它采用某一程序設(shè)計(jì)語(yǔ)言的然語(yǔ)言更精確。它采用某一程序設(shè)計(jì)語(yǔ)言的基本語(yǔ)法，操作指令可

11、以結(jié)合自然語(yǔ)言來(lái)設(shè)基本語(yǔ)法，操作指令可以結(jié)合自然語(yǔ)言來(lái)設(shè)計(jì)。計(jì)。優(yōu)點(diǎn)：表達(dá)能力強(qiáng)，抽象性強(qiáng)，容易理解優(yōu)點(diǎn)：表達(dá)能力強(qiáng)，抽象性強(qiáng)，容易理解偽代碼偽代碼57 1. r = m % n; 2. 循環(huán)下列操作，直循環(huán)下列操作，直到到 r 等于等于0 2.1 m = n; 2.2 n = r; 2.3 r = m % n;3. 輸出輸出 n ;歐幾里德算法：偽碼描述歐幾里德算法：偽碼描述58類(lèi)程序設(shè)計(jì)語(yǔ)言類(lèi)程序設(shè)計(jì)語(yǔ)言59歐幾里德算法：歐幾里德算法：類(lèi)類(lèi)C+C+描述描述intint CommonFactor(intCommonFactor(int m, m, intint n) n) intint r=

12、 m % n; r= m % n; while (r!=0) while (r!=0) m=n; m=n; n=r; n=r; r=m % n; r=m % n; return n; return n; #include void main( ) coutCommonFactor(63, 54) endl;60冒泡排序void sort (int A ,int n) int i, j, k; for(i=0;in-1;i+) for(j=0;jAj+1) t=Aj; Aj=Aj+1; Aj+1=t;void sort (int A ,int n) for(i=0;in-1;i+) for(j=

13、0;kAj+1) AjAj+1;程序設(shè)計(jì)語(yǔ)言類(lèi)程序設(shè)計(jì)語(yǔ)言算法的(類(lèi))程序設(shè)計(jì)語(yǔ)言描述61類(lèi)類(lèi)C/C+C/C+語(yǔ)法概要語(yǔ)法概要賦值語(yǔ)句賦值語(yǔ)句簡(jiǎn)單賦值：x = 2; 串聯(lián)賦值：x1 = x2 = x3 = 4 ;變量名=表達(dá)式變量名1=變量名k=表達(dá)式條件賦值：z= xy ? x:y ;交換賦值：x y ; 變量名=條件表達(dá)式？表達(dá)式T:表達(dá)式F變量名變量名62類(lèi)類(lèi)C/C+C/C+語(yǔ)法概要語(yǔ)法概要賦值語(yǔ)句賦值語(yǔ)句成組賦值: (x1,x2,x3) = (1,2,3) 變量名1，變量名k = 表達(dá)式1，,表達(dá)式k結(jié)構(gòu)名 = 結(jié)構(gòu)名 或 結(jié)構(gòu)名 = (值1，值n)變量名 = 表達(dá)式array_A1.

14、5 = array_B3.7變量名變量名 起始下標(biāo)起始下標(biāo). .終止下標(biāo)終止下標(biāo) = = 變量名變量名 起始下標(biāo)起始下標(biāo). .終止下標(biāo)終止下標(biāo) 63算法分析算法分析64與時(shí)間相關(guān)因素與時(shí)間相關(guān)因素65算法的執(zhí)行時(shí)間算法的執(zhí)行時(shí)間int Algo1( int n) if (n0) return 0; sum=0; for( i=0 ;i=n; i+ ) sum=sum + i ; return sum;算法 = 控制結(jié)構(gòu) + 原操作 算法執(zhí)行時(shí)間= ( ( 基本操作基本操作(i)(i)的執(zhí)行次數(shù)的執(zhí)行次數(shù)基本操作基本操作(i)(i)的執(zhí)行時(shí)間的執(zhí)行時(shí)間 ) ) 算法的執(zhí)行時(shí)間 與 原操作執(zhí)行次數(shù)

15、之和 成正比 sum=sum=sumsum + i ; + i ;66定義定義 若存在兩個(gè)正的常數(shù)若存在兩個(gè)正的常數(shù)c和和n0，對(duì)于任意對(duì)于任意nn0，都有都有T( (n)cf( (n) )，則稱(chēng)則稱(chēng)T( (n) )=O( (f( (n)n0問(wèn)題規(guī)模問(wèn)題規(guī)模n執(zhí)執(zhí)行行次次數(shù)數(shù)n0之前的之前的情況無(wú)關(guān)情況無(wú)關(guān)緊要緊要T( (n) )cf( (n) )v當(dāng)問(wèn)題規(guī)模充分大時(shí)在漸近意義下的階當(dāng)問(wèn)題規(guī)模充分大時(shí)在漸近意義下的階算法分析算法分析大大OO符號(hào)符號(hào)67定理：若定理：若A(n)=amnm+am-1nm-1+a1n+a0是一個(gè)是一個(gè)m次多項(xiàng)式，則次多項(xiàng)式，則A(n)=O(nm)。定理：大定理：大O

16、O符號(hào)運(yùn)算符號(hào)運(yùn)算(1)(log2n)(n)(nlog2n)(n2)(n3) (2n)(n!) (1)(1) 常量階常量階( (n n) ) 線(xiàn)性階線(xiàn)性階(n2) 平方階平方階(log2n) 對(duì)數(shù)階對(duì)數(shù)階(2n) 指數(shù)階指數(shù)階68例例1 + + x ; 例例2 for ( ( i=1; i=n; +i) ) + + x ; 算法分析舉例一、二算法分析舉例一、二69算法算法T(nT(n) )舉例三舉例三for ( i=1 ; in ; i+)for ( i=1 ; in ; i+) y=y+1 ; y=y+1 ;for ( j=0 ; j=n ; j+ )for ( j=0 ; j=n ; j+

17、 ) x+ ; x+ ; 70算法算法T(nT(n) )舉例四舉例四x=1 ;x=1 ;for ( i=1 ;i=n ; i+ )for ( i=1 ;i=n ; i+ ) for ( j=1 ; j=i ;j+ ) for ( j=1 ; j=i ;j+ ) x+ x+ ; ;71算法算法T(nT(n) )舉例五舉例五i=1;while (i=1&change;i-) change=False; for ( j = 0;j aj+1 ) aj aj+1;aj aj+1; change=TRUE ; /for / bubble_sort73最好情況、最壞情況、平均情況最好情況、最壞情況、平均情