本課程教學內容第一章緒論第二章線性表第三章棧和隊列第四章串第五章數組和廣義表第六章樹和二叉樹第七章圖第八章動態存儲管理第九章查找第十章內部排序第十一章外部排序第十二章文件本課程內容結構數據結構線性結構非線性結構線性表棧隊列串數組和廣義表順序表鏈表單鏈表雙向鏈表循環鏈表兩種存儲結構順序存儲鏈式存儲樹圖二叉樹的遍歷樹和森林哈夫曼樹及哈夫曼編碼圖的存儲圖的遍歷最小生成樹拓撲排序和關鍵路徑最短路徑查找排序靜態動態哈希表內部外部第一章緒論1.1數據結構的研究對象1.2數據結構的基本概念1.3抽象數據類型的表示與實現1.4算法和算法分析計算機的發展僅能進行數值計算能處理各種非數值數據數據處理的種類數值數據

非數值數據

數(整數,實數)字符字符串文字圖形圖象聲音1.1數據結構的研究對象

數值問題與非數值問題1）數值問題例1已知：游泳池的長len和寬wide，求面積area問題涉及的對象：游泳池的長len

寬wide，面積area；

對象之間的關系：area=lenwide1.1數據結構的研究對象例2線性方程組求解

學號姓名性別出生日期籍貫入學成績所在班級 00201

楊潤生男

82/06/01廣州56100計算機2

00102石磊男83/12/21汕頭51200計算機1

00202李梅女83/02/23陽江53200計算機200301馬耀先男

82/07/12廣州

50900計算機32）非數值問題例1已知某年級學生情況,要求分班并按入學成績排列順序。在這類文檔管理的數學模型中,計算機處理的對象之間通常存在著一種最簡單的線性關系,這類數學模型稱為線性模型。1.1數據結構的研究對象例2迷宮問題。1.1數據結構的研究對象入口出口例3多岔路口交通燈的管理問題。1.1數據結構的研究對象CDEAB數據結構研究的問題：非數值數據之間的結構關系及如何表示，如何存儲，如何處理。1.1數據結構的研究對象1.2數據結構的基本概念一、基本概念二、數據結構的分類三、數據結構的存儲四、數據類型1.數據能被輸入計算機且能被計算機處理的一切對象。(是信息的載體，是客觀事物的符號表示。)

例如：整數，實數，字符串、圖象、聲音等都是數據。一、基本概念2.數據元素是現實世界中某獨立實體的數據描述。是數據結構討論的基本單位，有時稱為結點、或記錄。一般由若干數據項組成。1.2數據結構的基本概念3.數據項具有獨立意義的最小數據單位，是相對數據元素的，有時稱域或字段。一、基本概念姓名性別年齡專業班級

數據項4.數據對象具有相同特征的數據元素的有限集合。例如：某個學生信息(數據元素)1.2數據結構的基本概念5.數據結構結構是數據元素之間的關系。數據結構是帶結構的數據元素的集合。

一、基本概念例如一個12位的十進制數可以用三個4位十進制數表示：3214，6587，9345——a1(3214),a2(6587),a3(9345)在a1,a2,a3之間存在“次序”關系<a1,a2>,<a2,a3>3214,6587,9345≠6587,3214,9345a1a2a3a2a1a31.2數據結構的基本概念數據結構的數學定義形式：

B=(D,R)二元組

D:數據元素的集合(數據對象)R:D上關系的集合，表示數據元素之間的前驅、后繼關系。一、基本概念1.2數據結構的基本概念如：B=(D,R)D={a,b,c,d,e,f,g}R={<a,b>,<a,c>,<b,d>,<b,e>,<c,f>,<c,g>}cfbedag6.數據的邏輯結構上述定義中“關系”描述的是數據元素之間的邏輯關系，即數據的邏輯結構。通常簡稱為數據結構。一、基本概念7.數據的存儲結構數據結構在計算機中的表示，又稱物理結構。是邏輯結構在存儲器中的映像。1.2數據結構的基本概念1.集合二、數據結構的分類2.線性結構3.樹型結構4.圖狀結構1.2數據結構的基本概念某班學生基本情況登記表，記錄了每個學生的學號姓名專業政治面貌，表中的記錄是按學生的學號順序排列的。學號姓名 專業 政治面藐

001 王洪 計算機黨員

002孫文計算機團員

003 謝軍 計算機團員

004 李輝 計算機團員

005 沈祥福計算機黨員

006 余斌 計算機團員

007 鞏力 計算機團員

008 孔令輝計算機團員學生基本情況登記表的圖示

001003002004006005008007學生間學號順序關系是一種線性結構關系例一常用的數據結構

1）線性結構

2）非線性結構

如樹、圖等二、數據結構的分類家族的族譜

假設某家族有10個成員A，B，C，D，E，F，G，H，I，J，他們之間的血緣關系可以用如下圖表示。JIACBDHGFE例二、數據結構的分類樹形結構三、數據結構的存儲數據結構包括結點的值及結點之間的關系。1.順序存儲(順序映像)只存儲結點(數據元素)的值。結點之間的關系：由存儲單元的相鄰關系隱含地表示。適合于線性結構。在高級語言中常用數組表示順序存儲結構。1.2數據結構的基本概念地址數據3142331566316783173431887例：23，66，78，34，87三、數據結構的存儲2.鏈接存儲（非順序映像）存儲結點的值和結點之間的關系。用指針表示結點之間的關系，是各結點的后繼結點的地址。兩部分數據域：存儲結點自身的值指針域：存儲該結點的各后繼結點的存儲單元的地址1.2數據結構的基本概念地址

datalink0001630002000254000500038200040004660001000550^00030004000100020005存儲結構8266546350三、數據結構的存儲邏輯表示例1-1：有一線性結構結點集合：

D={63，54，82，66，50}

關系為結點值的降序：

R={<82,66>,<66,63>,<63,54>,<54,50>}1.2數據結構的基本概念例1-2：有一樹型結構：

B=（D，R）

D={A，B，C，D，E，F，G}R={<A,B>,<A,C>,<B,D>,<B,E>,<C,F>,<F,G>}

邏輯表示：存儲結構：三、數據結構的存儲adddataLlinkRlink0000A000100020001B000300040002C0005^0003D^^0004E^^0005F0006^0006G^^1.2數據結構的基本概念四、數據類型1.定義數據類型是一個值的集合和定義在這個值集上的一組操作的總稱。具體到高級語言中，例如整型、字符型等。整形上的加、減、乘、除操作。2.分類非結構類型：原子類型結構型：由一組原子類型或結構類型按某種結構組成1.2數據結構的基本概念數據類型是和數據結構密切相關的一個概念，最早出現在高級語言中，用以刻畫程序操作對象的特性。用高級語言編寫的程序中，每個變量、常量或表達式都有一個它所屬的數據類型。四、數據類型抽象數據類型-ADT(AbstractDataType)

是指一個數學模型以及定義在此數學模型上的一組操作。抽象數據類型和數據類型實質上是一個概念。1.2數據結構的基本概念抽象數據類型的描述抽象數據類型定義用三元組表示：（D，S，P），

其中，D是數據對象，

S是D上的關系集，

P是對D的基本操作集。定義格式：ADT抽象數據類型名{數據對象：<數據對象的定義>

數據關系：<數據關系的定義>

基本操作：<基本操作的定義>（相當于聲明若干函數)}ADT抽象數據類型名

四、數據類型1.2數據結構的基本概念如：用三元組定義出抽象數據類型復數ADTList{

數據對象：D={e1,e2|e1,e2∈實數,e1,e2分別代表實部與虛部}

數據關系：R1={<e1,e2>|}

基本操作：復數相加復數相減

}四、數據類型1.2數據結構的基本概念抽象數據類型的表示與實現我們通過固有的數據類型（高級語言中已實現的數據類型）來表示和實現抽象數據類型。

1.3抽象數據類型的表示與實現1.2數據結構的基本概念1.4算法和算法的衡量數據結構+算法=程序程序：為計算機處理問題編制的一組指令集數據結構：問題的數學模型算法：處理問題的策略，是對特定問題求解步驟的一種描述，是有限長的操作序列。

1.4算法和算法的衡量一、算法和算法的五個重要特性二、算法的設計原則三、時間復雜度和空間復雜度一、算法和算法的五個重要特性

算法有五個重要特性：1.有窮性2.確定性3.可行性4.輸入5.輸出1.3算法和算法的衡量一、算法和算法的五個重要特性1.有窮性：執行有窮步后結束，且每一步在有窮時間內完成。2.確定性：每一條指令必須有確切的含義，不會產生二義性。并且在任何條件下，算法都只有一條執行的路徑。3.可行性：算法中描述的操作都是可以通過基本運算執行有

限次實現。4.輸入：有0個或多個輸入。作為算法加工對象的量值，通常體現為算法中的一組變量值，有些是算法執行過程中輸入的，有些已被嵌入在算法中。5.輸出：有一個或多個輸出。是一組與輸入有確定關系的量值，是算法加工信息對象后得到的結果。這種確定關系即為算法的功能。

1.3算法和算法的衡量二、算法的設計原則衡量算法性能的標準。設計算法時，通常應考慮達到以下目標：1.正確性2.可讀性3.健壯性4.高效率與低存儲量的需求1.3算法和算法的衡量1.正確性（有效性）首先，算法能夠正確地實現預先規定的功能。其次，對正確性理解的四個層次：

(1)程序中不含語法錯誤

(2)程序對幾組輸入數據能夠得出滿足要求的結果

(3)程序對精心選擇的典型、苛刻而帶有刁難性的幾組輸入數據能得出滿足要求的結果

(4)對一切合法的輸入數據都能產生滿足要求的結果二、算法的設計原則1.3算法和算法的衡量2.可讀性可讀性好。算法的邏輯必須是清晰的、簡單的和結構化的。有助于人對算法的理解，為了人的閱讀與交流。3.健壯性很好的容錯性，即提供例外處理，對不合理的數據作出反應或進行處理，而不會產生莫明其妙的結果或出現異常中斷、死機等現象，對于出錯應報告出錯信息。三、算法的設計原則1.3算法和算法的衡量二、算法的設計原則4.高效率與低存儲量的需求

效率：指的是算法執行的時間；

存儲量：指的是算法執行過程中所需的最大存儲空間。通常，用時間復雜度來度量效率；用空間復雜度來試題存儲量。1.3算法和算法的衡量三、時間復雜度和空間復雜度1.時間復雜度(1)和算法執行時間相關的因素：1.問題性質

2.問題規模3.算法選用的策略4.編寫程序的語言5.編譯程序6.計算機執行指令的速度(2)算法的時間復雜度與運行算法的目標計算機及描述算法的工具無關。取決于以下三方面：問題性質問題規模算法性質1.3算法和算法的衡量算法=控制結構+原操作

三、時間復雜度和空間復雜度以基本操作重復執行的次數作為算法的時間量度。重復執行的次數是一個函數f(n)。自變量n稱做此算法的問題規模時間復雜度(漸進時間復雜度)記作：

T(n)=O(f(n))

算法執行時間的增長率和f(n)的增率相同。所研究的基本操作

1.3算法和算法的衡量例1-3

兩個n階矩陣相加，即C=A+B，其算法如下：#defineMAX20voidmatrixadd(int

n,int

a[MAX][MAX],int

b[MAX][MAX],int

c[MAX][MAX]){inti,j;for(i=0;i<n;i++)for(j=0;j<n;j++)

c[i][j]=a[i][j]+b[i][j];

//重復執行的次數為n2}

此時f(n)=n2

因此：

T(n)=O(f(n))=O(n2)

三、時間復雜度和空間復雜度1.3算法和算法的衡量

基本操作大多在循環和遞歸中。時間復雜度通常具有的形式：

O(1)、O(log2n)、O(n)、O(n*log2n)、O(n2)、O(n3)、O(2n)、O(n!)

不同數量級對應的值的關系：

O(1)<O(log2n)<O(n)<O(n*log2n)<O(n2)<O(n3)<O(2n)<O(n!)三、時間復雜度和空間復雜度1.3算法和算法的衡量

（1）有些算法，基本操作執行次數難以確定，只考慮它的階數。（2）有些算法，基本操作執行次數與問題的輸入數據有關，這時可考慮

算法平均時間復雜度

（3）算法在最壞情況下的時間復雜度三、時間復雜度和空間復雜度2．空間復雜度空間復雜度是算法在執行過程中占用存儲容量的度量。算法的存儲量包含：輸入數據、程序和輔助變量所占的存儲空間。

空間復雜度是問題規模的函數，記為g(n)。

表示為：S(n)=O(g(n))

其中：n為問題的規模，g(n)與解決問題所用的存儲