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

計算機信息表示A信息表示B著名計算機科學家N.Wirth提出下面的公式：算法+數據結構=程序

5計算機信息表示A信息表示B著名計算機科學家N.Wirth

數據結構討論的范疇3。編碼階段2。設計階段1。分析階段4。測試和維護（與本課程關系最密切）為一個實際問題開發一個程序，系統通常可以分成以下四個階段6數據結構討論的范疇3。編碼階段2。設計階段1。分析階段4。

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

可通行方向ABACADBABCBDDADBDCEAEBECED13問題分析

可通行方向13有些通行方向顯然不能同時進行，相應的結點間畫一條連線。ABACADBABCBDDADBDCEAEBECED圖1.2交叉路口的圖示模型14有些通行方向顯然不能同時進行，相應的結點間畫一條連線。ABA

把圖1.2中的結點進行分組，使得有結點相連的結點不在同一個組里。

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

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

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

算法精化：假設需要著色的圖是G，集合V1包括圖中所有未被著色的結點，著色開始時V1是G所有結點集合。NEW表示已確定可以用新顏色著色的結點集合。從V1中找出可用新顏色著色的結點集的程序框架描述為：NEW={};for每個vV1doifv與NEW中所有結點間都沒有邊{從V1中去掉v;NEW=NEW{v};}20算法精化：假設需要著色的圖是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由上述實例，抽象出數據結構的概念：概括地說，

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

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

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

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

S是D上關系的有限集。33數據邏輯結構的形式定義描述為:數據結構是一個二元組Data數據的存儲結構

——邏輯結構在存儲器中的映象“數據元素”的映象？“關系”的映象？34數據的存儲結構——邏輯結構在存儲器中的映象“數據元素”的數據的存儲結構：順序存儲結構鏈式存儲結構索引存儲結構散列存儲結構35數據的存儲結構：35數據元素的映象方法：用二進制位(bit)的位串表示數據元素(321)10=(501)8=(101000001)2A=(101)8=(001000001)236數據元素的映象方法：用二進制位(bit)的位串表示數據元素(關系的映象方法：（表示x,y的方法）順序映象以相對的存儲位置表示后繼關系例如:令y的存儲位置和x的存儲位置之間差一個常量C而C是一個隱含值，整個存儲結構中只含數據元素本身的信息xy37關系的映象方法：（表示x,y的方法）順序映象以相對的存鏈式映象以附加信息(指針)表示后繼關系需要用一個和x在一起的附加信息指示y的存儲位置yx38鏈式映象以附加信息(指針)表示后繼關系需要用一個和x在一在不同的編程環境中，存儲結構可有不同的描述方法，當用高級程序設計語言進行編程時，通常可用高級編程語言中提供的數據類型描述之。39在不同的編程環境中，存儲結構可有不同的描述方法，當用高級程序例如:以三個帶有次序關系的整數表示一個長整數時，可利用C語言中提供的整數數組類型，typedefintLong_int[3]定義長整數為:40例如:以三個帶有次序關系的整數表示一個長整數時，可利用typedefstruct{

inty;//年號Year

intm;//月號Month

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

charid[8];//學號

charname[16];//姓名

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

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

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

不同類型的變量，其所能取的值的范圍不同，所能進行的操作不同。例如：整型值的范圍是：-32768-32767操作是：+，-，*，/，%44數據結構：一組具有相同結構的值。不同類型的變量，其所能各種高級程序設計語言中都擁有“整數”類型，盡管它們在不同處理器上實現的方法不同，但對程序員而言是“相同的”，因為它們的數學特性相同。從“數學抽象”的角度看，可稱它為一個“抽象數據類型”。45各種高級程序設計語言中都擁有“整數”類型，盡管它們在不同處理三、抽象數據類型

(AbstractDataType簡稱ADT)是指一個數學模型以及定義在此數學模型上的一組操作46三、抽象數據類型是指一個數學模型以及定義在此數學模型上的例如:“整數”是一個抽象數據類型。其數學特性和具體的計算機或語言無關。“抽象”的意義在于強調數據類型的數學特性。47例如:其數學特性和具體的計算機或語言無關。47抽象數據類型還包括用戶在設計軟件系統時自己定義的數據類型。在構造軟件系統的各個相對獨立的模塊時，定義一組數據和施與這些數據之上的一組操作，并在模塊內部給出它們的表示和實現細節，在模塊外部使用的只是抽象的數據和抽象的操作。48抽象數據類型還包括用戶在設計軟件系統時自己定義的數據類型。在例如，定義抽象數據類型“復數”

數據對象：

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

數據關系：

R1＝{P}P是很復雜的關系，如兩向量平行、垂直、相等、夾角，可比較大小，不可比較大小等。ADTComplex{49例如，定義抽象數據類型“復數”數據對象：ADT基本操作：AssignComplex(&Z,v1,v2)操作結果：構造復數Z,其實部和虛部分別被賦以參數v1和v2的值。DestroyComplex(&Z)操作結果：復數Z被銷毀。GetReal(Z,&realPart)初始條件：復數已存在。操作結果：用realPart返回復數Z的實部值。50基本操作：AssignComplex(&Z,v1,v2GetImag(Z,&ImagPart)初始條件：復數已存在。操作結果：用ImagPart返回復數Z的虛部值。Add(z1,z2,&sum)初始條件：z1,z2是復數。操作結果：用sum返回兩個復數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有兩個重要特征:數據抽象

用ADT描述程序處理的實體時，強調的是其本質的特征、其所能完成的功能以及它和外部用戶的接口（即外界使用它的方法）數據封裝

將實體的外部特性和其內部實現細節分離，并且對外部用戶隱藏其內部實現細節54ADT有兩個重要特征:數據抽象用ADT描述抽象數據類型的描述方法抽象數據類型可用（D，S，P）三元組表示其中，D是數據對象，

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

抽象數據類型名{數據對象：〈數據對象的定義〉

數據關系：〈數據關系的定義〉

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

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

操作結果：〈操作結果描述〉

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

floatrealpart；

floatimagpart；}complex；//-----存儲結構的定義//-----基本操作的函數原型說明void

Assign(complex&Z,

floatrealval,floatimagval)；//構造復數Z,其實部和虛部分別被賦以參數//realval和imagval的值59typedefstruct{//-----存儲結構的float

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

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

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

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

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

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

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

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

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

簡單賦值變量名=表達式；

串聯賦值變量名1=變量名2=...=變量名n=表達式；

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

結構賦值結構名1=結構名2；

結構名=（值1，值2，...，值n）；

條件賦值變量名=條件表達式?表達式1：表達式2；交換賦值變量名1變量名2；693.在算法描述中可以使用的賦值語句形式有：694.在算法描述中可以使用的選擇結構語句形式有：條件語句1if（表達式）語句；條件語句2if（表達式）語句；else語句；開關語句1

switch（表達式）{

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

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

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

default：語句序列n+1；}704.在算法描述中可以使用的選擇結構語句形式有：70開關語句2

switch{

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

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

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

5.在算法描述中可以使用的循環結構語句形式有：for循環語句

for（表達式1；循環條件表達式；表達式2）語句；while循環語句

while（循環條件表達式）語句；do-while循環語句

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

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

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

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

首先，算法應當滿足以特定的“規格說明”方式給出的需求。

其次，對算法是否“正確”的理解可以有以下四個層次：a．程序中不含語法錯誤；b．程序對于幾組輸入數據能夠得出滿足要求的結果；751．正確性首先，算法應當滿足以特定的“規格說明”方式c．程序對于精心選擇的、典型、苛刻且帶有刁難性的幾組輸入數據能夠得出滿足要求的結果；通常以第c層意義的正確性作為衡量一個算法是否合格的標準。

d．程序對于一切合法的輸入數據都能得出滿足要求的結果；76c．程序對于精心選擇的、典型、苛刻且帶有刁難性的幾組輸入數2.可讀性算法主要是為了人的閱讀與交流，其次才是為計算機執行。因此算法應該易于人的理解；另一方面，晦澀難讀的程序易于隱藏較多錯誤而難以調試；772.可讀性算法主要是為了人的閱讀與交流，其次才是為3．健壯性當輸入的數據非法時，算法應當恰當地作出反映或進行相應處理，而不是產生莫名奇妙的輸出結果。并且，處理出錯的方法不應是中斷程序的執行，而應是返回一個表示錯誤或錯誤性質的值，以便在更高的抽象層次上進行處理。783．健壯性當輸入的數據非法時，算法應當恰當地作出反映或4．高效率與低存儲量需求通常，效率指的是算法執行時間；存儲量指的是算法執行過程中所需的最大存儲空間。兩者都與問題的規模有關。794．高效率與低存儲量需求通常，效率指的是算法執行時間；三、算法效率的衡量方法和準則通常有兩種衡量算法效率的方法:

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

算法的執行時間

與

原操作執行次數之和

成正比

如何估算算法的時間復雜度？84算法=控制結構+原操作（固有數據類型的操作）算法的執從算法中選取一種對于所研究的問題來說是基本操作

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

//以二維數組存儲矩陣元素，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基本操作:

乘法操作時間復雜度:

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

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

}//select_sort基本操作:

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

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中整數序列重新排列成自小至大有序的整數序列。for

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

賦值操作時間復雜度:

O(n2){

change=FALSE;

//change為元素進行交換標志

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常見函數的增長率算法時間效率的度量分析圖1-7常見函數的增長率90四、算法的存儲空間需求算法的空間復雜度定義為:

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

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

計算機信息表示A信息表示B著名計算機科學家N.Wirth提出下面的公式：算法+數據結構=程序

104計算機信息表示A信息表示B著名計算機科學家N.Wirth

數據結構討論的范疇3。編碼階段2。設計階段1。分析階段4。測試和維護（與本課程關系最密切）為一個實際問題開發一個程序，系統通常可以分成以下四個階段105數據結構討論的范疇3。編碼階段2。設計階段1。分析階段4。

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

可通行方向ABACADBABCBDDADBDCEAEBECED112問題分析

可通行方向13有些通行方向顯然不能同時進行，相應的結點間畫一條連線。ABACADBABCBDDADBDCEAEBECED圖1.2交叉路口的圖示模型113有些通行方向顯然不能同時進行，相應的結點間畫一條連線。ABA

把圖1.2中的結點進行分組，使得有結點相連的結點不在同一個組里。

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

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

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

算法精化：假設需要著色的圖是G，集合V1包括圖中所有未被著色的結點，著色開始時V1是G所有結點集合。NEW表示已確定可以用新顏色著色的結點集合。從V1中找出可用新顏色著色的結點集的程序框架描述為：NEW={};for每個vV1doifv與NEW中所有結點間都沒有邊{從V1中去掉v;NEW=NEW{v};}119算法精化：假設需要著色的圖是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由上述實例，抽象出數據結構的概念：概括地說，

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

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

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

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

S是D上關系的有限集。132數據邏輯結構的形式定義描述為:數據結構是一個二元組Data數據的存儲結構

——邏輯結構在存儲器中的映象“數據元素”的映象？“關系”的映象？133數據的存儲結構——邏輯結構在存儲器中的映象“數據元素”的數據的存儲結構：順序存儲結構鏈式存儲結構索引存儲結構散列存儲結構134數據的存儲結構：35數據元素的映象方法：用二進制位(bit)的位串表示數據元素(321)10=(501)8=(101000001)2A=(101)8=(001000001)2135數據元素的映象方法：用二進制位(bit)的位串表示數據元素(關系的映象方法：（表示x,y的方法）順序映象以相對的存儲位置表示后繼關系例如:令y的存儲位置和x的存儲位置之間差一個常量C而C是一個隱含值，整個存儲結構中只含數據元素本身的信息xy136關系的映象方法：（表示x,y的方法）順序映象以相對的存鏈式映象以附加信息(指針)表示后繼關系需要用一個和x在一起的附加信息指示y的存儲位置yx137鏈式映象以附加信息(指針)表示后繼關系需要用一個和x在一在不同的編程環境中，存儲結構可有不同的描述方法，當用高級程序設計語言進行編程時，通常可用高級編程語言中提供的數據類型描述之。138在不同的編程環境中，存儲結構可有不同的描述方法，當用高級程序例如:以三個帶有次序關系的整數表示一個長整數時，可利用C語言中提供的整數數組類型，typedefintLong_int[3]定義長整數為:139例如:以三個帶有次序關系的整數表示一個長整數時，可利用typedefstruct{

inty;//年號Year

intm;//月號Month

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

charid[8];//學號

charname[16];//姓名

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

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

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

不同類型的變量，其所能取的值的范圍不同，所能進行的操作不同。例如：整型值的范圍是：-32768-32767操作是：+，-，*，/，%143數據結構：一組具有相同結構的值。不同類型的變量，其所能各種高級程序設計語言中都擁有“整數”類型，盡管它們在不同處理器上實現的方法不同，但對程序員而言是“相同的”，因為它們的數學特性相同。從“數學抽象”的角度看，可稱它為一個“抽象數據類型”。144各種高級程序設計語言中都擁有“整數”類型，盡管它們在不同處理三、抽象數據類型

(AbstractDataType簡稱ADT)是指一個數學模型以及定義在此數學模型上的一組操作145三、抽象數據類型是指一個數學模型以及定義在此數學模型上的例如:“整數”是一個抽象數據類型。其數學特性和具體的計算機或語言無關。“抽象”的意義在于強調數據類型的數學特性。146例如:其數學特性和具體的計算機或語言無關。47抽象數據類型還包括用戶在設計軟件系統時自己定義的數據類型。在構造軟件系統的各個相對獨立的模塊時，定義一組數據和施與這些數據之上的一組操作，并在模塊內部給出它們的表示和實現細節，在模塊外部使用的只是抽象的數據和抽象的操作。147抽象數據類型還包括用戶在設計軟件系統時自己定義的數據類型。在例如，定義抽象數據類型“復數”

數據對象：

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

數據關系：

R1＝{P}P是很復雜的關系，如兩向量平行、垂直、相等、夾角，可比較大小，不可比較大小等。ADTComplex{148例如，定義抽象數據類型“復數”數據對象：ADT基本操作：AssignComplex(&Z,v1,v2)操作結果：構造復數Z,其實部和虛部分別被賦以參數v1和v2的值。DestroyComplex(&Z)操作結果：復數Z被銷毀。GetReal(Z,&realPart)初始條件：復數已存在。操作結果：用realPart返回復數Z的實部值。149基本操作：AssignComplex(&Z,v1,v2GetImag(Z,&ImagPart)初始條件：復數已存在。操作結果：用ImagPart返回復數Z的虛部值。Add(z1,z2,&sum)初始條件：z1,z2是復數。操作結果：用sum返回兩個復數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有兩個重要特征:數據抽象

用ADT描述程序處理的實體時，強調的是其本質的特征、其所能完成的功能以及它和外部用戶的接口（即外界使用它的方法）數據封裝

將實體的外部特性和其內部實現細節分離，并且對外部用戶隱藏其內部實現細節153ADT有兩個重要特征:數據抽象用ADT描述抽象數據類型的描述方法抽象數據類型可用（D，S，P）三元組表示其中，D是數據對象，

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

抽象數據類型名{數據對象：〈數據對象的定義〉

數據關系：〈數據關系的定義〉

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

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

操作結果：〈操作結果描述〉

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

floatrealpart；

floatimagpart；}complex；//-----存儲結構的定義//-----基本操作的函數原型說明void

Assign(complex&Z,

floatrealval,floatimagval)；//構造復數Z,其實部和虛部分別被賦以參數//realval和imagval的值158typedefstruct{//-----存儲結構的float

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

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

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

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

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

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