數(shù)據(jù)結(jié)構(gòu)第1章緒論(第1-2講補(bǔ)充結(jié)構(gòu)體)

1、第第 1 1章章緒緒論論本章主題：數(shù)據(jù)結(jié)構(gòu)的基本概念和術(shù)語(yǔ)本章主題：數(shù)據(jù)結(jié)構(gòu)的基本概念和術(shù)語(yǔ)教學(xué)目的：了解數(shù)據(jù)結(jié)構(gòu)的基本概念，理解常教學(xué)目的：了解數(shù)據(jù)結(jié)構(gòu)的基本概念，理解常用術(shù)語(yǔ)用術(shù)語(yǔ)教學(xué)重點(diǎn)：熟悉數(shù)據(jù)結(jié)構(gòu)常用術(shù)語(yǔ)，掌握基本教學(xué)重點(diǎn)：熟悉數(shù)據(jù)結(jié)構(gòu)常用術(shù)語(yǔ)，掌握基本概念，了解算法時(shí)間復(fù)雜度和空間復(fù)雜度的分概念，了解算法時(shí)間復(fù)雜度和空間復(fù)雜度的分析與評(píng)價(jià)析與評(píng)價(jià) 教學(xué)難點(diǎn)：數(shù)據(jù)元素間的教學(xué)難點(diǎn)：數(shù)據(jù)元素間的 4 4 種結(jié)構(gòu)關(guān)系。種結(jié)構(gòu)關(guān)系。緒論緒論第第 1 1章章緒緒論論針對(duì)每一種新的應(yīng)用領(lǐng)域的處理對(duì)象：針對(duì)每一種新的應(yīng)用領(lǐng)域的處理對(duì)象：如何選擇合適的數(shù)據(jù)表示（結(jié)構(gòu)）；如何選擇合適的數(shù)據(jù)表示（結(jié)構(gòu)

2、）；如何有效地組織計(jì)算機(jī)存儲(chǔ)；如何有效地組織計(jì)算機(jī)存儲(chǔ)；在此基礎(chǔ)上又如何有效地實(shí)現(xiàn)對(duì)象之間的在此基礎(chǔ)上又如何有效地實(shí)現(xiàn)對(duì)象之間的“運(yùn)算運(yùn)算”關(guān)系；關(guān)系；數(shù)據(jù)結(jié)構(gòu)就是研究和解決這些問(wèn)題的重要基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)就是研究和解決這些問(wèn)題的重要基礎(chǔ)理論。理論。為什么要學(xué)數(shù)據(jù)結(jié)構(gòu)為什么要學(xué)數(shù)據(jù)結(jié)構(gòu)第第 1 1章章緒緒論論數(shù)據(jù)結(jié)構(gòu)課程的主要內(nèi)容數(shù)據(jù)結(jié)構(gòu)課程的主要內(nèi)容數(shù)據(jù)結(jié)構(gòu)是一門(mén)研究數(shù)據(jù)結(jié)構(gòu)是一門(mén)研究非數(shù)值計(jì)算非數(shù)值計(jì)算的程序設(shè)計(jì)的程序設(shè)計(jì)問(wèn)題中計(jì)算機(jī)的操作對(duì)象以及它們之間的關(guān)問(wèn)題中計(jì)算機(jī)的操作對(duì)象以及它們之間的關(guān)系和操作的學(xué)科。系和操作的學(xué)科。數(shù)據(jù)結(jié)構(gòu)主要包括數(shù)據(jù)結(jié)構(gòu)主要包括3 3方面內(nèi)容：邏輯結(jié)構(gòu)、方面內(nèi)容：

3、邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)（或稱物理結(jié)構(gòu)）、數(shù)據(jù)運(yùn)算。存儲(chǔ)結(jié)構(gòu)（或稱物理結(jié)構(gòu)）、數(shù)據(jù)運(yùn)算。數(shù)據(jù)結(jié)構(gòu)在程序設(shè)計(jì)中的地位：數(shù)據(jù)結(jié)構(gòu)在程序設(shè)計(jì)中的地位：程序設(shè)計(jì)程序設(shè)計(jì) = = 算法算法 + + 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)第第 1 1章章緒緒論論一個(gè)含一個(gè)含1212位數(shù)的十進(jìn)制數(shù)可以用三個(gè)位數(shù)的十進(jìn)制數(shù)可以用三個(gè)4 4位的十進(jìn)制數(shù)表示位的十進(jìn)制數(shù)表示3214,6587,9345 a1(3214),a2(6587),a3(9345)3214,6587,9345 a1(3214),a2(6587),a3(9345)在在a1a1、a2a2和和a3 a3 之間存在之間存在“次序次序”關(guān)系關(guān)系 、 32143214，65876

4、587，9345 65879345 6587，32143214，93459345a1 a1 a2 a2 a3 a3 a2a2a1 a1 a3a3非數(shù)值計(jì)算的程序設(shè)計(jì)問(wèn)題非數(shù)值計(jì)算的程序設(shè)計(jì)問(wèn)題 例例1: 1: 求一組求一組(n(n個(gè)個(gè)) )整數(shù)中的最大值整數(shù)中的最大值算法算法: : 基本操作是基本操作是“比較兩個(gè)數(shù)的大小比較兩個(gè)數(shù)的大小”數(shù)據(jù)結(jié)構(gòu)：？數(shù)據(jù)結(jié)構(gòu)：？若整數(shù)為若整數(shù)為1212位數(shù)，在計(jì)算機(jī)中如何表示該數(shù)？位數(shù)，在計(jì)算機(jī)中如何表示該數(shù)？第第 1 1章章緒緒論論電話號(hào)碼查詢系統(tǒng)電話號(hào)碼查詢系統(tǒng)設(shè)有一個(gè)電話號(hào)碼薄，它記錄了設(shè)有一個(gè)電話號(hào)碼薄，它記錄了N N個(gè)人的名字和個(gè)人的名字和其相應(yīng)的電

5、話號(hào)碼。要求設(shè)計(jì)一個(gè)算法，當(dāng)給定其相應(yīng)的電話號(hào)碼。要求設(shè)計(jì)一個(gè)算法，當(dāng)給定任何一個(gè)人的名字時(shí)，該算法能夠打印出此人的任何一個(gè)人的名字時(shí)，該算法能夠打印出此人的電話號(hào)碼，如果該電話簿中根本就沒(méi)有這個(gè)人，電話號(hào)碼，如果該電話簿中根本就沒(méi)有這個(gè)人，則該算法也能夠報(bào)告沒(méi)有這個(gè)人的信息。則該算法也能夠報(bào)告沒(méi)有這個(gè)人的信息。算法的實(shí)現(xiàn)，依賴于計(jì)算機(jī)如何存儲(chǔ)人的名字和對(duì)算法的實(shí)現(xiàn)，依賴于計(jì)算機(jī)如何存儲(chǔ)人的名字和對(duì)應(yīng)的電話號(hào)碼，或者說(shuō)依賴于名字和其電話號(hào)碼的應(yīng)的電話號(hào)碼，或者說(shuō)依賴于名字和其電話號(hào)碼的結(jié)構(gòu)。結(jié)構(gòu)。第第 1 1章章緒緒論論數(shù)據(jù)結(jié)構(gòu)在程序設(shè)計(jì)中的地位：數(shù)據(jù)結(jié)構(gòu)在程序設(shè)計(jì)中的地位： 程序設(shè)計(jì)程序設(shè)計(jì)

6、 = = 算法算法 + + 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)是關(guān)于數(shù)據(jù)組織和處理的基本技數(shù)據(jù)結(jié)構(gòu)是關(guān)于數(shù)據(jù)組織和處理的基本技術(shù)的一門(mén)學(xué)科，是程序設(shè)計(jì)的中級(jí)課程，術(shù)的一門(mén)學(xué)科，是程序設(shè)計(jì)的中級(jí)課程，主要培養(yǎng)我們分析數(shù)據(jù)、組織數(shù)據(jù)的能力，主要培養(yǎng)我們分析數(shù)據(jù)、組織數(shù)據(jù)的能力，告訴我們?nèi)绾尉帉?xiě)效率高、結(jié)構(gòu)好的程序。告訴我們?nèi)绾尉帉?xiě)效率高、結(jié)構(gòu)好的程序。第第 1 1章章緒緒論論1 1數(shù)據(jù)數(shù)據(jù)(Data) (Data) 數(shù)據(jù)數(shù)據(jù)(Data)(Data)：是對(duì)信息的一種符號(hào)表示。：是對(duì)信息的一種符號(hào)表示。在計(jì)算機(jī)科學(xué)中是指所有能輸入到計(jì)算在計(jì)算機(jī)科學(xué)中是指所有能輸入到計(jì)算機(jī)中并被計(jì)算機(jī)程序處理的符號(hào)的總稱。機(jī)中并

7、被計(jì)算機(jī)程序處理的符號(hào)的總稱。包括文字、表格、圖象等。包括文字、表格、圖象等。 如一個(gè)圖書(shū)管理程序所要處理的數(shù)據(jù)可如一個(gè)圖書(shū)管理程序所要處理的數(shù)據(jù)可能是一張表格。能是一張表格。基本概念和基本概念和常用術(shù)語(yǔ)常用術(shù)語(yǔ)第第 1 1章章緒緒論論數(shù)據(jù)元素?cái)?shù)據(jù)元素(Data Element)(Data Element)：是數(shù)據(jù)的：是數(shù)據(jù)的基本單位基本單位，在計(jì)，在計(jì)算機(jī)程序中通常作為一個(gè)整體進(jìn)行考慮和處理。算機(jī)程序中通常作為一個(gè)整體進(jìn)行考慮和處理。一個(gè)數(shù)據(jù)元素可由若干個(gè)一個(gè)數(shù)據(jù)元素可由若干個(gè)數(shù)據(jù)項(xiàng)數(shù)據(jù)項(xiàng)組成。數(shù)據(jù)項(xiàng)是數(shù)組成。數(shù)據(jù)項(xiàng)是數(shù)據(jù)的不可分割的據(jù)的不可分割的最小單位最小單位?；靖拍詈突靖拍詈统Ｓ眯g(shù)

8、語(yǔ)常用術(shù)語(yǔ)數(shù)據(jù)元素是數(shù)據(jù)項(xiàng)的集合。例：數(shù)據(jù)元素是數(shù)據(jù)項(xiàng)的集合。例： 運(yùn)動(dòng)員信息表表頭如下：運(yùn)動(dòng)員信息表表頭如下：姓名姓名俱樂(lè)部俱樂(lè)部名稱名稱出生出生日期日期參 加參 加日期日期職務(wù)職務(wù)業(yè)績(jī)業(yè)績(jī)第第 1 1章章緒緒論論數(shù)據(jù)對(duì)象數(shù)據(jù)對(duì)象(Data Object)(Data Object)：是性質(zhì)相同的數(shù)據(jù)元素的：是性質(zhì)相同的數(shù)據(jù)元素的集合。是數(shù)據(jù)的一個(gè)子集。集合。是數(shù)據(jù)的一個(gè)子集。概念之間的關(guān)系：概念之間的關(guān)系：數(shù)據(jù)數(shù)據(jù)數(shù)據(jù)對(duì)象數(shù)據(jù)對(duì)象數(shù)據(jù)元素?cái)?shù)據(jù)元素?cái)?shù)據(jù)項(xiàng)數(shù)據(jù)項(xiàng)基本概念和基本概念和常用術(shù)語(yǔ)常用術(shù)語(yǔ)第第 1 1章章緒緒論論表表1 1 某班學(xué)生成績(jī)管理表某班學(xué)生成績(jī)管理表學(xué)號(hào)學(xué)號(hào)性別性別高數(shù)高數(shù)英語(yǔ)

9、英語(yǔ) C C語(yǔ)言程序設(shè)計(jì)語(yǔ)言程序設(shè)計(jì)101101F F909085857878102102M M898976769090103103M M767643436969104104M M585892927676例：通過(guò)下表說(shuō)明數(shù)據(jù)的相關(guān)概念例：通過(guò)下表說(shuō)明數(shù)據(jù)的相關(guān)概念第第 1 1章章緒緒論論數(shù)據(jù)結(jié)構(gòu)：是相互之間存在一種或多數(shù)據(jù)結(jié)構(gòu)：是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。種特定關(guān)系的數(shù)據(jù)元素的集合。問(wèn)題：數(shù)據(jù)結(jié)構(gòu)包括哪問(wèn)題：數(shù)據(jù)結(jié)構(gòu)包括哪3 3方面內(nèi)容？方面內(nèi)容？數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)(Data(Data Structure) Structure)第第 1 1章章緒緒論論邏輯結(jié)構(gòu)：描述數(shù)據(jù)元素

10、間的邏輯關(guān)系，與數(shù)據(jù)邏輯結(jié)構(gòu)：描述數(shù)據(jù)元素間的邏輯關(guān)系，與數(shù)據(jù)的存儲(chǔ)無(wú)關(guān)。的存儲(chǔ)無(wú)關(guān)。數(shù)據(jù)邏輯結(jié)構(gòu)可以用二元組（數(shù)據(jù)邏輯結(jié)構(gòu)可以用二元組（D D，R R）描述）描述D D：數(shù)據(jù)元素定義域集合：數(shù)據(jù)元素定義域集合R R：數(shù)據(jù)元素上的關(guān)系：數(shù)據(jù)元素上的關(guān)系r ri i的集合的集合主要討論主要討論R=rR=r的情況的情況關(guān)系關(guān)系r r中若有序偶中若有序偶，則，則a a稱為稱為b b的的前驅(qū)前驅(qū)，b b稱稱為為a a的的后繼后繼1.1.邏輯結(jié)構(gòu)邏輯結(jié)構(gòu)第第 1 1章章緒緒論論邏輯結(jié)構(gòu)可分為：邏輯結(jié)構(gòu)可分為：集合結(jié)構(gòu)集合結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù)元素除了同屬于一種類：結(jié)構(gòu)中的數(shù)據(jù)元素除了同屬于一種類型外，別無(wú)其

11、它關(guān)系。較少使用型外，別無(wú)其它關(guān)系。較少使用線性結(jié)構(gòu)線性結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一對(duì)一的：結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一對(duì)一的關(guān)系。關(guān)系。樹(shù)型結(jié)構(gòu)樹(shù)型結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一對(duì)多的：結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一對(duì)多的關(guān)系。關(guān)系。圖形結(jié)構(gòu)圖形結(jié)構(gòu)（或稱（或稱網(wǎng)狀結(jié)構(gòu)網(wǎng)狀結(jié)構(gòu)）：結(jié)構(gòu)中的數(shù)據(jù)元素）：結(jié)構(gòu)中的數(shù)據(jù)元素之間存在多對(duì)多的關(guān)系。之間存在多對(duì)多的關(guān)系。1.1.邏輯結(jié)構(gòu)邏輯結(jié)構(gòu)第第 1 1章章緒緒論論學(xué)號(hào)學(xué)號(hào)姓名姓名性別性別生日生日01丁一丁一男男02張三張三女女XXXOXOXOX沈陽(yáng)沈陽(yáng)北京北京西安西安長(zhǎng)沙長(zhǎng)沙廣州廣州重慶重慶烏魯木齊烏魯木齊拉薩拉薩23571113171923293

12、137線性結(jié)構(gòu)線性結(jié)構(gòu)樹(shù)型結(jié)構(gòu)樹(shù)型結(jié)構(gòu)圖形結(jié)構(gòu)圖形結(jié)構(gòu)集合結(jié)構(gòu)集合結(jié)構(gòu)第第 1 1章章緒緒論論一種數(shù)據(jù)結(jié)構(gòu)一種數(shù)據(jù)結(jié)構(gòu)G G（D, RD, R），其中），其中 D=D=1 1，2 2，3 3，4 4，5 5，6 6 R=R=r rr=r=， ， ， ， 試畫(huà)出對(duì)試畫(huà)出對(duì)應(yīng)的邏輯結(jié)構(gòu)圖，并說(shuō)明它是何種數(shù)據(jù)結(jié)構(gòu)？應(yīng)的邏輯結(jié)構(gòu)圖，并說(shuō)明它是何種數(shù)據(jù)結(jié)構(gòu)？邏輯邏輯結(jié)構(gòu)結(jié)構(gòu)舉例舉例第第 1 1章章緒緒論論物理結(jié)構(gòu)（存儲(chǔ)結(jié)構(gòu)）：數(shù)據(jù)結(jié)構(gòu)在計(jì)物理結(jié)構(gòu)（存儲(chǔ)結(jié)構(gòu)）：數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的存儲(chǔ)表示。它包括數(shù)據(jù)元素的算機(jī)中的存儲(chǔ)表示。它包括數(shù)據(jù)元素的表示和關(guān)系的表示。表示和關(guān)系的表示。基本物理結(jié)構(gòu)基本物理結(jié)構(gòu)順序存

13、儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)索引存儲(chǔ)結(jié)構(gòu)索引存儲(chǔ)結(jié)構(gòu)散列存儲(chǔ)結(jié)構(gòu)散列存儲(chǔ)結(jié)構(gòu)2.2.存儲(chǔ)結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)最常用的兩種存儲(chǔ)結(jié)構(gòu)最常用的兩種存儲(chǔ)結(jié)構(gòu)第第 1 1章章緒緒論論0 01 12 23 3.順序結(jié)構(gòu)空間示意圖順序結(jié)構(gòu)空間示意圖鏈?zhǔn)浇Y(jié)構(gòu)空間示意圖鏈?zhǔn)浇Y(jié)構(gòu)空間示意圖數(shù)組數(shù)組用指針實(shí)現(xiàn)用指針實(shí)現(xiàn)2.2.存儲(chǔ)結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)第第 1 1章章緒緒論論3.3.運(yùn)算集合運(yùn)算集合邏輯結(jié)構(gòu)決定了算法的設(shè)計(jì)。邏輯結(jié)構(gòu)決定了算法的設(shè)計(jì)。物理結(jié)構(gòu)決定了算法的實(shí)現(xiàn)。物理結(jié)構(gòu)決定了算法的實(shí)現(xiàn)。第第 1 1章章緒緒論論練習(xí)題1.1.從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為（從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為（ ）兩大類。兩大類。A A

14、動(dòng)態(tài)結(jié)構(gòu)、靜態(tài)結(jié)構(gòu)動(dòng)態(tài)結(jié)構(gòu)、靜態(tài)結(jié)構(gòu) B B順序結(jié)構(gòu)、鏈?zhǔn)浇Y(jié)構(gòu)順序結(jié)構(gòu)、鏈?zhǔn)浇Y(jié)構(gòu)C C線性結(jié)構(gòu)、非線性結(jié)構(gòu)線性結(jié)構(gòu)、非線性結(jié)構(gòu) D D初等結(jié)構(gòu)、構(gòu)造型結(jié)構(gòu)初等結(jié)構(gòu)、構(gòu)造型結(jié)構(gòu)第第 1 1章章緒緒論論練習(xí)題2.2.采用順序存儲(chǔ)結(jié)構(gòu)表示數(shù)據(jù)時(shí)，相鄰的采用順序存儲(chǔ)結(jié)構(gòu)表示數(shù)據(jù)時(shí)，相鄰的數(shù)數(shù)據(jù)元素的存儲(chǔ)地址（據(jù)元素的存儲(chǔ)地址（ ）。）。A A一定連續(xù)一定連續(xù) B B一定不連續(xù)一定不連續(xù) C C不一定連續(xù)不一定連續(xù) D D部分連續(xù)，部分不連續(xù)部分連續(xù)，部分不連續(xù)第第 1 1章章緒緒論論抽象數(shù)據(jù)類型（抽象數(shù)據(jù)類型（AbstructAbstruct Data Data TypeType，簡(jiǎn)稱簡(jiǎn)稱ADTADT

15、）第第 1 1章章緒緒論論抽象數(shù)據(jù)類型（抽象數(shù)據(jù)類型（AbstructAbstruct Data Data TypeType，簡(jiǎn)稱簡(jiǎn)稱ADTADT）第第 1 1章章緒緒論論算法算法：對(duì)特定問(wèn)題求解步驟的一種描述，是：對(duì)特定問(wèn)題求解步驟的一種描述，是指令的有限序列。其中每一條指令表示一個(gè)指令的有限序列。其中每一條指令表示一個(gè)或多個(gè)操作?；蚨鄠€(gè)操作。例：燒開(kāi)水的步驟（算法）：例：燒開(kāi)水的步驟（算法）：E1E1：清洗水壺；：清洗水壺；E2E2：將水壺灌入適量的涼水；：將水壺灌入適量的涼水；E3E3：把水壺放到灶上；：把水壺放到灶上；E4E4：打開(kāi)火；：打開(kāi)火；E5E5：注意傾聽(tīng)，直到聽(tīng)到水開(kāi)的聲音；

16、：注意傾聽(tīng)，直到聽(tīng)到水開(kāi)的聲音；E6E6：關(guān)火；：關(guān)火；E7E7：把開(kāi)水灌入暖瓶中；：把開(kāi)水灌入暖瓶中；第第 1 1章章緒緒論論有窮性有窮性：算法總在執(zhí)行有窮步后結(jié)束，且每：算法總在執(zhí)行有窮步后結(jié)束，且每一步都在有窮時(shí)間內(nèi)完成。一步都在有窮時(shí)間內(nèi)完成。確定性確定性：不存在二義性，且相同的輸入一定：不存在二義性，且相同的輸入一定得到相同的輸出。得到相同的輸出。可行性可行性：算法描述的操作都可通過(guò)已經(jīng)實(shí)現(xiàn)：算法描述的操作都可通過(guò)已經(jīng)實(shí)現(xiàn)的基本運(yùn)算執(zhí)行有限次來(lái)實(shí)現(xiàn)。的基本運(yùn)算執(zhí)行有限次來(lái)實(shí)現(xiàn)。輸入輸入：一個(gè)算法有零個(gè)或多個(gè)輸入。：一個(gè)算法有零個(gè)或多個(gè)輸入。輸出輸出：一個(gè)算法有一個(gè)或多個(gè)輸出。：一個(gè)算

17、法有一個(gè)或多個(gè)輸出。判斷題：算法必須有輸出，但可以沒(méi)有輸入。判斷題：算法必須有輸出，但可以沒(méi)有輸入。第第 1 1章章緒緒論論第第 1 1章章緒緒論論“好好”算法設(shè)計(jì)的要求算法設(shè)計(jì)的要求正確性正確性：算法應(yīng)滿足具體問(wèn)題的需求。：算法應(yīng)滿足具體問(wèn)題的需求?？勺x性可讀性：便于理解、調(diào)試和維護(hù)。：便于理解、調(diào)試和維護(hù)。健狀性健狀性：算法應(yīng)具有容錯(cuò)處理。當(dāng)輸入非法數(shù)據(jù)：算法應(yīng)具有容錯(cuò)處理。當(dāng)輸入非法數(shù)據(jù)時(shí)，算法應(yīng)對(duì)其作出反應(yīng)，而不是產(chǎn)生莫名其妙時(shí)，算法應(yīng)對(duì)其作出反應(yīng)，而不是產(chǎn)生莫名其妙的輸出結(jié)果。的輸出結(jié)果。高效性和存儲(chǔ)量需求：高效性和存儲(chǔ)量需求：求解同一問(wèn)題若有多種算求解同一問(wèn)題若有多種算法，則執(zhí)行時(shí)

18、間短的算法效率更高，占用存儲(chǔ)空法，則執(zhí)行時(shí)間短的算法效率更高，占用存儲(chǔ)空間少的算法較好。間少的算法較好。 第第 1 1章章緒緒論論算法的時(shí)間復(fù)雜度算法的時(shí)間復(fù)雜度是指算法運(yùn)行從開(kāi)始到結(jié)束所需要的時(shí)間；是指算法運(yùn)行從開(kāi)始到結(jié)束所需要的時(shí)間；是對(duì)算法運(yùn)行時(shí)間長(zhǎng)短的相對(duì)度量；是對(duì)算法運(yùn)行時(shí)間長(zhǎng)短的相對(duì)度量；是用算法包含的簡(jiǎn)單操作的次數(shù)度量，是是用算法包含的簡(jiǎn)單操作的次數(shù)度量，是問(wèn)問(wèn)題規(guī)模題規(guī)模的一個(gè)函數(shù)。的一個(gè)函數(shù)。在實(shí)際應(yīng)用中，往往放棄復(fù)雜的函數(shù)來(lái)表示在實(shí)際應(yīng)用中，往往放棄復(fù)雜的函數(shù)來(lái)表示確切的時(shí)間復(fù)雜度，而采用一些簡(jiǎn)單的函數(shù)確切的時(shí)間復(fù)雜度，而采用一些簡(jiǎn)單的函數(shù)來(lái)近似表示時(shí)間性能，這就是來(lái)近似表

19、示時(shí)間性能，這就是漸近時(shí)間復(fù)雜漸近時(shí)間復(fù)雜度度，簡(jiǎn)稱時(shí)間復(fù)雜度。，簡(jiǎn)稱時(shí)間復(fù)雜度。第第 1 1章章緒緒論論例例: :求下列算法的時(shí)間復(fù)雜度求下列算法的時(shí)間復(fù)雜度main()main() int a,b,cint a,b,c; ;c=a+bc=a+b; ;printf(“the end is:%d”,cprintf(“the end is:%d”,c);); 時(shí)間復(fù)雜度為時(shí)間復(fù)雜度為(1)(1)，即，即常量階常量階。第第 1 1章章緒緒論論例：求下列算法的時(shí)間復(fù)雜度：例：求下列算法的時(shí)間復(fù)雜度：int sum(intint sum(int n) n) int i,sint i,s=0;=0; f

20、or(i=1;i=n;ifor(i=1;i=n;i+)+) s+=i;s+=i; return s;return s;時(shí)間復(fù)雜度為時(shí)間復(fù)雜度為(n)(n)，即，即線性階線性階。第第 1 1章章緒緒論論例例: :計(jì)算計(jì)算f=1f=1！+2+2！+3+3！+ +n+n！void factorsumvoid factorsum（intint n n） int i,j,f,wint i,j,f,w；f=0f=0；forfor（i=1;i=n;ii=1;i=n;i+） w=1w=1； forfor（j=1;j=i;jj=1;j=i;j+）w=ww=w* *j j； f=f+wf=f+w； return

21、return； 時(shí)間復(fù)雜度為時(shí)間復(fù)雜度為(n(n2 2) )。第第 1 1章章緒緒論論例：例：for(I=1,I=n;+Ifor(I=1,I=n;+I) ) for(j=1;j=n;+j for(j=1;j=n;+j) ) cIj cIj=0;=0; for(k=1;k=n;+k for(k=1;k1 & change;-I) change=0; for(j=0;jaj+1) aj aj+1; change=1；該程序中的操作次數(shù)依據(jù)輸入數(shù)據(jù)的不同而該程序中的操作次數(shù)依據(jù)輸入數(shù)據(jù)的不同而不同，通常這種情況下以最壞的情況為依據(jù)不同，通常這種情況下以最壞的情況為依據(jù)計(jì)算時(shí)間復(fù)雜度為計(jì)算時(shí)間復(fù)雜度為

22、:O(n:O(n2 2) )第第 1 1章章緒緒論論常見(jiàn)的漸進(jìn)時(shí)間復(fù)雜度按數(shù)量級(jí)遞增常見(jiàn)的漸進(jìn)時(shí)間復(fù)雜度按數(shù)量級(jí)遞增排列為：排列為：(1)(1)(loglog2 2n)(n)(n)(n)(nlognlog2 2n)n)(n n2 2)()(n n3 3)(2)numstu2-num若定義了指向結(jié)構(gòu)體的指針變量，也可用若定義了指向結(jié)構(gòu)體的指針變量，也可用-來(lái)引用成員。來(lái)引用成員。第第 1 1章章緒緒論論結(jié)構(gòu)體變量的初始化結(jié)構(gòu)體變量的初始化結(jié)構(gòu)體變量的初始化，就是在定義結(jié)構(gòu)體變量的結(jié)構(gòu)體變量的初始化，就是在定義結(jié)構(gòu)體變量的同時(shí)，對(duì)其成員賦初值。同時(shí)，對(duì)其成員賦初值。結(jié)構(gòu)體變量初始化的格式：結(jié)構(gòu)體變

23、量初始化的格式：structstruct 結(jié)構(gòu)體名結(jié)構(gòu)體名 結(jié)構(gòu)體變量名結(jié)構(gòu)體變量名= = 初始數(shù)據(jù)初始數(shù)據(jù) ；與數(shù)組類似，結(jié)構(gòu)體變量只可整體初始化，不與數(shù)組類似，結(jié)構(gòu)體變量只可整體初始化，不可可整體賦值整體賦值，但結(jié)構(gòu)體變量間可以相互賦值。，但結(jié)構(gòu)體變量間可以相互賦值。第第 1 1章章緒緒論論main()struct student stu1；stu1=2010001,“Lifeng”,M,18,87.0, “Beijing”; 例：例：struct student long num; char name20; char sex; int age; float score; char add

24、r30;struct student stu1=2010001, “Li feng”, M, 18, 87.0, “Beijing”; 結(jié)構(gòu)體變量可以整體初始化。結(jié)構(gòu)體變量可以整體初始化。結(jié)構(gòu)體變量不可整體賦值。結(jié)構(gòu)體變量不可整體賦值。第第 1 1章章緒緒論論structstruct student student long num=2010001; long num=2010001; char name20=“ char name20=“Li fengLi feng”;”; char sex=M; char sex=M; int int age=18; age=18; float score

25、=87.0; float score=87.0; char addr30=“Beijing”; char addr30=“Beijing”; stu1,stu2; stu1,stu2;結(jié)構(gòu)體類型不能直接在結(jié)構(gòu)體成員表中對(duì)成結(jié)構(gòu)體類型不能直接在結(jié)構(gòu)體成員表中對(duì)成員賦初值員賦初值第第 1 1章章緒緒論論結(jié)構(gòu)體數(shù)組的概念結(jié)構(gòu)體數(shù)組的概念結(jié)構(gòu)體數(shù)組是其數(shù)組元素都是具有相同結(jié)構(gòu)體結(jié)構(gòu)體數(shù)組是其數(shù)組元素都是具有相同結(jié)構(gòu)體類型的結(jié)構(gòu)體變量。即結(jié)構(gòu)體數(shù)組是結(jié)構(gòu)體變類型的結(jié)構(gòu)體變量。即結(jié)構(gòu)體數(shù)組是結(jié)構(gòu)體變量集合的一種數(shù)組。量集合的一種數(shù)組。例如例如: :20100011 2010002 2010030 Life

26、ng Wangbing Chenming M M M 18 18 17 87 79 92 Beijing Beijing Beijing structstruct student student int int num; num; char name20; char name20; char sex; char sex; int int age; age; float score; float score; char addr30; char addr30; stu1,stu2, stu1,stu2,stu30; stu30; stu30;stu30;第第 1 1章章緒緒論論思考思考學(xué)生信息包括學(xué)號(hào)和成績(jī)學(xué)生信息包括學(xué)號(hào)和成績(jī)2 2項(xiàng)，請(qǐng)從鍵盤(pán)敲項(xiàng)，請(qǐng)從鍵盤(pán)敲入入4 4個(gè)學(xué)生的信息，然后計(jì)算該四名學(xué)生的個(gè)學(xué)生的信息，然后計(jì)算該四名學(xué)生的平均成績(jī)并輸出結(jié)果。平均成績(jī)并輸出結(jié)果。structstruct student studentintint num; num;intint score; score;structstruct student s4; student s4;第第 1 1章章緒緒論論用用typedeftypedef定義數(shù)據(jù)類型定義數(shù)據(jù)類型用用typedeftypedef定義數(shù)據(jù)類型定義數(shù)據(jù)類型就是給已經(jīng)存在的就是給已經(jīng)存在的數(shù)據(jù)類型重新命名一個(gè)新名字。