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

第~章緒論

“學(xué)生”表格

學(xué)號姓名性別籍貫出生年月

198131劉激揚男北京1979.12

298164衣春生男青島1979.07

398165盧聲凱男天津1981.02

498182袁秋慧女廣州1980.10

598224洪偉男太原1981.01

698236熊南燕女蘇州1980.03

798297宮力男北京1981.01

898310蔡曉莉女昆明1981.02

998318陳健男杭州1979.12

“課程”表格

課程編號課程名學(xué)時

024002程序設(shè)計基礎(chǔ)64

024010匯編語言48

024016計算機(jī)原理64

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

024021微機(jī)技術(shù)64

024024操作系統(tǒng)48

024026數(shù)據(jù)庫原理48

“選課單”包含如下信息

學(xué)號課程編號成績時間

學(xué)生選課系統(tǒng)中實體構(gòu)成的網(wǎng)狀關(guān)系

UNIX文件系統(tǒng)的系統(tǒng)結(jié)構(gòu)圖

數(shù)據(jù)(data)

數(shù)據(jù)是信息的載體,是描述客觀事物

的數(shù)、字符、以及所有能輸入到計算

機(jī)中，被計算機(jī)程序識別和處理的符

號的集合。

?數(shù)值性數(shù)據(jù)

?非數(shù)值性數(shù)據(jù)

數(shù)據(jù)對象(dataobject)

-數(shù)據(jù)的子集。al有相同性質(zhì)的數(shù)據(jù)成

員（數(shù)據(jù)元素）的集合。

?整數(shù)數(shù)據(jù)對象

N={0,±1,+2,...}

.學(xué)生數(shù)據(jù)對象

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

定義:

由某一數(shù)據(jù)對象及該對象中所有

數(shù)據(jù)成員之間的關(guān)系組成。記為：

DataStructure={D,R}

其中，E是某一數(shù)據(jù)對象，R是該

對象中所有數(shù)據(jù)成員之間的關(guān)系的有

限集合。

N個網(wǎng)點之間的連通關(guān)系

樹形關(guān)系網(wǎng)狀關(guān)系

抽象數(shù)據(jù)類型及面向?qū)ο蟾拍?/p>

業(yè)MA皿）

■數(shù)L據(jù)類型

定義：一組性質(zhì)相同的值的集合，以

及定義于這個值集合上的一組操作

的總稱.

-c語言中的數(shù)據(jù)類型

charintfloatdoublevoid

字符型整型浮點型雙精度型無值

抽象數(shù)據(jù)類型

(ADTs:AbstractDataTypes)

?由用戶定義，用以表示應(yīng)用問題的

數(shù)據(jù)模型

?由基本的數(shù)據(jù)類型組成,并包括一組

相關(guān)的服務(wù)(或稱操作)

?信息隱蔽和數(shù)據(jù)封裝,使用與實現(xiàn)

相分離

自然數(shù)的抽象數(shù)據(jù)類型定義

ADTNaturalNumberis

objects:一個整數(shù)的有序子集合，它開始于0,

結(jié)束于機(jī)器能表示的最大整數(shù)即Xm。。

Function:對于所有的蒼y￡NaturalNumber^

False,TrueGBoolean,+、?、v、==、=等

都是可用的服務(wù)。

Zero():NaturalNumber返回自然數(shù)0

IsZero(x):if(x==0)返回True

Booleanelse返回False

Add(x,y):if返回x+y

NaturalNumberelse返回AfoxZra，

Subtract(x,y):if(x<y)返回0

NaturalNumberelse返回x-y

Equal(x,y):if(x==y)返回True

Booleanelse返回False

Successor(x):if(x==MaxInt)返回x

NaturalNumberelse返回x+1

endNaturalNumber

面向?qū)ο蟮母拍?/p>

-面向?qū)ο?對象+類+繼承+通信

■對象

?在應(yīng)用問題中出現(xiàn)的各種實體、

事件、規(guī)格說明等

?由一組屬性值和在這組值上的一

組服務(wù)（或稱操作）構(gòu)成

類(class),實例(instance)

.具有相同屬性和服務(wù)的對象歸于

同一類，形成類

?類中的對象為該類的實例

uadrilateral^\ZquadrilaterallA/^quadrilateral^

----------------------―—————

aPointlaPointl(35,10)(50,10)(45,65)(50,45)

aPoint3aPoint4(35,25)(50,25)(65,66)(60,70)

-------眼本一

服務(wù)一----------------------

Draw()Draw()Draw()

move(Ax,Ay)move(Ax,Ay)move(Ax9Ay)

^ontains(aP()in^^ontains(aPoiiit^^ontains(aPoiii?

邊形類及其對象

繼承

派生類：四邊形，三角形，…

子類特化類（特殊化類）

?基類：多邊形

父類泛化類（一般化類）

■通信

?消息傳遞

Polygon^Quadrilateral^

referencePointreferencePoint

VerticesVertices

Draw()Draw()

move(Ax,Ay)ntove(/\x^Ay)

entains(aPoin^

Polygon類Polygon的子類

Quadrilateral類

數(shù)據(jù)結(jié)構(gòu)的抽象層次

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

?直接存取類數(shù)組，文件

?順序存取類表，棧，隊列，優(yōu)先隊列

?廣義索引類線性索引,搜索樹

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

?層次結(jié)構(gòu)類樹，二叉樹，堆

?群結(jié)構(gòu)類集合，圖

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

(bin)-----(dey)

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

樹二叉樹二叉搜索樹

堆結(jié)構(gòu)

?e???

“最大”堆"最小”堆

群聚類

圖結(jié)構(gòu)網(wǎng)絡(luò)結(jié)構(gòu)

數(shù)據(jù)的兩個視圖

數(shù)據(jù)的邏輯結(jié)構(gòu)面向應(yīng)用

■數(shù)據(jù)的物理結(jié)構(gòu)面向存儲

?順序結(jié)構(gòu)

?鏈表結(jié)構(gòu)

?散列結(jié)構(gòu)

.索弓結(jié)構(gòu)

-在該數(shù)I贏構(gòu)I上的操作

為什么選用面向?qū)ο蠹癈++語言

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

PASCAL與C描述是面向過程的。

C++描述兼有面向過程與面向?qū)?/p>

象的特點。

■Java描述是面向?qū)ο蟮摹?/p>

-用面向?qū)ο蠹癈++描述與國際接

軌，是市場需要。

用C++描述面向?qū)ο蟪绦?/p>

?C++的函數(shù)特征?C++的函數(shù)名重載和

?C++的數(shù)據(jù)聲明操作符重載

?C++的作用域?C++的動態(tài)存儲分配

?C++的類?友元(friend)函數(shù)

?C++的對象?內(nèi)聯(lián)(inline)函數(shù)

?C++的輸入/輸出?結(jié)構(gòu)(struct)與類

?C++的函數(shù)?聯(lián)合(Union)與類

?C++的參數(shù)傳遞

算法定義

定義J一個有窮的指令集，這些指令為

解決某一特定任務(wù)規(guī)定了一個運算序列

■特性：

?輸入有0個或多個輸入

?輸出有一個或多個輸出（處理結(jié)果）

?確定性每步定義都是確切、無歧義的

?有窮性算法應(yīng)在執(zhí)行有窮步后結(jié)束

?有效性每一條運算應(yīng)足夠基本

算法設(shè)計自頂向下，逐步求精

?事例學(xué)習(xí)：選擇排序問題

?明確問題：遞增排序

?解決方案：逐個選擇最小數(shù)據(jù)

?器框架：一

for(inti=0;i<n-1;i++){〃n?l趟

&a[i]檢查到a[n到];

若最小整數(shù)在a[k],交換a[i]與a[k];

)

?細(xì)化程序：程序SelectSort

voidselectSort(inta[]9constintn){

//對n個整數(shù)…,按遞增順序排序

for(inti=0;i<n-l;i++){

intk=i;

〃從a[i]查到我最小整數(shù)，在a[k]

for(intj=i+l;j<n;j++)

if(a[j]<a[k])k=j;

inttemp=a[i];a[i]=a[k];a[k]=temp;

模板（template）

定義

適合多種數(shù)據(jù)類型的類定義或算法,

在特定環(huán)境下通過簡單地代換，變成

針對具體某種數(shù)據(jù)類型的類定義或算

法

用模板定義用于排序的數(shù)據(jù)表類

#include<iostream.h>

template<classType>

classdataList{

private:

Type"Element;

intArraySize;

voidSwap(intml,intm2);

intMaxKey(intlow,inthigh);

public:

dataList(intsize=10):ArraySize(size),

Element(newType[Size]){}

-dataList(){delete[]Element;}

voidSort();

friendostream&operator?(ostream&

outStream,datalist<Type>&outList);

friendistream&operator?(istream&

inStream,datalist<Type>&inList);

類中所有操作作為模板函數(shù)的實現(xiàn)

#include“datalist.h"

template<classType>voiddataList

<Type>::Swap(intml,intm2){

//交換由ml,m2為下標(biāo)的數(shù)組元素的值

Typetemp=Element[ml];

Element[ml]=Element[m2];

Element[m2]=temp;

template<classType>

intdataList<Type>::

MaxKey(intlow,inthigh){

〃查找數(shù)組Element[low]到Element[high]

//中的最大值，函數(shù)返回其位置

intmax=low;

for(intk=low+1,k<=high,k++)

if(Element[max]<Element[k])

max=k;

returnmax;

template<classType>ostream&

operator?(ostream&OutStream,

dataList<Type>OutList){

OutStream?“數(shù)組內(nèi)容：\n”;

for(inti=0;i<OutList.ArraySize;i++)

OutStream?OutList.Element[i]vv，，；

OutStream?endl;

OuStream?“數(shù)組當(dāng)前大?。骸?

OutList.ArraySize?endl;

returnOutStream;

template<classType>

istream&operator?(istream&InStream,

dataList<Type>InList){

cout?“錄入數(shù)組當(dāng)前大?。猴w

Instream?InList.ArraySize;

cout?“錄入數(shù)組元素值：\n”；

for(inti=0;i<InList.ArraySize;i++){

cout?“元素”?ivv“：”；

InStream?InList.Element[i];

}

returnInStream;

template<classType>

voiddataList<Type>::Sort(){

//按非遞減順序?qū)rraySize個關(guān)鍵碼

“Element[0]到Element]ArraySize-1]排序

for(inti=ArraySize-1;i>0;i--){

intj=MaxKey(0,i);

if(j!=i)swap(j5i);

使用模板的選擇排序算法的主函數(shù)

#include"selecttm.h"

constintSIZE=10;

intmain(){

dataList<int>TestList(SIZE);

cin?TestList;

cout?TestList?endl;

TestList.Sort();

cout?TestList?endl;

return0;

性能分析與度量

?算法的性能標(biāo)準(zhǔn)

?算法的后期測試

?算法的事前估計

算法的性能標(biāo)準(zhǔn)

?正確性

?可使用性

?可讀性

?效率

?健壯性

算法的后期測試

在算法中的某些部位插裝時間函數(shù)

time()

測定算法完成某一功能所花費時間

順序搜索(SequenialSearch)

intseqsearch(inta[]5intn,intx){

〃在a[0],…,中搜索x

inti=0;

while(i<n&&a[i]!=x)

i++；

if(i==n)return-1;

returni;

插裝time()的計時程序

doublestart,stop;

time(&start);

intk=seqsearch(a,n,x);

time(&stop);

doublerunTime=stop-start;

cout?""?n?""?

runTime?endl;

算法的事前估計

?空間復(fù)雜度

?時間復(fù)雜度

空間復(fù)雜度度量

存儲空間的固定部分

程序指令代碼的空間，常數(shù)、簡單變量、

’定長成分（如數(shù)組元素、結(jié)構(gòu)成分、對象

的數(shù)據(jù)成員等）變量所占空間

可變部分A

尺寸與實例特性有關(guān)的成分變量所占空

間、引用變量所占空間、遞歸棧所用空

間、通過new和delete命令動態(tài)使用空間

時間復(fù)雜度度量

編譯時間

運行時間

?程序步

，語法上或語義上有意義的一段指令

序列

，執(zhí)行時間與實例特性無關(guān)

，例如：聲明語句：程序步數(shù)為0;表

達(dá)式：程序步數(shù)為1

程序步確定方法

?插入計數(shù)全局變量count

?建表，列出個語句的程序步

例以迭代方式求累加和的函數(shù)

floatsum(floata[]5intn){

floats=0.0;

for(inti=0;i<n;i++)

s+=a[i];

returns;

在求累加和程序中加入co〃加語句

floatsum(floata[]9intn){

floats=0.0;

count++;//count統(tǒng)計執(zhí)行語句條數(shù)

for(inti=0;i<n;i++){

count++;〃針對fbr語句

s+=a[i];

count++;

}〃針對賦值語句

count++;〃針對for的最后一次

count++;〃針對return語句

returns;

執(zhí)行結(jié)束得程序步數(shù)count=2*n+3

程序的簡化形式

voidsum(floata[],intn){

for(inti=0;i<n;i++)

count+=2;

count+=3;

注意:

一個語句本身的程序步數(shù)可能不等

于該語句一次執(zhí)行所具有的程序步數(shù)。

例如：賦值語句x=sum(R,n)

本身的程序步數(shù)為1;

一次執(zhí)行對函數(shù)sum(R,n)的調(diào)用

需要的程序步數(shù)為2*n+3;

一次執(zhí)行的程序步數(shù)為

l+2*n+3=2*n+4

計算累加和程序

計算工作表格

一次執(zhí)行所執(zhí)行程序

程序語句需程序步數(shù)頻度步數(shù)

(010

floats=0.0;111

for(inti-0;i<n;i-HF)1n+1n+1

s+=a[i];1nn

returns;111

}010

總程序步數(shù)2n+3

時間復(fù)雜度的漸進(jìn)表示法

大O表示法

加法規(guī)則針對并列程序段

T(n,m)=T1(n)+T2(m)

=O(maxg(⑼))

23

c<log2n<n<nlog2n<n<n<

2n<3n<n!

乘法規(guī)則針對嵌套程序段

T(〃,m)=T1(H)*T2(m)

=o(f(〃)*gO))

漸進(jìn)的空間復(fù)雜度

S⑺=

兩個并列循環(huán)的例子

voidexam(floatx[][]5intm,intn){

floatsum[];

for(inti=0;i<m;i++){〃x中各行

sum[i]=0.0;〃數(shù)據(jù)累加

for(intj=0;j<n;j++)

sum[i]+=x[i][j];

)

for(i=0;i<m;i++)〃打印各行數(shù)據(jù)和

cout?i?":"?sum[i]?endl;

漸進(jìn)時間復(fù)雜度為0（陽收（/w*%m））

template<classType>〃起泡排序

voiddataList<Type>::bubbleSort(){

〃對表逐趟比較，ArraySize是表當(dāng)前長度

inti=1;intexchange=1;

〃當(dāng)exchange為0則停止排序

while(i<ArraySize&&exchange){

BubbleExchange(i5exchange);

i++；

}〃一趟比較

噌華

}會

(案

g案

(

}

m

M

1

M

(

u

眼e

m

s

蛆M

K

p

u

.'

x

T叼

g豺

M

g

A

啾u刑、

電「l

L

照恁

二g

/

/

w

—/

/

/

g

A

z

'

A

:

-

a

:

s

-二

/

<

d

U自

a

A

D

U

d

g

I

o

A

u缺

V

H

I

S

g

S

V

U

WJ

u

H

m

U

g

J

P

m

I

g

￡

二I

p

J

y

P

w

V

x

bn

F

X

U

u

)

w

J

D

3