數(shù)據(jù)結(jié)構(gòu)2016h

1、數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)題型題型(1)p基本概念基本概念40n選擇2x15n判斷1x10p簡答簡答10 x3=30p給定數(shù)據(jù)實(shí)例，運(yùn)行相關(guān)算法，得出結(jié)果，分析效率，例如p霍夫曼編碼霍夫曼編碼p快速快速/ /堆排序算法堆排序算法p三種哈希算法的實(shí)例運(yùn)行三種哈希算法的實(shí)例運(yùn)行p根據(jù)根據(jù)二叉樹遍歷結(jié)果畫出樹（前序中序求后序等）二叉樹遍歷結(jié)果畫出樹（前序中序求后序等）p二叉樹和森林的轉(zhuǎn)換二叉樹和森林的轉(zhuǎn)換p拓?fù)渫負(fù)渑判蚺判蝾}型題型(2)p算法設(shè)計(jì)題算法設(shè)計(jì)題10 x3=30n常見題型p遍歷一維數(shù)組，兩位數(shù)組：查找或轉(zhuǎn)置遍歷一維數(shù)組，兩位數(shù)組：查找或轉(zhuǎn)置p鏈表操作（轉(zhuǎn)置鏈表操作（轉(zhuǎn)置/ /合并合并/ /拆分）拆

2、分）p二叉樹（復(fù)制，相等二叉樹（復(fù)制，相等，求高度，求高度, ,求子孫數(shù)。使用求子孫數(shù)。使用簡單遞歸算簡單遞歸算法）法）第一章第一章 緒論緒論學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的意義學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的意義p是為研究和解決如何有效地組織和處理是為研究和解決如何有效地組織和處理非數(shù)值數(shù)據(jù)非數(shù)值數(shù)據(jù)而而產(chǎn)生的理論、技術(shù)和方法。產(chǎn)生的理論、技術(shù)和方法。p是計(jì)算機(jī)科學(xué)中的一門綜合性的專業(yè)基礎(chǔ)課。是計(jì)算機(jī)科學(xué)中的一門綜合性的專業(yè)基礎(chǔ)課。 涉及計(jì)算機(jī)軟件、硬件以及數(shù)學(xué)等涉及計(jì)算機(jī)軟件、硬件以及數(shù)學(xué)等基本術(shù)語基本術(shù)語p數(shù)據(jù)數(shù)據(jù) 被計(jì)算機(jī)加工處理的對象。p數(shù)據(jù)元素?cái)?shù)據(jù)元素（記錄記錄、表目表目） 數(shù)據(jù)的基本單位，是數(shù)據(jù)集合中的一個(gè)有意義的

3、個(gè)體。p數(shù)據(jù)項(xiàng)數(shù)據(jù)項(xiàng) 一個(gè)數(shù)據(jù)元素可由若干個(gè)數(shù)據(jù)項(xiàng)數(shù)據(jù)項(xiàng)組成。 組合項(xiàng)組合項(xiàng)年 月 日學(xué) 號姓 名班 號性別出生日期入學(xué)成績原子項(xiàng)原子項(xiàng)基本基本術(shù)語術(shù)語2 2p數(shù)據(jù)對象數(shù)據(jù)對象 是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個(gè)子集。 學(xué)號 姓名 班號 性別 出生日期 入學(xué)成績 001 劉影 01 女 19840417 623 002 李恒 01 男 19831211 679 003 陳誠 02 男 19840910 638 p數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 具有結(jié)構(gòu)的數(shù)據(jù)元素的集合。它包括數(shù)據(jù)元素的邏輯結(jié)構(gòu)邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)（物理結(jié)構(gòu)）存儲(chǔ)結(jié)構(gòu)（物理結(jié)構(gòu)）和相適應(yīng)的運(yùn)算運(yùn)算。數(shù)據(jù)元素（以班級學(xué)生關(guān)系為例）(1)集合

4、結(jié)構(gòu)集合結(jié)構(gòu) 數(shù)據(jù)元素除了“屬于同一集合”的聯(lián)系之外，沒有其它的關(guān)系。(2)線性結(jié)構(gòu)線性結(jié)構(gòu) 數(shù)據(jù)元素之間存在一對一的關(guān)系。(3)樹型結(jié)構(gòu)樹型結(jié)構(gòu) 數(shù)據(jù)元素之間存在一對多的關(guān)系。(4)圖狀結(jié)構(gòu)圖狀結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu)網(wǎng)狀結(jié)構(gòu) 數(shù)據(jù)元素之間存在多對多的關(guān)系。成員關(guān)系長幼關(guān)系管理關(guān)系朋友關(guān)系四種基本的邏輯結(jié)構(gòu)四種基本的邏輯結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)：數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)中如何表示。p數(shù)據(jù)元素的映象數(shù)據(jù)元素的映象 用二進(jìn)制位(bit)的位串表示數(shù)據(jù)元素。 每個(gè)數(shù)據(jù)元素的映象稱為每個(gè)數(shù)據(jù)元素的映象稱為結(jié)點(diǎn)結(jié)點(diǎn) 每個(gè)數(shù)據(jù)項(xiàng)的映象稱為每個(gè)數(shù)據(jù)項(xiàng)的映象稱為數(shù)據(jù)域數(shù)據(jù)域p關(guān)系的映象關(guān)系的映象

5、兩種基本方法及其組合使用。兩種基本方法及其組合使用。n順序映象順序映象：以相對的存儲(chǔ)位置表示關(guān)系以相對的存儲(chǔ)位置表示關(guān)系n鏈?zhǔn)接诚箧準(zhǔn)接诚螅阂愿郊有畔ⅲ阂愿郊有畔? (指針指針) )表示關(guān)系表示關(guān)系p注意：數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)的關(guān)系n可以用數(shù)組等線形存儲(chǔ)的方式存儲(chǔ)邏輯上的樹形結(jié)構(gòu)可以用數(shù)組等線形存儲(chǔ)的方式存儲(chǔ)邏輯上的樹形結(jié)構(gòu)n也可以用樹狀的復(fù)雜的存儲(chǔ)結(jié)構(gòu)來存儲(chǔ)邏輯上的集合關(guān)系以達(dá)也可以用樹狀的復(fù)雜的存儲(chǔ)結(jié)構(gòu)來存儲(chǔ)邏輯上的集合關(guān)系以達(dá)到提高檢索速度的目的到提高檢索速度的目的數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu) 數(shù)據(jù)的邏輯結(jié)構(gòu)+運(yùn)算的定義-面向用戶，需求分析 （抽象數(shù)據(jù)類型） 概念層 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)+

6、運(yùn)算的實(shí)現(xiàn)-面向計(jì)算機(jī) 實(shí)現(xiàn)層數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)算法和算法分析算法和算法分析p正確性（最重要的標(biāo)準(zhǔn)）n算法應(yīng)滿足具體問題的需求算法應(yīng)滿足具體問題的需求n對于典型的、苛刻而帶有刁難性的一組對于典型的、苛刻而帶有刁難性的一組有效輸入有效輸入得到正確的得到正確的結(jié)果結(jié)果p健壯性（魯棒性）n算法應(yīng)具有容錯(cuò)處理。當(dāng)輸入算法應(yīng)具有容錯(cuò)處理。當(dāng)輸入非法數(shù)據(jù)非法數(shù)據(jù)時(shí)，算法應(yīng)對其作出時(shí)，算法應(yīng)對其作出反應(yīng)，而不是產(chǎn)生莫名其妙或隨機(jī)的輸出結(jié)果反應(yīng)，而不是產(chǎn)生莫名其妙或隨機(jī)的輸出結(jié)果p可讀性n算法應(yīng)該好讀。以有利于閱讀者對程序的理解和維護(hù)算法應(yīng)該好讀。以有利于閱讀者對程序的理解和維護(hù)

7、p高效性：時(shí)間復(fù)雜度n算法執(zhí)行占用的算法執(zhí)行占用的CPU時(shí)間，隨問題規(guī)模時(shí)間，隨問題規(guī)模n的變化函數(shù)的變化函數(shù)p高效性：空間復(fù)雜度n算法執(zhí)行占用的內(nèi)存總量，隨問題規(guī)模算法執(zhí)行占用的內(nèi)存總量，隨問題規(guī)模n的變化函數(shù)的變化函數(shù)評價(jià)算法優(yōu)劣的基本標(biāo)準(zhǔn)評價(jià)算法優(yōu)劣的基本標(biāo)準(zhǔn)時(shí)間復(fù)雜度時(shí)間復(fù)雜度pnn問題規(guī)模，一般為數(shù)據(jù)的輸入量問題規(guī)模，一般為數(shù)據(jù)的輸入量pf(n)n算法中基本操作重復(fù)執(zhí)行的次數(shù)算法中基本操作重復(fù)執(zhí)行的次數(shù)頻度頻度n是問題規(guī)模是問題規(guī)模n n的某個(gè)函數(shù)的某個(gè)函數(shù)p算法的時(shí)間量度、時(shí)間復(fù)雜度算法的時(shí)間量度、時(shí)間復(fù)雜度n算法中各語句的頻度之和算法中各語句的頻度之和T(n)nT(n)=O(f(

8、n)n隨問題規(guī)模的增大，執(zhí)行時(shí)間的增長率和隨問題規(guī)模的增大，執(zhí)行時(shí)間的增長率和f(n)的增長率相同的增長率相同時(shí)間復(fù)雜度曲線時(shí)間復(fù)雜度曲線p常見的時(shí)間復(fù)雜度： O(1), O(log2n), O(n), O(n log2n), O(n2), O(n3), O(2n)pO(1)data=x) L2 = p-next; p-next = NULL; break; else p = p-next; p將單向鏈表（頭為L）斷裂成兩個(gè)單鏈表，截掉元素x之后的部分生成為鏈表L2。第三章第三章 棧和隊(duì)列棧和隊(duì)列插入和刪除操作受限的線性表插入和刪除操作受限的線性表p棧和隊(duì)列都是線性表線性表，只是在操作上做了限

9、制操作上做了限制p棧（stack）n后進(jìn)先出后進(jìn)先出(LIFO:Last In First Out)的線性表的線性表n表頭端稱為棧底（表頭端稱為棧底（bottom）n表尾端稱為棧頂（表尾端稱為棧頂（top）n插入和刪除都在棧頂進(jìn)行插入和刪除都在棧頂進(jìn)行p隊(duì)列（queue）n先進(jìn)先出先進(jìn)先出(FIFO:First In First Out)的線性表的線性表n表頭端稱為隊(duì)頭（表頭端稱為隊(duì)頭（front）n表尾端稱為隊(duì)尾（表尾端稱為隊(duì)尾（rear）n插入在隊(duì)尾進(jìn)行，而刪除則在隊(duì)頭進(jìn)行插入在隊(duì)尾進(jìn)行，而刪除則在隊(duì)頭進(jìn)行棧的定義和基本操作棧的定義和基本操作 棧的基本操作棧的基本操作nInitStack(

10、&s)初始化堆棧nStackEmpty(s)判斷堆棧是否空npush(s, e)將元素e壓入堆棧npop(s, &e)彈出棧頂元素棧的存儲(chǔ)結(jié)構(gòu)棧的存儲(chǔ)結(jié)構(gòu)p存儲(chǔ)方式n順序表方式（常用）順序表方式（常用）n鏈表方式鏈表方式p順序表方式的堆棧類型定義#define STACK_SIZE 128ElemType stackSTACK_SIZE;int top;p棧的應(yīng)用棧的應(yīng)用n函數(shù)調(diào)用（函數(shù)調(diào)用（CPU內(nèi)置堆棧操作）內(nèi)置堆棧操作）n遞歸（函數(shù)自己調(diào)用自己的一種特殊函數(shù)調(diào)用。直接遞歸，遞歸（函數(shù)自己調(diào)用自己的一種特殊函數(shù)調(diào)用。直接遞歸，間接遞歸）間接遞歸）隊(duì)列隊(duì)列隊(duì)列的定義隊(duì)列的定義

11、p 隊(duì)列是一種特殊的線性表p 限定插入和刪除操作分別在表的兩端進(jìn)行p 具有先進(jìn)先出(FIFOFirst In First Out)的特點(diǎn)。隊(duì)列的操作隊(duì)列的操作p 主要操作n 增加（入隊(duì)）增加（入隊(duì)） EnQueue(Q, e);n 刪除（出隊(duì)）刪除（出隊(duì)） DeQueue(Q, &e);n 判斷隊(duì)列是否為空判斷隊(duì)列是否為空 QueueEmpty(Q)p 其他操作n 初始化隊(duì)列初始化隊(duì)列InitQueue(Q)n 獲取隊(duì)列長度獲取隊(duì)列長度 QueueLength(Q)n 清除隊(duì)列中的所有元素清除隊(duì)列中的所有元素 ClearQueue(Q)隊(duì)列的隊(duì)列的存儲(chǔ)結(jié)構(gòu)和實(shí)現(xiàn)存儲(chǔ)結(jié)構(gòu)和實(shí)現(xiàn)p 鏈表方

12、式p 順序表方式兩維數(shù)組的遍歷兩維數(shù)組的遍歷p統(tǒng)計(jì)整形數(shù)組AMN中非零元素的個(gè)數(shù)n = 0;for (i = 0; i M; i+) for (j = 0; j N; j+) if (aij != 0) n+;printf(“n=%dn”, n);第六章第六章 樹和二叉樹樹和二叉樹樹的定義和基本術(shù)語樹的定義和基本術(shù)語樹的定義樹的定義p樹是一類重要的非線性數(shù)據(jù)結(jié)構(gòu)，是以分支關(guān)系定義的層次結(jié)構(gòu)；p樹是n(n0)個(gè)結(jié)點(diǎn)的有限集，非空樹滿足：n有且僅有一個(gè)特定的稱之為有且僅有一個(gè)特定的稱之為(root)的結(jié)點(diǎn)；的結(jié)點(diǎn)；n除根以外的其余結(jié)點(diǎn)可分為除根以外的其余結(jié)點(diǎn)可分為m(0 mlchild); Pre

13、order(t-rchild); void Inorder(BiTree t) if (t) Inorder(t-lchild); visit(t); Inorder(t-rchild); void Postorder(BiTree t) if (t) Postorder(t-lchild); Postorder(t -rchild); visit( t ); 遍歷二叉樹的遞歸算法遍歷二叉樹的遞歸算法判斷兩個(gè)二叉樹是否相等類似的其他遞歸式二叉樹算法類似的其他遞歸式二叉樹算法(1)交換二叉樹的左右子樹計(jì)算二叉樹高度二叉樹拷貝計(jì)算二叉樹的平衡因子計(jì)算二叉樹的節(jié)點(diǎn)個(gè)數(shù)類似的其他遞歸式二叉樹算法類似的

14、其他遞歸式二叉樹算法(2)求二叉樹中的節(jié)點(diǎn)數(shù)目（每個(gè)節(jié)點(diǎn)有counter域記錄該二叉樹中的節(jié)點(diǎn)數(shù)目）typedef struct Node TElemType data； int counter; struct Node*lchild； struct Node*rchild； *BitTree；int count(BiTree t) int nl, nr; if (t = NULL) return 0; nl = count(t-lchild); nr = count(t-rchild); t-counter = nl + nr + 1; return t-counter;樹和森林樹和森林樹的

15、存儲(chǔ)結(jié)構(gòu)樹的存儲(chǔ)結(jié)構(gòu): :孩子兄弟表示法孩子兄弟表示法p孩子兄弟表示法ABCDEFGABCEFGD森林與二叉樹的轉(zhuǎn)換森林與二叉樹的轉(zhuǎn)換p轉(zhuǎn)換原則n按孩子兄弟表示法進(jìn)行轉(zhuǎn)換按孩子兄弟表示法進(jìn)行轉(zhuǎn)換(左為長子，左為長子，右右為弟為弟)。p樹與二叉樹的轉(zhuǎn)換DE森林與二叉樹的相互轉(zhuǎn)換森林與二叉樹的相互轉(zhuǎn)換赫夫曼樹及其應(yīng)用赫夫曼樹及其應(yīng)用赫夫曼樹及其應(yīng)用赫夫曼樹及其應(yīng)用p赫夫曼樹n最優(yōu)樹；最優(yōu)樹；n是一類帶權(quán)路徑長度最短的樹；是一類帶權(quán)路徑長度最短的樹；n路徑長度路徑長度p指樹中兩個(gè)結(jié)點(diǎn)間路徑上所含有的分支數(shù)目。n樹的路徑長度樹的路徑長度p指從樹根到每一結(jié)點(diǎn)的路徑長度之和。n帶權(quán)路徑長度帶權(quán)路徑長度p指

16、結(jié)點(diǎn)的路徑長度與該結(jié)點(diǎn)的權(quán)之積。赫夫曼樹赫夫曼樹樹的帶權(quán)路徑長度n樹中所有葉子結(jié)點(diǎn)的帶權(quán)路徑長度；樹中所有葉子結(jié)點(diǎn)的帶權(quán)路徑長度；p最優(yōu)二叉樹或赫夫曼樹。nWPL 最小的二叉樹。最小的二叉樹。結(jié)點(diǎn)到根的路徑長度權(quán)值其中：記作：kknkkklwlwwpl1赫夫曼樹的構(gòu)造赫夫曼樹的構(gòu)造p根據(jù)給定的n個(gè)權(quán)值w1,w2,.wn構(gòu)成n棵二叉樹的集合F=T1,T2,.,Tn，其中每棵二叉樹Ti中只有一個(gè)帶權(quán)為wi的根結(jié)點(diǎn)，其左右子樹均空；p在F中選取兩棵根結(jié)點(diǎn)的權(quán)值最小的樹作為左右子樹構(gòu)造一棵新的二叉樹，且置新的二叉樹的根結(jié)點(diǎn)的權(quán)值為其左、右子樹上根結(jié)點(diǎn)的權(quán)值之和。p在F中刪除這兩棵樹，同時(shí)將新得到的二叉

17、樹加入F中；p重復(fù)2和3，直到F中只含一棵樹為止；p這棵樹就是赫夫曼樹；p赫夫曼樹的性質(zhì)赫夫曼樹的性質(zhì) 所有節(jié)點(diǎn)的度要么為所有節(jié)點(diǎn)的度要么為0，要么為，要么為2； 葉子個(gè)數(shù)葉子個(gè)數(shù)=非葉子結(jié)點(diǎn)個(gè)數(shù)非葉子結(jié)點(diǎn)個(gè)數(shù) + 1； 子樹也是赫夫曼樹；子樹也是赫夫曼樹； 權(quán)權(quán)值越大的值越大的節(jié)點(diǎn)離根越近節(jié)點(diǎn)離根越近 w=5, 29, 7, 8, 14, 23, 3, 1151429 7823 3111429 7823 1135887151429233581111358191429238715113581929 231487152929148715291135819234211358192342291487

18、15295811358192342291487152958100赫夫曼樹構(gòu)造赫夫曼樹構(gòu)造舉例舉例1 1赫夫曼編碼的特點(diǎn)赫夫曼編碼的特點(diǎn)n不等長編碼不等長編碼 赫夫曼編碼是不等長編碼n前綴編碼前綴編碼 赫夫曼編碼是赫夫曼編碼是前綴編碼前綴編碼，即任一編碼，即任一編碼另一字符編碼另一字符編碼的前綴的前綴n發(fā)送過程（編碼）發(fā)送過程（編碼） 根據(jù)由赫夫曼樹得到的編碼表根據(jù)由赫夫曼樹得到的編碼表 送出字符數(shù)據(jù)送出字符數(shù)據(jù)n接收過程（解碼）接收過程（解碼） 按左按左0、右、右1的規(guī)定，從根結(jié)點(diǎn)走到一個(gè)葉結(jié)點(diǎn)，完成一個(gè)的規(guī)定，從根結(jié)點(diǎn)走到一個(gè)葉結(jié)點(diǎn)，完成一個(gè)字符的譯碼。反復(fù)此過程，直到接收數(shù)據(jù)字符的譯碼。反

19、復(fù)此過程，直到接收數(shù)據(jù)結(jié)束結(jié)束第七章第七章 圖圖圖的定義圖的定義和術(shù)語和術(shù)語(1)(1)p圖Gn由兩個(gè)集合由兩個(gè)集合V(G)和和E(G)組成，記作組成，記作G=(V,E) n其中其中V(G)是頂點(diǎn)的非空有窮集合，是頂點(diǎn)的非空有窮集合，E(G)是邊的有窮集合，是邊的有窮集合，而邊是頂點(diǎn)的無序?qū)蛴行驅(qū)Α６吺琼旤c(diǎn)的無序?qū)蛴行驅(qū)Α?112323423圖的基本術(shù)語圖的基本術(shù)語(2)(2)p頂點(diǎn)(vertex)n數(shù)據(jù)元素所構(gòu)成的結(jié)點(diǎn)通常稱為頂點(diǎn)。數(shù)據(jù)元素所構(gòu)成的結(jié)點(diǎn)通常稱為頂點(diǎn)。p弧弧(arc)n若兩個(gè)頂點(diǎn)間有關(guān)系若兩個(gè)頂點(diǎn)間有關(guān)系E ，則稱，則稱為一條弧。為一條弧。p弧頭(又稱終端點(diǎn))n若若為一條

20、弧，則頂點(diǎn)為一條弧，則頂點(diǎn) y 稱為弧頭。稱為弧頭。p弧尾(又稱初始點(diǎn))n若若為一條弧，則頂點(diǎn)為一條弧，則頂點(diǎn) x 稱為弧尾。稱為弧尾。p邊邊(Edge)n無向圖中兩條弧無向圖中兩條弧和和可用一條邊可用一條邊(x,y)來表示來表示 。圖的基本圖的基本術(shù)語術(shù)語(3)(3)p頂點(diǎn)的度頂點(diǎn)的度（degree）n無向圖：與頂點(diǎn)相關(guān)聯(lián)的無向圖：與頂點(diǎn)相關(guān)聯(lián)的邊邊數(shù)稱為該頂點(diǎn)的度數(shù)稱為該頂點(diǎn)的度n有向圖：分為入度和出度有向圖：分為入度和出度 p頂點(diǎn)的入度（indegree）n以頂點(diǎn)為頭的弧數(shù)稱為該頂點(diǎn)的入度以頂點(diǎn)為頭的弧數(shù)稱為該頂點(diǎn)的入度 。p頂點(diǎn)的出度（outdegree）n以頂點(diǎn)為尾的弧數(shù)稱為該頂點(diǎn)的

21、出度以頂點(diǎn)為尾的弧數(shù)稱為該頂點(diǎn)的出度 。p路徑（path）n由頂點(diǎn)由頂點(diǎn)vi經(jīng)過一系列邊和頂點(diǎn)到達(dá)頂點(diǎn)經(jīng)過一系列邊和頂點(diǎn)到達(dá)頂點(diǎn)vj所得到的頂點(diǎn)序列。所得到的頂點(diǎn)序列。p回路（loop-又稱環(huán)環(huán) cycle）n起點(diǎn)和終點(diǎn)為同一頂點(diǎn)的路徑稱為回路。起點(diǎn)和終點(diǎn)為同一頂點(diǎn)的路徑稱為回路。ABCEFD圖的基本圖的基本術(shù)語術(shù)語(4)(4)p簡單路徑n(路徑的頂點(diǎn)路徑的頂點(diǎn))序列中頂點(diǎn)不重復(fù)出現(xiàn)的路徑。序列中頂點(diǎn)不重復(fù)出現(xiàn)的路徑。p簡單回路(簡單環(huán)) n除路徑起點(diǎn)和終點(diǎn)相同外，其余頂點(diǎn)均不相同的回路。除路徑起點(diǎn)和終點(diǎn)相同外，其余頂點(diǎn)均不相同的回路。p權(quán)(weight)n有些圖的邊或弧具有一定的大小，稱之為

22、權(quán)。有些圖的邊或弧具有一定的大小，稱之為權(quán)。p網(wǎng)網(wǎng)n帶權(quán)值的圖又稱為網(wǎng)或網(wǎng)絡(luò)。帶權(quán)值的圖又稱為網(wǎng)或網(wǎng)絡(luò)。ABCEFD圖的基本圖的基本術(shù)語術(shù)語(5)(5)p子圖n由圖的部分頂點(diǎn)和邊組成的新圖稱為原圖的子圖。由圖的部分頂點(diǎn)和邊組成的新圖稱為原圖的子圖。p生成子圖生成子圖n由圖的由圖的全部頂點(diǎn)和全部頂點(diǎn)和部分邊部分邊組成的子圖稱為原圖的生成子圖。組成的子圖稱為原圖的生成子圖。p鄰接點(diǎn)n若邊若邊(vi,vj)E，則，則 vi與與vj互為鄰接點(diǎn)?；猷徑狱c(diǎn)。圖的基本圖的基本術(shù)語術(shù)語(6)(6)p有向圖n若若E ，并不總有，并不總有E，則稱此圖為有向圖，則稱此圖為有向圖p無向圖n若若E ，總有，總有E，則

23、稱此圖為無向圖，則稱此圖為無向圖p完全圖n具有具有 n*(n-1)/2條邊的無向圖稱為完全圖條邊的無向圖稱為完全圖。p有向完全圖n具有具有 n*(n-1)條弧的有向圖稱為有向完全圖。條弧的有向圖稱為有向完全圖。圖的基本術(shù)語圖的基本術(shù)語(7)(7)p生成樹n連通圖的連通圖的極小連通生成子圖極小連通生成子圖稱為原圖的生成樹。稱為原圖的生成樹。p生成森林n由多棵有向樹構(gòu)成的有向圖的生成子圖稱為生成森林。由多棵有向樹構(gòu)成的有向圖的生成子圖稱為生成森林。p最小代價(jià)生成樹n連通網(wǎng)中由最小權(quán)值的邊構(gòu)成的生成樹。連通網(wǎng)中由最小權(quán)值的邊構(gòu)成的生成樹。拓?fù)渑判蛲負(fù)渑判騪拓?fù)渑判騨由某集合上的一個(gè)由某集合上的一個(gè)偏

24、序偏序得到該集合上的一個(gè)得到該集合上的一個(gè)全序全序pAOV 網(wǎng)(Activity On Vertex)n有向有向邊邊表示兩個(gè)活動(dòng)間的表示兩個(gè)活動(dòng)間的次序關(guān)系次序關(guān)系n頂點(diǎn)頂點(diǎn)表示表示活動(dòng)活動(dòng)n這類圖又稱為頂點(diǎn)活動(dòng)圖，簡稱這類圖又稱為頂點(diǎn)活動(dòng)圖，簡稱 AOV 圖圖n如用頂點(diǎn)表示課程，用弧表示某些課程是其它課程的如用頂點(diǎn)表示課程，用弧表示某些課程是其它課程的先修課，則拓?fù)渑判蚓褪乔笤谕瑫r(shí)只能學(xué)習(xí)一門課程先修課，則拓?fù)渑判蚓褪乔笤谕瑫r(shí)只能學(xué)習(xí)一門課程時(shí)的學(xué)習(xí)次序時(shí)的學(xué)習(xí)次序拓?fù)渑判虻乃惴ú襟E拓?fù)渑判虻乃惴ú襟E1.掃描圖中每個(gè)頂點(diǎn)，將入度為零的頂點(diǎn)入隊(duì)列；2.從隊(duì)列中取出一個(gè)頂點(diǎn)輸出，并將其所有鄰接點(diǎn)

25、的入度減 1 ，若入度減為零，則將該鄰接點(diǎn)入隊(duì)列 3.反復(fù)執(zhí)行步驟 2，直至所有頂點(diǎn)的入度均為零p若該有向圖是有環(huán)圖，則不存在拓?fù)渑判蛴协h(huán)圖，則不存在拓?fù)渑判颍筒豢赡茌敵鋈宽旤c(diǎn)；否則就可以輸出全部頂點(diǎn)。此特點(diǎn)可用來判斷一個(gè)有向圖是否存在回路。C1C2C3C6C4C5C7C8C9C10C1C2C3C4C5C6C7C8C9C10C2C1C3C4C5C6C7C8C9C10C1C2C4C3C5C6C7C8C9C10C2C1C4C3C5C6C7C8C9C10C1C2C5C4C3C6C7C8C10C9拓?fù)渑判蚪Y(jié)果：第九章第九章 查找查找基本概念基本概念p查找表n由同一類型的數(shù)據(jù)元素構(gòu)成的集合；由同一類

26、型的數(shù)據(jù)元素構(gòu)成的集合；n靜態(tài)查找表靜態(tài)查找表p對查找表的查找僅是以查詢?yōu)槟康?，不改?dòng)查找表中的數(shù)據(jù)。n動(dòng)態(tài)查找表動(dòng)態(tài)查找表p可以在查找表中插入不存在的記錄，或刪除某個(gè)已存在的記錄。p關(guān)鍵字n數(shù)據(jù)元素（或記錄）的某個(gè)數(shù)據(jù)項(xiàng)，能用來標(biāo)識一個(gè)數(shù)據(jù)元素。數(shù)據(jù)元素（或記錄）的某個(gè)數(shù)據(jù)項(xiàng)，能用來標(biāo)識一個(gè)數(shù)據(jù)元素。p查找n指定某個(gè)值，在查找表中確定是否存在一個(gè)記錄，該記錄的關(guān)鍵指定某個(gè)值，在查找表中確定是否存在一個(gè)記錄，該記錄的關(guān)鍵字等于給定值字等于給定值?；靖拍睿ɡm(xù)）基本概念（續(xù)）p查找成功n查找表中存在滿足查找條件的記錄。查找表中存在滿足查找條件的記錄。p查找不成功n查找表中不存在滿足查找條件的記錄

27、。查找表中不存在滿足查找條件的記錄。p平均查找長度ASL查找方法時(shí)效的度量n為確定記錄在查找表中的位置，需將關(guān)鍵字和給定值比較次數(shù)的為確定記錄在查找表中的位置，需將關(guān)鍵字和給定值比較次數(shù)的期望值。期望值。n查找成功時(shí)的查找成功時(shí)的ASL計(jì)算方法：計(jì)算方法：pn：記錄的個(gè)數(shù)ppi：查找第i個(gè)記錄的概率，( 不特別聲明時(shí)認(rèn)為等概率 pi =1/n )pci：找到第i個(gè)記錄所需的比較次數(shù)動(dòng)態(tài)動(dòng)態(tài)查找表查找表折半查找折半查找只有有序表才能用折半查找的方法只有有序表才能用折半查找的方法p將給定值與中間的記錄進(jìn)行比較；p若找到則查找成功；p否則若給定值比中間記錄小，則對前一半子表進(jìn)行折半查找，反之則對后一

28、半子表進(jìn)行折半查找。p若在查找過程中，遇到查找子表的上界小于下界，則表示查找失敗動(dòng)態(tài)查找表平衡二叉樹動(dòng)態(tài)查找表平衡二叉樹p平衡二叉樹平衡二叉樹n平衡二叉樹又稱平衡二叉樹又稱 AVL AVL 樹，它具有如下性質(zhì)：樹，它具有如下性質(zhì)：p或者為空樹，或者為空樹，p或者根結(jié)點(diǎn)的左、右子樹也均為平衡二叉樹，或者根結(jié)點(diǎn)的左、右子樹也均為平衡二叉樹，且左、右子樹的樹高之差的絕對值不超過且左、右子樹的樹高之差的絕對值不超過1 1。n平衡平衡因子因子bfbfp結(jié)點(diǎn)的左子樹高度減去右子樹高度的值稱為該結(jié)點(diǎn)的左子樹高度減去右子樹高度的值稱為該結(jié)點(diǎn)的平衡因子。結(jié)點(diǎn)的平衡因子。p平衡二叉樹也可以這樣定義：平衡二叉樹是所

29、平衡二叉樹也可以這樣定義：平衡二叉樹是所有結(jié)點(diǎn)的平衡因子的絕對值均小于有結(jié)點(diǎn)的平衡因子的絕對值均小于2 2的二叉樹。的二叉樹。結(jié)點(diǎn)的平衡因子為結(jié)點(diǎn)的平衡因子為 1 1、1 1、0 0p查找算法的效率O(log2n）哈希表哈希表p哈希表n一個(gè)有限的連續(xù)地址空間，用以容納按哈希地址存儲(chǔ)的記錄。一個(gè)有限的連續(xù)地址空間，用以容納按哈希地址存儲(chǔ)的記錄。p哈希函數(shù)n記錄的存儲(chǔ)位置與它的關(guān)鍵字之間存在的一種對應(yīng)關(guān)系。記錄的存儲(chǔ)位置與它的關(guān)鍵字之間存在的一種對應(yīng)關(guān)系。n Loc(ri)=H(keyi)p沖突n不同的兩個(gè)關(guān)鍵字經(jīng)過哈希函數(shù)運(yùn)算后所得到的散列地址相同不同的兩個(gè)關(guān)鍵字經(jīng)過哈希函數(shù)運(yùn)算后所得到的散列地

30、址相同n理想情況下沒有沖突，查找復(fù)雜度理想情況下沒有沖突，查找復(fù)雜度O(1)n一般考慮哈希表，沖突是不可避免發(fā)生的；一般考慮哈希表，沖突是不可避免發(fā)生的；p同義詞n在同一地址出現(xiàn)沖突的各關(guān)鍵字。在同一地址出現(xiàn)沖突的各關(guān)鍵字。 p哈希(散列)地址n根據(jù)設(shè)定的哈希函數(shù)根據(jù)設(shè)定的哈希函數(shù)H(key)和處理沖突的方法確定的記錄的存儲(chǔ)位置。和處理沖突的方法確定的記錄的存儲(chǔ)位置。p裝填因子n=記錄數(shù)記錄數(shù)/哈希表長度哈希表長度n1 必然沖突， 1也有可能沖突哈希函數(shù)的構(gòu)造方法哈希函數(shù)的構(gòu)造方法p直接定址法：nH(key)=a*key+b，a、b為常數(shù)；為常數(shù)；p數(shù)字分析法n分析關(guān)鍵字，找出其中幾位數(shù)字作散

31、列地址（例如：指針值）分析關(guān)鍵字，找出其中幾位數(shù)字作散列地址（例如：指針值）p除留余數(shù)法nH(key)=key % p （求余數(shù)）（求余數(shù)）np可以選用素?cái)?shù)，更有利于可以選用素?cái)?shù)，更有利于“散列散列”，少?zèng)_突，少?zèng)_突p偽隨機(jī)數(shù)法n選取一個(gè)用關(guān)鍵字作為種子的偽隨機(jī)數(shù)發(fā)生器生成散列地址選取一個(gè)用關(guān)鍵字作為種子的偽隨機(jī)數(shù)發(fā)生器生成散列地址解決沖突的常見三種方法解決沖突的常見三種方法p線性再探測線性再探測法法p鏈地址法鏈地址法n散列表設(shè)立指針，將所有散列地址為此位置的關(guān)鍵字散列表設(shè)立指針，將所有散列地址為此位置的關(guān)鍵字記錄用單鏈表形式存儲(chǔ)起來；記錄用單鏈表形式存儲(chǔ)起來；p公共溢出區(qū)法公共溢出區(qū)法n建立

32、公共溢出區(qū)，將所有發(fā)生沖突的關(guān)鍵字記錄存儲(chǔ)建立公共溢出區(qū)，將所有發(fā)生沖突的關(guān)鍵字記錄存儲(chǔ)到公共溢出區(qū)中去到公共溢出區(qū)中去 有一組關(guān)鍵字序列（38、59、125、168、216、719、455、20），用函數(shù) H(key) = key % 10 將其按順序散列到散列表 HT(0:9) 中，分別用三種方法解決沖突：線性再探測法、鏈地址法、公共溢出區(qū)法，畫出這三種方法建立的散列表，并分別求在等概率情況下查找成功和不成功的平均查找長度。例：例：0123456789 3859125 216168 71945520ASL成功 = = = 281683+3+3+1+1+3+1+1ASL不成功 = = = 4

33、.61046104+3+2+1+1+9+8+7+6+51、168 168719719455 4552020ASL成功 = = 81181+1+2+1+1+2+1+2ASL不成功 = = = 1.81018102+1+1+1+1+3+2+1+3+32、01234567893859125216201687194550123456789 3859125 216168 719 45520ASL成功 = = 81481+1+1+1+1+2+3+4ASL不成功 = = = 31030105+1+1+1+1+5+5+1+5+53、012345 公共溢出區(qū)：168 719455719455 455第十章第十章 內(nèi)部排序內(nèi)部排序基本概念基本概念p排序