數(shù)據(jù)結(jié)構(gòu)-p第一章緒論

2/58第一章緒論數(shù)據(jù)結(jié)構(gòu)基本概念和術(shù)語抽象數(shù)據(jù)類型算法和算法分析數(shù)據(jù)結(jié)構(gòu)中用到的C語言3/58數(shù)據(jù)結(jié)構(gòu)數(shù)值數(shù)據(jù)非數(shù)值數(shù)據(jù)

數(shù)據(jù)處理的種類數(shù)（整數(shù)，實(shí)數(shù)）字符

字符串

文字

數(shù)據(jù)布爾值

圖形

圖象

聲音數(shù)據(jù)：所有能輸入到計(jì)算機(jī)中，并能被其、加工、處理的符號(hào)的集合。數(shù)據(jù)就是客觀對(duì)象的符號(hào)表示。程序1.1原始數(shù)據(jù)結(jié)果數(shù)據(jù)數(shù)據(jù)結(jié)構(gòu)1.1數(shù)值問題例1：已知游泳池的長len和寬width，求面積area。建立模型涉及的對(duì)象：游泳池的長len，寬width，面積area對(duì)象之間的關(guān)系：area=len×width設(shè)計(jì)求解問題的方法編程voidmain

(

)

{int

len,

width

,area

;scanf

(”%d%d\n”,

&len,&width);area=len*width;printf

(”area=%d”,area);}4/58數(shù)據(jù)結(jié)構(gòu)1.1非數(shù)值問題例2

已知學(xué)生選課情況，安排課程考試的日程，要求在盡可能短的時(shí)間內(nèi)完成考試。選課情況表選修課1選修課2選修課3算法分析（A）形式語言（B）計(jì)算機(jī)網(wǎng)絡(luò)（E）石 磊

計(jì)算機(jī)圖形學(xué)（C）

模式識(shí)別（D）計(jì)算機(jī)圖形學(xué)（C）計(jì)算機(jī)網(wǎng)絡(luò)（E）人工智能（F）模式識(shí)別（D

）人工智能（F）算法分析（A）形式語言（B）人工智能（F）5/581.1數(shù)據(jù)結(jié)構(gòu)選課情況表

選修課1選修課2選修課3算法分析（A）形式語言（B）計(jì)算機(jī)網(wǎng)絡(luò)（E）石 磊

計(jì)算機(jī)圖形學(xué)（C）

模式識(shí)別（D）計(jì)算機(jī)圖形學(xué)（C）計(jì)算機(jī)網(wǎng)絡(luò)（E）人工智能（F）模式識(shí)別（D

）形式語言（B）人工智能（F）人工智能（F）算法分析（A）建立模型問題涉及的對(duì)象：課程課程之間的關(guān)系：同一選修的課程之間有某選修的課程不能安排在同一時(shí)種“

”關(guān)系。要求：同一個(gè)間進(jìn)行內(nèi)考試。6/587/581.1數(shù)據(jù)結(jié)構(gòu)選課情況表

選修課1算法分析（A）選修課2形式語言（B）選修課3計(jì)算機(jī)網(wǎng)絡(luò)（E）石 磊

計(jì)算機(jī)圖形學(xué)（C）

模式識(shí)別（D）計(jì)算機(jī)圖形學(xué)（C）計(jì)算機(jī)網(wǎng)絡(luò)（E）人工智能（F）模式識(shí)別（D

）形式語言（B）人工智能（F） 算法分析（A）人工智能（F）DEFCBA頂點(diǎn)：表示課程同一學(xué)生選修的課程用邊連接有邊連接的課程不能安排在同一時(shí)間考試；8/58數(shù)據(jù)結(jié)構(gòu)1.1設(shè)計(jì)求解問題的方法課程考試可用圖的法求解問題。每一種顏色代表一個(gè)考試時(shí)間，著上相同顏色的頂點(diǎn)是可以安排在同一時(shí)間考試的課程；，使相鄰的頂DEFBA用盡可能少的顏色為圖的頂點(diǎn)點(diǎn)著上不同的顏色。如下是一種考試日程：1:算法分析(A)計(jì)算機(jī)圖形學(xué)(C)2:形式語言(B)模式識(shí)別人工智能（D)

C3:計(jì)算機(jī)網(wǎng)絡(luò)(E)4:人工智能(F)9/581.1數(shù)據(jù)結(jié)構(gòu)求解考試日程的流程:設(shè)：G表示課程關(guān)系圖，V是圖G中所有尚未的頂點(diǎn)集合，NEW表示可以用新顏色

的頂點(diǎn)集合。1)I=1；V={圖中所有頂點(diǎn)的集合}若V非空DO置NEW為空集合；在V中找出所有“不相鄰”的頂點(diǎn)將這些頂點(diǎn)加入NEW，從V中去掉這些頂點(diǎn)（第I天考試課程為NEW中頂點(diǎn)所對(duì)應(yīng)的課程）以某種形式輸出NEW中頂點(diǎn)所對(duì)應(yīng)的課程；

I=I+1；若V空，結(jié)束編程圖，集合實(shí)現(xiàn)圖/集合的操作1.1數(shù)據(jù)結(jié)構(gòu)數(shù)值問題與非數(shù)值問題的比較數(shù)值問題對(duì)象：len,wide,area——用數(shù)值表示對(duì)象之間的關(guān)系：area=lenwide——用方程或函數(shù)表示數(shù)據(jù)

：可用程序設(shè)計(jì)語言中的實(shí)型變量 數(shù)據(jù)問題求解方法：某種數(shù)值計(jì)算方法求解非數(shù)值問題*對(duì)象：課程——用課程名表示對(duì)象之間的關(guān)系：課程間有“

”關(guān)系數(shù)據(jù)

：數(shù)據(jù)及數(shù)據(jù)之間的關(guān)系問題求解方法不能用數(shù)值表示課程之間的這種關(guān)系不能用方程或函數(shù)表10示/58數(shù)據(jù)結(jié)構(gòu)1.1數(shù)據(jù)結(jié)構(gòu)所研究的問題何非數(shù)值數(shù)據(jù)之間的結(jié)構(gòu)關(guān)系，及如何表示，如，如何處理。本課程

的問題以下兩方面的問應(yīng)用中最常用的幾種數(shù)據(jù)結(jié)構(gòu)。對(duì)于每一種數(shù)據(jù)結(jié)構(gòu)，主要題：數(shù)據(jù)的邏輯結(jié)構(gòu)，數(shù)據(jù)結(jié)構(gòu)的基本操作；數(shù)據(jù)的

結(jié)構(gòu)，數(shù)據(jù)結(jié)構(gòu)基本操作的實(shí)現(xiàn)。11/58數(shù)據(jù)結(jié)構(gòu)?1.1數(shù)據(jù)結(jié)構(gòu)？數(shù)據(jù)結(jié)構(gòu)是一門“描述現(xiàn)實(shí)世界實(shí)體的數(shù)學(xué)模型（非數(shù)值計(jì)算）及其上的操作在計(jì)算機(jī)中如何表示”的學(xué)科。1968年， 的

D.E.Knuth

教授開創(chuàng)了數(shù)據(jù)結(jié)構(gòu)的最初體系，他的名著《計(jì)算機(jī)程序設(shè)計(jì)技巧》較為系統(tǒng)地闡述了數(shù)據(jù)的邏輯結(jié)構(gòu)和

結(jié)構(gòu)及其操作。12/581.2

基本概念和術(shù)語數(shù)據(jù)(data)：客觀對(duì)象的符號(hào)表示。數(shù)據(jù)元素(dataelement)：數(shù)據(jù)的基本單位，在計(jì)算機(jī)程序中通常作為一個(gè)整體考慮和處理，通常具有完整確定的實(shí)際意義。（節(jié)點(diǎn)、頂點(diǎn)、記錄）數(shù)據(jù)項(xiàng)(dataitem)：數(shù)據(jù)不可分割的最小標(biāo)識(shí)單位。一個(gè)數(shù)據(jù)元素可由若干數(shù)據(jù)項(xiàng)組成，通常不具有完整確定的實(shí)際意義。（字段）0001男19491001工程師0002黃

紅女19650506助工0003張

華女19461118高工……………13/581.2

基本概念和術(shù)語數(shù)據(jù)結(jié)構(gòu)(datastructure)：具有相同特征的數(shù)據(jù)元素的集合，如果在這些數(shù)據(jù)元

間存在一種或多種特定的關(guān)系，則稱為一種數(shù)據(jù)結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)：帶有結(jié)構(gòu)和操作的數(shù)據(jù)元素集合。結(jié)構(gòu)：數(shù)據(jù)元

間的關(guān)系；操作：對(duì)數(shù)據(jù)的加工處理。對(duì)每種數(shù)據(jù)結(jié)構(gòu)，主要

如下兩方面的問題：數(shù)據(jù)的邏輯結(jié)構(gòu)，數(shù)據(jù)結(jié)構(gòu)的基本操作數(shù)據(jù)的

結(jié)構(gòu)，數(shù)據(jù)結(jié)構(gòu)基本操作的實(shí)現(xiàn)。14/581.2

基本概念和術(shù)語數(shù)據(jù)的邏輯結(jié)構(gòu)：數(shù)據(jù)之間的結(jié)構(gòu)關(guān)系，是具體關(guān)系的抽象。數(shù)據(jù)元

間存在四種基本結(jié)構(gòu)集合（無關(guān)系）線性結(jié)構(gòu)（一對(duì)一）樹形結(jié)構(gòu)（一對(duì)多）圖狀結(jié)構(gòu)（多對(duì)多）15/581.2

基本概念和術(shù)語線性結(jié)構(gòu):學(xué)生基本情況登記表，記錄了每個(gè)學(xué)生的學(xué)號(hào)、、專業(yè)、政治面貌，記錄按學(xué)生的學(xué)號(hào)順序排列。001學(xué)生間學(xué)號(hào)順序關(guān)系是一種線性結(jié)構(gòu)關(guān)系線性結(jié)構(gòu)：除第一個(gè)元素和最后一個(gè)元素外，其他元素都有且僅有一個(gè)直接前趨，有且僅有一個(gè)直接后繼。002

003

004

005

006

007

008學(xué)號(hào)001002003004005006007008專業(yè)

政治面貌計(jì)算機(jī)

黨員計(jì)算機(jī)

團(tuán)員計(jì)算機(jī)

團(tuán)員計(jì)算機(jī)

團(tuán)員計(jì)算機(jī)

黨員計(jì)算機(jī)

團(tuán)員計(jì)算機(jī)

團(tuán)員計(jì)算機(jī)

團(tuán)員16/581.2

基本概念和術(shù)語J樹形結(jié)構(gòu):假設(shè)某

有10個(gè)成員A、B、C、D、E、F、G、H、I、J，他們之間的血緣關(guān)系可以用圖表示。ACBDE

F

G

H

I樹形結(jié)構(gòu)：每一個(gè)元素只有一個(gè)直接前趨，有0個(gè)或多個(gè)直接后繼。17/581.2

基本概念和術(shù)語圖形結(jié)構(gòu)：每一個(gè)元素可以有0個(gè)或多個(gè)直V1接前趨，有0個(gè)或多個(gè)直接后繼。18/58V0圖形結(jié)構(gòu):工程進(jìn)度圖。V2V3V4V5V619/581.2

基本概念和術(shù)語數(shù)據(jù)結(jié)構(gòu)的表示圖示表示圖示表示是由頂點(diǎn)和邊構(gòu)成的圖，其中頂點(diǎn)表示數(shù)據(jù)，邊表示數(shù)據(jù)之間的結(jié)構(gòu)關(guān)系。二元組表示二元組表示是用一個(gè)二元組（D，S）表示數(shù)據(jù)結(jié)

構(gòu)，其中D是數(shù)據(jù)元素集合，S

是D上關(guān)系的集合。1.2

基本概念和術(shù)語例：學(xué)生基本情況表的二元組表示（D，S）00120/58002

003

004

005

006

007

008D

=

{

001，002，003，004，005，006，007，008

}S=

{R}R

=

{

<001,002>,

<002,003>,

<003,004>,<004,005>,

<005,006>,

<006,007>,

<007,008>

}1.2

基本概念和術(shù)語例：D

=

{

A，B，C，D，E，F(xiàn)，G，H，I，J

}S

={

R}R

={<A,B>,

<A,C>,

<A,D>,

<B,E>,

<B,F>,<C,G>,

<D,H>,

<D,I>, <D,J>

}J樹的二元組表示（D，S）AB

C

DE

F

G

H

I21/581.2

基本概念和術(shù)語數(shù)據(jù)的結(jié)構(gòu)邏輯結(jié)構(gòu)：從操作對(duì)象抽象出來的數(shù)學(xué)模型。結(jié)構(gòu)：邏輯結(jié)構(gòu)在計(jì)算機(jī)中的表示。結(jié)構(gòu)結(jié)構(gòu)，鏈?zhǔn)?/p>

結(jié)構(gòu)，散列結(jié)構(gòu)和索引結(jié)構(gòu)。結(jié)構(gòu)：借助元素在器中的相對(duì)位置來表示數(shù)間的邏輯關(guān)系（一維數(shù)組描述）。常見的順序順序據(jù)元鏈?zhǔn)浇Y(jié)構(gòu)：借助指示元素地址的指針來表示數(shù)據(jù)元

間的邏輯關(guān)系（指針類型描述）。注意：算法的設(shè)計(jì)取決于所選定的邏輯結(jié)構(gòu)，算法的實(shí)現(xiàn)則依賴于采用的

結(jié)構(gòu)。22/5823/581.2

基本概念和術(shù)語順序Lo元素1Lo+m元素2Lo+(i-1)*m……..元素iLo+（n-1)*m……..元素n結(jié)構(gòu)地址

內(nèi)容Loc(元素i)=Lo+（i-1)*

m鏈?zhǔn)?.2

基本概念和術(shù)語結(jié)構(gòu)1536元素21400元素11346元素3∧元素41345h地址內(nèi)容指針1345元素114001346元素4∧…….……..…….1400元素21536…….……..…….1536元素3134624/581.3

抽象數(shù)據(jù)類型ADT是一種描述用戶與數(shù)據(jù)之間接口的抽象模型。它定義了一個(gè)數(shù)據(jù)模型和在這個(gè)數(shù)據(jù)模型上的一組操作。注意：抽象數(shù)據(jù)類型的定義僅取決于它的一組邏輯特性，而與其在計(jì)算機(jī)

如何表示

無關(guān)，即不論其結(jié)構(gòu)如何變化，只要它的數(shù)學(xué)特性不變，都不影響其外部的使用。ADT抽象數(shù)據(jù)類型名{數(shù)據(jù)對(duì)象：<數(shù)據(jù)對(duì)象的定義>數(shù)據(jù)關(guān)系：<數(shù)據(jù)關(guān)系的定義>基本操作：<基本操作的定義>}25/5826/581.3

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

List

{數(shù)據(jù)對(duì)象：D={a1,

a2

,...

,

ai

-1, ai

, ai+1,

…,

an}數(shù)據(jù)關(guān)系：r={<a1,a2>,<a2,a3>,…,<an-1,an>}基本操作：<基本操作的定義>InitList(&L)操作結(jié)果：構(gòu)造一個(gè)空的線性表L；DetroyList(&L)初始條件：線性表已存在操作結(jié)果：銷毀線性表LClearList(&L)初始條件：線性表已存在操作結(jié)果：將L重置為空表ListEmpty(L)初始條件：線性表已存在操作結(jié)果：若L為空表返回TRUE，否則返回FALSE…}1.4

算法與算法分析27/58算法是為了解決某類問題而規(guī)定的一個(gè)有限長的操作序列。一個(gè)算法必須滿足以下五個(gè)重要特性：有窮性、確定性、可行性、有輸入和有輸出。有窮性：算法必須在有限步內(nèi)結(jié)束。確定性：算法的操作清晰無二義性?？尚行裕核惴ǖ牟僮鞅仨毮軌?qū)崿F(xiàn)。有輸入：有0個(gè)或多個(gè)輸入。有輸出：有1個(gè)或多個(gè)輸出。評(píng)價(jià)算法的標(biāo)準(zhǔn):正確性可讀性健壯性高效率與低

量需求1.4

算法與算法分析28/581．正確性29/58首先，算法應(yīng)當(dāng)滿足以特定的“規(guī)格說明”方式給出的需求。其次，對(duì)算法是否“正確”的理解可以有以下四個(gè)層次：程序中不含語法錯(cuò)誤；程序?qū)τ趲捉M輸入數(shù)據(jù)能夠得出滿足要求的結(jié)果；c．程序?qū)τ诰倪x擇的、典型、苛刻且?guī)в械箅y性的幾組輸入數(shù)據(jù)能夠得出滿足要求的結(jié)果；30/58d．程序?qū)τ谝磺泻戏ǖ妮斎霐?shù)據(jù)都能得出滿足要求的結(jié)果；通常以第c

層意義的正確性作為衡量一個(gè)算法是否合格的標(biāo)準(zhǔn)。2.可讀性31/58算法主要是為了人的閱讀與交流，其次才是為計(jì)算機(jī)執(zhí)行，因此算法應(yīng)該易于人的理解；另一方面，晦澀難讀的程序易于隱藏較多錯(cuò)誤而難以調(diào)試。3．健壯性當(dāng)輸入的數(shù)據(jù)時(shí)，算法應(yīng)當(dāng)恰當(dāng)?shù)刈鞒龇从郴蜻M(jìn)行相應(yīng)處理，而不是產(chǎn)生莫名奇妙的輸出結(jié)果。并且，處理出錯(cuò)的方法不應(yīng)是中斷程序的執(zhí)行，而應(yīng)是返回一個(gè)表示錯(cuò)誤或錯(cuò)誤性質(zhì)的值，以便在更高的抽象層次上進(jìn)行處理。32/584．高效率與低 量需求通常，效率指的是算法執(zhí)行時(shí)間；量指的是算法執(zhí)行過程中所需的最大 空間，兩者都與問題的規(guī)模有關(guān)。33/581.4

算法與算法分析34/58算法效率的度量算法的時(shí)間復(fù)雜度：算法的時(shí)間效率算法的空間復(fù)雜度：算法的空間效率算法效率的35/58衡量方法和準(zhǔn)則通常有兩種衡量算法效率的方法:事后統(tǒng)計(jì)法缺點(diǎn)：1．必須執(zhí)行程序2．其它因素掩蓋算法本質(zhì)事前分析估算法和算法執(zhí)行時(shí)間相關(guān)的因素：36/58算法選用的策略問題的規(guī)模編寫程序的語言編譯程序產(chǎn)生的機(jī)器代碼的質(zhì)量計(jì)算機(jī)執(zhí)行指令的速度一個(gè)特定算法的“運(yùn)行工作量”的大小，只依賴于問題的規(guī)模（通常用整數(shù)量n表示），或者說，它是問題規(guī)模的函數(shù)。37/5838/58假如，隨著問題規(guī)模n

的增長，算法執(zhí)行時(shí)間的增長率和f(n)的增長率相同，則可記作：T

(n)=O(f(n))稱T(n)為算法的(漸近)時(shí)間復(fù)雜度。nf

(n)lim

T

(n)

C如何估算算法的時(shí)間復(fù)雜度？39/58算法=控制結(jié)構(gòu)+原操作（固有數(shù)據(jù)類型的操作）40/58算法的執(zhí)行時(shí)間=∑原操作(i)的執(zhí)行次數(shù)×原操作(i)的執(zhí)行時(shí)間算法的執(zhí)行時(shí)間與

原操作執(zhí)行次數(shù)之和

成正比41/58從算法中選取一種對(duì)于所研究的問題來說是基本操作的原操作，以該基本操作在算法中重復(fù)執(zhí)行的次數(shù)作為算法運(yùn)行時(shí)間的衡量準(zhǔn)則?；静僮鲬?yīng)是其重復(fù)執(zhí)行次數(shù)和算法執(zhí)行時(shí)間成正比的原操作，一般是最 次內(nèi)的語句。例一兩個(gè)矩陣相乘void

mult(int

a[],

int

b[],

int&c[]

)

{//以二維數(shù)組

矩陣元素，c

為

a和

b

的乘積for

(i=1;

i<=n;

++i)for

(j=1;

j<=n;

++j){c[i,j]

=

0;for

(k=1;

k<=n;

++k)c[i,j]

+=a[i,k]*b[k,j];}

//for}

//mult時(shí)間復(fù)雜度:O(n3)42/58選擇排序43/58例void

select_sort(int&

a[],

int

n)

{時(shí)間復(fù)雜度:O(n2)j

=i;//選擇第i個(gè)最小元素二

//

將

a

中整數(shù)序列重新排列成自小至大有序的整數(shù)序列。for

(

i

=

0; i<

n-1;

++i

)

{for

(

k

=

i+1; k

<n;

++k

)if

(a[k]

<

a[j]

) j

=k;if

(j

!=

i) a[j]

←→

a[i]}}

//

select_sort三44/58泡排序例void

bubble_sort(int&

a[],int

n){//將a

中整數(shù)序列重新排列成自小至大有序的整數(shù)序列。起

for

(i=n-1,

change=TRUE; i>1

&&

change;

--i)時(shí)間復(fù)雜度:O(n2){

change=FALSE;

//change

為元素進(jìn)行交換標(biāo)志for

(j=0;

j<i;

++j)if

(a[j]

>

a[j+1])change

=

TRUE

;}{

a[j]

←→

a[j+1];}//一趟起泡}

//

bubble_sort四、算法的

空間需求算法的空間復(fù)雜度定義為:S(n)

=

O(g(n))表示隨著問題規(guī)模

n的增大，算法運(yùn)行所需 量的增長率與g(n)

的增長率相同。45/58算法的

量包括:1．輸入數(shù)據(jù)所占空間程序本身所占空間輔助變量所占空間46/58若輸入數(shù)據(jù)所占空間只取決于問題本身，和算法無關(guān)，則只需要分析除輸入和程序之外的輔助變量所占額外空間。若所需額外空間相對(duì)于輸入數(shù)據(jù)量來說是常數(shù)，則稱此算法為原地工作。若所需 量依賴于特定的輸入，則通常按 情況考慮。47/5848/581.5

數(shù)據(jù)結(jié)構(gòu)中用到的C語言本課程采用的類C語言描述算法，類C語言精選了C語言的一個(gè)

子集，同時(shí)作了若干擴(kuò)充修改，增強(qiáng)了語言的描述功能。預(yù)定義常量和類型//函數(shù)結(jié)果狀態(tài)代碼TRUE

1FALSE

0ERROR

0#define#define#define

OK

1#define#defineOVERFLOW -2//Status

是函數(shù)的類型，其值是函數(shù)結(jié)果狀態(tài)代碼typedef

int

Status;49/581.5

數(shù)據(jù)結(jié)構(gòu)中用到的C語言值傳遞–普通參數(shù)–指針參數(shù)傳遞參數(shù)。

參數(shù)是實(shí)參的別名，所謂別名就是同一變量的另外一個(gè)名字。50/581.5

數(shù)據(jù)結(jié)構(gòu)中用到的C語言{

//函數(shù)定義//參數(shù)為值參數(shù)inttemp;temp=n;n=m;m=temp;交換兩個(gè)整數(shù)變量的算法void

swap

(int

n,

int

m

) void

swap&

(

int

&n,int

&m)參數(shù){

//函數(shù)定義//參數(shù)為inttemp;temp=n;n=m;m=temp;}}main(

){int

a=10,b=20,c=10,d=20;swap(a,

b

);swap&(

c,

d);//函數(shù)調(diào)用//函數(shù)調(diào)用}結(jié)果：a=10,b=20c=20,d=10nm10ab20參數(shù)傳遞

執(zhí)行Swap()2051/5810main(

){inta=10,b=20;swap(a,b);}void

swap

(

intn,int

m){int

temp;temp=n;n=m;m=temp;}1.5

數(shù)據(jù)結(jié)構(gòu)中用到的C語言00ab2010參數(shù)傳遞執(zhí)行Swap&()nminttemp;temp=n;n=m;m=temp;}main(

){i