數(shù)據(jù)與算法

第 1章數(shù)據(jù)、數(shù)學(xué)模型和算法 ................................................................................ 1
1.1數(shù)據(jù)時(shí)代 ................................................................................................... 1
1.1.1什么是數(shù)據(jù) ..................................................................................... 1
1.1.2大數(shù)據(jù)時(shí)代 ..................................................................................... 2
1.1.3數(shù)據(jù)的重要性 .................................................................................. 4
1.2數(shù)據(jù)的表示 ................................................................................................ 5
1.2.1二元關(guān)系及其性質(zhì) ........................................................................... 5
1.2.2數(shù)據(jù)的邏輯結(jié)構(gòu) .............................................................................. 9
1.2.3數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu) .............................................................................12
1.2.4抽象數(shù)據(jù)類(lèi)型 .................................................................................12
1.3數(shù)學(xué)模型 ..................................................................................................13
1.3.1什么是數(shù)學(xué)模型 .............................................................................13
1.3.2數(shù)學(xué)模型的種類(lèi) .............................................................................14
1.3.3數(shù)學(xué)模型與計(jì)算機(jī) ..........................................................................15
1.3.4數(shù)據(jù)結(jié)構(gòu) .......................................................................................16
1.4算法及復(fù)雜度分析 .....................................................................................16
1.4.1什么是算法 ....................................................................................16
1.4.2問(wèn)題與解 .......................................................................................17
1.4.3算法的分析與評(píng)價(jià) ..........................................................................18
1.5本章小結(jié) ..................................................................................................22
第 2章線(xiàn)性結(jié)構(gòu)...................................................................................................24
2.1線(xiàn)性表 .....................................................................................................24
2.1.1線(xiàn)性表的概念及其抽象數(shù)據(jù)類(lèi)型 ......................................................24
2.1.2線(xiàn)性表的順序存儲(chǔ)——順序表 .........................................................27
2.1.3線(xiàn)性表的鏈?zhǔn)酱鎯?chǔ)——鏈表 .............................................................30
2.1.4線(xiàn)性表小結(jié) ....................................................................................35
2.2棧 ............................................................................................................35
2.2.1棧的概念與實(shí)現(xiàn) .............................................................................35
2.2.2棧的應(yīng)用 .......................................................................................38
2.2.3遞歸 ..............................................................................................41
2.3隊(duì)列 .........................................................................................................48
2.3.1隊(duì)列的概念與實(shí)現(xiàn) ..........................................................................48
2.3.2優(yōu)先級(jí)隊(duì)列 ....................................................................................51
2.4字符串 .....................................................................................................55
2.4.1字符串的概念和 ADT ......................................................................55
2.4.2字符串的存儲(chǔ)表示 ..........................................................................56
2.4.3字符串的模式匹配和簡(jiǎn)單匹配算法 ...................................................57
2.4.4 KMP算法 .....................................................................................58
2.5本章小結(jié) ..................................................................................................61
第 3章樹(shù)與二叉樹(shù) ...............................................................................................62
3.1樹(shù)的基本概念 ...........................................................................................62
3.1.1普遍存在的樹(shù)結(jié)構(gòu) ..........................................................................62
3.1.2樹(shù)的定義和性質(zhì) .............................................................................65
3.2二叉樹(shù) .....................................................................................................67
3.2.1二叉樹(shù)的定義和性質(zhì) .......................................................................68
3.2.2二叉樹(shù)的表示和實(shí)現(xiàn) .......................................................................70
3.2.3二叉樹(shù)的遍歷 .................................................................................76
3.2.4二叉樹(shù)運(yùn)算 ....................................................................................81
3.2.5二叉樹(shù)的建立 .................................................................................83
3.3二叉樹(shù)的應(yīng)用 ...........................................................................................84
3.3.1表達(dá)式求值 ....................................................................................84
3.3.2二叉搜索樹(shù) ....................................................................................85
3.3.3 Hu.man樹(shù)與編碼 ..........................................................................89
3.3.4堆 .................................................................................................95
3.4并查集 ................................................................................................... 102
3.5本章小結(jié) ................................................................................................ 103
第 4章圖........................................................................................................... 105
4.1圖的基本概念 ......................................................................................... 105
4.1.1圖的定義和概念 ........................................................................... 105
4.1.2圖的抽象數(shù)據(jù)類(lèi)型 ........................................................................ 110
4.1.3歐拉路徑 ..................................................................................... 110
4.2圖的存儲(chǔ)結(jié)構(gòu) ......................................................................................... 112
4.2.1圖的鄰接矩陣表示 ........................................................................ 112
4.2.2圖的鄰接表表示 ........................................................................... 115
4.2.3圖的其他表示方法 ........................................................................ 119
4.3圖的遍歷 ................................................................................................ 122
4.3.1圖的深度優(yōu)先遍歷 ........................................................................ 123
目錄 IX
4.3.2圖的廣度優(yōu)先遍歷 ........................................................................ 124
4.3.3圖遍歷的應(yīng)用 ............................................................................... 125
4.3.4圖的連通性 .................................................................................. 128
4.4有向圖與有向無(wú)環(huán)圖 ............................................................................... 129
4.4.1有向圖的連通性和傳遞閉包 ........................................................... 129
4.4.2有向無(wú)環(huán)圖和拓?fù)渑判?................................................................. 132
4.4.3關(guān)鍵路徑 ..................................................................................... 135
4.5最小生成樹(shù) ............................................................................................. 137
4.5.1圖的生成樹(shù)與最小生成樹(shù) .............................................................. 137
4.5.2普里姆 (Prim)算法 ...................................................................... 139
4.5.3克魯斯卡爾 (Kruskal)算法 ............................................................ 142
4.6最短路徑問(wèn)題 ......................................................................................... 144
4.6.1單源最短路徑 ............................................................................... 145
4.6.2全源最短路徑 ............................................................................... 147
4.7最大流 ................................................................................................... 149
4.7.1網(wǎng)絡(luò)流的基本概念 ........................................................................ 150
4.7.2 Ford-Fulkerson方法 ..................................................................... 151
4.8匹配 ....................................................................................................... 154
4.8.1二分圖和匹配的基本概念 .............................................................. 154
4.8.2匈牙利算法 .................................................................................. 155
4.8.3最大匹配與最大流 ........................................................................ 157
4.9本章小結(jié) ................................................................................................ 157