二級公共基礎(chǔ)知識_圖文

1、123456 7 8 9 10 通過工作原理了解，熟悉計算機(jī)內(nèi)部執(zhí)行功能的基本意義。為理解程序打下基礎(chǔ)，特別理解計算機(jī)是機(jī)器。v 指令的集合。（解釋指令）v 通過硬件控制系統(tǒng)自動完成某一功能。v 通過一系列代碼實(shí)現(xiàn)。11v 計算機(jī)本身僅能識別二進(jìn)制代碼“0”、“1”。v 編程最直接、最低級的就是機(jī)器語言。v 為解決機(jī)器語言難理解、記憶等問題。出現(xiàn)符號語言。v 為使編程接近自然語言，出現(xiàn)高級語言。如C、PASCAL、FORTRAN等。v 為配合高級語言編程，出現(xiàn)了開發(fā)工具，提高效率、減輕勞動量。如VB、VC、PB、Delphi、VFP等。因此VFP不是編程語言。12v 不管什么形式編寫代碼，最終

2、都應(yīng)將代碼翻譯成機(jī)器語言， 這就是編譯程序的工作。不同的語言有不同的編譯器。v 程序控制是一種邏輯控制。因此，嚴(yán)謹(jǐn)?shù)倪壿嬎季S是一個 程序員必備的基本素質(zhì)。v 用程序?qū)崿F(xiàn)某一功能。有許多方法。具體用哪種完全取決 于程序員個人的思維方式。因此，程序是腦力勞動的結(jié)晶， 從某種意義上，編程又是一門藝術(shù)。v 程序的特殊性決定了程序的復(fù)雜性，且與實(shí)現(xiàn)功能的復(fù)雜 性密切相關(guān)成正比。因此為使復(fù)雜的、智力的編程工作規(guī) 范化、科學(xué)化，便出現(xiàn)了各種編程設(shè)計方法。如結(jié)構(gòu)化編 程方法、面向?qū)ο蟮某绦蛟O(shè)計方法等。13v 不管用什么方法編程，不管編程者智力程度如何，不管 采用什么樣的編程語言和方法，程序最終完成的功能穩(wěn) 定

3、、可靠、實(shí)用、易維護(hù)和安全等是程序的最終目標(biāo)， 也是程序員的追求。v 程序設(shè)計是一個復(fù)雜艱巨的過程。編寫代碼僅是程序設(shè) 計的一部分。必須先有思想，再有方法，然后才是編寫 代碼，且要經(jīng)過許多反復(fù)，不可急功近利。14v 程序設(shè)計語言指的是用來編寫程序的語言。v 人與計算機(jī)交流要使用語言，以便讓計算機(jī)工作，計算 機(jī)也通過語言把結(jié)果告訴用計算機(jī)的人“人機(jī)對 話”。v 人與計算機(jī)交流的語言非平常人與人之間交流的語言， 是專門的語言程序設(shè)計語言。v 程序設(shè)計語言是計算機(jī)系統(tǒng)軟件的重要組成部分。15v 執(zhí)行程序設(shè)計的語言有很多，可分高級語言和低級語言， 區(qū)別在于接近自然語言的程度v 高級語言一般與具體的計算

4、機(jī)硬件無關(guān)，比較接近人類 自然語言的語法習(xí)慣及數(shù)學(xué)表達(dá)形式。v 用高級語言編寫的源程序不能被機(jī)器直接執(zhí)行，需通過 編譯成解釋程序的翻譯才可被機(jī)器執(zhí)行（機(jī)器語言）。 16algorithm1 1、算法的基本概念、算法的基本概念 算法是對特定問題求解步驟的一種描述，它是指令的有限序列，其中每一條指令表示一個或多個操作。它是一組嚴(yán)謹(jǐn)?shù)囟x運(yùn)算順序的規(guī)則，并且每一個規(guī)則都是有效的，且是明確的，此順序?qū)⒃谟邢薜拇螖?shù)下終止。算法具有有窮性有窮性、確定性確定性、可行性可行性、輸入輸入和輸出輸出（擁有足夠的情報）等個重要特性。172 2、算法的基本要素、算法的基本要素v 對數(shù)據(jù)對象的運(yùn)算和操作： 算術(shù)運(yùn)算、邏

5、輯運(yùn)算、關(guān)系運(yùn)算、數(shù)據(jù)傳輸 算法中各操作之間的執(zhí)行順序； 描述算法的工具通常有傳統(tǒng)流程圖、N-S結(jié)構(gòu)化流程 圖、算法描述語言等； 一個算法一般可以用順序、選擇、循環(huán)三種基本結(jié)構(gòu) 組合而成。v 算法的控制結(jié)構(gòu)： 183 3、算法設(shè)計的基本方法、算法設(shè)計的基本方法v 列舉法v 歸納法v 遞推v 遞歸（以簡潔的形式設(shè)計和描述算法）v 減半遞推技術(shù)v 回溯法191 1、時間復(fù)雜度、時間復(fù)雜度v 依據(jù)算法編制的程序在計算機(jī)上運(yùn)行時所消耗的時間 來度量。通常有事后統(tǒng)計法和事前分析估算法。v 一個算法是由控制結(jié)構(gòu)（順序、分支和循環(huán)）和原操 作構(gòu)成的，算法時間取決于兩者的綜合效果。v 算法中基本操作重復(fù)執(zhí)行次

6、數(shù)n和算法執(zhí)行時間同步 增長，稱作算法的時間復(fù)雜度。202 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) 行操作的工作單元和存儲一些為實(shí)現(xiàn)計算所需信息的輔 助空間。213 3、例題講解、例題講解v 算法的時間復(fù)雜度是指算法的時間復(fù)雜度是指( ( C C ) ) A A、執(zhí)行算法程序所需要的時間執(zhí)行算法程序所需要的時間 B B、算法程序的長度算法程序的

7、長度 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í)行過程中所需要的存儲空間 22v 在計算機(jī)中，算法是

8、指（ 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 算法的工作量大小和實(shí)現(xiàn)算法所需的存儲單元多少分別稱 為算法的 【 1 1 】 ?！敬鸢浮俊敬鸢浮? :時間復(fù)雜度和空間復(fù)雜度時間復(fù)雜度和空間復(fù)雜度 23Data Structure1 1、數(shù)據(jù)結(jié)構(gòu)研究的主要內(nèi)容、數(shù)據(jù)結(jié)構(gòu)研究的主要內(nèi)容v 當(dāng)今計算機(jī)應(yīng)用的特點(diǎn)： 1、所處理的數(shù)

9、據(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)系。24 學(xué) 生 基 本 情 況 學(xué) 號 姓 名 性 別 出 生 年 月 . 99070101 李 軍 男 80 12 . 99070102 王 顏 霞 女 81 2 . 99070103 孫 濤 男 80 9 . 99070104 單 曉 宏 男 81 3 . . . . . . 特點(diǎn)： 每個學(xué)生的信息占據(jù)一行，所有學(xué)生的信息按學(xué)號順序依次排列構(gòu)成一張表格； 表中每個學(xué)生的信

10、息依據(jù)學(xué)號的大小存在著一種前后關(guān)系，這就是我們所說的線性結(jié)構(gòu)； 對它的操作通常是插入某個學(xué)生的信息，刪除某個學(xué)生的信息，更新某個學(xué)生的信息，按條件檢索某個學(xué)生的信息等等。v 應(yīng)用舉例1學(xué)籍檔案管理假設(shè)一個學(xué)籍檔案管理系統(tǒng)應(yīng)包含如下表所示的學(xué)生信息。25v 應(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)系圖特點(diǎn)： 在求解過程中，所處理的數(shù)據(jù)之間具有層次關(guān)系，這是我們 所說的樹形結(jié)構(gòu)； 對它的操作有：建立樹形結(jié)構(gòu)，輸出最結(jié)點(diǎn)內(nèi)容等等。v 應(yīng)用舉例3制定教學(xué)計劃 在制定教學(xué)計劃時，需

11、要考慮各門課程的開設(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 操作系統(tǒng) C 3 ，C 6 C 9 高等數(shù)學(xué) 無 C 1 0 線性代數(shù) C 9 C 1 1 普通物理 C 9 C 1

12、2 數(shù)值分析 C 9 ，C 1 0 ，C 1 26這種數(shù)據(jù)可以用下面的圖來表示：v 課程先后關(guān)系的圖形描形式：c1c9c4c2c12c10c11c5c3c6c7c8圖 1-2 計算機(jī)專業(yè)必修課程開設(shè)先后關(guān)系27 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)酱鎯?線性表線性表?xiàng)ｊ?duì)隊(duì)樹形結(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é)

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

14、,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é)點(diǎn)進(jìn)行操作處理對數(shù)據(jù)結(jié)構(gòu)中的節(jié)點(diǎn)進(jìn)行操作處理（插入、刪除、修改、查找、排序）（插入、刪除、修改、查找、排序）30v 數(shù)據(jù)元素數(shù)據(jù)元素( (Data Element)Data Element) 數(shù)據(jù)元素是數(shù)據(jù)的基本單位，即數(shù)據(jù)集合中的個體。 有時一個數(shù)據(jù)元素可由若干數(shù)據(jù)項(xiàng)數(shù)據(jù)項(xiàng)(Data ItemData Item)組成。數(shù)據(jù)項(xiàng)是數(shù)據(jù)的最小單位。數(shù)據(jù)元素亦稱節(jié)點(diǎn)節(jié)點(diǎn)或記錄記錄。數(shù)據(jù)結(jié)構(gòu)可描

15、述為數(shù)據(jù)結(jié)構(gòu)可描述為 Group=Group=（D D，R R）有限個數(shù)據(jù)元素的集合有限個數(shù)據(jù)元素的集合有限個節(jié)點(diǎn)間關(guān)系的集合有限個節(jié)點(diǎn)間關(guān)系的集合3132數(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=父親，兒子，女兒父親，兒子，女兒 R=（父親，兒子），（父親，女兒）（父親，兒子），（父親，女兒）冬冬春春夏夏秋秋父親父

16、親兒子兒子女兒女兒33數(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é)點(diǎn)、前件、后件、根結(jié)點(diǎn)、葉子 ）34v 樹形結(jié)構(gòu)全校學(xué)生檔案管理的組織方式全校學(xué)生檔案管理的組織方式計算機(jī)程序管理系統(tǒng)也是典型的計算機(jī)程序管理系統(tǒng)也是典型的樹形結(jié)構(gòu)樹形結(jié)構(gòu)。35HGFECDBA361 14 42 23 3 D=1 , 2 , 3 , 4 D=1 , 2 , 3 , 4R=(1,2),(1,3), R=(1,2),(1,3), (1,4),(2,3), (1,

17、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é)點(diǎn)間的連結(jié)是任意的節(jié)點(diǎn)間的連結(jié)是任意的373 3、例題講解、例題講解v 數(shù)據(jù)處理的最小單位是數(shù)據(jù)處理的最小單位是( ( C C ) ) A)A)數(shù)據(jù)數(shù)據(jù) B)B)數(shù)據(jù)元素數(shù)據(jù)元素 C) C) 數(shù)據(jù)項(xiàng)數(shù)據(jù)項(xiàng) D) D) 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)v 數(shù)據(jù)結(jié)構(gòu)作為計算機(jī)的一門學(xué)科，主要研究數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)結(jié)構(gòu)作為計算機(jī)的一門學(xué)科，主要研究數(shù)據(jù)的

18、邏輯結(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)）38v 線性結(jié)構(gòu)與非線性結(jié)構(gòu)：線性結(jié)構(gòu)與非線性結(jié)構(gòu)：v 線性結(jié)構(gòu)：有且只有一個根結(jié)點(diǎn)；每一個線性結(jié)構(gòu)：有且只有一個根結(jié)點(diǎn)；每一個結(jié)點(diǎn)最多有一個前件，也最多有一個后件。結(jié)點(diǎn)最多有一個前件，

19、也最多有一個后件。 如：一年四季，如：一年四季，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) 394、線性表、線性表（Linear List）學(xué)學(xué) 生生 成成 績績 表表 ( (按成績排列按成績排列) )86胡孝臣986110395劉忠賞9861107100張卓9861109成 績姓 名學(xué) 號v 線性表線性表結(jié)點(diǎn)間是以線性關(guān)系聯(lián)結(jié)：結(jié)點(diǎn)間是以線性關(guān)系聯(lián)結(jié)：v 線性表線性表：具有線性結(jié)構(gòu)的有限序列。 數(shù)據(jù)元素在線性表中的位置只取決于它們自己的序號，即數(shù)據(jù)元素之間的相對位置是

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

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

22、連續(xù)的。 3 3、各數(shù)據(jù)元素在存儲空間中是按邏輯順序依次存放的、各數(shù)據(jù)元素在存儲空間中是按邏輯順序依次存放的 （a a）做插入、刪除時需移動大量元素。做插入、刪除時需移動大量元素。 （b b）空間估計不明時，按最大空間分配?？臻g估計不明時，按最大空間分配。42順順序序存存儲儲存儲地址存儲地址存儲內(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 線性表

23、的線性表的 順序存儲結(jié)構(gòu)順序存儲結(jié)構(gòu)：首地址首地址起始地址起始地址基地址基地址43元素元素a a1 1元素元素a a2 2.元素元素a ai+1i+1. 0 0 1 1i i 線性表的順序存儲結(jié)構(gòu)線性表的順序存儲結(jié)構(gòu)可用可用C C語言中的一維數(shù)組來描述語言中的一維數(shù)組來描述. .第第i i個元素的個元素的a ai i存儲地址：存儲地址：Loc(aLoc(ai i)=Loc(a)=Loc(a1 1)+(i-1)+(i-1)* * m mVV VV ViViVm-1Vm-1 intint VM; VM; 其中：其中：V V是數(shù)組的名字，是數(shù)組的名字，M M是數(shù)組大小，是數(shù)組大小， 假設(shè)數(shù)組中的元素

24、是整型類型假設(shè)數(shù)組中的元素是整型類型v插入運(yùn)算插入運(yùn)算.a2a a1 1an.ai+1ai01i-1in-1a ai-1i-1.a a2 2a a1 1a alengthlength a ai+1i+1a ai i x x a ai-1i-1. a a2 2 a a1 1 X X a ai ia ai+1i+1.a alengtlength h 插入算法的分析 假設(shè)線性表中含有n個數(shù)據(jù)元素，在進(jìn)行插入操作時，若假定在n+1個位置上插入元素的可能性均等，則平均移動元素的個數(shù)為：1n1iis2n1)i(n1n1E44在進(jìn)行刪除操作時，若假定刪除每個元素的可能性均等，則平均移動元素的個數(shù)為：分析結(jié)論

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

26、都相等時，插入一個元素所需移動元素的平均個數(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) 除第一個元素和最后一個元素外，其余每個元素都有一除第一個元素和最后一個元素外，其余每個元素都有一 個且只有一個直接

27、前件和直接后件個且只有一個直接前件和直接后件 4647v 數(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)在

28、計算機(jī)中所占的空間不一定是連續(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)

29、和靜態(tài)結(jié)構(gòu) B) B) 緊湊結(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)實(shí)現(xiàn)存儲時，其主要特點(diǎn)是當(dāng)線性表采用順序存儲結(jié)構(gòu)實(shí)現(xiàn)存儲時，其主要特點(diǎn)是【1】。 【答案【答案】邏輯結(jié)構(gòu)中相鄰的結(jié)點(diǎn)在存儲結(jié)構(gòu)中仍相鄰。邏輯結(jié)構(gòu)中相鄰的結(jié)點(diǎn)在存儲結(jié)構(gòu)中仍相鄰。485 5、堆棧和隊(duì)列、堆棧和隊(duì)列q 堆棧和隊(duì)列的定義堆棧和隊(duì)列的定義 棧和隊(duì)列棧和隊(duì)列是兩種特殊的線性表，它們是運(yùn)算時要受到是

30、兩種特殊的線性表，它們是運(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始終指向新數(shù)據(jù)元素將存放的位置。始終

31、指向新數(shù)據(jù)元素將存放的位置。棧底棧底（bottom):bottom):不允許插入和刪除的一端。不允許插入和刪除的一端。 a1 a2 . an進(jìn)棧進(jìn)棧出棧出棧棧頂棧頂棧底棧底49v 隊(duì)列的定義隊(duì)列的定義隊(duì)列：隊(duì)列：一種特殊的線性結(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隊(duì)隊(duì) 列列 示示 意意 圖圖隊(duì)頭隊(duì)頭隊(duì)尾隊(duì)尾v 隊(duì)列的主要運(yùn)算隊(duì)列的主要運(yùn)算（1）設(shè)置一個空隊(duì)列；（2）插

32、入一個新的隊(duì)尾元素，稱為進(jìn)隊(duì)；（3）刪除隊(duì)頭元素，稱為出隊(duì)；（4）讀取隊(duì)頭元素；50q 堆棧和隊(duì)列的例題講解堆棧和隊(duì)列的例題講解v棧和隊(duì)列的共同特點(diǎn)是（棧和隊(duì)列的共同特點(diǎn)是（ C C ） A)A)都是先進(jìn)先出都是先進(jìn)先出 B) B) 都是先進(jìn)后出都是先進(jìn)后出 C) C) 只允許在端點(diǎn)處插入和刪除元素只允許在端點(diǎn)處插入和刪除元素 D) D) 沒有共同點(diǎn)沒有共同點(diǎn)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,e

33、2,e1 C) e3,e4,e1,e2 C) e3,e4,e1,e2 D) D) 任意順序任意順序v一些重要的程序語言一些重要的程序語言( (如如C C語言和語言和PascalPascal語言語言) ) 允許過程的允許過程的遞歸調(diào)用。而實(shí)現(xiàn)遞歸調(diào)用中的存儲分配通常用（遞歸調(diào)用。而實(shí)現(xiàn)遞歸調(diào)用中的存儲分配通常用（ A A ） A) A) 棧棧 B) B) 堆堆 C) C) 數(shù)組數(shù)組 D) D) 鏈表鏈表 51v 棧底至棧頂依次存放元素棧底至棧頂依次存放元素A A、B B、C C、D D，在第五個元素在第五個元素E E 入棧前，棧中元素可以出棧，則出棧序列可能是（入棧前，棧中元素可以出棧，則出棧序

34、列可能是（ B B ） A) ABCEDA) ABCED B) DCBEAB) DCBEA C) DBCEA C) DBCEA D) CDABE D) CDABE v 棧通常采用的兩種存儲結(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) 線性存儲結(jié)構(gòu)和非線性存儲結(jié)構(gòu)線性存儲結(jié)構(gòu)和非線性存儲結(jié)構(gòu)v 棧和隊(duì)列通常采用的存儲結(jié)構(gòu)是棧和隊(duì)列通常采用的存儲結(jié)構(gòu)是 【1 1】。 【答案【答案】鏈?zhǔn)酱鎯晚樞虼鎯︽準(zhǔn)酱鎯晚樞虼鎯

35、 下列數(shù)據(jù)結(jié)構(gòu)中，按先進(jìn)后出原則組織數(shù)據(jù)的是（下列數(shù)據(jù)結(jié)構(gòu)中，按先進(jìn)后出原則組織數(shù)據(jù)的是（ B B ） A) A) 線性鏈表線性鏈表 B) B) 棧棧 C) C) 循環(huán)鏈表循環(huán)鏈表 D) D) 順序表順序表 52v 當(dāng)循環(huán)隊(duì)列非空且隊(duì)尾指針等于隊(duì)頭指針時，說明循環(huán)隊(duì)列當(dāng)循環(huán)隊(duì)列非空且隊(duì)尾指針等于隊(duì)頭指針時，說明循環(huán)隊(duì)列已滿，不能進(jìn)行入隊(duì)運(yùn)算。這種情況稱為已滿，不能進(jìn)行入隊(duì)運(yùn)算。這種情況稱為【2 2】。答案：答案：上溢上溢 v 由兩個棧共享一個存儲空間的好處是（由兩個棧共享一個存儲空間的好處是（ B B ） A) A) 減少存取時間，降低下溢發(fā)生的機(jī)率減少存取時間，降低下溢發(fā)生的機(jī)率 B) B)

36、 節(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)于棧的敘述中正確的是（ D D ）) )在棧中只能插入數(shù)據(jù)在棧中只能插入數(shù)據(jù) B B）在棧中只能刪除數(shù)據(jù)在棧中只能刪除數(shù)據(jù)C C）棧是先進(jìn)先出的線性表?xiàng)Ｊ窍冗M(jìn)先出的線性表 D D）棧是后進(jìn)先出的線性表?xiàng)Ｊ呛筮M(jìn)先出的線性表v 下列關(guān)于隊(duì)列的敘述中正確的是（下列關(guān)于隊(duì)列的敘述中正確的是（ C C ）在隊(duì)列中只能插入數(shù)據(jù)）在隊(duì)列中只能插入數(shù)據(jù)

37、B B）在隊(duì)列中只能刪除數(shù)據(jù)在隊(duì)列中只能刪除數(shù)據(jù)C C）隊(duì)列是先進(jìn)先出的線性表隊(duì)列是先進(jìn)先出的線性表 D D）隊(duì)列是后進(jìn)先出的線性表隊(duì)列是后進(jìn)先出的線性表 53 順序存儲結(jié)構(gòu)常用于線性數(shù)據(jù)結(jié)構(gòu)，將邏輯上相鄰的數(shù)據(jù)元素存儲在物理上相鄰的存儲單元里。v 順序存儲結(jié)構(gòu)的三個缺點(diǎn)： 1.作插入或刪除操作時，需移動大量元數(shù)。 2.長度變化較大時，需按最大空間分配。 3.表的容量難以擴(kuò)充。存儲內(nèi)容存儲內(nèi)容元素元素n n.元素元素i i.元素元素2 2元素元素1 154556 6、線性鏈表、線性鏈表v線性鏈表的基本概念：線性鏈表的基本概念： 線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)稱為線性鏈表。 為了適應(yīng)線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)，

38、計算機(jī)存儲空間被劃分為一個一個小塊，每一小塊占若干字節(jié)，通常稱這些小塊為存儲結(jié)點(diǎn)。將存儲空間中的每一個存儲結(jié)點(diǎn)分為兩部：v一部分稱為數(shù)據(jù)域，用于存儲數(shù)據(jù)元素的值；v另一部分稱為指針域，用于存放下一個數(shù)據(jù)元素的存儲序號（即存儲結(jié)點(diǎn)的地址），也就是指向后件結(jié)點(diǎn). 線性鏈表中存儲結(jié)點(diǎn)的結(jié)構(gòu)如圖2.20所示56571、比順序存儲結(jié)構(gòu)的存儲密度小 (每個節(jié)點(diǎn)都由數(shù)據(jù)域和指針域組成，所以相同空間內(nèi)假設(shè)全存滿的話順序比鏈?zhǔn)酱鎯Ω?。2、邏輯上相鄰的節(jié)點(diǎn)物理上不必相鄰。3、插入、刪除靈活 (不必移動節(jié)點(diǎn)，只要改變節(jié)點(diǎn)中的指針)。4、查找結(jié)點(diǎn)時鏈?zhǔn)酱鎯σ软樞虼鎯β?。v 鏈接存儲結(jié)構(gòu)特點(diǎn)：鏈接存儲結(jié)構(gòu)特點(diǎn)：5

39、8 指向線性表中第一個結(jié)點(diǎn)的指針HEAD稱為頭指針。 當(dāng)HEAD=NULL（或0）時稱為空表。 對于線性鏈表，可以從頭指針開始，沿著各個結(jié)點(diǎn)的指針掃描到鏈表中的所有結(jié)點(diǎn)。線性鏈表的邏輯結(jié)構(gòu)圖所示59596061v 線性鏈表的基本運(yùn)算：線性鏈表的基本運(yùn)算：線性鏈表的運(yùn)算主要有以下幾個：線性鏈表的運(yùn)算主要有以下幾個： 在線性鏈表中包含指定元素的結(jié)點(diǎn)之前在線性鏈表中包含指定元素的結(jié)點(diǎn)之前 插入插入一個新元素。一個新元素。 在線性鏈表中在線性鏈表中刪除刪除包含指定元素的結(jié)點(diǎn)。包含指定元素的結(jié)點(diǎn)。 將兩個線性鏈表按要求將兩個線性鏈表按要求合并合并成一個線性成一個線性 鏈表。鏈表。62 線性鏈表的線性鏈表

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

41、點(diǎn)，首先要在線性鏈表中找到這個結(jié)點(diǎn)，結(jié)點(diǎn)，首先要在線性鏈表中找到這個結(jié)點(diǎn)，然后將要刪除結(jié)點(diǎn)放回到可利用棧。然后將要刪除結(jié)點(diǎn)放回到可利用棧。 線性鏈表的線性鏈表的 刪除刪除 運(yùn)算：運(yùn)算：6565 循環(huán)鏈表的結(jié)構(gòu)與前面所討論的線性鏈表相比，具有以下循環(huán)鏈表的結(jié)構(gòu)與前面所討論的線性鏈表相比，具有以下兩個特點(diǎn)：兩個特點(diǎn)： 循環(huán)鏈表的頭指針指向表頭結(jié)點(diǎn)。循環(huán)鏈表的頭指針指向表頭結(jié)點(diǎn)。 在循環(huán)鏈表中，所有結(jié)點(diǎn)的指針構(gòu)成了一個環(huán)狀鏈。在循環(huán)鏈表中，所有結(jié)點(diǎn)的指針構(gòu)成了一個環(huán)狀鏈。 圖圖2.292.29是循環(huán)鏈表的示意圖。是循環(huán)鏈表的示意圖。v循環(huán)鏈表：循環(huán)鏈表：6667 在實(shí)際應(yīng)用中，循環(huán)鏈表與線性單鏈表相

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

43、事先估計存儲空間 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)v線性表的順序存儲結(jié)構(gòu)和線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)分別是線性表的順序存儲結(jié)構(gòu)和線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)分別是( ( B B ) )A) A) 順序存取的存儲結(jié)構(gòu)、順序存取的存儲結(jié)構(gòu)順序存取的存儲結(jié)構(gòu)、順序存取的存儲結(jié)構(gòu)B) B) 隨機(jī)存取的存儲結(jié)構(gòu)、順序存取的存儲結(jié)構(gòu)隨機(jī)存取的存儲

44、結(jié)構(gòu)、順序存取的存儲結(jié)構(gòu)C) C) 隨機(jī)存取的存儲結(jié)構(gòu)、隨機(jī)存取的存儲結(jié)構(gòu)隨機(jī)存取的存儲結(jié)構(gòu)、隨機(jī)存取的存儲結(jié)構(gòu)D) D) 任意存取的存儲結(jié)構(gòu)、任意存取的存儲結(jié)構(gòu)任意存取的存儲結(jié)構(gòu)、任意存取的存儲結(jié)構(gòu)q 線性鏈表的例題講解線性鏈表的例題講解68697 7、樹與二叉樹：、樹與二叉樹：v 樹的基本概念：樹的基本概念： 前面我們討論的線性表，棧、隊(duì)列和數(shù)組等都是線性結(jié)構(gòu)。而樹是一種非線性數(shù)據(jù)結(jié)構(gòu)，它的每一個結(jié)點(diǎn)，都可以有不止一個直接后繼，除根外的所有結(jié)點(diǎn)，都有且只有一個直接前趨。這些數(shù)據(jù)結(jié)點(diǎn)按分支關(guān)系組織起來，清晰地反映了數(shù)據(jù)元素之間的層次關(guān)系。 70現(xiàn)實(shí)世界中，能用樹的結(jié)構(gòu)表示的例子現(xiàn)實(shí)世界中，能

45、用樹的結(jié)構(gòu)表示的例子：學(xué)校的行政關(guān)系、書的層次結(jié)構(gòu)、人類的家族血緣關(guān)系等。學(xué)校的行政關(guān)系、書的層次結(jié)構(gòu)、人類的家族血緣關(guān)系等。71717272 二叉樹(binary tree)是一種很有用的非線性結(jié)構(gòu)。 二叉樹具有以下兩個特點(diǎn)：（1）非空二叉樹只有一個根結(jié)點(diǎn)；（2）每一個結(jié)點(diǎn)最多有兩棵子樹，且分別 稱為該結(jié)點(diǎn)的左子樹與右子樹。v 二叉樹（二叉樹（Binary TreeBinary Tree）：）： 因?yàn)闃涞拿總€結(jié)點(diǎn)的度不同，存儲困難，使對樹的處理算法很復(fù)雜。所以引出二叉樹的討論。737474性質(zhì)性質(zhì)1 1：在任意一棵二叉樹中，度為0的結(jié)點(diǎn) （即葉子結(jié)點(diǎn)）總是比度為2的結(jié)點(diǎn)多 一個。例子例子1

46、1：某二叉樹中度為2的結(jié)點(diǎn)有18個，則 該二叉樹中有 19 19 個葉子結(jié)點(diǎn)。二叉樹的性質(zhì)：二叉樹的性質(zhì)： 特別要注意：二叉樹不是樹的特殊情況。a aa ab bb b兩棵不同的二叉樹7576性質(zhì)性質(zhì)2 2：二叉樹的第i層上至多有2 i-1（i 1）個結(jié)點(diǎn)二叉樹的性質(zhì)：二叉樹的性質(zhì)：423167891011121314155第三層上(i=3)，有23-1=4個節(jié)點(diǎn)。第四層上(i=4)，有24-1=8個節(jié)點(diǎn)。77二叉樹的性質(zhì)：二叉樹的性質(zhì)：性質(zhì)性質(zhì)3 3：深度為深度為h h的二叉樹中至多含有的二叉樹中至多含有2 2h h-1 -1個結(jié)點(diǎn)個結(jié)點(diǎn)423167891011121314155此樹的深度此

47、樹的深度h=4h=4，共有共有2 24 4-1=15-1=15個節(jié)點(diǎn)。個節(jié)點(diǎn)。78v滿二叉樹與完全二叉樹滿二叉樹與完全二叉樹 滿二叉樹是指除最后一層外，每一層上的所有結(jié)點(diǎn)都有兩個子結(jié)點(diǎn)。 完全二叉樹是指這樣的二叉樹：除最后一層外，每一層上的結(jié)點(diǎn)數(shù)均達(dá)到最大值；在最后一層上只缺少右邊的若干結(jié)點(diǎn)。 注意：滿二叉樹是完全二叉樹，完全二叉樹不一定是滿二叉樹。79v 滿二叉樹的特點(diǎn)：滿二叉樹的特點(diǎn)：每一層上都含有最大結(jié)點(diǎn)數(shù)。每一層上都含有最大結(jié)點(diǎn)數(shù)。7980v完全二叉樹的特點(diǎn)：完全二叉樹的特點(diǎn)：除最后一層外，每一層都取最大除最后一層外，每一層都取最大 結(jié)點(diǎn)數(shù)，最后一層結(jié)點(diǎn)都集中在該層最左邊的若干位置結(jié)點(diǎn)

48、數(shù)，最后一層結(jié)點(diǎn)都集中在該層最左邊的若干位置8081 對于對于完全二叉樹完全二叉樹而言而言如果它的結(jié)點(diǎn)個數(shù)為如果它的結(jié)點(diǎn)個數(shù)為偶偶數(shù)，則該二叉樹中：數(shù)，則該二叉樹中：葉子結(jié)點(diǎn)的個數(shù)葉子結(jié)點(diǎn)的個數(shù)=非葉子結(jié)點(diǎn)的個數(shù)非葉子結(jié)點(diǎn)的個數(shù)如果它的結(jié)點(diǎn)個數(shù)為如果它的結(jié)點(diǎn)個數(shù)為奇奇數(shù)，則該二叉樹中：數(shù)，則該二叉樹中：葉子結(jié)點(diǎn)的個數(shù)葉子結(jié)點(diǎn)的個數(shù)=非葉子結(jié)點(diǎn)的個數(shù)非葉子結(jié)點(diǎn)的個數(shù)+1+1（即葉子結(jié)點(diǎn)數(shù)比非葉子結(jié)點(diǎn)數(shù)（即葉子結(jié)點(diǎn)數(shù)比非葉子結(jié)點(diǎn)數(shù)多一個多一個）規(guī)律總結(jié)：規(guī)律總結(jié)：82v 例題講解例題講解1、設(shè)一棵完全二叉樹共有700個結(jié)點(diǎn)，則 在該二叉樹中有 350 350 個葉子結(jié)點(diǎn)。2、在深度為5的滿二叉樹中

49、，葉子結(jié)點(diǎn)的 個數(shù)為（ C C ） A) 32 B) 31 C) 16 D) 15 v二叉樹的遍歷二叉樹的遍歷 二叉樹的遍歷是指不重復(fù)地訪問二叉樹中的所有結(jié)點(diǎn)。 二叉樹的遍歷可以分為三種：前序前序遍歷、中中序序遍歷、后序后序遍歷。 設(shè)訪問根結(jié)點(diǎn)記作設(shè)訪問根結(jié)點(diǎn)記作V V；遍歷根的左子樹記作遍歷根的左子樹記作L L；遍歷根的右子樹記作遍歷根的右子樹記作R R； 前序：前序： VLRVLR（即即根根左右）左右） 中序：中序： LVRLVR（即左即左根根右）右） 后序：后序： LRVLRV（即左右即左右根根）838484851 1、設(shè)一棵二叉樹的中序遍歷結(jié)果為、設(shè)一棵二叉樹的中序遍歷結(jié)果為DBEAF

50、C,DBEAFC, 前序遍歷結(jié)果為前序遍歷結(jié)果為ABDECFABDECF，則后序遍歷結(jié)則后序遍歷結(jié) 果為：果為： DEBFCADEBFCA v 例題講解例題講解2 2、已知一棵二叉樹前序遍歷和中序遍歷分別、已知一棵二叉樹前序遍歷和中序遍歷分別 為為ABDEGCFHABDEGCFH和和DBGEACHFDBGEACHF，則該二叉樹則該二叉樹 的后序遍歷為（的后序遍歷為（ B B ） A) GEDHFBCA A) GEDHFBCA B) DGEBHFCAB) DGEBHFCA C) ABCDEFGH C) ABCDEFGH D) ACBFEDHG D) ACBFEDHG v具有具有3 3個結(jié)點(diǎn)的二叉

51、樹有（個結(jié)點(diǎn)的二叉樹有（ D D ） A) 2A) 2種形態(tài)種形態(tài) B) 4B) 4種形態(tài)種形態(tài) C) 7C) 7種形態(tài)種形態(tài) D) 5D) 5種形態(tài)種形態(tài) v 設(shè)有下列二叉樹：設(shè)有下列二叉樹： 對此二叉樹前序遍歷的結(jié)果為（對此二叉樹前序遍歷的結(jié)果為（ B B ） A) ZBTTCPXA A) ZBTTCPXA B) ATBZXCTP B) ATBZXCTP C) ZBTACTXP D) ATBZXCPT C) ZBTACTXP D) ATBZXCPT 86878 8、查找和排序：、查找和排序：v查找查找又稱為又稱為檢索檢索 查找算法的評價主要考慮算法的時間復(fù)雜查找算法的評價主要考慮算法的時間

52、復(fù)雜性，既可以采用數(shù)量級的形式表示，也可以采性，既可以采用數(shù)量級的形式表示，也可以采用平均檢索（查找）長度，即在查找成功情況用平均檢索（查找）長度，即在查找成功情況下的平均比較次數(shù)來表示。下的平均比較次數(shù)來表示。 查找可分為查找可分為順序查找順序查找和和二分法查找二分法查找兩種。兩種。88（a a）順序查找：順序查找： 順序查找順序查找又稱又稱線性查找線性查找。它是一種最簡單、。它是一種最簡單、最基本的查找方法。基本思想是：從表中第一最基本的查找方法。基本思想是：從表中第一條記錄開始，逐個進(jìn)行記錄的關(guān)鍵字和給定值條記錄開始，逐個進(jìn)行記錄的關(guān)鍵字和給定值的比較。若某個記錄的關(guān)鍵字和給定值相等，的

53、比較。若某個記錄的關(guān)鍵字和給定值相等，則查找成功；否則，若直至最后一個記錄，其則查找成功；否則，若直至最后一個記錄，其關(guān)鍵字和給定值都不相等，則表明表中沒有所關(guān)鍵字和給定值都不相等，則表明表中沒有所查記錄，查找不成功。查記錄，查找不成功。89 二分查找二分查找又稱又稱折半查找折半查找。作為二分查找對。作為二分查找對象的表必須是順序存儲的有序表，即各記錄的象的表必須是順序存儲的有序表，即各記錄的次序是按其關(guān)鍵字的大小順序（以下假定按從次序是按其關(guān)鍵字的大小順序（以下假定按從小到大的順序）排列的表。小到大的順序）排列的表。（b b）二分查找：二分查找：90 二分查找的二分查找的具體做法具體做法是是

54、: : 先取表先取表中間中間位置的記錄關(guān)位置的記錄關(guān)鍵字與給定值比較。若相等鍵字與給定值比較。若相等, , 則查找成功；否則則查找成功；否則, , 若給若給定值比該記錄的關(guān)鍵字小，則給定值必在表的前半部分。定值比該記錄的關(guān)鍵字小，則給定值必在表的前半部分。 在這前半部分中再取中間位置記錄的關(guān)鍵字進(jìn)行比較，在這前半部分中再取中間位置記錄的關(guān)鍵字進(jìn)行比較，就又可以排除這部分的一半。依次反復(fù)進(jìn)行，直到找到就又可以排除這部分的一半。依次反復(fù)進(jìn)行，直到找到給定值或找完全表而找不到為止。給定值或找完全表而找不到為止。 對于對于n n較大時，查找長度可以近似地表示為較大時，查找長度可以近似地表示為91 排序

55、排序是將一組雜亂無章的數(shù)據(jù)按一定的規(guī)是將一組雜亂無章的數(shù)據(jù)按一定的規(guī)律順次排列起來。律順次排列起來。 通常數(shù)據(jù)對象有多個屬性域，即由多個數(shù)通常數(shù)據(jù)對象有多個屬性域，即由多個數(shù)據(jù)成員組成據(jù)成員組成, , 其中有一個屬性域可用來區(qū)分對象其中有一個屬性域可用來區(qū)分對象, , 作為排序依據(jù)。該域稱為作為排序依據(jù)。該域稱為關(guān)鍵字（關(guān)鍵字（keykey）。 排序的時間開銷是衡量算法好壞的最重要排序的時間開銷是衡量算法好壞的最重要的標(biāo)志。對于長度為的標(biāo)志。對于長度為n n的有序線性表，查找時最的有序線性表，查找時最壞情況只需比較壞情況只需比較 n n次。次。v 排序（排序（sortsort）92（a a）交

56、換類排序：交換類排序：交換類排序法：交換類排序法：冒泡排序法冒泡排序法：需要比較的次數(shù)為：需要比較的次數(shù)為n(n-1)/2n(n-1)/2快速排序法快速排序法：是對冒泡排序的改進(jìn)，是：是對冒泡排序的改進(jìn)，是目目 前內(nèi)部排序中速度最快的一種。前內(nèi)部排序中速度最快的一種。 93（b b）插入類排序：插入類排序： 插入類排序的插入類排序的基本方法基本方法是：每步將一個待是：每步將一個待排序的對象，按其關(guān)鍵字大小，插入到前面已排序的對象，按其關(guān)鍵字大小，插入到前面已經(jīng)排好序的一組對象的適當(dāng)位置上，直到對象經(jīng)排好序的一組對象的適當(dāng)位置上，直到對象全部插入為止全部插入為止。簡單插入排序法：簡單插入排序法：

57、最壞情況需要最壞情況需要n(n-1)/2n(n-1)/2次比較；次比較；希爾排序法：希爾排序法：最壞情況需要最壞情況需要OO（n n ）次比較。次比較。94（c c）選擇類排序：選擇類排序： 選擇類排序的選擇類排序的思想思想是：每一趟（例如，第是：每一趟（例如，第i i趟，趟，i=0i=0，1 1，n n2 2）在后面在后面n ni i個待排序?qū)ο笾羞x個待排序?qū)ο笾羞x出關(guān)鍵字最?。ㄉ?，若為降序，選出最大關(guān)鍵出關(guān)鍵字最?。ㄉ?，若為降序，選出最大關(guān)鍵字）的對象，作為有序?qū)ο笮蛄械牡谧郑┑膶ο?，作為有序?qū)ο笮蛄械牡趇 i個對象。待個對象。待到第到第n n2 2趟作完，待排序?qū)ο笾皇Ｏ绿俗魍?，待?/p>

58、序?qū)ο笾皇Ｏ? 1個，不用再個，不用再選了，結(jié)束排序。選了，結(jié)束排序。簡單選擇排序法簡單選擇排序法，最壞情況需要，最壞情況需要n(n-1)/2n(n-1)/2次比較；次比較；堆排序法堆排序法，最壞情況需要，最壞情況需要OO（nlognlog2 2 n n）次比較。次比較。95（一）程序設(shè)計方法與風(fēng)格（一）程序設(shè)計方法與風(fēng)格 v 如何形成良好的程序設(shè)計風(fēng)格：如何形成良好的程序設(shè)計風(fēng)格： 1 1、源程序內(nèi)部文檔化；、源程序內(nèi)部文檔化； 選擇標(biāo)識符的名字選擇標(biāo)識符的名字 注釋（注釋（序言性序言性和和功能性功能性注釋）注釋） 程序的視覺組織程序的視覺組織一般位于模塊的一般位于模塊的首部，用于說明首部，

59、用于說明模塊的相關(guān)信息模塊的相關(guān)信息位于源程序位于源程序模塊內(nèi)部模塊內(nèi)部96 顯式地說明一切變量顯式地說明一切變量 數(shù)據(jù)說明的次序應(yīng)該規(guī)范化數(shù)據(jù)說明的次序應(yīng)該規(guī)范化 便于查找變量（按順序排列）便于查找變量（按順序排列） 對復(fù)雜數(shù)據(jù)結(jié)構(gòu)應(yīng)注釋說明對復(fù)雜數(shù)據(jù)結(jié)構(gòu)應(yīng)注釋說明 2 2、數(shù)據(jù)說明、數(shù)據(jù)說明3 3、語句的結(jié)構(gòu)、語句的結(jié)構(gòu) 每條語句簡單明了 盡量不用或少用GOTO語句 盡量只采用3種基本控制結(jié)構(gòu)編程4 4、輸入和輸出、輸入和輸出 對所有輸入數(shù)據(jù)進(jìn)行校驗(yàn)和合理性檢查對所有輸入數(shù)據(jù)進(jìn)行校驗(yàn)和合理性檢查 輸入輸出格式保持一致輸入輸出格式保持一致 設(shè)計良好的輸出報表設(shè)計良好的輸出報表 輸入方式輸入方

60、式應(yīng)力求簡單，盡量避免給用戶帶來不必要的麻煩；應(yīng)力求簡單，盡量避免給用戶帶來不必要的麻煩；交互式輸入數(shù)據(jù)時應(yīng)有必要的提示信息交互式輸入數(shù)據(jù)時應(yīng)有必要的提示信息; ; 程序應(yīng)對輸入數(shù)據(jù)的程序應(yīng)對輸入數(shù)據(jù)的合法性進(jìn)行檢查合法性進(jìn)行檢查; ;若用戶輸入某些數(shù)據(jù)后可能產(chǎn)生嚴(yán)重后果若用戶輸入某些數(shù)據(jù)后可能產(chǎn)生嚴(yán)重后果, ,應(yīng)應(yīng)給用戶輸出必要的提示并要求用戶確認(rèn)；應(yīng)根據(jù)系統(tǒng)的特點(diǎn)和給用戶輸出必要的提示并要求用戶確認(rèn)；應(yīng)根據(jù)系統(tǒng)的特點(diǎn)和用戶的習(xí)慣設(shè)計出令用戶滿意的輸入方式。用戶的習(xí)慣設(shè)計出令用戶滿意的輸入方式。 輸出數(shù)據(jù)的格式輸出數(shù)據(jù)的格式應(yīng)清晰，美觀；輸出數(shù)據(jù)時要加上必要的應(yīng)清晰，美觀；輸出數(shù)據(jù)時要加上必