《算法精解》这本书

一、简介

二、指针操作

  • 指针基础
  • 存储空间分配
  • 数据集合与指针的算术运算
  • 指向指针的指针
  • 泛型指针与类型转换
  • 函数指针

    三、递归

  • 基本递归

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    int fact(int n){
    if (n < 0)
    return 0;
    else if (n==0)
    return 1;
    else if (n == 1)
    return 1;
    else
    return n*fact(n - 1);
    }
  • 尾递归

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    int facttail(int n, int a){
    if (n < 0)
    return 0;
    else if (n==0)
    return 1;
    else if (n==1)
    return a;
    else
    return facttail(n - 1, n*a);
    }

四、算法分析

  • 最坏情况分析
  • O表示法(指明一个函数的上限)
    • 常数项用O(1)
    • 常数因子往往被忽略O(T)
    • 加法运算取最大值 max(O(T1),O(T2))
    • 乘法结果不需要改变 O(T1T2)
  • 计算的复杂度

五、链表

  • 链表可以说是一种最为基础的数据结构
    • 单链表:是由各个元素之间通过一个指针彼此链接起来而组成。(你的弱点有多弱,你的强度就有多强)
    • 双向链表:链表元素之间由两个指针链接。双向链表中的每一个元素都由3个部分组成:成了数据成员和next指针外,每个元素还包含一个指向其前驱元素的指针,称为prev指针。为了表示链表的头和尾,将第一个元素的prev指针和最后一个元素的next指针设置为NULL。
    • 循环链表:提供了更为灵活的遍历链表元素的能力。循环链表可以是单向的或者是双向的,但区分一个链表是不是循环链表只要看它有没有尾部元素即可。

六、栈和队列

  • 栈:后进先出(LIFO)想象成一桶网球
  • 队列:先进先出(FIFO)排队

七、集合

  • 集合:
    • 集合能够采用基本的数学定义来描述。和其他数据对象一样,集合包含一些基本定义,基本的操作以及属性。
    • 集合是相关成员的无序组合,且每个成员在集合中仅出现一次。

八、哈希表

  • 哈希表支持一种最有效的检索方法:散列。从根本上来说,一个哈希表包含一个数组,通过特殊的索引值(键)来访问数组中的元素。哈希表的主要思想是通过一个哈希函数,在所有可能的键与槽位之间建立一张映射表。哈希函数每次接受一个键将返回与键相对应的哈希编码或哈希值。键的数据类型可能多种多样,但哈希值的类型只能是整型。

九、树

  • 树由称为节点的元素按照层次结构的方式组织而成。层次结构最顶端的结点为根。与根结点直接相连的结点称为根的子结点,通常子结点本身也有属于它们自己的子结点。除了根结点外,在这个层次体系中的每个结点都有唯一的父结点,也就是与其直接相连的上级结点。一个结点拥有多个子结点取决于树的类型,这个量值称为树的分支因子,它决定了当插入结点时树的分支扩展的速度。
    • 二叉树
    • 树的周游算法
    • 树的平衡
    • 二叉搜索树
    • 树的旋转

十、堆和优先队列

  • 堆:它是一种树形组织,使我们能够迅速确定包含最大值的结点。维持一棵树的代价低于维持一个有序数据集的代价。同样,我们可以通过堆快速地找到包含最小值的元素。
    • 堆是一颗二叉树,通常其子结点存储的值比父结点的值小。所以,根结点是树中最大的结点。同样,我们也可以让堆向另一种方向发展,即每个子结点存储的值比父结点的值大。这样根结点就是树中最小的结点。这样的二叉树是局部有序的,任何一个结点与其兄弟结点之间都没有必然的顺序关系,但它与其父子结点有大小顺序关系。子结点比父结点小的堆称为最大值堆,这是因为根结点存储该树所有结点的最大值。反之亦然,子结点比父结点大的堆称为最小值堆。
  • 优先队列:他是一个从堆自然衍生而来的数据结构。在优先队列中,数据保存在一个堆中,这样我们能够迅速确定下一个最高优先级的结点。所谓元素的“优先级”在不同的问题中意义也不相同。
  • 应用
    • 排序
      • 具体来说,就是指堆排序。在堆排序中,要排序的数据首先存储在一个堆中。从堆中一次取出一个结点,放置到有序数据集的尾部。
    • 任务调度
    • 包囊分拣
    • 霍夫曼编码
    • 负载均衡

十一、图

  • 图:一种灵活的数据结构,一般作为一种模型用来定义对象之间的关联或者联系。对象由顶点表示,而对象之间的关系或者关联则通过顶点之间的边来表示。
    • 图由两种类型的元素组成:顶点和边。顶点代表对象,边则建立起对象之间的关系或关联。在许多问题中,图的边都关联了值或者权重的信息;
    • 有向图:边是由两个顶点组成的有序对,具由特定的方向。有时候,有向图的边也称之为弧。
    • 无向图:边是没有方向的,因此无向图的边九直接用线来代替剪头表示。
      • 应用场景:计算网络跳数
        • 用来确定在互联网中从一个结点到另一个结点的最佳路径。一种建模方法是采用无向图,其中顶点表示网络结点,边代表之间的连接。通过这种模型,可以采用广度优先搜索来帮助确定结点间的最小跳数。

十二、排序和搜索

  • 插入排序
  • 快速排序
  • 归并排序
  • 计数排序
  • 基数排序
  • 二分查找