前辅文
第1章 绪论
1.1 算法实现
算法0-0：求两个正整数的最大公约数GCD(x, y)
算法1-1：求数组与整数乘积的最大值 MaxProduct1(array, m)
算法1-2：求数组与整数乘积的最大值 MaxProduct2(array, m)
算法1-3：将数组中元素反转存放 ReverseArray1(array)
算法1-4：将数组中元素反转存放 ReverseArray2(array)
算法1-5：计算1～n2的和加上1～n的和 SumUp(n)
算法1-6：计算1～n与1～m每一项相互乘积的和SumProducts(n, m)
算法1-7：连续子序列最大和的O(n3)算法MaxSubsequenceSum1(s)
算法1-8：连续子序列最大和的O(n2)算法 MaxSubsequenceSum2(s)
算法1-9：连续子序列最大和的O(n)算法 MaxSubsequenceSum3(s)
算法1-10：输出1～n的递归算法 RecursivePrint(n)
算法1-11：输出1～n的循环算法 IterativePrint(n)
1.2 基础练习
练习1-1 二分查找
练习1-2 两枚硬币
1.3 进阶实验
实验1-1 有序数组的插入
实验1-2 爆气球
第2章 线性表
2.1 算法实现
算法2-1：在顺序表list中查找元素x Search(list, x)
算法2-2：在顺序表list的第i个位置上插入元素x Insert(list, i, x)
算法2-3：从顺序表list中删除第i个元素 Remove(list, i)
算法2-4：求单链表list中的元素个数，即表长 Length(list)
算法2-5：返回单链表list中第i个元素的值 Get(list, i)
算法2-6：在单链表list中查找元素x所在的结点 Search(list, x)
算法2-7：在单链表list的第i个位置上插入元素x Insert(list, i, x)
算法2-8：从单链表list中删除第i个元素 Remove(list, i)
算法2-9：一元多项式加法运算 PolynomialAdd(p1, p2)
算法2-10：大整数加法运算 BigIntAdd(a, b)
算法2-11：大整数乘法运算 BigIntMultiply(a, b)
2.2 基础练习
练习2-1 带空头结点的单链表操作
练习2-2 线性表循环右移
练习2-3 一元多项式求导
练习2-4 最长连续递增子序列
2.3 进阶实验
实验2-1 求链式线性表的倒数第m项
实验2-2 一元多项式的乘法运算
实验2-3 线性表元素的区间删除
实验2-4 单链表分段逆转
*实验2-5 约瑟夫问题
*实验2-6 判断两个广义表是否相等
*实验2-7 稀疏矩阵的链式结构构建
第3章 栈与队列
3.1 算法实现
算法3-1：顺序栈的入栈操作 Push(stack, x)
算法3-2：顺序栈的取顶操作 Top(stack)
算法3-3：顺序栈的出栈操作 Pop(stack)
算法3-4：链式栈的入栈操作 Push(stack, x)
算法3-5：链式栈的取顶操作 Top(stack)
算法3-6：链式栈的出栈操作 Pop(stack)
算法3-7：顺序存储的循环队列的入队操作 EnQueue(queue, x)
算法3-8：顺序存储的循环队列的查看队首操作 GetFront(queue)
算法3-9：顺序存储的循环队列的出队操作 DeQueue(queue)
算法3-10：链式队列的入队操作 EnQueue(queue, x)
算法3-11：链式队列的查看队首操作 GetFront(queue)
算法3-12：链式队列的出队操作 DeQueue(queue)
算法3-13：后缀表达式求值 PostFixEval(expr)
算法3-14：阶乘的递归实现 Factorial(n)
算法3-15：火车车厢重排 TrainCarriageScheduling(in_track, out_track, n, k)
3.2 基础练习
练习3-1 仅有头指针的队列
练习3-2 栈操作的合法性
练习3-3 用两个栈实现队列
*练习3-4 符号配对
3.3 进阶实验
实验3-1 在一个数组中实现两个栈
实验3-2 出栈序列的合法性
实验3-3 简单计算器
实验3-4 取行李
实验3-5 双端队列
*实验3-6 滑动窗口的极值
第4章 字符串
4.1 算法实现
算法4-1：顺序存储字符串的插入操作StrInsert(s, pos, t)
算法4-2：顺序存储字符串的删除操作StrRemove(s, pos, len)
算法4-3：顺序存储字符串的截取子串操作 SubString(s, pos, len)
算法4-4：顺序存储字符串的连接操作 StrConcat(s, t)
算法4-5：顺序存储字符串的比较操作 StrCompare(s, t)
算法4-6：链式存储字符串的插入操作StrInsert(s, pos, t)
算法4-7：链式存储字符串的删除操作 StrRemove(s, pos, len)
算法4-8：链式存储字符串的截取子串操作 SubString(s, pos, len)
算法4-9：链式存储字符串的连接操作 StrConcat(s, t)
算法4-10：链式存储字符串的比较操作 StrCompare(s, t)
算法4-11：朴素字符串模式匹配算法 PatternMatchBF(s, t)
算法4-12：字符串替换算法 Replace(s, sub_s, t)
算法4-13：求解字符串t的next数组 GetNext(t, next)
算法4-14：字符串模式匹配的KMP算法 PatternMatchKMP(s, t)
算法4-15：字符串模式匹配的KR算法 PatternMatchKR(s, t)
算法4-16：字符串模式匹配的Sunday算法 PatternMatchSunday(s, t)
4.2 基础练习
练习4-1 字符串匹配算法比较
练习4-2 剪切粘贴
4.3 进阶实验
实验4-1 吃火锅
实验4-2 猜近似数字
实验4-3 出院
第5章 树与二叉树
5.1 算法实现
算法5-1：构造二叉树 CreateBinaryTree(value, left_tree, right_tree)
算法5-2：前序遍历二叉树 PreOrder(tree)
算法5-3：中序遍历二叉树 InOrder(tree)
算法5-4：后序遍历二叉树 PostOrder(tree)
算法5-5：计算二叉树高度 Height(tree)
算法5-6：将表达式树转换成中缀表达式 PrintInfixExpression(tree)
算法5-7：非递归前序遍历二叉树 PreOrder(tree)
算法5-8：非递归中序遍历二叉树 InOrder(tree)
算法5-9：非递归后序遍历二叉树 PostOrder(tree)
算法5-10：层序遍历二叉树 LevelOrder(tree)
算法5-11：二叉树前序序列化 PreOrderSerialize(tree)
算法5-12：根据前序序列重构二叉树 PreOrderDeSerialize( preorder, n)
算法5-13：二叉树层序序列化 LevelOrderSerialize(tree)
算法5-14：根据层序序列重构二叉树 LevelOrderDeSerialize(levelorder, n)
算法5-15：创建Huffman树 CreateHuffmanTree(w)
算法5-16：对二进制字符串解码 Decoding(tree, binary_code)
算法5-17：查找根结点 FindRoot(tree, x)
算法5-18：查找树中带有指定数据的结点 Search(tree, x)
算法5-19：前序遍历树 PreOrder(tree)
算法5-20：后序遍历树 PostOrder(tree)
算法5-21：创建Trie树结点 CreateTrieNode(k)
算法5-22：Trie树中插入字符串 Insert(trie, k, s)
算法5-23：判断给定字符串是否在Trie树中 IsIn(trie, k, s)
算法5-24：构建后缀树BuildSuffixTree(s, k)
5.2 基础练习
练习5-1 顺序存储的二叉树的遍历
练习5-2 列出叶结点
练习5-3 还原二叉树
*练习5-4 转换树的表示法
5.3 进阶实验
实验5-1 树的同构
实验5-2 树的宽度
实验5-3 二叉树直径
实验5-4 根据后序和中序遍历输出前序遍历
实验5-5 顺序存储的二叉树的最近公共祖先问题
*实验5-6 修理牧场
*实验5-7 家谱处理
*实验5-8 我爱背单词
第6章 优先级队列
6.1 算法实现
算法6-1：二叉堆的上调操作 SiftUp(h, i)
算法6-2：二叉堆的下调操作 SiftDown(h, i)
算法6-3：二叉堆的插入操作 Insert(h, x)
算法6-4：二叉堆的删顶操作 ExtractMin(h)
算法6-5：二叉堆的朴素建堆操作 MakeHeapUp(h)
算法6-6：二叉堆的快速建堆操作 MakeHeapDown(h)
算法6-7：多叉堆的上调操作 SiftUpD(h, d, i)
算法6-8：多叉堆的下调操作 SiftDownD(h, d, i)
算法6-9：左堆的合并操作 LeftistMerge(h1, h2)
算法6-10：斜堆的合并操作 SkewMerge(h1, h2)
6.2 基础练习
练习6-1 堆中的路径
练习6-2 Huffman树的实现
6.3 进阶实验
实验6-1 是不是堆
实验6-2 关于堆的判断
实验6-3 Windows消息队列
实验6-4 D度完全树
*实验6-5 对顶堆维护中位数
*实验6-6 堆的合并操作比较
第7章 图
7.1 算法实现
算法7-1：获取图的顶点个数 NumberOfVerts(graph)
算法7-2：判断边是否存在 ExistEdge(graph, u, v)
算法7-3：找顶点的第一个邻接顶点 FirstAdjVert(graph, v)
算法7-4：向图中插入边 InsertEdge(graph, u, v, weight)
算法7-5：从图中删除边 RemoveEdge(graph, u, v)
算法7-6：从图中删除顶点及所有邻接于该顶点的边 RemoveVert(graph, v)
算法7-7：返回图中顶点的第一个邻接顶点 FirstAdjVert(graph, v)
算法7-8：判断边是否存在 ExistEdge(graph, u, v)
算法7-9：向图中插入边 InsertEdge(graph, u, v, weight)
算法7-10：从图中删除顶点及所有邻接于该顶点的边 RemoveVert(graph, v)
算法7-11：深度优先遍历图中顶点 DFS(graph)
算法7-12：从指定顶点开始深度优先遍历 DFSv(graph, v, visited)
算法7-13：广度优先遍历图中顶点 BFS(graph)
算法7-14：从指定顶点开始广度优先遍历 BFSv(graph, v, visited)
算法7-15：图的连通性判断 IsConnected(graph)
算法7-16：验证六度空间理论SixDegreesOfSeparation(graph, v)
算法7-17：获取图的强连通分量 StronglyConnectedComponents(graph)
算法7-18：后序深度优先遍历记录顶点 PostOrderDFS(graph, v, visited, dfs_seq, dfs_num)
算法7-19：后序深度优先遍历输出顶点 PrintV(graph, v, visited)
算法7-20：从给定顶点出发获得一条回路 GetCircuit(graph, start)
算法7-21：求欧拉回路 EulerCircle(graph)
算法7-22：利用深度优先遍历计算dfn和low的值 DfnAndLow(graph, v, parent)
算法7-23：求割点的Tarjan算法 ArticulationPoint(graph, start)
算法7-24：求割边的Tarjan算法 ArticulationEdge(graph, start)
7.2 基础练习
练习7-1 哥尼斯堡七桥问题
练习7-2 判断两点是否连通
练习7-3 判断广度优先遍历序列
7.3 进阶实验
实验7-1 Hamilton回路
实验7-2 列出连通集
实验7-3 诈骗电话检测
实验7-4 是否有回路
实验7-5 社交网络图中顶点的“重要性”计算
第8章 图应用
8.1 算法实现
算法8-1：求单源最短路径的Dijkstra算法 Dijkstra(graph, s, path, dist)
算法8-2：求单源最短路径的Bellman-Ford算法 BellmanFord(graph, s, dist)
算法8-3：求所有点对间最短路径的Floyd-Warshall算法 Floyd Warshall(graph, path, dist)
算法8-4：求最小生成树的Prim算法 Prim(graph)
算法8-5：拓扑排序 TopSort(graph, top_s)
算法8-6：求图中关键活动 CriticalAnalysis(graph)
算法8-7：求解二部图最大匹配的匈牙利算法 MaximumMatch(bigraph, match)
算法8-8：找二部图匹配的增广路径 FindAugmentingPath(bigraph, match, u, visited)
8.2 基础练习
练习8-1 旅游规划
练习8-2 哈利·波特的考试
练习8-3 公路村村通
练习8-4 任务调度的合理性
8.3 进阶实验
实验8-1 城市间紧急救援
实验8-2 最短路径的交点
实验8-3 打怪升级
实验8-4 最小生成树的唯一性
*实验8-5 拆积木
*实验8-6 爱之匹配
第9章 不相交集
9.1 算法实现
算法9-1：初始化不相交集 InitSet(set, n)
算法9-2：查找元素所在的集合 Find(set, x)
算法9-3：合并两个元素所在的集合 Union(set, x, y)
算法9-4：初始化采用按秩合并策略的不相交集 InitSet(set, n)
算法9-5：利用按秩合并策略合并两个元素所在的集合 Union(set, x, y)
算法9-6：以路径压缩策略查找元素所在的集合Find(set, x)
算法9-7：Tarjan算法求解最近公共祖先 LCA(P, u, set, ancestor, visited)
9.2 基础练习
练习9-1 文件传输
*练习9-2 团结就是力量
9.3 进阶实验
实验9-1 部落
*实验9-2 两个序列的故事
第10章 内排序
10.1 算法实现
算法10-1：插入排序 InsertionSort(a, l, r)
算法10-2：Shell排序 ShellSort(a, l, r)
算法10-3：简单选择排序 SelectionSort(a, l, r)
算法10-4：堆排序 HeapSort(a, l, r)
算法10-5：冒泡排序 BubbleSort(a, l, r)
算法10-6：序列拆分 Partition(a, l, r)
算法10-7：快速排序 QuickSort(a, l, r)
算法10-8：二路归并 TwoWayMerge(a, l_x, r_x, l_y, r_y)
算法10-9：归并排序 MergeSort(a, l, r)
算法10-10：自底向上的归并排序 MergeSortBottomUp(a, l, r)
算法10-11：改进的二路归并 TwoWayMergeImproved(a, t, l, m, r)
算法10-12：改进的自底向上归并排序 MergeSortBottomUpImproved(a, l, r)
算法10-13：二路归并求逆序对减量 TwoWayInversionCount(a, l, m, r)
算法10-14：归并排序兼求逆序对数量 InversionCount(a, l, r)
算法10-15：计数排序 CountingSort(a, l, r, k)
算法10-16：基数排序中使用的计数排序 CountingSort2(a, l, r, radix, k, d)
算法10-17：MSD基数排序 MSDRadixSort(a, l, r, radix, k, d)
算法10-18：LSD基数排序 LSDRadixSort(a, l, r, radix, d)
算法10-19：基于插入排序的索引排序 IndexedInsertionSort(a, idx, l, r)
算法10-20：元素顺序调整 ElementAdjust(a, idx, l, r)
算法10-21：内省排序 IntroSort(a, l, r, d)
算法10-22：Tim排序 TimSort(a, l, r)
10.2 基础练习
练习10-1 排序
练习10-2 正负数分类
练习10-3 模拟Excel排序
练习10-4 插入排序还是归并排序
练习10-5 与零交换
10.3 进阶实验
实验10-1 分类排序
实验10-2 德才论
实验10-3 插入排序还是堆排序
实验10-4 统计工龄
实验10-5 清点代码库
第11章 查找
11.1 算法实现
算法11-1：顺序表的顺序查找 SequentialSearch(record, n, key)
算法11-2：二分查找 BinarySearch(record, low, high, key)
算法11-3：索引表的顺序查找 IndexSequentialSearch(record, idx, m, l, key)
算法11-4：二叉查找树的查找 SearchBST(bstree, key)
算法11-5：二叉查找树的插入 InsertBST(bstree, x)
算法11-6：二叉查找树的删除 DeleteBST(bstree, key)
算法11-7：AVL树的插入 InsertAVL(tree, x)
算法11-8：AVL树的左单旋转（RR型） RRSingleRotation(root)
算法11-9：AVL树的先左后右双向旋转(LR型） LRDoubleRotation(root)
算法11-10：英文字典的散列 StringHash(string, table_size)
算法11-11：开放定址法散列查找 SearchHash(htable, key)
算法11-12：开放定址法散列插入 InsertHash(htable, x)
11.2 基础练习
练习11-1 垃圾分类
练习11-2 是否二叉查找树
练习11-3 AVL树的根
练习11-4 整型关键字的散列映射
11.3 进阶实验
实验11-1 集合相似度
实验11-2 查找树判断
实验11-3 树种统计
*实验11-4 笛卡儿树
*实验11-5 新浪微博热门话题
第12章 高级查找
12.1 算法实现
算法12-1：构建最小值线段树BuildSegTree(seg_tree, array, l, r, p)
算法12-2：求最小值线段树的单点更新 Update(seg_tree, l, r, p, idx, value)
算法12-3：求最小值线段树的区间查询 Query(seg_tree, l, r, p, ql, qr)
算法12-4：求最小值线段树的区间增值更新 RangeUpdate(seg_tree, lazy, l, r, p, ql, qr, c)
算法12-5：树状数组区间求前缀和 GetPrefixSum(c, k)
算法12-6：树状数组单点更新 Update(c, n, k, d)
算法12-7：红黑树中的右旋 RRotate(rbtree, x)
算法12-8：红黑树中插入结点后的调整 InsertAdjust(rbtree, x)
算法12-9：删除黑结点及颜色调整 DeleteAdjust(rbtree, x)
算法12-10：树堆的插入 InsertTreap(treap, x)
12.2 基础练习
练习12-1 是否红黑树
*练习12-2 三逆序组
12.3 进阶实验
实验12-1 树种统计
*实验12-2 染成红黑树
*实验12-3 逆序对
第13章 外排序
13.1 算法实现
算法13-1：初始化败者树 InitLoserTree(tree, array, size)
算法13-2：从内部结点到根结点的路径上进行比赛 Play(tree, p, left, right)
算法13-3：重构时从外部结点到根结点的路径上重新进行比赛 RePlay(tree, i)
算法13-4：利用败者树进行多路归并排序MultiMerge(tree, racer, buffer_ pool, f, size)
算法13-5：置换选择算法 ReplacementSelection(ram_array, m, file_ in, file_out)
13.2 基础练习
*练习13-1 数据去重
13.3 进阶实验
*实验13-1 文件排序
第14章 索引
14.1 基础练习
*练习14-1 B+树的查找
*练习14-2 基于词频的文件相似度
14.2 进阶实验
*实验14-1 3 阶B+树
*实验14-2 迷你搜索引擎
第15章 算法设计基础
15.1 算法实现
算法15-1：小规模分书问题的嵌套循环算法 BookAssignment(T)
算法15-2：枚举法的嵌套循环实现 IterBruteForce(T)
算法15-3：枚举法的递归实现 RecBruteForce(T, s, i, n)
算法15-4：分书问题的递归枚举算法 BookAssignmentBF(table, s, i, n, m)
算法15-5：回溯法的通用伪代码 Backtracking(i, n)
算法15-6：点集重构问题回溯算法的伪代码 PointSetReconstruction(x, D, n, left, right)
算法15-7：分治法的伪代码描述 DivideAndConquer(n)
算法15-8：第n项斐波那契数的递归计算 RecFib(n)
算法15-9：第n项斐波那契数的循环计算 Fib(n)
算法15-10：计算m1, n的动态规划算法 OptimalMatrixOrdering(m, p, r, n)
算法15-11：活动安排问题的贪心算法 ActivitySelection(a, k, n)
算法15-12：连续背包问题的贪心算法 Knapsack(W, s, x, n)
算法15-13：离散背包（0-1 背包）问题的递归分治解法 Knapsack01(W, s, x, f, n, i)
算法15-14：整数重量限制下离散背包问题的动态规划解法 Knapsack01(W, s, opt, n)
15.2 基础练习
练习15-1 分书问题
练习15-2 n皇后问题
*练习15-3 旅行商问题
练习15-4 最长公共子序列
练习15-5 带权的活动安排问题
练习15-6 教室安排问题
15.3 进阶实验
实验15-1 0-1 背包问题的回溯剪枝解
实验15-2 0-1 背包问题的分支限界解
实验15-3 拼题A打卡奖励
实验15-4 有多少红黑树
*实验15-5 代金券
第16章 高级算法设计
16.1 算法实现
算法16-1：顶点覆盖问题的近似算法 VertexCoverApproximation(E)
算法16-2：基于贪心策略的离散背包问题近似算法 KnapsackGreedyApproximation(W, s, x, n)
算法16-3：基于动态规划的离散背包问题近似算法 KnapsackDPApproximation(W, s, x, n, eps)
算法16-4：A算法 A(h, init_state, goal_state)
算法16-5：爬山算法 HillClimbing(f, init_solution, E)
算法16-6：模拟退火算法 SimulatedAnnealing(init_solution, E, T, alpha, k, iter_num, eps)
算法16-7：计算 ai mod n的幂取模算法 PowMod(a, i, n)
算法16-8：Miller-Rabin素数测试算法 MillerRabin_IsPrime(n, k)
16.2 进阶实验
实验16-1 0-1 背包问题的近似解
*实验16-2 旅行商问题
*实验16-3 九宫数独
*实验16-4 五子棋
*实验16-5 最小生成树
参考文献
