數(shù)據(jù)結(jié)構(gòu)第1次課基本概念課件

1、第一章第一章 緒論緒論 計(jì)算機(jī)是一門(mén)研究利用計(jì)算機(jī)進(jìn)行信計(jì)算機(jī)是一門(mén)研究利用計(jì)算機(jī)進(jìn)行信息表示和處理的科學(xué)。息表示和處理的科學(xué)。 涉及：涉及： 信息的表示信息的表示 信息的處理信息的處理用計(jì)算機(jī)解決問(wèn)題的過(guò)程用計(jì)算機(jī)解決問(wèn)題的過(guò)程建立模型建立模型構(gòu)造求解算法構(gòu)造求解算法選擇存儲(chǔ)結(jié)構(gòu)選擇存儲(chǔ)結(jié)構(gòu)編寫(xiě)程序編寫(xiě)程序測(cè)試測(cè)試描述問(wèn)題的共描述問(wèn)題的共性性描述問(wèn)題的求描述問(wèn)題的求解方法解方法將問(wèn)題涉及的數(shù)據(jù)將問(wèn)題涉及的數(shù)據(jù)存儲(chǔ)到計(jì)算機(jī)中存儲(chǔ)到計(jì)算機(jī)中 早期：早期： 主要用于數(shù)值計(jì)算。主要用于數(shù)值計(jì)算。后來(lái)：后來(lái)： 處理逐漸擴(kuò)大到非數(shù)值計(jì)算領(lǐng)域（能處理逐漸擴(kuò)大到非數(shù)值計(jì)算領(lǐng)域（能處理多種復(fù)雜的具有一定結(jié)構(gòu)關(guān)

2、系的數(shù)處理多種復(fù)雜的具有一定結(jié)構(gòu)關(guān)系的數(shù)據(jù)）。據(jù)）。 早期：早期： 主要用于數(shù)值計(jì)算。主要用于數(shù)值計(jì)算。后來(lái)：后來(lái)： 處理逐漸擴(kuò)大到非數(shù)值計(jì)算領(lǐng)域（能處理逐漸擴(kuò)大到非數(shù)值計(jì)算領(lǐng)域（能處理多種復(fù)雜的具有一定結(jié)構(gòu)關(guān)系的數(shù)處理多種復(fù)雜的具有一定結(jié)構(gòu)關(guān)系的數(shù)據(jù)）。據(jù)）。登錄號(hào)：書(shū)名：作者名：分類(lèi)號(hào)：出版單位：出版時(shí)間：價(jià)格：書(shū)目卡片001高等數(shù)學(xué)樊映川S01002理論力學(xué)羅遠(yuǎn)祥L(zhǎng)01003高等數(shù)學(xué)華羅庚S01004線性代數(shù)欒汝書(shū)S02書(shū)目文件按書(shū)名按作者名按分類(lèi)號(hào)高等數(shù)學(xué)001，003理論力學(xué)002，.線性代數(shù)004，.樊映川001,華羅庚002,.欒汝書(shū)004,.L002,S001,003,索引表.

3、CEDABABACADBABCBDDADBDCEAEBECED用計(jì)算機(jī)解決問(wèn)題的過(guò)程用計(jì)算機(jī)解決問(wèn)題的過(guò)程建立模型建立模型構(gòu)造求解算法構(gòu)造求解算法選擇存儲(chǔ)結(jié)構(gòu)選擇存儲(chǔ)結(jié)構(gòu)編寫(xiě)程序編寫(xiě)程序測(cè)試測(cè)試描述問(wèn)題的共描述問(wèn)題的共性性描述問(wèn)題的求描述問(wèn)題的求解方法解方法將問(wèn)題涉及的數(shù)據(jù)將問(wèn)題涉及的數(shù)據(jù)存儲(chǔ)到計(jì)算機(jī)中存儲(chǔ)到計(jì)算機(jī)中面臨的問(wèn)題面臨的問(wèn)題復(fù)雜算法設(shè)計(jì)復(fù)雜算法設(shè)計(jì)?復(fù)雜存儲(chǔ)結(jié)構(gòu)？復(fù)雜存儲(chǔ)結(jié)構(gòu)？編程效率提高？編程效率提高？ 主要考慮的是設(shè)計(jì)出合適的數(shù)據(jù)結(jié)構(gòu)及相主要考慮的是設(shè)計(jì)出合適的數(shù)據(jù)結(jié)構(gòu)及相應(yīng)的算法。應(yīng)的算法。 即：首先要考慮對(duì)相關(guān)的各種信息如何表即：首先要考慮對(duì)相關(guān)的各種信息如何表示、組織和存

4、儲(chǔ)？示、組織和存儲(chǔ)？ 因此，簡(jiǎn)單說(shuō)來(lái)，因此，簡(jiǎn)單說(shuō)來(lái)，數(shù)據(jù)結(jié)構(gòu)是一門(mén)研究非數(shù)據(jù)結(jié)構(gòu)是一門(mén)研究非數(shù)值計(jì)算的程序設(shè)計(jì)問(wèn)題中計(jì)算機(jī)的操作數(shù)值計(jì)算的程序設(shè)計(jì)問(wèn)題中計(jì)算機(jī)的操作對(duì)象以及它們之間的關(guān)系和操作的學(xué)科。對(duì)象以及它們之間的關(guān)系和操作的學(xué)科。數(shù)據(jù)結(jié)構(gòu)課程的形成和發(fā)展數(shù)據(jù)結(jié)構(gòu)課程的形成和發(fā)展 形成階段形成階段l6060年代初期，年代初期，“數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)”有關(guān)的內(nèi)容散見(jiàn)于操作系有關(guān)的內(nèi)容散見(jiàn)于操作系統(tǒng)、編譯原理和表處理語(yǔ)言等課程。統(tǒng)、編譯原理和表處理語(yǔ)言等課程。l19681968年，美唐納德年，美唐納德克努特克努特(Donald Ervin Knuth)(Donald Ervin Knuth)教教

5、授開(kāi)創(chuàng)了數(shù)據(jù)結(jié)構(gòu)的最初體系，授開(kāi)創(chuàng)了數(shù)據(jù)結(jié)構(gòu)的最初體系，計(jì)算機(jī)程序設(shè)計(jì)技計(jì)算機(jī)程序設(shè)計(jì)技巧巧第一卷第一卷基本算法基本算法 ，“數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)”被列入美國(guó)被列入美國(guó)一些大學(xué)計(jì)算機(jī)科學(xué)系的教學(xué)計(jì)劃。一些大學(xué)計(jì)算機(jī)科學(xué)系的教學(xué)計(jì)劃。 發(fā)展階段：發(fā)展階段：l數(shù)據(jù)結(jié)構(gòu)的概念不斷擴(kuò)充，包括了網(wǎng)絡(luò)、集合代數(shù)論數(shù)據(jù)結(jié)構(gòu)的概念不斷擴(kuò)充，包括了網(wǎng)絡(luò)、集合代數(shù)論、關(guān)系等、關(guān)系等“離散數(shù)學(xué)結(jié)構(gòu)離散數(shù)學(xué)結(jié)構(gòu)”的內(nèi)容。的內(nèi)容。l7070年代后期，年代后期，8080年代初，我國(guó)高校陸續(xù)開(kāi)設(shè)該課程。年代初，我國(guó)高校陸續(xù)開(kāi)設(shè)該課程。 計(jì)算機(jī)程序設(shè)計(jì)技巧計(jì)算機(jī)程序設(shè)計(jì)技巧,【作者作者】（美）克努特（美）克努特（D.E. Knu

6、th）著；）著；管紀(jì)文，蘇運(yùn)霖譯管紀(jì)文，蘇運(yùn)霖譯 1968年，年，計(jì)算機(jī)程序設(shè)計(jì)藝術(shù)計(jì)算機(jī)程序設(shè)計(jì)藝術(shù)(TAOCP)的第一卷正式出版了。的第一卷正式出版了。這一卷的標(biāo)題叫這一卷的標(biāo)題叫基本算法基本算法，但，但難度卻并不低。據(jù)說(shuō)比爾難度卻并不低。據(jù)說(shuō)比爾蓋茨曾蓋茨曾經(jīng)花了幾個(gè)月的時(shí)間讀完這一卷，經(jīng)花了幾個(gè)月的時(shí)間讀完這一卷，并且做了大量的練習(xí)，然后他說(shuō)，并且做了大量的練習(xí)，然后他說(shuō)，如果你想成為一個(gè)優(yōu)秀的程序員，如果你想成為一個(gè)優(yōu)秀的程序員，那就去讀這個(gè)那就去讀這個(gè)基本算法基本算法吧。高吧。高德納本人的說(shuō)法更犀利：要是看不德納本人的說(shuō)法更犀利：要是看不懂，就別當(dāng)程序員。懂，就別當(dāng)程序員。 將數(shù)據(jù)

7、的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)以及將數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)以及對(duì)每種結(jié)構(gòu)所定義的操作組成了對(duì)每種結(jié)構(gòu)所定義的操作組成了“數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)”的主要內(nèi)容。此后，各的主要內(nèi)容。此后，各大學(xué)紛紛開(kāi)設(shè)大學(xué)紛紛開(kāi)設(shè)“數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)”課程。課程。1.2 基本概念和術(shù)語(yǔ)基本概念和術(shù)語(yǔ)C C在不同的編程環(huán)境中在不同的編程環(huán)境中 存儲(chǔ)結(jié)構(gòu)可有不同的描述方法。存儲(chǔ)結(jié)構(gòu)可有不同的描述方法。 當(dāng)用高級(jí)程序設(shè)計(jì)語(yǔ)言進(jìn)行編程時(shí)，通當(dāng)用高級(jí)程序設(shè)計(jì)語(yǔ)言進(jìn)行編程時(shí)，通?？捎酶呒?jí)編程語(yǔ)言中提供的數(shù)據(jù)類(lèi)型常可用高級(jí)編程語(yǔ)言中提供的數(shù)據(jù)類(lèi)型描述之。描述之。 例如：以三個(gè)帶有次序關(guān)系的整數(shù)表示例如：以三個(gè)帶有次序關(guān)系的整數(shù)表示一個(gè)長(zhǎng)整數(shù)時(shí)，

8、可利用一個(gè)長(zhǎng)整數(shù)時(shí)，可利用C+語(yǔ)言中提供語(yǔ)言中提供的整數(shù)數(shù)組類(lèi)型，定義長(zhǎng)整數(shù)為：的整數(shù)數(shù)組類(lèi)型，定義長(zhǎng)整數(shù)為： int long_int3;實(shí)現(xiàn)細(xì)節(jié)。如復(fù)數(shù)定義實(shí)現(xiàn)細(xì)節(jié)。如復(fù)數(shù)定義抽象數(shù)據(jù)類(lèi)型的表示和實(shí)現(xiàn)抽象數(shù)據(jù)類(lèi)型的表示和實(shí)現(xiàn)1.4 算法和算法分析算法和算法分析算法算法：是對(duì)特定問(wèn)題求解步驟的一種描述，是指令的有限序列，：是對(duì)特定問(wèn)題求解步驟的一種描述，是指令的有限序列，其中每一條指令表示一個(gè)或多個(gè)操作。其中每一條指令表示一個(gè)或多個(gè)操作。 算法具有以下五個(gè)特性：算法具有以下五個(gè)特性：（1）有窮性有窮性 一個(gè)算法必須總是在執(zhí)行有窮步之后結(jié)束，且每一個(gè)算法必須總是在執(zhí)行有窮步之后結(jié)束，且每一步都

9、在有窮時(shí)間內(nèi)完成。一步都在有窮時(shí)間內(nèi)完成。（2）確定性確定性 算法中每一條指令必須有確切的含義。不存在二義算法中每一條指令必須有確切的含義。不存在二義性。性。（3）可行性可行性 一個(gè)算法是可行的。即算法描述的操作都是可以通一個(gè)算法是可行的。即算法描述的操作都是可以通過(guò)已經(jīng)實(shí)現(xiàn)的基本運(yùn)算執(zhí)行有限次來(lái)實(shí)現(xiàn)的。過(guò)已經(jīng)實(shí)現(xiàn)的基本運(yùn)算執(zhí)行有限次來(lái)實(shí)現(xiàn)的。（4）輸入輸入 一個(gè)算法有零個(gè)或多個(gè)輸入，這些輸入取自于某個(gè)特一個(gè)算法有零個(gè)或多個(gè)輸入，這些輸入取自于某個(gè)特定的對(duì)象集合。定的對(duì)象集合。（5）輸出輸出 一個(gè)算法有一個(gè)或多個(gè)輸出，這些輸出是同輸入有著一個(gè)算法有一個(gè)或多個(gè)輸出，這些輸出是同輸入有著某些特定關(guān)

10、系的量。某些特定關(guān)系的量。1.4.2 1.4.2 算法設(shè)計(jì)的要求算法設(shè)計(jì)的要求評(píng)價(jià)一個(gè)好的算法有以下幾個(gè)標(biāo)準(zhǔn)評(píng)價(jià)一個(gè)好的算法有以下幾個(gè)標(biāo)準(zhǔn): :(1)(1)正確性正確性: :算法應(yīng)滿足具體問(wèn)題的需求。算法應(yīng)滿足具體問(wèn)題的需求。(2)(2)可讀性可讀性: :算法應(yīng)該好讀。以有利于閱讀者對(duì)程序的理解。算法應(yīng)該好讀。以有利于閱讀者對(duì)程序的理解。(3)(3)健狀性健狀性: :算法應(yīng)具有容錯(cuò)處理。當(dāng)輸入非法數(shù)據(jù)時(shí)，算法應(yīng)算法應(yīng)具有容錯(cuò)處理。當(dāng)輸入非法數(shù)據(jù)時(shí)，算法應(yīng)對(duì)其作出反應(yīng)，而不是產(chǎn)生莫名其妙的輸出結(jié)果。對(duì)其作出反應(yīng)，而不是產(chǎn)生莫名其妙的輸出結(jié)果。(4)(4)效率與存儲(chǔ)量需求效率與存儲(chǔ)量需求 效率指的

11、是算法執(zhí)行的時(shí)間；存儲(chǔ)量效率指的是算法執(zhí)行的時(shí)間；存儲(chǔ)量需求指算法執(zhí)行過(guò)程中所需要的最大存儲(chǔ)空間。一般，這兩者需求指算法執(zhí)行過(guò)程中所需要的最大存儲(chǔ)空間。一般，這兩者與問(wèn)題的規(guī)模有關(guān)。執(zhí)行時(shí)間少，存儲(chǔ)空間小。與問(wèn)題的規(guī)模有關(guān)。執(zhí)行時(shí)間少，存儲(chǔ)空間小。1.4.3 算法效率的度量算法效率的度量 對(duì)一個(gè)算法要作出全面的分析可分成兩種方法：對(duì)一個(gè)算法要作出全面的分析可分成兩種方法：事先分析事先分析 求出該算法的一個(gè)時(shí)間界限函數(shù)求出該算法的一個(gè)時(shí)間界限函數(shù)事后統(tǒng)計(jì)事后統(tǒng)計(jì) 收集此算法的執(zhí)行時(shí)間和實(shí)際占用空間的收集此算法的執(zhí)行時(shí)間和實(shí)際占用空間的統(tǒng)計(jì)資料。缺陷：一是必須先運(yùn)行依據(jù)算法編制的程統(tǒng)計(jì)資料。缺陷：

12、一是必須先運(yùn)行依據(jù)算法編制的程序；二是所得時(shí)間的統(tǒng)計(jì)量依賴(lài)于計(jì)算機(jī)的硬件、軟序；二是所得時(shí)間的統(tǒng)計(jì)量依賴(lài)于計(jì)算機(jī)的硬件、軟件等環(huán)境因素，有時(shí)容易掩蓋算法本身的優(yōu)劣。件等環(huán)境因素，有時(shí)容易掩蓋算法本身的優(yōu)劣。例、例、for(i=1;i=n;+i) for(j=1;j=n;+j) cij=0; for(k=1;k=n;+k) cij+=aik*bkj; 一般情況下，算法中基本操作一般情況下，算法中基本操作重復(fù)執(zhí)行的次數(shù)重復(fù)執(zhí)行的次數(shù)是問(wèn)是問(wèn)題規(guī)模題規(guī)模n的某個(gè)函數(shù)的某個(gè)函數(shù)f(n)，算法的時(shí)間量度記作，算法的時(shí)間量度記作 T(n)=O(f(n) 它表示隨問(wèn)題規(guī)模它表示隨問(wèn)題規(guī)模n的增大，算法執(zhí)行時(shí)

13、間的增長(zhǎng)率和的增大，算法執(zhí)行時(shí)間的增長(zhǎng)率和 f(n)的增長(zhǎng)率相同，稱(chēng)作算法的漸近時(shí)間復(fù)雜度，簡(jiǎn)稱(chēng)時(shí)的增長(zhǎng)率相同，稱(chēng)作算法的漸近時(shí)間復(fù)雜度，簡(jiǎn)稱(chēng)時(shí)間復(fù)雜度。間復(fù)雜度。 由于是一個(gè)三重循環(huán)，每個(gè)循環(huán)從由于是一個(gè)三重循環(huán)，每個(gè)循環(huán)從1到到n，則總次數(shù)為則總次數(shù)為: nnn=n3，時(shí)間復(fù)雜度為時(shí)間復(fù)雜度為T(mén)(n)=O(n3) 為了便于比較同一問(wèn)題的不同算法，通常的做法是為了便于比較同一問(wèn)題的不同算法，通常的做法是，從算法中選取一種對(duì)于所研究的問(wèn)題（或算法類(lèi)型），從算法中選取一種對(duì)于所研究的問(wèn)題（或算法類(lèi)型）來(lái)說(shuō)是來(lái)說(shuō)是基本操作基本操作的原操作，以該操作重復(fù)執(zhí)行的次數(shù)作的原操作，以該操作重復(fù)執(zhí)行的次數(shù)作

14、為算法的時(shí)間量度。為算法的時(shí)間量度。語(yǔ)句重復(fù)執(zhí)行的次數(shù)也稱(chēng)為語(yǔ)句的語(yǔ)句重復(fù)執(zhí)行的次數(shù)也稱(chēng)為語(yǔ)句的頻度頻度：例例 +x;s=0; 將將x自增看成是基本操作，則語(yǔ)句頻度為，即時(shí)間復(fù)雜度為自增看成是基本操作，則語(yǔ)句頻度為，即時(shí)間復(fù)雜度為(1) 如果將如果將s=0也看成是基本操作，則語(yǔ)句頻度為也看成是基本操作，則語(yǔ)句頻度為1，其時(shí)間復(fù)雜度，其時(shí)間復(fù)雜度仍為仍為(1)，即常量階。，即常量階。例例 for(i=1;i=n;+i) +x;s+=x; 語(yǔ)句頻度為：語(yǔ)句頻度為：n其時(shí)間復(fù)雜度為：其時(shí)間復(fù)雜度為：O(n) 即時(shí)間復(fù)雜度為線性階。即時(shí)間復(fù)雜度為線性階。i=0: 賦值次賦值次i=1: 賦值賦值 2 次

15、次i=2: 賦值賦值3次次i=n-1:賦值賦值n次次.+1+2+3+n=(1+n)n/2=n2/2+n/2例例 for(i=1;i=n;+i)for(j=1;j=n;+j) +x;s+=x; 語(yǔ)句頻度為：語(yǔ)句頻度為：n2其時(shí)間復(fù)雜度為：其時(shí)間復(fù)雜度為：O(n2) 即時(shí)間復(fù)雜度為平方階。即時(shí)間復(fù)雜度為平方階。例例 for(i=0;i=n-1;+i) for(j=0;j=i;+j)aij=0; 其時(shí)間復(fù)雜度為：其時(shí)間復(fù)雜度為：O(n2) 即時(shí)間復(fù)雜度為平方階。即時(shí)間復(fù)雜度為平方階。 取語(yǔ)句頻度增長(zhǎng)最快的項(xiàng)。取語(yǔ)句頻度增長(zhǎng)最快的項(xiàng)。 以下幾種計(jì)算算法時(shí)間的多項(xiàng)式是最常用的。其以下幾種計(jì)算算法時(shí)間的多

16、項(xiàng)式是最常用的。其關(guān)系為：關(guān)系為： 指數(shù)時(shí)間的關(guān)系為：指數(shù)時(shí)間的關(guān)系為： O(2n)O(n!)0 ;i-) for(j=0;jaj+1) aj aj+1; 最好情況：最好情況：0次次 最壞情況：每次都換，最壞情況：每次都換， (n2) 由小到大排列由小到大排列i=n-1: j從從0到到n-2 交換交換n-1次次.+(n-1)+(n-2)+(n-3)+1=(n-1)n/2=n2/2-n/2i=n-2: j從從0到到n-3 交換交換n-2次次i=n-3: j從從0到到n-4 交換交換n-3次次i=1: j從從0到到0 交換交換1次次注意：時(shí)間與空間往往是對(duì)矛盾，要綜合考慮。注意：時(shí)間與空間往往是對(duì)矛盾，要綜合考慮。1.4.4算法的存儲(chǔ)空間需求算法的存儲(chǔ)空間需求空間復(fù)雜度空間復(fù)雜度:算法所需存儲(chǔ)空間的度量，記作算法所需存儲(chǔ)空間的度量，記作: S(n)=O(f(n) 其中其中n為問(wèn)題的規(guī)模為問(wèn)題的規(guī)模(或大小或大小)本章學(xué)習(xí)要點(diǎn)本