吉林大學(xué)內(nèi)部絕密資料數(shù)據(jù)結(jié)構(gòu)總復(fù)習(xí)（課堂PPT）

1、.1數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)總復(fù)習(xí).2教學(xué)內(nèi)容教學(xué)內(nèi)容l第一章第一章緒論緒論l第二章第二章線性表、堆棧和隊列線性表、堆棧和隊列l(wèi)第三章第三章數(shù)組和字符串?dāng)?shù)組和字符串l第六章第六章遞歸遞歸l第四章第四章樹樹l第五章第五章圖圖l第七章第七章排序排序l第八章第八章查找查找基礎(chǔ)知識基礎(chǔ)知識基礎(chǔ)知識基礎(chǔ)知識線性結(jié)構(gòu)線性結(jié)構(gòu)非線性結(jié)構(gòu)非線性結(jié)構(gòu)非線性結(jié)構(gòu)非線性結(jié)構(gòu).3重點內(nèi)容重點內(nèi)容l三三兩兩三三兩兩l三要素（邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)、操作）l三個數(shù)據(jù)結(jié)構(gòu)（線性表、樹、圖）l兩類算法（排序、查找）l兩個評價算法的主要標準（時間、空間復(fù)雜性）l兩個表（33，22）.433（2、3、4、5章）章）線性表樹圖邏輯結(jié)構(gòu)存儲結(jié)構(gòu)

2、操作.522（7、8章）章）時間復(fù)雜性空間復(fù)雜性排序插入、交換、選擇、合并查找有序表的查找雜湊.6重點內(nèi)容重點內(nèi)容l3+2三類數(shù)據(jù)結(jié)構(gòu)l線性表l樹l圖兩類算法l排序l查找.7教學(xué)內(nèi)容教學(xué)內(nèi)容l基礎(chǔ)知識第一章緒 論.8一、基礎(chǔ)知識一、基礎(chǔ)知識l掌握數(shù)據(jù)結(jié)構(gòu)的基本概念和術(shù)語掌握數(shù)據(jù)結(jié)構(gòu)的基本概念和術(shù)語包括：數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項、數(shù)據(jù)結(jié)構(gòu)等基本包括：數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項、數(shù)據(jù)結(jié)構(gòu)等基本 概念。概念。l算法和算法分析算法和算法分析掌握算法、算法的時間復(fù)雜度和空間復(fù)雜度等概念掌握算法、算法的時間復(fù)雜度和空間復(fù)雜度等概念掌握算法分析的方法，對一般算法能分析出時間復(fù)掌握算法分析的方法，對一般算法能分析出

3、時間復(fù)雜度。雜度。 .9一、基礎(chǔ)知識一、基礎(chǔ)知識l數(shù)據(jù)數(shù)據(jù):計算機程序要處理的“原料”l數(shù)據(jù)元素數(shù)據(jù)元素:是組成數(shù)據(jù)的基本單位。在程序中通常把結(jié)點作為一個整體進行考慮和處理。l數(shù)據(jù)項數(shù)據(jù)項:每個數(shù)據(jù)元素都有學(xué)號、姓名這兩個數(shù)據(jù)項構(gòu)成。數(shù)據(jù)項是構(gòu)成數(shù)據(jù)的最小單位。.10一、基礎(chǔ)知識一、基礎(chǔ)知識的定義：的定義：按某種邏輯關(guān)系將一批數(shù)據(jù)元素組織起按某種邏輯關(guān)系將一批數(shù)據(jù)元素組織起來來按一定的存儲方式把它們存儲起來；按一定的存儲方式把它們存儲起來；1.在數(shù)據(jù)上定義需要施加的操作。在數(shù)據(jù)上定義需要施加的操作。.11一、基礎(chǔ)知識一、基礎(chǔ)知識l數(shù)據(jù)結(jié)構(gòu)的組成：數(shù)據(jù)結(jié)構(gòu)的組成：數(shù)據(jù)的數(shù)據(jù)的數(shù)據(jù)的數(shù)據(jù)的數(shù)據(jù)需要

4、數(shù)據(jù)需要.12邏輯結(jié)構(gòu)邏輯結(jié)構(gòu)l數(shù)據(jù)元素之間的邏輯關(guān)系稱為數(shù)據(jù)數(shù)據(jù)元素之間的邏輯關(guān)系稱為數(shù)據(jù)的的邏輯結(jié)構(gòu)邏輯結(jié)構(gòu)。l邏輯結(jié)構(gòu)的形式化表示邏輯結(jié)構(gòu)的形式化表示邏輯結(jié)構(gòu)表示為二元組邏輯結(jié)構(gòu)表示為二元組 L=(N, R)，其中，其中N(L)是結(jié)點的有限集合，是結(jié)點的有限集合， R(L)是是N上的關(guān)系集合。上的關(guān)系集合。.13邏輯結(jié)構(gòu)的分類邏輯結(jié)構(gòu)的分類l線性結(jié)構(gòu)結(jié)構(gòu)中有且僅有一個有且僅有一個始結(jié)點和一個終結(jié)點，始結(jié)點只有一個后繼結(jié)點，終結(jié)點只有一個前趨結(jié)點，每個內(nèi)結(jié)點有且僅有一個有且僅有一個前趨結(jié)點和一個后繼結(jié)點。l非線性結(jié)構(gòu)（樹、圖）結(jié)構(gòu)中的結(jié)點可能有多個可能有多個前趨結(jié)點和多個后繼結(jié)點.14數(shù)據(jù)

5、的存儲結(jié)構(gòu)數(shù)據(jù)的存儲結(jié)構(gòu)l數(shù)據(jù)在計算機中的存儲表示稱為數(shù)據(jù)的存儲結(jié)構(gòu)。順序存儲結(jié)構(gòu)鏈接存儲結(jié)構(gòu).15數(shù)據(jù)需要施加的操作數(shù)據(jù)需要施加的操作l數(shù)據(jù)處理是指對數(shù)據(jù)進行查找、插入、刪數(shù)據(jù)處理是指對數(shù)據(jù)進行查找、插入、刪除、合并、排序、統(tǒng)計以及簡單計算等的除、合并、排序、統(tǒng)計以及簡單計算等的操作過程。操作過程。線性表樹圖.16算法描述語言算法描述語言 ADLlADL 的格式算法（變量i1,變量im.變量j1,變量jn）/單行注釋（或/*/多行注釋） 步驟名1 步驟1所執(zhí)行操作的高度概括 語句序列. 步驟名n 步驟n所執(zhí)行操作的高度概括 語句序列. .17時間復(fù)雜性對所研究問題的基本操作對所研究問題的基本

6、操作數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)邏輯結(jié)構(gòu)邏輯結(jié)構(gòu)存儲結(jié)構(gòu)存儲結(jié)構(gòu)操作操作線線性性結(jié)結(jié)構(gòu)構(gòu)樹樹型型結(jié)結(jié)構(gòu)構(gòu)圖圖狀狀結(jié)結(jié)構(gòu)構(gòu)集集合合順順 序序存存 儲儲結(jié)結(jié) 構(gòu)構(gòu)鏈鏈 式式存存 儲儲結(jié)結(jié) 構(gòu)構(gòu).19二、常用數(shù)據(jù)結(jié)構(gòu)線性表樹圖.20線性表l掌握線性表的定義和邏輯結(jié)構(gòu)，了解線性表的基本運算。掌握線性表的定義和邏輯結(jié)構(gòu)，了解線性表的基本運算。l掌握順序表的插入和刪除操作及平均時間性能分析。掌握順序表的插入和刪除操作及平均時間性能分析。l熟練掌握單鏈表查找、插入和刪除操作并分析其時間復(fù)雜度。熟練掌握單鏈表查找、插入和刪除操作并分析其時間復(fù)雜度。l了解循環(huán)單鏈表算法和單鏈表上相應(yīng)算法的異同點。了解循環(huán)單鏈表算法和單鏈表

7、上相應(yīng)算法的異同點。l熟練利用單鏈表設(shè)計算法解決簡單的應(yīng)用問題。熟練利用單鏈表設(shè)計算法解決簡單的應(yīng)用問題。l掌握雙鏈表的基本操作。掌握雙鏈表的基本操作。l掌握順序表和鏈表的主要優(yōu)缺點掌握順序表和鏈表的主要優(yōu)缺點.21線性表線性表定義：線性表定義：一個線性表是由零個或多個一個線性表是由零個或多個具有相同類型的結(jié)點組成的有序集合。具有相同類型的結(jié)點組成的有序集合。用（用（a0，a1，an-1）來表示一個線性）來表示一個線性表。當(dāng)表。當(dāng)n0時，時，a0稱為表的始結(jié)點，稱為表的始結(jié)點，an-1稱為表的終結(jié)點，當(dāng)稱為表的終結(jié)點，當(dāng)n=0時，線性表中時，線性表中有零個結(jié)點，稱為空表。有零個結(jié)點，稱為空表。

8、.22線性表的存儲結(jié)構(gòu)線性表的存儲結(jié)構(gòu)l順序存儲結(jié)構(gòu)順序存儲結(jié)構(gòu)l鏈接存儲結(jié)構(gòu)鏈接存儲結(jié)構(gòu)單鏈表單鏈表循環(huán)鏈表循環(huán)鏈表雙向循環(huán)鏈表雙向循環(huán)鏈表.23棧棧 和和 隊隊 列（線性表的應(yīng)用）列（線性表的應(yīng)用）l掌握棧的邏輯結(jié)構(gòu)特點。掌握棧的邏輯結(jié)構(gòu)特點。l掌握順序棧和鏈棧上實現(xiàn)的進棧、退棧等基本掌握順序棧和鏈棧上實現(xiàn)的進棧、退棧等基本算法。算法。l掌握隊列的邏輯結(jié)構(gòu)特點。掌握隊列的邏輯結(jié)構(gòu)特點。l掌握順序隊列（主要是循環(huán)隊列）和鏈隊列上掌握順序隊列（主要是循環(huán)隊列）和鏈隊列上實現(xiàn)的入隊、出隊等基本算法。實現(xiàn)的入隊、出隊等基本算法。.24棧棧 和和 隊隊 列（線性表的應(yīng)用）列（線性表的應(yīng)用）棧和隊列都

9、是操作受限的線性表棧和隊列都是操作受限的線性表棧的定義：棧是插入和刪除只能在其一端進行的線性表。棧的定義：棧是插入和刪除只能在其一端進行的線性表。并按先進后出（并按先進后出（ F I L O )F I L O )或后進先出（或后進先出（I I）的原則進行操作。的原則進行操作。隊列的定義：隊列是插入在一端進行而刪除在其另一端隊列的定義：隊列是插入在一端進行而刪除在其另一端進行的線性表。并按先進向出（進行的線性表。并按先進向出（FIFOFIFO）的原則進行操）的原則進行操作。能進行刪除的一端稱為隊首（作。能進行刪除的一端稱為隊首（frontfront），能進行），能進行插入操作的一端稱為隊尾（插入

10、操作的一端稱為隊尾（rearrear）。）。.25 棧的應(yīng)用棧的應(yīng)用算術(shù)表達式求值算術(shù)表達式求值運算規(guī)則：運算規(guī)則：(1) 先計算括號內(nèi)，后計算括號外；先計算括號內(nèi)，后計算括號外；(2) 在無括號或同層括號內(nèi)，先進行乘除運算，在無括號或同層括號內(nèi)，先進行乘除運算，后進行加減運算，即乘除運算的優(yōu)先級高于加后進行加減運算，即乘除運算的優(yōu)先級高于加減運算的優(yōu)先級；減運算的優(yōu)先級；(3) 同一優(yōu)先級運算，從左向右依次進行。同一優(yōu)先級運算，從左向右依次進行。.26數(shù)組、字符串和集合（線性結(jié)構(gòu)）數(shù)組、字符串和集合（線性結(jié)構(gòu)）l掌握一維、二維數(shù)組的存儲方法及對任意元素求地址公式l掌握稀疏矩陣的概念及存儲方法

11、l掌握串的有關(guān)概念及基本算法。l了解串的兩種存儲表示。l了解模式匹配算法.27樹樹l掌握樹的常用術(shù)語及含義。l掌握二叉樹的遞歸定義及樹與二叉樹的差別。l熟練掌握二叉樹的性質(zhì)。l掌握二叉樹的兩種存儲方法。l熟練掌握二叉樹的四種遍歷算法。l熟練掌握確定四種遍歷所得到的相應(yīng)的結(jié)點訪問序列。.28樹樹l熟練掌握以二叉樹遍歷算法為基礎(chǔ)，設(shè)計有關(guān)算法解決簡單的應(yīng)用問題。l掌握樹的存儲方法并設(shè)計有關(guān)算法解決簡單的應(yīng)用問題。l掌握線索二叉樹的概念及存儲方法并能將一棵二叉樹線索化。l熟練掌握樹和森林與二叉樹之間的轉(zhuǎn)換方法。l熟練掌握根據(jù)給定的葉結(jié)點及其權(quán)值構(gòu)造出哈夫曼樹。.29常用數(shù)據(jù)結(jié)構(gòu)常用數(shù)據(jù)結(jié)構(gòu)l樹樹是由

12、唯一的起始結(jié)點“根結(jié)點”( r o o t)出發(fā)的結(jié)點集合，其中，任何非根結(jié)點都有且僅有一個前任何非根結(jié)點都有且僅有一個前趨結(jié)點趨結(jié)點，稱之為該結(jié)點的父結(jié)點；任何結(jié)點都可能任何結(jié)點都可能有多個后繼結(jié)點有多個后繼結(jié)點，稱之為該結(jié)點的子結(jié)點；若某結(jié)點沒有后繼結(jié)點，則稱之為葉子結(jié)點。若存在路徑，其中是的后繼結(jié)點，則稱為的子孫結(jié)點，稱為的祖先結(jié)點，該路徑所經(jīng)歷的邊的個數(shù)被稱為路徑的長度。一個結(jié)點到它的某個子孫結(jié)點有且僅有一條路徑。.30二叉樹 (Binary Tree)二叉樹是結(jié)點的有限集合，它必須滿足二叉樹是結(jié)點的有限集合，它必須滿足 下面的一個條件：下面的一個條件：（1）它是空集。）它是空集。（2

13、）它由一個根結(jié)點）它由一個根結(jié)點,根結(jié)點的左右子樹根結(jié)點的左右子樹構(gòu)成，且其左右子樹滿足二叉樹定義。構(gòu)成，且其左右子樹滿足二叉樹定義。.31樹的儲結(jié)構(gòu) 1 1 順序存儲結(jié)構(gòu)順序存儲結(jié)構(gòu) 完全二叉樹的順序存儲完全二叉樹的順序存儲: :按層次次序給結(jié)點編號按層次次序給結(jié)點編號，使，使用用一維數(shù)組一維數(shù)組A來存放。來存放。A0A0存儲二叉樹的根結(jié)點，存儲二叉樹的根結(jié)點，AiAi結(jié)點的左孩子結(jié)點存放在結(jié)點的左孩子結(jié)點存放在2i+12i+1處，而處，而AiAi的右孩子的右孩子結(jié)點存放在結(jié)點存放在A2i+2A2i+2處處 2 2 鏈式存儲結(jié)構(gòu)鏈式存儲結(jié)構(gòu) 二叉樹諸結(jié)點被隨機存放在內(nèi)存空間中，結(jié)點二叉樹諸結(jié)

14、點被隨機存放在內(nèi)存空間中，結(jié)點之間的關(guān)系用指針說明。之間的關(guān)系用指針說明。( (線索樹線索樹) ).32基本操作l二叉樹的遍歷：按照一定次序訪問樹中所有結(jié)二叉樹的遍歷：按照一定次序訪問樹中所有結(jié) 點，并且每個結(jié)點的值僅被訪問一次的過程。點，并且每個結(jié)點的值僅被訪問一次的過程。遍歷次序是樹中結(jié)點的一遍歷次序是樹中結(jié)點的一個有序序列，稱為二叉樹的先根（中根、后根）個有序序列，稱為二叉樹的先根（中根、后根）序列。序列。.33構(gòu)造哈夫曼樹哈夫曼算法基本思想：哈夫曼算法基本思想： 根據(jù)給定的根據(jù)給定的n個權(quán)值個權(quán)值w1 , w2 , ,wn構(gòu)成構(gòu)成n棵二叉樹的棵二叉樹的森林森林F=T1 ,T2 , ,T

15、n ,其中每棵二叉樹其中每棵二叉樹Ti中都只有一中都只有一個權(quán)值為個權(quán)值為wi的根結(jié)點，其左、右子樹均空；的根結(jié)點，其左、右子樹均空； 在森林在森林F中選出兩棵根結(jié)點權(quán)值最小的樹作為一棵新中選出兩棵根結(jié)點權(quán)值最小的樹作為一棵新樹的左、右子樹，且置新樹的根結(jié)點的權(quán)值為其左、樹的左、右子樹，且置新樹的根結(jié)點的權(quán)值為其左、右子樹上根結(jié)點的權(quán)值之和；右子樹上根結(jié)點的權(quán)值之和； 從從F中刪除構(gòu)成新樹的那兩棵樹，同時把新樹加入中刪除構(gòu)成新樹的那兩棵樹，同時把新樹加入F中；中； 重復(fù)第和第步，直到重復(fù)第和第步，直到F中只含有一棵樹為止，此中只含有一棵樹為止，此樹便是哈夫曼樹。樹便是哈夫曼樹。.34圖l掌握圖

16、的常用術(shù)語及含義。掌握圖的常用術(shù)語及含義。l掌握圖的深度優(yōu)先搜索和廣度優(yōu)先搜索兩種遍掌握圖的深度優(yōu)先搜索和廣度優(yōu)先搜索兩種遍歷算法及執(zhí)行過程。歷算法及執(zhí)行過程。l熟練掌握確定兩種遍歷所得到的頂點訪問序列。熟練掌握確定兩種遍歷所得到的頂點訪問序列。.35圖l要求對給定的連通圖，根據(jù)要求對給定的連通圖，根據(jù)Prim和和Kruskar算算法構(gòu)造最小生成樹。法構(gòu)造最小生成樹。l對于給定的有向圖，根據(jù)對于給定的有向圖，根據(jù)Dijkstra算法能畫出算法能畫出求單源最短路徑的過程示意圖。求單源最短路徑的過程示意圖。l對于給定的有向圖，若拓撲序列存在，則要求對于給定的有向圖，若拓撲序列存在，則要求寫出一個或

17、多個拓撲序列。寫出一個或多個拓撲序列。l對于給定的有向圖，能求出其關(guān)鍵路徑等。對于給定的有向圖，能求出其關(guān)鍵路徑等。.36圖l圖（圖（Graph）是一種較線性表和樹更為復(fù)雜的）是一種較線性表和樹更為復(fù)雜的非線性結(jié)構(gòu)。在圖結(jié)構(gòu)中，對結(jié)點（圖中常稱非線性結(jié)構(gòu)。在圖結(jié)構(gòu)中，對結(jié)點（圖中常稱為頂點）的前趨和后繼個數(shù)都是不加限制的，為頂點）的前趨和后繼個數(shù)都是不加限制的，即結(jié)點之間的關(guān)系是任意的。圖中任意兩個結(jié)即結(jié)點之間的關(guān)系是任意的。圖中任意兩個結(jié)點之間都可能相關(guān)。圖狀結(jié)構(gòu)可以描述各種復(fù)點之間都可能相關(guān)。圖狀結(jié)構(gòu)可以描述各種復(fù)雜的數(shù)據(jù)對象。雜的數(shù)據(jù)對象。.37圖的存儲結(jié)構(gòu)圖的存儲結(jié)構(gòu)l鄰接矩陣l鄰接表

18、 (Adjacency List).38圖的基本操作遍歷遍歷深度優(yōu)先遍歷深度優(yōu)先遍歷廣度優(yōu)先遍歷廣度優(yōu)先遍歷.39基于圖的算法拓撲排序拓撲排序關(guān)鍵路徑關(guān)鍵路徑最短路徑（最短路徑（Dijkstra算法）算法）最小支撐樹最小支撐樹(Prim、Kruskar算法算法).40排序排序l排序排序：將一組雜亂無章的數(shù)據(jù)按一定的規(guī)律順：將一組雜亂無章的數(shù)據(jù)按一定的規(guī)律順次排列起來。次排列起來。l插入排序插入排序l交換排序交換排序l選擇排序選擇排序l合并排序合并排序各種內(nèi)部排序方法的比較各種內(nèi)部排序方法的比較 排序方法排序方法 最好時間最好時間 平均時間平均時間 最壞時間最壞時間穩(wěn)定性穩(wěn)定性輔助空間輔助空間冒泡冒泡O(n)O(n)O(nO(n2 2) )O(nO(n2 2) )穩(wěn)定穩(wěn)定O(1)O(1)希爾希爾 O(nO(n1.251.25) ) 不穩(wěn)定不穩(wěn)定O(1)O(1)直接插入直接插入O(n)O(n)O(nO(n2 2) )O(nO(n2 2) )穩(wěn)定穩(wěn)定O(1)O(1)直接選擇直接選擇O(nO(n2 2) )O(nO(n2 2) )O(nO(n2 2) )不穩(wěn)定不穩(wěn)定O(1)O(1)快速快速O(nlogO(nlog2 2n)n)O(nlogO(nlog2 2n)n)O(nO(n2 2) )不穩(wěn)定不穩(wěn)定O(l