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

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

串講

主講教師：杜永萍

概述

《數(shù)據(jù)結(jié)構(gòu)導(dǎo)論》是計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)的一門必修課程。本

課程介紹如何組織各種數(shù)據(jù)在計(jì)算機(jī)中的存儲、傳遞和轉(zhuǎn)換。

內(nèi)容包括：線性表、棧、隊(duì)列、串、數(shù)組、樹、二叉樹、圖等基

本數(shù)據(jù)結(jié)構(gòu)及其應(yīng)用；排序和查找的原理與方法；數(shù)據(jù)在外存上的組

織方法。

第一章概論

引方

數(shù)據(jù)元素和數(shù)據(jù)以

數(shù)據(jù)、邏輯結(jié)構(gòu)和運(yùn)鄲數(shù)據(jù)的邏輯結(jié)構(gòu)

運(yùn)算和基布運(yùn)算

存儲實(shí)現(xiàn)

存儲實(shí)現(xiàn)和運(yùn)雪實(shí)現(xiàn)

概論運(yùn)算實(shí)現(xiàn)

正珅性

算法分析易讀性

健H性

高效率

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

數(shù)據(jù)結(jié)構(gòu)被其評價(jià)和選掙1

數(shù)據(jù)結(jié)構(gòu)的泮價(jià)和選擇

本章總述

要求熟悉各名詞、術(shù)語的含義，掌握基本概念。包括數(shù)據(jù)、數(shù)據(jù)

元素、數(shù)據(jù)項(xiàng)、邏輯關(guān)系和邏輯結(jié)構(gòu)、運(yùn)算和基本運(yùn)算、數(shù)據(jù)結(jié)構(gòu)、

存儲方式和存儲結(jié)構(gòu)、算法及算法分析等。

注意這些概念之間的聯(lián)系。

本章重點(diǎn)

邏輯結(jié)構(gòu)和數(shù)據(jù)結(jié)構(gòu)的概念。

本章難點(diǎn)

算法的時(shí)間復(fù)雜性分析。

本章知識點(diǎn)

1.數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項(xiàng)

數(shù)據(jù)一能被計(jì)算機(jī)存儲、加工的對象通稱為數(shù)據(jù)。

數(shù)據(jù)元素一是數(shù)據(jù)的基本單位，在程序中作為一個(gè)整體來考慮和

處理。具有完整確定的實(shí)際意義。

數(shù)據(jù)項(xiàng)一是數(shù)據(jù)不可分割的最小標(biāo)識單位。數(shù)據(jù)元素可由若干個(gè)

數(shù)據(jù)項(xiàng)組成，數(shù)據(jù)項(xiàng)通常不具有完整確定的實(shí)際意義。

數(shù)據(jù)、數(shù)據(jù)元素和數(shù)據(jù)項(xiàng)構(gòu)成了數(shù)據(jù)組織的三個(gè)層次，如下圖所

不：

數(shù)據(jù)元素

O

O數(shù)據(jù)項(xiàng)

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)o?o?o?o

樹形結(jié)構(gòu)

圖狀結(jié)構(gòu)

集合結(jié)構(gòu)°cPo

存儲結(jié)構(gòu)：邏輯結(jié)構(gòu)在計(jì)算機(jī)中的表示（映像）被稱為存儲結(jié)構(gòu),

其中應(yīng)該包含數(shù)據(jù)元素的內(nèi)容及其關(guān)系的表示。

四種基本存儲方式：

順序存儲方式

特點(diǎn)：借助于數(shù)據(jù)元素在存儲器中的位置來表示數(shù)據(jù)元素之間的

邏輯關(guān)系

鏈?zhǔn)酱鎯Ψ绞?/p>

特點(diǎn)：借助指示元素存儲地址的指針來表示數(shù)據(jù)元素之間的邏輯

關(guān)系

索引存儲方式

散列存儲方式

3.算法

算法就是解決問題的方法。

算法分析主要從時(shí)間復(fù)雜度、空間復(fù)雜度方面進(jìn)行算法分析。

時(shí)間復(fù)雜度:最壞情況時(shí)間復(fù)雜度，平均時(shí)間復(fù)雜度。

本章結(jié)束

第二章線性表

線性結(jié)構(gòu)

線性表的舉本概念

線性表

瞋序表

茂性表的順序?qū)崿F(xiàn)基本運(yùn)葬在帕序表上的灰現(xiàn)

順序?qū)崿F(xiàn)的算法分析

（單處表

線性表的進(jìn)接實(shí)現(xiàn)<單處表的簡單操作

建性表（基本運(yùn)駕在單盜表上的實(shí)現(xiàn)

（建表

其他運(yùn)算在單鞋表上的實(shí)現(xiàn)<

I清除電史結(jié)點(diǎn)

循環(huán)鏈表

其他漣表

雙燧表

（空間性能

順序?qū)崿F(xiàn)與鏈接實(shí)現(xiàn)的比較\

I時(shí)間性能

串的基本概念

串串的基本運(yùn)算

山的（中的順序存儲

串的存儲\

I串的犍接存儲

本章總述

本章主要討論了線性表及它的兩種存儲實(shí)現(xiàn)：順序?qū)崿F(xiàn)和鏈接實(shí)

現(xiàn)；另外，簡單介紹了串這種特殊的線性表的運(yùn)算和存儲實(shí)現(xiàn)。

線性表是一種最簡單最常見的數(shù)據(jù)結(jié)構(gòu)

本章重點(diǎn)

線性結(jié)構(gòu)的定義和特點(diǎn)；

線性表的運(yùn)算；

順序表和單鏈表的組織方法和算法設(shè)計(jì)。

本章難點(diǎn)

單鏈表上的算法設(shè)計(jì)。

線性表的邏輯結(jié)構(gòu)定義

線性表是一個(gè)含有n個(gè)數(shù)據(jù)元素的有限序列。

線性表長度

直接前驅(qū)直接后繼

線性結(jié)構(gòu)的基本特征：

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

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

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

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

4.除第一元素之外，均有唯一的前驅(qū)。

順序存儲結(jié)構(gòu)

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

順序表特點(diǎn)：

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

屬隨機(jī)存取的存儲結(jié)構(gòu)。

假設(shè)線性表中每個(gè)元素

需占用L個(gè)存儲單元

LOC(ai+1)=LOC(aj)+L

L:一個(gè)數(shù)據(jù)元素所占存儲量

LOC(aj)

=LOC(ax)+(i-l)*L

T基地址

插入、刪除算法的分析

n+1

插入算法的數(shù)學(xué)期望值Eis=EPi(n-i+l)

Z=1

n

刪除算法的數(shù)學(xué)期望值

Edi=E*(〃—

i=\

設(shè)：Pi=l/(n+1),q^l/n,則可以得出：

1n+1

In

Eis=E(〃-2+l)=—

〃+li=l2

1〃n-1

E

di=-Z(〃—i)=一

nz=i2

順序表表示的優(yōu)缺點(diǎn)

優(yōu)點(diǎn)：

隨機(jī)存取表中的任一結(jié)點(diǎn)。

缺點(diǎn)：

插入和刪除運(yùn)算不方便，須移動(dòng)大量的結(jié)點(diǎn)；存儲分配只能預(yù)先

分配。

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

用一組任意的存儲單元（可能不連續(xù)）

存儲線性表的數(shù)據(jù)元素。

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

數(shù)據(jù)域指針域

該數(shù)據(jù)元素的

數(shù)據(jù)元素內(nèi)容直接后繼地址

L=(al,a2,a3,a4,a5,a6)

L

a1a2―?a3a4—?a5A

以線性表中第一個(gè)數(shù)據(jù)元素4的存儲地址作為線性表的地址,

稱作線性表的頭指針。

L

Illia1a2)anA

結(jié)點(diǎn)

有時(shí)為了操作方便，在第一個(gè)結(jié)點(diǎn)之前附設(shè)一個(gè)“頭結(jié)點(diǎn)”，以

指向頭結(jié)點(diǎn)的指針為鏈表的頭指針

指針域?yàn)榭?/p>

二含有頭結(jié)點(diǎn)的空表

特點(diǎn)：

邏輯順序與物理順序有可能不一致。

屬順序存取的存儲結(jié)構(gòu)，即存取每個(gè)數(shù)據(jù)元素所花

費(fèi)的時(shí)間不相等。

其它形式的鏈表

1.雙向鏈表(doublelinkedlist)

每個(gè)結(jié)點(diǎn)有兩個(gè)指針域

priordatanext

特點(diǎn)：克服單鏈表的單向性

2.循環(huán)鏈表

表中最后一個(gè)結(jié)點(diǎn)的指針域指向頭結(jié)點(diǎn)，鏈表形成一個(gè)環(huán)。

特點(diǎn)

從表中任何一個(gè)結(jié)點(diǎn)出發(fā)可掃描整個(gè)鏈表中的所有結(jié)點(diǎn)。

順序?qū)崿F(xiàn)與鏈接實(shí)現(xiàn)的比較

時(shí)間性能比較

定位運(yùn)算：順序表和單鏈表，均為0(a)

讀表元：順序表-0(1)(隨機(jī)存取)；

單鏈表-0(n)

鏈入/摘除：順序表-0(n);

單鏈表-0(1)(插入、刪除方便)

第三章棧、隊(duì)列和數(shù)組

P

再

注^

名*

2

N

^”

"

2

松筆龍晉*

上-

￡

明H

R

上三2

1

■

￡

京4

3

,

上職叵附后京M水

親2

Y位

W世

京W

雙3

3

a坐

理宏密M

W

將里三Y

8

1

3

/

出M出一

Y壬

￡

s

Y

卻,父

￡對自—自出

圖S

U官出

b愎

因^

出

ft

鼻曲N

)

,浜

.

M

為s

營

m

祥3

?*

芝然珞f

黑里1

機(jī)蚯

祟4

/薄

上W

e

1

J單舉

苗g

城色5聒

篋期

9世

^

2

￡合金妻

左<

￡

￡

3君

￡

金，紐w卻

7

M

”錄正—

W總

或旬

「卻

5總

先3

都

&

，

%顯

本章總述

棧和隊(duì)列是兩種常用的數(shù)據(jù)結(jié)構(gòu)，這兩種結(jié)構(gòu)與線性表有密切的

聯(lián)系。

棧和隊(duì)列的邏輯結(jié)構(gòu)是線性結(jié)構(gòu)，它們的基本運(yùn)算與線性表的基

本運(yùn)算十分類似，可看作是運(yùn)算受限的線性表。

數(shù)組與線性表也有密切的聯(lián)系。

本章重點(diǎn)

棧和隊(duì)列的特點(diǎn)；

順序棧和鏈棧上基本運(yùn)算的實(shí)現(xiàn)和簡單算法;

鏈隊(duì)上基本運(yùn)算實(shí)現(xiàn)和簡單算法設(shè)計(jì)。

本章難點(diǎn)

循環(huán)隊(duì)的組織，隊(duì)滿、隊(duì)空的條件及算法設(shè)計(jì)。

棧的類型定義

插入、刪除只在表尾進(jìn)行的線性表被稱為棧。

插入

ala2a3a4????an

刪除

棧的特點(diǎn)

后進(jìn)先出----UFO

(LastInFirstOut)

棧頂浮動(dòng)

棧底固定

棧的表示和實(shí)現(xiàn)

順序存儲結(jié)構(gòu):

順序棧

鏈?zhǔn)酱鎯Y(jié)構(gòu):

鏈棧

隊(duì)列定義

若線性表的插入操作在一端進(jìn)行，刪除操作在另一端進(jìn)

行，則稱此線性表為隊(duì)列。

隊(duì)頭front隊(duì)尾rear

刪除端插入端

隊(duì)列特點(diǎn)

FIFO

(FirstInFirstOut)

隊(duì)頭、隊(duì)尾均是浮動(dòng)的

隊(duì)列類型的實(shí)現(xiàn)

鏈隊(duì)列——鏈?zhǔn)接诚?/p>

循環(huán)隊(duì)列一一順序映象

隊(duì)列的順序存儲結(jié)構(gòu)

入隊(duì)

Q[rear++]=e;

4rear

3q4

出隊(duì)

2q3

e=Q[front++]

1q2

0qi4front

隊(duì)列的順序存儲結(jié)構(gòu)

<rear

q4

q3

q2“假溢出”現(xiàn)象

qi4front

解決的方法：

將隊(duì)列構(gòu)成環(huán)狀

7

循環(huán)隊(duì)列

隊(duì)歹U空：sq.rear=sq.front隊(duì)歹U滿：((sq.rear+1)%maxsize)==sq.front;

數(shù)組

是一種已經(jīng)在高級語言中實(shí)現(xiàn)了的數(shù)據(jù)結(jié)構(gòu)0

通常采用順序存儲結(jié)構(gòu)來存放數(shù)組。

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

1）以行序?yàn)橹餍颍ǖ拖聵?biāo)優(yōu)先）;

2）以列序?yàn)橹餍颍ǜ呦聵?biāo)優(yōu)先）;

以“行序?yàn)橹餍颉钡拇鎯τ诚?/p>

例如：

ao,oao,la0,2

al,oal,lal,2

二維數(shù)組A中任一元素ajj的存儲位置

LOC(i,j)=LOC(O,0)+(b2Xi+j)XL

i1

稱為基地址或基址。

矩陣的壓縮存儲

矩陣可用二維數(shù)組來表示。實(shí)際問題中，會碰到階數(shù)高的矩陣,

但存在許多值相同的元素和零元素。

壓縮存儲的基本思想：值相同的多個(gè)元素只分配一個(gè)存儲空間,

零元素不分配空間。

特殊矩陣的壓縮存儲（對稱矩陣，三角矩陣）

稀疏矩陣的壓縮存儲（三元組順序表）

第四章樹

樹的基本概念

（二叉樹的范本概念

二叉樹I二叉樹的性質(zhì)

二叉樹的鏈?zhǔn)酱鎯Y(jié)構(gòu)

｛二叉樹的順序存儲結(jié)構(gòu)

（先根遍歷

二叉樹的遍歷｛中根遍歷

I后根遍歷

（簡單遞歸消除

遞歸消除＜

（基于棧的遞歸消除

孩子被表表表示法

孩子兄弟盛表表示法

（雙親表示法

〈（先根遍歷

樹的遍歷J中根遍歷

（后根遍歷

'樹、森林與二叉樹的關(guān)系

（分類與判定樹

判定樹和哈夫曼樹\

I哈夫曼樹與哈夫曼算法

本章總述

本章是數(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)算的實(shí)現(xiàn)

以及它們之間的轉(zhuǎn)換。

本章重點(diǎn)

樹形結(jié)構(gòu)的概念；

二叉樹的定義、存儲結(jié)構(gòu)和遍歷算法

本章難點(diǎn)

二叉樹的遍歷算法

二叉樹或?yàn)榭諛洌换蚴怯梢粋€(gè)根結(jié)點(diǎn)加上兩棵分別稱為左子樹和

右子樹的、互不交的二叉樹組成。

二叉樹的五種基本形態(tài):

只含根結(jié)點(diǎn)

空樹

Q

六不切卜小六就左右子樹均不

右子樹為空樹左子樹為仝樹為其田

7LRLR

二叉樹的重要特性

性質(zhì)1:在二叉樹的第，層上至多有Z-，個(gè)結(jié)點(diǎn)。（1^1）

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

性質(zhì)3:對任何一棵二叉樹，若它含有nO個(gè)葉子結(jié)點(diǎn)、n2個(gè)度

為2的結(jié)點(diǎn)，則必存在關(guān)系式：nO=n2+l

兩類特殊的二叉樹：

（1）滿二叉樹：指的是深度為k且含有2k-1個(gè)結(jié)點(diǎn)的二叉樹。

（2）完全二叉樹：樹中所含的n個(gè)結(jié)點(diǎn)和滿二叉樹中編號為1至

n的結(jié)點(diǎn)---對應(yīng)。

性質(zhì)4:具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為Llog2nJ+1

性質(zhì)5:若對含n個(gè)結(jié)點(diǎn)的完全二叉樹從上到下且從左至右進(jìn)行

1至n的編號，則對完全二叉樹中任意一個(gè)編號為i的結(jié)點(diǎn)：

(1)若則該結(jié)點(diǎn)是二叉樹的根，無雙親，否則，編號為

Li/2j的結(jié)點(diǎn)為其雙親結(jié)點(diǎn)；

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

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

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

否則，編號為2i+l的結(jié)點(diǎn)為其右孩子結(jié)點(diǎn)。

二叉樹的存儲結(jié)構(gòu)

1、二叉樹的順序存儲表示

適用于完全二叉樹或滿二叉樹。

2、二叉樹的鏈?zhǔn)酱鎯Ρ硎?/p>

二叉鏈表

三叉鏈表

二叉樹遍歷

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

問一次，而且僅被訪問一次。

遍歷算法

先（根）序的遍歷算法

中（根）序的遍歷算法

后（根）序的遍歷算法

以遍歷為基礎(chǔ)，可以實(shí)現(xiàn)二叉樹上的許多復(fù)雜運(yùn)算。

先(根)序的遍歷算法:

若二叉樹為空樹，則空操作；否則,

(1)訪問根結(jié)點(diǎn)；

(2)先序遍歷左子樹；

(3)先序遍歷右子樹。

中(根)序的遍歷算法:

若二叉樹為空樹，則空操作;否貝I」,

(1)中序遍歷左子樹；

(2)訪問根結(jié)點(diǎn)；

(3)中序遍歷右子樹。

后(根)序的遍歷算法:

若二叉樹為空樹，則空操作；否則,

(1)后序遍歷左子樹；

(2)后序遍歷右子樹；

(3)訪問根結(jié)點(diǎn)。

a

PreOrder:abcdegfh

Lb)也

InOrder:cbegdfah

PostOrder:cgefdbha

樹和森林

樹的三種存儲結(jié)構(gòu)

雙親表示法孩子鏈表表示法孩子-兄弟存儲表示法

樹的遍歷

先根遍歷后根遍歷層次遍歷

樹、森林與二叉樹的關(guān)系(相互轉(zhuǎn)換)

注意：

(1)與樹對應(yīng)的二叉樹的根結(jié)點(diǎn)的右子樹一定為空

(2)和樹對應(yīng)的二叉樹，其左、右子樹的概念已改變?yōu)椋?/p>

左是孩子，右是兄弟

判定樹和哈夫曼樹

樹的帶權(quán)的路徑長度

樹中所有葉子結(jié)點(diǎn)的帶權(quán)路徑長度之和

n

wp/=工3Jk

k=1

其^中：wk尤又不苴

lL.——結(jié)點(diǎn)到根的跨徑長度

Huffman樹

設(shè)有n個(gè)權(quán)值｛wpW2,...wj,構(gòu)造一棵有n個(gè)葉子結(jié)點(diǎn)的二叉樹,

每個(gè)葉子的權(quán)值為叫，貝Uwpl最小的二叉樹叫Huffman樹

哈夫曼算法

本章結(jié)束

第五章圖

圖的實(shí)際背景

圖的基本概念

圖的定義和術(shù)語

'轉(zhuǎn)接矩陣

圖的存儲結(jié)構(gòu)

、鄰接表

圖的遍歷連通圖的深，度優(yōu)先拽索

連通圖的I'度優(yōu)先搜索

圖的連通分戰(zhàn)計(jì)算

最小生成樹

拓?fù)渑判?/p>

本章總述

本章主要討論圖這一重要的數(shù)據(jù)結(jié)構(gòu)。圖不同于線性

結(jié)構(gòu)，也不同于樹形結(jié)構(gòu)，在任何兩個(gè)頂點(diǎn)之間都可能存

在鄰接關(guān)系。

圖的存儲結(jié)構(gòu)、圖的遍歷以及圖的應(yīng)用一最小生成樹、

拓?fù)渑判颉?/p>

本章重點(diǎn)

圖的存儲結(jié)構(gòu)和連通圖的遍歷O

本章難點(diǎn)

Prim算法。

名詞和術(shù)語

網(wǎng)、子圖

完全圖、稀疏圖、稠密圖

鄰接點(diǎn)、度、入度、出度

路徑、路徑長度、簡單路徑、簡單回路

連通圖、連通分量、強(qiáng)連通圖、強(qiáng)連通分量

生成樹、生成森林

圖的存儲結(jié)構(gòu)

一、圖的數(shù)組（鄰接矩陣）存儲表示

二、圖的鄰接表存儲表示

鄰接表是圖的一種鏈?zhǔn)酱鎯Y(jié)構(gòu)。

為圖中每個(gè)頂點(diǎn)建立一個(gè)單鏈表，第i個(gè)單鏈表中的結(jié)點(diǎn)表示依

附于頂點(diǎn)Vi的邊（有向圖中指以Vi為尾的弧）。

鄰接矩陣特點(diǎn)

無向圖的鄰接矩陣是對稱矩陣；

有向圖的鄰接矩陣不一定是對稱矩陣;

判斷任意兩個(gè)點(diǎn)的鄰接關(guān)系容易;

ABCDE

適用于稠密圖的表示。

A01010

B00100

C00001

D00100

E11000

鄰接表特點(diǎn)

無向圖中：頂點(diǎn)Vi的度為第i個(gè)單鏈表中的結(jié)點(diǎn)數(shù)。

有向圖中：

頂點(diǎn)Vi的出度為第i個(gè)單鏈表中的結(jié)點(diǎn)個(gè)數(shù)；

頂點(diǎn)Vi的入度需遍歷整個(gè)鄰接表,鄰接點(diǎn)域指向Vi的結(jié)點(diǎn)個(gè)數(shù)。

圖的遍歷

從圖中某個(gè)頂點(diǎn)出發(fā)訪問圖中每個(gè)頂點(diǎn)一次且僅一次的過程。

連通圖深度優(yōu)先搜索

連通圖廣度優(yōu)先搜索

深度優(yōu)先搜索：VOnVInV3nV7nV4nV2nV5nV6

廣度優(yōu)先搜索序列：V0=>VInV2nV3nV4nV5nV6nV7

V7

連通圖的深度優(yōu)先搜索遍歷

從圖中某個(gè)頂點(diǎn)V0出發(fā)，訪問此頂點(diǎn)，然后依次從

V0的各個(gè)未被訪問的鄰接點(diǎn)出發(fā)深度優(yōu)先搜索遍歷圖

中的其余頂點(diǎn)，直至圖中所有和V0有路徑相通的頂點(diǎn)

都被訪問到為止。

連通圖的廣度優(yōu)先搜索遍歷

從圖中的某個(gè)頂點(diǎn)V0出發(fā)，并在訪問此頂點(diǎn)之后依次訪

問V0的所有未被訪問過的鄰接點(diǎn)，隨后按這些頂點(diǎn)被訪問

的先后次序依次訪問它們的鄰接點(diǎn)，直至圖中所有與V0有

路徑相通的頂點(diǎn)都被訪問到為止。

最小生成樹

問題的提出：假設(shè)要在〃個(gè)城市之間建立通訊聯(lián)絡(luò)網(wǎng)，則連通

n個(gè)城市只需要修建〃々條線路，如何在最節(jié)省經(jīng)費(fèi)的前提下建立這

個(gè)通訊網(wǎng)？

該問題等價(jià)于：構(gòu)造網(wǎng)的一棵最小生成樹，即：在e條帶權(quán)的

邊中選取n-1條邊（不構(gòu)成回路），使“權(quán)值之和”為最小。

最小生成樹構(gòu)造一普里姆Prim算法

指定圖中某個(gè)頂點(diǎn)v作為生成樹的根，隨后往生成樹上添

加新的頂點(diǎn)Wo

在添加的頂點(diǎn)W和已經(jīng)在生成樹上的頂點(diǎn)V之間必定存在

一條邊，并且該邊的權(quán)值在所有連通頂點(diǎn)V和W之間的邊中

取值最小。之后繼續(xù)往生成樹上添加頂點(diǎn)，直至生成樹上含有

n個(gè)頂點(diǎn)為止。

例如:

19

b5

12

4

18

18

21

所得生成樹權(quán)值和

=14+8+3+5+16+21=67

如何進(jìn)行拓?fù)渑判?

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

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

重復(fù)上述兩步，直至圖空或者圖不空但找不到無前驅(qū)的頂點(diǎn)為止。

66

空

7

輸出結(jié)點(diǎn)1后輸出結(jié)點(diǎn)4后輸出結(jié)點(diǎn)3后輸出結(jié)點(diǎn)7后輸出結(jié)點(diǎn)6后

本章結(jié)束

第六章查找表

（集合的基本概念

基本概念｛

I杳找表的基本概念

嘴序表上的查找

有序表上的查找

（索引順序表上的直找

查找表（二叉排序樹上的查找

一叉排序樹\二叉排序樹的插入

I二義排序樹的刪除

1平衡二叉排序利

（數(shù)字分析法

除余法

散列函數(shù)的構(gòu)造法T方取中法

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

I隨機(jī)算注

查找

散列表動(dòng)態(tài)查找表在開散列表上的實(shí)現(xiàn)插入

（蒯除

'線性探測法

二次探照法

動(dòng)態(tài)查找表在M散列表上的實(shí)NL

多重散列法

公共沿出區(qū)法

開散列表與閉數(shù)列表的比較

本章總述

本章主要介紹了查找表和查找的概念，查找表的分類，并分別詳

細(xì)討論了靜態(tài)查找表與動(dòng)態(tài)查找表的各種常用的實(shí)現(xiàn)方法。

散列是一種重要的查找方法。散列技術(shù)的原始動(dòng)機(jī)是無需鍵值比

較而完成查找。

本章重點(diǎn)

二分查找

二叉排序樹的查找

散列表的查找

本章難點(diǎn)

二叉排序樹的插入算法

查找表概念

查找表是由同一類型的數(shù)據(jù)元素（或記錄）構(gòu)成的集合。

由于“集合”中的數(shù)據(jù)元素之間存在著松散的關(guān)系，因此查找表

是一種應(yīng)用靈活且方便的結(jié)構(gòu)。

查找表的常見操作

1）查詢某個(gè)“特定的”數(shù)據(jù)元素是否在查找表中;

2）檢索某個(gè)“特定的”數(shù)據(jù)元素的各種屬性；

3）在查找表中插入一個(gè)數(shù)據(jù)元素；

4）從查找表中刪去某個(gè)數(shù)據(jù)元素。

查找表的兩個(gè)類別:

靜態(tài)查找表

僅作查詢和檢索操作的查找表。

動(dòng)態(tài)查找表

有時(shí)在查詢之后，還需要將“不在查找表中”的數(shù)據(jù)元素插

入到查找表中；或者，從查找表中刪除其“查詢”結(jié)果為“在查

找表中”的數(shù)據(jù)元素。

靜態(tài)查找表

一、順序查找表

在等概率查找的情況下，順序表查找成功的平均查找長度為:

1n+\

ASL優(yōu)=一一+1）=

〃,=12

二、有序查找表（二分查找）

1Z2+1

ASLb=—ZC=--------log2(?+1)-1

nn

三、索引順序表

靜態(tài)查找表的上述三種不同實(shí)現(xiàn)方法各有優(yōu)缺點(diǎn)。

順序查找效率最低但限制最少；

二分查找效率最高但限制最強(qiáng)；

分塊查找則介于上述二者之間。

動(dòng)態(tài)查找表一二叉排序樹

1.定義

2.查找算法

3.插入算法

4.刪除算法

5.查找性能的分析

二叉排序樹定義

二叉排序樹或者是一棵空二叉樹;或者是具有如下特性的二叉樹:

(1)若它的左子樹不空，則左子樹上所有結(jié)點(diǎn)的值均小于根結(jié)

點(diǎn)的值；

(2)若它的右子樹不空，則右子樹上所有結(jié)點(diǎn)的值均大于根結(jié)

點(diǎn)的值；

(3)它的左、右子樹也都分別是二叉排序樹。

重要性質(zhì)：中根遍歷一棵二叉樹所得的結(jié)點(diǎn)訪問序列是鍵值的遞

增序列。

查找性能的分析

對于每一棵特定的二叉排序樹，均可按照平均查找長度的定

義來求它的ASL值，顯然，由值相同的n個(gè)關(guān)鍵字，構(gòu)造所得

的不同形態(tài)的各棵二叉排序樹的平均查找長度的值不同，甚至可

能差別很大。

1

由關(guān)鍵字序列1,2,3,4,5構(gòu)造而得的二小

叉排序樹，

%)

ASL=(1+2+3+4+5)/5

=3(5

由關(guān)鍵字序列3,1,2,5,4構(gòu)造而得的二叉排序

樹，

Cl)(5

ASL=(1+2+3+2+3)/5

=2.2

②④

二叉平衡樹是二叉排序樹的另一種形式，其特點(diǎn)為：

樹中每個(gè)結(jié)點(diǎn)的左、右子樹深度之差的絕對值不大于1,即

構(gòu)造二叉平衡（查找）樹的方法是:

在插入過程中，采用平衡旋轉(zhuǎn)技術(shù)。

散列表

1)散列函數(shù)是一個(gè)映象，即：

將關(guān)鍵字的集合映射到某個(gè)地址集合上，

它的設(shè)置很靈活，只要不超出地址集合允許的范圍即可；

2)由于散列函數(shù)是一個(gè)壓縮映象，因此，在一般情況下，很容易

產(chǎn)生“沖突”現(xiàn)象，即：keylwkey2,而H(keyl)=H(key2)o

構(gòu)造散列函數(shù)的方法

對數(shù)字的關(guān)鍵字可有下列構(gòu)造方法：

1.數(shù)字分析法

2.平方取中法

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

4.除留余數(shù)法

5.隨機(jī)數(shù)法

實(shí)際造表時(shí)，采用何種構(gòu)造哈希函數(shù)的方法取決于建表的關(guān)鍵字

集合的情況（包括關(guān)鍵字的范圍和形態(tài)），總的原則是使產(chǎn)生沖突的可

能性降到盡可能地小。

散列表

按照組織形式的不同，通常有兩類散列表：開散列表與閉散列表。

開散列表的組織方式：將所有散列地址相同的記錄都鏈接在同一

鏈表中。

閉散列表解決沖突的基本思想：為每個(gè)鍵值生成一個(gè)散列地址序

列do6…6…如

d。=H(K),是K的散列地址，其余dj(0〈i〈m)是后繼散列地址。

線性探測法二次探測法

散列技術(shù)的原始動(dòng)機(jī)是無需鍵值比較而完成查找。

但由于同義詞的存在，不能實(shí)現(xiàn)。

本章結(jié)束

第七章文件

（文件結(jié)構(gòu)

基本概念＜

（件存儲器簡介

麻序文件的順序存取

順序文件的隨機(jī)存取

｛順序文件按關(guān)鍵字存取

索引文件

ISAM文件

VSANI文件

散列文件

［多重表文件

多關(guān)鍵字文件（

例排文件

本章總述

本章針對在外存儲器中的數(shù)據(jù)，討論了它的組織方法和操作方法。

文件結(jié)構(gòu)是以記錄的集合作為邏輯結(jié)構(gòu)。

如何有效的實(shí)現(xiàn)文件結(jié)構(gòu)是本章的重點(diǎn)。本章著重介紹了順序文

件、索引文件以及散列文件等幾種常見的組織方法。

本章總要求

熟悉文件的概念；

熟悉順序文件、索引文件和散列文件的組織方式和操作方式。

通常將存放在外存中的數(shù)據(jù)稱為文件。

文件是由特性相同的記錄所構(gòu)成的集合，每個(gè)記錄由一個(gè)或多個(gè)

數(shù)據(jù)項(xiàng)構(gòu)成，這是文件的邏輯結(jié)構(gòu)。

文件在存儲介質(zhì)（如磁盤和磁帶）上的實(shí)際組織方式稱為文件的

存儲結(jié)構(gòu)或物理結(jié)構(gòu)，常見的有四種：順序組織、索引組織、散列組

織和鏈組織。

文件在外存儲器上組織結(jié)構(gòu)主要有三種：

順序文件

散列文件

索引文件

ISAM文件

索引順序存取方法ISAM(IndexedSequentialMethod)是一1種專

為磁盤存取設(shè)計(jì)的索引順序文件組織方式。

ISAM文件由多級主索引、柱面索引、磁道索引和主文件組成。

VSAM文件

VSAM(VirtualStorageAccessMethod)虛擬存儲存取方法，是

一種索引順序文件的組織方式，采用動(dòng)態(tài)索引結(jié)構(gòu)。

B-樹與B+樹

定義

B-樹與B+樹的差異

B+樹廣泛的使用在包括VSAM文件在內(nèi)的多種文件系統(tǒng)中。

本章結(jié)束

第八章排序

/慨述

插入排序

:一‘年序］

國泡排庠

快速排序

直接選擇排序

排序\選擇排序＜

、堆排序

（勺L的"1

歸并排序

I二路歸并排序

\外排簡介

本章總述

對于數(shù)據(jù)處理工作，排序是其最基本的運(yùn)算之一。為了

提高計(jì)算機(jī)的工作效率，人們提出了各種各樣的排序方法和

算法。

本章重點(diǎn)介紹了5種內(nèi)部排序算法：直接插入排序、快速

排序、直接選擇排序、堆排序和歸并排序。另外，也介紹了

冒泡排序等。

本章重點(diǎn)

快速排序，堆排序。

本章難點(diǎn)

堆排序。

什么是排序？

所謂排序是指將一組“無序”的記錄序列調(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)

內(nèi)部排序和外部排序

若整個(gè)排序過程不需要訪問外存便能完成，則稱此類排序?yàn)?/p>

內(nèi)部排序；反之，若參加排序的記錄數(shù)量很大，整個(gè)排序過程不

可能在內(nèi)存中完成，則稱此類排序?yàn)橥獠颗判颉?/p>

內(nèi)部排序的方法

按照內(nèi)部排序過程使用的基本手段可以將排序方法分為5個(gè)

類別：

插入排序

交換排序

選擇排序

歸并排序

分配排序

1.插入排序

不斷地將無序子序列中的記錄“插入”到有序序列中，從而逐漸

地增加有序子序列的長度，直到所有記錄都進(jìn)入有序序列中為止。

直接插入排序（基于順序查找）

折半插入排序（基于折半查找）

2.交換排序

不斷地考查待排序列中關(guān)鍵字之間的有序性，一旦發(fā)現(xiàn)非有序關(guān)

系，將其“交換”，直到所有記錄均按照有序性就位為止。

冒泡排序

快速排序

3.選擇排序

不斷地從無序子序列中“選擇”關(guān)鍵字最?。ɑ蜃畲螅┱?，并將其

加入到有序子序列中，以此方法增加有序子序列的長度，直到所有的

記錄都進(jìn)入有序序列中為止。

簡單選擇排序

堆排序

4.歸并排序

通過“歸并”兩個(gè)或兩個(gè)以上的有序子序列，逐步增加有序序列

的長度，直到所有的記錄都進(jìn)入一個(gè)有序序列中為止。

2-路歸并排序

堆排序

堆的定義:

堆是滿足下列性質(zhì)的記錄序列｛一,「2，…，rn

ri^rZir->/2/

或《''（大頂堆）

<（小頂堆）

出-r2i+ln—々+1

1234567891011

{12,36,27,65,40,34,98,81,73,55,49)是小頂堆

{12,36,27,65,40,14,98,81,73,55,49}不是堆

通常將該記錄序列看作一棵完全二叉樹，

rr

則r2i是i的左孩子；r2i+i是i的右孩子。

堆排序是指利用堆的特性對記錄序列進(jìn)行排序的一種排序方法。

基本過程：

lo根據(jù)原始記錄序列創(chuàng)建堆；

2o將根與堆中的最后一個(gè)結(jié)點(diǎn)交換；

30將堆中的最后結(jié)點(diǎn)從堆中刪去；

4O將剩余的結(jié)點(diǎn)重新調(diào)整成堆。

需要解決的兩個(gè)問題:

1、如何“建初堆”？

2、如何調(diào)整“堆”？

建“初堆”的基本方法：

從堆中最后一個(gè)有孩子的結(jié)點(diǎn)開始利用調(diào)整。

(40,55,49,73,12,27,98,81,64,36)

81

7349

64362740

55128

在98和12進(jìn)行互換之后，破壞了“堆”的特性，因此，需要對它

進(jìn)行“篩選”。

在81和12進(jìn)行互換之后，破壞了“堆”的特性，因此，需要對它

進(jìn)行“篩選”。

12

64

w?

在73和12進(jìn)行互換之后，破壞了“堆”的特性，因此，需要

對它進(jìn)行“篩選”。

在64和40進(jìn)行互換之后，破壞了“堆”的特性，因此，需要

對它進(jìn)行“篩選”。

27

49

4027

12365564

73818

在55和27進(jìn)行互換之后，破壞了“堆”的特性，因此，需要對

它進(jìn)行“篩選”。

40

3627

12495564

73818

在49和36進(jìn)行互換之后，破壞了“堆”的特性，因此，需要

對它進(jìn)行“篩選”。

12

排序后的記錄序列:

{12,27,36,40,49,55,6473,81,98)

各種排序方法的綜合比較

1.平均的時(shí)間性能

時(shí)間復(fù)雜度為0（/21og/2）:

快速排序、堆排序和歸并排序

時(shí)間復(fù)雜度為03：

直接插入排序、冒泡排序和

簡單選擇排序

2.最壞時(shí)間性能

時(shí)間復(fù)雜度為0(/71og/7):

堆排序和歸并排序

時(shí)間復(fù)雜度為0(n2)：

快速排序、直接插入排序、

冒泡排序和簡單選擇排序

3.當(dāng)待排記錄序列按關(guān)鍵字順序有序時(shí)

直接插入排序和起泡排序能達(dá)到0(〃)的時(shí)間復(fù)雜度，

快速排序的時(shí)間性能退化為0(772)o

4.簡單選擇排序、堆排序和歸并排序的時(shí)間性能不隨記錄序列中

關(guān)鍵字的分布而改變。

5.空間性能

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

L所有的簡單排序方法(包括：直接插入、起泡和簡單選擇)和

堆排序的空間復(fù)雜度為0(1);

2.快速排序?yàn)?(log〃)，為遞歸程序執(zhí)行過程中，棧所需的輔助

空間；

3.歸并排序所需輔助空間最多，其空間復(fù)雜度為0(〃)。

本章結(jié)束

考情交