括号匹配的原理_判断括号是否匹配的算法

数据结构与算法——栈的应用括号匹配 　　目 录 　　译者序 　　前言 　　第一部分 预备知识 　　第1章 C++程序设计 　　1 　　1.1 引言 　　1 　　1.2 函数与参数 　　2 　　1.2.1 传值参数 　　2 　　1.2.2 模板函数 　　3 　　1.2.3 引用参数 　　3 　　1.2.4 常量引用参数 　　4 　　1.2.5 返回值 4 　　1.2.6 递归函数 5 　　1.3 动态存储分配 9 　　1.3.1 操作符new 9 　　1.3.2 一维数组 9 　　1.3.3 异常处理 10 　　1.3.4 操作符delete 10 　　1.3.5 二维数组 10 　　1.4 类 13 　　1.4.1 类Currency 13 　　1.4.2 使用不同的描述方法 18 　　1.4.3 操作符重载 20 　　1.4.4 引发异常 22 　　1.4.5 友和保护类成员 23 　　1.4.6 增加#ifndef, #define和#endif语句 24 　　1.5 测试与调试 24 　　1.5.1 什么是测试 24 　　1.5.2 设计测试数据 26 　　1.5.3 调试 28 　　1.6 参考及推荐读物 29 　　第2章 程序性能 30 　　2.1 引言 30 　　2.2 空间复杂性 31 　　2.2.1 空间复杂性的组成 31 　　2.2.2 举例 35 　　2.3 时间复杂性 37 　　2.3.1 时间复杂性的组成 37 　　2.3.2 操作计数 37 　　2.3.3 执行步数 44 　　2.4 渐进符号（O、 健?、 o） 55 　　2.4.1 大写O符号 56 　　2.4.2 椒?58 　　2.4.3 符号 59 　　2.4.4 小写o符号 60 　　2.4.5 特性 60 　　2.4.6 复杂性分析举例 61 　　2.5 实际复杂性 66 　　2.6 性能测量 68 　　2.6.1 选择实例的大小 69 　　2.6.2 设计测试数据 69 　　2.6.3 进行实验 69 　　2.7 参考及推荐读物 74 　　第二部分 数据结构 　　第3章 数据描述 75 　　3.1 引言 75 　　3.2 线性表 76 　　3.3 公式化描述 77 　　3.3.1 基本概念 77 　　3.3.2 异常类NoMem 79 　　3.3.3 操作 79 　　3.3.4 评价 83 　　3.4 链表描述 86 　　3.4.1 类ChainNode 和Chain 86 　　3.4.2 操作 88 　　3.4.3 扩充类Chain 91 　　3.4.4 链表遍历器类 92 　　3.4.5 循环链表 93 　　3.4.6 与公式化描述方法的比较 94 　　3.4.7 双向链表 95 　　3.4.8 小结 96 　　3.5 间接寻址 99 　　3.5.1 基本概念 99 　　3.5.2 操作 100 　　3.6 模拟指针 102 　　3.6.1 SimSpace的操作 103 　　3.6.2 采用模拟指针的链表 106 　　3.7 描述方法的比较 110 　　3.8 应用 111 　　3.8.1 箱子排序 111 　　3.8.2 基数排序 116 　　3.8.3 等价类 117 　　3.8.4 凸包 122 　　3.9 参考及推荐读物 127 　　第4章 数组和矩阵 128 　　4.1 数组 128 　　4.1.1 抽象数据类型 128 　　4.1.2 C++数组 129 　　4.1.3 行主映射和列主映射 129 　　4.1.4 类Array1D 131 　　4.1.5 类Array2D 133 　　4.2 矩阵 137 　　4.2.1 定义和操作 137 　　4.2.2 类Matrix 138 　　4.3 特殊矩阵 141 　　4.3.1 定义和应用 141 　　4.3.2 对角矩阵 143 　　4.3.3 三对角矩阵 144 　　4.3.4 三角矩阵 145 　　4.3.5 对称矩阵 146 　　4.4 稀疏矩阵 149 　　4.4.1 基本概念 149 　　4.4.2 数组描述 149 　　4.4.3 链表描述 154 　　第5章 堆栈 161 　　5.1 抽象数据类型 161 　　5.2 派生类和继承 162 　　5.3 公式化描述 163 　　5.3.1 Stack的效率 164 　　5.3.2 自定义Stack 164 　　5.4 链表描述 166 　　5.5 应用 169 　　5.5.1 括号匹配 169 　　5.5.2 汉诺塔 170 　　5.5.3 火车车厢重排 172 　　5.5.4 开关盒布线 176 　　5.5.5 离线等价类问题 178 　　5.5.6 迷宫老鼠 180 　　5.6 参考及推荐读物 188 　　第6章 队列 189 　　6.1 抽象数据类型 189 　　6.2 公式化描述 190 　　6.3 链表描述 194 　　6.4 应用 197 　　6.4.1 火车车厢重排 197 　　6.4.2 电路布线 201 　　6.4.3 识别图 204 　　6.4.4 工厂仿真 206 　　6.5 参考及推荐读物 217 　　第7章 跳表和散列 218 　　7.1 字典 218 　　7.2 线性表描述 219 　　7.3 跳表描述 222 　　7.3.1 理想情况 222 　　7.3.2 插入和删除 223 　　7.3.3 级的分配 224 　　7.3.4 类SkipNode 224 　　7.3.5 类SkipList 225 　　7.3.6 复杂性 229 　　7.4 散列表描述 229 　　7.4.1 理想散列 229 　　7.4.2 线性开型寻址散列 230 　　7.4.3 链表散列 234 　　7.5 应用——文本压缩 238 　　7.5.1 LZW压缩 239 　　7.5.2 LZW压缩的实现 239 　　7.5.3 LZW解压缩 243 　　7.5.4 LZW解压缩的实现 243 　　7.6 参考及推荐读物 247 　　第8章 二叉树和其他树 248 　　8.1 树 248 　　8.2 二叉树 251 　　8.3 二叉树的特性 252 　　8.4 二叉树描述 253 　　8.4.1 公式化描述 253 　　8.4.2 链表描述 254 　　8.5 二叉树常用操作 256 　　8.6 二叉树遍历 256 　　8.7 抽象数据类型BinaryTree 259 　　8.8 类BinaryTree 260 　　8.9 抽象数据类型及类的扩充 263 　　8.9.1 输出 263 　　8.9.2 删除 264 　　8.9.3 计算高度 264 　　8.9.4 统计节点数 265 　　8.10 应用 265 　　8.10.1 设置信号放大器 265 　　8.10.2 在线等价类 268 　　8.11 参考及推荐读物 275 　　第9章 优先队列 276 　　9.1 引言 276 　　9.2 线性表 277 　　9.3 堆 278 　　9.3.1 定义 278 　　9.3.2 最大堆的插入 279 　　9.3.3 最大堆的删除 279 　　9.3.4 最大堆的初始化 280 　　9.3.5 类MaxHeap 281 　　9.4 左高树 285 　　9.4.1 高度与宽度优先的最大及最小 　　左高树 285 　　9.4.2 最大HBLT的插入 287 　　9.4.3 最大HBLT的删除 287 　　9.4.4 合并两棵最大HBLT 287 　　9.4.5 初始化最大HBLT 289 　　9.4.6 类MaxHBLT 289 　　9.5 应用 293 　　9.5.1 堆排序 293 　　9.5.2 机器调度 294 　　9.5.3 霍夫曼编码 297 　　9.6 参考及推荐读物 302 　　第10章 竞?303 　　10.1 引言 303 　　10.2 抽象数据类型WinnerTree 306 　　10.3 类WinnerTree 307 　　10.3.1 定义 307 　　10.3.2 类定义 307 　　10.3.3 构造函数、析构函数及Winner 　　函数 308 　　10.3.4 初始化赢者树 308 　　10.3.5 重新组织比赛 310 　　10.4 输者树 311 　　10.5 应用 312 　　10.5.1 用最先匹配法求解箱子装载 　　问题 312 　　10.5.2 用相邻匹配法求解箱子装载 　　问题 316 　　第11章 搜索树 319 　　11.1 二叉搜索树 320 　　11.1.1 基本概念 320 　　11.1.2 抽象数据类型BSTree和 　　IndexedBSTree 321 　　11.1.3 类BSTree 322 　　11.1.4 搜索 322 　　11.1.5 插入 323 　　11.1.6 删除 324 　　11.1.7 类DBSTree 326 　　11.1.8 二叉搜索树的高度 327 　　11.2 AVL树 328 　　11.2.1 基本概念 328 　　11.2.2 AVL树的高度 328 　　11.2.3 AVL树的描述 329 　　11.2.4 AVL搜索树的搜索 329 　　11.2.5 AVL搜索树的插入 329 　　11.2.6 AVL搜索树的删除 332 　　11.3 红－黑树 334 　　11.3.1 基本概念 334 　　11.3.2 红－黑树的描述 336 　　11.3.3 红－黑树的搜索 336 　　11.3.4 红－黑树的插入 336 　　11.3.5 红－黑树的删除 339 　　11.3.6 实现细节的考虑及复杂性分析 343 　　11.4 B－树 344 　　11.4.1 索引顺序访问方法 344 　　11.4.2 m 叉搜索树 345 　　11.4.3 m 序B－树 346 　　11.4.4 B－树的高度 347 　　11.4.5 B－树的搜索 348 　　11.4.6 B－树的插入 348 　　11.4.7 B－树的删除 350 　　11.4.8 节点结构 353 　　11.5 应用 354 　　11.5.1 直方图 354 　　11.5.2 用最优匹配法求解箱子装载 　　问题 357 　　11.5.3 交叉分布 359 　　11.6 参考及推荐读物 363 　　第12章 图 365 　　12.1 基本概念 365 　　12.2 应用 366 　　12.3 特性 368 　　12.4 抽象数据类型Graph和Digraph 370 　　12.5 无向图和有向图的描述 371 　　12.5.1 邻接矩阵 371 　　12.5.2 邻接压缩表 373 　　12.5.3 邻接链表 374 　　12.6 网络描述 375 　　12.7 类定义 376 　　12.7.1 不同的类 376 　　12.7.2 邻接矩阵类 377 　　12.7.3 扩充Chain类 380 　　12.7.4 类LinkedBase 381 　　12.7.5 链接类 382 　　12.8 图的遍历 386 　　12.8.1 基本概念 386 　　12.8.2 邻接矩阵的遍历函数 387 　　12.8.3 邻接链表的遍历函数 388 　　12.9 语言特性 389 　　12.9.1 虚函数和多态性 389 　　12.9.2 纯虚函数和抽象类 391 　　12.9.3 虚基类 391 　　12.9.4 抽象类和抽象数据类型 393 　　12.10 图的搜索算法 394 　　12.10.1 宽度优先搜索 394 　　12.10.2 类Network 395 　　12.10.3 BFS的实现 395 　　12.10.4 BFS的复杂性分析 396 　　12.10.5 深度优先搜索 397 　　12.11 应用 399 　　12.11.1 寻找路径 399 　　12.11.2 连通图及其构件 400 　　12.11.3 生成树 402 　　第三部分 算法设计方法 　　第13章 贪婪算法 405 　　13.1 最优化问题 405 　　13.2 算法思想 406 　　13.3 应用 409 　　13.3.1 货箱装船 409 　　13.3.2 0/1背包问题 410 　　13.3.3 拓扑排序 412 　　13.3.4 二分覆盖 415 　　13.3.5 单源最短路径 421 　　13.3.6 最小耗费生成树 424 　　13.4 参考及推荐读物 433 　　第14章 分而治之算法 434 　　14.1 算法思想 434 　　14.2 应用 440 　　14.2.1 残缺棋盘 440 　　14.2.2 归并排序 443 　　14.2.3 快速排序 447 　　14.2.4 选择 452 　　14.2.5 距离最近的点对 454 　　14.3 解递归方程 462 　　14.4 复杂性的下限 463 　　14.4.1 最小最大问题的下限 464 　　14.4.2 排序算法的下限 465 　　第15章 动态规划 467 　　15.1 算法思想 467 　　15.2 应用 469 　　15.2.1 0/1背包问题 469 　　15.2.2 图像压缩 471 　　15.2.3 矩阵乘法链 476 　　15.2.4 最短路径 480 　　15.2.5 网络的无交叉子集 483 　　15.2.6 件折叠 486 　　15.3 参考及推荐读物 491 　　第16章 回溯 492 　　16.1 算法思想 492 　　16.2 应用 496 　　16.2.1 货箱装船 496 　　16.2.2 0/1背包问题 503 　　16.2.3 最大完备子图 506 　　16.2.4 旅行商问题 508 　　16.2.5 电路板排列 510 　　第17章 分枝定界 516 　　17.1 算法思想 516 　　17.2 应用 519 　　17.2.1 货箱装船 519 　　17.2.2 0/1背包问题 526 　　17.2.3 最大完备子图 528 　　17.2.4 旅行商问题 529 　　17.2.5 电路板排列 532