《C語言程序設(shè)計(jì)與數(shù)據(jù)結(jié)構(gòu)》課件第12章

1、C語言程序設(shè)計(jì)與數(shù)據(jù)結(jié)構(gòu)第第12章章 數(shù)據(jù)結(jié)構(gòu)緒論數(shù)據(jù)結(jié)構(gòu)緒論教學(xué)目標(biāo)：通過本章的學(xué)習(xí)，使讀者能夠掌握數(shù)據(jù)結(jié)教學(xué)目標(biāo)：通過本章的學(xué)習(xí)，使讀者能夠掌握數(shù)據(jù)結(jié) 構(gòu)的概念和有關(guān)的術(shù)語。構(gòu)的概念和有關(guān)的術(shù)語。 C語言程序設(shè)計(jì)與數(shù)據(jù)結(jié)構(gòu)12.1 什么是數(shù)據(jù)結(jié)構(gòu) 計(jì)算機(jī)科學(xué)技術(shù)的廣泛應(yīng)用已從傳統(tǒng)的數(shù)值計(jì)計(jì)算機(jī)科學(xué)技術(shù)的廣泛應(yīng)用已從傳統(tǒng)的數(shù)值計(jì)算領(lǐng)域發(fā)展到各種非數(shù)值計(jì)算領(lǐng)域。為了有效地處算領(lǐng)域發(fā)展到各種非數(shù)值計(jì)算領(lǐng)域。為了有效地處理數(shù)據(jù)，需要為數(shù)據(jù)建立一定的結(jié)構(gòu)，描述所處理理數(shù)據(jù)，需要為數(shù)據(jù)建立一定的結(jié)構(gòu)，描述所處理的對(duì)象的特性以及各對(duì)象之間的關(guān)系。的對(duì)象的特性以及各對(duì)象之間的關(guān)系。 數(shù)據(jù)結(jié)構(gòu)這門學(xué)科主要是

2、研究各種結(jié)構(gòu)、定義數(shù)據(jù)結(jié)構(gòu)這門學(xué)科主要是研究各種結(jié)構(gòu)、定義在各種結(jié)構(gòu)上的操作和這些操作在計(jì)算機(jī)中的實(shí)現(xiàn)在各種結(jié)構(gòu)上的操作和這些操作在計(jì)算機(jī)中的實(shí)現(xiàn)方法。方法。 C語言程序設(shè)計(jì)與數(shù)據(jù)結(jié)構(gòu)用計(jì)算機(jī)解決一個(gè)具體問題時(shí)要考慮以下步驟 (1)(1)從具體問題中抽象出一個(gè)適當(dāng)?shù)臄?shù)學(xué)模型。即從從具體問題中抽象出一個(gè)適當(dāng)?shù)臄?shù)學(xué)模型。即從具體問題中找出操作對(duì)象之間含有的關(guān)系，然后具體問題中找出操作對(duì)象之間含有的關(guān)系，然后用數(shù)學(xué)語言加以描述。用數(shù)學(xué)語言加以描述。(2)(2)設(shè)計(jì)一個(gè)適合該數(shù)學(xué)模型的算法（設(shè)計(jì)一個(gè)適合該數(shù)學(xué)模型的算法（Algorithm）。）。(3)(3)編寫程序。編寫程序。 (4) 進(jìn)行測(cè)試、調(diào)整

3、、修改，直至解決問題。進(jìn)行測(cè)試、調(diào)整、修改，直至解決問題。 所以，數(shù)據(jù)結(jié)構(gòu)是研究程序設(shè)計(jì)中計(jì)算機(jī)操所以，數(shù)據(jù)結(jié)構(gòu)是研究程序設(shè)計(jì)中計(jì)算機(jī)操作的對(duì)象以及它們之間的關(guān)系和運(yùn)算的一門學(xué)科。作的對(duì)象以及它們之間的關(guān)系和運(yùn)算的一門學(xué)科。 C語言程序設(shè)計(jì)與數(shù)據(jù)結(jié)構(gòu)實(shí)際問題中，各個(gè)對(duì)象之間的關(guān)系有：實(shí)際問題中，各個(gè)對(duì)象之間的關(guān)系有：線性的：線性的：列車中各車箱之間的關(guān)系，排隊(duì)買車票列車中各車箱之間的關(guān)系，排隊(duì)買車票的人之間的關(guān)系，一疊盤子中各盤子之間的關(guān)系都的人之間的關(guān)系，一疊盤子中各盤子之間的關(guān)系都是線性的。是線性的。 層次的：在軍隊(duì)的編制中，軍下面是師，師下面是層次的：在軍隊(duì)的編制中，軍下面是師，師下面是

4、團(tuán)，軍、師、團(tuán)之間是層次關(guān)系；在人的輩分關(guān)系團(tuán)，軍、師、團(tuán)之間是層次關(guān)系；在人的輩分關(guān)系中，祖輩下是父輩，父輩下是子輩，這些是層次關(guān)中，祖輩下是父輩，父輩下是子輩，這些是層次關(guān)系；在學(xué)校的編制中，學(xué)校分成若干個(gè)學(xué)院、學(xué)院系；在學(xué)校的編制中，學(xué)校分成若干個(gè)學(xué)院、學(xué)院下又分成若干個(gè)系、系下又分成若干個(gè)教研室，這下又分成若干個(gè)系、系下又分成若干個(gè)教研室，這些也都是層次關(guān)系。些也都是層次關(guān)系。 網(wǎng)狀的：在城市鐵路交通圖中，各城市之間的關(guān)系網(wǎng)狀的：在城市鐵路交通圖中，各城市之間的關(guān)系是網(wǎng)狀關(guān)系。在電話網(wǎng)中，各電話之間是網(wǎng)狀關(guān)系。是網(wǎng)狀關(guān)系。在電話網(wǎng)中，各電話之間是網(wǎng)狀關(guān)系。 對(duì)象之間的關(guān)系C語言程序設(shè)計(jì)

5、與數(shù)據(jù)結(jié)構(gòu)12.2 基本概念和術(shù)語基本概念和術(shù)語 數(shù)據(jù)數(shù)據(jù) 數(shù)據(jù)是人們利用文字符號(hào)、數(shù)字符號(hào)以及其他規(guī)定數(shù)據(jù)是人們利用文字符號(hào)、數(shù)字符號(hào)以及其他規(guī)定的符號(hào)對(duì)現(xiàn)實(shí)世界的事物及其活動(dòng)所做的描述。在的符號(hào)對(duì)現(xiàn)實(shí)世界的事物及其活動(dòng)所做的描述。在計(jì)算機(jī)科學(xué)中，數(shù)據(jù)的含義非常廣泛，我們把一切計(jì)算機(jī)科學(xué)中，數(shù)據(jù)的含義非常廣泛，我們把一切能夠輸入到計(jì)算機(jī)中并被計(jì)算機(jī)程序處理的信息，能夠輸入到計(jì)算機(jī)中并被計(jì)算機(jī)程序處理的信息，包括文字、表格、圖象等，都稱為數(shù)據(jù)。包括文字、表格、圖象等，都稱為數(shù)據(jù)。 C語言程序設(shè)計(jì)與數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)舉例一個(gè)個(gè)人書庫管理程序所要處理的數(shù)據(jù)可能是一張如一個(gè)個(gè)人書庫管理程序所要處理的數(shù)據(jù)可

6、能是一張如表所示的表格。表所示的表格。C語言程序設(shè)計(jì)與數(shù)據(jù)結(jié)構(gòu)結(jié)點(diǎn) 結(jié)點(diǎn)也叫數(shù)據(jù)元素，它是組成數(shù)據(jù)的基本單結(jié)點(diǎn)也叫數(shù)據(jù)元素，它是組成數(shù)據(jù)的基本單位。在程序中通常把結(jié)點(diǎn)作為一個(gè)整體進(jìn)行考慮和位。在程序中通常把結(jié)點(diǎn)作為一個(gè)整體進(jìn)行考慮和處理。例如，在上表所示的個(gè)人書庫中，為了便于處理。例如，在上表所示的個(gè)人書庫中，為了便于處理，把其中的每一行（代表一本書）作為一個(gè)基處理，把其中的每一行（代表一本書）作為一個(gè)基本單位來考慮，故該數(shù)據(jù)由本單位來考慮，故該數(shù)據(jù)由10個(gè)結(jié)點(diǎn)構(gòu)成。個(gè)結(jié)點(diǎn)構(gòu)成。 一般情況下，一個(gè)結(jié)點(diǎn)中含有若干個(gè)字段一般情況下，一個(gè)結(jié)點(diǎn)中含有若干個(gè)字段（也叫數(shù)據(jù)項(xiàng)）。例如，在上表所示的表格數(shù)據(jù)

7、中，（也叫數(shù)據(jù)項(xiàng)）。例如，在上表所示的表格數(shù)據(jù)中，每個(gè)結(jié)點(diǎn)都有登錄號(hào)、書號(hào)、書名、作者、出版社每個(gè)結(jié)點(diǎn)都有登錄號(hào)、書號(hào)、書名、作者、出版社和價(jià)格等六個(gè)字段構(gòu)成。和價(jià)格等六個(gè)字段構(gòu)成。 字段是構(gòu)成數(shù)據(jù)的最小單位。字段是構(gòu)成數(shù)據(jù)的最小單位。C語言程序設(shè)計(jì)與數(shù)據(jù)結(jié)構(gòu)邏輯結(jié)構(gòu) 結(jié)點(diǎn)和結(jié)點(diǎn)之間的邏輯關(guān)系稱為數(shù)據(jù)的邏輯結(jié)構(gòu)。結(jié)點(diǎn)和結(jié)點(diǎn)之間的邏輯關(guān)系稱為數(shù)據(jù)的邏輯結(jié)構(gòu)。 在上表所示的表格數(shù)據(jù)中，各結(jié)點(diǎn)之間在邏輯在上表所示的表格數(shù)據(jù)中，各結(jié)點(diǎn)之間在邏輯上有一種線性關(guān)系，它指出了上有一種線性關(guān)系，它指出了10個(gè)結(jié)點(diǎn)在表中的排個(gè)結(jié)點(diǎn)在表中的排列順序。根據(jù)這種線性關(guān)系，可以看出表中第一本列順序。根據(jù)這種線性關(guān)系，可

8、以看出表中第一本書是什么書，第二本書是什么書，等等。書是什么書，第二本書是什么書，等等。 C語言程序設(shè)計(jì)與數(shù)據(jù)結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu) 數(shù)據(jù)在計(jì)算機(jī)中的存儲(chǔ)表示稱為數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)。數(shù)據(jù)在計(jì)算機(jī)中的存儲(chǔ)表示稱為數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)。 在上表所示的表格數(shù)據(jù)在計(jì)算機(jī)中可以有多在上表所示的表格數(shù)據(jù)在計(jì)算機(jī)中可以有多種存儲(chǔ)表示，例如，可以表示成數(shù)組，存放在內(nèi)種存儲(chǔ)表示，例如，可以表示成數(shù)組，存放在內(nèi)存中；也可以表示成文件，存放在磁盤上，等等。存中；也可以表示成文件，存放在磁盤上，等等。 C語言程序設(shè)計(jì)與數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)處理 數(shù)據(jù)處理：是指對(duì)數(shù)據(jù)進(jìn)行查找、插入、刪除、合數(shù)據(jù)處理：是指對(duì)數(shù)據(jù)進(jìn)行查找、插入、刪除、合并、排序、統(tǒng)計(jì)

9、以及簡(jiǎn)單計(jì)算等的操作過程。并、排序、統(tǒng)計(jì)以及簡(jiǎn)單計(jì)算等的操作過程。例：例：從數(shù)據(jù)結(jié)構(gòu)從數(shù)據(jù)結(jié)構(gòu)S中找出滿足條件的結(jié)點(diǎn)在中找出滿足條件的結(jié)點(diǎn)在 S 中位置的中位置的運(yùn)算是型運(yùn)算。運(yùn)算是型運(yùn)算。從數(shù)據(jù)結(jié)構(gòu)從數(shù)據(jù)結(jié)構(gòu)S S中讀出結(jié)構(gòu)中指定位置上內(nèi)容運(yùn)算是中讀出結(jié)構(gòu)中指定位置上內(nèi)容運(yùn)算是型運(yùn)算。型運(yùn)算。 從數(shù)據(jù)結(jié)構(gòu)從數(shù)據(jù)結(jié)構(gòu)S S中修改結(jié)構(gòu)中某指定結(jié)點(diǎn)內(nèi)容的運(yùn)算中修改結(jié)構(gòu)中某指定結(jié)點(diǎn)內(nèi)容的運(yùn)算是型運(yùn)算。是型運(yùn)算。 C語言程序設(shè)計(jì)與數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)（Data Structure） 數(shù)據(jù)結(jié)構(gòu)：是研究數(shù)據(jù)元素（數(shù)據(jù)結(jié)構(gòu)：是研究數(shù)據(jù)元素（Data Element）之間之間抽象化的相互關(guān)系和這種關(guān)系在計(jì)算機(jī)中的

10、存儲(chǔ)表抽象化的相互關(guān)系和這種關(guān)系在計(jì)算機(jī)中的存儲(chǔ)表示（即所謂數(shù)據(jù)的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)），并對(duì)這示（即所謂數(shù)據(jù)的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)），并對(duì)這種結(jié)構(gòu)定義相適應(yīng)的運(yùn)算，設(shè)計(jì)出相應(yīng)的算法，而種結(jié)構(gòu)定義相適應(yīng)的運(yùn)算，設(shè)計(jì)出相應(yīng)的算法，而且確保經(jīng)過這些運(yùn)算后所得到的新結(jié)構(gòu)仍然是原來且確保經(jīng)過這些運(yùn)算后所得到的新結(jié)構(gòu)仍然是原來的結(jié)構(gòu)類型。的結(jié)構(gòu)類型。 為了敘述上的方便和避免產(chǎn)生混淆，通常我們?yōu)榱藬⑹錾系姆奖愫捅苊猱a(chǎn)生混淆，通常我們 把數(shù)據(jù)的邏輯結(jié)構(gòu)統(tǒng)稱為數(shù)據(jù)結(jié)構(gòu)；把數(shù)據(jù)的物理把數(shù)據(jù)的邏輯結(jié)構(gòu)統(tǒng)稱為數(shù)據(jù)結(jié)構(gòu)；把數(shù)據(jù)的物理結(jié)構(gòu)統(tǒng)稱為存儲(chǔ)結(jié)構(gòu)（結(jié)構(gòu)統(tǒng)稱為存儲(chǔ)結(jié)構(gòu)（Storage Structure）。）。 C語言

11、程序設(shè)計(jì)與數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)類型數(shù)據(jù)類型 數(shù)據(jù)類型是指程序設(shè)計(jì)語言中各變量可取的數(shù)數(shù)據(jù)類型是指程序設(shè)計(jì)語言中各變量可取的數(shù)據(jù)種類。數(shù)據(jù)類型是高級(jí)程序設(shè)計(jì)語言中的一個(gè)基據(jù)種類。數(shù)據(jù)類型是高級(jí)程序設(shè)計(jì)語言中的一個(gè)基本概念，它和數(shù)據(jù)結(jié)構(gòu)的概念密切相關(guān)。本概念，它和數(shù)據(jù)結(jié)構(gòu)的概念密切相關(guān)。 一方面，在程序設(shè)計(jì)語言中，每一個(gè)數(shù)據(jù)都屬一方面，在程序設(shè)計(jì)語言中，每一個(gè)數(shù)據(jù)都屬于某種數(shù)據(jù)類型。類型明顯或隱含地規(guī)定了數(shù)據(jù)的于某種數(shù)據(jù)類型。類型明顯或隱含地規(guī)定了數(shù)據(jù)的取值范圍、存儲(chǔ)方式以及允許進(jìn)行的運(yùn)算?？梢哉J(rèn)取值范圍、存儲(chǔ)方式以及允許進(jìn)行的運(yùn)算。可以認(rèn)為，數(shù)據(jù)類型是在程序設(shè)計(jì)中已經(jīng)實(shí)現(xiàn)了的數(shù)據(jù)結(jié)為，數(shù)據(jù)類型是在程序設(shè)

12、計(jì)中已經(jīng)實(shí)現(xiàn)了的數(shù)據(jù)結(jié)構(gòu)。構(gòu)。 另一方面，在程序設(shè)計(jì)過程中，當(dāng)需要引入另一方面，在程序設(shè)計(jì)過程中，當(dāng)需要引入某種新的數(shù)據(jù)結(jié)構(gòu)時(shí)，總是借助編程語言所提供的某種新的數(shù)據(jù)結(jié)構(gòu)時(shí)，總是借助編程語言所提供的數(shù)據(jù)類型來描述數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)。數(shù)據(jù)類型來描述數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)。 C語言程序設(shè)計(jì)與數(shù)據(jù)結(jié)構(gòu)算法 簡(jiǎn)單地說就是解決特定問題的方法。特定的簡(jiǎn)單地說就是解決特定問題的方法。特定的問題可以是數(shù)值的，也可以是非數(shù)值的。問題可以是數(shù)值的，也可以是非數(shù)值的。解決數(shù)值問題的算法叫做數(shù)值算法，科學(xué)和工程計(jì)解決數(shù)值問題的算法叫做數(shù)值算法，科學(xué)和工程計(jì)算方面的算法都屬于數(shù)值算法，如求解數(shù)值積分，算方面的算法都屬于數(shù)值算法，如求

13、解數(shù)值積分，求解線性方程組、求解代數(shù)方程、求解微分方程等。求解線性方程組、求解代數(shù)方程、求解微分方程等。解決非數(shù)值問題的算法叫做非數(shù)值算法，數(shù)據(jù)處理解決非數(shù)值問題的算法叫做非數(shù)值算法，數(shù)據(jù)處理方面的算法都屬于非數(shù)值算法。例如各種排序算法、方面的算法都屬于非數(shù)值算法。例如各種排序算法、查找算法、插入算法、刪除算法、遍歷算法等。查找算法、插入算法、刪除算法、遍歷算法等。 數(shù)值算法和非數(shù)值算法并沒有嚴(yán)格的區(qū)別。數(shù)值算法和非數(shù)值算法并沒有嚴(yán)格的區(qū)別。 C語言程序設(shè)計(jì)與數(shù)據(jù)結(jié)構(gòu)12.3 算法和算法的描述算法和算法的描述 算法是執(zhí)行特定計(jì)算的有窮過程。這個(gè)過程有算法是執(zhí)行特定計(jì)算的有窮過程。這個(gè)過程有5個(gè)

14、特點(diǎn)：個(gè)特點(diǎn)：（1）動(dòng)態(tài)有窮：當(dāng)執(zhí)行一個(gè)算法時(shí)，不論是何種情動(dòng)態(tài)有窮：當(dāng)執(zhí)行一個(gè)算法時(shí)，不論是何種情況，在經(jīng)過了有限步驟后，這個(gè)算法一定要終止。況，在經(jīng)過了有限步驟后，這個(gè)算法一定要終止。 （2）確定性：算法中的每條指令都必須有確切的確定性：算法中的每條指令都必須有確切的含義，不能有二義性。含義，不能有二義性。 （3）輸入：具有輸入：具有0個(gè)或個(gè)或0個(gè)以上由外界提供的輸入個(gè)以上由外界提供的輸入量。量。 （4）輸出：產(chǎn)生輸出：產(chǎn)生1個(gè)或多個(gè)結(jié)果。個(gè)或多個(gè)結(jié)果。 （5）可行性：算法中描述的操作都是可以通過已可行性：算法中描述的操作都是可以通過已經(jīng)實(shí)現(xiàn)的基本運(yùn)算執(zhí)行有限次來實(shí)現(xiàn)的。經(jīng)實(shí)現(xiàn)的基本運(yùn)算執(zhí)

15、行有限次來實(shí)現(xiàn)的。 C語言程序設(shè)計(jì)與數(shù)據(jù)結(jié)構(gòu)算法的描述 一個(gè)算法可以用自然語言、數(shù)字語言或約定一個(gè)算法可以用自然語言、數(shù)字語言或約定的符號(hào)來描述，也可以用計(jì)算機(jī)高級(jí)程序語言來描的符號(hào)來描述，也可以用計(jì)算機(jī)高級(jí)程序語言來描述，如述，如Pascal語言、語言、C語言或偽代碼等。語言或偽代碼等。 本書選用本書選用C語言作為描述算法的工具。語言作為描述算法的工具。 C語言程序設(shè)計(jì)與數(shù)據(jù)結(jié)構(gòu)算法評(píng)價(jià) 設(shè)計(jì)一個(gè)好的算法應(yīng)考慮以下幾個(gè)方面：設(shè)計(jì)一個(gè)好的算法應(yīng)考慮以下幾個(gè)方面：正確性正確性 運(yùn)行時(shí)間運(yùn)行時(shí)間 占用的存儲(chǔ)空間占用的存儲(chǔ)空間 簡(jiǎn)單性簡(jiǎn)單性 C語言程序設(shè)計(jì)與數(shù)據(jù)結(jié)構(gòu)正確性 “正確正確”的含義在通常的

16、用法中有很大的差別，的含義在通常的用法中有很大的差別，大體可分為以下四個(gè)層次：大體可分為以下四個(gè)層次：程序不含語法錯(cuò)誤；程序不含語法錯(cuò)誤；程序?qū)τ趲捉M輸入數(shù)據(jù)能夠得出滿足規(guī)格說明要求程序?qū)τ趲捉M輸入數(shù)據(jù)能夠得出滿足規(guī)格說明要求的結(jié)果；的結(jié)果；程序?qū)τ诰倪x擇的典型、苛刻而帶有刁難性的幾程序?qū)τ诰倪x擇的典型、苛刻而帶有刁難性的幾組數(shù)據(jù)能夠得出滿足規(guī)格說明要求的結(jié)果；組數(shù)據(jù)能夠得出滿足規(guī)格說明要求的結(jié)果；程序?qū)σ磺泻戏ǖ妮斎霐?shù)據(jù)都能產(chǎn)生滿足規(guī)格說明程序?qū)σ磺泻戏ǖ妮斎霐?shù)據(jù)都能產(chǎn)生滿足規(guī)格說明要求的結(jié)果。要求的結(jié)果。 C語言程序設(shè)計(jì)與數(shù)據(jù)結(jié)構(gòu)運(yùn)行時(shí)間 運(yùn)行時(shí)間是指一個(gè)算法在計(jì)算機(jī)上運(yùn)算所花費(fèi)的時(shí)間

17、。運(yùn)行時(shí)間是指一個(gè)算法在計(jì)算機(jī)上運(yùn)算所花費(fèi)的時(shí)間。它大致等于計(jì)算機(jī)執(zhí)行一種簡(jiǎn)單操作（如賦值操作、轉(zhuǎn)向它大致等于計(jì)算機(jī)執(zhí)行一種簡(jiǎn)單操作（如賦值操作、轉(zhuǎn)向操作、比較操作等等）所需要的時(shí)間與算法中進(jìn)行簡(jiǎn)單操操作、比較操作等等）所需要的時(shí)間與算法中進(jìn)行簡(jiǎn)單操作次數(shù)的乘積。通常把算法中包含簡(jiǎn)單操作次數(shù)的多少叫作次數(shù)的乘積。通常把算法中包含簡(jiǎn)單操作次數(shù)的多少叫做算法的時(shí)間復(fù)雜性，它是一個(gè)算法運(yùn)行時(shí)間的相對(duì)量度。做算法的時(shí)間復(fù)雜性，它是一個(gè)算法運(yùn)行時(shí)間的相對(duì)量度。 在算法分析中絕對(duì)的量不能反映時(shí)間復(fù)雜度，使用一在算法分析中絕對(duì)的量不能反映時(shí)間復(fù)雜度，使用一個(gè)函數(shù)個(gè)函數(shù)(n)表示一個(gè)算法的復(fù)雜度。一個(gè)算法所解

18、決問題表示一個(gè)算法的復(fù)雜度。一個(gè)算法所解決問題的規(guī)模的規(guī)模n增大時(shí)，時(shí)間的增長(zhǎng)率越小，時(shí)間復(fù)雜度越好，反增大時(shí)，時(shí)間的增長(zhǎng)率越小，時(shí)間復(fù)雜度越好，反之時(shí)間復(fù)雜度越壞。也就是說，時(shí)間復(fù)雜度是之時(shí)間復(fù)雜度越壞。也就是說，時(shí)間復(fù)雜度是n的一個(gè)函數(shù)。的一個(gè)函數(shù)。 從好到壞表示時(shí)間復(fù)雜度的函數(shù)依次是：常量從好到壞表示時(shí)間復(fù)雜度的函數(shù)依次是：常量階階O(1)；對(duì)對(duì)數(shù)階數(shù)階O(log n)；線性階線性階O(n)；平方階平方階O(n2 )；多項(xiàng)式階多項(xiàng)式階O(nk)；指數(shù)階指數(shù)階O(2n)等。等。 C語言程序設(shè)計(jì)與數(shù)據(jù)結(jié)構(gòu)時(shí)間復(fù)雜度舉例下列三段程序的時(shí)間復(fù)雜度分別是：下列三段程序的時(shí)間復(fù)雜度分別是： x+;s

19、=x+2; 時(shí)間復(fù)雜度為時(shí)間復(fù)雜度為(1) for(k=1;k=n;k+) s=k+2: 時(shí)間復(fù)雜度為時(shí)間復(fù)雜度為(n) for (k=1;k=n; k+) for(j=1;j=n;j+) s=k+j: 時(shí)間復(fù)雜度為時(shí)間復(fù)雜度為(n2) C語言程序設(shè)計(jì)與數(shù)據(jù)結(jié)構(gòu)占用的存儲(chǔ)空間 一個(gè)算法在計(jì)算機(jī)存儲(chǔ)器上所占用的存儲(chǔ)空一個(gè)算法在計(jì)算機(jī)存儲(chǔ)器上所占用的存儲(chǔ)空間，包括存儲(chǔ)算法本身所占用的存儲(chǔ)空間，算法的間，包括存儲(chǔ)算法本身所占用的存儲(chǔ)空間，算法的輸入、輸出數(shù)據(jù)所占用的存儲(chǔ)空間和算法運(yùn)行過程輸入、輸出數(shù)據(jù)所占用的存儲(chǔ)空間和算法運(yùn)行過程中臨時(shí)占用的存儲(chǔ)空間。中臨時(shí)占用的存儲(chǔ)空間。 分析一個(gè)算法所占用的存儲(chǔ)空間要從各方面綜分析一個(gè)算法所占用的存儲(chǔ)空間要從各方面綜合考慮。合考慮。 算法在運(yùn)行過程中所占用的存儲(chǔ)空間的大小被算法在運(yùn)行過程中所