專業(yè)課參考-數(shù)據(jù)結(jié)構(gòu)

1第1章緒論2第一章緒論

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

1.2基本概念和術(shù)語

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

1.4算法和算法分析

1.5數(shù)據(jù)結(jié)構(gòu)中用到的C語言31.1什么是數(shù)據(jù)結(jié)構(gòu)

數(shù)據(jù)處理的種類數(shù)據(jù)數(shù)值數(shù)據(jù)非數(shù)值數(shù)據(jù)數(shù)（整數(shù)，實(shí)數(shù)）字符字符串文字布爾值圖形圖象聲音數(shù)據(jù)：所有能輸入到計(jì)算機(jī)中，并能被其存儲(chǔ)、加工、處理的符號的集合。數(shù)據(jù)就是客觀對象的符號表示。

程序原始數(shù)據(jù)結(jié)果數(shù)據(jù)41.1什么是數(shù)據(jù)結(jié)構(gòu)數(shù)值問題例1：已知游泳池的長len和寬width，求面積area。建立模型

涉及的對象：游泳池的長len，寬width，面積area

對象之間的關(guān)系：area=len×width設(shè)計(jì)求解問題的方法編程 main() { intlen,width,area;

scanf(”%d%d”,&len,&width);

area=len*width;

printf(”area=%d\n”,area);

}51.1什么是數(shù)據(jù)結(jié)構(gòu)非數(shù)值問題 例2已知學(xué)生選課情況，安排課程考試的日程，要求在盡可能短的時(shí)間內(nèi)完成考試。學(xué)生選課情況表姓名選修課1 選修課2選修課3 楊潤生算法分析（A）形式語言（B）計(jì)算機(jī)網(wǎng)絡(luò)（E）

石磊計(jì)算機(jī)圖形學(xué)（C）模式識別（D）

魏慶濤計(jì)算機(jī)圖形學(xué)（C）計(jì)算機(jī)網(wǎng)絡(luò)（E）人工智能（F）

馬耀先模式識別（D）人工智能（F）算法分析（A）

齊硯生形式語言（B）人工智能（F）61.1什么是數(shù)據(jù)結(jié)構(gòu)學(xué)生選課情況表姓名選修課1 選修課2選修課3 楊潤生算法分析（A）形式語言（B）計(jì)算機(jī)網(wǎng)絡(luò)（E）

石磊計(jì)算機(jī)圖形學(xué)（C）模式識別（D）

魏慶濤計(jì)算機(jī)圖形學(xué)（C）計(jì)算機(jī)網(wǎng)絡(luò)（E）人工智能（F）

馬耀先模式識別（D）人工智能（F）算法分析（A）

齊硯生形式語言（B）人工智能（F）◆建立模型

問題涉及的對象：課程

課程之間的關(guān)系：同一學(xué)生選修的課程之間有某種“沖突”關(guān)系。要求：同一個(gè)學(xué)生選修的課程不能安排在同一時(shí)間進(jìn)行內(nèi)考試。

71.1什么是數(shù)據(jù)結(jié)構(gòu)學(xué)生選課情況表姓名選修課1 選修課2選修課3 楊潤生算法分析（A）形式語言（B）計(jì)算機(jī)網(wǎng)絡(luò)（E）

石磊計(jì)算機(jī)圖形學(xué)（C）模式識別（D）

魏慶濤計(jì)算機(jī)圖形學(xué)（C）計(jì)算機(jī)網(wǎng)絡(luò)（E）人工智能（F）

馬耀先模式識別（D）人工智能（F）算法分析（A）

齊硯生形式語言（B）人工智能（F）DEFCBA頂點(diǎn)：表示課程同一學(xué)生選修的課程用邊連接有邊連接的課程不能安排在同一時(shí)間考試；81.1什么是數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)求解問題的方法 課程考試可用圖的著色法求解問題。 每一種顏色代表一個(gè)考試時(shí)間，著上相同顏色的頂點(diǎn)是可以安排在同一時(shí)間考試的課程； 用盡可能少的顏色為圖的頂點(diǎn)著色，使相鄰的頂點(diǎn)著上不同的顏色。ACEFBDDEFCBA如下是一種考試日程：

1:算法分析(A)計(jì)算機(jī)圖形學(xué)(C)2:形式語言(B)模式識別人工智能（D)3:計(jì)算機(jī)網(wǎng)絡(luò)(E)4:人工智能(F)91.1什么是數(shù)據(jù)結(jié)構(gòu)求解考試日程的流程設(shè)：G表示課程關(guān)系圖，V是圖G中所有尚未著色的頂點(diǎn)集合，NEW表示可以用新顏色著色的頂點(diǎn)集合。1)I=1；V={圖中所有頂點(diǎn)的集合}

2)若V非空DO

置NEW為空集合；

在V中找出所有“不相鄰”的頂點(diǎn)

將這些頂點(diǎn)加入NEW，從V中去掉這些頂點(diǎn)

（第I天考試課程為NEW中頂點(diǎn)所對應(yīng)的課程）

以某種形式輸出NEW中頂點(diǎn)所對應(yīng)的課程；

I=I+1；3)若V空，結(jié)束◆編程

存儲(chǔ)圖，集合實(shí)現(xiàn)圖/集合的操作101.1什么是數(shù)據(jù)結(jié)構(gòu)數(shù)值問題與非數(shù)值問題的比較數(shù)值問題*對象：len,wide,area

——用數(shù)值表示*對象之間的關(guān)系：

area=lenwide

——用方程或函數(shù)表示*數(shù)據(jù)存儲(chǔ)：可用程序設(shè)計(jì)語言中的實(shí)型變量存儲(chǔ)數(shù)據(jù)*問題求解方法：某種數(shù)值計(jì)算方法求解

非數(shù)值問題*對象：課程——用課程名表示*對象之間的關(guān)系：課程間有“沖突”關(guān)系*數(shù)據(jù)存儲(chǔ)：數(shù)據(jù)及數(shù)據(jù)之間的關(guān)系存儲(chǔ)*問題求解方法不能用數(shù)值表示課程之間的這種關(guān)系不能用方程或函數(shù)表示111.1什么是數(shù)據(jù)結(jié)構(gòu)什么是數(shù)據(jù)結(jié)構(gòu)？

數(shù)據(jù)結(jié)構(gòu)是一門討論“描述現(xiàn)實(shí)世界實(shí)體的數(shù)學(xué)模型（非數(shù)值計(jì)算）及其上的操作在計(jì)算機(jī)中如何表示和實(shí)現(xiàn)”的學(xué)科。 1968年，美國的D.E.Knuth(DonaldErvinKnuth)教授開創(chuàng)了數(shù)據(jù)結(jié)構(gòu)的最初體系，他的名著《計(jì)算機(jī)程序設(shè)計(jì)技巧》較為系統(tǒng)地闡述了數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)及其操作。121.1什么是數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)所研究的問題 非數(shù)值數(shù)據(jù)之間的結(jié)構(gòu)關(guān)系，及如何表示，如何存儲(chǔ)，如何處理。本課程討論的問題 應(yīng)用中最常用的幾種數(shù)據(jù)結(jié)構(gòu)。

131.2基本概念和術(shù)語數(shù)據(jù)(data)：客觀對象的符號表示。數(shù)據(jù)元素(dataelement)：數(shù)據(jù)的基本單位，在計(jì)算機(jī)程序中通常作為一個(gè)整體考慮和處理，通常具有完整確定的實(shí)際意義。（節(jié)點(diǎn)、頂點(diǎn)、記錄）數(shù)據(jù)項(xiàng)(dataitem)：數(shù)據(jù)不可分割的最小標(biāo)識單位。一個(gè)數(shù)據(jù)元素可由若干數(shù)據(jù)項(xiàng)組成，通常不具有完整確定的實(shí)際意義。（字段）0001劉建國男19491001工程師0002黃紅女19650506助工0003張華女19461118高工……………141.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)系；

操作：對數(shù)據(jù)的加工處理。

對每種數(shù)據(jù)結(jié)構(gòu)，主要討論如下兩方面的問題： 1)數(shù)據(jù)的邏輯結(jié)構(gòu)，數(shù)據(jù)結(jié)構(gòu)的基本操作 2)數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)，數(shù)據(jù)結(jié)構(gòu)基本操作的實(shí)現(xiàn)。151.2基本概念和術(shù)語數(shù)據(jù)的邏輯結(jié)構(gòu)：

數(shù)據(jù)之間的邏輯關(guān)系，是抽象的數(shù)學(xué)模型。數(shù)據(jù)元素之間存在四種基本結(jié)構(gòu)集合（無關(guān)系）線性結(jié)構(gòu)（一對一）樹形結(jié)構(gòu)（一對多）圖狀結(jié)構(gòu)（多對多）161.2基本概念和術(shù)語線性結(jié)構(gòu) 學(xué)生基本情況登記表，記錄了每個(gè)學(xué)生的學(xué)號、姓名、專業(yè)、政治面貌，記錄按學(xué)生的學(xué)號順序排列。

001003002004006005008007學(xué)生間學(xué)號順序關(guān)系是一種線性結(jié)構(gòu)關(guān)系線性結(jié)構(gòu)：除第一個(gè)元素和最后一個(gè)元素外，其他元素都有且僅有一個(gè)直接前趨，有且僅有一個(gè)直接后繼。學(xué)號姓名 專業(yè)政治面貌001 王洪 計(jì)算機(jī)黨員002孫文計(jì)算機(jī)團(tuán)員003 謝軍 計(jì)算機(jī)團(tuán)員004 李輝 計(jì)算機(jī)團(tuán)員005 沈祥福計(jì)算機(jī)黨員006 余斌 計(jì)算機(jī)團(tuán)員

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

008 孔令輝計(jì)算機(jī)團(tuán)員171.2基本概念和術(shù)語樹形結(jié)構(gòu) 假設(shè)某家族有10個(gè)成員A、B、C、D、E、F、G、H、I、J，他們之間的血緣關(guān)系可以用圖表示。JIACBDHGFE樹形結(jié)構(gòu)：每一個(gè)元素只有一個(gè)直接前趨，有0個(gè)或多個(gè)直接后繼。181.2基本概念和術(shù)語圖形結(jié)構(gòu) 工程進(jìn)度圖。圖形結(jié)構(gòu)：每一個(gè)元素可以有0個(gè)或多個(gè)直接前趨，有0個(gè)或多個(gè)直接后繼。

V1

V0

V2

V3

V4

V5

V6191.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)系的集合。201.2基本概念和術(shù)語例：學(xué)生基本情況表的二元組表示（D，S）

001003002004006005008007D={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>}211.2基本概念和術(shù)語例：家族樹的二元組表示（D，S）

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>}JIACBDHGFE221.2基本概念和術(shù)語數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)：

邏輯結(jié)構(gòu)在計(jì)算機(jī)中的表示。常見的存儲(chǔ)結(jié)構(gòu)

順序存儲(chǔ)結(jié)構(gòu)，鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，散列結(jié)構(gòu)和索引結(jié)構(gòu)。順序存儲(chǔ)結(jié)構(gòu)：借助元素在存儲(chǔ)器中的相對位置來表示數(shù)據(jù)元素之間的邏輯關(guān)系（一維數(shù)組描述）。鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)：借助指示元素存儲(chǔ)地址的指針來表示數(shù)據(jù)元素之間的邏輯關(guān)系（指針類型描述）。注意：算法的設(shè)計(jì)取決于所選定的邏輯結(jié)構(gòu)，算法的實(shí)現(xiàn)則依賴于采用的存儲(chǔ)結(jié)構(gòu)。231.2基本概念和術(shù)語順序存儲(chǔ)結(jié)構(gòu)元素n……..元素i……..元素2元素1LoLo+mLo+(i-1)*mLo+（n-1)*m存儲(chǔ)地址存儲(chǔ)內(nèi)容Loc(元素i)=Lo+（i-1)*m241.2基本概念和術(shù)語鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)1536元素21400元素11386元素3

∧元素41345h存儲(chǔ)地址

存儲(chǔ)內(nèi)容

指針

1345元素1

1400

1386元素4

∧

…….

……..

…….

1400元素2

1536

…….

……..

…….

1536元素3

1386251.3抽象數(shù)據(jù)類型 ADT是一種描述用戶與數(shù)據(jù)之間接口的抽象模型。它定義了一個(gè)數(shù)據(jù)模型和在這個(gè)數(shù)據(jù)模型上的一組操作。

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

數(shù)據(jù)對象：<數(shù)據(jù)對象的定義>

數(shù)據(jù)關(guān)系：<數(shù)據(jù)關(guān)系的定義>

基本操作：<基本操作的定義>}

注意：抽象數(shù)據(jù)類型的定義僅取決于它的一組邏輯特性，而與其在計(jì)算機(jī)內(nèi)部如何表示和實(shí)現(xiàn)無關(guān)，即不論其內(nèi)部結(jié)構(gòu)如何變化，只要它的數(shù)學(xué)特性不變，都不影響其外部的使用。261.3抽象數(shù)據(jù)類型ADTList{

數(shù)據(jù)對象：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é)果：銷毀線性表L

ClearList(&L)

初始條件：線性表已存在 操作結(jié)果：將L重置為空表

ListEmpty(L)

初始條件：線性表已存在 操作結(jié)果：若L為空表返回TRUE，否則返回FALSE

…

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

正確性，可讀性，可維護(hù)性，健壯性，效率。算法效率的度量

計(jì)算復(fù)雜度、漸進(jìn)復(fù)雜度

時(shí)間復(fù)雜度：算法的時(shí)間效率T(n)=O(f(n))

空間復(fù)雜度：算法的空間效率S(n)=O(f(n))

*基本操作次數(shù)f(n)為問題規(guī)模n的函數(shù)291.5數(shù)據(jù)結(jié)構(gòu)中用到的C語言 本課程采用的類C語言描述算法，類C語言精選了C語言的一個(gè)核心子集，同時(shí)作了若干擴(kuò)充修改，增強(qiáng)了語言的描述功能。預(yù)定義常量和類型

//函數(shù)結(jié)果狀態(tài)代碼

#defineTRUE1

#defineFALSE0

#defineOK1

#defineERROR0

#defineOVERFLOW-2

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

typedefintStatus;301.5數(shù)據(jù)結(jié)構(gòu)中用到的C語言值傳遞普通參數(shù)指針參數(shù)引用傳遞 引用參數(shù)。引用參數(shù)是實(shí)參的別名，所謂別名就是同一變量的另外一個(gè)名字。311.5數(shù)據(jù)結(jié)構(gòu)中用到的C語言交換兩個(gè)整數(shù)變量的算法voidswap(intn,intm){//函數(shù)定義

//參數(shù)為值參數(shù)

inttemp;

temp=n;n=m;m=temp;

}voidswap&(int&n,int&m){//函數(shù)定義

//參數(shù)為引用參數(shù)

inttemp;

temp=n;n=m;m=temp;

}main(){inta=10,b=20,c=10,d=20;

swap(a,b);//函數(shù)調(diào)用

swap&(c,d);//函數(shù)調(diào)用

printf(”%d%d%d%d\n”,a,b,c,d);}結(jié)果：a=10,b=20

c=20,d=1032nma10b20參數(shù)傳遞1020執(zhí)行Swap()2010voidswap(intn,intm){

inttemp;

temp=n;n=m;m=temp;

}main(){

inta=10,b=20;

swap(a,b);

printf(”%d%d\n”,a,b);

}1.5數(shù)據(jù)結(jié)構(gòu)中用到的C語言33ab1020執(zhí)行Swap&()ab2010參數(shù)傳遞nmvoidswap&(int&n,int&m){inttemp;

temp=n;n=m;m=temp;

}main(){

inta=10,b=20;

swap&(a,b);printf(”%d%d\n”,a,b);

}對數(shù)據(jù)有修改作用的操作（函數(shù)），要用引用參數(shù)作形參，而不能用值參作形參1.5數(shù)據(jù)結(jié)構(gòu)中用到的C語言34小結(jié)—必須掌握的基本概念數(shù)據(jù)結(jié)構(gòu)定義:是一門研究非數(shù)值計(jì)算