《Java版數(shù)據(jù)結(jié)構(gòu)(程序員必須看)課件.ppt》由會(huì)員分享，可在線閱讀，更多相關(guān)《Java版數(shù)據(jù)結(jié)構(gòu)(程序員必須看)課件.ppt（1062頁珍藏版）》請?jiān)趨R文網(wǎng)上搜索。

1、Java版數(shù)據(jù)結(jié)構(gòu)(程序員必須看)第一章第一章緒緒論論1.1什么是數(shù)據(jù)結(jié)構(gòu)什么是數(shù)據(jù)結(jié)構(gòu)1.2有關(guān)概念和術(shù)語有關(guān)概念和術(shù)語1.3算法和算法分析算法和算法分析1.3.1算法算法1.3.2算法設(shè)計(jì)的要求算法設(shè)計(jì)的要求1.3.3算法效率的度量算法效率的度量1.3.4算法的存儲(chǔ)空間的需求算法的存儲(chǔ)空間的需求第一章第一章 緒緒 論論 計(jì)算機(jī)學(xué)科一直處于高速發(fā)展中計(jì)算機(jī)學(xué)科一直處于高速發(fā)展中,而且這種發(fā)展速度還會(huì)持續(xù)。而且這種發(fā)展速度還會(huì)持續(xù)。計(jì)算機(jī)科學(xué)已經(jīng)難以完全覆蓋學(xué)科新的發(fā)展，因此擴(kuò)展后的計(jì)算機(jī)科學(xué)已經(jīng)難以完全覆蓋學(xué)科新的發(fā)展，因此擴(kuò)展后的學(xué)科稱為學(xué)科稱為計(jì)算學(xué)科計(jì)算學(xué)科。包括：計(jì)算機(jī)科學(xué)、計(jì)算機(jī)工

2、程、軟件工程、信息系統(tǒng)包括：計(jì)算機(jī)科學(xué)、計(jì)算機(jī)工程、軟件工程、信息系統(tǒng)關(guān)鍵問題：利用計(jì)算機(jī)進(jìn)行信息表示和處理的涉及：關(guān)鍵問題：利用計(jì)算機(jī)進(jìn)行信息表示和處理的涉及：信息的表示信息的表示 信息的處理信息的處理 而信息的表示和組織又直接關(guān)系到處理信息的程序的效率。而信息的表示和組織又直接關(guān)系到處理信息的程序的效率。隨著計(jì)算機(jī)的普及，信息量的增加，信息范圍的拓寬，使許多系隨著計(jì)算機(jī)的普及，信息量的增加，信息范圍的拓寬，使許多系統(tǒng)程序和應(yīng)用程序的規(guī)模很大，結(jié)構(gòu)又相當(dāng)復(fù)雜。因此，為了編統(tǒng)程序和應(yīng)用程序的規(guī)模很大，結(jié)構(gòu)又相當(dāng)復(fù)雜。因此，為了編寫出一個(gè)寫出一個(gè)“好好”的程序，必須分析待處理的對象的特征及各對象

3、的程序，必須分析待處理的對象的特征及各對象之間存在的關(guān)系，這就是數(shù)據(jù)結(jié)構(gòu)這門課所要研究的問題。之間存在的關(guān)系，這就是數(shù)據(jù)結(jié)構(gòu)這門課所要研究的問題。1.1什么是數(shù)據(jù)結(jié)構(gòu)什么是數(shù)據(jù)結(jié)構(gòu)眾所周知，計(jì)算機(jī)的程序是對信息進(jìn)行處理。在大眾所周知，計(jì)算機(jī)的程序是對信息進(jìn)行處理。在大多數(shù)情況下，這些信息并不是沒有組織的，信息（數(shù)多數(shù)情況下，這些信息并不是沒有組織的，信息（數(shù)據(jù)）之間往往具有重要的結(jié)構(gòu)關(guān)系，這就是數(shù)據(jù)結(jié)構(gòu)據(jù)）之間往往具有重要的結(jié)構(gòu)關(guān)系，這就是數(shù)據(jù)結(jié)構(gòu)的內(nèi)容。什么是數(shù)據(jù)結(jié)構(gòu)呢？的內(nèi)容。什么是數(shù)據(jù)結(jié)構(gòu)呢？例子：例子：例例1、電話號(hào)碼查詢系統(tǒng)、電話號(hào)碼查詢系統(tǒng)設(shè)有一個(gè)電話號(hào)碼薄，它記錄了設(shè)有一個(gè)電話號(hào)

4、碼薄，它記錄了N個(gè)人的名字和其個(gè)人的名字和其相應(yīng)的電話號(hào)碼，假定按如下形式安排：相應(yīng)的電話號(hào)碼，假定按如下形式安排：(a1，b1)(a2，b2)(an，bn)其中其中(ai，bi)(i=1，2n)分別表示某人的名字和對應(yīng)分別表示某人的名字和對應(yīng)的電話號(hào)碼。要求設(shè)計(jì)一個(gè)算法，當(dāng)給定任何一個(gè)人的電話號(hào)碼。要求設(shè)計(jì)一個(gè)算法，當(dāng)給定任何一個(gè)人的名字時(shí)，該算法能夠打印出此人的電話號(hào)碼，如果的名字時(shí)，該算法能夠打印出此人的電話號(hào)碼，如果該電話簿中根本就沒有這個(gè)人，則該算法也能夠報(bào)告該電話簿中根本就沒有這個(gè)人，則該算法也能夠報(bào)告沒有這個(gè)人的信息。沒有這個(gè)人的信息。數(shù)據(jù)結(jié)構(gòu)含義：數(shù)據(jù)結(jié)構(gòu)含義：就是研究數(shù)據(jù)的邏

5、輯結(jié)構(gòu)和物理結(jié)構(gòu)以及它們就是研究數(shù)據(jù)的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)以及它們之間相互關(guān)系，并對這種結(jié)構(gòu)定義相應(yīng)的運(yùn)算，而之間相互關(guān)系，并對這種結(jié)構(gòu)定義相應(yīng)的運(yùn)算，而且確保經(jīng)過這些運(yùn)算后所得到的新結(jié)構(gòu)仍然是原來且確保經(jīng)過這些運(yùn)算后所得到的新結(jié)構(gòu)仍然是原來的結(jié)構(gòu)類型。的結(jié)構(gòu)類型。所有能所有能被輸入被輸入到計(jì)算機(jī)中，且能被計(jì)算機(jī)到計(jì)算機(jī)中，且能被計(jì)算機(jī)處處理的符號(hào)理的符號(hào)的集合。的集合。數(shù)據(jù)數(shù)據(jù):是是計(jì)算機(jī)操作的對象計(jì)算機(jī)操作的對象的總稱。的總稱。是計(jì)算機(jī)處理的是計(jì)算機(jī)處理的信息的信息的某種特定的符號(hào)某種特定的符號(hào)表示表示形式形式。1.2有關(guān)概念和術(shù)語有關(guān)概念和術(shù)語是數(shù)據(jù)（集合）中的一個(gè)是數(shù)據(jù)（集合）中的一個(gè)“

6、個(gè)體個(gè)體”數(shù)據(jù)元素?cái)?shù)據(jù)元素:是數(shù)據(jù)結(jié)構(gòu)中討論的是數(shù)據(jù)結(jié)構(gòu)中討論的基本基本單位單位數(shù)據(jù)結(jié)構(gòu)主要指邏輯結(jié)構(gòu)和物理結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)主要指邏輯結(jié)構(gòu)和物理結(jié)構(gòu) 數(shù)據(jù)之間的相互關(guān)系稱為邏輯結(jié)構(gòu)。通常數(shù)據(jù)之間的相互關(guān)系稱為邏輯結(jié)構(gòu)。通常分為四類基本結(jié)構(gòu)：分為四類基本結(jié)構(gòu)：一、一、集合集合 結(jié)構(gòu)中的數(shù)據(jù)元素除了同屬于一結(jié)構(gòu)中的數(shù)據(jù)元素除了同屬于一種類型外，別無其它關(guān)系。種類型外，別無其它關(guān)系。二、二、線性結(jié)構(gòu)線性結(jié)構(gòu) 結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一對一的關(guān)系。對一的關(guān)系。三、三、樹型結(jié)構(gòu)樹型結(jié)構(gòu) 結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一對多的關(guān)系。對多的關(guān)系。四、四、圖狀結(jié)構(gòu)或網(wǎng)

7、狀結(jié)構(gòu)圖狀結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu) 結(jié)構(gòu)中的數(shù)據(jù)元素結(jié)構(gòu)中的數(shù)據(jù)元素之間存在多對多的關(guān)系。之間存在多對多的關(guān)系。一個(gè)數(shù)據(jù)元素可由若干個(gè)數(shù)據(jù)項(xiàng)組成。一個(gè)數(shù)據(jù)元素可由若干個(gè)數(shù)據(jù)項(xiàng)組成。數(shù)據(jù)項(xiàng)是數(shù)據(jù)的不可分割的最小單位。數(shù)據(jù)項(xiàng)是數(shù)據(jù)的不可分割的最小單位。數(shù)據(jù)對象數(shù)據(jù)對象(DataObject)：是性質(zhì)相同的數(shù)據(jù)是性質(zhì)相同的數(shù)據(jù)元素的集合。是數(shù)據(jù)的一個(gè)子集。元素的集合。是數(shù)據(jù)的一個(gè)子集。數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)(DataStructure)：是相互之間存在是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。數(shù)據(jù)在計(jì)算機(jī)中的表示稱為數(shù)據(jù)的數(shù)據(jù)在計(jì)算機(jī)中的表示稱為數(shù)據(jù)的物理物理結(jié)構(gòu)結(jié)構(gòu)，又

8、稱為，又稱為存儲(chǔ)結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)。數(shù)據(jù)對象可以是有限的，也可以是無限的。數(shù)據(jù)對象可以是有限的，也可以是無限的。數(shù)據(jù)結(jié)構(gòu)不同于數(shù)據(jù)類型，也不同于數(shù)據(jù)對數(shù)據(jù)結(jié)構(gòu)不同于數(shù)據(jù)類型，也不同于數(shù)據(jù)對象，它不僅要描述數(shù)據(jù)類型的數(shù)據(jù)對象，而且象，它不僅要描述數(shù)據(jù)類型的數(shù)據(jù)對象，而且要描述數(shù)據(jù)對象各元素之間的相互關(guān)系。要描述數(shù)據(jù)對象各元素之間的相互關(guān)系。數(shù)據(jù)類型數(shù)據(jù)類型：在一種程序設(shè)計(jì)語言中，變量所具有的數(shù)：在一種程序設(shè)計(jì)語言中，變量所具有的數(shù)據(jù)種類。據(jù)種類。例例1、在在FORTRAN語言中，變量的數(shù)據(jù)類型有整型、語言中，變量的數(shù)據(jù)類型有整型、實(shí)型、和復(fù)數(shù)型實(shí)型、和復(fù)數(shù)型例例2、在、在C+語言中語言中數(shù)據(jù)類型：基本

9、類型和構(gòu)造類型數(shù)據(jù)類型：基本類型和構(gòu)造類型基本類型：整型、浮點(diǎn)型、字符型基本類型：整型、浮點(diǎn)型、字符型構(gòu)造類型：數(shù)組、結(jié)構(gòu)、聯(lián)合、指針、枚舉型、自定構(gòu)造類型：數(shù)組、結(jié)構(gòu)、聯(lián)合、指針、枚舉型、自定義義數(shù)據(jù)對象數(shù)據(jù)對象：某種數(shù)據(jù)類型元素的集合。：某種數(shù)據(jù)類型元素的集合。例例3、整數(shù)的數(shù)據(jù)對象是、整數(shù)的數(shù)據(jù)對象是-3，-2，-1，0，1，2，3，英文字符類型的數(shù)據(jù)對象是英文字符類型的數(shù)據(jù)對象是A，B，C，D，E，F(xiàn)，1.3算法和算法分析算法和算法分析1.3.1算法：算法：是對特定問題求解步驟的一種描述，是指令的有限序列，其中是對特定問題求解步驟的一種描述，是指令的有限序列，其中每一條指令表示一個(gè)或多

10、個(gè)操作。每一條指令表示一個(gè)或多個(gè)操作。算法具有以下五個(gè)特性：算法具有以下五個(gè)特性：（1）有窮性有窮性一個(gè)算法必須總是在執(zhí)行有窮步之后結(jié)束，且每一個(gè)算法必須總是在執(zhí)行有窮步之后結(jié)束，且每一步都在有窮時(shí)間內(nèi)完成。一步都在有窮時(shí)間內(nèi)完成。（2）確定性確定性算法中每一條指令必須有確切的含義。不存在二義算法中每一條指令必須有確切的含義。不存在二義性。性。（3）可行性可行性一個(gè)算法是可行的。即算法描述的操作都是可以通一個(gè)算法是可行的。即算法描述的操作都是可以通過已經(jīng)實(shí)現(xiàn)的基本運(yùn)算執(zhí)行有限次來實(shí)現(xiàn)的。過已經(jīng)實(shí)現(xiàn)的基本運(yùn)算執(zhí)行有限次來實(shí)現(xiàn)的。（4）輸入輸入一個(gè)算法有零個(gè)或多個(gè)輸入，這些輸入取自于某個(gè)特一個(gè)算法

11、有零個(gè)或多個(gè)輸入，這些輸入取自于某個(gè)特定的對象集合。定的對象集合。（5）輸出輸出一個(gè)算法有一個(gè)或多個(gè)輸出，這些輸出是同輸入有著一個(gè)算法有一個(gè)或多個(gè)輸出，這些輸出是同輸入有著某些特定關(guān)系的量。某些特定關(guān)系的量。1.3.2算法設(shè)計(jì)的要求算法設(shè)計(jì)的要求設(shè)計(jì)算法時(shí)，通常應(yīng)考慮達(dá)到以下目標(biāo)：設(shè)計(jì)算法時(shí)，通常應(yīng)考慮達(dá)到以下目標(biāo)：1、正確性、正確性2、可讀性、可讀性3、健壯性、健壯性4、高效率與低存儲(chǔ)量需求、高效率與低存儲(chǔ)量需求1正確性正確性首先，首先，算法應(yīng)當(dāng)滿足以特定的算法應(yīng)當(dāng)滿足以特定的“規(guī)格說規(guī)格說明明”方式給出的需求。方式給出的需求。其次，其次，對算法是否對算法是否“正確正確”的理解可以的理解可以

12、有以下四個(gè)層次：有以下四個(gè)層次：a程序中不含語法錯(cuò)誤；程序中不含語法錯(cuò)誤；b程序?qū)τ趲捉M輸入數(shù)據(jù)能夠得出程序?qū)τ趲捉M輸入數(shù)據(jù)能夠得出滿足要求的結(jié)果；滿足要求的結(jié)果；c程序?qū)τ诰倪x擇的、典型、苛刻且程序?qū)τ诰倪x擇的、典型、苛刻且?guī)в械箅y性的幾組輸入數(shù)據(jù)能夠得出滿足帶有刁難性的幾組輸入數(shù)據(jù)能夠得出滿足要求的結(jié)果；要求的結(jié)果；通常以通常以第第c層層意義的正確性作為衡意義的正確性作為衡量一個(gè)算法是否合格的標(biāo)準(zhǔn)。量一個(gè)算法是否合格的標(biāo)準(zhǔn)。d程序?qū)τ谝磺泻戏ǖ妮斎霐?shù)據(jù)都能得出程序?qū)τ谝磺泻戏ǖ妮斎霐?shù)據(jù)都能得出滿足要求的結(jié)果；滿足要求的結(jié)果；2.2.可讀性可讀性 算法主要是為了人的閱讀與交流，算法主要是

13、為了人的閱讀與交流，其次才是為計(jì)算機(jī)執(zhí)行，因此算法應(yīng)該其次才是為計(jì)算機(jī)執(zhí)行，因此算法應(yīng)該易易于人的理解于人的理解；另一方面，晦澀難讀的程序；另一方面，晦澀難讀的程序易于隱藏較多錯(cuò)誤而難以調(diào)試。易于隱藏較多錯(cuò)誤而難以調(diào)試。3 3健壯性健壯性 當(dāng)當(dāng)輸入的數(shù)據(jù)非法輸入的數(shù)據(jù)非法時(shí)，算法應(yīng)當(dāng)恰當(dāng)時(shí)，算法應(yīng)當(dāng)恰當(dāng)?shù)刈鞒龇从郴虻刈鞒龇从郴蜻M(jìn)行相應(yīng)處理進(jìn)行相應(yīng)處理，而不是產(chǎn)，而不是產(chǎn)生莫名奇妙的輸出結(jié)果。并且，處理出生莫名奇妙的輸出結(jié)果。并且，處理出錯(cuò)的方法不應(yīng)是中斷程序的執(zhí)行，而應(yīng)錯(cuò)的方法不應(yīng)是中斷程序的執(zhí)行，而應(yīng)是返回一個(gè)表示錯(cuò)誤或錯(cuò)誤性質(zhì)的值，是返回一個(gè)表示錯(cuò)誤或錯(cuò)誤性質(zhì)的值，以便在更高的抽象層次上進(jìn)

14、行處理。以便在更高的抽象層次上進(jìn)行處理。4 4高效率與低存儲(chǔ)量需求高效率與低存儲(chǔ)量需求通常，效率指的是通常，效率指的是算法執(zhí)行時(shí)間算法執(zhí)行時(shí)間；存儲(chǔ)量指的是算法執(zhí)行過程中存儲(chǔ)量指的是算法執(zhí)行過程中所需的所需的最大存儲(chǔ)空間最大存儲(chǔ)空間，兩者都與問題的規(guī)模，兩者都與問題的規(guī)模有關(guān)。有關(guān)。1.3.3算法效率的度量算法效率的度量通常有兩種衡量算法效率的方法通常有兩種衡量算法效率的方法:事后統(tǒng)計(jì)法事后統(tǒng)計(jì)法事前分析估算法事前分析估算法缺點(diǎn)：缺點(diǎn)：1必須執(zhí)行程序必須執(zhí)行程序2其它因素掩蓋算法本質(zhì)其它因素掩蓋算法本質(zhì)和算法執(zhí)行時(shí)間相關(guān)的因素：和算法執(zhí)行時(shí)間相關(guān)的因素：1算法選用的策略算法選用的策略2問題的規(guī)

15、模問題的規(guī)模3編寫程序的語言編寫程序的語言4編譯程序產(chǎn)生的機(jī)器代碼的質(zhì)量編譯程序產(chǎn)生的機(jī)器代碼的質(zhì)量5計(jì)算機(jī)執(zhí)行指令的速度計(jì)算機(jī)執(zhí)行指令的速度 一個(gè)特定一個(gè)特定算法的算法的“運(yùn)行工作量運(yùn)行工作量”的大小，只依賴于的大小，只依賴于問題的規(guī)模問題的規(guī)模（通常用整數(shù)量（通常用整數(shù)量n表示），或者說，表示），或者說，它是問題規(guī)模的函數(shù)。它是問題規(guī)模的函數(shù)。假如，隨著問題規(guī)模假如，隨著問題規(guī)模 n的增長，的增長，算法執(zhí)行時(shí)間的增長率和算法執(zhí)行時(shí)間的增長率和 f(n)的增長的增長率相同，則可記作：率相同，則可記作：T(n)=O(f(n)稱稱T(n)為算法的為算法的(漸近漸近)時(shí)間復(fù)雜度。時(shí)間復(fù)雜度。如何估

16、算如何估算 算法的時(shí)間復(fù)雜度？算法的時(shí)間復(fù)雜度？算法算法=控制結(jié)構(gòu)控制結(jié)構(gòu)+原操作原操作（固有數(shù)據(jù)類型的操作）（固有數(shù)據(jù)類型的操作）算法的執(zhí)行時(shí)間算法的執(zhí)行時(shí)間=原操作原操作(i)的執(zhí)行次數(shù)的執(zhí)行次數(shù)原操作原操作(i)的執(zhí)行時(shí)間的執(zhí)行時(shí)間算法的執(zhí)行時(shí)間算法的執(zhí)行時(shí)間 與與 原操作執(zhí)行次數(shù)之和原操作執(zhí)行次數(shù)之和 成正比成正比 從算法中選取一種對于所研究的從算法中選取一種對于所研究的問題來說是問題來說是 基本操作基本操作 的原操作，以的原操作，以該基本操作該基本操作 在算法中重復(fù)執(zhí)行的次在算法中重復(fù)執(zhí)行的次數(shù)數(shù) 作為算法運(yùn)行時(shí)間的衡量準(zhǔn)則。作為算法運(yùn)行時(shí)間的衡量準(zhǔn)則。voidmult(int a,

17、int b,int c)for(i=1;i=n;+i)for(j=1;j=n;+j)cij=0;for(k=1;k=n;+k)cij+=aik*bkj;/for/mult基本操作:乘法乘法操作時(shí)間復(fù)雜度:O(n3)例例1例例+x;s=0;將將x自增看成是基本操作，則語句頻度為自增看成是基本操作，則語句頻度為1，即時(shí)間復(fù)雜度為，即時(shí)間復(fù)雜度為(1)如果將如果將s=0也看成是基本操作，則語句頻度為也看成是基本操作，則語句頻度為1，其時(shí)間復(fù)雜度，其時(shí)間復(fù)雜度仍為仍為(1)，即常量階。，即常量階。例例for(i=1;i=n;+i)+x;s+=x;語句頻度為：語句頻度為：n其時(shí)間復(fù)雜度為：其時(shí)間復(fù)雜度為

18、：O(n)即時(shí)間復(fù)雜度為線性階。即時(shí)間復(fù)雜度為線性階。i=0:賦值次賦值次i=1:賦值賦值2次次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;語句頻度為：語句頻度為：n2其時(shí)間復(fù)雜度為：其時(shí)間復(fù)雜度為：O(n2)即時(shí)間復(fù)雜度為平方階。即時(shí)間復(fù)雜度為平方階。例例for(i=0;i=n-1;+i)for(j=0;j1=n0，n為正整數(shù)為正整數(shù)時(shí)，時(shí)，xn+1xn，所以：所以：|an|*|xn|+|an-1|*|xn-1|+|a1|*|x1|+|a0|*|x0|an

19、|*|xn|+|an-1|*|xn|+|a1|*|xn|+|a0|*|xn|=(|an|+|an-1|+|a1|+|a0|)|xn|=c|xn|其中：其中：n0=1,c=|an|+|an-1|+|a1|+|a0|,g(n)=xn 一個(gè)算法時(shí)間為一個(gè)算法時(shí)間為O(1)的算法，它的基本運(yùn)算執(zhí)行的的算法，它的基本運(yùn)算執(zhí)行的次數(shù)是固定的。因此，總的時(shí)間由一個(gè)常數(shù)（即零次次數(shù)是固定的。因此，總的時(shí)間由一個(gè)常數(shù)（即零次多項(xiàng)式）來限界。而一個(gè)時(shí)間為多項(xiàng)式）來限界。而一個(gè)時(shí)間為O(n2)的算法則由一個(gè)的算法則由一個(gè)二次多項(xiàng)式來限界。二次多項(xiàng)式來限界。以下六種計(jì)算算法時(shí)間的多項(xiàng)式是最常用的。其以下六種計(jì)算算法時(shí)

20、間的多項(xiàng)式是最常用的。其關(guān)系為：關(guān)系為：O(1)O(logn)O(n)O(nlogn)O(n2)O(n3)指數(shù)時(shí)間的關(guān)系為：指數(shù)時(shí)間的關(guān)系為：O(2n)O(n!)0;i-)for(j=0;jaj+1)ajaj+1;時(shí)間：時(shí)間：最好情況最好情況：0次次最壞情況：每次都換最壞情況：每次都換，(n2)空間：一個(gè)數(shù)據(jù)交換的輔助空間空間：一個(gè)數(shù)據(jù)交換的輔助空間-算法原地工作。算法原地工作。例例7：遞歸程序的分析遞歸程序的分析intfact(intn)if(n=1)return1;elsereturnn*fact(n-1);f(n)=c+f(n-1)=c+(c+f(n-2)=2c+f(n-2)=(n-1)

21、c+f(1)=(n-1)c+c0課時(shí)安排與考核課時(shí)安排與考核學(xué)分學(xué)分3:授課授課2.5(40課時(shí)課時(shí))上機(jī)上機(jī)0.5(8+8課時(shí)課時(shí))考核考核:平時(shí)成績平時(shí)成績20%作業(yè)作業(yè)(課后與課堂課后與課堂)、實(shí)驗(yàn)實(shí)驗(yàn)課程考試課程考試80%作業(yè)作業(yè)：.計(jì)算時(shí)間復(fù)雜度計(jì)算時(shí)間復(fù)雜度sum=1;for(i=0;sum0)記作記作：(a1，a2，an)這里的數(shù)據(jù)元素這里的數(shù)據(jù)元素ai(1in)只是一個(gè)抽象的符號(hào)只是一個(gè)抽象的符號(hào)，其其具體含義在不同的情況下可以不同具體含義在不同的情況下可以不同。例例1、26個(gè)英文字母組成的字母表個(gè)英文字母組成的字母表（A，B，C、Z）例例2、某校從某校從1978年到年到198

22、3年各種型號(hào)的計(jì)算機(jī)擁有年各種型號(hào)的計(jì)算機(jī)擁有量的變化情況量的變化情況。（6，17，28，50，92，188）.神經(jīng)衰弱神經(jīng)衰弱17男男790634張立立張立立健康健康21男男790633劉建平劉建平一般一般20女女790632陳陳紅紅健康健康18男男790631王小林王小林健康情況健康情況年齡年齡性性別別學(xué)學(xué)號(hào)號(hào)姓姓名名例例3、學(xué)生健康情況登記表如下：、學(xué)生健康情況登記表如下：從以上例子可看出線性表的邏輯特征是：從以上例子可看出線性表的邏輯特征是：(1)對非空的線性表，有且僅有一個(gè)開始結(jié)點(diǎn)對非空的線性表，有且僅有一個(gè)開始結(jié)點(diǎn)a1，它沒有直接前它沒有直接前驅(qū)，而僅有一個(gè)直接后繼驅(qū)，而僅有一個(gè)直

23、接后繼a2；(2)有且僅有一個(gè)終端結(jié)點(diǎn)有且僅有一個(gè)終端結(jié)點(diǎn)an，它沒有直接后繼，而僅有一個(gè)直接它沒有直接后繼，而僅有一個(gè)直接前驅(qū)前驅(qū)an-1；(3)其余的內(nèi)部結(jié)點(diǎn)其余的內(nèi)部結(jié)點(diǎn)ai(2in-1)都有且僅有一個(gè)直接前驅(qū)都有且僅有一個(gè)直接前驅(qū)ai-1和一個(gè)和一個(gè)直接后繼直接后繼ai+1。線性表是一種典型的線性結(jié)構(gòu)。線性表是一種典型的線性結(jié)構(gòu)。數(shù)據(jù)的運(yùn)算是定義在邏輯結(jié)構(gòu)上的，而運(yùn)算的具體實(shí)現(xiàn)則是在數(shù)據(jù)的運(yùn)算是定義在邏輯結(jié)構(gòu)上的，而運(yùn)算的具體實(shí)現(xiàn)則是在存儲(chǔ)結(jié)構(gòu)上進(jìn)行的。存儲(chǔ)結(jié)構(gòu)上進(jìn)行的。2.2線性表的順序存儲(chǔ)結(jié)構(gòu)線性表的順序存儲(chǔ)結(jié)構(gòu)2.2.1線性表線性表把線性表的結(jié)點(diǎn)按邏輯順序依次存放在一組地址連續(xù)的

24、存把線性表的結(jié)點(diǎn)按邏輯順序依次存放在一組地址連續(xù)的存儲(chǔ)單元里。用這種方法存儲(chǔ)的線性表簡稱順序表。儲(chǔ)單元里。用這種方法存儲(chǔ)的線性表簡稱順序表。假設(shè)線性表的每個(gè)元素需占用假設(shè)線性表的每個(gè)元素需占用m個(gè)存儲(chǔ)單元，并以所占的個(gè)存儲(chǔ)單元，并以所占的第一個(gè)單元的存儲(chǔ)地址作為數(shù)據(jù)元素的存儲(chǔ)位置作為參考點(diǎn)。第一個(gè)單元的存儲(chǔ)地址作為數(shù)據(jù)元素的存儲(chǔ)位置作為參考點(diǎn)。則線性表中第則線性表中第i+1個(gè)數(shù)據(jù)元素的存儲(chǔ)位置個(gè)數(shù)據(jù)元素的存儲(chǔ)位置Loc(ai+1)和第和第i個(gè)數(shù)據(jù)個(gè)數(shù)據(jù)元素的存儲(chǔ)位置元素的存儲(chǔ)位置Loc(ai)之間滿足下列關(guān)系：之間滿足下列關(guān)系：Loc(ai+1)=Loc(ai)+maiai+1Loc(ai+1

25、)m個(gè)字節(jié)個(gè)字節(jié)Loc(ai)線性表的第線性表的第i個(gè)數(shù)據(jù)元素個(gè)數(shù)據(jù)元素ai的存儲(chǔ)位置為的存儲(chǔ)位置為:a1a2aianLoc(a1)i-1個(gè)元素個(gè)元素Loc(ai)=(i-1)*m+Loc(a1)=Loc(a1)-m+i*m由于由于Loc(a1)和和m都是已知的都是已知的所以：所以：V0=Loc(a1)-mLoc(ai)=V0+i*m由于在高級(jí)語言中的一維數(shù)組也是采用順序存儲(chǔ)表示，由于在高級(jí)語言中的一維數(shù)組也是采用順序存儲(chǔ)表示，故可以用數(shù)組類型來描述順序表。又因?yàn)槌擞脭?shù)組來故可以用數(shù)組類型來描述順序表。又因?yàn)槌擞脭?shù)組來存儲(chǔ)線性表的元素之外，順序表還應(yīng)該用一個(gè)變量來表存儲(chǔ)線性表的元素之外，順

26、序表還應(yīng)該用一個(gè)變量來表示線性表的長度屬性，利用示線性表的長度屬性，利用C+語言的結(jié)構(gòu)類型來定義語言的結(jié)構(gòu)類型來定義順序表類型順序表類型。#defineListSize100/表容量表容量typedefintDataType;/以以int為例為例structSqlistDataTypedataListSize;intlenth;/當(dāng)前表中元素?cái)?shù)當(dāng)前表中元素?cái)?shù);lenth.SqlistdataListSize個(gè)個(gè)2.2.2順序表上實(shí)現(xiàn)的基本操作順序表上實(shí)現(xiàn)的基本操作在順序表存儲(chǔ)結(jié)構(gòu)中，很容易實(shí)現(xiàn)線性表的一些操作，如線性在順序表存儲(chǔ)結(jié)構(gòu)中，很容易實(shí)現(xiàn)線性表的一些操作，如線性表的構(gòu)造、第表的構(gòu)造、第

27、i個(gè)元素的訪問。個(gè)元素的訪問。注意：注意：C/C+語言中的數(shù)組下標(biāo)從語言中的數(shù)組下標(biāo)從“0”開始，因此，若開始，因此，若L是是Sqlist類型的順序表，則表中第類型的順序表，則表中第i個(gè)元素位置是個(gè)元素位置是L.datai-1。線性表的插入和刪除兩種運(yùn)算。線性表的插入和刪除兩種運(yùn)算。1、插入、插入線性表的插入運(yùn)算是指在表的線性表的插入運(yùn)算是指在表的i(1in+1)個(gè)位置上，插入一個(gè)個(gè)位置上，插入一個(gè)新結(jié)點(diǎn)新結(jié)點(diǎn)x，使長度為使長度為n的線性表的線性表(a1，ai-1，ai，an)變成長度為變成長度為n+1的線性表的線性表(a1，ai-1，x，ai，an)注：注：可用可用memmove(L.dat

28、a+i,L.dada+i-1,(L.lenth-i+1)*sizeof(DataType)代替代替for循環(huán)循環(huán)（包含文件包含文件：string.h,一般格式一般格式格式格式：memmove(目的地址，源地址，移動(dòng)字節(jié)數(shù)目的地址，源地址，移動(dòng)字節(jié)數(shù))voidInsertList(L,x,i)/在線性表在線性表L中第中第i個(gè)個(gè)位置插入元素位置插入元素xif(iL.length+1)cout“插入序號(hào)錯(cuò)誤插入序號(hào)錯(cuò)誤”=ListSize)溢出處理溢出處理；elsefor(j=L.length-1;j=i-1;j-)/第第i個(gè)元素（下標(biāo)為個(gè)元素（下標(biāo)為i-1)開始開始L.dataj+1=L.data

29、j;/順序后移順序后移L.datai-1=x;L.length+;memcpy(目的地址目的地址,源地址，字節(jié)數(shù)源地址，字節(jié)數(shù)）memset(目的地址目的地址,字符，字節(jié)數(shù)字符，字節(jié)數(shù)）inta5050,b5050;a a清清0 0for(i=0;i50;i+)for(j=0;j50;j+)aij=0;拷貝拷貝：for(i=0;i50;i+)for(j=0;j-最好情況；最好情況；當(dāng)當(dāng)=1時(shí)，需移動(dòng)表中所有結(jié)點(diǎn)時(shí)，需移動(dòng)表中所有結(jié)點(diǎn)-最壞情況最壞情況，a1，ai-1，ai，anx移動(dòng)數(shù)據(jù)：移動(dòng)數(shù)據(jù)：n-i+1算法的平均移動(dòng)算法的平均移動(dòng) 由于插入可能在表中任何位置上進(jìn)行，在長度為由于插入可能在

30、表中任何位置上進(jìn)行，在長度為n的線性表中第的線性表中第i個(gè)位置上插入一個(gè)結(jié)點(diǎn)，令個(gè)位置上插入一個(gè)結(jié)點(diǎn)，令Eis(n)表示表示移動(dòng)結(jié)點(diǎn)的期望值（即移動(dòng)的平均次數(shù)），則在第移動(dòng)結(jié)點(diǎn)的期望值（即移動(dòng)的平均次數(shù)），則在第i個(gè)個(gè)位置上插入一個(gè)結(jié)點(diǎn)的移動(dòng)次數(shù)為位置上插入一個(gè)結(jié)點(diǎn)的移動(dòng)次數(shù)為n-i+1。Pi代表在代表在第第i個(gè)位置插入概率，則個(gè)位置插入概率，則 Eis(n)=p1n+p2(n-1)+.+pn 1+pn+1 0 若表中任何位置若表中任何位置(1in+1)上插入結(jié)點(diǎn)的概率是上插入結(jié)點(diǎn)的概率是均等的，則均等的，則 p1=p2=p3=pn+1=1/(n+1)因此，在等概率插入的情況下：因此，在等概率

31、插入的情況下：Eis(n)=1/(n+1)n+(n-1)+1+0=n/2a1，ai-1，ai，an可能的插入點(diǎn)有可能的插入點(diǎn)有n+1處處結(jié)論：在順序表上做插入運(yùn)算，平均要結(jié)論：在順序表上做插入運(yùn)算，平均要移動(dòng)表上一半結(jié)移動(dòng)表上一半結(jié)點(diǎn)點(diǎn)。當(dāng)表長。當(dāng)表長n較大時(shí)，算法的效率相當(dāng)?shù)?。雖然較大時(shí)，算法的效率相當(dāng)?shù)?。雖然Eis(n)中中n的系數(shù)較小，但就數(shù)量級(jí)而言，它仍然是線性階的。的系數(shù)較小，但就數(shù)量級(jí)而言，它仍然是線性階的。因此算法的平均時(shí)間復(fù)雜度為因此算法的平均時(shí)間復(fù)雜度為O(n)。2 2、刪除刪除 線性表的刪除運(yùn)算是指將表的第線性表的刪除運(yùn)算是指將表的第i(1in)結(jié)點(diǎn)刪除，結(jié)點(diǎn)刪除，使長度為

32、使長度為n的線性表：的線性表：(a1，ai-1，ai，ai+1，an)變成長度為變成長度為n-1的線性表的線性表 (a1，ai-1，ai+1，an)void deleteList(L,i)/表L中刪除第i個(gè)元素 if(iL.length)cout“刪除序號(hào)錯(cuò)”endl;return ERROR;for(j=i;jch;while(ch!=$)p=newLNode;pdata=ch;pnext=h;h=p;cinch;LNode*CreateList()charch;LNode*h,*p;h=NULL;cinch;while(ch!=$)p=newLNode;pdata=ch;pnext=h;h

33、=p;cinch;returnh;#includestructLNodechardata;LNode*next;LNode*CreateList()charch;LNode*h,*p;h=NULL;cinch;while(ch!=$)p=newLNode;pdata=ch;pnext=h;h=p;cinch;returnh;voidCreateList1(LNode*&h)charch;LNode*p;h=NULL;cinch;while(ch!=$)p=newLNode;pdata=ch;pnext=h;h=p;cinch;voidprint(LNode*h)LNode*p=h;while(p!=NULL)coutdatanext;coutch;while(ch!=$)p=newLNode;pdata=ch;if(head=NULL)head=p;elser-next=p;r=p;cin