數(shù)據(jù)結(jié)構(gòu)：第1章-緒論

1、數(shù)據(jù)結(jié)構(gòu)：第1章-緒論Return主要教學(xué)內(nèi)容主要教學(xué)內(nèi)容： 1.1 1.1 本課程的研究對(duì)象；本課程的研究對(duì)象； 1.2 1.2 數(shù)據(jù)結(jié)構(gòu)的有關(guān)基本概念；數(shù)據(jù)結(jié)構(gòu)的有關(guān)基本概念； 1.3 1.3 數(shù)據(jù)結(jié)構(gòu)的分類及表示；數(shù)據(jù)結(jié)構(gòu)的分類及表示； 1.4 1.4 算法及算法分析（算法評(píng)價(jià)）算法及算法分析（算法評(píng)價(jià)） 1.1 1.1 本課程研究的問題本課程研究的問題計(jì)算機(jī)的發(fā)展計(jì)算機(jī)的發(fā)展 軟件軟件 硬件硬件 應(yīng)用領(lǐng)域應(yīng)用領(lǐng)域數(shù)據(jù)處理的種類和能力數(shù)據(jù)處理的種類和能力 數(shù)據(jù)數(shù)據(jù)數(shù)值數(shù)據(jù)數(shù)值數(shù)據(jù)非數(shù)值數(shù)據(jù)非數(shù)值數(shù)據(jù)數(shù)數(shù) (整數(shù)整數(shù),實(shí)數(shù)實(shí)數(shù)) 字符字符 字符串字符串 文字文字 圖形圖形 圖象圖象 聲音聲

2、音數(shù)據(jù)：客觀對(duì)象的符號(hào)表示數(shù)據(jù)：客觀對(duì)象的符號(hào)表示數(shù)學(xué)中的整數(shù)、實(shí)數(shù)，數(shù)學(xué)中的整數(shù)、實(shí)數(shù)，課程名，地名、書名課程名，地名、書名程序程序原始數(shù)據(jù)原始數(shù)據(jù)結(jié)果數(shù)據(jù)結(jié)果數(shù)據(jù) 數(shù)值問題與非數(shù)值問題數(shù)值問題與非數(shù)值問題1）數(shù)值問題）數(shù)值問題例例1 已知：游泳池的長已知：游泳池的長len和寬和寬wide，求面積，求面積area設(shè)計(jì)設(shè)計(jì) 求解問題的方法求解問題的方法 編程編程main ( ) int len, wide ,area ;scanf (“%d %d%n”, &l,&w);area=len*wide ;printf (“area=%d”,area); 建模型：建模型：?jiǎn)栴}涉及的對(duì)象

3、：游泳池的長問題涉及的對(duì)象：游泳池的長len 寬寬wide，面積，面積area；對(duì)象之間的關(guān)系：對(duì)象之間的關(guān)系：area=len wide 學(xué)號(hào)學(xué)號(hào) 姓名姓名 性別性別 出生日期出生日期 籍貫籍貫 入學(xué)成績(jī)?nèi)雽W(xué)成績(jī) 所在班級(jí)所在班級(jí) 00201 楊潤生 男 82/06/01 廣州 561 00計(jì)算機(jī)200102 石磊 男 83/12/21 汕頭 512 00計(jì)算機(jī)100202 李梅 女 83/02/23 陽江 532 00計(jì)算機(jī)200301 馬耀先 男 82/07/12 廣州 509 00計(jì)算機(jī)32）非數(shù)值問題）非數(shù)值問題例例 2 已知某級(jí)學(xué)生情況已知某級(jí)學(xué)生情況 , 要求分班按入學(xué)成績(jī)排列順

4、序。要求分班按入學(xué)成績(jī)排列順序。在這類文檔管理的數(shù)學(xué)模型中在這類文檔管理的數(shù)學(xué)模型中, 計(jì)算機(jī)處理的對(duì)象之間通常存在著一種最簡(jiǎn)單的計(jì)算機(jī)處理的對(duì)象之間通常存在著一種最簡(jiǎn)單的線性關(guān)系線性關(guān)系 , 這類數(shù)學(xué)模型稱為線性模型。這類數(shù)學(xué)模型稱為線性模型。例例 3 迷宮問題。在迷宮中，每走到一處，接下來可走的通路迷宮問題。在迷宮中，每走到一處，接下來可走的通路有三條。計(jì)算機(jī)處理的這類對(duì)象之間通常不存在線性關(guān)系。若有三條。計(jì)算機(jī)處理的這類對(duì)象之間通常不存在線性關(guān)系。若把從迷宮入口處到出口的過程中所有可能的通路都畫出，則可把從迷宮入口處到出口的過程中所有可能的通路都畫出，則可得一棵得一棵“樹樹” 入口入口

5、出口出口 城市間交通網(wǎng)問題數(shù)據(jù)結(jié)構(gòu)的研究問題：數(shù)據(jù)結(jié)構(gòu)的研究問題： 非數(shù)值數(shù)據(jù)之間的結(jié)構(gòu)關(guān)系，非數(shù)值數(shù)據(jù)之間的結(jié)構(gòu)關(guān)系，及如何表示，如何存儲(chǔ)，如何處理。及如何表示，如何存儲(chǔ)，如何處理。本課程討論的問題：本課程討論的問題： 應(yīng)用中常用的幾種數(shù)據(jù)間的結(jié)構(gòu)關(guān)系，應(yīng)用中常用的幾種數(shù)據(jù)間的結(jié)構(gòu)關(guān)系，及如何表示及如何表示, ,如何存儲(chǔ)，如何處理。如何存儲(chǔ)，如何處理。 數(shù)據(jù)：客觀對(duì)象的符號(hào)表示。數(shù)據(jù)：客觀對(duì)象的符號(hào)表示。 例如：學(xué)號(hào)，姓名，班名都是數(shù)據(jù)。例如：學(xué)號(hào)，姓名，班名都是數(shù)據(jù)。 數(shù)據(jù)元素：數(shù)據(jù)的基本單位。相當(dāng)于數(shù)據(jù)元素：數(shù)據(jù)的基本單位。相當(dāng)于“記錄記錄”, ,在計(jì)算機(jī)程序中通常作為一個(gè)整體在計(jì)算機(jī)程

6、序中通常作為一個(gè)整體考慮和處理考慮和處理 數(shù)據(jù)項(xiàng)數(shù)據(jù)項(xiàng): : 相當(dāng)于記錄的相當(dāng)于記錄的“域域”, , 是數(shù)據(jù)的不可分割的最小單位是數(shù)據(jù)的不可分割的最小單位, ,如學(xué)號(hào)如學(xué)號(hào) 數(shù)據(jù)對(duì)象：性質(zhì)相同的數(shù)據(jù)元素的集合數(shù)據(jù)對(duì)象：性質(zhì)相同的數(shù)據(jù)元素的集合. . 例如例如: : 所有班名相同的記錄集合所有班名相同的記錄集合 數(shù)據(jù)結(jié)構(gòu)：是相互間存在關(guān)系的數(shù)據(jù)元素集合。數(shù)據(jù)結(jié)構(gòu)：是相互間存在關(guān)系的數(shù)據(jù)元素集合。 1.2 1.2 數(shù)據(jù)結(jié)構(gòu)的有關(guān)概念數(shù)據(jù)結(jié)構(gòu)的有關(guān)概念對(duì)每種數(shù)據(jù)結(jié)構(gòu)，主要討論如下兩方面的問題：對(duì)每種數(shù)據(jù)結(jié)構(gòu)，主要討論如下兩方面的問題： 1 1） 數(shù)據(jù)的邏輯結(jié)構(gòu)，數(shù)據(jù)的邏輯結(jié)構(gòu)，數(shù)據(jù)結(jié)構(gòu)的數(shù)據(jù)結(jié)構(gòu)的基

7、本操作；基本操作； 2 2） 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)，數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)，數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)基本操作的實(shí)現(xiàn)；基本操作的實(shí)現(xiàn)；數(shù)據(jù)的邏輯結(jié)構(gòu)：數(shù)據(jù)的邏輯結(jié)構(gòu)： 數(shù)據(jù)之間的結(jié)構(gòu)關(guān)系，是數(shù)據(jù)之間的結(jié)構(gòu)關(guān)系，是具體具體關(guān)系的抽象。關(guān)系的抽象。數(shù)據(jù)結(jié)構(gòu)的數(shù)據(jù)結(jié)構(gòu)的基本操作：基本操作： 指對(duì)數(shù)據(jù)結(jié)構(gòu)的加工處理指對(duì)數(shù)據(jù)結(jié)構(gòu)的加工處理數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu) ( (物理結(jié)構(gòu)物理結(jié)構(gòu)) )： 數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)內(nèi)存中的表示數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)內(nèi)存中的表示數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)基本操作的實(shí)現(xiàn)：基本操作的實(shí)現(xiàn)： 基本操作在計(jì)算機(jī)上的實(shí)現(xiàn)（方法基本操作在計(jì)算機(jī)上的實(shí)現(xiàn)（方法) ) 某班學(xué)生基本情況登記表，記錄了每個(gè)學(xué)生的學(xué)號(hào)某班學(xué)生基本情

8、況登記表，記錄了每個(gè)學(xué)生的學(xué)號(hào) 姓名姓名 專業(yè)專業(yè) 政治政治 面貌面貌 ，表中的記錄是按學(xué)生的學(xué)號(hào)順序排列的。，表中的記錄是按學(xué)生的學(xué)號(hào)順序排列的。 學(xué)號(hào)學(xué)號(hào) 姓名姓名 專業(yè)專業(yè) 政治面藐政治面藐 001001 王洪王洪 計(jì)算機(jī)計(jì)算機(jī) 黨員黨員 002 002 孫文孫文 計(jì)算機(jī)計(jì)算機(jī) 團(tuán)員團(tuán)員 003003 謝軍謝軍 計(jì)算機(jī)計(jì)算機(jī) 團(tuán)員團(tuán)員 004004 李輝李輝 計(jì)算機(jī)計(jì)算機(jī) 團(tuán)員團(tuán)員 005005 沈祥福沈祥福 計(jì)算機(jī)計(jì)算機(jī) 黨員黨員 006006 余斌余斌 計(jì)算機(jī)計(jì)算機(jī) 團(tuán)員團(tuán)員 007007 鞏力鞏力 計(jì)算機(jī)計(jì)算機(jī) 團(tuán)員團(tuán)員 008008 孔令輝孔令輝 計(jì)算機(jī)計(jì)算機(jī) 團(tuán)員團(tuán)員學(xué)生基本情

9、況登記表的圖示學(xué)生基本情況登記表的圖示 001001003003002002004004006006005005008008007007學(xué)生間學(xué)號(hào)順序關(guān)系學(xué)生間學(xué)號(hào)順序關(guān)系是一種線性結(jié)構(gòu)關(guān)系是一種線性結(jié)構(gòu)關(guān)系例例一一 常用的數(shù)據(jù)結(jié)構(gòu)常用的數(shù)據(jù)結(jié)構(gòu) 1） 集合集合 2） 線性結(jié)構(gòu)線性結(jié)構(gòu) 3） 樹結(jié)構(gòu)樹結(jié)構(gòu) 4） 圖結(jié)構(gòu)圖結(jié)構(gòu) 5 5）其它復(fù)雜結(jié)構(gòu)）其它復(fù)雜結(jié)構(gòu) 1.3 1.3 數(shù)據(jù)結(jié)構(gòu)的分類及表示數(shù)據(jù)結(jié)構(gòu)的分類及表示 家族的族譜家族的族譜 假設(shè)某家族有假設(shè)某家族有1010個(gè)成員個(gè)成員A A， B B， C C， D D， E E， F F， G G， H H，I I， J J，他們之間的血緣關(guān)

10、系可以用，他們之間的血緣關(guān)系可以用如下圖表示。如下圖表示。J JI IA AC CB BD DH HG GF FE E例例數(shù)據(jù)結(jié)構(gòu)的表示數(shù)據(jù)結(jié)構(gòu)的表示 圖示表示圖示表示 圖示表示是由頂點(diǎn)和邊構(gòu)成的圖，其中頂點(diǎn)表示數(shù)據(jù)圖示表示是由頂點(diǎn)和邊構(gòu)成的圖，其中頂點(diǎn)表示數(shù)據(jù) ，邊表示數(shù)據(jù)之間的結(jié)構(gòu)，邊表示數(shù)據(jù)之間的結(jié)構(gòu)關(guān)系；關(guān)系； 001001003003002002004004006006005005008008007007學(xué)生基本情況表的圖示表示學(xué)生基本情況表的圖示表示J JI IA AC CB BD DH HG GF FE E家族樹的圖示表示家族樹的圖示表示13 數(shù)據(jù)結(jié)構(gòu)的分類及表示學(xué)生基本情況表的

11、二元組表示學(xué)生基本情況表的二元組表示（D D，S S） 二元組表示二元組表示 二元組表示是用一個(gè)二元組（二元組表示是用一個(gè)二元組（D D，S S）表示數(shù)據(jù)結(jié)構(gòu)，）表示數(shù)據(jù)結(jié)構(gòu)， 其中其中 D D 是數(shù)據(jù)元素集合，是數(shù)據(jù)元素集合，S S 是是 D D 上關(guān)系的集合。上關(guān)系的集合。D = 001D = 001，002002，003003，004004，005005，006006，007007，008008S = R S = R R= ,R= , , , 家族樹的二元組表示家族樹的二元組表示（D D，S S） D = A D = A，B B，C C，D D，E E，F(xiàn) F，G G，H H，I I，J

12、J S = R S = R R = R = A,B, A,B, 13 數(shù)據(jù)結(jié)構(gòu)的分類及表示J JI IA AC CB BD DH HG GF FE E 001001003003002002004004006006005005008008007007 1.4 1.4 算法與算法分析算法與算法分析一一 算法的概念算法的概念 算法是求解問題的操作序列算法是求解問題的操作序列 算法的基本特征：算法的基本特征：1 1）輸入：）輸入：0 0個(gè)或多個(gè)輸入；個(gè)或多個(gè)輸入；2 2）輸出：）輸出：1 1個(gè)或多個(gè)輸出；個(gè)或多個(gè)輸出；3 3）有窮性：算法必須在有限步內(nèi)結(jié)束；）有窮性：算法必須在有限步內(nèi)結(jié)束；4 4）確

13、定性：組成算法的操作必須清晰無二義性。）確定性：組成算法的操作必須清晰無二義性。5 5）可行性：組成算法的操作必須能夠在計(jì)算機(jī)上實(shí)現(xiàn)。）可行性：組成算法的操作必須能夠在計(jì)算機(jī)上實(shí)現(xiàn)。 求兩個(gè)正整數(shù)求兩個(gè)正整數(shù) m m，n n 中的最大數(shù)中的最大數(shù)MAXMAX的算法的算法 （1 1）若若 m n m n 則則 max=mmax=m （2 2）若若 m = n m = n 則則 max=n max=n 例例 所有算法均以函數(shù)形式給出, 算法的輸入數(shù)據(jù)來自參數(shù)表 參數(shù)表的參數(shù)在算法之前均進(jìn)行類型說明 有關(guān)結(jié)點(diǎn)結(jié)構(gòu)的類型定義,以及全局變量的說明等均在算法之前進(jìn)行說明評(píng)價(jià)算法標(biāo)準(zhǔn)評(píng)價(jià)算法標(biāo)準(zhǔn) 算法的正確

14、性，可讀性，可維護(hù)性，健壯性等算法的正確性，可讀性，可維護(hù)性，健壯性等，1 算法時(shí)間復(fù)雜度算法時(shí)間復(fù)雜度T（n） 本課程采用以求解問題的基本操作（原操作）的執(zhí)行次數(shù)作為算法時(shí)間的度量。本課程采用以求解問題的基本操作（原操作）的執(zhí)行次數(shù)作為算法時(shí)間的度量。 14 算法與算法分析O（n3） 稱為矩陣相乘算法時(shí)間復(fù)雜度；稱為矩陣相乘算法時(shí)間復(fù)雜度；O（n3）表示矩陣相乘算法執(zhí)行時(shí)間與）表示矩陣相乘算法執(zhí)行時(shí)間與n3成正比成正比, 即即O（n3）與）與n3 同一數(shù)量級(jí)；同一數(shù)量級(jí)； n 階矩階矩 陣相乘的算法陣相乘的算法For ( i = 1; i=n; i+ ) For (j = 1; j=n; j

15、+ ) c i j = 0 ; For (k = 1; k= n; k+ ) c i j += a i k * b k j 乘法乘法 加法加法執(zhí)行次數(shù)均為執(zhí)行次數(shù)均為 n3 例例 矩陣相乘的基本運(yùn)算：乘法矩陣相乘的基本運(yùn)算：乘法 加法；加法； 有些算法，基本操作執(zhí)行次數(shù)與問題的輸入數(shù)據(jù)有關(guān)，這時(shí)可考慮有些算法，基本操作執(zhí)行次數(shù)與問題的輸入數(shù)據(jù)有關(guān)，這時(shí)可考慮 （1） 算法平均時(shí)間復(fù)雜度算法平均時(shí)間復(fù)雜度 （2） 算法在最壞情況下的時(shí)間復(fù)雜度算法在最壞情況下的時(shí)間復(fù)雜度算法的時(shí)間復(fù)雜度算法的時(shí)間復(fù)雜度 一般來說，設(shè)算法中基本操作的執(zhí)行次數(shù)是問題規(guī)模一般來說，設(shè)算法中基本操作的執(zhí)行次數(shù)是問題規(guī)模n

16、的某個(gè)函數(shù)的某個(gè)函數(shù)f(n)，算法的，算法的時(shí)間復(fù)雜度記作：時(shí)間復(fù)雜度記作： T(n) = O(f(n) 它表示隨問題規(guī)模它表示隨問題規(guī)模n的增大，算法執(zhí)行時(shí)間的增長率與的增大，算法執(zhí)行時(shí)間的增長率與f(n) 的增長率相同。的增長率相同。 14 算法與算法分析算法的時(shí)間復(fù)雜度為算法的時(shí)間復(fù)雜度為O (N3) 14 算法與算法分析 100元買元買100支筆支筆, 其中鋼筆其中鋼筆 3元元/支支, 圓珠筆圓珠筆 2元元/支支, 鉛筆鉛筆 0.5元元/支支. 寫寫算法輸出各種組合方案算法輸出各種組合方案解法解法1 #define N 100void scheme() int i, j, k, cou

17、nt, money; for (i = 0; i=N; i+ ) for (j = 0; j=N; j+ ) for (k=0; k=N; k+) count=i+j+k; money=3*i+2*j+0.5*k; if ( count=N & money=N) printf (“%d, %d, %d n%”, i, j, k) ; 例例# define N 100Void scheme( ) int i, j; for (i=0; i=N/3; i+) for (j=0; j=(N-3*i)/2; j+) if (3*i+2*j+0.5*(N-i-j)= =N) printf(“%d

18、, %d, %dn%”, i, j, N-i-j); 時(shí)間復(fù)雜度為O(N2 ) 14 算法與算法分析例例2 算法空間復(fù)雜度算法空間復(fù)雜度 在本課程中，用執(zhí)行算法所需的輔助空間的大小作為算法所需空間的度量。在本課程中，用執(zhí)行算法所需的輔助空間的大小作為算法所需空間的度量。 設(shè)執(zhí)行算法所需的輔助空間是問題規(guī)模設(shè)執(zhí)行算法所需的輔助空間是問題規(guī)模n的某個(gè)函數(shù)的某個(gè)函數(shù)g(n),則算法空間復(fù)雜則算法空間復(fù)雜度記作：度記作： S（n）= O(g(n)表示算法輔助空間的增長率表示算法輔助空間的增長率與與g(n) 的增長率相同的增長率相同計(jì)算計(jì)算 解法解法1 先計(jì)算先計(jì)算x 的冪的冪, 存于存于power 中中,再分別乘以相應(yīng)的系數(shù)再分別乘以相應(yīng)的系數(shù) # define N 100 float evaluate (float coef , float x ,