数据结构与算法JavaScript描述.pdf

高清文字版，可复制
目录推荐序....................................................................................................................................................XI前言....................................................................................................................................................... XII第 1 章 JavaScript 的编程环境和模型........................................................................................11.1 JavaScript 环境...........................................................................................................................11.2 JavaScript 编程实践...................................................................................................................21.2.1 声明和初始化变量 ........................................................................................................31.2.2 JavaScript 中的算术运算和数学库函数.......................................................................31.2.3 判断结构 ........................................................................................................................41.2.4 循环结构 ........................................................................................................................61.2.5 函数 ................................................................................................................................71.2.6 变量作用域 ....................................................................................................................71.2.7 递归 ................................................................................................................................91.3 对象和面向对象编程...............................................................................................................101.4 小结...........................................................................................................................................11第 2 章 数组.......................................................................................................................................132.1 JavaScript 中对数组的定义.....................................................................................................132.2 使用数组...................................................................................................................................132.2.1 创建数组 ......................................................................................................................142.2.2 读写数组 ......................................................................................................................152.2.3 由字符串生成数组 ......................................................................................................152.2.4 对数组的整体性操作 ..................................................................................................162.3 存取函数...................................................................................................................................172.3.1 查找元素 ......................................................................................................................17VI ｜ 目录2.3.2 数组的字符串表示 ......................................................................................................182.3.3 由已有数组创建新数组 ..............................................................................................182.4 可变函数...................................................................................................................................192.4.1 为数组添加元素 ..........................................................................................................192.4.2 从数组中删除元素 ......................................................................................................202.4.3 从数组中间位置添加和删除元素 ..............................................................................212.4.4 为数组排序 ..................................................................................................................212.5 迭代器方法...............................................................................................................................222.5.1 不生成新数组的迭代器方法 ......................................................................................222.5.2 生成新数组的迭代器方法 ..........................................................................................252.6 二维和多维数组.......................................................................................................................272.6.1 创建二维数组 ..............................................................................................................272.6.2 处理二维数组的元素 ..................................................................................................282.6.3 参差不齐的数组 ..........................................................................................................292.7 对象数组...................................................................................................................................302.8 对象中的数组...........................................................................................................................312.9 练习...........................................................................................................................................32第 3 章 列表.......................................................................................................................................333.1 列表的抽象数据类型定义.......................................................................................................333.2 实现列表类...............................................................................................................................343.2.1 append：给列表添加元素...........................................................................................353.2.2 remove：从列表中删除元素.......................................................................................353.2.3 find：在列表中查找某一元素.....................................................................................353.2.4 length：列表中有多少个元素...................................................................................363.2.5 toString：显示列表中的元素...................................................................................363.2.6 insert：向列表中插入一个元素...............................................................................373.2.7 clear：清空列表中所有的元素.................................................................................373.2.8 contains：判断给定值是否在列表中.......................................................................373.2.9 遍历列表 ......................................................................................................................383.3 使用迭代器访问列表...............................................................................................................393.4 一个基于列表的应用...............................................................................................................403.4.1 读取文本文件 ..............................................................................................................403.4.2 使用列表管理影碟租赁 ..............................................................................................413.5 练习...........................................................................................................................................44第 4 章 栈...........................................................................................................................................454.1 对栈的操作...............................................................................................................................45目录 ｜ VII4.2 栈的实现...................................................................................................................................464.3 使用 Stack 类 ...........................................................................................................................484.3.1 数制间的相互转换 ......................................................................................................494.3.2 回文 ..............................................................................................................................504.3.3 递归演示 ......................................................................................................................514.4 练习...........................................................................................................................................52第 5 章 队列.......................................................................................................................................535.1 对队列的操作...........................................................................................................................535.2 一个用数组实现的队列...........................................................................................................545.3 使用队列：方块舞的舞伴分配问题.......................................................................................575.4 使用队列对数据进行排序.......................................................................................................615.5 优先队列...................................................................................................................................635.6 练习...........................................................................................................................................65第 6 章 链表.......................................................................................................................................676.1 数组的缺点...............................................................................................................................676.2 定义链表...................................................................................................................................676.3 设计一个基于对象的链表.......................................................................................................696.3.1 Node 类..........................................................................................................................696.3.2 LinkedList 类..............................................................................................................696.3.3 插入新节点 ..................................................................................................................696.3.4 从链表中删除一个节点 ..............................................................................................716.4 双向链表...................................................................................................................................746.5 循环链表...................................................................................................................................786.6 链表的其他方法.......................................................................................................................796.7 练习...........................................................................................................................................79第 7 章 字典.......................................................................................................................................817.1 Dictionary 类...........................................................................................................................817.2 Dictionary 类的辅助方法.......................................................................................................837.3 为 Dictionary 类添加排序功能..............................................................................................857.4 练习...........................................................................................................................................86第 8 章 散列.......................................................................................................................................878.1 散列概览...................................................................................................................................878.2 HashTable 类.............................................................................................................................888.2.1 选择一个散列函数 ......................................................................................................888.2.2 一个更好的散列函数 ..................................................................................................91VIII ｜ 目录8.2.3 散列化整型键 ..............................................................................................................938.2.4 对散列表排序、从散列表中取值 ..............................................................................958.3 碰撞处理...................................................................................................................................968.3.1 开链法 ..........................................................................................................................968.3.2 线性探测法 ..................................................................................................................998.4 练习.........................................................................................................................................100第 9 章 集合.....................................................................................................................................1019.1 集合的定义、操作和属性.....................................................................................................1019.1.1 集合的定义 ................................................................................................................1019.1.2 对集合的操作 ............................................................................................................1029.2 Set 类的实现..........................................................................................................................1029.3 更多集合操作.........................................................................................................................1049.4 练习.........................................................................................................................................107第 10 章 二叉树和二叉查找树...................................................................................................10910.1 树的定义...............................................................................................................................10910.2 二叉树和二叉查找树...........................................................................................................11110.2.1 实现二叉查找树..................................................................................................... 11110.2.2 遍历二叉查找树.....................................................................................................11310.3 在二叉查找树上进行查找...................................................................................................11610.3.1 查找最小值和最大值.............................................................................................11610.3.2 查找给定值.............................................................................................................11710.4 从二叉查找树上删除节点...................................................................................................11810.5 计数.......................................................................................................................................12010.6 练习.......................................................................................................................................123第 11 章 图和图算法.....................................................................................................................12511.1 图的定义...............................................................................................................................12511.2 用图对现实中的系统建模...................................................................................................12711.3 图类.......................................................................................................................................12711.3.1 表示顶点.................................................................................................................12711.3.2 表示边.....................................................................................................................12711.3.3 构建图.....................................................................................................................12811.4 搜索图...................................................................................................................................13011.4.1 深度优先搜索.........................................................................................................13011.4.2 广度优先搜索.........................................................................................................13311.5 查找最短路径.......................................................................................................................13511.5.1 广度优先搜索对应的最短路径.............................................................................135目录 ｜ IX11.5.2 确定路径.................................................................................................................13511.6 拓扑排序...............................................................................................................................13711.6.1 拓扑排序算法.........................................................................................................13711.6.2 实现拓扑排序算法.................................................................................................13711.7 练习.......................................................................................................................................141第 12 章 排序算法.........................................................................................................................14312.1 数组测试平台.......................................................................................................................14312.2 基本排序算法.......................................................................................................................14512.2.1 冒泡排序.................................................................................................................14512.2.2 选择排序.................................................................................................................14812.2.3 插入排序.................................................................................................................15012.2.4 基本排序算法的计时比较.....................................................................................15112.3 高级排序算法.......................................................................................................................15312.3.1 希尔排序.................................................................................................................15312.3.2 归并排序.................................................................................................................15812.3.3 快速排序.................................................................................................................16312.4 练习.......................................................................................................................................167第 13 章 检索算法.........................................................................................................................16913.1 顺序查找...............................................................................................................................16913.1.1 查找最小值和最大值.............................................................................................17213.1.2 使用自组织数据.....................................................................................................17513.2 二分查找算法.......................................................................................................................17713.3 查找文本数据.......................................................................................................................18313.4 练习.......................................................................................................................................185第 14 章 高级算法.........................................................................................................................18714.1 动态规划...............................................................................................................................18714.1.1 动态规划实例：计算斐波那契数列.....................................................................18814.1.2 寻找最长公共子串.................................................................................................19114.1.3 背包问题：递归解决方案.....................................................................................19414.1.4 背包问题：动态规划方案.....................................................................................19514.2 贪心算法...............................................................................................................................19614.2.1 第一个贪心算法案例：找零问题.........................................................................19614.2.2 背包问题的贪心算法解决方案.............................................................................19714.3 练习.......................................................................................................................................199封面介绍..............................................................................................................................................200