计算机算法 C++描述 第二章

template 模板

  1. 类模板
    假设一个类中数据成员的数据类型不能确定。或者是某个成员函数的參数或返回值的类型不能确定。就必须将此类声明为模板,它的存在不是代表一个详细的、实际的类,而是代表着一类类。

    1
    2
    3
    4
    5
    6
    template <class Type>
    class foo
    {
    private:
    Type a;
    }
  2. 类模板的使用

    1
    类名<实际的类型>

    类模板的使用实际上是将类模板实例化成一个详细的类

  3. 在类外面定义函数模板

    1
    2
    3
    4
    5
    template<typename(或class) T>
    <返回类型><函数名>(參数表)
    {
    函数体
    }
    1
    2
    3
    4
    5
    6
    template<typename(或class) T>
    T fuc(T x, T y)
    {
    T x;
    //……
    }
  4. 模板函数

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    double d;
    int a;
    fuc(d,a);
    则系统将用实參d的数据类型double去取代函数模板中的T生成函数:

    double fuc(double x,int y)
    {
    double x;
    //……
    }

    模板函数的生成就是将函数模板的类型形參实例化的过程。

队列

队列的一种有效表示方法是用数组,把他看成环形结构

  • 判断队列为空 rear == front
  • 队尾插入操作 rear = (++rear)%MaxSize

二叉树

  1. 引理

    • 一棵二叉树第i层上最多结点个数为2i-1, 一个深度为k的二叉树最多节点数为2k-1

      n个节点的完全二叉树可以存放在一维数组tree[n+1]中

    • 任何一个包含n个节点的完全二叉树,如果采用上述的方法表示,对于任何下标的节点i来说,1 <= i <= n有:
      1. 当 i != 1 时,parent(i)在 ⌊i/2⌋。当i == 1时,i是树根没有parent
      2. 当 2i <= n 时,lchild(i)在2i。如果2i > n,i没有左孩子
      3. 当 2i + 1 <= n 时,rchild(i)在2i+1,否则没有右孩子
  2. 二叉搜索树

    特征

    1. 每个元素都有一个键值,并且没有两个元素键值相同
    2. 左子树的键值(如果有的话)都小于树根的键值
    3. 右子树的键值(如果有的话)都大于树根的键值
    4. 左右子树也都是二叉搜索树
  3. 堆(Heap)

    1. 堆性质:每个节点的值都至少与其孩子一样大(一样小) —> 依次递增(减)
    2. 堆排序:这可真的是一个秀的头疼的操作。靠其自身的insert和deletemax构建新堆获得旧堆的顺序
  4. 集合与 不相交 集合的并集

    1. 用森林表示集合,每个集合都可以表示为一棵树。把孩子节点链接到父节点上
    2. 为了得到两个集合的并集,我们可以把一课树的树根的父节点域设置为另一棵树的树根( 不相交)
    3. 忽略集合的名字并且用表示集合的树的树根来标志该集合
    4. 权重规则 : 如果以i为树根的树所包含的节点少于以j为树根的树,那么就令j成为i的父节点。否则i成为j的父节点
    5. 收缩规则 : 如果节点j在节点i到树根的路径上,并且p[i] != root[i],那么将p[i]置为root[i]
      —–> p[j]及路径上所有节点的父节点置为root[i]
    1. 图的定义和特点
      1. 欧拉定义定点的度等于与他相接的边的条数
      • 对于有向图来说:V的入/出度是以v为头/尾的所有边的条数
      1. 当且仅当所有定点的度数都是偶数,满足这样条件的路径被成为 欧拉路径
      2. 我们通常用G=(V, E)来表示一个图
      • V 是有穷非空的定点的集合
      • E 是顶点对称的集合,又被称为边
      • 无向图中任意边的顶点对都是无序的 (u, v)
      • 有向图中任意边的顶点对都是有序的 <u, v>, u是头,v是尾
      1. 图不能包含定点v到自己的边。这样的边被称为自边或者自环
      2. 图不能有一条边重复多次,如果去掉这个限制那么我们得到的是多图
      • 任意包含n个顶点的无向图的最大边数为 n(n-1)/2,包含最大边数的无向图是完全的
      • 任意包含n个顶点的有向图的最大边数为 n(n-1)
      1. 路径的长度就是其中的边数
      2. 简单路径: 路径中可能除了第一个和最后一个都是不同的顶点(只有可能第一个和最后一个相同,其他的都不同)
      3. 环: 第一个和最后一个相同的路径
    2. 图的表示
      1. 邻接矩阵
      • 邻接矩阵是一个n*n的矩阵
      • 若存在边(i, j),则a[i, j] = 1,其他的等于0
      • 无向图的邻接矩阵是对称的
      • 无向图上的顶点i其度数等于它对应的行之和
      • 有向图上行之和是出度,列之和是入度
      1. 邻接表
        邻接表
      2. 邻接多重表