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

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

串講

主講教師：杜永萍

概述

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

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

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

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

織方法。

第一章概論

引方

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

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

運算和基布運算

存儲實現(xiàn)

存儲實現(xiàn)和運雪實現(xiàn)

概論運算實現(xiàn)

正珅性

算法分析易讀性

健H性

高效率

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

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

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

本章總述

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

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

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

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

本章重點

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

本章難點

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

本章知識點

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

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

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

處理。具有完整確定的實際意義。

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

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

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

不：

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

O

O數(shù)據(jù)項

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)在計算機中的表示（映像）被稱為存儲結(jié)構(gòu),

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

四種基本存儲方式：

順序存儲方式

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

邏輯關(guān)系

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

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

關(guān)系

索引存儲方式

散列存儲方式

3.算法

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

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

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

本章結(jié)束

第二章線性表

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

線性表的舉本概念

線性表

瞋序表

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

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

（單處表

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

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

（建表

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

I清除電史結(jié)點

循環(huán)鏈表

其他漣表

雙燧表

（空間性能

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

I時間性能

串的基本概念

串串的基本運算

山的（中的順序存儲

串的存儲\

I串的犍接存儲

本章總述

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

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

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

本章重點

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

線性表的運算；

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

本章難點

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

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

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

線性表長度

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

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

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

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

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

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

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

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

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

順序表特點：

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

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

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

需占用L個存儲單元

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

L:一個數(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)缺點

優(yōu)點：

隨機存取表中的任一結(jié)點。

缺點：

插入和刪除運算不方便，須移動大量的結(jié)點；存儲分配只能預(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

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

稱作線性表的頭指針。

L

Illia1a2)anA

結(jié)點

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

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

指針域為空

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

特點：

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

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

費的時間不相等。

其它形式的鏈表

1.雙向鏈表(doublelinkedlist)

每個結(jié)點有兩個指針域

priordatanext

特點：克服單鏈表的單向性

2.循環(huán)鏈表

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

特點

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

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

時間性能比較

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

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

單鏈表-0(n)

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

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

第三章棧、隊列和數(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

機蚯

祟4

/薄

上W

e

1

J單舉

苗g

城色5聒

篋期

9世

^

2

￡合金妻

左<

￡

￡

3君

￡

金，紐w卻

7

M

”錄正—

W總

或旬

「卻

5總

先3

都

&

，

%顯

本章總述

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

聯(lián)系。

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

本運算十分類似，可看作是運算受限的線性表。

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

本章重點

棧和隊列的特點；

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

鏈隊上基本運算實現(xiàn)和簡單算法設(shè)計。

本章難點

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

棧的類型定義

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

插入

ala2a3a4????an

刪除

棧的特點

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

(LastInFirstOut)

棧頂浮動

棧底固定

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

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

順序棧

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

鏈棧

隊列定義

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

行，則稱此線性表為隊列。

隊頭front隊尾rear

刪除端插入端

隊列特點

FIFO

(FirstInFirstOut)

隊頭、隊尾均是浮動的

隊列類型的實現(xiàn)

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

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

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

入隊

Q[rear++]=e;

4rear

3q4

出隊

2q3

e=Q[front++]

1q2

0qi4front

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

<rear

q4

q3

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

qi4front

解決的方法：

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

7

循環(huán)隊列

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

數(shù)組

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

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

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

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

2）以列序為主序（高下標(biāo)優(yōu)先）;

以“行序為主序”的存儲映象

例如：

ao,oao,la0,2

al,oal,lal,2

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

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

i1

稱為基地址或基址。

矩陣的壓縮存儲

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

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

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

零元素不分配空間。

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

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

第四章樹

樹的基本概念

（二叉樹的范本概念

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

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

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

（先根遍歷

二叉樹的遍歷｛中根遍歷

I后根遍歷

（簡單遞歸消除

遞歸消除＜

（基于棧的遞歸消除

孩子被表表表示法

孩子兄弟盛表表示法

（雙親表示法

〈（先根遍歷

樹的遍歷J中根遍歷

（后根遍歷

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

（分類與判定樹

判定樹和哈夫曼樹\

I哈夫曼樹與哈夫曼算法

本章總述

本章是數(shù)據(jù)結(jié)構(gòu)課程的重點之一。主要內(nèi)容包括：樹

形結(jié)構(gòu)的基本概念，定義在樹形結(jié)構(gòu)上的兩種重要的數(shù)據(jù)

結(jié)構(gòu)-二叉樹和樹，它們的常見存儲結(jié)構(gòu)、遍歷運算的實現(xiàn)

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

本章重點

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

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

本章難點

二叉樹的遍歷算法

二叉樹或為空樹；或是由一個根結(jié)點加上兩棵分別稱為左子樹和

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

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

只含根結(jié)點

空樹

Q

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

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

7LRLR

二叉樹的重要特性

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

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

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

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

兩類特殊的二叉樹：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

二叉鏈表

三叉鏈表

二叉樹遍歷

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

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

遍歷算法

先（根）序的遍歷算法

中（根）序的遍歷算法

后（根）序的遍歷算法

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

先(根)序的遍歷算法:

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

(1)訪問根結(jié)點；

(2)先序遍歷左子樹；

(3)先序遍歷右子樹。

中(根)序的遍歷算法:

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

(1)中序遍歷左子樹；

(2)訪問根結(jié)點；

(3)中序遍歷右子樹。

后(根)序的遍歷算法:

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

(1)后序遍歷左子樹；

(2)后序遍歷右子樹；

(3)訪問根結(jié)點。

a

PreOrder:abcdegfh

Lb)也

InOrder:cbegdfah

PostOrder:cgefdbha

樹和森林

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

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

樹的遍歷

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

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

注意：

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

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

左是孩子，右是兄弟

判定樹和哈夫曼樹

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

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

n

wp/=工3Jk

k=1

其^中：wk尤又不苴

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

Huffman樹

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

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

哈夫曼算法

本章結(jié)束

第五章圖

圖的實際背景

圖的基本概念

圖的定義和術(shù)語

'轉(zhuǎn)接矩陣

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

、鄰接表

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

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

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

最小生成樹

拓?fù)渑判?/p>

本章總述

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

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

在鄰接關(guān)系。

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

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

本章重點

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

本章難點

Prim算法。

名詞和術(shù)語

網(wǎng)、子圖

完全圖、稀疏圖、稠密圖

鄰接點、度、入度、出度

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

連通圖、連通分量、強連通圖、強連通分量

生成樹、生成森林

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

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

二、圖的鄰接表存儲表示

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

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

附于頂點Vi的邊（有向圖中指以Vi為尾的?。?。

鄰接矩陣特點

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

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

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

ABCDE

適用于稠密圖的表示。

A01010

B00100

C00001

D00100

E11000

鄰接表特點

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

有向圖中：

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

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

圖的遍歷

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

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

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

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

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

V7

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

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

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

中的其余頂點，直至圖中所有和V0有路徑相通的頂點

都被訪問到為止。

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

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

問V0的所有未被訪問過的鄰接點，隨后按這些頂點被訪問

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

路徑相通的頂點都被訪問到為止。

最小生成樹

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

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

個通訊網(wǎng)？

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

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

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

指定圖中某個頂點v作為生成樹的根，隨后往生成樹上添

加新的頂點Wo

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

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

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

n個頂點為止。

例如:

19

b5

12

4

18

18

21

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

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

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

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

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

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

66

空

7

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

本章結(jié)束

第六章查找表

（集合的基本概念

基本概念｛

I杳找表的基本概念

嘴序表上的查找

有序表上的查找

（索引順序表上的直找

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

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

I二義排序樹的刪除

1平衡二叉排序利

（數(shù)字分析法

除余法

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

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

I隨機算注

查找

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

（蒯除

'線性探測法

二次探照法

動態(tài)查找表在M散列表上的實NL

多重散列法

公共沿出區(qū)法

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

本章總述

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

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

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

較而完成查找。

本章重點

二分查找

二叉排序樹的查找

散列表的查找

本章難點

二叉排序樹的插入算法

查找表概念

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

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

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

查找表的常見操作

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

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

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

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

查找表的兩個類別:

靜態(tài)查找表

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

動態(tài)查找表

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

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

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

靜態(tài)查找表

一、順序查找表

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

1n+\

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

〃,=12

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

1Z2+1

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

nn

三、索引順序表

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

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

二分查找效率最高但限制最強；

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

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

1.定義

2.查找算法

3.插入算法

4.刪除算法

5.查找性能的分析

二叉排序樹定義

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

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

點的值；

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

點的值；

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

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

增序列。

查找性能的分析

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

義來求它的ASL值，顯然，由值相同的n個關(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

②④

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

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

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

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

散列表

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

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

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

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

產(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.隨機數(shù)法

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

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

能性降到盡可能地小。

散列表

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

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

鏈表中。

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

列do6…6…如

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

線性探測法二次探測法

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

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

本章結(jié)束

第七章文件

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

基本概念＜

（件存儲器簡介

麻序文件的順序存取

順序文件的隨機存取

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

索引文件

ISAM文件

VSANI文件

散列文件

［多重表文件

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

例排文件

本章總述

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

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

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

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

本章總要求

熟悉文件的概念；

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

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

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

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

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

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

織和鏈組織。

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

順序文件

散列文件

索引文件

ISAM文件

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

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

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

VSAM文件

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

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

B-樹與B+樹

定義

B-樹與B+樹的差異

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

本章結(jié)束

第八章排序

/慨述

插入排序

:一‘年序］

國泡排庠

快速排序

直接選擇排序

排序\選擇排序＜

、堆排序

（勺L的"1

歸并排序

I二路歸并排序

\外排簡介

本章總述

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

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

算法。

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

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

冒泡排序等。

本章重點

快速排序，堆排序。

本章難點

堆排序。

什么是排序？

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

若整個排序過程不需要訪問外存便能完成，則稱此類排序為

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

可能在內(nèi)存中完成，則稱此類排序為外部排序。

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

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

類別：

插入排序

交換排序

選擇排序

歸并排序

分配排序

1.插入排序

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

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

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

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

2.交換排序

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

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

冒泡排序

快速排序

3.選擇排序

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

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

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

簡單選擇排序

堆排序

4.歸并排序

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

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

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將根與堆中的最后一個結(jié)點交換；

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

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

需要解決的兩個問題:

1、如何“建初堆”？

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

建“初堆”的基本方法：

從堆中最后一個有孩子的結(jié)點開始利用調(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.平均的時間性能

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

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

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

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

簡單選擇排序

2.最壞時間性能

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

堆排序和歸并排序

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

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

冒泡排序和簡單選擇排序

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

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

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

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

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

5.空間性能

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

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

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

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

空間；

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

本章結(jié)束

考情交