計(jì)算機(jī)二級(jí)概述基本數(shù)據(jù)結(jié)構(gòu)與算法

1、計(jì)算機(jī)二級(jí)概述基本數(shù)據(jù)結(jié)構(gòu)與算法計(jì)算機(jī)二級(jí)概述基本數(shù)據(jù)結(jié)構(gòu)與算法1.1 算法(0.82%)1.1.1 算法(algorithm)基本概念定義：算法是指解題方案的準(zhǔn)確而完整的描述。算法不等于程序，不等于計(jì)算方法。只能說(shuō)程序是算法的一種描述，所以，程序不可能優(yōu)于算法的設(shè)計(jì)。算法是指一系列解決問(wèn)題的清晰指令。特征：算法具有可行性、確定性、有窮性、輸入和輸出（擁有足夠的情報(bào)）等個(gè)重要特性。計(jì)算機(jī)二級(jí)概述基本數(shù)據(jù)結(jié)構(gòu)與算法1.1.2 算法的基本要素 1、對(duì)數(shù)據(jù)的運(yùn)算和操作算術(shù)運(yùn)算邏輯運(yùn)算關(guān)系運(yùn)算數(shù)據(jù)傳輸2、算法的控制結(jié)構(gòu)算法中各操作之間的執(zhí)行順序描述算法的工具通常有傳統(tǒng)流程圖、N-S結(jié)構(gòu)化流程圖、算法描

2、述語(yǔ)言等一個(gè)算法一般可以用順序、選擇、循環(huán)三種基本機(jī)構(gòu)組合而成。計(jì)算機(jī)二級(jí)概述基本數(shù)據(jù)結(jié)構(gòu)與算法1.1.3 算法設(shè)計(jì)基本方法列舉法歸納法遞推遞歸減半遞推技術(shù)回溯法計(jì)算機(jī)二級(jí)概述基本數(shù)據(jù)結(jié)構(gòu)與算法1.2 算法復(fù)雜度1.2.1 時(shí)間復(fù)雜度 所謂算法的時(shí)間復(fù)雜度，是指執(zhí)行算法所需要的計(jì)算工作量。 可以用算法在執(zhí)行過(guò)程中所需要的基本運(yùn)算的執(zhí)行次數(shù)來(lái)度量算法的工作量。計(jì)算機(jī)二級(jí)概述基本數(shù)據(jù)結(jié)構(gòu)與算法1.2.2 算法的空間復(fù)雜度一般是指執(zhí)行這個(gè)算法所需要的內(nèi)存空間一個(gè)算法所占用的存儲(chǔ)空間包括算法程序所占的空間、輸入的初始數(shù)據(jù)所占的存儲(chǔ)空間以及某種數(shù)據(jù)結(jié)構(gòu)所需要的附加存儲(chǔ)空間計(jì)算機(jī)二級(jí)概述基本數(shù)據(jù)結(jié)構(gòu)與算法

3、1.2 數(shù)據(jù)結(jié)構(gòu)(0.96%)數(shù)據(jù)結(jié)構(gòu)的定義數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)的圖形表示線性結(jié)構(gòu)與非線性結(jié)構(gòu)計(jì)算機(jī)二級(jí)概述基本數(shù)據(jù)結(jié)構(gòu)與算法 數(shù)據(jù)結(jié)構(gòu)是一門研究數(shù)據(jù)組織、存儲(chǔ)和運(yùn)算的一般方法的學(xué)科。1.2.2 基本概念和術(shù)語(yǔ)計(jì)算機(jī)二級(jí)概述基本數(shù)據(jù)結(jié)構(gòu)與算法能輸入到計(jì)算機(jī)中并能被計(jì)算機(jī)程序處理的符號(hào)的集合。整數(shù)(1,2)、實(shí)數(shù)(1.1,1.2)字符串(Beijing)、圖形、聲音。1.2.2 基本概念和術(shù)語(yǔ) 數(shù)據(jù)結(jié)構(gòu)是一門研究數(shù)據(jù)組織、存儲(chǔ)和運(yùn)算的一般方法的學(xué)科。計(jì)算機(jī)二級(jí)概述基本數(shù)據(jù)結(jié)構(gòu)與算法1.2.2 基本概念和術(shù)語(yǔ)計(jì)算機(jī)管理圖書(shū)問(wèn)題 在圖書(shū)館里有各種卡片：有按書(shū)名編排的、有按作者編排的、有按

4、分類編排如何將查詢圖書(shū)的這些信息存入計(jì)算機(jī)中既要考慮查詢時(shí)間短，又要考慮節(jié)省空間 數(shù)據(jù)結(jié)構(gòu)是一門研究數(shù)據(jù)組織、存儲(chǔ)和運(yùn)算的一般方法的學(xué)科。計(jì)算機(jī)二級(jí)概述基本數(shù)據(jù)結(jié)構(gòu)與算法最簡(jiǎn)單的辦法之一是建立一張表，每一本書(shū)的信息在表中占一行，如 1.2.2 基本概念和術(shù)語(yǔ) 數(shù)據(jù)結(jié)構(gòu)是一門研究數(shù)據(jù)組織、存儲(chǔ)和運(yùn)算的一般方法的學(xué)科。計(jì)算機(jī)二級(jí)概述基本數(shù)據(jù)結(jié)構(gòu)與算法如何將0,1,2,3,4,5,6,7,8,9這10個(gè)數(shù)存放在計(jì)算機(jī)中能最快地達(dá)到你所需要的目的？ 目的不同，最佳的存儲(chǔ)方方法就不同。 從大到小排列：9,8,7,6,5,4,3,2,1,0輸出偶數(shù)：0,2,4,6,8,1,3,5,7,9 數(shù)據(jù)元素在計(jì)算機(jī)

5、中的表示 數(shù)據(jù)結(jié)構(gòu)是一門研究數(shù)據(jù)組織、存儲(chǔ)和運(yùn)算的一般方法的學(xué)科。1.2.2 基本概念和術(shù)語(yǔ)計(jì)算機(jī)二級(jí)概述基本數(shù)據(jù)結(jié)構(gòu)與算法對(duì)數(shù)據(jù)結(jié)構(gòu)中的節(jié)點(diǎn)進(jìn)行操作處理(插入、刪除、修改、查找、排序)1.2.2 基本概念和術(shù)語(yǔ) 數(shù)據(jù)結(jié)構(gòu)是一門研究數(shù)據(jù)組織、存儲(chǔ)和運(yùn)算的一般方法的學(xué)科。計(jì)算機(jī)二級(jí)概述基本數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)元素(Data Element) 數(shù)據(jù)元素是數(shù)據(jù)的基本單位，即數(shù)據(jù)集合中的個(gè)體。 有時(shí)一個(gè)數(shù)據(jù)元素可由若干數(shù)據(jù)項(xiàng)(Data Item)組成。數(shù)據(jù)項(xiàng)是數(shù)據(jù)的最小單位。數(shù)據(jù)元素亦稱節(jié)點(diǎn)或記錄。計(jì)算機(jī)二級(jí)概述基本數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)可描述為 B=（D，R）有限個(gè)數(shù)據(jù)元素的集合有限個(gè)節(jié)點(diǎn)間關(guān)系的集合

6、計(jì)算機(jī)二級(jí)概述基本數(shù)據(jù)結(jié)構(gòu)與算法 1數(shù)據(jù)的邏輯結(jié)構(gòu) 2、數(shù)據(jù)的存儲(chǔ)（物理）結(jié)構(gòu) 3、數(shù)據(jù)的運(yùn)算：檢索、排序、插入、刪除、修改等。 A線性結(jié)構(gòu) B非線性結(jié)構(gòu)A 順序存儲(chǔ) B 鏈?zhǔn)酱鎯?chǔ) 線性表?xiàng)ｊ?duì)樹(shù)形結(jié)構(gòu)圖形結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)的三個(gè)方面 數(shù)據(jù)結(jié)構(gòu)可描述為 B=（D，R）計(jì)算機(jī)二級(jí)概述基本數(shù)據(jù)結(jié)構(gòu)與算法線性結(jié)構(gòu) A , B , C , ，X ,Y , Z學(xué) 生 成 績(jī) 表86胡孝臣95劉忠賞100張卓成績(jī)姓名學(xué)號(hào)線性表結(jié)點(diǎn)間是以線性關(guān)系聯(lián)結(jié)計(jì)算機(jī)二級(jí)概述基本數(shù)據(jù)結(jié)構(gòu)與算法 1數(shù)據(jù)的邏輯結(jié)構(gòu) 2、數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu) 3、數(shù)據(jù)的運(yùn)算：檢索、排序、插入、刪除、修改等。 A線性結(jié)構(gòu) B非線性結(jié)構(gòu)A 順序存儲(chǔ) B 鏈?zhǔn)?/p>

7、存儲(chǔ) 線性表?xiàng)ｊ?duì)樹(shù)形結(jié)構(gòu)圖形結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)的三個(gè)方面 數(shù)據(jù)結(jié)構(gòu)可描述為 B=（D，R）計(jì)算機(jī)二級(jí)概述基本數(shù)據(jù)結(jié)構(gòu)與算法樹(shù)形結(jié)構(gòu)全校學(xué)生檔案管理的組織方式計(jì)算機(jī)程序管理系統(tǒng)也是典型的樹(shù)形結(jié)構(gòu)計(jì)算機(jī)二級(jí)概述基本數(shù)據(jù)結(jié)構(gòu)與算法ABCDEFGH樹(shù)形結(jié)構(gòu) 結(jié)點(diǎn)間具有分層次的連接關(guān)系HBCDEFGA計(jì)算機(jī)二級(jí)概述基本數(shù)據(jù)結(jié)構(gòu)與算法 1數(shù)據(jù)的邏輯結(jié)構(gòu) 2、數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu) 3、數(shù)據(jù)的運(yùn)算：檢索、排序、插入、刪除、修改等。 A線性結(jié)構(gòu) B非線性結(jié)構(gòu)A 順序存儲(chǔ) B 鏈?zhǔn)酱鎯?chǔ) 線性表?xiàng)ｊ?duì)樹(shù)形結(jié)構(gòu)圖形結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)的三個(gè)方面 (亦稱物理結(jié)構(gòu))計(jì)算機(jī)二級(jí)概述基本數(shù)據(jù)結(jié)構(gòu)與算法1423 D= 1 , 2 , 3 , 4 R

8、=(1,2) , (1,3) , (1,4) , (2,3) (3,4) , (2,4) 213 D= 1 , 2 , 3 R= (1,2) , (2,3) , (3,2) , (1,3) 圖形結(jié)構(gòu)節(jié)點(diǎn)間的連結(jié)是任意的計(jì)算機(jī)二級(jí)概述基本數(shù)據(jù)結(jié)構(gòu)與算法 1數(shù)據(jù)的邏輯結(jié)構(gòu) 2、數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu) 3、數(shù)據(jù)的運(yùn)算：檢索、排序、插入、刪除、修改等。 A線性結(jié)構(gòu) B非線性結(jié)構(gòu)A 順序存儲(chǔ) B 鏈?zhǔn)酱鎯?chǔ) 線性表?xiàng)ｊ?duì)樹(shù)形結(jié)構(gòu)圖形結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)的三個(gè)方面 (亦稱物理結(jié)構(gòu))計(jì)算機(jī)二級(jí)概述基本數(shù)據(jù)結(jié)構(gòu)與算法元素n.元素i.元素2元素1LoLo+mLo+(i-1)*mLo+（n-1)*m存儲(chǔ)地址存儲(chǔ)內(nèi)容Loc(a)=Lo

9、+（i-1)*m順序存儲(chǔ)每個(gè)元素所占用的存儲(chǔ)單元個(gè)數(shù)計(jì)算機(jī)二級(jí)概述基本數(shù)據(jù)結(jié)構(gòu)與算法元素n.元素i.元素2元素1存儲(chǔ)內(nèi)容順序存儲(chǔ)結(jié)構(gòu)常用于線性數(shù)據(jù)結(jié)構(gòu)，將邏輯上相鄰的數(shù)據(jù)元素存儲(chǔ)在物理上相鄰的存儲(chǔ)單元里。順序存儲(chǔ)結(jié)構(gòu)的三個(gè)弱點(diǎn)：1.作插入或刪除操作時(shí)，需移動(dòng)大量元數(shù)。2.長(zhǎng)度變化較大時(shí)，需按最大空間分配。3.表的容量難以擴(kuò)充。計(jì)算機(jī)二級(jí)概述基本數(shù)據(jù)結(jié)構(gòu)與算法 1數(shù)據(jù)的邏輯結(jié)構(gòu) 2、數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu) 3、數(shù)據(jù)的運(yùn)算：檢索、排序、插入、刪除、修改等。 A線性結(jié)構(gòu) B非線性結(jié)構(gòu)A 順序存儲(chǔ) B 鏈?zhǔn)酱鎯?chǔ) 線性表?xiàng)ｊ?duì)樹(shù)形結(jié)構(gòu)圖形結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)的三個(gè)方面 (亦稱物理結(jié)構(gòu))計(jì)算機(jī)二級(jí)概述基本數(shù)據(jù)結(jié)構(gòu)與算法15

10、36元素21400元素11346元素3 元素41345h 鏈?zhǔn)酱鎯?chǔ) 每個(gè)節(jié)點(diǎn)都由兩部分組成：數(shù)據(jù)域和指針域。數(shù)據(jù)域存放元素本身的數(shù)據(jù)，指針域存放指針。數(shù)據(jù)元素之間邏輯上的聯(lián)系由指針來(lái)體現(xiàn)。計(jì)算機(jī)二級(jí)概述基本數(shù)據(jù)結(jié)構(gòu)與算法1536元素21400元素11346元素3 元素4head 1346 元素3 1536 . . . 1536 元素2 1400 . . . 元素4 1346 1400 元素1 1345 指針 存儲(chǔ)內(nèi)容存儲(chǔ)地址 鏈?zhǔn)酱鎯?chǔ) 1345計(jì)算機(jī)二級(jí)概述基本數(shù)據(jù)結(jié)構(gòu)與算法1536元素21400元素11346元素3 元素41345h 鏈?zhǔn)酱鎯?chǔ) 1.比順序存儲(chǔ)結(jié)構(gòu)的存儲(chǔ)密度小 (每個(gè)節(jié)點(diǎn)都由數(shù)

11、據(jù)域和指針愈組成)。2.邏輯上相鄰的節(jié)點(diǎn)物理上不必相鄰。3.插入、刪除靈活 (不必移動(dòng)節(jié)點(diǎn)，只要改變節(jié)點(diǎn)中的指針)。鏈接存儲(chǔ)結(jié)構(gòu)特點(diǎn)：計(jì)算機(jī)二級(jí)概述基本數(shù)據(jù)結(jié)構(gòu)與算法 1數(shù)據(jù)的邏輯結(jié)構(gòu) 2、數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu) 3、數(shù)據(jù)的運(yùn)算：檢索、排序、插入、刪除、修改等。 A線性結(jié)構(gòu) B非線性結(jié)構(gòu)A 順序存儲(chǔ) B 鏈?zhǔn)酱鎯?chǔ) 線性表?xiàng)ｊ?duì)樹(shù)形結(jié)構(gòu)圖形結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)的三個(gè)方面 (亦稱物理結(jié)構(gòu))計(jì)算機(jī)二級(jí)概述基本數(shù)據(jù)結(jié)構(gòu)與算法 線性結(jié)構(gòu)和非線性結(jié)構(gòu)如果一個(gè)非空的數(shù)據(jù)結(jié)構(gòu)滿足下列兩個(gè)條件：有且只有一個(gè)根結(jié)點(diǎn)；每一個(gè)結(jié)點(diǎn)最多有一個(gè)前件，也最多有一個(gè)后件則稱該數(shù)據(jù)結(jié)構(gòu)為線性結(jié)構(gòu)（又稱為線性表）。一個(gè)線性結(jié)構(gòu)中插入或刪除任何一個(gè)

12、節(jié)點(diǎn)后還應(yīng)是線性結(jié)構(gòu)。如果一個(gè)數(shù)據(jù)結(jié)構(gòu)不是線性結(jié)構(gòu)，則稱之為非線性結(jié)構(gòu)。線性與非線性結(jié)構(gòu)都可以是空的數(shù)據(jù)結(jié)構(gòu)。計(jì)算機(jī)二級(jí)概述基本數(shù)據(jù)結(jié)構(gòu)與算法1.3 線性表(0.24%)1.3.1 線性表的定義 線性表是n個(gè)元素的有限序列，它們之間的關(guān)系可以排成一個(gè)線性序列： a1，a2， ，ai， ，an其中n稱作表的長(zhǎng)度，當(dāng)n=0時(shí)，稱作空表。計(jì)算機(jī)二級(jí)概述基本數(shù)據(jù)結(jié)構(gòu)與算法線性表的特點(diǎn)：1.線性表中所有元素的性質(zhì)相同。2.除第一個(gè)和最后一個(gè)數(shù)據(jù)元素之外，其它數(shù)據(jù)元素有且僅有一個(gè)前驅(qū)和一個(gè)后繼。第一個(gè)數(shù)據(jù)元素?zé)o前驅(qū)，最后一個(gè)數(shù)據(jù)元素?zé)o后繼。3.數(shù)據(jù)元素在表中的位置只取決于它自身的序號(hào)。在線性表上常用的運(yùn)算

13、有：初始化、求長(zhǎng)度、取元素、修改、插入、刪除、檢索、排序。計(jì)算機(jī)二級(jí)概述基本數(shù)據(jù)結(jié)構(gòu)與算法1.3.2 線性表的順序存儲(chǔ)結(jié)構(gòu)及其插入與刪除操作特點(diǎn)： 1、線性表中數(shù)據(jù)元素類型一致，只有數(shù)據(jù)域，存儲(chǔ)空間利用率高。 2、所有元素所占的存儲(chǔ)空間是連續(xù)的 3、各數(shù)據(jù)元素在存儲(chǔ)空間中是按邏輯順序依次存放的 2. 做插入、刪除時(shí)需移動(dòng)大量元素。 3. 空間估計(jì)不明時(shí)，按最大空間分配。計(jì)算機(jī)二級(jí)概述基本數(shù)據(jù)結(jié)構(gòu)與算法元素an.元素ai.元素a2元素a1bb+mb+(i-1)*m b+(maxlen-1)*m存儲(chǔ)地址內(nèi)存狀態(tài)Loc(元素i)=b +（i-1)*m順序存儲(chǔ)結(jié)構(gòu)示意圖(順序表)：首地址起始地址基地址

14、每個(gè)元素所占用的存儲(chǔ)單元個(gè)數(shù)計(jì)算機(jī)二級(jí)概述基本數(shù)據(jù)結(jié)構(gòu)與算法.a2a1an.ai+1ai01i-1in-1 1- 1插入運(yùn)算ai-1.a2a1alength ai+1ai x ai-1. a2 a1 ai ai+1 alength alength ai+1 ai x計(jì)算機(jī)二級(jí)概述基本數(shù)據(jù)結(jié)構(gòu)與算法 插入算法的分析 假設(shè)線性表中含有n個(gè)數(shù)據(jù)元素，在進(jìn)行插入操作時(shí)，若假定在n+1個(gè)位置上插入元素的可能性均等，則平均移動(dòng)元素的個(gè)數(shù)為：計(jì)算機(jī)二級(jí)概述基本數(shù)據(jù)結(jié)構(gòu)與算法 刪除算法的分析 在進(jìn)行刪除操作時(shí)，若假定刪除每個(gè)元素的可能性均等，則平均移動(dòng)元素的個(gè)數(shù)為： 分析結(jié)論 順序存儲(chǔ)結(jié)構(gòu)表示的線性表，在做插

15、入或刪除操作時(shí)，平均需要移動(dòng)大約一半的數(shù)據(jù)元素。當(dāng)線性表的數(shù)據(jù)元素量較大，并且經(jīng)常要對(duì)其做插入或刪除操作時(shí)，這一點(diǎn)需要值得考慮。計(jì)算機(jī)二級(jí)概述基本數(shù)據(jù)結(jié)構(gòu)與算法1.4 棧和隊(duì)列(3.47%)1.4.1 棧和隊(duì)列的定義 棧和隊(duì)列是兩種特殊的線性表，它們是運(yùn)算時(shí)要受到某些限制的線性表，故也稱為限定性的數(shù)據(jù)結(jié)構(gòu)。計(jì)算機(jī)二級(jí)概述基本數(shù)據(jù)結(jié)構(gòu)與算法棧的定義棧：限定只能在表的一端進(jìn)行插入和刪除的特殊的線性表,此種結(jié)構(gòu)稱為后進(jìn)先出設(shè)棧s=（a1，a2，. . . ,ai，. . . ，an），其中a1是棧底元素， an是棧頂元素。棧頂（top)：允許插入和刪除的一端； 約定top始終指向新數(shù)據(jù)元素將存放的位

16、置。棧底（bottom):不允許插入和刪除的一端。 a1 a2 . an進(jìn)棧出棧棧頂棧底計(jì)算機(jī)二級(jí)概述基本數(shù)據(jù)結(jié)構(gòu)與算法隊(duì)列的主要運(yùn)算（1）設(shè)置一個(gè)空隊(duì)列；（2）插入一個(gè)新的隊(duì)尾元素，稱為進(jìn)隊(duì)；（3）刪除隊(duì)頭元素，稱為出隊(duì)；（4）讀取隊(duì)頭元素；1.4.1.2 隊(duì)列的定義定義：一種特殊的線性結(jié)構(gòu)，限定只能在表的一端進(jìn)行插入，在表的另一端進(jìn)行刪除的線性表 。此種結(jié)構(gòu)稱為先進(jìn)先出（FIFO）表。 a1 , a2 , a3 , a4 , an-1 , an 隊(duì) 列 示 意 圖隊(duì)頭隊(duì)尾計(jì)算機(jī)二級(jí)概述基本數(shù)據(jù)結(jié)構(gòu)與算法1.4.2 棧的順序存儲(chǔ)結(jié)構(gòu)及其基本運(yùn)算 a2 a1 a1 a2 top 用順序存儲(chǔ)結(jié)構(gòu)

17、表示的棧。 順序棧用一組連續(xù)的存儲(chǔ)單元存放自棧底到棧頂?shù)臄?shù)據(jù)元素，一般用一維數(shù)組表示，設(shè)置一個(gè)簡(jiǎn)單變量top指示棧頂位置，稱為棧頂指針，它始終指向待插入元素的位置?；具\(yùn)算：壓（進(jìn)）棧：PUSH出棧：POP計(jì)算機(jī)二級(jí)概述基本數(shù)據(jù)結(jié)構(gòu)與算法 3 2 1 0 (a)rear=front=-1(隊(duì)空） e3 e4 (c)e1,e2出隊(duì)，e4入隊(duì) 隊(duì) 滿rearfront e1 e2 e3 (b)rearfront(b)e1,e2,e3入隊(duì)隊(duì)空時(shí)， 令rear=front=-1，當(dāng)有新元素入隊(duì)時(shí)，尾指針加1，當(dāng)有元素出隊(duì)時(shí)，頭指針加1。故在非空隊(duì)列中，頭指針始終指向隊(duì)頭元素前一個(gè)位置，而尾指針始終指向

18、隊(duì)尾元素的位置1.4.3 隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)及其基本運(yùn)算計(jì)算機(jī)二級(jí)概述基本數(shù)據(jù)結(jié)構(gòu)與算法1.5 線性鏈表（線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)） (0.24%)線性鏈表循環(huán)鏈表結(jié)構(gòu)及其基本運(yùn)算計(jì)算機(jī)二級(jí)概述基本數(shù)據(jù)結(jié)構(gòu)與算法1.5.1 線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 將線性表的元素放到一個(gè)具有頭指針的鏈表中，鏈表中每個(gè)結(jié)點(diǎn)包含數(shù)據(jù)域和指針域。 數(shù)據(jù)域存放數(shù)據(jù)，指針域存放后繼結(jié)點(diǎn)的地址，最后一個(gè)結(jié)點(diǎn)的指針域?yàn)榭?。邏輯上相鄰的?shù)據(jù)元素在內(nèi)存中的物理存儲(chǔ)空間不一定相鄰。計(jì)算機(jī)二級(jí)概述基本數(shù)據(jù)結(jié)構(gòu)與算法上圖的線性表為ZHAO，QIAN，SUN，LI，ZHOU，WU，ZHENG，WANG計(jì)算機(jī)二級(jí)概述基本數(shù)據(jù)結(jié)構(gòu)與算法線性鏈表表

19、示法:計(jì)算機(jī)二級(jí)概述基本數(shù)據(jù)結(jié)構(gòu)與算法鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的特點(diǎn) 插入、刪除靈活方便，不需要移動(dòng)結(jié)點(diǎn)，只要改變結(jié)點(diǎn)中指針域的值即可。 適合于線性表是動(dòng)態(tài)變化的,不進(jìn)行頻繁查找操作、但經(jīng)常進(jìn)行插入刪除時(shí)使用。 鏈表的查找只能從頭指針開(kāi)始順序查找。 計(jì)算機(jī)二級(jí)概述基本數(shù)據(jù)結(jié)構(gòu)與算法1.5.2 循環(huán)鏈表: 首尾相接的鏈表。 將最后一個(gè)結(jié)點(diǎn)的空指針改為指向頭結(jié)點(diǎn)，從任一結(jié)點(diǎn)出發(fā)均可找到其它結(jié)點(diǎn)。a1a2ana3L.帶頭結(jié)點(diǎn)的單鏈表a1a2ana3L.循環(huán)單鏈表計(jì)算機(jī)二級(jí)概述基本數(shù)據(jù)結(jié)構(gòu)與算法1.5.3 雙向鏈表 在每個(gè)結(jié)點(diǎn)中設(shè)置兩個(gè)指針，一個(gè)指向后繼，一個(gè)指向前驅(qū)?？芍苯哟_定一個(gè)結(jié)點(diǎn)的前驅(qū)和后繼結(jié)點(diǎn)。可提高效

20、率。datanextbefore計(jì)算機(jī)二級(jí)概述基本數(shù)據(jù)結(jié)構(gòu)與算法1.6 樹(shù)與二叉樹(shù)(2.93%)樹(shù)的基本概念二叉樹(shù)的定義及其存儲(chǔ)結(jié)構(gòu)二叉樹(shù)的前序、中序和后序遍歷計(jì)算機(jī)二級(jí)概述基本數(shù)據(jù)結(jié)構(gòu)與算法1.6.1 樹(shù)的定義 由一個(gè)或多個(gè)結(jié)點(diǎn)組成的有限集合。僅有一個(gè)根結(jié)點(diǎn)，結(jié)點(diǎn)間有明顯的層次結(jié)構(gòu)關(guān)系。 A C G T2D H I T3J M B E L KT1 F現(xiàn)實(shí)世界中，能用樹(shù)的結(jié)構(gòu)表示的例子：學(xué)校的行政關(guān)系、書(shū)的層次結(jié)構(gòu)、人類的家族血緣關(guān)系等。計(jì)算機(jī)二級(jí)概述基本數(shù)據(jù)結(jié)構(gòu)與算法介紹幾個(gè)概念：結(jié)點(diǎn)（Node）：樹(shù)中的元素，包含數(shù)據(jù)項(xiàng)及若干指向其子樹(shù)的分支。結(jié)點(diǎn)的度（Degree）：結(jié)點(diǎn)擁有的子樹(shù)數(shù)。結(jié)點(diǎn)

21、的層次：從根結(jié)點(diǎn)開(kāi)始算起，根為第一層。葉子（Leaf）：度為零的結(jié)點(diǎn)，也稱端結(jié)點(diǎn)。孩子（Child）：結(jié)點(diǎn)子樹(shù)的根稱為該結(jié)點(diǎn)的孩子結(jié)點(diǎn)。兄弟（Sibling）：同一雙親的孩子。雙親（Parent）：孩子結(jié)點(diǎn)的上層結(jié)點(diǎn)，稱為這些結(jié)點(diǎn)的雙親。深度（Depth)： 樹(shù)中結(jié)點(diǎn)的最大層次數(shù)。森林（Forest）：M棵互不相交的樹(shù)的集合。 A C G T2D H I T3J M B E L KT1 F計(jì)算機(jī)二級(jí)概述基本數(shù)據(jù)結(jié)構(gòu)與算法1.6.2 二叉樹(shù) （Binary Tree）1 、二叉樹(shù)的定義及其性質(zhì) (1) 二叉樹(shù)的定義二叉樹(shù)的五種基本形態(tài)二叉樹(shù)一種特殊的樹(shù)型結(jié)構(gòu)，特點(diǎn)是樹(shù)中每個(gè)結(jié)點(diǎn)只有兩棵子樹(shù)，且子

22、樹(shù)有左右之分，次序不能顛倒。 空二叉樹(shù) 僅有根結(jié)點(diǎn) 右子樹(shù)為空 左子樹(shù)為空左右子樹(shù)均非空因?yàn)闃?shù)的每個(gè)結(jié)點(diǎn)的度不同，存儲(chǔ)困難，使對(duì)樹(shù)的處理算法很復(fù)雜。所以引出二叉樹(shù)的討論。計(jì)算機(jī)二級(jí)概述基本數(shù)據(jù)結(jié)構(gòu)與算法 二叉數(shù)是n(n0)個(gè)結(jié)點(diǎn)的有限集合。它或?yàn)榭諗?shù)(n=0),或由一個(gè)根結(jié)點(diǎn)和兩棵分別稱為根的左子樹(shù)和右子樹(shù)的互不相交的二叉數(shù)組成。 特別要注意：二叉數(shù)不是樹(shù)的特殊情況。aabb兩棵不同的二叉數(shù)計(jì)算機(jī)二級(jí)概述基本數(shù)據(jù)結(jié)構(gòu)與算法A、 二叉樹(shù)的第i層上至多有2 i-1（i 1）個(gè)結(jié)點(diǎn)。(2) 二叉樹(shù)的基本性質(zhì)423167891011121314155第三層上(i=3)，有23-1=4個(gè)節(jié)點(diǎn)。第四層上(

23、i=4)，有24-1=8個(gè)節(jié)點(diǎn)。計(jì)算機(jī)二級(jí)概述基本數(shù)據(jù)結(jié)構(gòu)與算法A、 二叉樹(shù)的第i層上至多有2 i-1（i 1）個(gè)結(jié)點(diǎn)。 B、 深度為h的二叉樹(shù)中至多含有2h-1個(gè)結(jié)點(diǎn)。(2) 二叉樹(shù)的基本性質(zhì)423167891011121314155此樹(shù)的深度h=4，共有24-1=15個(gè)節(jié)點(diǎn)。計(jì)算機(jī)二級(jí)概述基本數(shù)據(jù)結(jié)構(gòu)與算法A、 二叉樹(shù)的第i層上至多有2 i-1（i 1）個(gè)結(jié)點(diǎn)。B、 深度為h的二叉樹(shù)中至多含有2h-1個(gè)結(jié)點(diǎn)。C、 若在任意一棵二叉樹(shù)中，有n0個(gè)葉子結(jié)點(diǎn)， 有n2個(gè)度為2的結(jié)點(diǎn)，則：n0=n2+1(2) 二叉樹(shù)的基本性質(zhì)423167891011121314155n0=8n2=7計(jì)算機(jī)二級(jí)概述

24、基本數(shù)據(jù)結(jié)構(gòu)與算法（3）滿二叉樹(shù)423167891011121314155特點(diǎn)：每一層上都含有最大結(jié)點(diǎn)數(shù)。計(jì)算機(jī)二級(jí)概述基本數(shù)據(jù)結(jié)構(gòu)與算法4231678910 11125 非完全二叉樹(shù)（4）完全二叉樹(shù)4231678910 11125 完全二叉樹(shù)特點(diǎn)：除最后一層外，每一層都取最大結(jié)點(diǎn)數(shù)，最后一層結(jié)點(diǎn)都集中在該層最左邊的若干位置。計(jì)算機(jī)二級(jí)概述基本數(shù)據(jù)結(jié)構(gòu)與算法（5）樹(shù)與二叉樹(shù)的區(qū)別A樹(shù)的結(jié)點(diǎn)個(gè)數(shù)至少為1，而二叉樹(shù)的結(jié)點(diǎn)個(gè)數(shù)可以為0。B樹(shù)中結(jié)點(diǎn)的最大度數(shù)沒(méi)有限制，二叉樹(shù)結(jié)點(diǎn)最大度數(shù)為2。C樹(shù)的結(jié)點(diǎn)無(wú)左、右之分，二叉樹(shù)的結(jié)點(diǎn)子樹(shù)有明確的左、右之分。 樹(shù) 二叉樹(shù)計(jì)算機(jī)二級(jí)概述基本數(shù)據(jù)結(jié)構(gòu)與算法1.6.

25、3 二叉樹(shù)的遍歷 查找某個(gè)結(jié)點(diǎn)，或?qū)Χ鏄?shù)中全部結(jié)點(diǎn)進(jìn)行某種處理，就需要遍歷。（1）遍歷定義及遍歷算法 遍歷是指按某條搜索路線尋訪樹(shù)中每個(gè)結(jié)點(diǎn)，且每個(gè)結(jié)點(diǎn)只被訪問(wèn)一次。 按先左后右的原則，一般使用三種遍歷：先序遍歷(D L R): 訪問(wèn)根結(jié)點(diǎn)，按先序遍歷左子樹(shù)，按先序遍歷右子樹(shù)。中序遍歷(L D R): 按中序遍歷左子樹(shù)，訪問(wèn)根結(jié)點(diǎn)，按中序遍歷右子樹(shù)。后序遍歷(L R D): 按后序遍歷左子樹(shù)，按后序遍歷右子樹(shù)，訪問(wèn)根結(jié)點(diǎn)。 二叉樹(shù)為空時(shí)，執(zhí)行空操作，即空二叉樹(shù)已遍歷完。計(jì)算機(jī)二級(jí)概述基本數(shù)據(jù)結(jié)構(gòu)與算法 （2）遍歷算法先序遍歷：D L R中序遍歷：L D R后序遍歷：L R DADBCT1T2

26、T3D L RAD L RD L RBDCD L R以先序遍歷D L R為例演示遍歷過(guò)程 ABDCBDAC DBCA計(jì)算機(jī)二級(jí)概述基本數(shù)據(jù)結(jié)構(gòu)與算法1.7 查找和排序順序查找與二分查找算法基本排序算法（交換類排序、選擇類排序、插入類排序）計(jì)算機(jī)二級(jí)概述基本數(shù)據(jù)結(jié)構(gòu)與算法1.7.1 查找(0.89%)查找是在一個(gè)給定的數(shù)據(jù)結(jié)構(gòu)中，根據(jù)給定的條件查找滿足條件的結(jié)點(diǎn)。不同的數(shù)據(jù)結(jié)構(gòu)采用不同的查找方法。查找的效率直接影響數(shù)據(jù)處理的效率。查找的結(jié)果：查找成功：找到滿足條件的結(jié)點(diǎn)查找失?。赫也坏綕M足條件的結(jié)點(diǎn)。計(jì)算機(jī)二級(jí)概述基本數(shù)據(jù)結(jié)構(gòu)與算法1.7.1.1 順序查找（線性查找）查找過(guò)程： 對(duì)給定的一關(guān)鍵字

27、K，從線性表的一端開(kāi)始，逐個(gè)進(jìn)行記錄的關(guān)鍵字和K的比較，直到找到關(guān)鍵字等于K的記錄或到達(dá)表的另一端。可以采用從前向后查，也可采用從后向前查的方法。 在平均情況下，大約要與表中一半以上元素進(jìn)行比較，效率較低。平均查找長(zhǎng)度較大。 在下面兩種情況下只能采取順序查找： a. 線性表為無(wú)序表（元素排列是無(wú)序的）； b. 即使是有序線性表，但采用的是鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。最壞比較n次。計(jì)算機(jī)二級(jí)概述基本數(shù)據(jù)結(jié)構(gòu)與算法2.7.1.2 折半查找（二分法查找）思想：先確定待查找記錄所在的范圍，然后逐步縮小范圍，直到找到或確認(rèn)找不到該記錄為止。前提：必須在具有順序存儲(chǔ)結(jié)構(gòu)的有序表中進(jìn)行。分三種情況：1）若中間項(xiàng)的值等于x

28、,則說(shuō)明已查到。2）若x小于中間項(xiàng)的值，則在線性表的前半部分查找；3）若x大于中間項(xiàng)的值，則在線性表的后半部分查找。特點(diǎn)：比順序查找方法效率高。最壞的情況下，需要比較 log2n次。計(jì)算機(jī)二級(jí)概述基本數(shù)據(jù)結(jié)構(gòu)與算法查找23和79的過(guò)程如下圖：mid=(low+high)/2不進(jìn)位取整( 08, 14, 23, 37, 46, 55, 68, 79, 91 )( 08, 14, 23, 37, 46, 55, 68, 79, 91 )lowhighmid( 08, 14, 23, 37, 46, 55, 68, 79, 91 )lowhigh=mid-1mid( 08, 14, 23, 37,

29、46, 55, 68, 79, 91 )low=mid+1highmid( 08, 14, 23, 37, 46, 55, 68, 79, 91 )lowhighmid( 08, 14, 23, 37, 46, 55, 68, 79, 91 )lowhighmid( 08, 14, 23, 37, 46, 55, 68, 79, 91 )lowhighmid計(jì)算機(jī)二級(jí)概述基本數(shù)據(jù)結(jié)構(gòu)與算法1.7.2 排序(0.6%)1.7.2.1 概述1、排序的功能：將一個(gè)數(shù)據(jù)元素（或記錄）的任意序列，重新排成一個(gè)按關(guān)鍵字有序的序列。2、排序過(guò)程的組成步驟： 首先比較兩個(gè)關(guān)鍵字的大??； 然后將記錄從一個(gè)位置移

30、動(dòng)到另一個(gè)位置。計(jì)算機(jī)二級(jí)概述基本數(shù)據(jù)結(jié)構(gòu)與算法排序方法插入排序選擇排序交換排序簡(jiǎn)單插入排序希爾排序簡(jiǎn)單選擇排序堆排序冒泡排序快速排序計(jì)算機(jī)二級(jí)概述基本數(shù)據(jù)結(jié)構(gòu)與算法1.7.2.2 插入排序 簡(jiǎn)單插入、希爾1、簡(jiǎn)單插入排序: 基本思想：從數(shù)組的第2號(hào)元素開(kāi)始，順序從數(shù)組中取出元素，并將該元素插入到其左端已排好序的數(shù)組的適當(dāng)位置上。 最壞情況需要n(n-1)/2次比較計(jì)算機(jī)二級(jí)概述基本數(shù)據(jù)結(jié)構(gòu)與算法該算法適合于n 較小的情況，時(shí)間復(fù)雜度為O(n2).待排元素序列：53 27 36 15 69 42第一次排序： 27 53 36 15 69 42第二次排序： 27 36 53 15 69 42第三

31、次排序： 15 27 36 53 69 42第四次排序： 15 27 36 53 69 42第五次排序： 15 27 36 42 53 69 直接插入排序示例對(duì)于有n個(gè)數(shù)據(jù)元素的待排序列，插入操作要進(jìn)行n-1次計(jì)算機(jī)二級(jí)概述基本數(shù)據(jù)結(jié)構(gòu)與算法2、希爾排序書(shū)43頁(yè)圖比較次數(shù)為O(n1.5) 計(jì)算機(jī)二級(jí)概述基本數(shù)據(jù)結(jié)構(gòu)與算法 1、簡(jiǎn)單選擇排序 思想：首先從1n個(gè)元素中選出關(guān)鍵字最小的記錄交換到第一個(gè)位置上。然后再?gòu)牡? 個(gè)到第n個(gè)元素中選出次小的記錄交換到第二個(gè)位置上，依次類推。 時(shí)間復(fù)雜度為O(n2)，最壞情況下需要比較 n(n-1)/2次 適用于待排序元素較少的情況。1.7.2.3 選擇排序 簡(jiǎn)單選擇排序、堆排序計(jì)算機(jī)二級(jí)概述基本數(shù)據(jù)結(jié)構(gòu)與算法初態(tài)8 3 9 1 6 8 3 9 1 6 8 3 9 1 6 8 3 9 1 6 ijkijkijkijk1 3 9 8 6 互換ijk1 3 9 8 6 ikj1 3 9 8 6 ikj第一趟第二趟1 3 9 8 6 ikj第三趟計(jì)算機(jī)二級(jí)概述基本數(shù)據(jù)結(jié)構(gòu)與算法2堆排序也是一種選擇排序。是具有特定條件的順序存儲(chǔ)的完全二叉樹(shù)，其特定