《处理程序+资料结构=程式》求取 ⇩

第一章　基本资料结构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.13133

图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树系中插入键22194

图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 列出相对某一个负载因素α之平均探测E219

表4.7 αE220

图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