程序设计与数据结构

第1章 程序设计基础………………………………………………………………… 1

1.1 思想的力量 ……………………………………………………………………… 1

1.1.1 过程主题 …………………………………………………………………… 1

1.1.2 思维差异 …………………………………………………………………… 2

1.1.3 语言的鸿沟…………………………………………………………………… 3

1.2 变量与指针 ……………………………………………………………………… 12

1.2.1 变 量 ……………………………………………………………………… 12

1.2.2 值的表示形式 ……………………………………………………………… 16

1.2.3 数据的输入/输出 …………………………………………………………… 23

1.3 指针变量与指针的指针…………………………………………………………… 28

1.3.1 声明与访问 ………………………………………………………………… 28

1.3.2 变量的访问 ………………………………………………………………… 33

1.3.3 指针的指针 ………………………………………………………………… 36

1.4 简化表达式 ……………………………………………………………………… 38

1.4.1 逻辑表达式 ………………………………………………………………… 39

1.4.2 综合表达式 ………………………………………………………………… 40

1.4.3 条件表达式 ………………………………………………………………… 42

1.5 共性与可变性分析 ……………………………………………………………… 42

1.5.1 分析方法 …………………………………………………………………… 42

1.5.2 建立抽象 …………………………………………………………………… 44

1.5.3 建立接口 …………………………………………………………………… 44

1.5.4 实现接口 …………………………………………………………………… 48

1.5.5 使用接口 …………………………………………………………………… 50

1.6 数组与指针 ……………………………………………………………………… 51

1.6.1 数 组 ……………………………………………………………………… 51

1.6.2 数组的访问形式 …………………………………………………………… 57

1.6.3 泛型编程 …………………………………………………………………… 60

1.7 数组的数组与指针 ……………………………………………………………… 69

1.7.1 指向数组的指针 …………………………………………………………… 69

1.7.2 二维数组 …………………………………………………………………… 71

1.7.3 将二维数组作为函数参数 …………………………………………………… 73

1.8 字符串与指针 …………………………………………………………………… 77

1.8.1 字符常量 …………………………………………………………………… 77

1.8.2 字符串常量 ………………………………………………………………… 81

1.8.3 指针数组 …………………………………………………………………… 92

1.9 动态分配内存 …………………………………………………………………… 99

1.9.1 malloc()函数 ……………………………………………………………… 100

1.9.2 calloc()函数 ……………………………………………………………… 101

1.9.3 free()函数 ………………………………………………………………… 101

1.9.4 realloc()函数 ……………………………………………………………… 103

第2章 程序设计技术……………………………………………………………… 105

2.1 函数指针与指针函数 …………………………………………………………… 105

2.1.1 函数指针 …………………………………………………………………… 105

2.1.2 指针函数 …………………………………………………………………… 108

2.1.3 回调函数 …………………………………………………………………… 112

2.1.4 函数指针数组 ……………………………………………………………… 119

2.2 结构体 ………………………………………………………………………… 120

2.2.1 内存对齐 …………………………………………………………………… 121

2.2.2 内含基本数据类型 ………………………………………………………… 124

2.2.3 内置函数指针 ……………………………………………………………… 130

2.2.4 嵌套结构体 ………………………………………………………………… 134

2.2.5 结构体数组 ………………………………………………………………… 138

2.3 栈与函数返回…………………………………………………………………… 142

2.3.1 堆 栈 …………………………………………………………………… 142

2.3.2 入栈与出栈 ………………………………………………………………… 143

2.3.3 函数的调用与返回 ………………………………………………………… 144

2.4 栈 ADT ………………………………………………………………………… 146

2.4.1 不完全类型 ………………………………………………………………… 146

2.4.2 抽象数据类型 ……………………………………………………………… 150

2.4.3 开闭原则(OCP) …………………………………………………………… 160

第3章 算法与数据结构…………………………………………………………… 165

3.1 算法问题 ……………………………………………………………………… 165

3.1.1 排 序 …………………………………………………………………… 165

3.1.2 搜 索 …………………………………………………………………… 167

3.1.3 O 记法 …………………………………………………………………… 169

3.2 单向链表 ……………………………………………………………………… 175

3.2.1 存值与存址 ………………………………………………………………… 175

3.2.2 数据与p_next分离 ………………………………………………………… 184

3.2.3 接 口 …………………………………………………………………… 190

3.3 双向链表 ……………………………………………………………………… 201

3.3.1 添加结点 …………………………………………………………………… 205

3.3.2 删除结点 …………………………………………………………………… 208

3.3.3 遍历链表 …………………………………………………………………… 210

3.4 迭代器模式 …………………………………………………………………… 213

3.4.1 迭代器与容器 ……………………………………………………………… 213

3.4.2 迭代器接口 ………………………………………………………………… 214

3.4.3 算法的接口 ………………………………………………………………… 219

3.5 哈希表 ………………………………………………………………………… 225

3.5.1 问 题 …………………………………………………………………… 225

3.5.2 哈希表的类型 ……………………………………………………………… 229

3.5.3 哈希表的实现 ……………………………………………………………… 231

3.6 队列 ADT ……………………………………………………………………… 240

3.6.1 建立抽象 …………………………………………………………………… 240

3.6.2 建立接口 …………………………………………………………………… 240

3.6.3 实现与使用接口 …………………………………………………………… 243

第4章 面向对象编程……………………………………………………………… 252

4.1 OO 思想 ……………………………………………………………………… 252

4.1.1 职责转移 …………………………………………………………………… 252

4.1.2 OO 机制 …………………………………………………………………… 254

4.1.3 OO 收益 …………………………………………………………………… 255

4.2 类与对象 ……………………………………………………………………… 256

4.2.1 对 象 …………………………………………………………………… 256

4.2.2 类 ………………………………………………………………………… 258

4.2.3 封 装 …………………………………………………………………… 262

4.3 继承与多态 …………………………………………………………………… 268

4.3.1 抽 象 …………………………………………………………………… 268

4.3.2 继 承 …………………………………………………………………… 269

4.3.3 职责驱动设计 ……………………………………………………………… 272

4.3.4 多态性 …………………………………………………………………… 276

4.4 虚函数 ………………………………………………………………………… 279

4.4.1 二叉树 …………………………………………………………………… 279

4.4.2 表达式算术树 ……………………………………………………………… 280

4.4.3 虚函数 …………………………………………………………………… 288

4.5 状态机 ………………………………………………………………………… 292

4.5.1 有限状态机 ………………………………………………………………… 292

4.5.2 State模式 ………………………………………………………………… 296

4.5.3 动作类 …………………………………………………………………… 306

4.6 框架与重用 …………………………………………………………………… 308

4.6.1 框 架 …………………………………………………………………… 308

4.6.2 契 约 …………………………………………………………………… 309

4.6.3 建立契约 …………………………………………………………………… 310

4.6.4 框架与重构 ………………………………………………………………… 311

参 考 文 献…………………………………………………………………………… 313