數(shù)據(jù)結(jié)構(gòu)1數(shù)據(jù)結(jié)構(gòu)1教材：《數(shù)據(jù)結(jié)構(gòu)》浙江大學(xué)出版社《數(shù)據(jù)結(jié)構(gòu)（C語言版）》嚴(yán)蔚敏、吳偉民編著,清華大學(xué)出版社主要參考教材：《數(shù)據(jù)結(jié)構(gòu)》張乃孝編著，高等教育出版社《DATASTRUCTURES&PROGRAMDESIGNINC》RobertL.KrusePrentice-HallInternational,Inc.主講：周玉林電話QQ：279635371Email：srzhyl@126.com2教材：2第一章緒論3第一章緒論3數(shù)據(jù)結(jié)構(gòu)的地位數(shù)據(jù)結(jié)構(gòu)在計算機(jī)科學(xué)技術(shù)專業(yè)課程中起作基礎(chǔ)、核心、紐帶、橋梁的作用。是計算機(jī)專業(yè)的核心基礎(chǔ)課。是理論聯(lián)系實(shí)際、數(shù)學(xué)與計算機(jī)科學(xué)、軟件與硬件的紐帶。是通往其它專業(yè)課程的橋梁。學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的要求：課前必須預(yù)習(xí)課后必須復(fù)習(xí)多動手編程，每章至少獨(dú)立完成一個編程。4數(shù)據(jù)結(jié)構(gòu)的地位數(shù)據(jù)結(jié)構(gòu)在計算機(jī)科學(xué)技術(shù)專業(yè)課程中起作基礎(chǔ)、核學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的必要性

計算機(jī)信息表示A信息表示B著名計算機(jī)科學(xué)家N.Wirth提出下面的公式：算法+數(shù)據(jù)結(jié)構(gòu)=程序

5計算機(jī)信息表示A信息表示B著名計算機(jī)科學(xué)家N.Wirth

數(shù)據(jù)結(jié)構(gòu)討論的范疇3。編碼階段2。設(shè)計階段1。分析階段4。測試和維護(hù)（與本課程關(guān)系最密切）為一個實(shí)際問題開發(fā)一個程序，系統(tǒng)通?？梢苑殖梢韵滤膫€階段6數(shù)據(jù)結(jié)構(gòu)討論的范疇3。編碼階段2。設(shè)計階段1。分析階段4。

例如:數(shù)值計算的程序設(shè)計問題：微積分中的計算：求面積，體積，線積分，面積分等；線性代數(shù)中解方程組；近似計算，誤差估計等等。數(shù)值計算與非數(shù)值計算7例如:數(shù)值計算與非數(shù)值計算7非數(shù)值計算的程序設(shè)計問題例1:找一組(n個)整數(shù)中的最大值算法:?模型：？基本操作是“比較兩個數(shù)的大小”取決于整數(shù)值的范圍8非數(shù)值計算的程序設(shè)計問題例1:找一組(n個)整數(shù)中的最大值例2：旅館客房的管理算法：?模型：?先進(jìn)后出隊(duì)列9例2：旅館客房的管理算法：?先進(jìn)后出隊(duì)列9例3：實(shí)際問題中對象之間的關(guān)系——學(xué)生成績管理學(xué)號姓名大學(xué)英語C語言數(shù)據(jù)結(jié)構(gòu)…A07001王萍908595…A07002馬玲808590…A07003張?zhí)m959199…A07004李建708486…A07005黃勇827678…:：：：：：A07001王萍908595學(xué)生成績表A07002馬玲808590A07003張?zhí)m959199A07004李建708486A07005黃勇827678關(guān)系：線性特征：一個直接前趨，一個直接后繼10例3：實(shí)際問題中對象之間的關(guān)系——學(xué)生成績管理學(xué)號姓名大學(xué)英實(shí)際問題中對象之間的關(guān)系例4：“井字棋”的人機(jī)對弈××OO××OOO××OOO××OOO××OOO××OOO××O×OO××OO×O…×××OOO×××OOO關(guān)系：樹型特征：一個直接前趨，多個直接后繼…11實(shí)際問題中對象之間的關(guān)系例4：“井字棋”的人機(jī)對弈××OO對于一個多叉路口，設(shè)計一個交通信號燈的管理系統(tǒng)。首先需要分析一下所有車輛的行駛路線的沖突問題。這個問題可以歸結(jié)為對車輛的可能行駛方向作某種分組，對分組的要求是使任一個組中各個方向行駛的車輛可以同時安全行駛而不發(fā)生碰撞。例5：交通控制問題12對于一個多叉路口，例5：交通控制問題12問題分析

可通行方向ABACADBABCBDDADBDCEAEBECED13問題分析

可通行方向13有些通行方向顯然不能同時進(jìn)行，相應(yīng)的結(jié)點(diǎn)間畫一條連線。ABACADBABCBDDADBDCEAEBECED圖1.2交叉路口的圖示模型14有些通行方向顯然不能同時進(jìn)行，相應(yīng)的結(jié)點(diǎn)間畫一條連線。ABA

把圖1.2中的結(jié)點(diǎn)進(jìn)行分組，使得有結(jié)點(diǎn)相連的結(jié)點(diǎn)不在同一個組里。

地圖著色問題如果把上圖中的一個結(jié)點(diǎn)理解為一個國家，結(jié)點(diǎn)之間的連線看作兩國有共同邊界，上述問題就變成著名的“著色問題”：即求出最少要幾種顏色可將圖中所有國家著色，使得任意兩個相鄰的國家顏色都不相同。通過上面的分析，我們就獲得了該交通管系統(tǒng)的數(shù)學(xué)模型。15把圖1.2中的結(jié)點(diǎn)進(jìn)行分組，使得有結(jié)點(diǎn)相連的結(jié)點(diǎn)不在算法：?模型：?如何用最少的顏色對一個圖著色使得相鄰頂點(diǎn)的顏色都不同？圖交通控制問題可抽象為圖的作色問題：16算法：?如何用最少的顏色對一個圖著色使得相鄰頂點(diǎn)的顏色都不同程序設(shè)計

算法設(shè)計兩種簡單的方法：2.“貪心算法”while有結(jié)點(diǎn)未著色；{選擇一種新顏色；在未著色的結(jié)點(diǎn)中,給盡可能多的彼此結(jié)點(diǎn)之間沒有邊的點(diǎn)著色；}1.對n個結(jié)點(diǎn)，逐個測試其所有組合；17程序設(shè)計2.“貪心算法”1.對n個結(jié)點(diǎn)，逐個測試其所有組著色結(jié)果如下：ABACADBABCBDDADBDCEAEBECED圖1.2交叉路口的圖示模型，每組中沒有邊互連18著色結(jié)果如下：ABACADBABCBDDADBDCEAEB把上面方法應(yīng)用于圖1.2，得到下面的分組：

綠色：AB,AC,AD,BA,DC,ED藍(lán)色：BC,BD,EA紅色：DA,DB白色：EB,EC1919

算法精化：假設(shè)需要著色的圖是G，集合V1包括圖中所有未被著色的結(jié)點(diǎn)，著色開始時V1是G所有結(jié)點(diǎn)集合。NEW表示已確定可以用新顏色著色的結(jié)點(diǎn)集合。從V1中找出可用新顏色著色的結(jié)點(diǎn)集的程序框架描述為：NEW={};for每個vV1doifv與NEW中所有結(jié)點(diǎn)間都沒有邊{從V1中去掉v;NEW=NEW{v};}20算法精化：假設(shè)需要著色的圖是G，集合V1包括圖中所有未算法精化：intcolorUp(GraphG){intcolor=0;V1=G.V;while(!isSetEmpty(V1)){emptySet(NEW);while(vV1&&

notAdjacentWithSet(NEW,v,G)){addToSet(NEW,v);removeFromSet(V1,v);}++color;}return(color);}21算法精化：21由上述實(shí)例，抽象出數(shù)據(jù)結(jié)構(gòu)的概念：概括地說，

數(shù)據(jù)結(jié)構(gòu)是一門討論“描述現(xiàn)實(shí)世界實(shí)體的數(shù)學(xué)模型(非數(shù)值計算)及其上的操作在計算機(jī)中如何表示和實(shí)現(xiàn)”的學(xué)科。課本：數(shù)據(jù)結(jié)構(gòu):是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。22由上述實(shí)例，抽象出數(shù)據(jù)結(jié)構(gòu)的概念：數(shù)據(jù)結(jié)構(gòu)是一門討論“描《數(shù)據(jù)結(jié)構(gòu)課程》所處的地位：23《數(shù)據(jù)結(jié)構(gòu)課程》所處的地位：231.2基本概念一、數(shù)據(jù)與數(shù)據(jù)結(jié)構(gòu)二、數(shù)據(jù)類型三、抽象數(shù)據(jù)類型241.2基本概念一、數(shù)據(jù)與數(shù)據(jù)結(jié)構(gòu)二、數(shù)據(jù)類型三、抽象數(shù)據(jù)一、數(shù)據(jù)與數(shù)據(jù)結(jié)構(gòu)所有能被輸入到計算機(jī)中，且能被計算機(jī)處理的符號(數(shù)值、字符等)的集合。數(shù)據(jù):是計算機(jī)操作的對象的總稱。是計算機(jī)處理的信息的某種特定的符號表示形式。25一、數(shù)據(jù)與數(shù)據(jù)結(jié)構(gòu)所有能被輸入到計算機(jī)中，且能被計算機(jī)處是數(shù)據(jù)（集合）中的一個“個體”,在計算機(jī)中通常作為一個整體進(jìn)行考慮和處理。是數(shù)據(jù)結(jié)構(gòu)中討論的基本單位。數(shù)據(jù)元素:如:整數(shù)“5”,字符“N”等。----是不可分割的“原子”26是數(shù)據(jù)（集合）中的一個“個體”,在計算機(jī)中通常作為一個整

其中每個款項(xiàng)稱為一個“數(shù)據(jù)項(xiàng)”它是數(shù)據(jù)結(jié)構(gòu)中討論的最小單位數(shù)據(jù)元素也可以由若干款項(xiàng)構(gòu)成。例如：描述一個學(xué)生的數(shù)據(jù)元素稱之為組合項(xiàng)年月日姓名學(xué)號班號性別出生日期入學(xué)成績原子項(xiàng)27其中每個款項(xiàng)稱為一個“數(shù)據(jù)項(xiàng)”它是數(shù)據(jù)結(jié)構(gòu)中討論的最小單位數(shù)據(jù)結(jié)構(gòu)：帶結(jié)構(gòu)的數(shù)據(jù)元素的集合數(shù)據(jù)結(jié)構(gòu)是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。指的是數(shù)據(jù)元素之間存在的關(guān)系28數(shù)據(jù)結(jié)構(gòu)：帶結(jié)構(gòu)的數(shù)據(jù)元素的集合數(shù)據(jù)結(jié)構(gòu)是相互之間存在一種或例如，在2行3列的二維數(shù)組中六個元素{a1,a2,a3,a4,a5,a6}之間存在兩個關(guān)系:行的次序關(guān)系:row={<a1,a2>,<a2,a3>,<a4,a5>,<a5,a6>}col={<a1,a4>,<a2,a5>,<a3,a6>}

a1a2a3a4a5a6列的次序關(guān)系:29例如，在2行3列的二維數(shù)組中六個元素行的次序關(guān)系:r若在6個數(shù)據(jù)元素{a1,a2,a3,a4,a5,a6}之間存在如下的次序關(guān)系:{<ai,ai+1>|i=1,2,3,4,5}

數(shù)據(jù)結(jié)構(gòu)是相互之間存在著某種邏輯關(guān)系的數(shù)據(jù)元素的集合。可見，不同的“關(guān)系”構(gòu)成不同的“結(jié)構(gòu)”則構(gòu)成一維數(shù)組的定義。30若在6個數(shù)據(jù)元素{a1,a2,a3,a4,從關(guān)系或結(jié)構(gòu)分，數(shù)據(jù)結(jié)構(gòu)可歸結(jié)為以下四類:線性結(jié)構(gòu)樹形結(jié)構(gòu)圖狀結(jié)構(gòu)集合結(jié)構(gòu)31從關(guān)系或結(jié)構(gòu)分，數(shù)據(jù)結(jié)構(gòu)可歸結(jié)為以下四類:線性結(jié)構(gòu)樹形結(jié)構(gòu)圖數(shù)據(jù)結(jié)構(gòu)包括“邏輯結(jié)構(gòu)”和“物理結(jié)構(gòu)”兩個方面(層次):邏輯結(jié)構(gòu)是對數(shù)據(jù)元素之間的邏輯關(guān)系的描述，它可以應(yīng)一個數(shù)據(jù)元素的集合和定義在此集合上的若干關(guān)系來表示;物理結(jié)構(gòu)是邏輯結(jié)構(gòu)在計算機(jī)中的表示和實(shí)現(xiàn)，故又稱“存儲結(jié)構(gòu)”。32數(shù)據(jù)結(jié)構(gòu)包括“邏輯結(jié)構(gòu)”和“物理結(jié)構(gòu)”兩個方面(層次):邏數(shù)據(jù)邏輯結(jié)構(gòu)的形式定義描述為:數(shù)據(jù)結(jié)構(gòu)是一個二元組Data_Structures=(D,S)其中:D是數(shù)據(jù)元素的有限集，

S是D上關(guān)系的有限集。33數(shù)據(jù)邏輯結(jié)構(gòu)的形式定義描述為:數(shù)據(jù)結(jié)構(gòu)是一個二元組Data數(shù)據(jù)的存儲結(jié)構(gòu)

——邏輯結(jié)構(gòu)在存儲器中的映象“數(shù)據(jù)元素”的映象？“關(guān)系”的映象？34數(shù)據(jù)的存儲結(jié)構(gòu)——邏輯結(jié)構(gòu)在存儲器中的映象“數(shù)據(jù)元素”的數(shù)據(jù)的存儲結(jié)構(gòu)：順序存儲結(jié)構(gòu)鏈?zhǔn)酱鎯Y(jié)構(gòu)索引存儲結(jié)構(gòu)散列存儲結(jié)構(gòu)35數(shù)據(jù)的存儲結(jié)構(gòu)：35數(shù)據(jù)元素的映象方法：用二進(jìn)制位(bit)的位串表示數(shù)據(jù)元素(321)10=(501)8=(101000001)2A=(101)8=(001000001)236數(shù)據(jù)元素的映象方法：用二進(jìn)制位(bit)的位串表示數(shù)據(jù)元素(關(guān)系的映象方法：（表示x,y的方法）順序映象以相對的存儲位置表示后繼關(guān)系例如:令y的存儲位置和x的存儲位置之間差一個常量C而C是一個隱含值，整個存儲結(jié)構(gòu)中只含數(shù)據(jù)元素本身的信息xy37關(guān)系的映象方法：（表示x,y的方法）順序映象以相對的存鏈?zhǔn)接诚笠愿郊有畔?指針)表示后繼關(guān)系需要用一個和x在一起的附加信息指示y的存儲位置yx38鏈?zhǔn)接诚笠愿郊有畔?指針)表示后繼關(guān)系需要用一個和x在一在不同的編程環(huán)境中，存儲結(jié)構(gòu)可有不同的描述方法，當(dāng)用高級程序設(shè)計語言進(jìn)行編程時，通?？捎酶呒壘幊陶Z言中提供的數(shù)據(jù)類型描述之。39在不同的編程環(huán)境中，存儲結(jié)構(gòu)可有不同的描述方法，當(dāng)用高級程序例如:以三個帶有次序關(guān)系的整數(shù)表示一個長整數(shù)時，可利用C語言中提供的整數(shù)數(shù)組類型，typedefintLong_int[3]定義長整數(shù)為:40例如:以三個帶有次序關(guān)系的整數(shù)表示一個長整數(shù)時，可利用typedefstruct{

inty;//年號Year

intm;//月號Month

intd;//日號Day}DateType;//日期類型定義“日期”為:定義“學(xué)生”為:typedefstruct{

charid[8];//學(xué)號

charname[16];//姓名

charsex;//性別‘M/F’:男/女DateTypebdate;//出生日期}Student;//學(xué)生類型41typedefstruct{定義“日期”為:定義“學(xué)生”二、數(shù)據(jù)類型

在用高級程序語言編寫的程序中，必須對程序中出現(xiàn)的每個變量、常量或表達(dá)式，明確說明它們所

屬的數(shù)據(jù)類型。42二、數(shù)據(jù)類型在用高級程序語言編寫的程序中，必須對程序中出現(xiàn)例如，C語言中提供的基本數(shù)據(jù)類型有:整型int浮點(diǎn)型float字符型char邏輯型bool（C++語言）雙精度型double實(shí)型（C++語言）43例如，C語言中提供的基本數(shù)據(jù)類型有:整型int浮點(diǎn)型數(shù)據(jù)結(jié)構(gòu)：一組具有相同結(jié)構(gòu)的值。數(shù)據(jù)類型是一個值的集合和定義在此集合上的一組操作的總稱。

不同類型的變量，其所能取的值的范圍不同，所能進(jìn)行的操作不同。例如：整型值的范圍是：-32768-32767操作是：+，-，*，/，%44數(shù)據(jù)結(jié)構(gòu)：一組具有相同結(jié)構(gòu)的值。不同類型的變量，其所能各種高級程序設(shè)計語言中都擁有“整數(shù)”類型，盡管它們在不同處理器上實(shí)現(xiàn)的方法不同，但對程序員而言是“相同的”，因?yàn)樗鼈兊臄?shù)學(xué)特性相同。從“數(shù)學(xué)抽象”的角度看，可稱它為一個“抽象數(shù)據(jù)類型”。45各種高級程序設(shè)計語言中都擁有“整數(shù)”類型，盡管它們在不同處理三、抽象數(shù)據(jù)類型

(AbstractDataType簡稱ADT)是指一個數(shù)學(xué)模型以及定義在此數(shù)學(xué)模型上的一組操作46三、抽象數(shù)據(jù)類型是指一個數(shù)學(xué)模型以及定義在此數(shù)學(xué)模型上的例如:“整數(shù)”是一個抽象數(shù)據(jù)類型。其數(shù)學(xué)特性和具體的計算機(jī)或語言無關(guān)?！俺橄蟆钡囊饬x在于強(qiáng)調(diào)數(shù)據(jù)類型的數(shù)學(xué)特性。47例如:其數(shù)學(xué)特性和具體的計算機(jī)或語言無關(guān)。47抽象數(shù)據(jù)類型還包括用戶在設(shè)計軟件系統(tǒng)時自己定義的數(shù)據(jù)類型。在構(gòu)造軟件系統(tǒng)的各個相對獨(dú)立的模塊時，定義一組數(shù)據(jù)和施與這些數(shù)據(jù)之上的一組操作，并在模塊內(nèi)部給出它們的表示和實(shí)現(xiàn)細(xì)節(jié)，在模塊外部使用的只是抽象的數(shù)據(jù)和抽象的操作。48抽象數(shù)據(jù)類型還包括用戶在設(shè)計軟件系統(tǒng)時自己定義的數(shù)據(jù)類型。在例如，定義抽象數(shù)據(jù)類型“復(fù)數(shù)”

數(shù)據(jù)對象：

D＝{〈e1,e2〉｜e1,e2∈RealSet}

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

R1＝{P}P是很復(fù)雜的關(guān)系，如兩向量平行、垂直、相等、夾角，可比較大小，不可比較大小等。ADTComplex{49例如，定義抽象數(shù)據(jù)類型“復(fù)數(shù)”數(shù)據(jù)對象：ADT基本操作：AssignComplex(&Z,v1,v2)操作結(jié)果：構(gòu)造復(fù)數(shù)Z,其實(shí)部和虛部分別被賦以參數(shù)v1和v2的值。DestroyComplex(&Z)操作結(jié)果：復(fù)數(shù)Z被銷毀。GetReal(Z,&realPart)初始條件：復(fù)數(shù)已存在。操作結(jié)果：用realPart返回復(fù)數(shù)Z的實(shí)部值。50基本操作：AssignComplex(&Z,v1,v2GetImag(Z,&ImagPart)初始條件：復(fù)數(shù)已存在。操作結(jié)果：用ImagPart返回復(fù)數(shù)Z的虛部值。Add(z1,z2,&sum)初始條件：z1,z2是復(fù)數(shù)。操作結(jié)果：用sum返回兩個復(fù)數(shù)z1,z2的和值。Multiply(z1,z2,&z)division(z1,z2,&z)

}ADTComplex51GetImag(Z,&ImagPart)Add(z1

#include<iostream.h>#include"complex.h"

voidmain()

{

}……52#include<iostream.h>……52

complexz1,z2,z3,z4,z; floatRealPart,ImagPart;

InitComplex(z1,8.0,6.0);

InitComplex(z2,4.0,3.0);

Add(z1,z2,z3);

Multiply(z1,z2,z4); if(Division(z4,z3,z)){

GetReal(z,RealPart);

GetImag(z,ImagPart);}//if53 complexz1,z2,z3,z4,z;53ADT有兩個重要特征:數(shù)據(jù)抽象

用ADT描述程序處理的實(shí)體時，強(qiáng)調(diào)的是其本質(zhì)的特征、其所能完成的功能以及它和外部用戶的接口（即外界使用它的方法）數(shù)據(jù)封裝

將實(shí)體的外部特性和其內(nèi)部實(shí)現(xiàn)細(xì)節(jié)分離，并且對外部用戶隱藏其內(nèi)部實(shí)現(xiàn)細(xì)節(jié)54ADT有兩個重要特征:數(shù)據(jù)抽象用ADT描述抽象數(shù)據(jù)類型的描述方法抽象數(shù)據(jù)類型可用（D，S，P）三元組表示其中，D是數(shù)據(jù)對象，

S是D上的關(guān)系集，P是對D的基本操作集。55抽象數(shù)據(jù)類型的描述方法抽象數(shù)據(jù)類型可用（D，S，P）三元組表ADT

抽象數(shù)據(jù)類型名{數(shù)據(jù)對象：〈數(shù)據(jù)對象的定義〉

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

基本操作：〈基本操作的定義〉}ADT抽象數(shù)據(jù)類型名其中基本操作的定義格式為:基本操作名（參數(shù)表）

初始條件：〈初始條件描述〉

操作結(jié)果：〈操作結(jié)果描述〉

56ADT抽象數(shù)據(jù)類型名{其中基本操作的定義格式為:基本操作賦值參數(shù)只為操作提供輸入值；引用參數(shù)以&打頭，除可提供輸入值外，還將返回操作結(jié)果。初始條件描述了操作執(zhí)行之前數(shù)據(jù)結(jié)構(gòu)和參數(shù)應(yīng)滿足的條件，若不滿足，則操作失敗，并返回相應(yīng)出錯信息。操作結(jié)果說明了操作正常完成之后，數(shù)據(jù)結(jié)構(gòu)的變化狀況和應(yīng)返回的結(jié)果。若初始條件為空，則省略之。57賦值參數(shù)只為操作提供輸入值；初始條件描述了操作執(zhí)行之前數(shù)抽象數(shù)據(jù)類型的表示和實(shí)現(xiàn)抽象數(shù)據(jù)類型需要通過固有數(shù)據(jù)類型(高級編程語言中已實(shí)現(xiàn)的數(shù)據(jù)類型)來實(shí)現(xiàn)。例如，對以上定義的復(fù)數(shù)//-----存儲結(jié)構(gòu)的定義58抽象數(shù)據(jù)類型的表示和實(shí)現(xiàn)抽象數(shù)據(jù)類型需要通過固有數(shù)據(jù)typedefstruct{

floatrealpart；

floatimagpart；}complex；//-----存儲結(jié)構(gòu)的定義//-----基本操作的函數(shù)原型說明void

Assign(complex&Z,

floatrealval,floatimagval)；//構(gòu)造復(fù)數(shù)Z,其實(shí)部和虛部分別被賦以參數(shù)//realval和imagval的值59typedefstruct{//-----存儲結(jié)構(gòu)的float

GetReal(cpmplexZ)；//返回復(fù)數(shù)Z的實(shí)部值float

Getimag(cpmplexZ)；//返回復(fù)數(shù)Z的虛部值voidadd(complexz1,complexz2,complex&sum)；

//以sum返回兩個復(fù)數(shù)z1,z2的和60floatGetReal(cpmplexZ)；flo//-----基本操作的實(shí)現(xiàn)voidadd(complexz1,complexz2,complex&sum)

{//以sum返回兩個復(fù)數(shù)z1,z2的和sum.realpart=z1.realpart+z2.realpart;sum.imagpart=z1.imagpart+z2.imagpart;}{其它省略}61//-----基本操作的實(shí)現(xiàn)voidadd(compl1.3算法和算法的衡量一、算法二、算法設(shè)計的原則三、算法效率的衡量方法和準(zhǔn)則四、算法的存儲空間需求621.3算法和算法的衡量一、算法二、算法設(shè)計的原則三、算法效算法是為了解決某類問題而規(guī)定的一個有限長的操作序列。一個算法必須滿足以下五個重要特性：1．有窮性

2．確定性3．可行性4．有輸入5．有輸出一、算法63算法是為了解決某類問題而規(guī)定的一個有限長的操作序列。1．有窮性對于任意一組合法輸入值，在執(zhí)行有窮步驟之后一定能結(jié)束，即：算法中的每個步驟都能在有限時間內(nèi)完成；2．確定性

對于每種情況下所應(yīng)執(zhí)行的操作，在算法中都有確切的規(guī)定，使算法的執(zhí)行者或閱讀者都能明確其含義及如何執(zhí)行。并且在任何條件下，算法都只有一條執(zhí)行路徑；641．有窮性對于任意一組合法輸入值，在執(zhí)行有窮步驟之后一定3．可行性算法中的所有操作都必須足夠基本，都可以通過已經(jīng)實(shí)現(xiàn)的基本操作運(yùn)算有限次實(shí)現(xiàn)之；4．有輸入作為算法加工對象的量值，通常體現(xiàn)為算法中的一組變量。有些輸入量需要在算法執(zhí)行過程中輸入，而有的算法表面上可以沒有輸入，實(shí)際上已被嵌入算法之中；

5．有輸出它是一組與“輸入”與確定關(guān)系的量值，是算法進(jìn)行信息加工后得到的結(jié)果，這種確定關(guān)系即為算法的功能。653．可行性算法中的所有操作都必須足夠基本，都可以通過已經(jīng)本書算法的描述選擇算法描述語言的準(zhǔn)則（1）該語言應(yīng)該具有描述數(shù)據(jù)結(jié)構(gòu)和算法的基本功能；（2）該語言應(yīng)該盡可能地簡捷，以便于掌握、理解；（3）使用該語言描述的算法應(yīng)該能夠比較容易地轉(zhuǎn)換成任何一種程序設(shè)計語言?！邦怌”描述語言是通過對C語言進(jìn)行精心篩選保留的一個核心子集，并為了便于描述，又做了若干擴(kuò)展修改，從而，增強(qiáng)了語言的描述功能。66本書算法的描述661.預(yù)定義常量及類型

#defineTRUE1#defineFALSE0#defineOK1#defineERROR0 #defineINFEASIBLE-1#defineOVERFLOW-2typedefintstatus;數(shù)據(jù)元素被約定為ELEMENTType類型，用戶需要根據(jù)具體情況，自行定義該數(shù)據(jù)類型。671.預(yù)定義常量及類型672.算法描述為以下的函數(shù)形式：

函數(shù)類型函數(shù)名（函數(shù)參數(shù)表）{語句序列；}為了簡化函數(shù)的書寫，提高算法描述的清晰度，我們規(guī)定除函數(shù)參數(shù)表中的參數(shù)需要說明數(shù)據(jù)類型外，函數(shù)中使用的局部變量可以不做變量說明，必要時給出相應(yīng)的注釋即可。另外，在書寫算法時，應(yīng)該養(yǎng)成對重點(diǎn)語句段落添加注解的良好習(xí)慣。682.算法描述為以下的函數(shù)形式：683.在算法描述中可以使用的賦值語句形式有：

簡單賦值變量名=表達(dá)式；

串聯(lián)賦值變量名1=變量名2=...=變量名n=表達(dá)式；

成組賦值（變量名1，...，變量名n）=（表達(dá)式1，...，表達(dá)式n）；

結(jié)構(gòu)賦值結(jié)構(gòu)名1=結(jié)構(gòu)名2；

結(jié)構(gòu)名=（值1，值2，...，值n）；

條件賦值變量名=條件表達(dá)式?表達(dá)式1：表達(dá)式2；交換賦值變量名1變量名2；693.在算法描述中可以使用的賦值語句形式有：694.在算法描述中可以使用的選擇結(jié)構(gòu)語句形式有：條件語句1if（表達(dá)式）語句；條件語句2if（表達(dá)式）語句；else語句；開關(guān)語句1

switch（表達(dá)式）{

case值1：語句序列1；break；

case值2：語句序列2；break；...

case值n：語句序列n；break；

default：語句序列n+1；}704.在算法描述中可以使用的選擇結(jié)構(gòu)語句形式有：70開關(guān)語句2

switch{

case條件1：語句序列1；break；

case條件2：語句序列2；break；...

case條件n：語句序列n；break；default：語句序列n+1；}71開關(guān)語句2switch{71

5.在算法描述中可以使用的循環(huán)結(jié)構(gòu)語句形式有：for循環(huán)語句

for（表達(dá)式1；循環(huán)條件表達(dá)式；表達(dá)式2）語句；while循環(huán)語句

while（循環(huán)條件表達(dá)式）語句；do-while循環(huán)語句

do{語句序列；}while（循環(huán)條件表達(dá)式）；6.在描述算法中可以使用的結(jié)束語句形式有：函數(shù)結(jié)束語句return表達(dá)式；return;case或循環(huán)結(jié)束語句break;異常結(jié)束語句exit（異常代碼）；

725.在算法描述中可以使用的循環(huán)結(jié)構(gòu)語句形式有：727.在算法描述中可以使用的輸入輸出語句形式有：輸入語句scanf([格式串]，變量名1，...,變量名n)；輸出語句printf([格式串]，表達(dá)式1，...，表達(dá)式n);方括號（[]）中的內(nèi)容是可以省略的部分。8.在算法描述中使用的注釋格式為：單行注釋//文字序列

9.在算法描述中可以使用的擴(kuò)展函數(shù)有：求最大值max（表達(dá)式1，...，表達(dá)式n）；這個函數(shù)返回參數(shù)表中n個表達(dá)式計算結(jié)果中的最大值。

求最小值min（表達(dá)式1，...，表達(dá)式n）；這個函數(shù)返回參數(shù)表中n個表達(dá)式計算結(jié)果中的最小值。737.在算法描述中可以使用的輸入輸出語句形式有：73二、算法設(shè)計的原則設(shè)計算法時，通常應(yīng)考慮達(dá)到以下目標(biāo)：1．正確性2.可讀性3．健壯性4．高效率與低存儲量需求74二、算法設(shè)計的原則設(shè)計算法時，通常應(yīng)考慮達(dá)到以下目標(biāo)：1．正1．正確性

首先，算法應(yīng)當(dāng)滿足以特定的“規(guī)格說明”方式給出的需求。

其次，對算法是否“正確”的理解可以有以下四個層次：a．程序中不含語法錯誤；b．程序?qū)τ趲捉M輸入數(shù)據(jù)能夠得出滿足要求的結(jié)果；751．正確性首先，算法應(yīng)當(dāng)滿足以特定的“規(guī)格說明”方式c．程序?qū)τ诰倪x擇的、典型、苛刻且?guī)в械箅y性的幾組輸入數(shù)據(jù)能夠得出滿足要求的結(jié)果；通常以第c層意義的正確性作為衡量一個算法是否合格的標(biāo)準(zhǔn)。

d．程序?qū)τ谝磺泻戏ǖ妮斎霐?shù)據(jù)都能得出滿足要求的結(jié)果；76c．程序?qū)τ诰倪x擇的、典型、苛刻且?guī)в械箅y性的幾組輸入數(shù)2.可讀性算法主要是為了人的閱讀與交流，其次才是為計算機(jī)執(zhí)行。因此算法應(yīng)該易于人的理解；另一方面，晦澀難讀的程序易于隱藏較多錯誤而難以調(diào)試；772.可讀性算法主要是為了人的閱讀與交流，其次才是為3．健壯性當(dāng)輸入的數(shù)據(jù)非法時，算法應(yīng)當(dāng)恰當(dāng)?shù)刈鞒龇从郴蜻M(jìn)行相應(yīng)處理，而不是產(chǎn)生莫名奇妙的輸出結(jié)果。并且，處理出錯的方法不應(yīng)是中斷程序的執(zhí)行，而應(yīng)是返回一個表示錯誤或錯誤性質(zhì)的值，以便在更高的抽象層次上進(jìn)行處理。783．健壯性當(dāng)輸入的數(shù)據(jù)非法時，算法應(yīng)當(dāng)恰當(dāng)?shù)刈鞒龇从郴?．高效率與低存儲量需求通常，效率指的是算法執(zhí)行時間；存儲量指的是算法執(zhí)行過程中所需的最大存儲空間。兩者都與問題的規(guī)模有關(guān)。794．高效率與低存儲量需求通常，效率指的是算法執(zhí)行時間；三、算法效率的衡量方法和準(zhǔn)則通常有兩種衡量算法效率的方法:

事后統(tǒng)計法事前分析估算法缺點(diǎn)：1。必須執(zhí)行程序2。其它因素掩蓋算法本質(zhì)80三、算法效率的衡量方法和準(zhǔn)則通常有兩種衡量算法效率的方法:和算法執(zhí)行時間相關(guān)的因素：1．算法選用的策略2．問題的規(guī)模3．編寫程序的語言4．編譯程序產(chǎn)生的機(jī)器代碼的質(zhì)量5．計算機(jī)執(zhí)行指令的速度81和算法執(zhí)行時間相關(guān)的因素：1．算法選用的策略2．問題的規(guī)模3一個特定算法的“運(yùn)行工作量”的大小，只依賴于問題的規(guī)模（通常用整數(shù)量n表示），或者說，它是問題規(guī)模的函數(shù)。82一個特定算法的“運(yùn)行工作量”82假如，隨著問題規(guī)模n的增長，算法執(zhí)行時間的增長率和f(n)的增長率相同，則可記作：T(n)=O(f(n))稱T(n)為算法的(漸近)時間復(fù)雜度83假如，隨著問題規(guī)模n的增長，算法執(zhí)行時間的算法=控制結(jié)構(gòu)+原操作（固有數(shù)據(jù)類型的操作）算法的執(zhí)行時間=原操作(i)的執(zhí)行次數(shù)×原操作(i)的執(zhí)行時間

算法的執(zhí)行時間

與

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

成正比

如何估算算法的時間復(fù)雜度？84算法=控制結(jié)構(gòu)+原操作（固有數(shù)據(jù)類型的操作）算法的執(zhí)從算法中選取一種對于所研究的問題來說是基本操作

的原操作，以該基本操作在算法中重復(fù)執(zhí)行的次數(shù)作為算法運(yùn)行時間的衡量準(zhǔn)則。85從算法中選取一種對于所研究的問題來說是基本操作的原算法執(zhí)行的效率：實(shí)例：排序問題對個元素進(jìn)行從小到大排序如果用插入排序，其時間復(fù)雜度為O(2n2),在109/秒的高檔機(jī)下執(zhí)行，其所需的時間約為：如果動用歸并排序，其時間復(fù)雜度為O(50nlogn),在107/秒的低檔機(jī)下執(zhí)行，其所需的時間約為：此實(shí)例說明算法是決定效率的本質(zhì)因素。86算法執(zhí)行的效率：此實(shí)例說明算法是決定效率的本質(zhì)因素。86例一兩個矩陣相乘voidmult(inta[],intb[],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基本操作:

乘法操作時間復(fù)雜度:

O(n3)87例voidmult(inta[],intb[],i例二選擇排序voidselect_sort(int&a[],intn){

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

}//select_sort基本操作:

比較(數(shù)據(jù)元素)操作時間復(fù)雜度:

O(n2)j=i;//

選擇第i個最小元素for(k=i+1;k<n;++k)

if(a[k]<a[j])j=k;for(i=0;i<n-1;++i){if(j!=i)a[j]←→a[i]}88例voidselect_sort(int&a[],i例三起泡排序voidbubble_sort(int&a[],intn){//將a中整數(shù)序列重新排列成自小至大有序的整數(shù)序列。for

(i=n-1,change=TRUE;i>1&&change;--i)}//bubble_sort基本操作:

賦值操作時間復(fù)雜度:

O(n2){

change=FALSE;

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

for(j=0;j<i;++j)

if(a[j]>a[j+1])

{

a[j]←→a[j+1];

change=TRUE;}}//一趟起泡89例voidbubble_sort(int&a[],in算法時間效率的度量分析圖1-7常見函數(shù)的增長率算法時間效率的度量分析圖1-7常見函數(shù)的增長率90四、算法的存儲空間需求算法的空間復(fù)雜度定義為:

表示隨著問題規(guī)模n的增大，算法運(yùn)行所需存儲量的增長率與g(n)的增長率相同。S(n)=O(g(n))91四、算法的存儲空間需求算法的空間復(fù)雜度定義為:表示隨算法的存儲量包括:1．輸入數(shù)據(jù)所占空間2．程序本身所占空間；3．輔助變量所占空間。92算法的存儲量包括:1．輸入數(shù)據(jù)所占空間2．程序本身所占空間；若輸入數(shù)據(jù)所占空間只取決與問題本身，和算法無關(guān)，則只需要分析除輸入和程序之外的輔助變量所占額外空間。若所需額外空間相對于輸入數(shù)據(jù)量來說是常數(shù)，則稱此算法為原地工作。若所需存儲量依賴于特定的輸入，則通常按最壞情況考慮。93若輸入數(shù)據(jù)所占空間只取決與問題本身，和算法無關(guān)本章主要講解了兩個大的問題，一是數(shù)據(jù)結(jié)構(gòu)的定義和相關(guān)概念，二是算法的定義和算法分析。需要掌握的重點(diǎn)內(nèi)容包括：1、數(shù)據(jù)結(jié)構(gòu)的定義：數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值應(yīng)用問題中數(shù)據(jù)的物理結(jié)構(gòu)、邏輯結(jié)構(gòu)和對數(shù)據(jù)的操作即計算機(jī)算法的學(xué)科。2、數(shù)據(jù)的邏輯結(jié)構(gòu)包括兩大類：線性結(jié)構(gòu)和非線性結(jié)構(gòu)，并且非線性結(jié)構(gòu)又分為樹形結(jié)構(gòu)和圖形結(jié)構(gòu)。通常我們還將集合這種結(jié)構(gòu)增加進(jìn)來，因此也可以說數(shù)據(jù)的邏輯結(jié)構(gòu)包括：集合結(jié)構(gòu)、線性結(jié)構(gòu)、樹形結(jié)構(gòu)、圖形結(jié)構(gòu)四種類型。3、數(shù)據(jù)的物理結(jié)構(gòu)主要包括：順序結(jié)構(gòu)、鏈?zhǔn)浇Y(jié)構(gòu)、索引結(jié)構(gòu)和散列結(jié)構(gòu)四種。本章學(xué)習(xí)要點(diǎn)94本章主要講解了兩個大的問題，一是數(shù)據(jù)結(jié)構(gòu)的定義和相關(guān)概念，本章學(xué)習(xí)要點(diǎn)4、算法是解決某一類問題的特定方法，一個算法我們可以用計算機(jī)語言、自然語言、框圖、類語言等多種形式來描述。一段計算機(jī)程序可以用來表示一個算法，但是算法并不一定是用計算機(jī)程序描述的。5、任何一個算法都必須滿足五個特性，即正確性、確定性、有限性、輸入和輸出，其中正確性是進(jìn)行算法分析的前提。一個算法可以在程序中初始化一些變量，所以可以沒有輸入，但是一定要有輸出。6、當(dāng)解決一個問題都多種算法時，我們可以通過算法分析進(jìn)行優(yōu)化選擇。通常算法分析要包括時間復(fù)雜度分析和空間復(fù)雜度分析兩種。時間復(fù)雜度并不是具體的算法運(yùn)行時間，而是算法的運(yùn)行時間的數(shù)量級度量，通常有O(1)、O(n)、O(nlog2n)、O(n2)、O(n3)幾種。空間復(fù)雜度是算法運(yùn)行時需要的附加空間的數(shù)量級度量，常見的有O(1)、O(log2n)、O(n)幾種。95本章學(xué)習(xí)要點(diǎn)4、算法是解決某一類問題的特定方法，一個算法我們1.1簡述下列術(shù)語：數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)對象、存儲結(jié)構(gòu)、數(shù)據(jù)類型和抽象數(shù)據(jù)類型。1.2設(shè)有數(shù)據(jù)結(jié)構(gòu)（D,R）,其中D={d1,d2,d3,d4},R={r}r={(d1,d2),(d2,d3),(d3,d4)}。試按圖論中圖的畫法慣例畫出其邏輯結(jié)構(gòu)圖。1.3設(shè)n為正整數(shù)。試確定下列各程序段中前置以記號＠的語句的頻度；（1）i=1;k=0;while(i<=n-1){＠k+=10*i;i++;}（2）i=1;k=0;do{＠k+=10*i;i++;}while(i<=n-1);課后作業(yè)及習(xí)題(每周一交)961.1簡述下列術(shù)語：數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)對象、存儲結(jié)構(gòu)、數(shù)（3）i=1;k=0;while(i<=n-1){i++;＠k+=10*i;}（4）k=0;for(i=1;i<=n;i++){for(j=i;j<=n;j++)＠k++;}（6）x=n;y=0;//n是不小于1的常數(shù)While(x>=(y+1)*(y+1)){＠y++;}（5）for(i=1;i<=n;i++){for(j=1;j<=i;j++)for(k=1;k<=j;k++)＠x+=delta;}（7）x=91;y=100;While(y>0){＠if(x>100){x-=10;y--;}elsex++;}97（3）i=1;k=0;while(i<=n-1){i++;1.4按增長率由小至大的順序排列下列各函數(shù)

1.5試寫一算法，自大至小依次輸出順序讀入的三個整數(shù)X,Y和Z的值。981.4按增長率由小至大的順序排列下列各函數(shù)98演講完畢，謝謝觀看！演講完畢，謝謝觀看！99數(shù)據(jù)結(jié)構(gòu)100數(shù)據(jù)結(jié)構(gòu)1教材：《數(shù)據(jù)結(jié)構(gòu)》浙江大學(xué)出版社《數(shù)據(jù)結(jié)構(gòu)（C語言版）》嚴(yán)蔚敏、吳偉民編著,清華大學(xué)出版社主要參考教材：《數(shù)據(jù)結(jié)構(gòu)》張乃孝編著，高等教育出版社《DATASTRUCTURES&PROGRAMDESIGNINC》RobertL.KrusePrentice-HallInternational,Inc.主講：周玉林電話QQ：279635371Email：srzhyl@126.com101教材：2第一章緒論102第一章緒論3數(shù)據(jù)結(jié)構(gòu)的地位數(shù)據(jù)結(jié)構(gòu)在計算機(jī)科學(xué)技術(shù)專業(yè)課程中起作基礎(chǔ)、核心、紐帶、橋梁的作用。是計算機(jī)專業(yè)的核心基礎(chǔ)課。是理論聯(lián)系實(shí)際、數(shù)學(xué)與計算機(jī)科學(xué)、軟件與硬件的紐帶。是通往其它專業(yè)課程的橋梁。學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的要求：課前必須預(yù)習(xí)課后必須復(fù)習(xí)多動手編程，每章至少獨(dú)立完成一個編程。103數(shù)據(jù)結(jié)構(gòu)的地位數(shù)據(jù)結(jié)構(gòu)在計算機(jī)科學(xué)技術(shù)專業(yè)課程中起作基礎(chǔ)、核學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的必要性

計算機(jī)信息表示A信息表示B著名計算機(jī)科學(xué)家N.Wirth提出下面的公式：算法+數(shù)據(jù)結(jié)構(gòu)=程序

104計算機(jī)信息表示A信息表示B著名計算機(jī)科學(xué)家N.Wirth

數(shù)據(jù)結(jié)構(gòu)討論的范疇3。編碼階段2。設(shè)計階段1。分析階段4。測試和維護(hù)（與本課程關(guān)系最密切）為一個實(shí)際問題開發(fā)一個程序，系統(tǒng)通?？梢苑殖梢韵滤膫€階段105數(shù)據(jù)結(jié)構(gòu)討論的范疇3。編碼階段2。設(shè)計階段1。分析階段4。

例如:數(shù)值計算的程序設(shè)計問題：微積分中的計算：求面積，體積，線積分，面積分等；線性代數(shù)中解方程組；近似計算，誤差估計等等。數(shù)值計算與非數(shù)值計算106例如:數(shù)值計算與非數(shù)值計算7非數(shù)值計算的程序設(shè)計問題例1:找一組(n個)整數(shù)中的最大值算法:?模型：？基本操作是“比較兩個數(shù)的大小”取決于整數(shù)值的范圍107非數(shù)值計算的程序設(shè)計問題例1:找一組(n個)整數(shù)中的最大值例2：旅館客房的管理算法：?模型：?先進(jìn)后出隊(duì)列108例2：旅館客房的管理算法：?先進(jìn)后出隊(duì)列9例3：實(shí)際問題中對象之間的關(guān)系——學(xué)生成績管理學(xué)號姓名大學(xué)英語C語言數(shù)據(jù)結(jié)構(gòu)…A07001王萍908595…A07002馬玲808590…A07003張?zhí)m959199…A07004李建708486…A07005黃勇827678…:：：：：：A07001王萍908595學(xué)生成績表A07002馬玲808590A07003張?zhí)m959199A07004李建708486A07005黃勇827678關(guān)系：線性特征：一個直接前趨，一個直接后繼109例3：實(shí)際問題中對象之間的關(guān)系——學(xué)生成績管理學(xué)號姓名大學(xué)英實(shí)際問題中對象之間的關(guān)系例4：“井字棋”的人機(jī)對弈××OO××OOO××OOO××OOO××OOO××OOO××O×OO××OO×O…×××OOO×××OOO關(guān)系：樹型特征：一個直接前趨，多個直接后繼…110實(shí)際問題中對象之間的關(guān)系例4：“井字棋”的人機(jī)對弈××OO對于一個多叉路口，設(shè)計一個交通信號燈的管理系統(tǒng)。首先需要分析一下所有車輛的行駛路線的沖突問題。這個問題可以歸結(jié)為對車輛的可能行駛方向作某種分組，對分組的要求是使任一個組中各個方向行駛的車輛可以同時安全行駛而不發(fā)生碰撞。例5：交通控制問題111對于一個多叉路口，例5：交通控制問題12問題分析

可通行方向ABACADBABCBDDADBDCEAEBECED112問題分析

可通行方向13有些通行方向顯然不能同時進(jìn)行，相應(yīng)的結(jié)點(diǎn)間畫一條連線。ABACADBABCBDDADBDCEAEBECED圖1.2交叉路口的圖示模型113有些通行方向顯然不能同時進(jìn)行，相應(yīng)的結(jié)點(diǎn)間畫一條連線。ABA

把圖1.2中的結(jié)點(diǎn)進(jìn)行分組，使得有結(jié)點(diǎn)相連的結(jié)點(diǎn)不在同一個組里。

地圖著色問題如果把上圖中的一個結(jié)點(diǎn)理解為一個國家，結(jié)點(diǎn)之間的連線看作兩國有共同邊界，上述問題就變成著名的“著色問題”：即求出最少要幾種顏色可將圖中所有國家著色，使得任意兩個相鄰的國家顏色都不相同。通過上面的分析，我們就獲得了該交通管系統(tǒng)的數(shù)學(xué)模型。114把圖1.2中的結(jié)點(diǎn)進(jìn)行分組，使得有結(jié)點(diǎn)相連的結(jié)點(diǎn)不在算法：?模型：?如何用最少的顏色對一個圖著色使得相鄰頂點(diǎn)的顏色都不同？圖交通控制問題可抽象為圖的作色問題：115算法：?如何用最少的顏色對一個圖著色使得相鄰頂點(diǎn)的顏色都不同程序設(shè)計

算法設(shè)計兩種簡單的方法：2.“貪心算法”while有結(jié)點(diǎn)未著色；{選擇一種新顏色；在未著色的結(jié)點(diǎn)中,給盡可能多的彼此結(jié)點(diǎn)之間沒有邊的點(diǎn)著色；}1.對n個結(jié)點(diǎn)，逐個測試其所有組合；116程序設(shè)計2.“貪心算法”1.對n個結(jié)點(diǎn)，逐個測試其所有組著色結(jié)果如下：ABACADBABCBDDADBDCEAEBECED圖1.2交叉路口的圖示模型，每組中沒有邊互連117著色結(jié)果如下：ABACADBABCBDDADBDCEAEB把上面方法應(yīng)用于圖1.2，得到下面的分組：

綠色：AB,AC,AD,BA,DC,ED藍(lán)色：BC,BD,EA紅色：DA,DB白色：EB,EC11819

算法精化：假設(shè)需要著色的圖是G，集合V1包括圖中所有未被著色的結(jié)點(diǎn)，著色開始時V1是G所有結(jié)點(diǎn)集合。NEW表示已確定可以用新顏色著色的結(jié)點(diǎn)集合。從V1中找出可用新顏色著色的結(jié)點(diǎn)集的程序框架描述為：NEW={};for每個vV1doifv與NEW中所有結(jié)點(diǎn)間都沒有邊{從V1中去掉v;NEW=NEW{v};}119算法精化：假設(shè)需要著色的圖是G，集合V1包括圖中所有未算法精化：intcolorUp(GraphG){intcolor=0;V1=G.V;while(!isSetEmpty(V1)){emptySet(NEW);while(vV1&&

notAdjacentWithSet(NEW,v,G)){addToSet(NEW,v);removeFromSet(V1,v);}++color;}return(color);}120算法精化：21由上述實(shí)例，抽象出數(shù)據(jù)結(jié)構(gòu)的概念：概括地說，

數(shù)據(jù)結(jié)構(gòu)是一門討論“描述現(xiàn)實(shí)世界實(shí)體的數(shù)學(xué)模型(非數(shù)值計算)及其上的操作在計算機(jī)中如何表示和實(shí)現(xiàn)”的學(xué)科。課本：數(shù)據(jù)結(jié)構(gòu):是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。121由上述實(shí)例，抽象出數(shù)據(jù)結(jié)構(gòu)的概念：數(shù)據(jù)結(jié)構(gòu)是一門討論“描《數(shù)據(jù)結(jié)構(gòu)課程》所處的地位：122《數(shù)據(jù)結(jié)構(gòu)課程》所處的地位：231.2基本概念一、數(shù)據(jù)與數(shù)據(jù)結(jié)構(gòu)二、數(shù)據(jù)類型三、抽象數(shù)據(jù)類型1231.2基本概念一、數(shù)據(jù)與數(shù)據(jù)結(jié)構(gòu)二、數(shù)據(jù)類型三、抽象數(shù)據(jù)一、數(shù)據(jù)與數(shù)據(jù)結(jié)構(gòu)所有能被輸入到計算機(jī)中，且能被計算機(jī)處理的符號(數(shù)值、字符等)的集合。數(shù)據(jù):是計算機(jī)操作的對象的總稱。是計算機(jī)處理的信息的某種特定的符號表示形式。124一、數(shù)據(jù)與數(shù)據(jù)結(jié)構(gòu)所有能被輸入到計算機(jī)中，且能被計算機(jī)處是數(shù)據(jù)（集合）中的一個“個體”,在計算機(jī)中通常作為一個整體進(jìn)行考慮和處理。是數(shù)據(jù)結(jié)構(gòu)中討論的基本單位。數(shù)據(jù)元素:如:整數(shù)“5”,字符“N”等。----是不可分割的“原子”125是數(shù)據(jù)（集合）中的一個“個體”,在計算機(jī)中通常作為一個整

其中每個款項(xiàng)稱為一個“數(shù)據(jù)項(xiàng)”它是數(shù)據(jù)結(jié)構(gòu)中討論的最小單位數(shù)據(jù)元素也可以由若干款項(xiàng)構(gòu)成。例如：描述一個學(xué)生的數(shù)據(jù)元素稱之為組合項(xiàng)年月日姓名學(xué)號班號性別出生日期入學(xué)成績原子項(xiàng)126其中每個款項(xiàng)稱為一個“數(shù)據(jù)項(xiàng)”它是數(shù)據(jù)結(jié)構(gòu)中討論的最小單位數(shù)據(jù)結(jié)構(gòu)：帶結(jié)構(gòu)的數(shù)據(jù)元素的集合數(shù)據(jù)結(jié)構(gòu)是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。指的是數(shù)據(jù)元素之間存在的關(guān)系127數(shù)據(jù)結(jié)構(gòu)：帶結(jié)構(gòu)的數(shù)據(jù)元素的集合數(shù)據(jù)結(jié)構(gòu)是相互之間存在一種或例如，在2行3列的二維數(shù)組中六個元素{a1,a2,a3,a4,a5,a6}之間存在兩個關(guān)系:行的次序關(guān)系:row={<a1,a2>,<a2,a3>,<a4,a5>,<a5,a6>}col={<a1,a4>,<a2,a5>,<a3,a6>}

a1a2a3a4a5a6列的次序關(guān)系:128例如，在2行3列的二維數(shù)組中六個元素行的次序關(guān)系:r若在6個數(shù)據(jù)元素{a1,a2,a3,a4,a5,a6}之間存在如下的次序關(guān)系:{<ai,ai+1>|i=1,2,3,4,5}

數(shù)據(jù)結(jié)構(gòu)是相互之間存在著某種邏輯關(guān)系的數(shù)據(jù)元素的集合?？梢?，不同的“關(guān)系”構(gòu)成不同的“結(jié)構(gòu)”則構(gòu)成一維數(shù)組的定義。129若在6個數(shù)據(jù)元素{a1,a2,a3,a4,從關(guān)系或結(jié)構(gòu)分，數(shù)據(jù)結(jié)構(gòu)可歸結(jié)為以下四類:線性結(jié)構(gòu)樹形結(jié)構(gòu)圖狀結(jié)構(gòu)集合結(jié)構(gòu)130從關(guān)系或結(jié)構(gòu)分，數(shù)據(jù)結(jié)構(gòu)可歸結(jié)為以下四類:線性結(jié)構(gòu)樹形結(jié)構(gòu)圖數(shù)據(jù)結(jié)構(gòu)包括“邏輯結(jié)構(gòu)”和“物理結(jié)構(gòu)”兩個方面(層次):邏輯結(jié)構(gòu)是對數(shù)據(jù)元素之間的邏輯關(guān)系的描述，它可以應(yīng)一個數(shù)據(jù)元素的集合和定義在此集合上的若干關(guān)系來表示;物理結(jié)構(gòu)是邏輯結(jié)構(gòu)在計算機(jī)中的表示和實(shí)現(xiàn)，故又稱“存儲結(jié)構(gòu)”。131數(shù)據(jù)結(jié)構(gòu)包括“邏輯結(jié)構(gòu)”和“物理結(jié)構(gòu)”兩個方面(層次):邏數(shù)據(jù)邏輯結(jié)構(gòu)的形式定義描述為:數(shù)據(jù)結(jié)構(gòu)是一個二元組Data_Structures=(D,S)其中:D是數(shù)據(jù)元素的有限集，

S是D上關(guān)系的有限集。132數(shù)據(jù)邏輯結(jié)構(gòu)的形式定義描述為:數(shù)據(jù)結(jié)構(gòu)是一個二元組Data數(shù)據(jù)的存儲結(jié)構(gòu)

——邏輯結(jié)構(gòu)在存儲器中的映象“數(shù)據(jù)元素”的映象？“關(guān)系”的映象？133數(shù)據(jù)的存儲結(jié)構(gòu)——邏輯結(jié)構(gòu)在存儲器中的映象“數(shù)據(jù)元素”的數(shù)據(jù)的存儲結(jié)構(gòu)：順序存儲結(jié)構(gòu)鏈?zhǔn)酱鎯Y(jié)構(gòu)索引存儲結(jié)構(gòu)散列存儲結(jié)構(gòu)134數(shù)據(jù)的存儲結(jié)構(gòu)：35數(shù)據(jù)元素的映象方法：用二進(jìn)制位(bit)的位串表示數(shù)據(jù)元素(321)10=(501)8=(101000001)2A=(101)8=(001000001)2135數(shù)據(jù)元素的映象方法：用二進(jìn)制位(bit)的位串表示數(shù)據(jù)元素(關(guān)系的映象方法：（表示x,y的方法）順序映象以相對的存儲位置表示后繼關(guān)系例如:令y的存儲位置和x的存儲位置之間差一個常量C而C是一個隱含值，整個存儲結(jié)構(gòu)中只含數(shù)據(jù)元素本身的信息xy136關(guān)系的映象方法：（表示x,y的方法）順序映象以相對的存鏈?zhǔn)接诚笠愿郊有畔?指針)表示后繼關(guān)系需要用一個和x在一起的附加信息指示y的存儲位置yx137鏈?zhǔn)接诚笠愿郊有畔?指針)表示后繼關(guān)系需要用一個和x在一在不同的編程環(huán)境中，存儲結(jié)構(gòu)可有不同的描述方法，當(dāng)用高級程序設(shè)計語言進(jìn)行編程時，通?？捎酶呒壘幊陶Z言中提供的數(shù)據(jù)類型描述之。138在不同的編程環(huán)境中，存儲結(jié)構(gòu)可有不同的描述方法，當(dāng)用高級程序例如:以三個帶有次序關(guān)系的整數(shù)表示一個長整數(shù)時，可利用C語言中提供的整數(shù)數(shù)組類型，typedefintLong_int[3]定義長整數(shù)為:139例如:以三個帶有次序關(guān)系的整數(shù)表示一個長整數(shù)時，可利用typedefstruct{

inty;//年號Year

intm;//月號Month

intd;//日號Day}DateType;//日期類型定義“日期”為:定義“學(xué)生”為:typedefstruct{

charid[8];//學(xué)號

charname[16];//姓名

charsex;//性別‘M/F’:男/女DateTypebdate;//出生日期}Student;//學(xué)生類型140typedefstruct{定義“日期”為:定義“學(xué)生”二、數(shù)據(jù)類型

在用高級程序語言編寫的程序中，必須對程序中出現(xiàn)的每個變量、常量或表達(dá)式，明確說明它們所

屬的數(shù)據(jù)類型。141二、數(shù)據(jù)類型在用高級程序語言編寫的程序中，必須對程序中出現(xiàn)例如，C語言中提供的基本數(shù)據(jù)類型有:整型int浮點(diǎn)型float字符型char邏輯型bool（C++語言）雙精度型double實(shí)型（C++語言）142例如，C語言中提供的基本數(shù)據(jù)類型有:整型int浮點(diǎn)型數(shù)據(jù)結(jié)構(gòu)：一組具有相同結(jié)構(gòu)的值。數(shù)據(jù)類型是一個值的集合和定義在此集合上的一組操作的總稱。

不同類型的變量，其所能取的值的范圍不同，所能進(jìn)行的操作不同。例如：整型值的范圍是：-32768-32767操作是：+，-，*，/，%143數(shù)據(jù)結(jié)構(gòu)：一組具有相同結(jié)構(gòu)的值。不同類型的變量，其所能各種高級程序設(shè)計語言中都擁有“整數(shù)”類型，盡管它們在不同處理器上實(shí)現(xiàn)的方法不同，但對程序員而言是“相同的”，因?yàn)樗鼈兊臄?shù)學(xué)特性相同。從“數(shù)學(xué)抽象”的角度看，可稱它為一個“抽象數(shù)據(jù)類型”。144各種高級程序設(shè)計語言中都擁有“整數(shù)”類型，盡管它們在不同處理三、抽象數(shù)據(jù)類型

(AbstractDataType簡稱ADT)是指一個數(shù)學(xué)模型以及定義在此數(shù)學(xué)模型上的一組操作145三、抽象數(shù)據(jù)類型是指一個數(shù)學(xué)模型以及定義在此數(shù)學(xué)模型上的例如:“整數(shù)”是一個抽象數(shù)據(jù)類型。其數(shù)學(xué)特性和具體的計算機(jī)或語言無關(guān)?！俺橄蟆钡囊饬x在于強(qiáng)調(diào)數(shù)據(jù)類型的數(shù)學(xué)特性。146例如:其數(shù)學(xué)特性和具體的計算機(jī)或語言無關(guān)。47抽象數(shù)據(jù)類型還包括用戶在設(shè)計軟件系統(tǒng)時自己定義的數(shù)據(jù)類型。在構(gòu)造軟件系統(tǒng)的各個相對獨(dú)立的模塊時，定義一組數(shù)據(jù)和施與這些數(shù)據(jù)之上的一組操作，并在模塊內(nèi)部給出它們的表示和實(shí)現(xiàn)細(xì)節(jié)，在模塊外部使用的只是抽象的數(shù)據(jù)和抽象的操作。147抽象數(shù)據(jù)類型還包括用戶在設(shè)計軟件系統(tǒng)時自己定義的數(shù)據(jù)類型。在例如，定義抽象數(shù)據(jù)類型“復(fù)數(shù)”

數(shù)據(jù)對象：

D＝{〈e1,e2〉｜e1,e2∈RealSet}

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

R1＝{P}P是很復(fù)雜的關(guān)系，如兩向量平行、垂直、相等、夾角，可比較大小，不可比較大小等。ADTComplex{148例如，定義抽象數(shù)據(jù)類型“復(fù)數(shù)”數(shù)據(jù)對象：ADT基本操作：AssignComplex(&Z,v1,v2)操作結(jié)果：構(gòu)造復(fù)數(shù)Z,其實(shí)部和虛部分別被賦以參數(shù)v1和v2的值。DestroyComplex(&Z)操作結(jié)果：復(fù)數(shù)Z被銷毀。GetReal(Z,&realPart)初始條件：復(fù)數(shù)已存在。操作結(jié)果：用realPart返回復(fù)數(shù)Z的實(shí)部值。149基本操作：AssignComplex(&Z,v1,v2GetImag(Z,&ImagPart)初始條件：復(fù)數(shù)已存在。操作結(jié)果：用ImagPart返回復(fù)數(shù)Z的虛部值。Add(z1,z2,&sum)初始條件：z1,z2是復(fù)數(shù)。操作結(jié)果：用sum返回兩個復(fù)數(shù)z1,z2的和值。Multiply(z1,z2,&z)division(z1,z2,&z)

}ADTComplex150GetImag(Z,&ImagPart)Add(z1

#include<iostream.h>#include"complex.h"

voidmain()

{

}……151#include<iostream.h>……52

complexz1,z2,z3,z4,z; floatRealPart,ImagPart;

InitComplex(z1,8.0,6.0);

InitComplex(z2,4.0,3.0);

Add(z1,z2,z3);

Multiply(z1,z2,z4); if(Division(z4,z3,z)){

GetReal(z,RealPart);

GetImag(z,ImagPart);}//if152 complexz1,z2,z3,z4,z;53ADT有兩個重要特征:數(shù)據(jù)抽象

用ADT描述程序處理的實(shí)體時，強(qiáng)調(diào)的是其本質(zhì)的特征、其所能完成的功能以及它和外部用戶的接口（即外界使用它的方法）數(shù)據(jù)封裝

將實(shí)體的外部特性和其內(nèi)部實(shí)現(xiàn)細(xì)節(jié)分離，并且對外部用戶隱藏其內(nèi)部實(shí)現(xiàn)細(xì)節(jié)153ADT有兩個重要特征:數(shù)據(jù)抽象用ADT描述抽象數(shù)據(jù)類型的描述方法抽象數(shù)據(jù)類型可用（D，S，P）三元組表示其中，D是數(shù)據(jù)對象，

S是D上的關(guān)系集，P是對D的基本操作集。154抽象數(shù)據(jù)類型的描述方法抽象數(shù)據(jù)類型可用（D，S，P）三元組表ADT

抽象數(shù)據(jù)類型名{數(shù)據(jù)對象：〈數(shù)據(jù)對象的定義〉

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

基本操作：〈基本操作的定義〉}ADT抽象數(shù)據(jù)類型名其中基本操作的定義格式為:基本操作名（參數(shù)表）

初始條件：〈初始條件描述〉

操作結(jié)果：〈操作結(jié)果描述〉

155ADT抽象數(shù)據(jù)類型名{其中基本操作的定義格式為:基本操作賦值參數(shù)只為操作提供輸入值；引用參數(shù)以&打頭，除可提供輸入值外，還將返回操作結(jié)果。初始條件描述了操作執(zhí)行之前數(shù)據(jù)結(jié)構(gòu)和參數(shù)應(yīng)滿足的條件，若不滿足，則操作失敗，并返回相應(yīng)出錯信息。操作結(jié)果說明了操作正常完成之后，數(shù)據(jù)結(jié)構(gòu)的變化狀況和應(yīng)返回的結(jié)果。若初始條件為空，則省略之。156賦值參數(shù)只為操作提供輸入值；初始條件描述了操作執(zhí)行之前數(shù)抽象數(shù)據(jù)類型的表示和實(shí)現(xiàn)抽象數(shù)據(jù)類型需要通過固有數(shù)據(jù)類型(高級編程語言中已實(shí)現(xiàn)的數(shù)據(jù)類型)來實(shí)現(xiàn)。例如，對以上定義的復(fù)數(shù)//-----存儲結(jié)構(gòu)的定義157抽象數(shù)據(jù)類型的表示和實(shí)現(xiàn)抽象數(shù)據(jù)類型需要通過固有數(shù)據(jù)typedefstruct{

floatrealpart；

floatimagpart；}complex；//-----存儲結(jié)構(gòu)的定義//-----基本操作的函數(shù)原型說明void

Assign(complex&Z,

floatrealval,floatimagval)；//構(gòu)造復(fù)數(shù)Z,其實(shí)部和虛部分別被賦以參數(shù)//realval和imagval的值158typedefstruct{//-----存儲結(jié)構(gòu)的float

GetReal(cpmplexZ)；//返回復(fù)數(shù)Z的實(shí)部值float

Getimag(cpmplexZ)；//返回復(fù)數(shù)Z的虛部值voidadd(complexz1,complexz2,complex&sum)；

//以sum返回兩個復(fù)數(shù)z1,z2的和159floatGetReal(cpmplexZ)；flo//-----基本操作的實(shí)現(xiàn)voidadd(complexz1,complexz2,complex&sum)

{//以sum返回兩個復(fù)數(shù)z1,z2的和sum.realpart=z1.realpart+z2.realpart;sum.imagpart=z1.imagpart+z2.imagpart;}{其它省略}160//-----基本操作的實(shí)現(xiàn)voidadd(compl1.3算法和算法的衡量一、算法二、算法設(shè)計的原則三、算法效率的衡量方法和準(zhǔn)則四、算法的存儲空間需求1611.3算法和算法的衡量一、算法二、算法設(shè)計的原則三、算法效算法是為了解決某類問題而規(guī)定的一個有限長的操作序列。一個算法必須滿足以下五個重要特性：1．有窮性

2．確定性3．可行性4．有輸入5．有輸出一、算法162算法是為了解決某類問題而規(guī)定的一個有限長的操作序列。1．有窮性對于任意一組合法輸入值，在執(zhí)行有窮步驟之后一定能結(jié)束，即：算法中的每個步驟都能在有限時間內(nèi)完成；2．確定性

對于每種情況下所應(yīng)執(zhí)行的操作，在算法中都有確切的規(guī)定，使算法的執(zhí)行者或閱讀者都能明確其含義及如何執(zhí)行。并且在任何條件下，算法都只有一條執(zhí)行路徑；1631．有窮性對于任意一組合法輸入值，在執(zhí)行有窮步驟之后一定3．可行性算法中的所有操作都必須足夠基本，都可以通過已經(jīng)實(shí)現(xiàn)的基本操作運(yùn)算有限次實(shí)現(xiàn)之；4．有輸入作為算法加工對象的量值，通常體現(xiàn)為算法中的一組變量。有