处理程序+资料结构=程式PDF电子书下载

第一章　基本资料结构 1

1.1 概论 1

目录 1

1.2 资料型态之概念 2

1.3 基本资料型态 3

表之部份 5

表1.1 Boalean运算表 5

第一章 5

1.4 标准基本型态 5

1.5 次范围型态 6

1.6 阵列结构 7

图1.1 Row之阵列图示 7

第一章 7

图之部份 7

图、表、程式目录 7

索引 7

程式之部份 9

第一章 9

程式1.1 计算2的负幂次方 9

1.7 记录结构 9

1.8 记录结构之转化 11

1.9 集合结构 12

1.10 阵列、记录、集合之表示 15

1.10.1　阵列表示方式 16

图1.3 使用“填塞”之记录图示 16

图1.2 阵列和储存设备之对应关系图 16

1.10.2　记录之表示 18

1.10.3　集合之表示 18

1.11 连续性的档案结构 18

1.11.1　基本档案运算子 19

1.11.2　有次级结构之档案 20

1.11.3　文体结构 21

程式1.2 输入—实数 22

程式1.3 输出—实数 24

1.11.4　一个档案编辑方式 27

第二章　排序法 33

2.1　概论 33

2.2 阵列之排序法 34

2.2.1　直接插入排序法 34

第二章 35

表2.1 直接插入排序法之处理图例 35

程式2.1 直接插入排序法之程式 35

第二章 35

程式2.2 二分插入排序法 36

表2.2 直接选择排序法之处理图例 37

2.2.2　直接选择排序法 37

程式2.3 直接选择排序法程式 38

程式2.4 气泡式的排序法程式 39

表2.3 气泡式的排序法之处理图例 39

2.2.3 直接交换排序法 39

程式2.5 摇动排序法之程式 40

表2.4　摇动排序法之处理图例 40

2.2.4 缩减间隔式之插入排序法 41

表2.5 缩减间隔式之插入排序法之处理图例 41

图2.1 两个KEY间之重覆选择 42

第二章 42

2.2.5　树式排序法 42

程式2.6 雪儿排序法（Shell sort） 42

图2.3　回填最小KEY之空间 43

图2.2 最小KEY之选择 43

图2.5 具有七个元素之堆积图示 44

图2.4 用阵列方式所表之二分树系 44

图2.6 KEY 44在堆积中移动之图示 44

表2.7 堆积排序法的处理图示 45

程式2.7 堆积之移动 45

表2.6 堆积之建造 45

程式2.8 堆积排序之程式 46

2.2.6　画分排序法 46

程式2.9 阵列之划分程式 47

2.2.7 找中间值 48

图2.7 标准值太小之图示 48

程式2.10 快速排序法之程式 48

图2.8 标准值太大之图示 49

图2.9 正确之标值之图示 49

程式2.11 寻找第K个元素之程式 50

表2.9 各种排序程式之执行时间此较表 50

表2.8 三种直接排序法的此较表 50

2.2.8 阵列排序法之此较 50

2.3.1　直接合并 51

2.3 连续性档案之排序法 51

图2.10　直接合并排序法之处理图示 52

程式2.12　直接合并排序法之程式 53

2.3.2 自然合并法 54

图2.11 自然合并排序法之处理图示 54

表2.10 自然合并排序法之实例 55

程式2.13 自然合并排序法之程式 55

2.3.3 平衡多路合并法 57

程式2.14 平衡合并排序法之程式 59

2.3.4　多相排序法 62

图2.12 使用3个磁带来处理21个串的资料多相排序法图示 62

表2.11 二个磁带的最佳资料串之分配表 63

表2.12 五个磁带的最佳资料串之分配表 63

图2.13 使用6个磁带处理65串资料的多相排序法图示 63

图2.14 水平分布法 65

程式2.15 多相排序法程式 67

2.3.5 起始串的分布 70

图2.15 在堆积中移动一个KEY之处理图示 71

程式2.16 堆积排序法之起始资料分配程式 72

第三章　循环式解题方法 77

3.1 介绍 77

第三章 77

图3.1 循环式图型 77

3.2 什么时候不需用循环 79

图3.2 n-5时Flb（n）之15次呼叫 81

3.3 循环程式的两个例子 82

图3.3 Hilbert曲线 82

图3.4 画面定义 83

第三章 84

程式3.1　Hilbert曲线 84

图3.5 H1～H5之Hilbert曲线 85

图3.7 Si……S4之Seierpinski曲线 86

图3.6 1阶和2阶之Sierpinski曲线 86

程式3.2 Sierpinski曲线 88

3.4 折返解题方法 89

图3.8 骑士可能移动之八个位置图 91

程式3.3 四骑士漫游 92

第三章 92

表3.1 骑士漫游的三个解 92

3.5　八个皇后的例题 94

图3.9 八皇后问题之一解 96

程式3.4 八皇后之程式 97

程式3.5 八皇后之程式 98

表3.2 八皇后问题之12解 99

3.6 稳定婚姻的例题 99

表3.3 稳定婚姻问题之输入资料 101

程式3.6 稳定婚姻程式 104

3.7 最佳选择例题 106

表3.4 稳定婚姻问题之结果 106

图3.10 Hanoi图示 108

表3.5 最佳化选择之输出范例 108

程式3.7 最佳化选择程式 109

图3.11 1至4阶之w—曲线 111

第四章　动态资料结构 113

4.1　循环式资料型式 113

表4.1 程式及资料结构的对应关系 113

第四章 113

第四章 115

图4.1 循环记录结构的贮存形式 115

4.2 指标或参数变数 115

图4.3 由指标连接的结构 116

图4.2 家谱结构 116

图4.4 变数p↑的动态分配 117

图4.5 含nil指标的结构 118

第四章 119

程式4.1 程式及资料结构的对应关系 119

4.3.1 基本运算 120

4.3 线性表 120

图4.6 列表例子 121

图4.7 在p↑之后列表的插入 122

图4.8 p↑前之列表插入 123

图4.9 列表之删除及再插入 123

4.3.2 有序列表及重组列表 124

图4.10 有序列表插入 127

图4.12 重排列后的列表 130

图4.11 重排列前的列表 130

表4.2 列表搜寻方法的此较 131

图4.13 部分排列集合 132

4.3.3　应用：拓扑分类 132

图4.14 用线性排列方式来表图4.13 133

图4.15 由拓扑分类程式所产生的列表结构 135

图4.16 无前位者、领头者的列表 136

程式4.2 拓扑分类程式 137

4.4.1 基本观念及定义 138

4.4 树系结构 138

图4.17 树系结构之套组集合（b）套组括弧（c）抬头式（d）图形的表示法 139

图4.18 两个不同的二元树系 140

图4.19 以特殊结点扩充之三元树系 141

图4.20 运算公式（a+b/c）*（d-e*f）之树系表示法 142

图4.21 树系之资料结构表示 143

图4.22 完全平衡树系（perfecfly balanced frees） 144

表4.3 树系由一列阵代表 144

程式4.3 架构完全平衡树系 145

图4.23 由程式4.3产生的树系 146

4.4.2 二元树系之基本运算 147

图4.24 二元树系 148

图4.25 有岗哨之搜寻树系 150

4.4.3 树之搜寻及插入 151

图4.26 有序二元树系之插入 152

图4.27 由程式4.4产生之搜寻树系 152

程式4.4 树系之搜寻及插入 153

程式4.5 相互参考产生器 156

表4.4 程式4.5的样品输出 159

4.4.4 树系的删除 160

图4.28 树系的删除 161

4.4.5　分折树系的搜寻及插入 162

图4.29 树系结点之此重分配图 162

4.4.6 平面树系 165

4.4.7 平衡树系之插入 166

图4.30 高为2.3及4之Fibonacei树系 166

图4.32 由插入产生的不平衡 167

图4.31 平衡树系 167

图4.33 重返平衡 168

图4.34 平衡树系之插入 169

4.4.8 平衡树系之删除 172

图4.35 平衡树系之删除 173

4.4.9 最佳搜寻树系 176

图4.36 三个结点之搜寻树系 176

图4.37 标出有关或然率的搜寻树系 178

图4.38 一个结点的最佳树系 180

4.4.10 树结构的显示 181

图4.39 由程式4.6得到的树系 182

图4.40 完全平衡树系 183

表4.5 键及发生的次数 184

图4.41 最佳搜寻树系 185

图4.42 仅考虑键的最佳树系 185

程式4.6 寻找最佳搜寻树系 186

程式4.7 B树系搜寻、插入及删除 189

4.5 多元树系 190

图4.43 一多元树系 191

图4.44 一分为许多页的二元树系 192

4.5.1 B—树系 192

图4.46 m个键的B树系页 193

图4.45 二级元的B树系 193

图4.47 在B树系中插入键22 194

图4.48 二级B树系之扩张 197

图4.49 二级B树系之衰减 198

4.5.2 二元B树系 204

图4.50 BB树系结点之表示 204

图4.51 BB树系结点插入 206

图4.52 SBB树系之插入 207

图4.53 以（4.85）顺序插入之树篱树系发展 208

4.6 键转换化法（混杂化法） 211

4.6.1 键转换函数（H）之选择 212

4.6.2 碰撞处理 212

程式4.8 使用键转换法之相互参考表之产生器 214

4.6.3　键转换法分析 217

表4.6 列出相对某一个负载因素α之平均探测E 219

表4.7 αE 220

图4.54 周期性列表 222

图4.55 双方向列表 222

5.1 语言定义及其结构 227

第五章　电脑语言之结构和其编译程式 227

5.2 语句分析 231

5.3 语法图形之建立 238

图5.1 列题五之语法辨认图形 241

第五章 241

图5.2 简化后的语法辨认图形 242

5.4 语法剖析程式建立 243

程式5.1 例题5之文法剖析程式 246

第五章 246

5.5 表格驱动式剖析程式之建立 248

图5.3 图5-2之资料结构表示图 251

5.6 将BNF转为剖析驱动式资料结构之转换程式 253

第五章 254

表5.1 BNF和EBNF符号之对照表 254

程式5.2 （5.13）式之剖析程式 255

程式5.3 （5.13）式之编译程式 258

5.7　PL 10语言之程式撰写 261

图5.4 PL/φ之语法图形 262

5.8　PL 10语言之剖析程式 265

表5.2 PL/O之起始和后继符号集合 266

程式5.4　PL/0 之剖析程式程式 268

图5.5 PL/0之关系图形 268

5.9 语法错误之复元处理 274

图5.6 修改后之复合程式指令语法 277

表5.3 PL/0编译程式所产生之错误讯息对照表 277

程式5.5 具有错误复元之PL/0剖析程式 281

5.10　PL10处理机 286

图5.7 PL/O处理之资料堆（stack）安排方式 288

5.11 机器码（CODF）之产生 288

图5.8 指令码之格式 289

表5.4 后缀表示式及中间表示式之对照表 290

程式5.6　PL/φ之编辑程式 292