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

ContactMe:jia:(

)為什么學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)？計(jì)算機(jī)科學(xué)是一門研究數(shù)據(jù)表示和數(shù)據(jù)處理的科學(xué)用計(jì)算機(jī)來解決實(shí)際問題，僅掌握幾種計(jì)算機(jī)程序設(shè)計(jì)語言是難以應(yīng)付眾多復(fù)雜的課題的設(shè)計(jì)出一個(gè)結(jié)構(gòu)好效率高的程序，必須研究數(shù)據(jù)的特性及數(shù)據(jù)間的相互關(guān)系及其對應(yīng)的表示象方法與課堂學(xué)習(xí)：等《數(shù)據(jù)結(jié)構(gòu)（用面C++描述）》

()課后實(shí)習(xí)每周實(shí)驗(yàn)課程大作業(yè)成績期末考試上機(jī)+課程大作業(yè)平時(shí)作業(yè)第一章 緒論§1.1

數(shù)據(jù)結(jié)構(gòu)早期：數(shù)值計(jì)算——運(yùn)算對象是簡單的整型、實(shí)型或類型數(shù)據(jù)中后期：非數(shù)值計(jì)算——處理對象是類型復(fù)雜的數(shù)據(jù)，數(shù)據(jù)元 間的相互關(guān)系一般無法用數(shù)學(xué)方程式加以描述學(xué)號姓名籍貫出生年月98131劉激揚(yáng)男北京1979.1298164衣男青島1979.0798165男天津1981.0298182女廣州1980.1098203海1980.0598224洪偉男太原1981.0198236熊南燕女蘇州1980.0398297宮力男北京1981.0198310女昆明1981.0298318陳健男杭州1979.1212345678910例1：“學(xué)生”表格例2：八皇后問題(用四皇后描述)............四皇后問題的狀態(tài)樹先修課程無C1，C4課程名稱計(jì)算機(jī)導(dǎo)論數(shù)據(jù)結(jié)構(gòu)匯編語言課程C1C2C3C4C5C4C6C7接 術(shù)數(shù)據(jù)庫原理C1C程序設(shè)計(jì)語言

C1計(jì)算機(jī)圖形學(xué)

C2，C3，C3C2，C9C8C9例3：教學(xué)計(jì)劃編排問題編譯原理

C4（a）計(jì)操算作機(jī)系專統(tǒng)業(yè)的課程設(shè)C置2C1C2C3C6C4C5C9C7C8（b）表示課程之間優(yōu)先關(guān)系的有向圖例4：城市的煤氣管道問題（a）結(jié)點(diǎn)間管道的代價(jià)（b）最經(jīng)濟(jì)的管道鋪設(shè)描述這類非數(shù)值計(jì)算問題的數(shù)學(xué)模型不再是數(shù)學(xué)方程，而是諸如表、樹、圖之類的數(shù)據(jù)結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)是一門研究（非數(shù)值計(jì)算的）程序設(shè)計(jì)問題中所出現(xiàn)的計(jì)算機(jī)操作對象以及它們之間的關(guān)系和操作的學(xué)科。一些基本概念：數(shù)據(jù)數(shù)據(jù)元素（數(shù)據(jù)成員）數(shù)據(jù)對象數(shù)據(jù)：數(shù)據(jù)是信息的載體，是描述客觀事物的數(shù)、字符、以及所有能輸入到計(jì)算機(jī)中，被計(jì)算機(jī)程序識別和處理的符號（數(shù)值、字符等）的集合。數(shù)據(jù)元素（數(shù)據(jù)成員）:是數(shù)據(jù)的基本單位。在不同的條件下，數(shù)據(jù)元素又可稱為元素、結(jié)點(diǎn)、頂點(diǎn)、記錄等。數(shù)據(jù)對象：具有相同性質(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)系組成。記為：Data_Structure

=

{D,

R}其中，D是某一數(shù)據(jù)對象，R是該對象中所有數(shù)據(jù)成員之間的關(guān)系的有限集合。數(shù)據(jù)結(jié)構(gòu)的形式定義數(shù)據(jù)結(jié)構(gòu)包括“邏輯結(jié)構(gòu)”和“物理結(jié)構(gòu)”兩個(gè)方面(層次):邏輯結(jié)構(gòu)是對數(shù)據(jù)成員之間的邏輯關(guān)系的描述，它可以用一個(gè)數(shù)據(jù)成員的集合和定義在此集合上的若干關(guān)系來表示;物理結(jié)構(gòu)是邏輯結(jié)構(gòu)在計(jì)算機(jī)中的表示

，故又稱“結(jié)構(gòu)”。根據(jù)問題來建立邏輯結(jié)構(gòu)例如：Class=(D,S)數(shù)據(jù)集合：D={a,b1,…,bn,c1,…cn,d1,…dn}關(guān)系集合：S

=

{

R1,

R2

}R1

=

{

<a,

b1>,<a,

c1>,<a,

d1>}//班長-組長R2={<b1,bj>,<c1,cj>,<d1,dj>|

j =

2,

3,

…,

n

}//組長-組員ab1c1…

cnb2

b3

…

bn

c2

c3

d2

d3

…

dnd1班級Class的邏輯結(jié)構(gòu)的圖示結(jié)構(gòu)是邏輯結(jié)構(gòu)在 器中的映象。數(shù)據(jù)元素的映象：任何的數(shù)據(jù)元素在計(jì)算機(jī)中最終都是轉(zhuǎn)化成一個(gè)二進(jìn)制的位串。關(guān)系的映象：…關(guān)系的映象方法：（關(guān)系對x,

y）1.順序映象：以相對的 位置表示后繼關(guān)系例如:令

y

的 位置和

x

的 位置之間差一個(gè)常量

C，而

C

是一個(gè)隱含值，整個(gè)結(jié)構(gòu)中只含數(shù)據(jù)元素本身的信息xy2.鏈?zhǔn)接诚?以附加信息(指針)表示后繼關(guān)系需要用一個(gè)和

x 在一起的附加信息（指針)指示y

的 位置yx§1.2

抽象數(shù)據(jù)類型及面象概念C語言中的數(shù)據(jù)類型char

int

float

double

void字符型整型浮點(diǎn)型雙精度型無值數(shù)據(jù)類型定義：一組性質(zhì)相同的值的集合,以及定義于這個(gè)值集合上的一組操作的總稱.不同類型的變量，其所能取的值的范圍不同，所能進(jìn)行的操作不同。例如：整型(int)值的范圍是：-32768~32767（16位）操作是：+，-，*，/，%抽象數(shù)據(jù)類型

(ADTs: Data

Types)由用戶定義，用以表示應(yīng)用問題的數(shù)據(jù)模型由基本的數(shù)據(jù)類型組成,并包括一組相關(guān)的服務(wù)（或稱操作）支持了邏輯設(shè)計(jì)和物理實(shí)現(xiàn)的分離，支持封裝和信息隱蔽抽象：抽取反映問題本質(zhì)的東西，忽略非本質(zhì)的細(xì)節(jié)抽象數(shù)據(jù)類型的兩種視圖：設(shè)計(jì)者的角度：根據(jù)問題來定義抽象數(shù)據(jù)類型所包含的信息，給出其相關(guān)功能的實(shí)現(xiàn)，并提供公共界面的接口。用戶的角度：使用公共界面的接口對抽象數(shù)據(jù)類型進(jìn)行操作，不需要考慮其物理實(shí)現(xiàn)。對于外部用戶來說，抽象數(shù)據(jù)類型應(yīng)該是一個(gè)黑盒子。自然數(shù)的抽象數(shù)據(jù)類型定義ADT

NaturalNumber

isobjects:一個(gè)整數(shù)的有序子集合,它開始于0,結(jié)束于機(jī)器能表示的最大整數(shù)(MaxInt)。Function:

對于所有的

x,y

NaturalNumber;False,True

Boolean,+、-、<、==、=等都是可用的服務(wù)。Zero():

返回自然數(shù)0NaturalNumberif(x==0)

返回Trueelse

返回Falseif(x+y<=MaxInt)返回x+yelse

返回MaxIntif(x<y)返回0else

返回x-yif(x==y)返回Trueelse

返回Falseif(x==MaxInt)返回xelse

返回x+1IsZero(x)

:BooleanAdd

(x,

y):NaturalNumberSubtract

(x,

y):NaturalNumberEqual

(x,

y):BooleanSuccessor

(x):NaturalNumberendNaturalNumber面 象的概念面 象

=

對象＋類＋繼承＋通信面

象方法中類的定義充分體現(xiàn)了抽象數(shù)據(jù)類型的思想§1.3

數(shù)據(jù)結(jié)構(gòu)的抽象層次數(shù)據(jù)結(jié)構(gòu)的抽象層次線性結(jié)構(gòu)：表、棧、隊(duì)列非線性結(jié)構(gòu)層次結(jié)構(gòu)：樹，二叉樹，堆網(wǎng)狀結(jié)構(gòu)：圖其它：集合線性結(jié)構(gòu)bindevetclibuser層次結(jié)構(gòu)樹二叉樹11

128

910987456231堆（特殊的樹結(jié)構(gòu)）12711103

5

4

8

2“最大”堆96368

9“最小”堆7網(wǎng)狀結(jié)構(gòu)圖結(jié)構(gòu)12564312311216335

4網(wǎng)絡(luò)結(jié)構(gòu)C++的函數(shù)特征C++的數(shù)據(jù)C++的作用域C++的類C++的對象C++的輸入/輸出C++的函數(shù)C++的參數(shù)傳遞C++的函數(shù)名重載和操作符重載C++的動態(tài)

分配(friend)函數(shù)內(nèi)聯(lián)(inline)函數(shù)結(jié)構(gòu)(struct)與類聯(lián)合(Union)與類§1.4

用C++描述面

象程序Niklaus

Wirth

（1976）數(shù)據(jù)結(jié)構(gòu)+算法=程序設(shè)計(jì)為計(jì)算機(jī)處理問題編制一組指令集處理問題的策略問題的數(shù)學(xué)模型§1.5

算法定義算法：一個(gè)有窮的指令集，這些指令為解決某一特定任務(wù)規(guī)定了一個(gè)運(yùn)算序列。(算法是對特定問題求解步驟的一種描述)輸入

有0個(gè)或多個(gè)輸入輸出

有一個(gè)或多個(gè)輸出(處理結(jié)果)確定性

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

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

每一條運(yùn)算應(yīng)足夠基本一個(gè)算法必須滿足以下五個(gè)重要特性：§1.6

模板模板：適合多種數(shù)據(jù)類型的類定義或算法，在特定環(huán)境下通過簡單地代換，可以變成針對具體某種數(shù)據(jù)類型的類定義或算法。用模板定義用于排序的數(shù)據(jù)表(dataList)類#ifndef

DATALIST_H#define

DATALIST_H#include

<iostream.h>//模板標(biāo)識//類標(biāo)識template

<class

Type>class

dataList

{private:Type

*Element;int

ArraySize;void

Swap

(const

int

m1,

const

int

m2);

int

MaxKey

(constint

low,constint

high);public:dataList

(int

size

=

10)

:

ArraySize

(size),Element

(new

Type

[Size])

{

}~dataList

(

)

{delete

[

]

Element;}void

Sort

(

);friend

ostream&

operator

<<(ostream&outStream,

const

datalist<Type>&outList);friend

istream&

operator

>>

(istream&inStream,

const

datalist<Type>&inList);};#endifdataList類中所有操作作為模板函數(shù)的實(shí)現(xiàn)#ifndef

SELECTTM_H#define

SELECTTM_H#include

“datalist.h”template

<class

Type>void

dataList

<Type>::Swap

(const

int

m1, const

int

m2)

{//交換由m1,

m2為下標(biāo)的兩個(gè)數(shù)組元素的值Type

temp

=

Element

[m1];Element

[m1]

=

Element

[m2];Element

[m2]

=

temp;}template

<class

Type>int

dataList<Type>::MaxKey

(const

int

low,

const

int

high)

{//查找數(shù)組Element[low]～Element[high]中//的最大值，函數(shù)返回其位置int

max=low;for

(int

k

=

low+1,

k

<=

high,

k++)if

(

Element[max]

<

Element[k]

)max

=

k;return

max;}template

<class

Type>

ostream&operator<<

(ostream&

OutStream,const

dataList<Type>

OutList){//輸出對象為OutList，輸出流對象為OutStreamOutStream

<<

“Array

Contents

:

\n”;for

(int

i

=

0;

i

<

OutList.ArraySize;

i++)OutStream

<<

OutLis ement[i]

<<

‘

’;OutStream

<<

endl;OuStream

<<

“Array

Current

Size

:

”

<<OutList.ArraySize

<<

endl;return

OutStream;}template

<class

Type>istream&

operator

>>

(istream&

InStream,dataList<Type>

InList)

{//輸入對象為InList，輸入流對象為InStreamcout

<<

“Enter

array

Current

Size

:

”;Instream

>>

InList.ArraySize;cout

<<

“Enter

array

elements

:

\n”;for

(int

i

=

0;

i

<

InList.ArraySize;

i++)

{cout

<<

“Elememt”

<<

i

<<

“:”

;InStream

>>

InLis

ement[i];}return

InStream;}template

<class

Type>void

dataList<Type>::Sort

(

)

{//按非遞減順序?qū)rraySize個(gè)關(guān)鍵碼//Element[0]～Element[ArraySize-1]排序for(int

i=ArraySize

-1;i>0;i--){int

j

=

MaxKey

(0,

i);if

(

j

!=

i

)

swap

(j,

i);}}#endif使用模板的選擇排序算法的主函數(shù)#include

“selecttm.h”const

int

SIZE

=

10;int

main

(

)

{dataList

<int>

TestList

(SIZE);cin>>

TestList;cout

<<

“Testing

Selection

Sort

:

\n”

<<TestList

<<

endl;TestList.Sort

(

);cout

<<

“After

sorting

:

\n”

<<TestList

<<

endl;return

0;}§1.7

性能分析與度量算法的性能標(biāo)準(zhǔn)：正確性可使用性可讀性效率健壯性算法的效率包括時(shí)間代價(jià)和空間代價(jià)，前者指的是算法執(zhí)行時(shí)間；后者指的是算法執(zhí)行過程中所需的最大空間。兩者都與問題的規(guī)模有關(guān)。算法效率的衡量方法：事后估計(jì)事前估計(jì)算法的事后估計(jì)在算法中的某些部位插裝時(shí)間函數(shù)time

()測定算法完成某

能所花費(fèi)的時(shí)間算法的事前估計(jì)空間復(fù)雜度時(shí)間復(fù)雜度時(shí)間復(fù)雜度編譯時(shí)間運(yùn)行時(shí)間–程序步：語法（義）上有意義的一段指令例如：注釋：程序步數(shù)為0語句：程序步數(shù)為0表達(dá)式、賦值語句：程序步數(shù)為1循環(huán)語句：循環(huán)控制語句每次執(zhí)行的程序步數(shù)為1程序步確定方法計(jì)數(shù)全局變量count例以迭代方式求累加和的函數(shù)行float

sum

(floata[],const

int

n

)1

{floats

=

0.0;for(int

i

=0;

i

<n;i++

)4

s

+=a[i];5

return

s;6

}在求累加和程序中加入count語句float

sum

(

float

a[

],

const

int

n

)

{float

s

=

0.0;count++;

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

for

(int

i=0;i<n;i++){count++;

//針對for語句s

+=

a[i];count++;//針對賦值語句}count++;count++;//針對for的最后一次//針對return語句return

s;}

執(zhí)行結(jié)束得程序步數(shù)

count=2

*

n

+3注意：一個(gè)語句本身的程序步數(shù)可能不等于該語句一次執(zhí)行所具有的程序步數(shù)。例如：賦值語句x

=

sum

(R,

n);本身的程序步數(shù)為1；一次執(zhí)行對函數(shù)sum

(R,n)的調(diào)用需要的程序步數(shù)為2*n+3；一次執(zhí)行的程序步數(shù)為1+2*n+3

=

2*n+4

確定程序的準(zhǔn)確程序步數(shù)十分

。程序步數(shù)本身也不是一個(gè)精確的概念，不能確切反映運(yùn)行時(shí)間。一個(gè)算法的“運(yùn)行時(shí)間"通常是隨問題規(guī)模的增長而增長,它是問題規(guī)模(用正整數(shù)n表示)的函數(shù)。統(tǒng)計(jì)算法中作為基本運(yùn)算的原操作，以原操作重復(fù)執(zhí)行的次數(shù)作為算法的時(shí)間度量。算法中原操作重復(fù)執(zhí)行的次數(shù)是規(guī)模n的某個(gè)函數(shù)T(n)。時(shí)間復(fù)雜度的漸進(jìn)表示法要精確地計(jì)算T(n)通常較引入漸進(jìn)時(shí)間復(fù)雜度——在數(shù)量上估計(jì)一個(gè)算法的執(zhí)行時(shí)間，也能夠達(dá)到分析算法的目的。（觀察算法隨n增長的趨勢）(大Ο記號):T(n)=O(f(n))(稱T(n)為算法的(漸近)時(shí)間復(fù)雜度。表明，隨著問題規(guī)模n的增長，算法執(zhí)行時(shí)間的增長率和f(n)的增長率相同)例：一個(gè)程序的實(shí)際執(zhí)行時(shí)間為T(n)＝2.7n3+3.8n2+5.3

則T(n)＝Ο(n3)大O表示法:T(n)=O(f(n))的幾條規(guī)則加

則

針對并列程序段T(n,

m) =

T1

(n)

+

T2

(m)=

O(max

(f

(n),

g

(m)))乘

則

針對嵌套程序段T

(n,

m)

=

T1

(n)

*

T2

(m)=

O(f

(n)*g

(m))乘 則中的常數(shù)無關(guān)項(xiàng)

O(C)

→

O(1)T

(n)

=

O(

c

*

f(n))

=O(f(n))Ο(1)表示常數(shù)計(jì)算時(shí)間例1：兩個(gè)并列循環(huán)void

example

(float

x[

][

],

int

m,

int

n,

int

k)

{float

sum

[

];for

(int

i=0;i<m;i++){ //x[][]中各行sum[i]=0.0;

//數(shù)據(jù)累加for

(

int

j=0;

j<n;

j++

)

sum[i]

+=

x[i][j];}for

(i=0;i<m;i++)

//打印各行數(shù)據(jù)和

cout

<<“Line

”<<