第~章緒論

“學生”表格

學號姓名性別籍貫出生年月

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

“課程”表格

課程編號課程名學時

024002程序設計基礎64

024010匯編語言48

024016計算機原理64

024020數據結構64

024021微機技術64

024024操作系統48

024026數據庫原理48

“選課單”包含如下信息

學號課程編號成績時間

學生選課系統中實體構成的網狀關系

UNIX文件系統的系統結構圖

數據(data)

數據是信息的載體,是描述客觀事物

的數、字符、以及所有能輸入到計算

機中，被計算機程序識別和處理的符

號的集合。

?數值性數據

?非數值性數據

數據對象(dataobject)

-數據的子集。al有相同性質的數據成

員（數據元素）的集合。

?整數數據對象

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

.學生數據對象

什么是數據結構

定義:

由某一數據對象及該對象中所有

數據成員之間的關系組成。記為：

DataStructure={D,R}

其中，E是某一數據對象，R是該

對象中所有數據成員之間的關系的有

限集合。

N個網點之間的連通關系

樹形關系網狀關系

抽象數據類型及面向對象概念

業MA皿）

■數L據類型

定義：一組性質相同的值的集合，以

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

的總稱.

-c語言中的數據類型

charintfloatdoublevoid

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

抽象數據類型

(ADTs:AbstractDataTypes)

?由用戶定義，用以表示應用問題的

數據模型

?由基本的數據類型組成,并包括一組

相關的服務(或稱操作)

?信息隱蔽和數據封裝,使用與實現

相分離

自然數的抽象數據類型定義

ADTNaturalNumberis

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

結束于機器能表示的最大整數即Xm。。

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

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

都是可用的服務。

Zero():NaturalNumber返回自然數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

面向對象的概念

-面向對象=對象+類+繼承+通信

■對象

?在應用問題中出現的各種實體、

事件、規格說明等

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

組服務（或稱操作）構成

類(class),實例(instance)

.具有相同屬性和服務的對象歸于

同一類，形成類

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

uadrilateral^\ZquadrilaterallA/^quadrilateral^

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

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

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

-------眼本一

服務一----------------------

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類

數據結構的抽象層次

7線性結構

?直接存取類數組，文件

?順序存取類表，棧，隊列，優先隊列

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

-非線性結構

?層次結構類樹，二叉樹，堆

?群結構類集合，圖

線性結構

(bin)-----(dey)

樹形結構

樹二叉樹二叉搜索樹

堆結構

?e???

“最大”堆"最小”堆

群聚類

圖結構網絡結構

數據的兩個視圖

數據的邏輯結構面向應用

■數據的物理結構面向存儲

?順序結構

?鏈表結構

?散列結構

.索弓結構

-在該數I贏構I上的操作

為什么選用面向對象及C++語言

講述數據結構？

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

C++描述兼有面向過程與面向對

象的特點。

■Java描述是面向對象的。

-用面向對象及C++描述與國際接

軌，是市場需要。

用C++描述面向對象程序

?C++的函數特征?C++的函數名重載和

?C++的數據聲明操作符重載

?C++的作用域?C++的動態存儲分配

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

?C++的對象?內聯(inline)函數

?C++的輸入/輸出?結構(struct)與類

?C++的函數?聯合(Union)與類

?C++的參數傳遞

算法定義

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

解決某一特定任務規定了一個運算序列

■特性：

?輸入有0個或多個輸入

?輸出有一個或多個輸出（處理結果）

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

?有窮性算法應在執行有窮步后結束

?有效性每一條運算應足夠基本

算法設計自頂向下，逐步求精

?事例學習：選擇排序問題

?明確問題：遞增排序

?解決方案：逐個選擇最小數據

?器框架：一

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

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

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

)

?細化程序：程序SelectSort

voidselectSort(inta[]9constintn){

//對n個整數…,按遞增順序排序

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

intk=i;

〃從a[i]查到我最小整數，在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）

定義

適合多種數據類型的類定義或算法,

在特定環境下通過簡單地代換，變成

針對具體某種數據類型的類定義或算

法

用模板定義用于排序的數據表類

#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);

類中所有操作作為模板函數的實現

#include“datalist.h"

template<classType>voiddataList

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

//交換由ml,m2為下標的數組元素的值

Typetemp=Element[ml];

Element[ml]=Element[m2];

Element[m2]=temp;

template<classType>

intdataList<Type>::

MaxKey(intlow,inthigh){

〃查找數組Element[low]到Element[high]

//中的最大值，函數返回其位置

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?“數組內容：\n”;

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

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

OutStream?endl;

OuStream?“數組當前大小：”?

OutList.ArraySize?endl;

returnOutStream;

template<classType>

istream&operator?(istream&InStream,

dataList<Type>InList){

cout?“錄入數組當前大小：飛

Instream?InList.ArraySize;

cout?“錄入數組元素值：\n”；

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

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

InStream?InList.Element[i];

}

returnInStream;

template<classType>

voiddataList<Type>::Sort(){

//按非遞減順序對ArraySize個關鍵碼

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

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

intj=MaxKey(0,i);

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

使用模板的選擇排序算法的主函數

#include"selecttm.h"

constintSIZE=10;

intmain(){

dataList<int>TestList(SIZE);

cin?TestList;

cout?TestList?endl;

TestList.Sort();

cout?TestList?endl;

return0;

性能分析與度量

?算法的性能標準

?算法的后期測試

?算法的事前估計

算法的性能標準

?正確性

?可使用性

?可讀性

?效率

?健壯性

算法的后期測試

在算法中的某些部位插裝時間函數

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;

算法的事前估計

?空間復雜度

?時間復雜度

空間復雜度度量

存儲空間的固定部分

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

’定長成分（如數組元素、結構成分、對象

的數據成員等）變量所占空間

可變部分A

尺寸與實例特性有關的成分變量所占空

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

間、通過new和delete命令動態使用空間

時間復雜度度量

編譯時間

運行時間

?程序步

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

序列

，執行時間與實例特性無關

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

達式：程序步數為1

程序步確定方法

?插入計數全局變量count

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

例以迭代方式求累加和的函數

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統計執行語句條數

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

count++;〃針對fbr語句

s+=a[i];

count++;

}〃針對賦值語句

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

count++;〃針對return語句

returns;

執行結束得程序步數count=2*n+3

程序的簡化形式

voidsum(floata[],intn){

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

count+=2;

count+=3;

注意:

一個語句本身的程序步數可能不等

于該語句一次執行所具有的程序步數。

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

本身的程序步數為1;

一次執行對函數sum(R,n)的調用

需要的程序步數為2*n+3;

一次執行的程序步數為

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

計算累加和程序

計算工作表格

一次執行所執行程序

程序語句需程序步數頻度步數

(010

floats=0.0;111

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

s+=a[i];1nn

returns;111

}010

總程序步數2n+3

時間復雜度的漸進表示法

大O表示法

加法規則針對并列程序段

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

=O(maxg(⑼))

23

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

2n<3n<n!

乘法規則針對嵌套程序段

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

=o(f(〃)*gO))

漸進的空間復雜度

S⑺=

兩個并列循環的例子

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

floatsum[];

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

sum[i]=0.0;〃數據累加

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

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

)

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

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

漸進時間復雜度為0（陽收（/w*%m））

template<classType>〃起泡排序

voiddataList<Type>::bubbleSort(){

〃對表逐趟比較，ArraySize是表當前長度

inti=1;intexchange=1;

〃當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