二級公共基礎(chǔ)知識完整版課件

1、1算法及數(shù)據(jù)結(jié)構(gòu)算法及數(shù)據(jù)結(jié)構(gòu)程序設(shè)計基礎(chǔ)程序設(shè)計基礎(chǔ)軟件軟件工程基礎(chǔ)工程基礎(chǔ)數(shù)據(jù)庫設(shè)計基礎(chǔ)數(shù)據(jù)庫設(shè)計基礎(chǔ)2345 6 7 8algorithm1 1、算法的基本概念、算法的基本概念( (漢諾塔的例子) ) 算法是對特定問題求解步驟的一種描述，它是指令的有限序列，其中每一條指令表示一個或多個操作。它是一組嚴(yán)謹(jǐn)?shù)囟x運(yùn)算順序的規(guī)則，并且每一個規(guī)則都是有效的，且是明確的，此順序?qū)⒃谟邢薜拇螖?shù)下終止。算法具有可行性可行性、確定性確定性、有窮性有窮性、輸入輸入和輸出輸出（擁有足夠的情報）等個重要特性。漢 諾 塔l 1-B1-Bl 2-C 2-Cl 1-C 1-Cl 3-B 3-Bl 1-A 1-Al

2、2-B 2-Bl 1-B 1-BABC123算法：算法：算法：算法：對特定問題求解步驟的一種描述。對特定問題求解步驟的一種描述。算法的描述方法：算法的描述方法：自然語言、專用工具或某種計算機(jī)語言。自然語言、專用工具或某種計算機(jī)語言。返回102 2、算法的基本要素、算法的基本要素(1) 對數(shù)據(jù)對象的運(yùn)算和操作： 算術(shù)運(yùn)算、邏輯運(yùn)算、關(guān)系運(yùn)算、數(shù)據(jù)傳輸 算法中各操作之間的執(zhí)行順序； 描述算法的工具通常有傳統(tǒng)流程圖、N-S結(jié)構(gòu)化流程 圖、算法描述語言等； 一個算法一般可以用順序、選擇、循環(huán)三種基本結(jié)構(gòu) 組合而成。(2) 算法的控制結(jié)構(gòu)： 113 3、算法設(shè)計的基本方法、算法設(shè)計的基本方法及例子 列舉

3、法（列出所有可能，再逐一檢驗，得到符合條件的結(jié)果）百錢買百雞 歸納法（通過特殊情況，經(jīng)過分析，最后找出一般關(guān)系） 遞推（從已知的初始條件出發(fā)，逐步推算，得到結(jié)果）猴子分食桃子 遞歸（將問題逐層分解，最后歸結(jié)為一些最簡單的問題）求年齡問題 減半遞推（重復(fù)將問題的規(guī)模減半，而問題性質(zhì)不變）二分法求方程實根 回溯法（以最優(yōu)方式向前試探，如果失敗，則后退再選）八皇后問題12(1)(1)時間復(fù)雜度時間復(fù)雜度v 依據(jù)算法編制的程序在計算機(jī)上運(yùn)行時所消耗的時間 來度量。通常有事后統(tǒng)計法和事前分析估算法。v 一個算法是由控制結(jié)構(gòu)（順序、分支和循環(huán)）和原操 作構(gòu)成的，算法時間取決于兩者的綜合效果。v 算法中基本

4、操作重復(fù)執(zhí)行次數(shù)n和算法執(zhí)行時間同步 增長，稱作算法的時間復(fù)雜度。13(2)(2)空間復(fù)雜度空間復(fù)雜度v 一般是指執(zhí)行這個算法所需要的內(nèi)存空間。v 一個算法所占用的存儲空間包括算法程序所占的空間、 輸入的初始數(shù)據(jù)所占的存儲空間以及某種數(shù)據(jù)結(jié)構(gòu)所需 要的附加存儲空間。v 一個上機(jī)執(zhí)行的程序除了需要存儲空間來寄存本身所用 指令、常數(shù)、變量和輸入數(shù)據(jù)外，也需要一些對數(shù)據(jù)進(jìn) 行操作的工作單元和存儲一些為實現(xiàn)計算所需信息的輔 助空間。143 3、例題講解、例題講解v 算法的時間復(fù)雜度是指算法的時間復(fù)雜度是指( ( C C ) ) A A、執(zhí)行算法程序所需要的時間執(zhí)行算法程序所需要的時間 B B、算法程序

5、的長度算法程序的長度 C C、算法執(zhí)行過程中所需要的基本運(yùn)算次數(shù)算法執(zhí)行過程中所需要的基本運(yùn)算次數(shù) D D、算法程序中的指令條數(shù)算法程序中的指令條數(shù)v 算法的基本特征是可行性、確定性、算法的基本特征是可行性、確定性、 【1 1】和擁有足夠和擁有足夠 的情報。的情報。 【答案】【答案】: :有窮性有窮性v 算法的空間復(fù)雜度是指算法的空間復(fù)雜度是指( ( D D ) ) A) A) 算法程序的長度算法程序的長度 B) B) 算法程序中的指令條數(shù)算法程序中的指令條數(shù) C) C) 算法程序所占的存儲空間算法程序所占的存儲空間 D) D) 執(zhí)行過程中所需要的存儲空間執(zhí)行過程中所需要的存儲空間 15v 在

6、計算機(jī)中，算法是指（ B B ） A) 加工方法 B) B) 解題方案的準(zhǔn)確而完整的描述解題方案的準(zhǔn)確而完整的描述 C) 排序方法 D) 查詢方法v 算法分析的目的是( D D ) A) 找出數(shù)據(jù)結(jié)構(gòu)的合理性 B) 找出算法中輸入和輸出之間的關(guān)系 C) 分析算法的易懂性和可靠性 D) D) 分析算法的效率以求改進(jìn)分析算法的效率以求改進(jìn)v 算法的工作量大小和實現(xiàn)算法所需的存儲單元多少分別稱 為算法的 【 1 1 】 。【答案】【答案】: :時間復(fù)雜度和空間復(fù)雜度時間復(fù)雜度和空間復(fù)雜度 16Data Structure1 1、數(shù)據(jù)結(jié)構(gòu)研究的主要內(nèi)容、數(shù)據(jù)結(jié)構(gòu)研究的主要內(nèi)容v 當(dāng)今計算機(jī)應(yīng)用的特點：

7、 1、所處理的數(shù)據(jù)量大且具有一定的關(guān)系； 2、對其操作不再是單純的數(shù)值計算，而更多地是需 要對其進(jìn)行組織、管理和檢索。 對數(shù)據(jù)的討論不單單是數(shù)據(jù)本身，還要包括數(shù)據(jù)與對數(shù)據(jù)的討論不單單是數(shù)據(jù)本身，還要包括數(shù)據(jù)與數(shù)據(jù)之間的關(guān)系。數(shù)據(jù)之間的關(guān)系。下面各例表示不同的數(shù)據(jù)采用不同的數(shù)據(jù)結(jié)構(gòu)來組織。下面各例表示不同的數(shù)據(jù)采用不同的數(shù)據(jù)結(jié)構(gòu)來組織。17 學(xué) 生 基 本 情 況 學(xué) 號 姓 名 性 別 出 生 年 月 . 99070101 李 軍 男 80 12 . 99070102 王 顏 霞 女 81 2 . 99070103 孫 濤 男 80 9 . 99070104 單 曉 宏 男 81 3 . .

8、. . . . 特點： 每個學(xué)生的信息占據(jù)一行，所有學(xué)生的信息按學(xué)號順序依次排列構(gòu)成一張表格； 表中每個學(xué)生的信息依據(jù)學(xué)號的大小存在著一種前后關(guān)系，這就是我們所說的線性結(jié)構(gòu)； 對它的操作通常是插入某個學(xué)生的信息，刪除某個學(xué)生的信息，更新某個學(xué)生的信息，按條件檢索某個學(xué)生的信息等等。v 應(yīng)用舉例1學(xué)籍檔案管理假設(shè)一個學(xué)籍檔案管理系統(tǒng)應(yīng)包含如下表所示的學(xué)生信息。18v 應(yīng)用舉例2家庭血緣關(guān)系圖 表示家庭成員的輩分關(guān)系，使用下圖1-1所示的形式描述。3 1 21 3 21 2 31 23 2 12 3 12 1 32 11家庭血緣關(guān)系圖特點： 在求解過程中，所處理的數(shù)據(jù)之間具有層次關(guān)系，這是我們 所

9、說的樹形結(jié)構(gòu)； 對它的操作有：建立樹形結(jié)構(gòu)，輸出最結(jié)點內(nèi)容等等。v 應(yīng)用舉例3制定教學(xué)計劃 在制定教學(xué)計劃時，需要考慮各門課程的開設(shè)順序。有些課程需要先導(dǎo)課程，有些課程則不需要，而有些課程又是其他課程的先導(dǎo)課程。比如，計算機(jī)專業(yè)課程的開設(shè)情況如下表所示： 計算機(jī)專業(yè)學(xué)生的必修課程 課課程程編編號號 課課程程名名稱稱 需需要要的的先先導(dǎo)導(dǎo) 課課程程編編號號 C 1 程序設(shè)計基礎(chǔ) 無 C 2 離散數(shù)學(xué) C 1 C 3 數(shù)據(jù)結(jié)構(gòu) C 1 ，C 2 C 4 匯編語言 C 1 C 5 算法分析與設(shè)計 C 3 ，C 4 C 6 計算機(jī)組成原理 C 1 1 C 7 編譯原理 C 5 ，C 3 C 8 操作系

10、統(tǒng) C 3 ，C 6 C 9 高等數(shù)學(xué) 無 C 1 0 線性代數(shù) C 9 C 1 1 普通物理 C 9 C 1 2 數(shù)值分析 C 9 ，C 1 0 ，C 1 19這種數(shù)據(jù)可以用下面的圖來表示：v 課程先后關(guān)系的圖形描形式：c1c9c4c2c12c10c11c5c3c6c7c8圖 1-2 計算機(jī)專業(yè)必修課程開設(shè)先后關(guān)系20 1 1、數(shù)據(jù)的、數(shù)據(jù)的邏輯結(jié)構(gòu)邏輯結(jié)構(gòu) 2 2、數(shù)據(jù)的、數(shù)據(jù)的存儲結(jié)構(gòu)存儲結(jié)構(gòu) 3 3、數(shù)據(jù)的、數(shù)據(jù)的運(yùn)算運(yùn)算：檢索、排序、插入、刪除、修改等。：檢索、排序、插入、刪除、修改等。 A A線性結(jié)構(gòu)線性結(jié)構(gòu)B B非線性結(jié)構(gòu)非線性結(jié)構(gòu)A A順序存儲順序存儲 B B鏈?zhǔn)酱鎯︽準(zhǔn)酱鎯?

11、線性表線性表棧棧隊隊樹形結(jié)構(gòu)樹形結(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))數(shù)據(jù)結(jié)構(gòu)的主要研究問題：212 2、基本概念和術(shù)語、基本概念和術(shù)語 數(shù)據(jù)結(jié)構(gòu)是一門研究組織組織、存儲存儲和運(yùn)算運(yùn)算的一般方法的學(xué)科。例：整數(shù)整數(shù)(1,2)、實數(shù)實數(shù)(1.1,1.2)字符串字符串(Beijing)、圖形圖形、聲音聲音。計算機(jī)管理圖書問題 ： 在圖書館里有各種卡片：有按書名編排的、有按作者編排的、有按分類編排。如何將查詢圖書的這些信息存入計算機(jī)中既要考慮查詢時間短，又要考慮節(jié)省空間。最簡單的辦法之一是建立一張表，每一本書的信息在表中占一行，如：22數(shù)據(jù)元素在計算機(jī)中

12、的表示 數(shù)據(jù)結(jié)構(gòu)是一門研究組織組織、存儲存儲和運(yùn)算運(yùn)算的一般方法的學(xué)科。如何將0,1,2,3,4,5,6,7,8,9這10個數(shù)存放在計算機(jī)中能最快地達(dá)到你所需要的目的？ 目的不同，最佳的存儲方方法就不同。從大到小排列：9,8,7,6,5,4,3,2,1,0輸出偶數(shù)：0,2,4,6,8,1,3,5,7,9 對數(shù)據(jù)結(jié)構(gòu)中的節(jié)點進(jìn)行操作處理對數(shù)據(jù)結(jié)構(gòu)中的節(jié)點進(jìn)行操作處理（插入、刪除、修改、查找、排序）（插入、刪除、修改、查找、排序）23v 數(shù)據(jù)元素數(shù)據(jù)元素( (Data Element)Data Element) 數(shù)據(jù)元素是數(shù)據(jù)的基本單位，即數(shù)據(jù)集合中的個體。 有時一個數(shù)據(jù)元素可由若干數(shù)據(jù)項數(shù)據(jù)項(

13、Data ItemData Item)組成。數(shù)據(jù)項是數(shù)據(jù)的最小單位。數(shù)據(jù)元素亦稱節(jié)點節(jié)點或記錄記錄。數(shù)據(jù)結(jié)構(gòu)可描述為數(shù)據(jù)結(jié)構(gòu)可描述為 Group=Group=（D D，R R）有限個數(shù)據(jù)元素的集合有限個數(shù)據(jù)元素的集合有限個節(jié)點間關(guān)系的集合有限個節(jié)點間關(guān)系的集合2425數(shù)據(jù)結(jié)構(gòu)可描述為數(shù)據(jù)結(jié)構(gòu)可描述為 Group=（D，R）l 例例1：一年四季的數(shù)據(jù)結(jié)構(gòu)可表示成：一年四季的數(shù)據(jù)結(jié)構(gòu)可表示成B=（D，R） D=春，夏，秋，冬春，夏，秋，冬 R=（春，夏），（夏，秋），（秋，冬）（春，夏），（夏，秋），（秋，冬）l 例例2：家庭成員數(shù)據(jù)結(jié)構(gòu)可表示成：家庭成員數(shù)據(jù)結(jié)構(gòu)可表示成B=（D，R）D=父親，兒

14、子，女兒父親，兒子，女兒 R=（父親，兒子），（父親，女兒）（父親，兒子），（父親，女兒）26數(shù)據(jù)結(jié)構(gòu)也可用圖形表示數(shù)據(jù)結(jié)構(gòu)也可用圖形表示l一年四季的數(shù)據(jù)結(jié)構(gòu)可表示成一年四季的數(shù)據(jù)結(jié)構(gòu)可表示成l家庭成員數(shù)據(jù)結(jié)構(gòu)可表示成家庭成員數(shù)據(jù)結(jié)構(gòu)可表示成冬冬春春夏夏秋秋父親父親兒子兒子女兒女兒（ 概念：結(jié)點、前件、后件、根結(jié)點、葉子 ）27v 樹形結(jié)構(gòu)全校學(xué)生檔案管理的組織方式全校學(xué)生檔案管理的組織方式計算機(jī)程序管理系統(tǒng)也是典型的計算機(jī)程序管理系統(tǒng)也是典型的樹形結(jié)構(gòu)樹形結(jié)構(gòu)。281 14 42 23 3 D=1 , 2 , 3 , 4 D=1 , 2 , 3 , 4R=(1,2),(1,3), R=(1,

15、2),(1,3), (1,4),(2,3), (1,4),(2,3), (3,4),(2,4) (3,4),(2,4) 2 21 13 3 D= 1 , 2 , 3 D= 1 , 2 , 3 R=(1,2),(2,3),(3,2),(1,3) R=(1,2),(2,3),(3,2),(1,3)v 圖形結(jié)構(gòu)圖形結(jié)構(gòu)節(jié)點間的連結(jié)是任意的節(jié)點間的連結(jié)是任意的293 3、例題講解、例題講解v 數(shù)據(jù)處理的最小單位是數(shù)據(jù)處理的最小單位是( ( C C ) ) A)A)數(shù)據(jù)數(shù)據(jù) B)B)數(shù)據(jù)元素數(shù)據(jù)元素 C) C) 數(shù)據(jù)項數(shù)據(jù)項 D) D) 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)v 數(shù)據(jù)結(jié)構(gòu)作為計算機(jī)的一門學(xué)科，主要研究數(shù)據(jù)的邏

16、輯結(jié)構(gòu)、數(shù)據(jù)結(jié)構(gòu)作為計算機(jī)的一門學(xué)科，主要研究數(shù)據(jù)的邏輯結(jié)構(gòu)、對各種數(shù)據(jù)結(jié)構(gòu)進(jìn)行的運(yùn)算，以及對各種數(shù)據(jù)結(jié)構(gòu)進(jìn)行的運(yùn)算，以及( ( A A ) ) A) A) 數(shù)據(jù)的存儲結(jié)構(gòu)數(shù)據(jù)的存儲結(jié)構(gòu) B) B) 計算方法計算方法 C) C) 數(shù)據(jù)映象數(shù)據(jù)映象 D) D) 邏輯存儲邏輯存儲v 數(shù)據(jù)結(jié)構(gòu)包括數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)包括數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的 【4 4】 以及對數(shù)據(jù)的以及對數(shù)據(jù)的操作運(yùn)算。操作運(yùn)算。 【答案【答案】物理結(jié)構(gòu)（或存儲結(jié)構(gòu)）物理結(jié)構(gòu)（或存儲結(jié)構(gòu)）30v 線性結(jié)構(gòu)與非線性結(jié)構(gòu)：線性結(jié)構(gòu)與非線性結(jié)構(gòu)：v 線性結(jié)構(gòu)：有且只有一個根結(jié)點；每一個線性結(jié)構(gòu)：有且只有一個根結(jié)點；每一個結(jié)點最

17、多有一個前件，也最多有一個后件。結(jié)點最多有一個前件，也最多有一個后件。 如：一年四季，如：一年四季，2626個英文字母個英文字母v非線性結(jié)構(gòu)：線性以外的數(shù)據(jù)結(jié)構(gòu)。非線性結(jié)構(gòu)：線性以外的數(shù)據(jù)結(jié)構(gòu)。 如：反映家庭成員間輩分關(guān)系的數(shù)據(jù)結(jié)構(gòu)如：反映家庭成員間輩分關(guān)系的數(shù)據(jù)結(jié)構(gòu) 31結(jié)點間是以線性關(guān)系聯(lián)結(jié)，結(jié)點間是以線性關(guān)系聯(lián)結(jié)，如前面提到的：一年四季26個英文字母 線性 有限 序列4、線性表、線性表（Linear List）v 線性表線性表：具有線性結(jié)構(gòu)的有限序列。A AB BC CD DZ Z春春夏夏秋秋冬冬32學(xué)生成績表學(xué)生成績表線性表線性表33數(shù)據(jù)元素、結(jié)點、記錄數(shù)據(jù)項線性v 線性表的定義線性表

18、的定義: : 線性表線性表是是n n個元素的有限序列，它們之間的關(guān)系可以排成個元素的有限序列，它們之間的關(guān)系可以排成一個線性序列：一個線性序列：a1a1，a2a2， ，aiai， ，anan 其中其中n n稱作表的稱作表的長度長度，當(dāng)，當(dāng)n=0n=0時，稱作時，稱作空表空表。v 線性表的特點：線性表的特點： 1 1、線性表中所有元素的性質(zhì)相同。、線性表中所有元素的性質(zhì)相同。 2 2、除第一個和最后一個數(shù)據(jù)元素之外，其它數(shù)據(jù)元素有且、除第一個和最后一個數(shù)據(jù)元素之外，其它數(shù)據(jù)元素有且 僅有一個前驅(qū)和一個后繼。第一個數(shù)據(jù)元素?zé)o前驅(qū)，最僅有一個前驅(qū)和一個后繼。第一個數(shù)據(jù)元素?zé)o前驅(qū)，最 后一個數(shù)據(jù)元素?zé)o

19、后繼。后一個數(shù)據(jù)元素?zé)o后繼。 3 3、數(shù)據(jù)元素在表中的位置只取決于它自身的序號。、數(shù)據(jù)元素在表中的位置只取決于它自身的序號。v 在線性表上常用的運(yùn)算有：在線性表上常用的運(yùn)算有： 初始化、求長度、取元素、修改、前插、刪除、檢索、排序初始化、求長度、取元素、修改、前插、刪除、檢索、排序3435v 線性表的線性表的 順序存儲結(jié)構(gòu) 及其及其 插入 與與 刪除 操作操作 特點：特點： 1 1、線性表中數(shù)據(jù)元素類型一致，只有數(shù)據(jù)域，存儲空間、線性表中數(shù)據(jù)元素類型一致，只有數(shù)據(jù)域，存儲空間 利用率高。利用率高。 2 2、所有元素所占的存儲空間是連續(xù)的。、所有元素所占的存儲空間是連續(xù)的。 3 3、各數(shù)據(jù)元素在

20、存儲空間中是按邏輯順序依次存放的、各數(shù)據(jù)元素在存儲空間中是按邏輯順序依次存放的 （a a）做插入、刪除時需移動大量元素。做插入、刪除時需移動大量元素。 （b b）空間估計不明時，按最大空間分配?？臻g估計不明時，按最大空間分配。 36順順序序存存儲儲存儲地址存儲地址存儲內(nèi)容存儲內(nèi)容元素元素n n.元素元素i i.元素元素2 2元素元素1 1L Lo o + + mL Lo o+(i-1)+(i-1)mLo+Lo+（n-1)n-1)mLoc(Loc(元素元素i)=Li)=Lo o+ +（i-1)i-1)m每個元素所占用每個元素所占用的存儲單元個數(shù)的存儲單元個數(shù)v 線性表的線性表的 順序存儲結(jié)構(gòu)順序

21、存儲結(jié)構(gòu)：首地址首地址起始地址起始地址基地址基地址v插入運(yùn)算插入運(yùn)算a ai-1i-1.a a2 2a a1 1a alengthlength a ai+1i+1a ai ia alengtlength h 插入算法的分析 假設(shè)線性表中含有n個數(shù)據(jù)元素，在進(jìn)行插入操作時，若假定在n+1個位置上插入元素的可能性均等，則平均移動元素的個數(shù)為：1n1iis2n1)i(n1n1E37X Xa ai-1i-1.a a2 2a a1 1a alengthlength a ai+1i+1a ai iX X在進(jìn)行刪除操作時，若假定刪除每個元素的可能性均等，則平均移動元素的個數(shù)為：分析結(jié)論分析結(jié)論 順序存儲結(jié)構(gòu)

22、表示的線性表，在做插入或刪除操作時，平均需要移動大約一半的數(shù)據(jù)元素。當(dāng)線性表的數(shù)據(jù)元素量較大，并且經(jīng)常要對其做插入或刪除操作時，這一點需要值得考慮。n1idl21ni)(nn1Ev刪除算法的分析刪除算法的分析38q 線性表的例題講解線性表的例題講解v 順序存儲方法是把邏輯上相鄰的結(jié)點存儲在物理位置順序存儲方法是把邏輯上相鄰的結(jié)點存儲在物理位置 【1 1】 的存儲單元中。的存儲單元中。 【答案【答案】相鄰相鄰v 長度為長度為n n的順序存儲線性表中，當(dāng)在任何位置上插入一個元的順序存儲線性表中，當(dāng)在任何位置上插入一個元 素概率都相等時，插入一個元素所需移動元素的平均個數(shù)素概率都相等時，插入一個元素

23、所需移動元素的平均個數(shù) 為為【2 2】 。 【答案【答案】 n/2n/2v 線性表線性表L=(a1,a2,a3,L=(a1,a2,a3,aiai，an)an)，下列說法正確的是（下列說法正確的是（D D） A) A) 每個元素都有一個直接前件和直接后件每個元素都有一個直接前件和直接后件 B) B) 線性表中至少要有一個元素線性表中至少要有一個元素 C) C) 表中諸元素的排列順序必須是由小到大或由大到小表中諸元素的排列順序必須是由小到大或由大到小 D) D) 除第一個元素和最后一個元素外，其余每個元素都有一除第一個元素和最后一個元素外，其余每個元素都有一 個且只有一個直接前件和直接后件個且只有

24、一個直接前件和直接后件 3940 數(shù)據(jù)結(jié)構(gòu)中，與所使用的計算機(jī)無關(guān)的是數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)中，與所使用的計算機(jī)無關(guān)的是數(shù)據(jù)的( ( C C ) ) A) A) 存儲結(jié)構(gòu)存儲結(jié)構(gòu)B) B) 物理結(jié)構(gòu)物理結(jié)構(gòu) C) C) 邏輯結(jié)構(gòu)邏輯結(jié)構(gòu)D) D) 物理和存儲結(jié)構(gòu)物理和存儲結(jié)構(gòu) 下列敘述中，錯誤的是（下列敘述中，錯誤的是（ B B ） A) A) 數(shù)據(jù)的存儲結(jié)構(gòu)與數(shù)據(jù)處理的效率密切相關(guān)數(shù)據(jù)的存儲結(jié)構(gòu)與數(shù)據(jù)處理的效率密切相關(guān) B) B) 數(shù)據(jù)的存儲結(jié)構(gòu)與數(shù)據(jù)處理的效率無關(guān)數(shù)據(jù)的存儲結(jié)構(gòu)與數(shù)據(jù)處理的效率無關(guān) C) C) 數(shù)據(jù)的存儲結(jié)構(gòu)在計算機(jī)中所占的空間不一定是連續(xù)的數(shù)據(jù)的存儲結(jié)構(gòu)在計算機(jī)中所占的空間不一定

25、是連續(xù)的 D) D) 一種數(shù)據(jù)的邏輯結(jié)構(gòu)可以有多種存儲結(jié)構(gòu)一種數(shù)據(jù)的邏輯結(jié)構(gòu)可以有多種存儲結(jié)構(gòu) 數(shù)據(jù)的存儲結(jié)構(gòu)是指（數(shù)據(jù)的存儲結(jié)構(gòu)是指（ B B ） A A）數(shù)據(jù)所占的存儲空間數(shù)據(jù)所占的存儲空間 B B）數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機(jī)中的表示數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機(jī)中的表示 C C）數(shù)據(jù)在計算機(jī)中的順序存儲方式數(shù)據(jù)在計算機(jī)中的順序存儲方式 D D）存儲在外存中的數(shù)據(jù)存儲在外存中的數(shù)據(jù) 根據(jù)數(shù)據(jù)結(jié)構(gòu)中各數(shù)據(jù)元素之間前后件關(guān)系的復(fù)雜程度，一般根據(jù)數(shù)據(jù)結(jié)構(gòu)中各數(shù)據(jù)元素之間前后件關(guān)系的復(fù)雜程度，一般將數(shù)據(jù)結(jié)構(gòu)分成將數(shù)據(jù)結(jié)構(gòu)分成( ( C C ) ) A) A) 動態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu)動態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu) B) B)

26、緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu)緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu) C) C) 線性結(jié)構(gòu)和非線性結(jié)構(gòu)線性結(jié)構(gòu)和非線性結(jié)構(gòu) D) D) 內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu)內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu) 數(shù)據(jù)的邏輯結(jié)構(gòu)有線性結(jié)構(gòu)和數(shù)據(jù)的邏輯結(jié)構(gòu)有線性結(jié)構(gòu)和 【2 2】兩大類。兩大類。非線性結(jié)構(gòu)非線性結(jié)構(gòu) 當(dāng)線性表采用順序存儲結(jié)構(gòu)實現(xiàn)存儲時，其主要特點是當(dāng)線性表采用順序存儲結(jié)構(gòu)實現(xiàn)存儲時，其主要特點是【1】。 【答案【答案】邏輯結(jié)構(gòu)中相鄰的結(jié)點在存儲結(jié)構(gòu)中仍相鄰。邏輯結(jié)構(gòu)中相鄰的結(jié)點在存儲結(jié)構(gòu)中仍相鄰。41 a1 a2 . an進(jìn)棧進(jìn)棧出棧出棧棧頂棧頂棧底棧底5 5、堆棧和隊列、堆棧和隊列q 堆棧和隊列的定義堆棧和隊列的定義 棧和隊列棧和隊列是兩種特殊

27、的線性表，它們是運(yùn)算時要受到是兩種特殊的線性表，它們是運(yùn)算時要受到某些限制的線性表，故也稱為某些限制的線性表，故也稱為限定性的數(shù)據(jù)結(jié)構(gòu)。限定性的數(shù)據(jù)結(jié)構(gòu)。v 堆棧的定義堆棧的定義堆棧：堆棧：限定只能在表的一端進(jìn)行插入和刪除的特殊的線性表限定只能在表的一端進(jìn)行插入和刪除的特殊的線性表, ,此種此種 結(jié)構(gòu)稱為結(jié)構(gòu)稱為后進(jìn)先出。后進(jìn)先出。設(shè)棧設(shè)棧s=s=（a a1 1，a a2 2，a ai i， ，a an n）, ,其中其中a a1 1是是棧底棧底元素，元素， a an n是是棧頂棧頂元素。元素。棧頂（棧頂（top)top)：允許插入和刪除的一端；允許插入和刪除的一端；約定約定toptop始終指

28、向新數(shù)據(jù)元素將存放的位置。始終指向新數(shù)據(jù)元素將存放的位置。棧底棧底（bottom):bottom):不允許插入和刪除的一端。不允許插入和刪除的一端。42v 隊列的定義隊列的定義隊列：隊列：一種特殊的線性結(jié)構(gòu)，限定只能在表的一端進(jìn)行插入，一種特殊的線性結(jié)構(gòu)，限定只能在表的一端進(jìn)行插入， 在表的另一端進(jìn)行刪除的線性表在表的另一端進(jìn)行刪除的線性表 。此種結(jié)構(gòu)稱為。此種結(jié)構(gòu)稱為先進(jìn)先進(jìn) 先出（先出（FIFO）表表。 a1 , a2 , a3 , a4 , an-1 , an隊隊 列列 示示 意意 圖圖隊頭隊頭隊尾隊尾v 隊列的主要運(yùn)算隊列的主要運(yùn)算（1）設(shè)置一個空隊列；（2）插入一個新的隊尾元素，稱為

29、進(jìn)隊；（3）刪除隊頭元素，稱為出隊；（4）讀取隊頭元素；43q 堆棧和隊列的例題講解堆棧和隊列的例題講解v棧和隊列的共同特點是（棧和隊列的共同特點是（ C C ） A)A)都是先進(jìn)先出都是先進(jìn)先出 B) B) 都是先進(jìn)后出都是先進(jìn)后出 C) C) 只允許在端點處插入和刪除元素只允許在端點處插入和刪除元素 D) D) 沒有共同點沒有共同點v如果進(jìn)棧序列為如果進(jìn)棧序列為e1,e2,e3,e4e1,e2,e3,e4，則可能的出棧序列是（則可能的出棧序列是（ B B ） A) e3,e1,e4,e2 A) e3,e1,e4,e2 B) e4,e3,e2,e1B) e4,e3,e2,e1 C) e3,e

30、4,e1,e2 C) e3,e4,e1,e2 D) D) 任意順序任意順序 4445la = 42+b8 82 26 6lb = 63+clc = 32+dld = 1+2= 8 + b= 2 + c= 6 + d= 3826u 一些重要的程序語言一些重要的程序語言( (如如C C語言和語言和PascalPascal語言語言) ) 允許過程允許過程的遞歸調(diào)用。而實現(xiàn)遞歸調(diào)用中的存儲分配通常用（的遞歸調(diào)用。而實現(xiàn)遞歸調(diào)用中的存儲分配通常用（ A A ） A) A) 棧棧B) B) 堆堆 C) C) 數(shù)組數(shù)組 D) D) 鏈表鏈表v 當(dāng)循環(huán)隊列非空且隊尾指針等于隊頭指針時，說明循環(huán)隊列當(dāng)循環(huán)隊列非

31、空且隊尾指針等于隊頭指針時，說明循環(huán)隊列已滿，不能進(jìn)行入隊運(yùn)算。這種情況稱為已滿，不能進(jìn)行入隊運(yùn)算。這種情況稱為【2 2】。答案：答案：上溢上溢 v 由兩個棧共享一個存儲空間的好處是（由兩個棧共享一個存儲空間的好處是（ B B ） A) A) 減少存取時間，降低下溢發(fā)生的機(jī)率減少存取時間，降低下溢發(fā)生的機(jī)率 B) B) 節(jié)省存儲空間，降低上溢發(fā)生的機(jī)率節(jié)省存儲空間，降低上溢發(fā)生的機(jī)率 C) C) 減少存取時間，降低上溢發(fā)生的機(jī)率減少存取時間，降低上溢發(fā)生的機(jī)率 D) D) 節(jié)省存儲空間，降低下溢發(fā)生的機(jī)率節(jié)省存儲空間，降低下溢發(fā)生的機(jī)率v 下列關(guān)于棧的敘述中正確的是（下列關(guān)于棧的敘述中正確的是

32、（ D D ）) )在棧中只能插入數(shù)據(jù)在棧中只能插入數(shù)據(jù) B B）在棧中只能刪除數(shù)據(jù)在棧中只能刪除數(shù)據(jù)C C）棧是先進(jìn)先出的線性表棧是先進(jìn)先出的線性表 D D）棧是后進(jìn)先出的線性表棧是后進(jìn)先出的線性表v 下列關(guān)于隊列的敘述中正確的是（下列關(guān)于隊列的敘述中正確的是（ C C ）在隊列中只能插入數(shù)據(jù)）在隊列中只能插入數(shù)據(jù) B B）在隊列中只能刪除數(shù)據(jù)在隊列中只能刪除數(shù)據(jù)C C）隊列是先進(jìn)先出的線性表隊列是先進(jìn)先出的線性表 D D）隊列是后進(jìn)先出的線性表隊列是后進(jìn)先出的線性表 46兩個棧共享只有兩個棧兩個棧共享只有兩個棧都多時才溢出。不共享都多時才溢出。不共享的話，兩個棧只有一個的話，兩個棧只有一個

33、棧多就溢出，棧多就溢出，RearRear隊尾隊尾FrontFront隊頭隊頭v 棧底至棧頂依次存放元素棧底至棧頂依次存放元素A A、B B、C C、D D，在第五個元素在第五個元素E E 入棧前，棧中元素可以出棧，則出棧序列可能是（入棧前，棧中元素可以出棧，則出棧序列可能是（ B B ） A) ABCEDA) ABCED B) DCBEAB) DCBEA C) DBCEA C) DBCEA D) CDABE D) CDABE 47D D出出C C出出B B出出 E E出出A A出出 E E進(jìn)進(jìn) 順序出棧：出棧：進(jìn)棧：進(jìn)棧： 順序存儲結(jié)構(gòu)常用于線性數(shù)據(jù)結(jié)構(gòu)，將邏輯上相鄰的數(shù)據(jù)元素存儲在物理上相鄰

34、的存儲單元里。v 順序存儲結(jié)構(gòu)的三個缺點： 1.作插入或刪除操作時，需移動大量元數(shù)。 2.長度變化較大時，需按最大空間分配。 3.表的容量難以擴(kuò)充。存儲內(nèi)容存儲內(nèi)容元素元素n n.元素元素i i.元素元素2 2元素元素1 148496 6、線性表的鏈?zhǔn)酱鎯?線性鏈表線性鏈表v線性鏈表的基本概念：線性鏈表的基本概念： 線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)稱為線性鏈表。 為了適應(yīng)線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)，計算機(jī)存儲空間被劃分為一個一個小塊，每一小塊占若干字節(jié)，通常稱這些小塊為存儲結(jié)點。將存儲空間中的每一個存儲結(jié)點分為兩部：v一部分稱為數(shù)據(jù)域，用于存儲數(shù)據(jù)元素的值；v另一部分稱為指針域，用于存放下一個數(shù)據(jù)元素的存儲序號

35、（即存儲結(jié)點的地址），也就是指向后件結(jié)點. 線性鏈表中存儲結(jié)點的結(jié)構(gòu)如圖2.20所示501536元素21400元素11346元素3 元素4head 1346 元素3 1536 . . . 1536 元素2 1400 . . . 元素4 1346 1400 元素1 1345 指針 存儲內(nèi)容存儲地址 鏈?zhǔn)酱鎯?134552 指向線性表中第一個結(jié)點的指針HEAD稱為頭指針。 當(dāng)HEAD=NULL（或0）時稱為空表。 對于線性鏈表，可以從頭指針開始，沿著各個結(jié)點的指針掃描到鏈表中的所有結(jié)點。線性鏈表的邏輯結(jié)構(gòu)圖所示531、比順序存儲結(jié)構(gòu)的存儲密度小 (每個節(jié)點都由數(shù)據(jù)域和指針域組成，所以相同空間內(nèi)假設(shè)

36、全存滿的話順序比鏈?zhǔn)酱鎯Ω?。2、邏輯上相鄰的節(jié)點物理上不必相鄰。3、插入、刪除靈活 (不必移動節(jié)點，只要改變節(jié)點中的指針)。4、查找結(jié)點時鏈?zhǔn)酱鎯σ软樞虼鎯β?。v 鏈接存儲結(jié)構(gòu)特點：鏈接存儲結(jié)構(gòu)特點：545455v 線性鏈表的基本運(yùn)算：線性鏈表的基本運(yùn)算：線性鏈表的運(yùn)算主要有以下幾個：線性鏈表的運(yùn)算主要有以下幾個： 在線性鏈表中包含指定元素的結(jié)點之前在線性鏈表中包含指定元素的結(jié)點之前 插入插入一個新元素。一個新元素。 在線性鏈表中在線性鏈表中刪除刪除包含指定元素的結(jié)點。包含指定元素的結(jié)點。 將兩個線性鏈表按要求將兩個線性鏈表按要求合并合并成一個線性成一個線性 鏈表。鏈表。56 線性鏈表的

37、線性鏈表的 插入插入 運(yùn)算：運(yùn)算： 線性鏈表的插入線性鏈表的插入是指在鏈?zhǔn)酱鎯Y(jié)構(gòu)下是指在鏈?zhǔn)酱鎯Y(jié)構(gòu)下的線性表中插入一個新元素。的線性表中插入一個新元素。 為了要在線性鏈表中插入一個新元素，為了要在線性鏈表中插入一個新元素，首先要給該元素分配一個新結(jié)點，然后將存首先要給該元素分配一個新結(jié)點，然后將存放新元素值的結(jié)點鏈接到線性鏈表中指定的放新元素值的結(jié)點鏈接到線性鏈表中指定的位置。位置。575758 線性鏈表的刪除線性鏈表的刪除指在鏈?zhǔn)酱鎯Y(jié)構(gòu)下的指在鏈?zhǔn)酱鎯Y(jié)構(gòu)下的線性表中刪除包含指定元素的結(jié)點。線性表中刪除包含指定元素的結(jié)點。 為了在線性鏈表中刪除包含指定元素的為了在線性鏈表中刪除包含指定

38、元素的結(jié)點，首先要在線性鏈表中找到這個結(jié)點，結(jié)點，首先要在線性鏈表中找到這個結(jié)點，然后將要刪除結(jié)點放回到可利用棧。然后將要刪除結(jié)點放回到可利用棧。 線性鏈表的線性鏈表的 刪除刪除 運(yùn)算：運(yùn)算：5959a1a2ana3L.線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)可用線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)可用 “結(jié)構(gòu)指針結(jié)構(gòu)指針”來描述來描述帶頭結(jié)點的線性鏈表帶頭結(jié)點的線性鏈表datanexttypedef struct LNode int data; Struct LNode *next; JD;babaxPP單鏈表的插入運(yùn)算單鏈表的插入運(yùn)算S在在P所指向的結(jié)點之后插入新的結(jié)點所指向的結(jié)點之后插入新的結(jié)點babaxanaia1a2P

39、Pai-1xL單鏈表的插入運(yùn)算單鏈表的插入運(yùn)算S單鏈表的插入運(yùn)算單鏈表的插入運(yùn)算void lbcr (JD *p, int x) / * 在在P所指向的結(jié)點之后插入新的結(jié)點所指向的結(jié)點之后插入新的結(jié)點 */ JD *s; /* 定義指向結(jié)點類型的指針定義指向結(jié)點類型的指針 */ s=(JD *)malloc(sizeof(JD ); /* 生成新結(jié)點生成新結(jié)點 */ s-data=x; s-next=p-next; p-next=s; return OK; anaia1a2Pai-1L單鏈表的插入運(yùn)算單鏈表的插入運(yùn)算void lbcr (JD *p, int x) / * 在在P所指向的結(jié)點之

40、后插入新的結(jié)點所指向的結(jié)點之后插入新的結(jié)點 */ JD *s; /* 定義指向結(jié)點類型的指針定義指向結(jié)點類型的指針 */ s=(JD *)malloc(sizeof(JD ); /* 生成新結(jié)點生成新結(jié)點 */ s-data=x; s-next=p-next; p-next=s; return OK;anaia1a2Pai-1L單鏈表的插入運(yùn)算單鏈表的插入運(yùn)算void lbcr (JD *p, int x) / * 在在P所指向的結(jié)點之后插入新的結(jié)點所指向的結(jié)點之后插入新的結(jié)點 */ JD *s; /* 定義指向結(jié)點類型的指針定義指向結(jié)點類型的指針 */ s=(JD *)malloc(size

41、of(JD ); /* 生成新結(jié)點生成新結(jié)點 */ s-data=x; s-next=p-next; p-next=s; return OK; Sanaia1a2Pai-1xL單鏈表的插入運(yùn)算單鏈表的插入運(yùn)算void lbcr (JD *p, int x) / * 在在P所指向的結(jié)點之后插入新的結(jié)點所指向的結(jié)點之后插入新的結(jié)點 */ JD *s; /* 定義指向結(jié)點類型的指針定義指向結(jié)點類型的指針 */ s=(JD *)malloc(sizeof(JD ); /* 生成新結(jié)點生成新結(jié)點 */ s-data=x; s-next=p-next; p-next=s; return OK;Sanaia

42、1a2Pai-1xL單鏈表的插入運(yùn)算單鏈表的插入運(yùn)算void lbcr (JD *p, int x) / * 在在P所指向的結(jié)點之后插入新的結(jié)點所指向的結(jié)點之后插入新的結(jié)點 */ JD *s; /* 定義指向結(jié)點類型的指針定義指向結(jié)點類型的指針 */ s=(JD *)malloc(sizeof(JD ); /* 生成新結(jié)點生成新結(jié)點 */ s-data=x; s-next=p-next; p-next=s; return OK;Sanaia1a2Pai-1xL單鏈表的插入運(yùn)算單鏈表的插入運(yùn)算void lbcr (JD *p, int x) / * 在在P所指向的結(jié)點之后插入新的結(jié)點所指向的結(jié)點

43、之后插入新的結(jié)點 */ JD *s; /* 定義指向結(jié)點類型的指針定義指向結(jié)點類型的指針 */ s=(JD *)malloc(sizeof(JD ); /* 生成新結(jié)點生成新結(jié)點 */ s-data=x; s-next=p-next; p-next=s; return OK;void lbsc(JD *p) /* 刪除刪除p指針指向結(jié)點的后一個結(jié)點指針指向結(jié)點的后一個結(jié)點 */ JD *q; if(p-next !=NULL) q=p-next ; / * q指向指向p的后繼結(jié)點的后繼結(jié)點 */ p-next=q-next; /* 修改修改p結(jié)點的指針域結(jié)點的指針域 */ free(q); /

44、* 刪除并釋放結(jié)點刪除并釋放結(jié)點 */ 單鏈表的刪除運(yùn)算單鏈表的刪除運(yùn)算ai-1a1aiai+1Lpvoid lbsc(JD *p) /* 刪除刪除p指針指向結(jié)點的后一個結(jié)點指針指向結(jié)點的后一個結(jié)點 */ JD *q; if(p-next !=NULL) q=p-next ; / * q指向指向p的后繼結(jié)點的后繼結(jié)點 */ p-next=q-next; /* 修改修改p結(jié)點的指針域結(jié)點的指針域 */ free(q); /* 刪除并釋放結(jié)點刪除并釋放結(jié)點 */ 單鏈表的刪除運(yùn)算單鏈表的刪除運(yùn)算ai-1a1aiai+1Lpvoid lbsc(JD *p) /* 刪除刪除p指針指向結(jié)點的后一個結(jié)點指

45、針指向結(jié)點的后一個結(jié)點 */ JD *q; if(p-next !=NULL) q=p-next ; / * q指向指向p的后繼結(jié)點的后繼結(jié)點 */ p-next=q-next; /* 修改修改p結(jié)點的指針域結(jié)點的指針域 */ free(q); /* 刪除并釋放結(jié)點刪除并釋放結(jié)點 */ 單鏈表的刪除運(yùn)算單鏈表的刪除運(yùn)算a1q qai-1a1aiai+1Lpqvoid lbsc(JD *p) /*刪除刪除p指針指向結(jié)點的后一個結(jié)點指針指向結(jié)點的后一個結(jié)點 */ JD *q; if(p-next !=NULL) q=p-next ; / * q指向指向p的后繼結(jié)點的后繼結(jié)點 */ p-next=q

46、-next; /* 修改修改p結(jié)點的指針域結(jié)點的指針域 */ free(q); /* 刪除并釋放結(jié)點刪除并釋放結(jié)點 */ 單鏈表的刪除運(yùn)算單鏈表的刪除運(yùn)算ai-1a1aiai+1Lpqvoid lbsc(JD *p) /*刪除刪除p指針指向結(jié)點的后一個結(jié)點指針指向結(jié)點的后一個結(jié)點 */ JD *q; if(p-next !=NULL) q=p-next ; / * q指向指向p的后繼結(jié)點的后繼結(jié)點 */ p-next=q-next; /* 修改修改p結(jié)點的指針域結(jié)點的指針域 */ free(q); /* 刪除并釋放結(jié)點刪除并釋放結(jié)點 */ 單鏈表的刪除運(yùn)算單鏈表的刪除運(yùn)算ai-1a1aiai+

47、1Lpvoid lbsc(JD *p) /*刪除刪除p指針指向結(jié)點的后一個結(jié)點指針指向結(jié)點的后一個結(jié)點 */ JD *q; if(p-next !=NULL) q=p-next ; / * q指向指向p的后繼結(jié)點的后繼結(jié)點 */ p-next=q-next; /* 修改修改p結(jié)點的指針域結(jié)點的指針域 */ free(q); /* 刪除并釋放結(jié)點刪除并釋放結(jié)點 */ 單鏈表的刪除運(yùn)算單鏈表的刪除運(yùn)算線性鏈表的查找操作：線性鏈表的查找操作：設(shè)無表頭結(jié)點的線性鏈表的頭指針為設(shè)無表頭結(jié)點的線性鏈表的頭指針為h, h, 沿著鏈表的沿著鏈表的開始往后找結(jié)點開始往后找結(jié)點x x，若找到，則返回該結(jié)點在鏈表中

48、，若找到，則返回該結(jié)點在鏈表中的位置，否則返回空地址。的位置，否則返回空地址。JD *lbcz (JD *h,int x) JD *p; p=h; while (p!=NULL & p-data!=x) p=p-next; return(p); 2.5.2 2.5.2 循環(huán)鏈表循環(huán)鏈表: : 首尾相接的鏈表。首尾相接的鏈表。 將最后一個結(jié)點的空指針改為指向頭結(jié)點，從任一將最后一個結(jié)點的空指針改為指向頭結(jié)點，從任一結(jié)點出發(fā)均可找到其它結(jié)點。結(jié)點出發(fā)均可找到其它結(jié)點。a1a2ana3L.帶頭結(jié)點的單鏈表帶頭結(jié)點的單鏈表a1a2ana3L.循環(huán)單鏈表循環(huán)單鏈表LS28375PR(1) L=P

49、-next;28375PRSLL 對以下單鏈表分別執(zhí)行下列各程序段對以下單鏈表分別執(zhí)行下列各程序段,并并畫出結(jié)果示意圖畫出結(jié)果示意圖.LS28375PR(2) R-data=P-data;28575PRS(3) R-data=P-next-data;28775PRSLS28375PR(4) P-next-next-next-data=P-data;25375PRSLS28375PR(7) P=(JD*)malloc(sizeof(JD); P-data=10; R-link=P; P-link=S;LS28375PR(7) P=(JD*)malloc(sizeof(JD); P-data=10

50、; R-link=P; P-link=S;PLS28375PRLS28375PR(7) P=(JD*)malloc(sizeof(JD); P-data=10; R-next=P; P-next=S;P10LS28375PRLS28375PR(5) P=(JD*)malloc(sizeof(JD); P-data=10; R-next=P; P-next=S;LS28375RP10LS28375PR(7) P=(JD*)malloc(sizeof(JD); P-data=10; R-next=P; P-next=S;LS28375RP10LS28375PR(8) T=L; T-next=P-n

51、ext; free(P);LS2837PRT5LS28375PR(9) S-next=L;LS28375PR如果如果 S-next= =L 則則S所指向的結(jié)點為尾結(jié)點所指向的結(jié)點為尾結(jié)點.LS28375PR 循環(huán)鏈表的結(jié)構(gòu)與前面所討論的線性鏈表相比，具有以下循環(huán)鏈表的結(jié)構(gòu)與前面所討論的線性鏈表相比，具有以下兩個特點：兩個特點： 循環(huán)鏈表的頭指針指向表頭結(jié)點。循環(huán)鏈表的頭指針指向表頭結(jié)點。 在循環(huán)鏈表中，所有結(jié)點的指針構(gòu)成了一個環(huán)狀鏈。在循環(huán)鏈表中，所有結(jié)點的指針構(gòu)成了一個環(huán)狀鏈。 圖圖2.292.29是循環(huán)鏈表的示意圖。是循環(huán)鏈表的示意圖。v循環(huán)鏈表：循環(huán)鏈表：8889 在實際應(yīng)用中，循環(huán)鏈表

52、與線性單鏈表相在實際應(yīng)用中，循環(huán)鏈表與線性單鏈表相比主要有以下兩個方面的優(yōu)點：比主要有以下兩個方面的優(yōu)點： 在循環(huán)鏈表中，只要指出表中任何一個結(jié)點在循環(huán)鏈表中，只要指出表中任何一個結(jié)點 的位置，就可以從它出發(fā)訪問到表中其他所的位置，就可以從它出發(fā)訪問到表中其他所 有的結(jié)點。有的結(jié)點。 由于在循環(huán)鏈表中設(shè)置了一個表頭結(jié)點，因由于在循環(huán)鏈表中設(shè)置了一個表頭結(jié)點，因 此，在任何情況下，循環(huán)鏈表中至少有一個此，在任何情況下，循環(huán)鏈表中至少有一個 結(jié)點存在，結(jié)點存在，從而使空表與非空表的運(yùn)算統(tǒng)一從而使空表與非空表的運(yùn)算統(tǒng)一。v鏈表不具有的特點是（鏈表不具有的特點是（ B B ） A) A) 不必事先估計

53、存儲空間不必事先估計存儲空間 B) B) 可隨機(jī)訪問任一元素可隨機(jī)訪問任一元素 C) C) 插入刪除不需要移動元素插入刪除不需要移動元素 D) D) 所需空間與線性表長度成正比所需空間與線性表長度成正比v數(shù)據(jù)結(jié)構(gòu)分為邏輯結(jié)構(gòu)與存儲結(jié)構(gòu)，線性鏈表屬于數(shù)據(jù)結(jié)構(gòu)分為邏輯結(jié)構(gòu)與存儲結(jié)構(gòu)，線性鏈表屬于 【1 1】 。 【答案【答案】存儲結(jié)構(gòu)存儲結(jié)構(gòu)u 棧通常采用的兩種存儲結(jié)構(gòu)是（棧通常采用的兩種存儲結(jié)構(gòu)是（ A A ） A) A) 順序存儲結(jié)構(gòu)和鏈表存儲結(jié)構(gòu)順序存儲結(jié)構(gòu)和鏈表存儲結(jié)構(gòu) B) B) 散列方式和索引方式散列方式和索引方式 C) C) 鏈表存儲結(jié)構(gòu)和數(shù)組鏈表存儲結(jié)構(gòu)和數(shù)組 D) D) 線性存儲

54、結(jié)構(gòu)和非線性存儲結(jié)構(gòu)線性存儲結(jié)構(gòu)和非線性存儲結(jié)構(gòu)q 線性鏈表的例題講解線性鏈表的例題講解9091u 線性表的順序存儲結(jié)構(gòu)和線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)分別是線性表的順序存儲結(jié)構(gòu)和線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)分別是( ( C C ) )A) A) 順序存取的存儲結(jié)構(gòu)、順序存取的存儲結(jié)構(gòu)順序存取的存儲結(jié)構(gòu)、順序存取的存儲結(jié)構(gòu)B) B) 順序存取的存儲結(jié)構(gòu)、隨機(jī)存取的存儲結(jié)構(gòu)順序存取的存儲結(jié)構(gòu)、隨機(jī)存取的存儲結(jié)構(gòu)C) C) 隨機(jī)存取的存儲結(jié)構(gòu)、順序存取的存儲結(jié)構(gòu)隨機(jī)存取的存儲結(jié)構(gòu)、順序存取的存儲結(jié)構(gòu)D) D) 任意存取的存儲結(jié)構(gòu)、任意存取的存儲結(jié)構(gòu)任意存取的存儲結(jié)構(gòu)、任意存取的存儲結(jié)構(gòu)順序存儲結(jié)構(gòu)的地址在內(nèi)存中是連

55、續(xù)的所以可以通過計算地址實現(xiàn)隨機(jī)存取，而鏈?zhǔn)酱鎯Y(jié)構(gòu)的存儲地址不一定連續(xù)，只能通過第1個結(jié)點的指針順序存?。?927 7、樹與二叉樹：、樹與二叉樹：v 樹的基本概念：樹的基本概念： 前面我們討論的線性表，棧、隊列和數(shù)組等都是線性結(jié)構(gòu)。而樹是一種非線性數(shù)據(jù)結(jié)構(gòu)，它的每一個結(jié)點，都可以有不止一個直接后繼，除根外的所有結(jié)點，都有且只有一個直接前趨。這些數(shù)據(jù)結(jié)點按分支關(guān)系組織起來，清晰地反映了數(shù)據(jù)元素之間的層次關(guān)系。 93現(xiàn)實世界中，能用樹的結(jié)構(gòu)表示的例子現(xiàn)實世界中，能用樹的結(jié)構(gòu)表示的例子：學(xué)校的行政關(guān)系、書的層次結(jié)構(gòu)、人類的家族血緣關(guān)系等。學(xué)校的行政關(guān)系、書的層次結(jié)構(gòu)、人類的家族血緣關(guān)系等。9494

56、9595 二叉樹(binary tree)是一種很有用的非線性結(jié)構(gòu)。 二叉樹具有以下兩個特點：（1）非空二叉樹只有一個根結(jié)點；（2）每一個結(jié)點最多有兩棵子樹，且分別 稱為該結(jié)點的左子樹與右子樹。v 二叉樹（二叉樹（Binary TreeBinary Tree）：）： 因為樹的每個結(jié)點的度不同，存儲困難，使對樹的處理算法很復(fù)雜。所以引出二叉樹的討論。969797性質(zhì)性質(zhì)1 1：在任意一棵二叉樹中，度為0的結(jié)點 （即葉子結(jié)點）總是比度為2的結(jié)點多一個。二叉樹的性質(zhì)：二叉樹的性質(zhì)： 特別要注意：二叉樹是樹的特殊情況。a aa ab bb b兩棵不同的二叉樹98例子例子1 1：某二叉樹中度為2的結(jié)點有

57、18個，則 該二叉樹中有 19 19 個葉子結(jié)點。99性質(zhì)性質(zhì)2 2：二叉樹的第i層上至多有2 i-1（i 1）個結(jié)點二叉樹的性質(zhì)：二叉樹的性質(zhì)：423167891011121314155第三層上(i=3)，有23-1=4個節(jié)點。第四層上(i=4)，有24-1=8個節(jié)點。100二叉樹的性質(zhì)：二叉樹的性質(zhì)：性質(zhì)性質(zhì)3 3：深度為深度為h h的二叉樹中的二叉樹中至多至多含有含有2 2h h-1 -1個結(jié)點個結(jié)點423167891011121314155此樹的深度此樹的深度h=4h=4，共有共有2 24 4-1=15-1=15個節(jié)點。個節(jié)點。101v滿二叉樹與完全二叉樹滿二叉樹與完全二叉樹 滿二叉樹

58、是指除最后一層外，每一層上的所有結(jié)點都有兩個子結(jié)點。 完全二叉樹是指這樣的二叉樹：除最后一層外，每一層上的結(jié)點數(shù)均達(dá)到最大值；在最后一層上只缺少右邊的若干結(jié)點。 注意：滿二叉樹是完全二叉樹，完全二叉樹不一定是滿二叉樹。102v 滿二叉樹的特點：滿二叉樹的特點：每一層上都含有最大結(jié)點數(shù)。每一層上都含有最大結(jié)點數(shù)。102103v完全二叉樹的特點：完全二叉樹的特點：除最后一層外，每一層都取最大除最后一層外，每一層都取最大 結(jié)點數(shù)，最后一層結(jié)點都集中在該層最左邊的若干位置結(jié)點數(shù)，最后一層結(jié)點都集中在該層最左邊的若干位置103104 對于對于完全二叉樹完全二叉樹而言而言如果它的結(jié)點個數(shù)為如果它的結(jié)點個數(shù)

59、為偶偶數(shù)，則該二叉樹中：數(shù)，則該二叉樹中：葉子結(jié)點的個數(shù)葉子結(jié)點的個數(shù)=非葉子結(jié)點的個數(shù)非葉子結(jié)點的個數(shù)如果它的結(jié)點個數(shù)為如果它的結(jié)點個數(shù)為奇奇數(shù)，則該二叉樹中：數(shù)，則該二叉樹中：葉子結(jié)點的個數(shù)葉子結(jié)點的個數(shù)=非葉子結(jié)點的個數(shù)非葉子結(jié)點的個數(shù)+1+1（即葉子結(jié)點數(shù)比非葉子結(jié)點數(shù)（即葉子結(jié)點數(shù)比非葉子結(jié)點數(shù)多一個多一個）規(guī)律總結(jié)：規(guī)律總結(jié)：105v 例題講解例題講解1、設(shè)一棵完全二叉樹共有700個結(jié)點，則在該二叉樹中有 350 350 個葉子結(jié)點。2、在深度為5的滿二叉樹中，葉子結(jié)點的個數(shù)為（ C C ）(即第5層的葉子個數(shù)2i-1) A) 32 B) 31 C) 16 D) 15 v二叉樹的遍

60、歷二叉樹的遍歷 二叉樹的遍歷是指不重復(fù)地訪問二叉樹中的所有結(jié)點。 二叉樹的遍歷可以分為三種：前序前序遍歷、中序中序遍歷、后序后序遍歷。 設(shè)訪問根結(jié)點記作設(shè)訪問根結(jié)點記作V V；遍歷根的左子樹記作遍歷根的左子樹記作L L；遍遍歷根的右子樹記作歷根的右子樹記作R R； 前序：前序： VLRVLR（即即根根左右）左右） 中序：中序： LVRLVR（即左即左根根右）右） 后序：后序： LRVLRV（即左右即左右根根）1061071071081 1、設(shè)一棵二叉樹的中序遍歷結(jié)果為、設(shè)一棵二叉樹的中序遍歷結(jié)果為DBEAFC,DBEAFC, 前序遍歷結(jié)果為前序遍歷結(jié)果為ABDECFABDECF，則后序遍歷結(jié)則后序遍歷