算法与数据结构

Notebook系列

介绍

介绍算法与数据结构:首先介绍算法分析和设计,然后介绍一些常见的数据结构,最后介绍排序算法,查找算法,字符串算法等,以及一些深入探索.

算法分析

• 渐进记号
• 常用函数和记号
• 平摊分析

算法设计

• 迭代法
• 递推法与递归式
• 随机算法
• 穷举搜索法
• 分治算法
• 回溯法
• 动态规划
• 贪心算法

线性数据结构

基本

• 数组
• 字符串

链表

• 链表
• 双向链表
• 循环链表

其他线性结构

• 栈与队列

散列数据结构

树形数据结构

二叉查找树

• 二叉查找树(BST): 每个结点最多有2个子树的树结构
• AVL树: 一种自调整的平衡二叉查找树
• 伸展树(Splay Tree): 又叫分裂树,是一种自调整的二叉查找树
• 红黑树(Red Black Tree): 一种自调整的平衡二叉查找树
• Treap

堆

• 二叉堆(大根堆 小根堆)
• 左倾堆
• 二项堆
• 斐波那契堆(Fibonacci Heap)

其他树/树形结构

• B-Tree
• R-Tree
• 前缀树(Trie Tree)/后缀树(Suffix Tree)
• 最优二叉树(Huffman Tree)
• Segment Tree
• 跳表

排序算法

• 冒泡排序
• 快速排序
• 插入排序
• 希尔排序
• 选择排序
• 堆排序
• 归并排序
• 计数排序
• 基数排序
• 桶排序

查找算法

• 顺序表查找: 顺序查找
• 有序表查找: 二分查找
• 树查找: 二叉排序树,AVL树,B-,B+
• 哈希表查找: O(1)

图数据结构

• 图基本算法
  • 图结构: (对象和指针,矩阵,邻接表)
  • 图搜索/遍历: DFS BFS
• 最小生成树: kruskal prim
• 单源最短路径: Floyd,Dijkstra,bellman-ford,SPFA,A*

字符串算法

• 排序
• 字符串匹配
  • Knuth-Morris-Pratt
  • Boyer-Moore
• 正则表达式

算法研究

• 线性规划
• NP完全性

参考资料

基础

• 《算法导论》
• 《Algorithms》

面试算法

• 《剑指offer》
• 《编程之美》

延伸阅读

• 《深入理解计算机系统》
• 《计算机程序的构造和解释》

博客与网站

• JS-Sorting-Algorithm
• DataStructure
• The-Art-Of-Programming-By-July : [GitHub]
• leetcode : [leetcode]
• 算法和数据结构词典:[Dictionary of Algorithms and Data Structures]

说明

本系列中,部分图片和内容来自 Wiki Github 等,如有问题,请联系删除.