菜鸟笔记
提升您的技术认知

C++面试知识点

strcpy函数实现

char* strcpy(char* dest, const char* src){
  assert((dest != NULL) && (src != NULL));  //检查指针的有效性
  char* res = dest;
  while((*dest++ = *src++) != '\0');
  return res;  //返回res的原始值使函数能够支持链式表达式
}

memcpy函数实现

void* memcpy(void* dest, const void* src, size_t len){
  if(!dest || !src) return NULL;
  void* ret = dest;

  //没有内存重叠
  if(dest <= src || (char*)dest >= (char*)src + len){
    while(len--){
      *(char*)dest = *(char*)src;
      dest = (char*)dest + 1;
      src = (char*)src + 1;
    }
  }
  else{
    //存在重叠
    src = (char*)src + len - 1;
    dest = (char*)dest + len - 1;
    while(len--){
      *(char*)dest = *(char*)src;
      dest = (char*)dest - 1;
      src = (char*)src - 1;
    }
  }
  return ret;
}

类对象的构造

1) 只能动态分配类对象:就是用new运算符来创建一个类对象,在堆上分配内存。
将类的构造函数和析构函数设置为protected属性,这样类对象不能访问,但是派生类能够继承,也能够访问。

class A{
protected:
  A(){}
  ~A(){}

public:
  //将create设置为static,创建对象的时候,A* p = A::create(),
  //只有静态成员函数才能通过类名来访问。
  static A* create(){
    return new A();
  }

  void destroy(){
    delete this;
  }
};

2) 静态分配类对象:把new、delete运算符重载为private属性就可以了。

class A{
private:
  void* operator new(size_t t){}
  void operator delete(void* ptr){}

public:
  A(){}
  ~A(){}

};

红黑树

红黑树定义

其或者是一颗空树,或者是具有以下性质的对称平衡二叉查找树:

  • 节点非红即黑;
  • 根节点是黑色;
  • 所有NULL节点称为叶子节点,且其颜色为黑;
  • 所有红色节点的子节点都为黑色;
  • 从任一节点到其叶子节点的所有路径上都包含相同数目的黑色节点;

红黑树最大路径长度不可能大于两倍最短路径,为什么?

因为第一条该树上的节点非红即黑,由于第四条该树上不允许存在连续的红节点,那么对于从第一个节点到其叶子节点的一条最长路径一定是红黑交错的,那么最短路径一定是纯黑色的节点;而第五条从任一节点到其叶子节点的所有路径上都包含相同数目的黑色节点,这么说来最长路径上的黑节点的数目和最短路径上的黑节点的数目相等!而第二条根节点为黑,第三条叶子结点为黑色,那么可知:最长路径 ≤ 2 * 最短路径
一颗二叉树的平衡性能越好,那么它的效率越高!

红黑树放松了对平衡的限制,可以不再是严格意义上的平衡二叉树,但在每个节点上增加一个存储位表示节点的颜色,可以是Red 或者 Block。

【解释】:红黑树属于平衡二叉树,说它不严格是因为它不是严格控制左、右子树高度或者节点数之差小于等于1,但是红黑树的高度依然是平均log(n),且最坏情况下高度不会超过2log(n),这个可以数学证明。所以它算平衡树,只是不严格,不过严格与否并不影响数据结构的复杂度,红黑树多用于系统底层;

红黑树与AVL树的相同点和区别

红黑树和AVL树类似,都是在进行插入和删除操作时通过特定操作保持二叉查找树的平衡,从而获得较高的查找。自从红黑树出来后,AVL树就被放到了博物馆里,据说是红黑树有更好的效率,更高的统计性能。

红黑树与AVL树的区别在于它使用颜色来标识节点的高度,它所追求的是局部平衡而不是AVL树中的非常严格的平衡。AVL树的复杂比起红黑树来说简直是小巫见大巫。红黑树是真正的变态级数据结构。

红黑树的时间复杂度

在一棵二分查找树上,执行查找、插入、删除等操作的最好情况时间复杂度为O(lgn),因为一颗由n个节点,随机构造的二叉查找树的高度为lgn,一般操作的执行时间为O(lgn)。

但若是一颗具有n个节点的线性链,则这些操作最坏情况运行时间为O(n)。
而红黑树可以保证在最坏情况下,基本的动态几何操作的时间均为O(lgn)。

静态成员函数和数据成员有什么意义?

静态数据成员:类内数据成员声明的时候加上static修饰符;

特点:

  • 该类的所有对象共享访问该数据成员,在程序中,只有一个复制品。而对于非静态数据成员,每个类对象都有自己的复制品。
  • 存储在全局数据区。定义时要分配空间,所以不能在类声明中定义。
  • 与普通数据成员一样遵从public、protected、private访问规则。
  • 初始化在类外,不加static。

优点:

  • 静态数据成员没有进入程序全局名字空间,因此不会与程序中其他全局名字冲突。
  • 可以实现信息隐藏。静态数据成员可以是private成员,而全局变量不能。

静态成员函数

  • 是为类的全部服务而不是为类的某个对象服务;
  • 是类的内部实现,属于类定义的一部分;
  • 由于不与任何对象相联系,因此不具有this指针,所以无法访问类对象的非静态数据成员,也无法访问类非静态成员函数,只能访问静态数据成员,调用静态成员函数;

必须在构造函数初始化式里进行初始化的数据成员有哪些?

构造函数中,成员变量一定要通过初始化列表来初始化的有以下几种情况:

  • const常量成员:因为常量只能在初始化,不能赋值,所以必须放在初始化列表中;

  • 引用类型:引用必须在定义的时候初始化,并且不能重新赋值,所以也要写在初始化列表中;

  • 没有默认构造函数的类类型:因为使用初始化列表可以不必调用默认构造函数来初始化,而是直接调用拷贝构造函数;