數(shù)據(jù)結(jié)構(gòu)與算法

1、李賽紅 2011-03 全國計(jì)算機(jī)等級考試全國計(jì)算機(jī)等級考試二級公共基礎(chǔ)知識（一）河海大學(xué)文天學(xué)院教育培訓(xùn)中心河海大學(xué)文天學(xué)院教育培訓(xùn)中心1.數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法1.2 1.2 數(shù)據(jù)結(jié)構(gòu)的數(shù)據(jù)結(jié)構(gòu)的基本概念基本概念 1.3 1.3 線性表的順序存儲線性表的順序存儲1.4 1.4 棧和隊(duì)列棧和隊(duì)列 1.1 1.1 算法基本概念及算法評價算法基本概念及算法評價 第一章第一章 數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法1.6 1.6 樹與二叉樹樹與二叉樹 1.7 1.7 查找與排序查找與排序 1.5 1.5 線性表的鏈?zhǔn)酱鎯€性表的鏈?zhǔn)酱鎯Φ谝徽碌谝徽?數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法1.1 1.1 算法基本

2、概念及算法評價算法基本概念及算法評價 1.1.1 1.1.1 算法算法 考點(diǎn)考點(diǎn)1 1 算法的定義算法的定義 算法是用來解決某個特定類型問題的有限運(yùn)算序列。簡算法是用來解決某個特定類型問題的有限運(yùn)算序列。簡單的說：單的說：算法就是解決問題的方法算法就是解決問題的方法. . eg. eg.程序是用計(jì)算機(jī)語言表達(dá)的算法程序是用計(jì)算機(jī)語言表達(dá)的算法; ; 流程圖是圖形化的算法流程圖是圖形化的算法 第一章第一章 數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法算法特征：算法特征： （1 1）有窮性：一個算法（對任何合法的輸入）在執(zhí)行有）有窮性：一個算法（對任何合法的輸入）在執(zhí)行有窮窮步后能夠結(jié)束步后能夠結(jié)束，并且在有限的

3、時間內(nèi)完成。，并且在有限的時間內(nèi)完成。 （2 2）確定性：算法中的每一步都有）確定性：算法中的每一步都有確切確切的含義。的含義。 （3 3）可行性：算法中的操作能夠用已經(jīng)實(shí)現(xiàn)的基本運(yùn)算）可行性：算法中的操作能夠用已經(jīng)實(shí)現(xiàn)的基本運(yùn)算執(zhí)行有限次來實(shí)現(xiàn)。執(zhí)行有限次來實(shí)現(xiàn)。 （4 4）輸入：一個算法有）輸入：一個算法有零個零個或者多個輸入或者多個輸入，零個輸入就，零個輸入就是算法本身缺定了初始條件。是算法本身缺定了初始條件。 （5 5）輸出：一個算法有）輸出：一個算法有一個一個或者多個輸出或者多個輸出，以反映出數(shù)，以反映出數(shù)據(jù)加工的結(jié)果。據(jù)加工的結(jié)果。 （擁有足夠的情報(bào)）（擁有足夠的情報(bào)） 第一章第一

4、章 數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法例例1. 1. 問題處理方案的正確而完整的描述稱為問題處理方案的正確而完整的描述稱為_。20052005年年4 4月月 填空第填空第5 5題題 例例2. 2. 以下敘述中正確的是以下敘述中正確的是 (A)(A)用用C C語言實(shí)現(xiàn)的算法必須要有輸入和輸出操作語言實(shí)現(xiàn)的算法必須要有輸入和輸出操作 (B)(B)用用C C語言實(shí)現(xiàn)的算法可以沒有輸出但必須要有輸入語言實(shí)現(xiàn)的算法可以沒有輸出但必須要有輸入 (C)(C)用用C C程序?qū)崿F(xiàn)的算法可以沒有輸入但必須要有輸出程序?qū)崿F(xiàn)的算法可以沒有輸入但必須要有輸出 (D)(D)用用C C程序?qū)崿F(xiàn)的算法可以既沒有輸入也沒有輸出程序?qū)?/p>

5、現(xiàn)的算法可以既沒有輸入也沒有輸出 20052005年年9 9月月 選擇題第選擇題第1313題題 例例3. 3. 算法具有五個特性算法具有五個特性, ,以下選項(xiàng)中不屬于算法特性的是以下選項(xiàng)中不屬于算法特性的是 (A)(A)有窮性有窮性 (B)(B)簡潔性簡潔性 (C)(C)可行性可行性 (D)(D)確定性確定性 2005年年4月月 選擇題第選擇題第11題題第一章第一章 數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法算法基本要素對數(shù)據(jù)的運(yùn)算和操作算術(shù)運(yùn)算邏輯運(yùn)算關(guān)系運(yùn)算輸入輸入運(yùn)算算法的控制結(jié)構(gòu)順序結(jié)構(gòu)選擇結(jié)構(gòu)循環(huán)結(jié)構(gòu)第一章第一章 數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法3 3 算法設(shè)計(jì)的基本方法算法設(shè)計(jì)的基本方法(1)(1)

6、列舉法列舉法- 根據(jù)提出的問題列舉所有可能的情況，并用問題中給定的條件檢根據(jù)提出的問題列舉所有可能的情況，并用問題中給定的條件檢驗(yàn)?zāi)男┦切枰亩男┦遣恍枰?；?yàn)?zāi)男┦切枰亩男┦遣恍枰模?2)(2)歸納法歸納法- 通過列舉足夠多的特殊情況發(fā)現(xiàn)其中一些規(guī)律，經(jīng)過分析最終找通過列舉足夠多的特殊情況發(fā)現(xiàn)其中一些規(guī)律，經(jīng)過分析最終找出一般的關(guān)系；出一般的關(guān)系；(3)(3)遞推法遞推法- 從已知的初始條件出發(fā)，逐次地推出所要求的各中間結(jié)果和最后從已知的初始條件出發(fā)，逐次地推出所要求的各中間結(jié)果和最后結(jié)果；結(jié)果；(4)(4)遞歸法遞歸法 - 首先將問題逐層分解最后歸結(jié)為一些最簡單的問題，解決這些首先

7、將問題逐層分解最后歸結(jié)為一些最簡單的問題，解決這些最簡單問題后再沿著原來分解的逆過程逐步進(jìn)行綜合。最簡單問題后再沿著原來分解的逆過程逐步進(jìn)行綜合。 (5)(5)減半遞推技術(shù)減半遞推技術(shù)- 工程上常用的分治法，即將問題的規(guī)模減半來解，最工程上常用的分治法，即將問題的規(guī)模減半來解，最后重復(fù)后重復(fù)“減半減半”的過程；的過程；(6)(6)回溯法回溯法- 在處理復(fù)雜數(shù)據(jù)結(jié)構(gòu)時，通過對問題的分析找出一在處理復(fù)雜數(shù)據(jù)結(jié)構(gòu)時，通過對問題的分析找出一 個解決問題個解決問題的線索，然后沿著次線索逐步試探，若失敗就逐步回退并換別的路線再進(jìn)行的線索，然后沿著次線索逐步試探，若失敗就逐步回退并換別的路線再進(jìn)行試探；試探

8、；第一章第一章 數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法考點(diǎn)考點(diǎn)2 2 算法的復(fù)雜度算法的復(fù)雜度 1.1.算法設(shè)計(jì)的要求：（算法設(shè)計(jì)的要求：（一個好的算法要達(dá)到的目標(biāo)一個好的算法要達(dá)到的目標(biāo)） (1)(1)正確性正確性 (2)(2)健壯性健壯性 (3)(3)可讀性可讀性 (4)(4)效率與低存儲量的要求效率與低存儲量的要求 2.2.算法效率的度量算法效率的度量 1)1)算法的時間復(fù)雜度算法的時間復(fù)雜度 算法的執(zhí)行時間算法的執(zhí)行時間= =每條語句執(zhí)行時間之和；每條語句執(zhí)行時間之和； 每條語句執(zhí)行時間每條語句執(zhí)行時間= =語句執(zhí)行（頻度）次數(shù)語句執(zhí)行（頻度）次數(shù) * * 語句執(zhí)行一次所需時間；語句執(zhí)行一次所需

9、時間； 獨(dú)立于軟硬件系統(tǒng)來分析算法的時間耗費(fèi)獨(dú)立于軟硬件系統(tǒng)來分析算法的時間耗費(fèi) 可以設(shè)每條語句執(zhí)行時間均為一個單位時間可以設(shè)每條語句執(zhí)行時間均為一個單位時間 算法的執(zhí)行時間算法的執(zhí)行時間= =所有語句頻度之和所有語句頻度之和 第一章第一章 數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法 算法所執(zhí)行的運(yùn)算次數(shù)算法所執(zhí)行的運(yùn)算次數(shù)是問題規(guī)模的函數(shù)是問題規(guī)模的函數(shù)（f(n)）時間復(fù)雜度 算法的空間復(fù)雜度是指算法的空間復(fù)雜度是指執(zhí)行這個算法所需要的執(zhí)行這個算法所需要的內(nèi)存空間內(nèi)存空間空間復(fù)雜度算算法法復(fù)復(fù)雜雜度度第一章第一章 數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法例例1. 1. 算法復(fù)雜度主要包括時間復(fù)雜度和算法復(fù)雜度主要包括

10、時間復(fù)雜度和 【1 1】 復(fù)復(fù)雜度。雜度。20052005年年9 9月月 填空第填空第2 2題題 例例2. 2. 對長度為對長度為N N的線性表的線性表( (一維數(shù)組一維數(shù)組) )進(jìn)行順序查找進(jìn)行順序查找, ,在最壞的情況下所需要的比較次數(shù)為在最壞的情況下所需要的比較次數(shù)為 20052005年年4 4月月 選擇第選擇第4 4題題 (A)log2n(A)log2n (B)n/2(B)n/2 (C)n(C)n (D)n+1(D)n+1 。 第二節(jié)第二節(jié) 數(shù)據(jù)結(jié)構(gòu)基本概念數(shù)據(jù)結(jié)構(gòu)基本概念1.2 1.2 數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)結(jié)構(gòu)的基本概念1.2.1 1.2.1 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 考點(diǎn)考點(diǎn)3 3 數(shù)據(jù)

11、結(jié)構(gòu)的定義數(shù)據(jù)結(jié)構(gòu)的定義 ： 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)(data structure)(data structure)是指相互之間存在一種或多是指相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合，即數(shù)據(jù)的組織形式。種特定關(guān)系的數(shù)據(jù)元素的集合，即數(shù)據(jù)的組織形式。 數(shù)據(jù)數(shù)據(jù)+ +關(guān)系關(guān)系數(shù)據(jù)結(jié)構(gòu)學(xué)科，主要研究和討論以下三個方面：數(shù)據(jù)結(jié)構(gòu)學(xué)科，主要研究和討論以下三個方面： (l)(l)數(shù)據(jù)集合中個數(shù)據(jù)元素之間所固有的邏輯關(guān)系，即數(shù)數(shù)據(jù)集合中個數(shù)據(jù)元素之間所固有的邏輯關(guān)系，即數(shù)據(jù)的據(jù)的邏輯結(jié)構(gòu)邏輯結(jié)構(gòu)； (2)(2)在對數(shù)據(jù)元素進(jìn)行處理時，各數(shù)據(jù)元素在計(jì)算機(jī)中的在對數(shù)據(jù)元素進(jìn)行處理時，各數(shù)據(jù)元素在計(jì)算機(jī)中的存儲

12、關(guān)系，即數(shù)據(jù)的存儲關(guān)系，即數(shù)據(jù)的存儲結(jié)構(gòu)存儲結(jié)構(gòu)； (3)(3)對各種數(shù)據(jù)結(jié)構(gòu)進(jìn)行的對各種數(shù)據(jù)結(jié)構(gòu)進(jìn)行的運(yùn)算運(yùn)算。 第二節(jié)第二節(jié) 數(shù)據(jù)結(jié)構(gòu)基本概念數(shù)據(jù)結(jié)構(gòu)基本概念基本概念：基本概念： （1 1）數(shù)據(jù)）數(shù)據(jù)(data)(data)：是對客觀事物的符號表示，在計(jì)算機(jī)：是對客觀事物的符號表示，在計(jì)算機(jī)科學(xué)中是指所有能輸入到計(jì)算機(jī)中并被計(jì)算機(jī)程序處理的符科學(xué)中是指所有能輸入到計(jì)算機(jī)中并被計(jì)算機(jī)程序處理的符號的號的總稱總稱。 （2 2）數(shù)據(jù)元素）數(shù)據(jù)元素(data element)(data element)：是數(shù)據(jù)的：是數(shù)據(jù)的基本單位基本單位，在，在計(jì)算機(jī)程序中通常作為一個整體進(jìn)行考慮和處理。計(jì)算機(jī)程

13、序中通常作為一個整體進(jìn)行考慮和處理。 （3 3）數(shù)據(jù)對象）數(shù)據(jù)對象(data object)(data object)：是性質(zhì)相同的數(shù)據(jù)元素：是性質(zhì)相同的數(shù)據(jù)元素的集合的集合。（數(shù)據(jù)元素是數(shù)據(jù)對象的一個實(shí)例）。（數(shù)據(jù)元素是數(shù)據(jù)對象的一個實(shí)例） 例如：所有書的書目信息為數(shù)據(jù)對象，每一條書目信息為數(shù)例如：所有書的書目信息為數(shù)據(jù)對象，每一條書目信息為數(shù)據(jù)元素。據(jù)元素。 第二節(jié)第二節(jié) 數(shù)據(jù)結(jié)構(gòu)基本概念數(shù)據(jù)結(jié)構(gòu)基本概念（4 4）數(shù)據(jù)的邏輯結(jié)構(gòu)）數(shù)據(jù)的邏輯結(jié)構(gòu) ： （5 5）數(shù)據(jù)的存儲結(jié)構(gòu)）數(shù)據(jù)的存儲結(jié)構(gòu) (物理結(jié)構(gòu))1 1）順序存儲方式（向量存儲）順序存儲方式（向量存儲）2 2）鏈?zhǔn)酱鎯Ψ绞剑╂準(zhǔn)酱鎯Ψ?/p>

14、式3 3）索引存儲方式）索引存儲方式第二節(jié)第二節(jié) 數(shù)據(jù)結(jié)構(gòu)基本概念數(shù)據(jù)結(jié)構(gòu)基本概念考點(diǎn)考點(diǎn)4 4 數(shù)據(jù)結(jié)構(gòu)的圖形表示數(shù)據(jù)結(jié)構(gòu)的圖形表示 例如：一年四季的圖形表示例如：一年四季的圖形表示：例如：反映家庭成員輩分關(guān)系的圖形表示例如：反映家庭成員輩分關(guān)系的圖形表示春春夏夏秋秋冬冬父親父親兒子兒子女兒女兒第二節(jié)第二節(jié) 數(shù)據(jù)結(jié)構(gòu)基本概念數(shù)據(jù)結(jié)構(gòu)基本概念1.2.3 1.2.3 線性結(jié)構(gòu)與非線性結(jié)構(gòu)線性結(jié)構(gòu)與非線性結(jié)構(gòu) 考點(diǎn)考點(diǎn)5 5 線性結(jié)構(gòu)與非線性結(jié)構(gòu)線性結(jié)構(gòu)與非線性結(jié)構(gòu) 如果在一個數(shù)據(jù)結(jié)構(gòu)中一個數(shù)據(jù)元素都沒有，則稱該數(shù)如果在一個數(shù)據(jù)結(jié)構(gòu)中一個數(shù)據(jù)元素都沒有，則稱該數(shù)據(jù)結(jié)構(gòu)為據(jù)結(jié)構(gòu)為空空的數(shù)據(jù)結(jié)構(gòu)。的數(shù)

15、據(jù)結(jié)構(gòu)。 根據(jù)數(shù)據(jù)結(jié)構(gòu)中各數(shù)據(jù)元素之間邏輯關(guān)系，一般將數(shù)據(jù)根據(jù)數(shù)據(jù)結(jié)構(gòu)中各數(shù)據(jù)元素之間邏輯關(guān)系，一般將數(shù)據(jù)結(jié)構(gòu)分為兩大類型：結(jié)構(gòu)分為兩大類型：線性結(jié)構(gòu)與非線性結(jié)構(gòu)線性結(jié)構(gòu)與非線性結(jié)構(gòu)。 非空數(shù)據(jù)結(jié)構(gòu)滿足：非空數(shù)據(jù)結(jié)構(gòu)滿足： (l)(l)有有且只有一個沒有前件且只有一個沒有前件的結(jié)點(diǎn)；的結(jié)點(diǎn)； (2)(2)每一個結(jié)點(diǎn)每一個結(jié)點(diǎn)最多有一個前件最多有一個前件（直接前驅(qū)），（直接前驅(qū)），也最多有也最多有一個后件（直接后繼）。一個后件（直接后繼）。則稱該數(shù)據(jù)結(jié)構(gòu)為則稱該數(shù)據(jù)結(jié)構(gòu)為線性結(jié)構(gòu)線性結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)邏輯結(jié)構(gòu)邏輯結(jié)構(gòu)線性結(jié)構(gòu)線性結(jié)構(gòu)線性表線性表?xiàng)ｊ?duì)列隊(duì)列非線性結(jié)構(gòu)非線性結(jié)構(gòu)樹樹二叉樹二叉樹

16、存儲結(jié)構(gòu)即存儲結(jié)構(gòu)即物理結(jié)構(gòu)物理結(jié)構(gòu)順序存儲結(jié)構(gòu)順序存儲結(jié)構(gòu)鏈表存儲結(jié)構(gòu)鏈表存儲結(jié)構(gòu)索引存儲方式索引存儲方式1.3 1.3 線性表的線性表的順序存儲順序存儲結(jié)構(gòu)及結(jié)構(gòu)及鏈?zhǔn)芥準(zhǔn)酱鎯Υ鎯?1.3.1 1.3.1 線性表的基本概念線性表的基本概念考點(diǎn)考點(diǎn)6 6 1. 1.線性線性表表( (邏輯邏輯) )的的定義定義 線性表是線性表是n(n0)n(n0)個元素構(gòu)成的有限序列個元素構(gòu)成的有限序列(a1(a1，a2a2，an)an)。 2.2.線性表的特性：線性表的特性： (1) (1) 當(dāng)當(dāng)11i innext=NULLB) p=NULL D) p=head 循環(huán)鏈表的主要優(yōu)點(diǎn)是 A) 不再需要頭指針了 B) 從表中任一結(jié)點(diǎn)出發(fā)都能訪問到整個鏈表從表中任一結(jié)點(diǎn)出發(fā)都能訪問到整個鏈表 C) 在進(jìn)行插入、刪除運(yùn)算時，能更好的保證鏈表不斷開 D) 已知某個