數(shù)據(jù)結(jié)構(gòu)導(dǎo)論串講

數(shù)據(jù)結(jié)構(gòu)導(dǎo)論串講第1頁，共148頁，2023年，2月20日，星期六

概述

《數(shù)據(jù)結(jié)構(gòu)導(dǎo)論》是計算機(jī)科學(xué)與技術(shù)專業(yè)的一門必修課程。本課程介紹如何組織各種數(shù)據(jù)在計算機(jī)中的存儲、傳遞和轉(zhuǎn)換。內(nèi)容包括：線性表、棧、隊列、串、數(shù)組、樹、二叉樹、圖等基本數(shù)據(jù)結(jié)構(gòu)及其應(yīng)用；排序和查找的原理與方法；數(shù)據(jù)在外存上的組織方法。第2頁，共148頁，2023年，2月20日，星期六第一章概論第3頁，共148頁，2023年，2月20日，星期六第4頁，共148頁，2023年，2月20日，星期六本章總述要求熟悉各名詞、術(shù)語的含義，掌握基本概念。包括數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項、邏輯關(guān)系和邏輯結(jié)構(gòu)、運(yùn)算和基本運(yùn)算、數(shù)據(jù)結(jié)構(gòu)、存儲方式和存儲結(jié)構(gòu)、算法及算法分析等。注意這些概念之間的聯(lián)系。第5頁，共148頁，2023年，2月20日，星期六本章重點(diǎn)邏輯結(jié)構(gòu)和數(shù)據(jù)結(jié)構(gòu)的概念。本章難點(diǎn)算法的時間復(fù)雜性分析。第6頁，共148頁，2023年，2月20日，星期六本章知識點(diǎn)

1.數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項數(shù)據(jù)—能被計算機(jī)存儲、加工的對象通稱為數(shù)據(jù)。數(shù)據(jù)元素—是數(shù)據(jù)的基本單位，在程序中作為一個整體來考慮和處理。具有完整確定的實際意義。數(shù)據(jù)項—是數(shù)據(jù)不可分割的最小標(biāo)識單位。數(shù)據(jù)元素可由若干個數(shù)據(jù)項組成，數(shù)據(jù)項通常不具有完整確定的實際意義。第7頁，共148頁，2023年，2月20日，星期六數(shù)據(jù)數(shù)據(jù)項數(shù)據(jù)元素數(shù)據(jù)、數(shù)據(jù)元素和數(shù)據(jù)項構(gòu)成了數(shù)據(jù)組織的三個層次，如下圖所示:第8頁，共148頁，2023年，2月20日，星期六

2.數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)是數(shù)據(jù)元素之間的相互關(guān)系。結(jié)構(gòu)分為邏輯結(jié)構(gòu)與物理結(jié)構(gòu)。線性結(jié)構(gòu)樹形結(jié)構(gòu)圖狀結(jié)構(gòu)集合結(jié)構(gòu)第9頁，共148頁，2023年，2月20日，星期六存儲結(jié)構(gòu)：邏輯結(jié)構(gòu)在計算機(jī)中的表示（映像）被稱為存儲結(jié)構(gòu)，其中應(yīng)該包含數(shù)據(jù)元素的內(nèi)容及其關(guān)系的表示。

四種基本存儲方式：

順序存儲方式特點(diǎn)：借助于數(shù)據(jù)元素在存儲器中的位置來表示數(shù)據(jù)元素之間的邏輯關(guān)系

鏈?zhǔn)酱鎯Ψ绞教攸c(diǎn)：借助指示元素存儲地址的指針來表示數(shù)據(jù)元素之間的邏輯關(guān)系

索引存儲方式

散列存儲方式第10頁，共148頁，2023年，2月20日，星期六

3.算法算法就是解決問題的方法。算法分析主要從時間復(fù)雜度、空間復(fù)雜度方面進(jìn)行算法分析。時間復(fù)雜度:最壞情況時間復(fù)雜度,平均時間復(fù)雜度。Tnnlog2nn2本章結(jié)束第11頁，共148頁，2023年，2月20日，星期六第二章線性表第12頁，共148頁，2023年，2月20日，星期六第13頁，共148頁，2023年，2月20日，星期六本章總述本章主要討論了線性表及它的兩種存儲實現(xiàn)：順序?qū)崿F(xiàn)和鏈接實現(xiàn)；另外，簡單介紹了串這種特殊的線性表的運(yùn)算和存儲實現(xiàn)。線性表是一種最簡單最常見的數(shù)據(jù)結(jié)構(gòu)第14頁，共148頁，2023年，2月20日，星期六本章重點(diǎn)

線性結(jié)構(gòu)的定義和特點(diǎn)；線性表的運(yùn)算；順序表和單鏈表的組織方法和算法設(shè)計。本章難點(diǎn)

單鏈表上的算法設(shè)計。第15頁，共148頁，2023年，2月20日，星期六線性表的邏輯結(jié)構(gòu)定義線性表是一個含有n個數(shù)據(jù)元素的有限序列。L=(a1,a2,a3,a4,a5,a6,....,an)ai-1,

ai

,

ai+1直接前驅(qū)

直接后繼線性表長度第16頁，共148頁，2023年，2月20日，星期六

線性結(jié)構(gòu)的基本特征:線性結(jié)構(gòu)是一個數(shù)據(jù)元素的有序（次序）集

1.集合中必存在唯一的一個“第一元素”；

2.集合中必存在唯一的一個“最后元素”；

3.除最后元素之外，均有唯一的后繼；

4.除第一元素之外，均有唯一的前驅(qū)。第17頁，共148頁，2023年，2月20日，星期六順序存儲結(jié)構(gòu)

用一組地址連續(xù)的存儲單元依次存儲線性表的元素。

順序表特點(diǎn)：

邏輯順序與物理順序一致；

屬隨機(jī)存取的存儲結(jié)構(gòu)。第18頁，共148頁，2023年，2月20日，星期六......a1a2a3a4a5a6anbb+Lb+2Lb+3Lb+(n-1)L假設(shè)線性表中每個元素需占用L個存儲單元LOC(ai+1)=LOC(ai)+LLOC(ai)=LOC(a1)+(i-1)*LL:一個數(shù)據(jù)元素所占存儲量↑基地址第19頁，共148頁，2023年，2月20日，星期六插入、刪除算法的分析插入算法的數(shù)學(xué)期望值刪除算法的數(shù)學(xué)期望值設(shè)：pi=1/(n+1),qi=1/n，則可以得出：第20頁，共148頁，2023年，2月20日，星期六順序表表示的優(yōu)缺點(diǎn)優(yōu)點(diǎn)：隨機(jī)存取表中的任一結(jié)點(diǎn)。缺點(diǎn)：插入和刪除運(yùn)算不方便，須移動大量的結(jié)點(diǎn)；存儲分配只能預(yù)先分配。第21頁，共148頁，2023年，2月20日，星期六鏈?zhǔn)酱鎯Y(jié)構(gòu)用一組任意的存儲單元（可能不連續(xù)）存儲線性表的數(shù)據(jù)元素。......a3......a2......a1......a4...........第22頁，共148頁，2023年，2月20日，星期六鏈?zhǔn)酱鎯Y(jié)構(gòu)數(shù)據(jù)元素內(nèi)容該數(shù)據(jù)元素的直接后繼地址datanext數(shù)據(jù)域指針域第23頁，共148頁，2023年，2月20日，星期六L=(a1,a2,a3,a4,a5,a6)結(jié)點(diǎn)La1a2a3a4a5a6^以線性表中第一個數(shù)據(jù)元素的存儲地址作為線性表的地址，稱作線性表的頭指針。第24頁，共148頁，2023年，2月20日，星期六含有頭結(jié)點(diǎn)的空表//////^

ＬL////a1a2......an^頭結(jié)點(diǎn)有時為了操作方便，在第一個結(jié)點(diǎn)之前附設(shè)一個“頭結(jié)點(diǎn)”，以指向頭結(jié)點(diǎn)的指針為鏈表的頭指針指針域為空第25頁，共148頁，2023年，2月20日，星期六

特點(diǎn):邏輯順序與物理順序有可能不一致。屬順序存取的存儲結(jié)構(gòu)，即存取每個數(shù)據(jù)元素所花費(fèi)的時間不相等。第26頁，共148頁，2023年，2月20日，星期六datanextprior特點(diǎn)：克服單鏈表的單向性其它形式的鏈表1.雙向鏈表(doublelinkedlist)每個結(jié)點(diǎn)有兩個指針域第27頁，共148頁，2023年，2月20日，星期六

2.循環(huán)鏈表表中最后一個結(jié)點(diǎn)的指針域指向頭結(jié)點(diǎn)，鏈表形成一個環(huán)。特點(diǎn)從表中任何一個結(jié)點(diǎn)出發(fā)可掃描整個鏈表中的所有結(jié)點(diǎn)。第28頁，共148頁，2023年，2月20日，星期六順序?qū)崿F(xiàn)與鏈接實現(xiàn)的比較時間性能比較定位運(yùn)算:順序表和單鏈表,均為O(n)讀表元：順序表-O(1)(隨機(jī)存取);單鏈表-O(n)鏈入/摘除：順序表-0(n);單鏈表-O(1)（插入、刪除方便）第29頁，共148頁，2023年，2月20日，星期六第三章棧、隊列和數(shù)組第30頁，共148頁，2023年，2月20日，星期六第31頁，共148頁，2023年，2月20日，星期六本章總述棧和隊列是兩種常用的數(shù)據(jù)結(jié)構(gòu)，這兩種結(jié)構(gòu)與線性表有密切的聯(lián)系。棧和隊列的邏輯結(jié)構(gòu)是線性結(jié)構(gòu)，它們的基本運(yùn)算與線性表的基本運(yùn)算十分類似，可看作是運(yùn)算受限的線性表。數(shù)組與線性表也有密切的聯(lián)系。第32頁，共148頁，2023年，2月20日，星期六本章重點(diǎn)棧和隊列的特點(diǎn)；順序棧和鏈棧上基本運(yùn)算的實現(xiàn)和簡單算法；鏈隊上基本運(yùn)算實現(xiàn)和簡單算法設(shè)計。本章難點(diǎn)循環(huán)隊的組織，隊滿、隊空的條件及算法設(shè)計。第33頁，共148頁，2023年，2月20日，星期六棧的類型定義插入、刪除只在表尾進(jìn)行的線性表被稱為棧。a1a2a3a4....an插入刪除第34頁，共148頁，2023年，2月20日，星期六棧的特點(diǎn)后進(jìn)先出----LIFO(LastInFirstOut)棧頂浮動棧底固定a1a2a3a4出進(jìn)棧底棧頂?shù)?5頁，共148頁，2023年，2月20日，星期六棧的表示和實現(xiàn)順序存儲結(jié)構(gòu)：

順序棧鏈?zhǔn)酱鎯Y(jié)構(gòu)：

鏈棧第36頁，共148頁，2023年，2月20日，星期六隊列定義若線性表的插入操作在一端進(jìn)行，刪除操作在另一端進(jìn)行，則稱此線性表為隊列。第37頁，共148頁，2023年，2月20日，星期六a1,a2,a3,a4,...,an刪除端插入端隊頭front隊尾rear第38頁，共148頁，2023年，2月20日，星期六隊列特點(diǎn)FIFO(FirstInFirstOut)隊頭、隊尾均是浮動的隊列類型的實現(xiàn)鏈隊列——鏈?zhǔn)接诚笱h(huán)隊列——順序映象第39頁，共148頁，2023年，2月20日，星期六q4q3q2q1frontrear3210入隊

Q[rear++]=e;出隊

e=Q[front++]隊列的順序存儲結(jié)構(gòu)第40頁，共148頁，2023年，2月20日，星期六隊列的順序存儲結(jié)構(gòu)frontrear“假溢出”現(xiàn)象解決的方法:將隊列構(gòu)成環(huán)狀q4q3q2q1第41頁，共148頁，2023年，2月20日，星期六循環(huán)隊列012345678q1q2q3q4q5rearfront入隊操作：sq.rear=(sq.rear+1)%maxsize;出隊操作：sq.front=(sq.front+1)%maxsize;隊列空：sq.rear=sq.front隊列滿：((sq.rear+1)%maxsize)==sq.front;第42頁，共148頁，2023年，2月20日，星期六數(shù)組是一種已經(jīng)在高級語言中實現(xiàn)了的數(shù)據(jù)結(jié)構(gòu)。通常采用順序存儲結(jié)構(gòu)來存放數(shù)組。

有兩種順序映象的方式（二維數(shù)組）:

1)以行序為主序(低下標(biāo)優(yōu)先);

2)以列序為主序(高下標(biāo)優(yōu)先);第43頁，共148頁，2023年，2月20日，星期六例如：

稱為基地址或基址。以“行序為主序”的存儲映象二維數(shù)組A中任一元素ai,j

的存儲位置

LOC(i,j)=LOC(0,0)+(b2×i＋j)×a0,1a0,0a0,2a1,0a1,1a1,2a0,1a0,0a0,2a1,0a1,1a1,2L

L

第44頁，共148頁，2023年，2月20日，星期六矩陣的壓縮存儲矩陣可用二維數(shù)組來表示。實際問題中，會碰到階數(shù)高的矩陣，但存在許多值相同的元素和零元素。壓縮存儲的基本思想：值相同的多個元素只分配一個存儲空間，零元素不分配空間。特殊矩陣的壓縮存儲(對稱矩陣，三角矩陣)稀疏矩陣的壓縮存儲(三元組順序表)第45頁，共148頁，2023年，2月20日，星期六第四章樹第46頁，共148頁，2023年，2月20日，星期六第47頁，共148頁，2023年，2月20日，星期六本章總述本章是數(shù)據(jù)結(jié)構(gòu)課程的重點(diǎn)之一。主要內(nèi)容包括：樹形結(jié)構(gòu)的基本概念，定義在樹形結(jié)構(gòu)上的兩種重要的數(shù)據(jù)結(jié)構(gòu)-二叉樹和樹，它們的常見存儲結(jié)構(gòu)、遍歷運(yùn)算的實現(xiàn)以及它們之間的轉(zhuǎn)換。第48頁，共148頁，2023年，2月20日，星期六本章重點(diǎn)樹形結(jié)構(gòu)的概念；二叉樹的定義、存儲結(jié)構(gòu)和遍歷算法本章難點(diǎn)二叉樹的遍歷算法第49頁，共148頁，2023年，2月20日，星期六二叉樹或為空樹；或是由一個根結(jié)點(diǎn)加上兩棵分別稱為左子樹和右子樹的、互不交的二叉樹組成。ABCDEFGHK根結(jié)點(diǎn)左子樹右子樹第50頁，共148頁，2023年，2月20日，星期六二叉樹的五種基本形態(tài)：N空樹只含根結(jié)點(diǎn)NNNLRR右子樹為空樹L左子樹為空樹左右子樹均不為空樹第51頁，共148頁，2023年，2月20日，星期六二叉樹的重要特性性質(zhì)1:

在二叉樹的第i

層上至多有2i-1個結(jié)點(diǎn)。(i≥1)性質(zhì)2:

深度為k的二叉樹上至多含2k-1個結(jié)點(diǎn)（k≥1）性質(zhì)3:

對任何一棵二叉樹，若它含有n0個葉子結(jié)點(diǎn)、n2個度為2的結(jié)點(diǎn)，則必存在關(guān)系式：n0=n2+1兩類特殊的二叉樹：（1）滿二叉樹：指的是深度為k且含有2k-1個結(jié)點(diǎn)的二叉樹。（2）完全二叉樹：樹中所含的n個結(jié)點(diǎn)和滿二叉樹中編號為1至n的結(jié)點(diǎn)一一對應(yīng)。性質(zhì)4:

具有n個結(jié)點(diǎn)的完全二叉樹的深度為log2n+1第52頁，共148頁，2023年，2月20日，星期六性質(zhì)5:

若對含n個結(jié)點(diǎn)的完全二叉樹從上到下且從左至右進(jìn)行1至n的編號，則對完全二叉樹中任意一個編號為i的結(jié)點(diǎn)：

(1)若i=1，則該結(jié)點(diǎn)是二叉樹的根，無雙親,否則，編號為i/2的結(jié)點(diǎn)為其雙親結(jié)點(diǎn);

(2)若2i>n，則該結(jié)點(diǎn)無左孩子，

否則，編號為2i的結(jié)點(diǎn)為其左孩子結(jié)點(diǎn)；

(3)若2i+1>n，則該結(jié)點(diǎn)無右孩子結(jié)點(diǎn)，

否則，編號為2i+1的結(jié)點(diǎn)為其右孩子結(jié)點(diǎn)。第53頁，共148頁，2023年，2月20日，星期六二叉樹的存儲結(jié)構(gòu)1、二叉樹的順序存儲表示

適用于完全二叉樹或滿二叉樹。2、二叉樹的鏈?zhǔn)酱鎯Ρ硎?/p>

二叉鏈表三叉鏈表第54頁，共148頁，2023年，2月20日，星期六二叉樹遍歷

順著某一條搜索路徑巡訪二叉樹中的結(jié)點(diǎn)，使得每個結(jié)點(diǎn)均被訪問一次，而且僅被訪問一次。

遍歷算法先（根）序的遍歷算法中（根）序的遍歷算法后（根）序的遍歷算法以遍歷為基礎(chǔ)，可以實現(xiàn)二叉樹上的許多復(fù)雜運(yùn)算。第55頁，共148頁，2023年，2月20日，星期六

若二叉樹為空樹，則空操作；否則，（1）訪問根結(jié)點(diǎn)；（2）先序遍歷左子樹；（3）先序遍歷右子樹。先（根）序的遍歷算法：第56頁，共148頁，2023年，2月20日，星期六

若二叉樹為空樹，則空操作；否則，（1）中序遍歷左子樹；（2）訪問根結(jié)點(diǎn)；（3）中序遍歷右子樹。中（根）序的遍歷算法：第57頁，共148頁，2023年，2月20日，星期六

若二叉樹為空樹，則空操作；否則，（1）后序遍歷左子樹；（2）后序遍歷右子樹；（3）訪問根結(jié)點(diǎn)。后（根）序的遍歷算法：第58頁，共148頁，2023年，2月20日，星期六PreOrder:abcdegfhInOrder:cbegdfahPostOrder:cgefdbhaabcdefgh第59頁，共148頁，2023年，2月20日，星期六樹和森林

樹的三種存儲結(jié)構(gòu)雙親表示法孩子鏈表表示法孩子-兄弟存儲表示法

樹的遍歷先根遍歷后根遍歷層次遍歷

樹、森林與二叉樹的關(guān)系(相互轉(zhuǎn)換)注意：（1）與樹對應(yīng)的二叉樹的根結(jié)點(diǎn)的右子樹一定為空（2）和樹對應(yīng)的二叉樹，其左、右子樹的概念已改變?yōu)椋鹤笫呛⒆?，右是兄弟?0頁，共148頁，2023年，2月20日，星期六樹的帶權(quán)的路徑長度樹中所有葉子結(jié)點(diǎn)的帶權(quán)路徑長度之和

Huffman樹設(shè)有n個權(quán)值{w1,w2,……wn}，構(gòu)造一棵有n個葉子結(jié)點(diǎn)的二叉樹，每個葉子的權(quán)值為wi,則wpl最小的二叉樹叫Huffman樹哈夫曼算法判定樹和哈夫曼樹本章結(jié)束第61頁，共148頁，2023年，2月20日，星期六第五章圖第62頁，共148頁，2023年，2月20日，星期六第63頁，共148頁，2023年，2月20日，星期六本章總述本章主要討論圖這一重要的數(shù)據(jù)結(jié)構(gòu)。圖不同于線性結(jié)構(gòu)，也不同于樹形結(jié)構(gòu)，在任何兩個頂點(diǎn)之間都可能存在鄰接關(guān)系。圖的存儲結(jié)構(gòu)、圖的遍歷以及圖的應(yīng)用—最小生成樹、拓?fù)渑判?。?4頁，共148頁，2023年，2月20日，星期六本章重點(diǎn)圖的存儲結(jié)構(gòu)和連通圖的遍歷。本章難點(diǎn)

Prim算法。第65頁，共148頁，2023年，2月20日，星期六名詞和術(shù)語網(wǎng)、子圖完全圖、稀疏圖、稠密圖鄰接點(diǎn)、度、入度、出度路徑、路徑長度、簡單路徑、簡單回路連通圖、連通分量、強(qiáng)連通圖、強(qiáng)連通分量生成樹、生成森林第66頁，共148頁，2023年，2月20日，星期六圖的存儲結(jié)構(gòu)一、圖的數(shù)組(鄰接矩陣)存儲表示二、圖的鄰接表存儲表示鄰接表是圖的一種鏈?zhǔn)酱鎯Y(jié)構(gòu)。為圖中每個頂點(diǎn)建立一個單鏈表，第i個單鏈表中的結(jié)點(diǎn)表示依附于頂點(diǎn)Vi的邊（有向圖中指以Vi為尾的?。?。第67頁，共148頁，2023年，2月20日，星期六鄰接矩陣特點(diǎn)無向圖的鄰接矩陣是對稱矩陣；有向圖的鄰接矩陣不一定是對稱矩陣；判斷任意兩個點(diǎn)的鄰接關(guān)系容易；適用于稠密圖的表示。ABDCE0101000100000010010011000ABCDEABCDE第68頁，共148頁，2023年，2月20日，星期六鄰接表特點(diǎn)無向圖中:頂點(diǎn)Vi的度為第i個單鏈表中的結(jié)點(diǎn)數(shù)。有向圖中：頂點(diǎn)Vi的出度為第i個單鏈表中的結(jié)點(diǎn)個數(shù)；頂點(diǎn)Vi的入度需遍歷整個鄰接表,鄰接點(diǎn)域指向Vi的結(jié)點(diǎn)個數(shù)。第69頁，共148頁，2023年，2月20日，星期六圖的遍歷從圖中某個頂點(diǎn)出發(fā)訪問圖中每個頂點(diǎn)一次且僅一次的過程。連通圖深度優(yōu)先搜索連通圖廣度優(yōu)先搜索深度優(yōu)先搜索：V0V1V3V7V4V2V5V6廣度優(yōu)先搜索序列：V0V1V2V3V4V5V6V7V0V1V3V4V2V6V5V7第70頁，共148頁，2023年，2月20日，星期六從圖中某個頂點(diǎn)V0出發(fā)，訪問此頂點(diǎn)，然后依次從V0的各個未被訪問的鄰接點(diǎn)出發(fā)深度優(yōu)先搜索遍歷圖中的其余頂點(diǎn)，直至圖中所有和V0有路徑相通的頂點(diǎn)都被訪問到為止。連通圖的深度優(yōu)先搜索遍歷第71頁，共148頁，2023年，2月20日，星期六

從圖中的某個頂點(diǎn)V0出發(fā)，并在訪問此頂點(diǎn)之后依次訪問V0的所有未被訪問過的鄰接點(diǎn)，隨后按這些頂點(diǎn)被訪問的先后次序依次訪問它們的鄰接點(diǎn)，直至圖中所有與V0有路徑相通的頂點(diǎn)都被訪問到為止。連通圖的廣度優(yōu)先搜索遍歷第72頁，共148頁，2023年，2月20日，星期六最小生成樹問題的提出：假設(shè)要在n個城市之間建立通訊聯(lián)絡(luò)網(wǎng)，則連通n個城市只需要修建n-1條線路，如何在最節(jié)省經(jīng)費(fèi)的前提下建立這個通訊網(wǎng)？該問題等價于：構(gòu)造網(wǎng)的一棵最小生成樹，即：在e條帶權(quán)的邊中選取n-1條邊（不構(gòu)成回路），使“權(quán)值之和”為最小。第73頁，共148頁，2023年，2月20日，星期六最小生成樹構(gòu)造—普里姆Prim算法指定圖中某個頂點(diǎn)v作為生成樹的根，隨后往生成樹上添加新的頂點(diǎn)w。在添加的頂點(diǎn)w和已經(jīng)在生成樹上的頂點(diǎn)v之間必定存在一條邊，并且該邊的權(quán)值在所有連通頂點(diǎn)v和w之間的邊中取值最小。之后繼續(xù)往生成樹上添加頂點(diǎn)，直至生成樹上含有n個頂點(diǎn)為止。第74頁，共148頁，2023年，2月20日，星期六12abcdegf例如:1951418271682137aedcbgf所得生成樹權(quán)值和=14+8+3+5+16+21=67第75頁，共148頁，2023年，2月20日，星期六如何進(jìn)行拓?fù)渑判颍?/p>

1.從有向圖中選取一個沒有前驅(qū)的頂點(diǎn)，并輸出之；

2.從有向圖中刪去此頂點(diǎn)以及所有以它為尾的??；

重復(fù)上述兩步，直至圖空或者圖不空但找不到無前驅(qū)的頂點(diǎn)為止。第76頁，共148頁，2023年，2月20日，星期六3614752初始AOV網(wǎng)361475輸出結(jié)點(diǎn)2后36147輸出結(jié)點(diǎn)5后3647輸出結(jié)點(diǎn)1后367輸出結(jié)點(diǎn)4后67輸出結(jié)點(diǎn)3后6輸出結(jié)點(diǎn)7后空輸出結(jié)點(diǎn)6后本章結(jié)束第77頁，共148頁，2023年，2月20日，星期六第六章查找表第78頁，共148頁，2023年，2月20日，星期六第79頁，共148頁，2023年，2月20日，星期六本章總述本章主要介紹了查找表和查找的概念，查找表的分類，并分別詳細(xì)討論了靜態(tài)查找表與動態(tài)查找表的各種常用的實現(xiàn)方法。散列是一種重要的查找方法。散列技術(shù)的原始動機(jī)是無需鍵值比較而完成查找。第80頁，共148頁，2023年，2月20日，星期六本章重點(diǎn)二分查找二叉排序樹的查找散列表的查找本章難點(diǎn)二叉排序樹的插入算法第81頁，共148頁，2023年，2月20日，星期六查找表概念查找表是由同一類型的數(shù)據(jù)元素(或記錄)構(gòu)成的集合。由于“集合”中的數(shù)據(jù)元素之間存在著松散的關(guān)系，因此查找表是一種應(yīng)用靈活且方便的結(jié)構(gòu)。第82頁，共148頁，2023年，2月20日，星期六查找表的常見操作1）查詢某個“特定的”數(shù)據(jù)元素是否在查找表中；2）檢索某個“特定的”數(shù)據(jù)元素的各種屬性；3）在查找表中插入一個數(shù)據(jù)元素；4）從查找表中刪去某個數(shù)據(jù)元素。第83頁，共148頁，2023年，2月20日，星期六查找表的兩個類別：

靜態(tài)查找表僅作查詢和檢索操作的查找表。

動態(tài)查找表有時在查詢之后，還需要將“不在查找表中”的數(shù)據(jù)元素插入到查找表中；或者，從查找表中刪除其“查詢”結(jié)果為“在查找表中”的數(shù)據(jù)元素。第84頁，共148頁，2023年，2月20日，星期六靜態(tài)查找表一、順序查找表在等概率查找的情況下，順序表查找成功的平均查找長度為：二、有序查找表(二分查找)三、索引順序表靜態(tài)查找表的上述三種不同實現(xiàn)方法各有優(yōu)缺點(diǎn)。順序查找效率最低但限制最少；二分查找效率最高但限制最強(qiáng)；分塊查找則介于上述二者之間。第85頁，共148頁，2023年，2月20日，星期六動態(tài)查找表--二叉排序樹1．定義2．查找算法3．插入算法4．刪除算法5．查找性能的分析第86頁，共148頁，2023年，2月20日，星期六二叉排序樹定義二叉排序樹或者是一棵空二叉樹;或者是具有如下特性的二叉樹：（1）若它的左子樹不空，則左子樹上所有結(jié)點(diǎn)的值均小于根結(jié)點(diǎn)的值；（2）若它的右子樹不空，則右子樹上所有結(jié)點(diǎn)的值均大于根結(jié)點(diǎn)的值；（3）它的左、右子樹也都分別是二叉排序樹。

重要性質(zhì)：中根遍歷一棵二叉樹所得的結(jié)點(diǎn)訪問序列是鍵值的遞增序列。第87頁，共148頁，2023年，2月20日，星期六查找性能的分析對于每一棵特定的二叉排序樹，均可按照平均查找長度的定義來求它的ASL值，顯然，由值相同的n個關(guān)鍵字，構(gòu)造所得的不同形態(tài)的各棵二叉排序樹的平均查找長度的值不同，甚至可能差別很大。第88頁，共148頁，2023年，2月20日，星期六由關(guān)鍵字序列3，1，2，5，4構(gòu)造而得的二叉排序樹，由關(guān)鍵字序列1，2，3，4，5構(gòu)造而得的二叉排序樹，2134535412ASL=（1+2+3+4+5）/5=3ASL=（1+2+3+2+3）/5=2.2第89頁，共148頁，2023年，2月20日，星期六二叉平衡樹是二叉排序樹的另一種形式，其特點(diǎn)為：樹中每個結(jié)點(diǎn)的左、右子樹深度之差的絕對值不大于1，即548254821是平衡樹不是平衡樹構(gòu)造二叉平衡（查找）樹的方法是：在插入過程中，采用平衡旋轉(zhuǎn)技術(shù)。第90頁，共148頁，2023年，2月20日，星期六散列表

1)散列函數(shù)是一個映象，即：將關(guān)鍵字的集合映射到某個地址集合上，它的設(shè)置很靈活，只要不超出地址集合允許的范圍即可；

2)由于散列函數(shù)是一個壓縮映象，因此，在一般情況下，很容易產(chǎn)生“沖突”現(xiàn)象，即：key1key2，而H(key1)=H(key2)。第91頁，共148頁，2023年，2月20日，星期六構(gòu)造散列函數(shù)的方法對數(shù)字的關(guān)鍵字可有下列構(gòu)造方法：

1.數(shù)字分析法

2.平方取中法

3.基數(shù)轉(zhuǎn)換法

4.除留余數(shù)法

5.隨機(jī)數(shù)法實際造表時，采用何種構(gòu)造哈希函數(shù)的方法取決于建表的關(guān)鍵字集合的情況(包括關(guān)鍵字的范圍和形態(tài))，總的原則是使產(chǎn)生沖突的可能性降到盡可能地小。第92頁，共148頁，2023年，2月20日，星期六散列表按照組織形式的不同，通常有兩類散列表：開散列表與閉散列表。開散列表的組織方式：將所有散列地址相同的記錄都鏈接在同一鏈表中。閉散列表解決沖突的基本思想：為每個鍵值生成一個散列地址序列d0d1…di…dm-1

d0=H(K),是K的散列地址，其余di(0<i<m)是后繼散列地址。

線性探測法二次探測法

多重散列法公共溢出區(qū)法散列技術(shù)的原始動機(jī)是無需鍵值比較而完成查找。但由于同義詞的存在，不能實現(xiàn)。本章結(jié)束第93頁，共148頁，2023年，2月20日，星期六第七章文件第94頁，共148頁，2023年，2月20日，星期六第95頁，共148頁，2023年，2月20日，星期六本章總述本章針對在外存儲器中的數(shù)據(jù)，討論了它的組織方法和操作方法。文件結(jié)構(gòu)是以記錄的集合作為邏輯結(jié)構(gòu)。如何有效的實現(xiàn)文件結(jié)構(gòu)是本章的重點(diǎn)。本章著重介紹了順序文件、索引文件以及散列文件等幾種常見的組織方法。第96頁，共148頁，2023年，2月20日，星期六本章總要求

熟悉文件的概念；熟悉順序文件、索引文件和散列文件的組織方式和操作方式。第97頁，共148頁，2023年，2月20日，星期六通常將存放在外存中的數(shù)據(jù)稱為文件。文件是由特性相同的記錄所構(gòu)成的集合，每個記錄由一個或多個數(shù)據(jù)項構(gòu)成，這是文件的邏輯結(jié)構(gòu)。文件在存儲介質(zhì)（如磁盤和磁帶）上的實際組織方式稱為文件的存儲結(jié)構(gòu)或物理結(jié)構(gòu)，常見的有四種：順序組織、索引組織、散列組織和鏈組織。文件在外存儲器上組織結(jié)構(gòu)主要有三種：順序文件散列文件索引文件第98頁，共148頁，2023年，2月20日，星期六

ISAM文件索引順序存取方法ISAM(IndexedSequentialMethod)是一種專為磁盤存取設(shè)計的索引順序文件組織方式。

ISAM文件由多級主索引、柱面索引、磁道索引和主文件組成。第99頁，共148頁，2023年，2月20日，星期六

VSAM文件

VSAM(VirtualStorageAccessMethod)虛擬存儲存取方法，是一種索引順序文件的組織方式，采用動態(tài)索引結(jié)構(gòu)。

B-樹與B+樹定義

B-樹與B+樹的差異

B+樹廣泛的使用在包括VSAM文件在內(nèi)的多種文件系統(tǒng)中。本章結(jié)束第100頁，共148頁，2023年，2月20日，星期六第八章排序第101頁，共148頁，2023年，2月20日，星期六第102頁，共148頁，2023年，2月20日，星期六本章總述對于數(shù)據(jù)處理工作，排序是其最基本的運(yùn)算之一。為了提高計算機(jī)的工作效率，人們提出了各種各樣的排序方法和算法。本章重點(diǎn)介紹了5種內(nèi)部排序算法：直接插入排序、快速排序、直接選擇排序、堆排序和歸并排序。另外，也介紹了冒泡排序等。第103頁，共148頁，2023年，2月20日，星期六本章重點(diǎn)快速排序，堆排序。本章難點(diǎn)堆排序。第104頁，共148頁，2023年，2月20日，星期六什么是排序？所謂排序是指將一組“無序”的記錄序列調(diào)整為“有序”的記錄序列的過程。例如：下列是一組記錄對應(yīng)的關(guān)鍵字序列

(52,49,80,36,14,58,61,23,97,75)調(diào)整為

(14,23,36,49,52,58,61,75,80,97)第105頁，共148頁，2023年，2月20日，星期六內(nèi)部排序和外部排序若整個排序過程不需要訪問外存便能完成，則稱此類排序為內(nèi)部排序；反之，若參加排序的記錄數(shù)量很大，整個排序過程不可能在內(nèi)存中完成，則稱此類排序為外部排序。

第106頁，共148頁，2023年，2月20日，星期六內(nèi)部排序的方法按照內(nèi)部排序過程使用的基本手段可以將排序方法分為5個類別：插入排序交換排序選擇排序歸并排序分配排序第107頁，共148頁，2023年，2月20日，星期六

1.插入排序不斷地將無序子序列中的記錄“插入”到有序序列中，從而逐漸地增加有序子序列的長度，直到所有記錄都進(jìn)入有序序列中為止。直接插入排序（基于順序查找）折半插入排序（基于折半查找）第108頁，共148頁，2023年，2月20日，星期六

2.交換排序不斷地考查待排序列中關(guān)鍵字之間的有序性，一旦發(fā)現(xiàn)非有序關(guān)系，將其“交換”，直到所有記錄均按照有序性就位為止。冒泡排序快速排序第109頁，共148頁，2023年，2月20日，星期六

3.選擇排序不斷地從無序子序列中“選擇”關(guān)鍵字最小(或最大)者，并將其加入到有序子序列中，以此方法增加有序子序列的長度，直到所有的記錄都進(jìn)入有序序列中為止。簡單選擇排序堆排序第110頁，共148頁，2023年，2月20日，星期六

4.歸并排序通過“歸并”兩個或兩個以上的有序子序列，逐步增加有序序列的長度，直到所有的記錄都進(jìn)入一個有序序列中為止。

2-路歸并排序第111頁，共148頁，2023年，2月20日，星期六堆排序堆是滿足下列性質(zhì)的記錄序列{r1,r2,…，rn}：或堆的定義:{12,36,27,65,40,34,98,81,73,55,49}是小頂堆{12,36,27,65,40,14,98,81,73,55,49}不是堆(小頂堆)(大頂堆)1234567891011第112頁，共148頁，2023年，2月20日，星期六rir2ir2i+1通常將該記錄序列看作一棵完全二叉樹，則r2i

是ri

的左孩子；r2i+1

是ri

的右孩子。1236276549817355403498是堆14不第113頁，共148頁，2023年，2月20日，星期六

堆排序是指利用堆的特性對記錄序列進(jìn)行排序的一種排序方法?；具^程：1。根據(jù)原始記錄序列創(chuàng)建堆；2。將根與堆中的最后一個結(jié)點(diǎn)交換；3。將堆中的最后結(jié)點(diǎn)從堆中刪去；4。將剩余的結(jié)點(diǎn)重新調(diào)整成堆。第114頁，共148頁，2023年，2月20日，星期六1、如何“建初堆”？需要解決的兩個問題:2、如何調(diào)整“堆”？第115頁，共148頁，2023年，2月20日，星期六建“初堆”的基本方法：從堆中最后一個有孩子的結(jié)點(diǎn)開始利用調(diào)整。40554973816436122798（40,55,49,73,12,27,98,81,64,36)12368173499881735598494064361227第116頁，共148頁，2023年，2月20日，星期六9881497355641236274012在98和12進(jìn)行互換之后，破壞了“堆”的特性，因此，需要對它進(jìn)行“篩選”。98128173641298第117頁，共148頁，2023年，2月20日，星期六73496455129836274081在81和12進(jìn)行互換之后，破壞了“堆”的特性，因此，需要對它進(jìn)行“篩選”。1281比較1273比較645512第118頁，共148頁，2023年，2月20日，星期六73644955128198362740在73和12進(jìn)行互換之后，破壞了“堆”的特性，因此，需要對它進(jìn)行“篩選”。127312645512第119頁，共148頁，2023年，2月20日，星期六64554912738198362740在64和40進(jìn)行互換之后，破壞了“堆”的特性，因此，需要對它進(jìn)行“篩選”。6440405540第120頁，共148頁，2023年，2月20日，星期六55404912738198362764在55和27進(jìn)行互換之后，破壞了“堆”的特性，因此，需要對它進(jìn)行“篩選”。5527274927第121頁，共148頁，2023年，2月20日，星期六49402712738198365564在49和36進(jìn)行互換之后，破壞了“堆”的特性，因此，需要對它進(jìn)行“篩選”。49364036第122頁，共148頁，2023年，2月20日，星期六12273640738198495564排序后的記錄序列：{12，27，36，40，49，55，64，73，81，98}第123頁，共148頁，2023年，2月20日，星期六各種排序方法的綜合比較1.平均的時間性能時間復(fù)雜度為O(nlogn)：快速排序、堆排序和歸并排序時間復(fù)雜度為O(n2)：直接插入排序、冒泡排序和簡單選擇排序第124頁，共148頁，2023年，2月20日，星期六2.最壞時間性能時間復(fù)雜度為O(nlogn)：堆排序和歸并排序時間復(fù)雜度為O(n2)：快速排序、直接插入排序、冒泡排序和簡單選擇排序第125頁，共148頁，2023年，2月20日，星期六

3.當(dāng)待排記錄序列按關(guān)鍵字順序有序時直接插入排序和起泡排序能達(dá)到O(n)的時間復(fù)雜度，快速排序的時間性能退化為O(n2)。

4.簡單選擇排序、堆排序和歸并排序的時間性能不隨記錄序列中關(guān)鍵字的分布而改變。第126頁，共148頁，2023年，2月20日，星期六

5.空間性能指的是排序過程中所需的輔助空間大小

1.所有的簡單排序方法(包括：直接插入、起泡和簡單選擇)和堆排序的空間復(fù)雜度為O(1)；

2.快速排序為O(logn)，為遞歸程序執(zhí)行過程中，棧所需的輔助空間；

3.歸并排序所需輔助空間最多，其空間復(fù)雜度為O(n)。本章結(jié)束第127頁，共148頁，2023年，2月20日，星期六考情交流本課程的應(yīng)試方法和技巧復(fù)習(xí)技巧最近幾年必考的內(nèi)容考試情況的預(yù)測分析歷年考題真題示例講解第128頁，共148頁，2023年，2月20日，星期六本課程的應(yīng)試方法和技巧通過對歷年自考試卷的分析和以往教學(xué)環(huán)節(jié)的整理總結(jié)，我認(rèn)為這門課程大家學(xué)習(xí)的時候要以本課程大綱中所確定的識記、領(lǐng)會和應(yīng)用的有關(guān)要求為依據(jù)，同時要求大家認(rèn)真分析歷屆的真題，抓住考題的方向和規(guī)律，將理論和實際的應(yīng)用聯(lián)系與結(jié)合起來。大家一定要注意，不是書上所有的東西都要背下來，而是要根據(jù)不同的知識結(jié)構(gòu)特點(diǎn)，記住基礎(chǔ)知識，領(lǐng)會基本原理，認(rèn)真思考實際應(yīng)用。第129頁，共148頁，2023年，2月20日，星期六復(fù)習(xí)技巧1.注意歸納整理2.注意聯(lián)系實際3.熟記基礎(chǔ)理論4.學(xué)會獨(dú)立思考第130頁，共148頁，2023年，2月20日，星期六考試題型一、單項選擇題二、填空題三、應(yīng)用題四、算法設(shè)計題第131頁，共148頁，2023年，2月20日，星期六最近幾年必考的內(nèi)容1這幾年出題頻率高的知識點(diǎn)如下：1.線性表的插入刪除（順序表、鏈表）2.數(shù)組、矩陣的存儲（地址計算）3.二叉樹的相關(guān)性質(zhì)、存儲以及遍歷等算法4.圖的鄰接表存儲第132頁，共148頁，2023年，2月20日，星期六

5.Prim算法構(gòu)造最小生成樹

6.散列表的構(gòu)建及平均查找長度分析

7.構(gòu)建二叉排序樹

8.排序方法，如：冒泡排序、直接插入排序、快速排序；堆排序的過程（建立初始堆、調(diào)整堆）最近幾年必考的內(nèi)容2第133頁，共148頁，2023年，2月20日，星期六考試情況的預(yù)測分析根據(jù)歷年來的考題分析推理，我預(yù)計（只代表個人意見）這門課的出題方向主要集中在以下知識環(huán)節(jié)上：

1.線性表的存儲結(jié)構(gòu)及操作（順序表、鏈表）

2.基本概念理論（棧、循環(huán)隊列的特點(diǎn)等）

3.數(shù)組、矩陣的存儲

4.二叉樹的相關(guān)性質(zhì)、存儲及遍歷算法

5.圖的存儲結(jié)構(gòu)及應(yīng)用（鄰接矩陣、鄰接表）

6.散列表的構(gòu)建及平均查找長度分析

7.各種排序方法排序過程及時間復(fù)雜度分析第134頁，共148頁，2023年，2月20日，星期六

1.單項選擇題：若在長度為n的順序表中插入一個結(jié)點(diǎn)，則其結(jié)點(diǎn)的移動次數(shù)（）。

A、最少為0，最多為n

B、最少為1，最多為n

C、最少為0，最多為n+1

D、最少為1，最多為n+1

答案：A歷年考題真題示例講解第135頁，共148頁，2023年，2月20日，星期六

2.填空題：對順序表執(zhí)行刪除操作，其刪除算法的平均時間復(fù)雜性為

（n-1）/2

。

其他算法定位算法：平均時間復(fù)雜性量級為O(n)求表長算法、讀表元算法：時間復(fù)雜性為O(1).第136頁，共148頁，2023年，2月20日，星期六3.選擇題：設(shè)一個棧的輸入序列是a，b，c，d，則所得到的輸出序列（輸入過程中允許出棧）不可能出現(xiàn)的是（D）

A．a(chǎn)，b，c，d B.a，b，d，cC.d，c，b，a D.c，d，a，b第137頁，共14