ContactMe:jia:(

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

()課后實習每周實驗課程大作業成績期末考試上機+課程大作業平時作業第一章 緒論§1.1

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

C1計算機圖形學

C2，C3，C3C2，C9C8C9例3：教學計劃編排問題編譯原理

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

整數數據對象N

={0,

1,

2,

…}-

學生數據對象數據結構由某一數據對象及該對象中所有數據成員之間的關系組成。記為：Data_Structure

=

{D,

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

，故又稱“結構”。根據問題來建立邏輯結構例如：Class=(D,S)數據集合：D={a,b1,…,bn,c1,…cn,d1,…dn}關系集合：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的邏輯結構的圖示結構是邏輯結構在 器中的映象。數據元素的映象：任何的數據元素在計算機中最終都是轉化成一個二進制的位串。關系的映象：…關系的映象方法：（關系對x,

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

y

的 位置和

x

的 位置之間差一個常量

C，而

C

是一個隱含值，整個結構中只含數據元素本身的信息xy2.鏈式映象:以附加信息(指針)表示后繼關系需要用一個和

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

的 位置yx§1.2

抽象數據類型及面象概念C語言中的數據類型char

int

float

double

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

(ADTs: Data

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

NaturalNumber

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

對于所有的

x,y

NaturalNumber;False,True

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

返回自然數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面 象的概念面 象

=

對象＋類＋繼承＋通信面

象方法中類的定義充分體現了抽象數據類型的思想§1.3

數據結構的抽象層次數據結構的抽象層次線性結構：表、棧、隊列非線性結構層次結構：樹，二叉樹，堆網狀結構：圖其它：集合線性結構bindevetclibuser層次結構樹二叉樹11

128

910987456231堆（特殊的樹結構）12711103

5

4

8

2“最大”堆96368

9“最小”堆7網狀結構圖結構12564312311216335

4網絡結構C++的函數特征C++的數據C++的作用域C++的類C++的對象C++的輸入/輸出C++的函數C++的參數傳遞C++的函數名重載和操作符重載C++的動態

分配(friend)函數內聯(inline)函數結構(struct)與類聯合(Union)與類§1.4

用C++描述面

象程序Niklaus

Wirth

（1976）數據結構+算法=程序設計為計算機處理問題編制一組指令集處理問題的策略問題的數學模型§1.5

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

有0個或多個輸入輸出

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

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

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

每一條運算應足夠基本一個算法必須滿足以下五個重要特性：§1.6

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

DATALIST_H#define

DATALIST_H#include

<iostream.h>//模板標識//類標識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類中所有操作作為模板函數的實現#ifndef

SELECTTM_H#define

SELECTTM_H#include

“datalist.h”template

<class

Type>void

dataList

<Type>::Swap

(const

int

m1, const

int

m2)

{//交換由m1,

m2為下標的兩個數組元素的值Type

temp

=

Element

[m1];Element

[m1]

=

Element

[m2];Element

[m2]

=

temp;}template

<class

Type>int

dataList<Type>::MaxKey

(const

int

low,

const

int

high)

{//查找數組Element[low]～Element[high]中//的最大值，函數返回其位置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

(

)

{//按非遞減順序對ArraySize個關鍵碼//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使用模板的選擇排序算法的主函數#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

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

()測定算法完成某

能所花費的時間算法的事前估計空間復雜度時間復雜度時間復雜度編譯時間運行時間–程序步：語法（義）上有意義的一段指令例如：注釋：程序步數為0語句：程序步數為0表達式、賦值語句：程序步數為1循環語句：循環控制語句每次執行的程序步數為1程序步確定方法計數全局變量count例以迭代方式求累加和的函數行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統計執行語句條數

for

(int

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

//針對for語句s

+=

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

s;}

執行結束得程序步數

count=2

*

n

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

=

sum

(R,

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

(R,n)的調用需要的程序步數為2*n+3；一次執行的程序步數為1+2*n+3

=

2*n+4

確定程序的準確程序步數十分

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

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

則

針對并列程序段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))乘 則中的常數無關項

O(C)

→

O(1)T

(n)

=

O(

c

*

f(n))

=O(f(n))Ο(1)表示常數計算時間例1：兩個并列循環void

example

(float

x[

][

],

int

m,

int

n,

int

k)

{float

sum

[

];for

(int

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

//數據累加for

(

int

j=0;

j<n;

j++

)

sum[i]

+=

x[i][j];}for

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

//打印各行數據和

cout

<<“Line

”<<