勿在浮沙筑高台

目录

• 1 深入理解计算机系统
• 2 数据结构与算法之美
  • 数组
  • 链表
  • 栈
  • 队列
  • 递归
  • 排序
  • 二分查找
  • 散列表
  • 字符串
  • 二叉树
  • 堆
  • 图
  • 回溯
  • 分治
  • 动态规划
  • 剑指Offer & LeetCode
• 3 C++11
  • 适合初学者的经典教程
  • 几个常用类的实现
    • complex(封装与数据抽象)
    • String(内存管理与拷贝控制)
    • Vector<T>(模板编程)
    • 表达式计算器(面向对象)
• 4 矩阵&概率统计

---

1 深入理解计算机系统

1. Data Lab
2. Bomb Lab
3. Attack Lab
4. Cache Lab
5. Shell Lab
6. Malloc Lab
7. Proxy Lab

2 数据结构与算法之美

数组

• 实现一个支持动态扩容的数组
• 实现一个大小固定的有序数组，支持动态增删改操作
• 实现两个有序数组合并为一个有序数组

链表

• 实现单链表、循环链表、双向链表，支持增删操作
• 实现单链表反转
• 实现两个有序的链表合并为一个有序链表
• 实现求链表的中间结点

栈

• 用数组实现一个顺序栈
• 用链表实现一个链式栈
• 编程模拟实现一个浏览器的前进、后退功能

队列

• 用数组实现一个顺序队列
• 用链表实现一个链式队列
• 实现一个循环队列

递归

• 编程实现斐波那契数列求值f(n)=f(n-1)+f(n-2)
• 编程实现求阶乘n!
• 编程实现一组数据集合的全排列

排序

• 实现归并排序、快速排序、插入排序、冒泡排序、选择排序
• 编程实现O(n)时间复杂度内找到一组数据的第K大元素

二分查找

• 实现一个有序数组的二分查找算法
• 实现模糊二分查找算法（比如大于等于给定值的第一个元素）

散列表

• 实现一个基于链表法解决冲突问题的散列表
• 实现一个LRU缓存淘汰算法

字符串

• 实现一个字符集，只包含a～z这26个英文字母的Trie树
• 实现朴素的字符串匹配算法

二叉树

• 实现一个二叉查找树，并且支持插入、删除、查找操作
• 实现查找二叉查找树中某个节点的后继、前驱节点
• 实现二叉树前、中、后序以及按层遍历

堆

• 实现一个小顶堆、大顶堆、优先级队列
• 实现堆排序
• 利用优先级队列合并K个有序数组
• 求一组动态数据集合的最大Top K

图

• 实现有向图、无向图、有权图、无权图的邻接矩阵和邻接表表示方法
• 实现图的深度优先搜索、广度优先搜索
• 实现Dijkstra算法、A*算法
• 实现拓扑排序的Kahn算法、DFS算法

回溯

• 利用回溯算法求解八皇后问题
• 利用回溯算法求解0-1背包问题

分治

• 利用分治算法求一组数据的逆序对个数

动态规划

• 0-1背包问题
• 最小路径和
• 编程实现莱文斯坦最短编辑距离
• 编程实现查找两个字符串的最长公共子序列
• 编程实现一个数据序列的最长递增子序列

剑指Offer & LeetCode

3 C++11

适合初学者的经典教程

1. 侯捷C++大系
   1. C++面向对象高级编程
   2. STL与泛型编程
2. Accelerated C++
3. C++ in Action
4. A Tour of C++

推荐理由：直入主题，开门见山，向初学者展示 C++ 的核心，而没有一上来就给读者灌输一大堆语法的繁文缛节，严重影响学习的兴趣和效率。所以这儿没有给初学者推荐《C++ Primer》、《Effective C++》。

几个常用类的实现

complex(封装与数据抽象)

#ifndef __MYCOMPLEX__
#define __MYCOMPLEX__

class complex;
complex&
  __doapl (complex* ths, const complex& r);
complex&
  __doami (complex* ths, const complex& r);
complex&
  __doaml (complex* ths, const complex& r);


class complex
{
public:
  complex (double r = 0, double i = 0): re (r), im (i) { }
  complex& operator += (const complex&);
  complex& operator -= (const complex&);
  complex& operator *= (const complex&);
  complex& operator /= (const complex&);
  double real () const { return re; }
  double imag () const { return im; }
private:
  double re, im;

  friend complex& __doapl (complex *, const complex&);
  friend complex& __doami (complex *, const complex&);
  friend complex& __doaml (complex *, const complex&);
};


inline complex&
__doapl (complex* ths, const complex& r)
{
  ths->re += r.re;
  ths->im += r.im;
  return *ths;
}

inline complex&
complex::operator += (const complex& r)
{
  return __doapl (this, r);
}

inline complex&
__doami (complex* ths, const complex& r)
{
  ths->re -= r.re;
  ths->im -= r.im;
  return *ths;
}

inline complex&
complex::operator -= (const complex& r)
{
  return __doami (this, r);
}

inline complex&
__doaml (complex* ths, const complex& r)
{
  double f = ths->re * r.re - ths->im * r.im;
  ths->im = ths->re * r.im + ths->im * r.re;
  ths->re = f;
  return *ths;
}

inline complex&
complex::operator *= (const complex& r)
{
  return __doaml (this, r);
}

inline double
imag (const complex& x)
{
  return x.imag ();
}

inline double
real (const complex& x)
{
  return x.real ();
}

inline complex
operator + (const complex& x, const complex& y)
{
  return complex (real (x) + real (y), imag (x) + imag (y));
}

inline complex
operator + (const complex& x, double y)
{
  return complex (real (x) + y, imag (x));
}

inline complex
operator + (double x, const complex& y)
{
  return complex (x + real (y), imag (y));
}

inline complex
operator - (const complex& x, const complex& y)
{
  return complex (real (x) - real (y), imag (x) - imag (y));
}

inline complex
operator - (const complex& x, double y)
{
  return complex (real (x) - y, imag (x));
}

inline complex
operator - (double x, const complex& y)
{
  return complex (x - real (y), - imag (y));
}

inline complex
operator * (const complex& x, const complex& y)
{
  return complex (real (x) * real (y) - imag (x) * imag (y),
      real (x) * imag (y) + imag (x) * real (y));
}

inline complex
operator * (const complex& x, double y)
{
  return complex (real (x) * y, imag (x) * y);
}

inline complex
operator * (double x, const complex& y)
{
  return complex (x * real (y), x * imag (y));
}

complex
operator / (const complex& x, double y)
{
  return complex (real (x) / y, imag (x) / y);
}

inline complex
operator + (const complex& x)
{
  return x;
}

inline complex
operator - (const complex& x)
{
  return complex (-real (x), -imag (x));
}

inline bool
operator == (const complex& x, const complex& y)
{
  return real (x) == real (y) && imag (x) == imag (y);
}

inline bool
operator == (const complex& x, double y)
{
  return real (x) == y && imag (x) == 0;
}

inline bool
operator == (double x, const complex& y)
{
  return x == real (y) && imag (y) == 0;
}

inline bool
operator != (const complex& x, const complex& y)
{
  return real (x) != real (y) || imag (x) != imag (y);
}

inline bool
operator != (const complex& x, double y)
{
  return real (x) != y || imag (x) != 0;
}

inline bool
operator != (double x, const complex& y)
{
  return x != real (y) || imag (y) != 0;
}

#include <cmath>

inline complex
polar (double r, double t)
{
  return complex (r * cos (t), r * sin (t));
}

inline complex
conj (const complex& x)
{
  return complex (real (x), -imag (x));
}

inline double
norm (const complex& x)
{
  return real (x) * real (x) + imag (x) * imag (x);
}

#endif   //__MYCOMPLEX__

String(内存管理与拷贝控制)

#ifndef __MYSTRING__
#define __MYSTRING__

class String
{
public:
   String(const char* cstr=0);
   String(const String& str);
   String& operator=(const String& str);
   ~String();
   char* get_c_str() const { return m_data; }
private:
   char* m_data;
};

#include <cstring>

inline
String::String(const char* cstr)
{
   if (cstr) {
      m_data = new char[strlen(cstr)+1];
      strcpy(m_data, cstr);
   }
   else {
      m_data = new char[1];
      *m_data = '\0';
   }
}

inline
String::~String()
{
   delete[] m_data;
}

inline
String& String::operator=(const String& str)
{
   if (this == &str)
      return *this;

   delete[] m_data;
   m_data = new char[ strlen(str.m_data) + 1 ];
   strcpy(m_data, str.m_data);
   return *this;
}

inline
String::String(const String& str)
{
   m_data = new char[ strlen(str.m_data) + 1 ];
   strcpy(m_data, str.m_data);
}

#include <iostream>
using namespace std;

ostream& operator<<(ostream& os, const String& str)
{
   os << str.get_c_str();
   return os;
}

#endif

Vector<T>(模板编程)

#ifndef VECTOR_H
#define VECTOR_H

#include <algorithm>
#include <iostream>
#include <stdexcept>
#include "dsexceptions.h"

template <typename Object>
class Vector
{
  public:
    explicit Vector( int initSize = 0 )
      : theSize{ initSize }, theCapacity{ initSize + SPARE_CAPACITY }
      { objects = new Object[ theCapacity ]; }

    Vector( const Vector & rhs )
      : theSize{ rhs.theSize }, theCapacity{ rhs.theCapacity }, objects{ nullptr }
    {
        objects = new Object[ theCapacity ];
        for( int k = 0; k < theSize; ++k )
            objects[ k ] = rhs.objects[ k ];
    }

    Vector & operator= ( const Vector & rhs )
    {
        Vector copy = rhs;
        std::swap( *this, copy );
        return *this;
    }

    ~Vector( )
      { delete [ ] objects; }

    Vector( Vector && rhs )
      : theSize{ rhs.theSize }, theCapacity{ rhs.theCapacity }, objects{ rhs.objects }
    {
        rhs.objects = nullptr;
        rhs.theSize = 0;
        rhs.theCapacity = 0;
    }

    Vector & operator= ( Vector && rhs )
    {
        std::swap( theSize, rhs.theSize );
        std::swap( theCapacity, rhs.theCapacity );
        std::swap( objects, rhs.objects );

        return *this;
    }

    bool empty( ) const
      { return size( ) == 0; }
    int size( ) const
      { return theSize; }
    int capacity( ) const
      { return theCapacity; }

    Object & operator[]( int index )
    {
                                                     #ifndef NO_CHECK
        if( index < 0 || index >= size( ) )
            throw ArrayIndexOutOfBoundsException{ };
                                                     #endif
        return objects[ index ];
    }

    const Object & operator[]( int index ) const
    {
                                                     #ifndef NO_CHECK
        if( index < 0 || index >= size( ) )
            throw ArrayIndexOutOfBoundsException{ };
                                                     #endif
        return objects[ index ];
    }

    void resize( int newSize )
    {
        if( newSize > theCapacity )
            reserve( newSize * 2 );
        theSize = newSize;
    }

    void reserve( int newCapacity )
    {
        if( newCapacity < theSize )
            return;

        Object *newArray = new Object[ newCapacity ];
        for( int k = 0; k < theSize; ++k )
            newArray[ k ] = std::move( objects[ k ] );

        theCapacity = newCapacity;
        std::swap( objects, newArray );
        delete [ ] newArray;
    }

      // Stacky stuff
    void push_back( const Object & x )
    {
        if( theSize == theCapacity )
            reserve( 2 * theCapacity + 1 );
        objects[ theSize++ ] = x;
    }
      // Stacky stuff
    void push_back( Object && x )
    {
        if( theSize == theCapacity )
            reserve( 2 * theCapacity + 1 );
        objects[ theSize++ ] = std::move( x );
    }

    void pop_back( )
    {
        if( empty( ) )
            throw UnderflowException{ };
        --theSize;
    }

    const Object & back ( ) const
    {
        if( empty( ) )
            throw UnderflowException{ };
        return objects[ theSize - 1 ];
    }

      // Iterator stuff: not bounds checked
    typedef Object * iterator;
    typedef const Object * const_iterator;

    iterator begin( )
      { return &objects[ 0 ]; }
    const_iterator begin( ) const
      { return &objects[ 0 ]; }
    iterator end( )
      { return &objects[ size( ) ]; }
    const_iterator end( ) const
      { return &objects[ size( ) ]; }

    static const int SPARE_CAPACITY = 2;

  private:
    int theSize;
    int theCapacity;
    Object * objects;
};

#endif

表达式计算器(面向对象)

class Node
{
public:
  virtual ~Node () {}
  virtual double Calc () const = 0;
};


class NumNode: public Node
{
public:
  NumNode (double num) : _num (num ) {}
  double Calc () const;
private:
  const double _num;
};
double NumNode::Calc () const
{
  std::cout << "Numeric node " << _num << std::endl;
  return _num;
}


class BinNode: public Node
{
public:
  BinNode (Node * pLeft, Node * pRight)
   : _pLeft (pLeft), _pRight (pRight) {}
  ~BinNode ();
protected:
  Node * const _pLeft;
  Node * const _pRight;
};
BinNode::~BinNode ()
{
  delete _pLeft;
  delete _pRight;
}


class AddNode: public BinNode
{
public:
  AddNode (Node * pLeft, Node * pRight)
   : BinNode (pLeft, pRight) {}
  double Calc () const;
};
double AddNode::Calc () const
{
  std::cout << "Adding\n";
  return _pLeft->Calc () + _pRight->Calc ();
}


class MultNode: public BinNode
{
public:
  MultNode (Node * pLeft, Node * pRight)
   : BinNode (pLeft, pRight) {}
  double Calc () const;
};
double MultNode::Calc () const
{
  std::cout << "Multiplying\n";
  return _pLeft->Calc () * _pRight->Calc ();
}


int main ()
{
  // ( 20.0 + (-10.0) ) * 0.1
  Node * pNode1 = new NumNode (20.0);
  Node * pNode2 = new NumNode (-10.0);
  Node * pNode3 = new AddNode (pNode1, pNode2);
  Node * pNode4 = new NumNode (0.1);
  Node * pNode5 = new MultNode (pNode3, pNode4);
  std::cout << "Calculating the tree\n";
  // tell the root to calculate itself
  double x = pNode5->Calc ();
  std::cout << "Result: " << x << std::endl;
  delete pNode5; // and all children
}

4 矩阵&概率统计

矩阵类的实现

#ifndef MATRIX_H
#define MATRIX_H

#include <vector>
#include <initializer_list>
using namespace std;

template <typename Object>
class matrix
{
  public:
    matrix( int rows, int cols ) : array( rows )
    {
        for( auto & thisRow : array )
            thisRow.resize( cols );
    }

    matrix( initializer_list<vector<Object>> lst ) : array( lst.size( ) )
    {
        int i = 0;
        for( auto & v : lst )
            array[ i++ ] = std::move( v );
    }

    matrix( const vector<vector<Object>> & v ) : array{ v }
      { }
    matrix( vector<vector<Object>> && v ) : array{ std::move( v ) }
      { }

    const vector<Object> & operator[]( int row ) const
      { return array[ row ]; }
    vector<Object> & operator[]( int row )
      { return array[ row ]; }

    int numrows( ) const
      { return array.size( ); }
    int numcols( ) const
      { return numrows( ) ? array[ 0 ].size( ) : 0; }
  private:
    vector<vector<Object>> array;
};

#endif