源码

1 基础知识

1.1 编程语言

四个类型转换关键字

参考
1) static_cast
底层无const的一般静态转换，基本类型 / 具有继承关系的类型

//基本类型转换
int i = 0;
double d = static_cast<double>(i);  //相当于double d = double(i);
//转换继承类的对象为基类对象
class Base{};
class Derived: public Base{};
Derived d;
Base b = static_cast<Base>(d);  //相当于Base(d)

2) dynamic_cast
动态转换，派生类指针(引用)转换为基类指针(引用) / 没有继承关系但被转换类有虚函数

class Base{};
class Derived: public Base{};
//派生类指针转换为基类指针
Derived *pd = new Derived;
Base *pb = dynamic_cast<Base>(pd);
//检测
if(!pb){
  std::cout << "Failed Cast!";
}
//没有继承关系，但被转换类有虚函数
class A{
    virtual ~A();
};
class B{};
A *pa = new A;
B *pb = dynamic_cast<B>(pa);

3) const_cast
只改变const(常量)属性，不改变类型

const int *pci = 0;
//将常量转换为非常量
int *pk = const_cast<int*>(pci);  //相当于int *pk = int*(pci);
const A* pca = new A;
A *pa = const_cast<A*>(pca); //相当于A *pa = A*(pca);

4) reinterpret
重新解释、指针类型转换

//基本类型指针的类型转换
double d = 9.2;
double *pd = &d;
int *pi = reinterpret_cast<int*>(pd); //相当于int *pi = (int*)pd;
//不相关的类的指针类型转换
class A{};
class B{};
A *pa = new A;
B *pb = reinterpret_cast<B*>(pa); //相当于B *pb = (B*)pa;
//指针转换为整数
int *pi = 0;
long L = reinterpret_cast<long>(pi);  //相当于long L = (long)pi;

sizeof

1) 空类型使用sizeof，计算该类型实例的大小，使用实例，有大小，大小由编译器决定，一般是1
2) 有构造和析构函数的类型，一般也是1，实例调用这俩函数只需知道函数地址，函数地址与类型有关，与实例无关
3) 有虚函数的类型，大小为一个指针的大小（32/64->4/8），编译器会在实例中添加指向虚函数表的指针

复制构造函数

1) C++标准不允许复制构造函数进行值传递（递归溢出），允许常量引用

面试题1 赋值运算符函数

1) 返回引用（连续赋值），传入常量引用（高效、保护），释放已有内存（泄露），判断同一个实例
2) 异常安全
先释放内存还是先申请内存：内存不足的情况下，要保证原数据不变（不被提前释放），创建临时实例，构造函数new，new出来就交换，new不出来就抛出异常bad_alloc

1.2 数据结构

数组的效率

1) 静态数组：高时间效率，低空间效率
2) 动态数组：扩容操作增加时间复杂度（STL,vector）
3) 数组作为函数参数传递时，数组名将退化成同类型的指针

面试题3 数组中的重复数字

1) 题1找出重复数字，思路：把数字放到对应的下标的位置上，当发现对应位置已有该数字，则找到重复数字，对应空间O(1)，时间O(n)
2) 题2不修改数组找出重复数字，思路：二分法，种类二分，确定每一段内的种类出现的次数，是否为该段的种类数。
3) 明确要求时间还是要求空间效率

面试题4 二维数组查找

1) 规律，缩小查找范围

常量字符串的地址

1) 常量字符串初始化字符数组，不同数组的地址不同，原因是不同字符数组已分配了不同位置的内存以拷贝常量字符串 P49
2) 常量字符串初始化字符指针，不同指针指向的地址相同，原因是无需重新分配内存，直接指向常量在内存中的地址

面试题5 替换空格

1) 一次移动到位，O(n)，（此题不用自己扩容）
2) 考虑内存覆盖
3) 从尾部到头部，依次填入排序值

链表

1) 链表是考察重点
2) 为什么是传入指向指针的指针
要修改的是指针的内容（pHead，也就是修改一个地址），而不是修改指针指向的内容，因此传入的是指向指针的指针。
类比于，传入整型 int a 与传入其指针 int a的关系，这里是传入指针 ListNode *pHead 和指向指针的指针 ListNode **pHead。

面试题6 从尾到头打印链表

1) 栈
2) 递归 链表过长，可能导致函数调用栈溢出

void PrintListReversingly_Recursively(ListNode* pHead)
{
    if(pHead != nullptr)
    {
        if (pHead->m_pNext != nullptr)
        {
            PrintListReversingly_Recursively(pHead->m_pNext);
        }

        printf("%d\t", pHead->m_nValue);
    }
}

树

1) 二叉树特例
二叉搜索树
堆
红黑树

面试题7 重建二叉树

1) 已知前序和中序、或者已知后序和中序，都可以递归的形式，通过不断地 划分左右子树然后分别重建，这里方法更简洁。

面试题8 二叉树的下一个结点

1) 中序遍历：通过画图，分别考虑
2) case 1：存在右子树：下一个是其右子树的最左子结点（E -> K）
3) case 2：不存在右子树：
4) case 2.1：该结点是其父节点的左子结点，则下一个是其父节点（H -> D）
5) case 2.2：该结点是其父节点的右子结点，则下一个是向上溯源，直到溯源结点是其父节点的左子结点，则下一个是溯源结点的父节点（K -> A）

栈和队列

面试题9 用两个栈实现队列

1) 用两个队列实现栈

template <class T>
class CStack
{
    public: 
        CStack(void);
        ~CStack(void);
        void appendHead(const T& node);
        T deleteHead();

    private:
        queue<T> queue1;
        queue<T> queue2;
};

//入栈和出栈时，至少有一个队列为空
template <class T>
void CStack<T>::appendHead(const T& node)
{
    if(0 == queue1.size())      //向非空的队列push
        queue2.push(node);
    else if(0 == queue2.size())
        queue1.push(node);  
}

template <class T>
T CStack<T>::deleteHead()
{
    if(0 == queue1.size() && 0 == queue2.size())
        throw new exception("stack is empty");

    if(0 == queue1.size())      //从非空队列转移n-1个数据到空队列
    {
        while(1 != queue2.size())
        {
            T& data = queue2.top();
            queue2.pop();
            queue1.push(data);
        }
        T head = queue2.top();
        queue2.pop();
        return head;
    }
    else
    {
        while(1 != queue1.size())
        {
            T& data = queue1.top();
            queue1.pop();
            queue2.push(data);
        }
        T head = queue1.top();
        queue1.pop();
        return head;
    }
}

1.3 算法与数据操作

递归和循环

1) 递归优先
2) 递归，调用栈溢出，子问题重复计算
3) 自上而下的递归，可能出现子问题重复计算的问题，转而采用自下而上的循环

面试题10 斐波那契数列

1) 小青蛙，2^(n-1)
2) 覆盖矩形：f(1)=2，f(0)=0 ?

查找和排序

1) 查找重点：顺序查找、二分查找、哈希表查找、二叉排序树（二叉搜索树）
2) 排序各算法比较

排序	插入排序	冒泡排序	归并排序	快速排序
基本思想	自第二个记录开始，有序前插	相邻元素比较，逆序交换，逐遍把最大值移至最后	相邻两个/多个顺序表合并，初始每个元素都是一个顺序表	两侧依次扫描，将轴值移至正确位置
时间复杂度	n~n^2	n~n^2	nlbn	nlbn~n^2
平均时间复杂度	n^2	n^2	nlbn	nlbn
空间复杂度	1	1	n	lbn~n
应用/优化	适用于元素数量少，且基本有序，改进：分割，分别直插，基本有序后全体直插	双向起泡	相邻-一趟-递归	递归次数-空间复杂度

3) 二分查找

bool BinarySearch(const int r[], const int length, const int searchData)
{
    int start = 0;
    int end = length-1;
    int mid = (start+end)/2;

    while(start<=end)
    {
        if(r[mid]==searchData)
            return true;
        else if(r[mid]>searchData)
            end = mid - 1;
        else
            start = mid + 1;

        mid = (start+end)/2;
    }

    return false;
}

4) 快速排序

//进行一次排序
int Partition(int r[], int length, int start, int end)
{
    if((r==nullptr) || (length<0) || (start<0) || (end>=length))
        throw new std::exception("invalid parameter.");

    int pivot = r[start];   //取第一个值为轴值，挖一个坑
    int i = start;          //左侧扫描指针
    int j = end;            //右侧扫描指针

    while(i<j)
    {
        //右侧扫描：将右侧一个大值移到左侧坑位，空出一个右侧坑位
        while(i<j && pivot<r[j])
            j--;

        if(i<j)
        {
            r[i] = r[j];
            i++;
        }

        //左侧扫描：将左侧一个小值移到右侧坑位，空出一个左侧坑位
        while(i<j && pivot>r[i])
            i++;

        if(i<j)
        {
            r[j] = r[i];
            j--;
        }
    }

    r[i] = pivot;   //把坑位补齐
    return i;
}

void QuickSort(int r[], int length, int start, int end)
{
    if((r==nullptr) || (length<0) || (start<0) || (end>=length))
        throw new std::exception("invalid parameter.");

    if(start < end)
    {
        int index = Partition(r, length, start, end);
        if(start < index) 
            QuickSort(r, length, start, index-1);
        if(index < end)
            QuickSort(r, length, index+1, end);
    }
}

面试题11 旋转数组的最小数字

1) 二分，旋转0个，顺序查找，特例

回溯法

面试题12 矩阵中的路径

#include <cstring>
void* memset( void* dest, int ch, std::size_t count );
/*
Parameters
dest    -   pointer to the object to fill
ch  -   fill byte
count   -   number of bytes to fill
*/

1) 起始位置，for/for
2) 结束条件，‘\0’字符转结尾
3) 约束条件，不能重复走visited
4) 递归，周围四个格子
5) 回溯，pathLength–

面试题13 机器人的运动范围

动态规划与贪婪算法

1) 动态规划：
最优解问题
可分解成子问题，子问题的最优解组合起来得到整个问题的最优解
可能存在重复的子问题
自上而下分析，自下而上求解
2) 贪婪算法：数学证明

面试题14 剪绳子

位运算

1) 移位操作https://blog.csdn.net/weixin_42315600/article/details/80567944
2) 无符号数，左移右添0，右移左添0
有符号数，左移右添0，右移左补符号位
3) 移位效率高于乘除

面试题15 二进制中1的个数

1) 整数减1，再与原数与运算

2 代码质量

2.1 完整性

代码完整性

1) 测试用例
功能测试/边界测试/负面测试
2) 错误处理：返回值、全局变量、C++异常处理

/*使用异常*/
#include <iostream>
using namespace std;
int main()
{
    double m, n;
    cin >> m >> n;
    try 
    {
        cout << "before dividing." << endl;
        if (n == 0)
            throw - 1;  //抛出整型异常
        else if (m == 0)
            throw - 1.0;  //拋出 double 型异常
        else
            cout << m / n << endl;
        cout << "after dividing." << endl;
    }
    catch (double d) 
    {
        cout << "catch (double)" << d << endl;
    }
    catch (...) //捕获任何异常
    {
        cout << "catch (...)" << endl;
    }
    cout << "finished" << endl;
    return 0;
}

/*异常再抛出：
1、不处理
如果一个函数在执行过程中拋出的异常在本函数内就被 catch 块捕获并处理，那么该异常就不会拋给这个函数的调用者（也称为“上一层的函数”）；
如果异常在本函数中没有被处理，则它就会被拋给上一层的函数。
2、处理，但继续抛出，如下*/
catch (string s ) 
{
     cout << "CountTax error : " << s << endl;
     throw; //继续抛出捕获的异常，上级调用函数再次去捕获
}

/*C++标准异常类
exception 类的派生类:bad_typeid、bad_cast、bad_alloc、ios_base::failure、out_of_range...
C++ 程序在碰到某些异常时，即使程序中没有写 throw 语句，也会自动拋出上述异常类的对象。
这些异常类还都有名为 what 的成员函数，返回字符串形式的异常描述信息。*/
#include <exception> //exception类，异常类的基类
#include <stdexcept> //logic_error和runtime_error两个公派自exception的类
#include <new>  //bad_alloc公派自exception的类

面试题16 数值的整数次方

1) 考虑：底数为0，指数为负
2) 递归乘方
3) 位运算效率

面试题17 打印从1到最大的n位数

1) 大数问题

1、动态规划

DP问题三步走

1. 定义一个动态规划数组，明确数组元素，目的是保存计算的历史记录，节省重复计算时间
2. 确定数组间的关系
3. 找出初始值

最大连续子序列和

有一个数组，如1， －5， 8， 3， －4， 15， －8，查找其中连续和最大的相邻串的值。
在本例中，最大值为8 ＋ 3 ＋ －4 ＋ 15 ＝ 22。

1. 定义动态规划数组元素：dp[i]表示到第i个元素的最大连续子序列和。
2. 数组元素间的关系：dp[i] = max{ dp[i-1] + arc[i] , arc[i] }，即，到第i个元素的最大连续子序列和，要么是继续累加，要么就是元素本身（重新开始一轮累加）。最终的最大值是dp数组中的最大值。（可以累加一个负数，但不能在负数上累加）

3. 初始值：dp[0] = arc[0] 。

   int max_successive_sub_serial_sum(int* numbers, int size)
   {
   //定义与初始化
   int* dp = new int[size];
   dp[0] = numbers[0];
   int max_sum = dp[0];
   //推算
   for(int i=1;i<size;i++)
   {
       dp[i] = std::max( dp[i-1] + numbers[i] , numbers[i] );
       max_sum = dp[i]>max_sum ? dp[i] : max_sum;
   }
   
   delete[] dp;
   return max_sum;
   }

4. 优化空间复杂度：只维护前后两个序列和

   int max_successive_sub_serial_sum_space(int* numbers, int size)
   {   
   //定义与初始化
   int last_sum = numbers[0];
   int max_sum = last_sum;
   //推算
   for(int i=1;i<size;i++)
   {
       int cur_sum = std::max( last_sum + numbers[i] , numbers[i] );
       max_sum = cur_sum>max_sum ? cur_sum : max_sum;
       last_sum = cur_sum;
   }
   
   return max_sum;
   }

二维网格与路径

一个 m x n 的二维网格，从左上角移动到右下角，一共多少种路径，每次只能向右或向下移动一格。

1. 定义动态规划数组元素：dp[ i ][ j ] 是到达第 i 行第 j 列的路径总数，i 和 j 从0开始。
2. 数组元素间的关系：dp[ i ][ j ] = dp[ i – 1 ][ j ] + dp[ i ][ j – 1 ]，即这一点可以由上面网格和左侧网格抵达，路径总数为两路之和

3. 初始值：dp[ 0 ][ 0 ] … dp[ 0 ][ n-1 ] = 1，dp[ 0 ] … dp[ 0 ][ m-1 ][ 0 ] = 1，最左侧和最上面的网格都只有一条路径。

   int unique_path(int rows, int cols)
   {
   //定义与初始化
   int** dp = new int*[rows];
   for(int i=0;i<rows;i++)
   {
       dp[i] = new int[cols];
       memset(dp[i],0,cols);   //memset是逐字节初始化，因此只有0和-1是正常初始化
   }       
   
   for(int i=0;i<cols;i++)
       dp[0][i]=1;
   
   for(int i=0;i<rows;i++)
       dp[i][0]=1;
   //推算
   for(int i=1;i<rows;i++)
       for(int j=1;j<cols;j++)
           dp[i][j] = dp[i-1][j] + dp[i][j-1];
   //输出            
   int sum = dp[rows-1][cols-1];
   
   for(int i=0;i<rows;i++)
       delete[] dp[i];
   delete[] dp;
   
   return sum;
   }

4. 优化空间复杂度：只保存一行的记录，然后不断迭代

   int unique_path_space(int rows, int cols)
   {
   //定义与初始化
   int* dp = new int[cols];
   for(int i=0;i<cols;i++)
       dp[i] = 1;
   //推算
   for(int i=1;i<rows;i++)
       for(int j=1;j<cols;j++)
           dp[j] = dp[j] + dp[j-1];
   //输出            
   int sum = dp[cols-1];
   
   delete[] dp;
   
   return sum;
   }

二维网格与路径2 最短路径

一个 m x n 的二维网格，从左上角移动到右下角，求最短路径长度，每次只能向右或向下移动一格。

1. 定义动态规划数组元素：dp[ i ][ j ] 为到达第 i 行第 j 列的最短路径。
2. 数组元素间的关系：dp[ i ][ j ] = min{ dp[ i – 1 ][ j ] + arc[ i ][ j ] , dp[ i ][ j-1 ] + arc[ i ][ j ] }。

3. 初始值：
   dp[ 0 ][ 0 ] = arc[ 0 ][ 0 ]
   dp[ 0 ][ j ] = dp[ 0 ][ j – 1 ] + arc[ 0 ][ j ]
   dp[ i ][ 0 ] = dp[ i – 1 ][ 0 ] + arc[ i ][ 0 ]

   int unique_path_shortest(int** map, int rows, int cols )
   {
   //定义与初始化
   int** dp = new int*[rows];
   for(int i=0;i<rows;i++)
   {
       dp[i] = new int[cols];
       memset(dp[i],0,cols); 
   }
   
   dp[0][0] = map[0][0];   
   for(int i=1;i<cols;i++)
       dp[0][i] = dp[0][i-1] + map[0][i];
   for(int i=1;i<rows;i++)
       dp[i][0] = dp[i-1][0] + map[i][0];
   //推算
   for(int i=1;i<rows;i++)
       for(int j=1;j<cols;j++)
           dp[i][j] = std::min(dp[i-1][j] + map[i][j] , dp[i][j-1] + map[i][j]);
   //输出
   int sum_shortest = dp[rows-1][cols-1];
   
   for(int i=0;i<rows;i++)
       delete[] dp[i];
   delete[] dp;
   
   return sum_shortest;
   }

4. 优化空间复杂度：只保存一行的记录，然后不断迭代

   int unique_path_shortest_space(int** map, int rows, int cols )
   {
   //定义与初始化
   int* dp = new int[cols];
   dp[0] = map[0][0];  
   for(int i=1;i<cols;i++)
       dp[i] = dp[i-1] + map[0][i];
   //推算
   for(int i=1;i<rows;i++)
   {
       dp[0] = dp[0] + map[i][0];
       for(int j=1;j<cols;j++)
           dp[j] = std::min(dp[j] + map[i][j] , dp[j-1] + map[i][j]);
   }
   //输出
   int sum_shortest = dp[cols-1];
   
   delete[] dp;
   
   return sum_shortest;
   }

最长递增子序列（LIS）

最长递增子序列（LIS）

2、排序

排序	插入排序	冒泡排序	归并排序	快速排序
基本思想	自第二个记录开始，有序前插	相邻元素比较，逆序交换，逐遍把最大值移至最后	相邻两个/多个顺序表合并，初始每个元素都是一个顺序表	两侧依次扫描，将轴值移至正确位置
时间复杂度	n~n^2	n~n^2	nlbn	nlbn~n^2
平均时间复杂度	n^2	n^2	nlbn	nlbn
空间复杂度	1	1	n	lbn~n
应用/优化	适用于元素数量少，且基本有序，改进：分割，分别直插，基本有序后全体直插	双向起泡	相邻-一趟-递归	递归次数-空间复杂度

快速排序

将待排数组不断分成两部分，分别排序

int partition(int arr[], int start, int end)
{
    int mid = arr[start];
    int i = start;
    int j = end;

    while(i<j){
        //右侧扫描，将小于轴值的元素移到左侧
        while(i<j && arr[j]>mid)
            j--;
        if(i<j){
            arr[i] = arr[j];
            i++;
        }

        //左侧扫描，将大于轴值的元素移到右侧
        while(i<j && arr[i]<mid)
            i++;
        if(i<j){
            arr[j] = arr[i];
            j--;
        }
    }
    arr[i] = mid;
    return i;
}

void quick_sort(int arr[], int start, int end)
{
    int mid_index = partition(arr, start, end);
    if(start < mid_index)
        quick_sort(arr, start, mid_index-1);
    if(mid_index < end)
        quick_sort(arr, mid_index+1,end);
}

3、查找

二分查找

复杂度 lgn

bool binary_search(int arr[], int length, int num)
{
    int start = 0;
    int end = length-1;
    int mid = (start+end)/2;

    while(start<=end)
    {
        if(arr[mid]==num)
            return true;
        else if(arr[mid]>num)
            end = mid - 1;
        else
            start = mid + 1;

        mid = (start+end)/2;
    }

    return false;
}

二叉排序树

复杂度 lgn~n

myNode* searchSortBiTree(myNode* root, int k)
{
    if(root == nullptr)
        return nullptr;
    else if(root->data == k)
        return root;
    else if(root->data > k)
        return searchSortBiTree(root->leftChild, k);
    else
        return searchSortBiTree(root->rightChild, k);
}

4、二叉树

struct myNode
{
    int data;
    myNode* leftChild;
    myNode* rightChild;
    int flag;
};

树的构造与释放

按层序遍历的方式构造。

myNode* createBiTree(int values[], int length)
{
    queue<myNode*> nodes;
    int cnt = 0;

    myNode* n = new myNode;
    n->data = values[0];
    nodes.push(n);
    cnt++;

    while(cnt<length)
    {
        myNode* top = nodes.front();
        nodes.pop();

        myNode* left_n = new myNode;
        left_n->data = values[cnt];

        nodes.push(left_n);
        top->leftChild = left_n;
        cnt++;

        if(cnt==length)
            break;

        myNode* right_n = new myNode;
        right_n->data = values[cnt];
        nodes.push(right_n);
        top->rightChild = right_n;
        cnt++;
    }

    return n;
}

void releaseBiTree(myNode* n) 
{
    /*按照后序遍历的顺序释放二叉树*/
    if(n != NULL) 
    {                  
        releaseBiTree(n->leftChild); /*释放左子树*/
        releaseBiTree(n->rightChild); /*释放右子树*/
        delete n; /*删除根结点*/
    }  
}

前序遍历

// 非递归：栈
void frontPrintBiTree(myNode* root)
{
    stack<myNode*> nodes;
    myNode* n = root;

    while(n != nullptr || nodes.empty()!=1)
    {
        while(n != nullptr)
        {
            nodes.push(n);
            cout<<n->data<<" ";
            n = n->leftChild;
        }

        if(nodes.empty()!=1)
        {
            n = nodes.top();
            nodes.pop();
            n = n->rightChild;
        }
    }
}

// 递归
void frontPrintBiTree_recursion(myNode* root) 
{
    if(root == NULL) /*递归调用的边界条件*/
        return;
    else 
    {       
        cout<<root->data<<" "; /*访问根结点*/
        frontPrintBiTree_recursion(root->leftChild); /*前序递归遍历左子树*/
        frontPrintBiTree_recursion(root->rightChild); /*前序递归遍历右子树*/
    }
}

中序遍历

// 非递归：栈
void middlePrintBiTree(myNode* root)
{
    stack<myNode*> nodes;
    myNode* n = root;

    while(n != nullptr || nodes.empty()!=1)
    {
        while(n != nullptr)
        {
            nodes.push(n);
            n = n->leftChild;
        }

        if(nodes.empty()!=1)
        {
            n = nodes.top();
            nodes.pop();
            cout<<n->data<<" ";
            n = n->rightChild;
        }
    }
}

// 递归
void middlePrintBiTree_recursion(myNode* root) 
{
    if(root == NULL) /*递归调用的边界条件*/
        return;
    else 
    {       
        middlePrintBiTree_recursion(root->leftChild); /*前序递归遍历左子树*/
        cout<<root->data<<" "; /*访问根结点*/
        middlePrintBiTree_recursion(root->rightChild); /*前序递归遍历右子树*/
    }
}

后序遍历

void backPrintBiTree(myNode* root)
{
    stack<myNode*> nodes;
    myNode* n = root;

    while(n!=nullptr || nodes.empty()!=1)
    {
        while(n != nullptr)
        {
            n->flag = 1;
            nodes.push(n);
            n = n->leftChild;
        }

        while(nodes.empty()!=1 && nodes.top()->flag==2)
        {
            n = nodes.top();
            nodes.pop();
            cout<<n->data<<" ";

            if(n==root)
                return;
        }

        if(nodes.empty()!=1)
        {
            n = nodes.top();
            n->flag = 2;
            n = n->rightChild;
        }
    }
}

// 递归
void backPrintBiTree_recursion(myNode* root) 
{
    if(root == NULL) /*递归调用的边界条件*/
        return;
    else 
    {       
        backPrintBiTree_recursion(root->leftChild); /*前序递归遍历左子树*/
        backPrintBiTree_recursion(root->rightChild); /*前序递归遍历右子树*/
        cout<<root->data<<" "; /*访问根结点*/
    }
}

层序遍历

void levelPrintBiTree(myNode* root)
{
    queue<myNode*> nodes;
    myNode* n = root;
    nodes.push(n);

    while(nodes.empty()!=1)
    {
        n = nodes.top();
        nodes.pop();
        cout<<n->data<<" ";
        if(n->leftChild != nullptr)
            nodes.push(n->leftChild);
        if(n->rightChild != nullptr)
            nodes.push(n->rightChild);
    }
}

Z字遍历

void ZPrintBiTree(myNode* root)
{
    queue<myNode*> nodes_que;
    stack<myNode*> nodes_sta;
    int line = 1;
    int cnt = 0;

    queue<myNode*> nodes;
    myNode* n = root;
    nodes.push(n);

    while(nodes.empty()!=1)
    {
        //层序遍历
        n = nodes.front();
        nodes.pop();
        if(n->leftChild != nullptr)
            nodes.push(n->leftChild);
        if(n->rightChild != nullptr)
            nodes.push(n->rightChild);

        //Z字遍历
        cnt++;
        if(line%2 == 1)
        {
            nodes_que.push(n);
            if(cnt==pow(2,line-1))
            {
                line++;
                cnt=0;
                while(nodes_que.empty()!=1)
                {
                    cout<<nodes_que.front()->data<<" ";
                    nodes_que.pop();
                }
            }
        }
        else
        {
            nodes_sta.push(n);
            if(cnt==pow(2,line-1))
            {
                line++;
                cnt=0;
                while(nodes_sta.empty()!=1)
                {
                    cout<<nodes_sta.top()->data<<" ";
                    nodes_sta.pop();
                }
            }
        }       
    }
    //没打印的打印完
    while(nodes_que.empty()!=1)
    {
        cout<<nodes_que.front()->data<<" ";
        nodes_que.pop();
    }
    while(nodes_sta.empty()!=1)
    {
        cout<<nodes_sta.top()->data<<" ";
        nodes_sta.pop();
    }
}

重建二叉树：前序+中序

myNode* createBiTreeByFrontMid(int* frontValues, int* midValues, int length)
{
    if(length==0)//只针对第一次使用
        return nullptr;

    myNode* root = new myNode;//确定这一段的根节点，然后划分左右两子树
    root->data = frontValues[0];
    root->leftChild = nullptr;
    root->rightChild = nullptr;

    int i;
    for(i=0;i<length && midValues[i]!=frontValues[0];i++)
        ;

    int leftLength = i;
    int rightLength = length-i-1;

    if(leftLength>0)
        root->leftChild = createBiTreeByFrontMid(&frontValues[1], &midValues[0], leftLength);
    if(rightLength>0)
        root->rightChild = createBiTreeByFrontMid(&frontValues[leftLength+1], &midValues[leftLength+1], rightLength);

    return root;
}

重建二叉树：中序+后序

myNode* createBiTreeByBackMid(int* backValues, int* midValues, int length)
{
    if(length==0)//只针对第一次使用
        return nullptr;

    myNode* root = new myNode;//确定这一段的根节点，然后划分左右两子树
    root->data = backValues[length-1];
    root->leftChild = nullptr;
    root->rightChild = nullptr;

    int i;
    for(i=0;i<length && midValues[i]!=backValues[length-1];i++)
        ;

    int leftLength = i;
    int rightLength = length-i-1;

    if(leftLength>0)
        root->leftChild = createBiTreeByBackMid(&backValues[0], &midValues[0], leftLength);
    if(rightLength>0)
        root->rightChild = createBiTreeByBackMid(&backValues[leftLength], &midValues[leftLength+1], rightLength);

    return root;
}

二叉排序树

二叉排序树：空树或非空树，非空树满足左子树所有节点小于根节点，右子树所有节点大于根节点，左右子树又是二叉排序树。

插入

void insertSortBiTree(myNode* &root, myNode* newNode)
{
    if(root==nullptr)
        root = newNode;
    else if(root->data > newNode->data)
        insertSortBiTree(root->leftChild, newNode);
    else
        insertSortBiTree(root->rightChild, newNode);
}

构造

myNode* createSortBiTree(int data[], int n)
{
    myNode* root = nullptr;
    myNode* newNode;
    for(int i=0;i<n;i++)
    {
        newNode = new myNode;
        newNode->data = data[i];
        newNode->leftChild = nullptr;
        newNode->rightChild = nullptr;
        insertSortBiTree(root, newNode);
    }
    return root;
}

5、队列与栈

两个队列实现栈

class myStack
{
    private:
        queue<int> que1;
        queue<int> que2;

    public:
        myStack();
        ~myStack(){};

        void push(int);
        void pop();
        int top();
};

myStack::myStack(){}
void myStack::push(int data)//在非空的队列末尾添加新元素
{
    if(que1.empty())
        que2.push(data);
    else
        que1.push(data);
}

void myStack::pop()//将非空队列元素转移到空队列，留最后一个弹出
{
    if(que1.empty() && que2.empty())
        return ;

    if(que1.empty())
    {
        while(que2.size()!=1)
        {
            que1.push(que2.front());
            que2.pop();
        }
        que2.pop();
    }
    else
    {
        while(que1.size()!=1)
        {
            que2.push(que1.front());
            que1.pop();
        }
        que1.pop();
    }   
}

int myStack::top()//将非空队列元素转移到空队列，最后一个输出
{
    if(que1.empty() && que2.empty())
        return -1;

    int out;
    if(que1.empty())
    {
        while(que2.size()!=1)
        {
            que1.push(que2.front());
            que2.pop();
        }
        out = que2.front();
        que1.push(out);
        que2.pop();
    }
    else
    {
        while(que1.size()!=1)
        {
            que2.push(que1.front());
            que1.pop();
        }
        out = que1.front();
        que2.push(out);
        que1.pop();
    }
        return out;
}

两个栈实现队列

class myQueue
{
    private:
        stack<int> sta1;//存
        stack<int> sta2;//取

    public:
        myQueue();
        ~myQueue(){};

        void push(int);
        void pop();
        int front();
};

myQueue::myQueue(){}
void myQueue::push(int data)
{
    sta1.push(data);
}

void myQueue::pop()
{
    if(sta1.empty())
        return ;

    while(sta1.size()!=1)
    {   
        sta2.push(sta1.top());
        sta1.pop();
    }

    sta1.pop(); 

    while(sta2.size()!=0)   
    {
        sta1.push(sta2.top());
        sta2.pop();
    }   
}
int myQueue::front()
{
    if(sta1.empty())
        return -1;

    while(sta1.size()!=1)
    {   
        sta2.push(sta1.top());
        sta1.pop();
    }

    int out = sta1.top();
    sta2.push(out);
    sta1.pop(); 

    while(sta2.size()!=0)   
    {
        sta1.push(sta2.top());
        sta2.pop();
    }   

    return out;
}

循环队列*

相对于直线队列来讲，直线队列在元素出队后，头指针向后移动，导致删除元素后的空间无法在利用，即使元素个数小于空间大小，依然无法再进行插入，即所谓的“假上溢”。当变成循环队列之后，删除元素后的空间仍然可以利用，最大限度的利用空间。

6、图

深度优先遍历

void DFS_recursion(int curVertex, int vertexNum, vector<int>* arc, vector<int>* visited)
{
    (*visited)[curVertex] = 1;              //标记该次遍历的顶点
    cout<<curVertex<<" ";
    for(int i=0; i<vertexNum;i++)       //遍历该顶点连接的其他顶点
        if((*visited)[i]==0 && (*arc)[curVertex*vertexNum+i]==1)
            DFS_recursion(i, vertexNum, arc, visited);  
}

void DFS(int vertexNum, vector<int>* arc)
{
//初始化所有顶点未被遍历
    vector<int> visited; 
    for(int i=0;i<vertexNum; i++)
        visited.push_back(0);

//深度遍历
    for(int i=0; i<vertexNum; i++)//从第i个顶点开始的一个连通分量
    {
        if(visited[i]==0)
            DFS_recursion(i, vertexNum, arc, &visited);
    }
}

广度优先遍历

void BFS(int vertexNum, vector<int>* arc)
{
//初始化所有顶点未被遍历
    vector<int> visited; 
    for(int i=0;i<vertexNum; i++)
        visited.push_back(0);

//广度遍历
    queue<int> q;
    for(int i=0;i<vertexNum; i++)//从第i个顶点开始的一个连通分量
    {
        if(visited[i]==0)
        {
            q.push(i);
            visited[i]=1;

            while(q.empty()!=1)
            {
                int v = q.front();
                q.pop();
                cout<<v<<" ";

                for(int j=0; j<vertexNum; j++)
                    if(visited[j]==0 && (*arc)[v*vertexNum+j]==1)
                    {
                        q.push(j);
                        visited[j]=1;
                    }
            }
        }
    }
}

最小生成树

n个城市之间铺设电缆，目标使得任意两个城市互通，不同城市之间铺设电缆代价不同，求代价最小的铺设方法。

Prim

向最小生成树添加点。

void Prim(int vertexNum, vector<int>* arc)
{
//初始化候选最短边集
    vector<int> connectCost;    //候选最短边集：候选顶点到正式顶点的最小代价 代价为0，即选为正式顶点
    vector<int> connectVertex;  //候选最短边集：最小代价对应的正式顶点        找内推？

    for(int i=0;i<vertexNum;i++)
    {
        connectCost.push_back((*arc)[0*vertexNum + i]); //默认到自身的代价为0，因此0号顶点初始化即选为正式顶点
        connectVertex.push_back(0);
    }

//最小生成树：每次加入一个正式顶点，并更新候选最短边集
    for(int m=1;m<vertexNum;m++)
    {
        //遍历最短边集，找到最最短的一个
        int k=0;
        for(int i=0;i<vertexNum;i++)
            if(connectCost[i]!=0)
            {
                k=i; break;
            }

        for(int i=0;i<vertexNum;i++)
            if(connectCost[i]!=0 && connectCost[i]<connectCost[k])
                k=i;

        if(connectCost[k]==0)//找一圈发现均已添加到正式顶点中，则退出
            return ;

        cout<<"("<<connectVertex[k]<<"->"<<k<<")-cost-"<<connectCost[k]<<" ";
        //把第k个顶点加入正式顶点中
        connectCost[k]=0;   
        //看看剩下的候选节点是不是到k的代价更小
        for(int i=0;i<vertexNum;i++)
            if(connectCost[i]!=0 && connectCost[i]>(*arc)[k*vertexNum + i])
            {
                connectCost[i] = (*arc)[k*vertexNum + i];   
                connectVertex[i] = k;
            }
    }   
}

Kruscal

向最小生成树添加边。

struct Edge
{
    int vertexA;
    int vertexB;
    int cost;
};
bool cmp(const Edge &a,const Edge &b)
{
    return (a.cost) < (b.cost);
}
int find_parent(int v, vector<int> &parents)
{
    return parents[v]==v ? v : find_parent(parents[v], parents);//递归找到顶层双亲
}
void Kruscal(int vertexNum, vector<int>* arc)
{
//数据准备
    vector<Edge> edges;
    for(int i=0;i<vertexNum;i++)
        for(int j=i+1;j<vertexNum;j++)
            if((*arc)[i*vertexNum + j] < 100)
            {
                Edge edge;
                edge.vertexA = i;
                edge.vertexB = j;
                edge.cost = (*arc)[i*vertexNum + j];
                edges.push_back(edge);
            }
//Kruscal
    //边集数组初始化:升序排列
    sort(edges.begin(),edges.end(),cmp);

    //顶层双亲初始化：用于判断某一边的两顶点是否在同一个连通分量
    vector<int> parents;
    for(int i=0;i<vertexNum;i++)
        parents.push_back(i);//初始化每个顶点自成一个连通分量，其双亲为自身

    //最小生成树：每次添加一条边
    for(int i=0;i<edges.size();i++)
    {
        //拿出一条边，判断是否在同一个连通分量:判断顶层双亲是否相同
        Edge e = edges[i];
        if(find_parent(e.vertexA, parents) != find_parent(e.vertexB, parents))
        {
            parents[find_parent(e.vertexB, parents)]=find_parent(e.vertexA, parents);
            cout<<"("<<e.vertexA<<"->"<<e.vertexB<<")-cost-"<<e.cost<<" ";
        }
    }
}

7、幷查集

题目背景
若某个家族人员过于庞大，要判断两个是否是亲戚，确实还很不容易，现在给出某个亲戚关系图，求任意给出的两个人是否具有亲戚关系。
题目描述
规定：x和y是亲戚，y和z是亲戚，那么x和z也是亲戚。如果x,y是亲戚，那么x的亲戚都是y的亲戚，y的亲戚也都是x的亲戚。
输入格式
第一行：三个整数n,m,p，（n<=5000,m<=5000,p<=5000），分别表示有n个人，m个亲戚关系，询问p对亲戚关系。
以下m行：每行两个数Mi，Mj，1<=Mi，Mj<=N，表示Mi和Mj具有亲戚关系。
接下来p行：每行两个数Pi，Pj，询问Pi和Pj是否具有亲戚关系。
输出格式
P行，每行一个’Yes’或’No’。表示第i个询问的答案为“具有”或“不具有”亲戚关系。

1. 幷查集的两种操作：查询是否在同一集合，合并不同集合
2. 幷查集的思想：每个集合确定一个代表元素，形成一个树状结构，代表元素为根节点，其他元素为子节点。集合的合并就是一个集合的根节点成为另一个集合的子节点。集合的查询就是不断找父节点，直到找到根节点，判断根节点是否相同。
3. 幷查集应用：最小生成树的Kruscal方法。
4. 幷查集的初始化，合并和查询

   int parent[NMAX]
   void init(int n)    //初始化为本身
   {
   for(int i=0;i<n;i++)
       parent[i]=i;
   }
   int find(int i)
   {
   return parent[i]==i ? i : find(parent[i]); //不断向上查询父节点，直到所属结合的根节点
   }
   int merge(int i, int j)
   {
   parent[find(i)] = find(j);//把i所属集合的根节点，变成j所属集合根节点的子节点
   }

5. 压缩：查询过程中将其父节点换成根节点，减少递归次数，因为只在查询时压缩，因此未必每个集合除了根节点，全是叶子节点

   int find(int i)
   {
   return parent[i]==i ? i : ( parent[i] = find(parent[i]) ); //查询过程中将其父节点换成根节点
   }

6. 按秩合并：把简单树合并到复杂树
   算法学习笔记(1) : 并查集

8、字符串

有效字符串

一个看着不错的答案

bool checkValidString(String s) {
    int low = 0; // 表示*号都作为右括号时，左括号的数量
    int hight = 0; // 表示*都作为左括号时，左括号的数量
    // 如果hight < 0 说明*都作为左括号了，还是不够抵消不了右括号
    // 如果low > 0 说明*号都作为右括号了，还是抵消不了括号的值
    for (int i=0; i<s.length();i++){
        char tmp = s.charAt(i);
        if (tmp == '(') {
            low++;
            hight++;
        } 
        else if (tmp == ')') {
            if (low > 0) {
                low--;
            }
            hight--;
        } else if (tmp == '*') {
            if (low > 0) {
                low--;
            }
            hight++;
        }

        if (hight < 0) {
            return false;
        }
    }
    return low == 0;
}

9、数组

差分数组 前缀和

class Solution {
public:
    vector<int> corpFlightBookings(vector<vector<int>>& bookings, int n) {

        vector<int> data;
        for(int i=0; i<n;i++)
            data.push_back(0);

        for(auto i : bookings)
        {
            data[i[0]-1]+=i[2];
            if(i[1]<n)
                data[i[1]]-=i[2];
        }

        for(int i=1; i<n;i++)
            data[i]+=data[i-1];

        return data;
    }
};

测试

代码

int main()
{
//动态规划
    int a[]{1,-5,8,3,-4,15,-8};
    std::cout<<"max_successive_sub_serial_sum: "<<max_successive_sub_serial_sum(a,7)<<std::endl;
    std::cout<<"max_successive_sub_serial_sum_space: "<<max_successive_sub_serial_sum_space(a,7)<<std::endl;

    std::cout<<"unique_path: "<<unique_path(3,7)<<std::endl;
    std::cout<<"unique_path_space: "<<unique_path_space(3,7)<<std::endl;

    int rows=3, cols=3;
    int** map = new int*[rows];
    for(int i=0;i<rows;i++)
    {
        map[i] = new int[cols];
        for(int j=0;j<cols;j++)
            map[i][j]=j;
    }
    std::cout<<"unique_path_shortest: "<<unique_path_shortest(map, rows, cols)<<std::endl;
    std::cout<<"unique_path_shortest_space: "<<unique_path_shortest_space(map, rows, cols)<<std::endl;
//排序    
    int arr[8]{8,7,6,5,4,4,2,1};
    quick_sort(arr,0,7);
    std:cout<<"quick_sort: ";
    for(int i=0;i<8;i++)
        std::cout<<arr[i]<<" ";
    std::cout<<std::endl;
//查找    
    int arr1[9]{8,7,6,5,4,4,2,1,11};
    std::cout<<"binary_search: "<<binary_search(arr, 8,5)<<std::endl;
    std::cout<<"binary_search: "<<binary_search(arr1, 9,3)<<std::endl;

//二叉树
    int arr2[9]{8,7,6,5,4,4,2,1,11};
    myNode* root = createBiTree(arr2, 9);
    cout<<"frontPrintBiTree: ";
    frontPrintBiTree(root);
    cout<<endl<<"middlePrintBiTree: ";
    middlePrintBiTree(root);
    cout<<endl<<"backPrintBiTree: ";
    backPrintBiTree(root);
    cout<<endl<<"frontPrintBiTree_recursion: ";
    frontPrintBiTree_recursion(root);
    cout<<endl<<"middlePrintBiTree_recursion: ";
    middlePrintBiTree_recursion(root);
    cout<<endl<<"backPrintBiTree_recursion: ";
    backPrintBiTree_recursion(root);
    cout<<endl<<"levelPrintBiTree: ";
    levelPrintBiTree(root);
    cout<<endl<<"ZPrintBiTree: ";
    ZPrintBiTree(root);
    releaseBiTree(root);

    int arr2_front[9]{8,7,5,1,11,4,6,4,2};
    int arr2_mid[9]{1,5,11,7,4,8,4,6,2};
    int arr2_back[9]{1,11,5,4,7,4,2,6,8};
    myNode* root1 = createBiTreeByFrontMid(arr2_front, arr2_mid, 9);
    cout<<endl<<"createBiTreeByFrontMid backPrintBiTree: ";
    backPrintBiTree(root1);
    releaseBiTree(root1);
    myNode* root2 = createBiTreeByBackMid(arr2_back, arr2_mid, 9);
    cout<<endl<<"createBiTreeByBackMid frontPrintBiTree: ";
    frontPrintBiTree(root2);
    releaseBiTree(root2);
    cout<<endl;

//队列与栈
    myStack s;
    s.push(1);
    s.push(2);
    s.push(3);
    s.push(4);
    s.push(5);
    cout<<"s.top():"<<s.top()<<endl;
    s.pop();
    cout<<"s.top() after pop():"<<s.top()<<endl;

    myQueue q;
    q.push(1);
    q.push(2);
    q.push(3);
    q.push(4);
    q.push(5);
    cout<<"q.front():"<<q.front()<<endl;
    q.pop();
    cout<<"q.front() after pop():"<<q.front()<<endl;

//图
    int vertexNum = 10;
                  //0 1 2 3 4  5 6 7 8 9 无向图 两个连通分量 
    int arc_a[10][10]={0,0,1,0,1, 1,0,0,0,0, 
               0,0,0,1,0, 0,0,0,0,0,
               1,0,0,0,0, 0,0,0,0,0,
               0,1,0,0,0, 0,0,0,0,0,
               1,0,0,0,0, 0,0,0,1,0,

               1,0,0,0,0, 0,1,1,0,0,
               0,0,0,0,0, 1,0,0,0,0,
               0,0,0,0,0, 1,0,0,0,0,
               0,0,0,0,1, 0,0,0,0,1,
               0,0,0,0,0, 0,0,0,1,0}; 

    vector<int> arc;
    for(int i=0;i<vertexNum;i++)
        for(int j=0;j<vertexNum;j++)
            arc.push_back(arc_a[i][j]);
    cout<<"DFS: ";
    DFS(vertexNum, &arc);   
    cout<<endl<<"BFS: ";
    BFS(vertexNum, &arc);   
    cout<<endl;

    vertexNum = 6;
               //0 1 2 3 4  5 6 7 8 9 无向连通图
    int arc_b[6][6]={0, 4,  100,    100,    5,  2,   
                  4,    0,  2,  100,    100,    1,
                 100,   2,  0,  10, 100,    3,
                 100,   100,    10, 0,  1,  4,
                 5, 100,    100,    1,  0,  8,
                 2, 1,  3,  4,  8,  0}; 
    arc.clear();
    for(int i=0;i<vertexNum;i++)
        for(int j=0;j<vertexNum;j++)
            arc.push_back(arc_b[i][j]);
    cout<<"Prim:";
    Prim(vertexNum, &arc);
    cout<<endl<<"Kruscal:";
    Kruscal(vertexNum, &arc);
    cout<<endl;

//二叉排序树
    int sortBiTree[]{80,40,70,90,100,15,81,77,89,96,1};
    myNode* sortRoot = createSortBiTree(sortBiTree, 11);
    cout<<"createSortBiTree frontPrintBiTree: ";
    frontPrintBiTree(sortRoot);
    cout<<endl;
    myNode* getNode = searchSortBiTree(sortRoot, 96);
    cout<<"searchSortBiTree 96:"<<(getNode!=nullptr)<<endl;
    getNode = searchSortBiTree(sortRoot, 77);
    cout<<"searchSortBiTree 77:"<<(getNode!=nullptr)<<endl;
    getNode = searchSortBiTree(sortRoot, 2);
    cout<<"searchSortBiTree 2:"<<(getNode!=nullptr)<<endl;
    releaseBiTree(sortRoot);    
    return 0;
}

输出

max_successive_sub_serial_sum: 22
max_successive_sub_serial_sum_space: 22
unique_path: 28
unique_path_space: 28
unique_path_shortest: 3
unique_path_shortest_space: 3
quick_sort: 1 2 4 4 5 6 7 8 
binary_search: 1
binary_search: 0
frontPrintBiTree: 8 7 5 1 11 4 6 4 2 
middlePrintBiTree: 1 5 11 7 4 8 4 6 2 
backPrintBiTree: 1 11 5 4 7 4 2 6 8 
frontPrintBiTree_recursion: 8 7 5 1 11 4 6 4 2 
middlePrintBiTree_recursion: 1 5 11 7 4 8 4 6 2 
backPrintBiTree_recursion: 1 11 5 4 7 4 2 6 8 
levelPrintBiTree: 8 7 6 5 4 4 2 1 11 
ZPrintBiTree: 8 6 7 5 4 4 2 11 1 
createBiTreeByFrontMid backPrintBiTree: 1 11 5 4 7 4 2 6 8 
createBiTreeByBackMid frontPrintBiTree: 8 7 5 1 11 4 6 4 2 
s.top():5
s.top() after pop():4
q.front():1
q.front() after pop():2
DFS: 0 2 4 8 9 5 6 7 1 3 
BFS: 0 2 4 5 8 6 7 9 1 3 
Prim:(0->5)-cost-2 (5->1)-cost-1 (1->2)-cost-2 (5->3)-cost-4 (3->4)-cost-1 
Kruscal:(1->5)-cost-1 (3->4)-cost-1 (0->5)-cost-2 (1->2)-cost-2 (3->5)-cost-4
createSortBiTree frontPrintBiTree: 80 40 15 1 70 77 90 81 89 100 96 
searchSortBiTree 96:1
searchSortBiTree 77:1
searchSortBiTree 2:0

1 图的结构

1.1 图的逻辑结构

1. 图（graph）由顶点（vertex）的非空集合和顶点之间的边（edge）的集合组成。

边	无向(undirected)边、有向边
图	无向图、有向图、稠密(dense)图、稀疏(sparse)图 、子图(subgraph)
简单图	不存在顶点到自身的边，不存在重复出现的边
完全图	任意两顶点存在边，无向完全图（数量为 (n-1)n/2 ）、有向完全图（双向 数量为 (n-1)n ）
邻接与依附	无向：顶点互为邻接(adjacent)点，边依附(adhere)于两顶点；有向：起点邻接到终点，终点是起点的邻接点
度	无向：依附于顶点的边的数量；有向：出度（作为起点）、入度（作为终点）
权值与网	权值(weight)：边的意义；网：带权值的图（有向网、无向网）
路径	路径、路径长度、回路（路径起终点相同）、简单路径（无重复顶点）、简单回路（只重复起终点）
连通图 连通分量	无向图中，任意两顶点存在路径；非连通图的极大连通子图为连通分量
强连通图 强连通分量	有向图中，任意两顶点双向存在路径；非强连通图的极大强连通子图为强连通分量
生成树	连通图的极小连通子图（n个顶点和最少的边）、有向图的子图（全部顶点且仅一顶点入度为0，其余入度为1）
生成森林	连通分量的生成树，组成森林

1. 遍历的方式
   ♥ 寻找邻接点
   ♥ 设置访问标志，避免重复访问
   ♥ 多个邻接点选择方式不同，分为深度优先（推荐使用栈）和广度优先（推荐使用队列）

1.2 图的存储结构

邻接矩阵（栅格）

1. 深度优先遍历

   //1、初始化各顶点未被访问
       for(int i=0;i<vertexNum;i++)
           visited[i]=0;
   //2、第一个顶点入栈
       stack<int> st;
       for(int i=0;i<vertexNum;i++)
           if(visited[i]==0)
           {
               st.push(i);     
               DFS(st.top());
               st.pop();
           }
   //3、递归
       void DFS(int v)
       {
           visited[v]=1;               //确认已遍历
           for(int i=0;i<vertexNum;i++)
           {
               if((visited[i]==0) && (arc[v][i]==1))//找到该顶点的邻接点
               {
                   st.push(i);
                   DFS(st.top());
                   st.pop();
               }
           }
       }

2. 广度优先遍历

   //1、初始化各顶点未被访问
       for(int i=0;i<vertexNum;i++)
           visited[i]=0;
   //2、第一个顶点入队
       queue<int> que;
       for(int i=0;i<vertexNum;i++)
           if(visited[i]==0)
           {
               que.push(i);
               visited[i]=1;
               break;
           }
   //3、循环：依次入队，依次处理
       while(!que.empty()) 
       {
           int v = que.front();
           for(int i=0;i<vertexNum;i++)
           {
               if((visited[i]==0) && (arc[v][i]==1))//找到该顶点的邻接点
               {
                   que.push(i);
                   visited[i]=1;
               }
           }
           que.pop();
       }

1.3 测试程序

邻接矩阵 深度优先遍历

针对无向连通图。

#include <iostream>
#include <stack>

using namespace std;

int vertexNum=5;
int visited[5]={0};
int arc[5][5]={0,1,0,1,1,   //邻接矩阵
               1,0,1,0,1,
               0,1,0,0,0,
               1,0,0,0,0,
               1,1,0,0,0};
stack<int> st;

void DFS(int v)
{
    visited[v]=1;               //确认已遍历
    for(int i=0;i<vertexNum;i++)
    {
        if((visited[i]==0) && (arc[v][i]==1))//找到该顶点的邻接点
        {
            st.push(i);
            cout<<"push:"<<i<<" "<<st.size()<<endl; 
            DFS(st.top());
            st.pop();
            cout<<"pop:"<<i<<" "<<st.size()<<endl;
        }
    }
}

int main()
{
    //1、初始化各顶点未被访问
        for(int i=0;i<vertexNum;i++)
            visited[i]=0;
    //2、第一个顶点入栈
        for(int i=0;i<vertexNum;i++)
        {
            if(visited[i]==0)
            {
                st.push(i); 
                cout<<"push:"<<i<<" "<<st.size()<<endl; 
                DFS(st.top());
                st.pop();
                cout<<"pop:"<<i<<" "<<st.size()<<endl;  
            }
        }

}

邻接矩阵 广度优先遍历

针对无向连通图。

#include <iostream>
#include <queue>

using namespace std;

int vertexNum=5;
int visited[5]={0};
int arc[5][5]={0,1,0,1,1,   //邻接矩阵
               1,0,1,0,1,
               0,1,0,0,0,
               1,0,0,0,0,
               1,1,0,0,0};

int main()
{
    //1、初始化各顶点未被访问
        for(int i=0;i<vertexNum;i++)
            visited[i]=0;
    //2、第一个顶点入队
        queue<int> que;
        for(int i=0;i<vertexNum;i++)
            if(visited[i]==0)
            {
                que.push(i);
                visited[i]=1;
                cout<<"push:"<<i<<" "<<que.size()<<endl;
                break;
            }

    //3、循环:依次入队，依次处理
        while(!que.empty()) 
        {
            int v = que.front();
            cout<<"front:"<<que.front()<<" "<<que.size()<<endl; 

            for(int i=0;i<vertexNum;i++)
            {
                if((visited[i]==0) && (arc[v][i]==1))//找到该顶点的邻接点
                {
                    que.push(i);
                    visited[i]=1;
                    cout<<"push:"<<i<<" "<<que.size()<<endl;    
                }
            }
            que.pop();
        }        
}

2 最小生成树

2.1 最小生成树（MST，minimal spanning tree）

无向连通网的生成树中，权值代价最小的生成树，称为最小权重生成树，简称最小生成树。
（无向图，连通图，权值与网，生成树）
应用：n个城市之间铺设电缆，目标使得任意两个城市互通，不同城市之间铺设电缆代价不同，求代价最小的铺设方法。这是一道面试题:(

2.2 Prim算法

基本思想

1. 设无向连通网 G=(V,E) ，最小生成树 T=(U,TE)
2. T 初值： U={v0} ，v0∈V，TE 为空
3. 重复：
   对每一个 V-U 中的顶点（设n个顶点），遍历 U 中顶点，找到一条最短边，n个顶点形成一个候选最短边集
   在候选最短边集中，找到最最短的一条边
   把 V-U 中的这一点，放入 U ，同时，把对应边放入 TE ，直到 V 和 U 相等。
4. 算法复杂度O(n2)，适于稠密连通网。
5. 关键：候选最短边集（基本过程的case和代码的shortEdge数组）

基本过程

————————->

1. 初始状态
   
2. 将点 v5 和边 (v0,v5)2 加入最小生成树
   
3. 将点 v1 和边 (v5,v1)1 加入最小生成树
   
4. 将点 v2 和边 (v1,v2)2 加入最小生成树
   
5. 将点 v3 和边 (v5,v3)4 加入最小生成树
   
6. 将点 v4 和边 (v3,v4)1 加入最小生成树
   

代码（非测试）

//1、初始化辅助数组，辅助数组用于标记 V-U中顶点 到 U中顶点 的 最短代价和对应顶点，功能类似于基本过程中的cost
for(int i=1;i<vertexNum;i++)
{
    //初始取v0加入集合U，因此最短代价依次是与v0的代价值，对应顶点为i和v0
    shortEdge[i].lowcost = arc[0][i];   //V-U中顶点 到 U中顶点 的最短代价
    shortEdge[i].adjvex = 0;            //V-U中顶点 到 U中顶点 的对应顶点
}

//2、加入集合的方式
shortEdge[0].lowcost = 0;               //代价为0时，认为改顶点已经在最小生成树中了，这里v0已经在其中了

//3、循环
for(int i=1;i<vertexNum;i++)            //这里是循环vertexNum-1次，每次添加一个顶点到U
{
    //3.1、根据辅助数组确定最最短边
    int k;                              //最最短边对应的 V-U中顶点
    for(int j=1;j<vertexNum;j++)        //初始化k
        if(shortEdge[j].lowcost != 0)
        { k=j; break; }
    for(int j=1;j<vertexNum;j++)        //更新k
        if(shortEdge[j].lowcost != 0 && shortEdge[j].lowcost < shortEdge[k].lowcost)
            k=j;

    //3.2、加入集合
    shortEdge[k].lowcost = 0;

    //3.3、更新辅助数组
    for(int j=1;j<vertexNum;j++)
        if(shortEdge[j].lowcost > arc[k][j])//比较新加入的顶点，是否代价更小（类似于RRT*的重选父节点）
        {
            shortEdge[j].lowcost = arc[k][j];   //V-U中顶点 到 U中顶点 的最短代价
            shortEdge[j].adjvex = k;            //V-U中顶点 到 U中顶点 的对应顶点
        }

}

2.3 Kruscal算法

基本思想

1. 设无向连通网 G=(V,E) ，最小生成树 T=(U,TE)
2. T 初值： U=V ，TE 为空，即每个顶点自成一个连通分量
3. 将 E 中权值有小到大排序
4. 重复：
   在 E 中选择最短边，判断该边的两顶点是否在两个连通分量上——边集数组
   是：加入 TE
   否：舍弃此边
5. 算法复杂度O(elbe)，适于稀疏连通网。
6. 关键：边集数组，如何判断两个点是否在不同的连通分量（利用边集数组）。

基本过程

— —
——

代码（非测试）

//1、定义、初始化、排序从小到大的边集数组
struct Edge
{
    Edge(){}
    Edge(int from_,int to_,int cost_,bool ok_):from(from_),to(to_),cost(cost_),ok(ok_){}
    int from;
    int to;
    int cost;
    bool ok;
};

Edge edges[edgeNum];
edges[0]=Edge{0,1,4,false};//...

bool cmp(const Edge &a,const Edge &b)
    return a.cost<b.cost;
sort(edges,edges+edgeNum,cmp);//按权值排序

//2、遍历边集数组
for(int i=0;i<edgeNum;i++)
{
    //2.1、判断该边的两个顶点是否在一个连通分量中
    //2.2、合并两个连通分量
    if(find_parent(edges[i].from)!=find_parent(edges[i].to))
    {
        merge(edges[i].from, edges[i].to); 
        edges[i].ok=true;
    }
    else
        edges[i].ok=false;
}

2.4 测试程序

Prim算法

#include <iostream>

int vertexNum=6;
int arc[6][6]={100,4,100,100,5,2,   //邻接矩阵
               4,100,2,100,100,1,
               100,2,100,10,100,3,
               100,100,10,100,1,4,
               5,100,100,1,100,8,
               2,1,3,4,8,100};

struct Cost
{
    int lowcost;
    int adjvex;
};

int main()
{

    Cost shortEdge[vertexNum];

    //1、初始化辅助数组，辅助数组用于标记 V-U中顶点 到 U中顶点 的 最短代价和对应顶点，功能类似于基本过程中的cost
    for(int i=1;i<vertexNum;i++)
    {
        //初始取v0加入集合U，因此最短代价依次是与v0的代价值，对应顶点为i和v0
        shortEdge[i].lowcost = arc[0][i];               //V-U中顶点 到 U中顶点 的最短代价
        shortEdge[i].adjvex = 0;                        //V-U中顶点 到 U中顶点 的对应顶点
    }

    //2、加入集合的方式
    shortEdge[0].lowcost = 0;                           //代价为0时，认为改顶点已经在最小生成树中了，这里v0已经在其中了

    //3、循环
    for(int i=1;i<vertexNum;i++)                        //这里是循环vertexNum-1次，每次添加一个顶点到U
    {
        //3.1、根据辅助数组确定最最短边
        int k;                                          //最最短边对应的 V-U中顶点
        for(int j=1;j<vertexNum;j++)                    //初始化k
            if(shortEdge[j].lowcost != 0)
            { 
                k=j; break; 
            }
        for(int j=1;j<vertexNum;j++)                    //更新k
            if(shortEdge[j].lowcost != 0 && shortEdge[j].lowcost < shortEdge[k].lowcost)
                k=j;

        std::cout<<"get vertex="<<k<<" with "<<shortEdge[k].adjvex<<",cost="<<shortEdge[k].lowcost<<std::endl;
        //3.2、加入集合
        shortEdge[k].lowcost = 0;

        //3.3、更新辅助数组
        for(int j=1;j<vertexNum;j++)
            if(shortEdge[j].lowcost > arc[k][j])        //比较新加入的顶点，是否代价更小（类似于RRT*的重选父节点）
            {
                shortEdge[j].lowcost = arc[k][j];       //V-U中顶点 到 U中顶点 的最短代价
                shortEdge[j].adjvex = k;                //V-U中顶点 到 U中顶点 的对应顶点
            }

    }

    return 0;

}

Kruscal算法

#include <iostream>
#include <algorithm>

int vertexNum=6;
int edgeNum=10;
int arc[6][6]={100,4,100,100,5,2,   //邻接矩阵
               4,100,2,100,100,1,
               100,2,100,10,100,3,
               100,100,10,100,1,4,
               5,100,100,1,100,8,
               2,1,3,4,8,100};
int parent[6];

//边集数组
struct Edge
{
    Edge(){}
    Edge(int from_,int to_,int cost_,bool ok_):from(from_),to(to_),cost(cost_),ok(ok_){}
    int from;
    int to;
    int cost;
    bool ok;
};

//边集数组：成员排序方式
bool cmp(const Edge &a,const Edge &b)
{
    return (a.cost) < (b.cost);
}

//幷查集：查找顶层双亲
int find_parent(int v)
{
    return parent[v]==v ? v : find_parent(parent[v]);
}

//幷查集：修改顶层双亲
void merge(int from,int to)
{
    parent[find_parent(to)]=find_parent(from);
}

int main()
{
//1、定义、初始化、排序从小到大的边集数组
    Edge edges[edgeNum];
    edges[0]=Edge{0,1,4,false};
    edges[1]=Edge{0,4,5,false};
    edges[2]=Edge{0,5,2,false};
    edges[3]=Edge{1,2,2,false};
    edges[4]=Edge{1,5,1,false};
    edges[5]=Edge{2,3,10,false};
    edges[6]=Edge{2,5,3,false};
    edges[7]=Edge{3,4,1,false};
    edges[8]=Edge{3,5,4,false};
    edges[9]=Edge{4,5,8,false};

    std::sort(edges,edges+edgeNum,cmp);//按权值排序

//2、初始化每个顶点的顶层双亲节点，用于判断是否在一个集合
    for(int i=0;i<vertexNum;i++)
        parent[i]=i;

//3、遍历边集数组
    for(int i=0;i<edgeNum;i++)
    {
        //3.1、判断该边的两个顶点是否在一个连通分量中
        //3.2、合并两个连通分量
        if(find_parent(edges[i].from)!=find_parent(edges[i].to))
        {
            merge(edges[i].from, edges[i].to); 
            edges[i].ok=true;
        }
        else
            edges[i].ok=false;

        std::cout<<"get edge: from "<<edges[i].from<<" to "<<edges[i].to
                 <<" cost:"<<edges[i].cost<<" ok:"<<edges[i].ok<<std::endl;
        for(int i=0;i<vertexNum;i++)
            std::cout<<i<<" parent:"<<find_parent(i)<<std::endl;
    }

    return 0;
}

3 最短路径问题

3.1 Dijkstra算法

1. 移步这里https://blog.csdn.net/fangfang12138/article/details/107949923

1 树的结构

1.1 树的逻辑结构

1) 树的定义与特点

		说明
树	子树、空树、有序树、无序树、森林	空树无结点，有序无序看子树交换顺序是不是同一棵
点	叶子结点、分支结点、根结点、孩子结点、双亲结点、兄弟结点、堂兄弟结点
度	结点的度、树的度	度即分叉数，最大的结点的度即树的度
路	路径长度、祖先、子孙	分支数为路径长度，路径若存在必唯一
层	结点的层数、树的深度/高度	层数从1开始
结点的层序编号		从上到下、从左到右、从1开始、连续自然数编号

2) 树的遍历
前序遍历：从根结点，从左到右前序遍历子树，ABEFCGHID
后序遍历：从叶子结点，从左到右后序遍历子树，EFBHIGCDA
层序遍历：按层序编号，ABCDEFGHI

1.2 树的存储结构

1) 双亲表示法：每个结点，除自身数据外，还记录双亲结点的下标，方便求解双亲，但求结点的孩子需要遍历。

2) 孩子链表表示法：每个结点，除自身数据外，还记录一个链表，链表记录从左到右孩子结点的下标，优缺点有双亲表示法相反

3) 孩子兄弟表示法：每个结点，除自身数据外，还记录第一个孩子结点和右侧的第一个兄弟结点

1.3 二叉树的逻辑结构

1) 二叉树的定义与说明

		说明
二叉树	左子树、右子树、空二叉树	左右子树互不相交，结点的度最大为2
斜树	左斜树、右斜树	所有分支都只有左子树/右子树，斜树 =》结点个数等于树的深度
满二叉树		所有分支结点都有左右子树，所有叶子结点都在同一层
完全二叉树		按层序编号，倒序从满二叉树中去掉任意数量结点，满二叉树=》完全二叉树

2) 二叉树的性质
3) 二叉树的遍历
前序遍历：从根结点，从左到右前序遍历左右子树，ABDGECF
中序遍历：先遍历根结点的左子树，访问根结点，遍历右子树，DGBEACF ，在遍历子树的过程中，也是按照：先左，然后结点，然后右，（NDGBEANCF）
后序遍历：从叶子结点，从左到右后序遍历左右子树，GDEBFCA
层序遍历：按层序编号，ABCDEFG

1.4 二叉树的存储结构（递归遍历）

1) 顺序存储结构
根据层序编号，使用一维数组存储。适用于完全二叉树，对于非完全二叉树，需要补充空结点生成完全二叉树，存在空间浪费的情况，特别是右斜树。
2) 二叉链表
对比树结构的孩子链表示法，结点使用二叉链表，每个结点包括数据域 和 左右两个指针域指向左右分支结点。
（二叉链表的遍历、构造和析构都可以递归的方式进行，以结点指针为空作为结束标志）
（二叉链表的构造：将二叉树进行扩展，使得原二叉树的结点的度都是2，然后再递归创建）

pLeftChild	data	pRightChild

template <class T>
struct BiNode{
    T data;       
    BiNode<T> *lchild, *rchild;
};

//构造
template <class T>
BiNode<T> *BiTree<T>::Creat(BiNode<T> *bt) 
{
    char ch;
    cout<<"请输入创建一棵二叉树的结点数据："<<endl;
    cin>>ch;
    /*'#'代表空二叉树*/
    if(ch == '#') 
        return NULL;
    else 
    { 
        bt = new BiNode<T>; /*生成新结点*/
        bt->data = ch;
        bt->lchild = Creat(bt->lchild); /*递归创建左子树*/
        bt->rchild = Creat(bt->rchild); /*递归创建右子树*/
    } 
    return bt;
}

//析构
template <class T>
void BiTree<T>::Release(BiNode<T> *bt) 
{
    /*按照后序遍历的顺序释放二叉树*/
    if(bt != NULL) 
    {                  
        Release(bt->lchild); /*释放左子树*/
        Release(bt->rchild); /*释放右子树*/
        delete bt; /*删除根结点*/
    }  
}

//前序遍历
template <class T>
void BiTree<T>::PreOrder(BiNode<T> *bt) 
{
    if(bt == NULL) /*递归调用的边界条件*/
        return;
    else 
    {       
        cout<<bt->data<<" "; /*访问根结点*/
        PreOrder(bt->lchild); /*前序递归遍历左子树*/
        PreOrder(bt->rchild); /*前序递归遍历右子树*/
    }
}

//中序遍历
template <class T>
void BiTree<T>::InOrder(BiNode<T> *bt) 
{
    if(bt == NULL)  
        return; /*递归调用的边界条件*/             
    else 
    {   
        InOrder(bt->lchild); /*中序递归遍历左子树*/
        cout<<bt->data<<" "; /*访问根结点*/
        InOrder(bt->rchild); /*中序递归遍历的右子树*/
    }
}

//后序遍历
template <class T>
void BiTree<T>::PostOrder(BiNode<T> *bt) 
{
    if(bt == NULL)  
        return; /*递归调用的边界条件*/
    else 
    {   
        PostOrder(bt->lchild); /*后序递归遍历左子树*/
        PostOrder(bt->rchild); /*后序递归遍历右子树*/
        cout<<bt->data<<" "; /*访问根结点*/
    }
}

//层序遍历
template <class T>
void BiTree<T>::LevelOrder(BiNode<T> *bt)
{
    BiNode<T> *q;
    queue<BiNode<T> *> Q;
    if(bt == NULL) 
        return;
    else 
    {
        Q.push(bt); /*bt入队*/
        /*队列非空时循环*/
        while(Q.empty() != 1) 
        {
            q = Q.pop(); /*队头出队*/
            cout<<q->data<<" "; /*访问队头*/    
            if(q->lchild != NULL) /*如果队头有左孩子，左孩子入队*/
                Q.push(q->lchild);      
            if(q->rchild != NULL) /*如果队头有右孩子，右孩子入队*/
                Q.push(q->rchild);
        }
    }
}

3) 三叉链表
在二叉链表的基础上，增加指向双亲结点的指针。

pLeftChild	data	pRightChild	pParent

2 二叉树应用

2.1 非递归遍历二叉树

//前序
template <class T>
void BiTree<T>::preOrder(BiNode<T> *bt) 
{
    stack<BiNode<T> *> S;//使用栈保存访问过的结点
    while(bt != NULL || S.empty() != 1)
    {
        while(bt != NULL)
        {
            cout<<bt->data<<endl;
            S.push(bt);
            bt = bt->lchild;
        }
        if(S.empty() != 1)
        {
            bt = S.pop();
            bt = bt->rchild;
        }
    }
}

//中序
template <class T>
void BiTree<T>::inOrder(BiNode<T> *bt) 
{
    stack<BiNode<T> *> S;//使用栈保存访问过的结点
    while(bt != NULL || S.empty() != 1)
    {
        while(bt != NULL)   //bt == NULL 说明左子树为空，或左子树已访问完
        {
            S.push(bt);
            bt = bt->lchild;
        }
        if(S.empty() != 1)
        {
            bt = S.pop();
            cout<<bt->data<<endl;//先打印左子树，再打印结点
            bt = bt->rchild;
        }
    }
}

//后序1：使用标志位，给结点绑定一个flag，访问完左子树，flag为1，左右子树都访问完后，flag为2
template <class T>
void BiTree<T>::postOrder(BiNode<T> *bt) 
{
    stack<Element> S;
    Element e;
    /*bt不为空或者栈不为空*/
    while(bt != NULL || S.Empty() == 0) 
    {
        while(bt != NULL) 
        {
            e.ptr = bt;
            e.flag = 1;
            S.posh(e);
            bt = bt->lchild;
        }
        /*栈不为空并且栈顶的flag为2时，出栈并访问*/
        while((S.empty() != 1)&&(S.top()).flag == 2) 
        {
            e = S.Pop();
            cout<<e.ptr->data<<" ";
        }
        /*栈不为空，并且栈顶的flag为1时，将栈顶的flag更改为2，并访问其右孩子*/
        if(S.empty() != 1) 
        {
            e = S.pop();
            bt = e.ptr->rchild;
            e.flag = 2;
            S.push(e);
        }
    }
}

//后序2：不使用标志位
template <class T>
void BiTree<T>::postOrder(BiNode<T> *bt) 
{
    stack<BiNode<T> *> s;
    stack<BiNode<T> *> output;
    s.push(bt);

    while (!s.empty()) 
    {
        bt = s.pop();
        output.push(bt);

        if (bt->lchild)
            s.push(bt->lchild);
        if (bt->rchild)
            s.push(bt->rchild);
    }

    while (!output.empty()) 
    {
        bt = output.pop();
        cout << bt->data << " ";
    }
}

2.2 重建二叉树

//由前序序列和中序序列
template <class T>
BiNode<T>* BiTree<T>::Rebuild(T *preOrder, T *inOrder, int n) 
{
    if(n == 0) 
        return NULL;

    T c = preOrder[0];/*获得前序遍历的第一个结点*/ 
    BiNode<T> *node = new BiNode<T >;/*创建根结点*/
    node->data = c;
    node->lchild = NULL;
    node->rchild = NULL;

    int i;
    for(i = 0; i < n && inOrder[i] != c; i++)/*在中序遍历序列中寻找根结点的位置*/
        ;

    int lenLeft = i;/*左子树结点个数*/ 
    int lenRight = n - i - 1; /*右子树结点个数*/

    if(lenLeft > 0)/*左子树不为空，递归重建左子树*/ 
        node->lchild = Rebuild(&preOrder[1], &inOrder[0], lenLeft);

    if(lenRight > 0) /*右子树不为空，递归重建右子树*/
        node->rchild = Rebuild(&preOrder[lenLeft+1], &inOrder[lenLeft+1], lenRight);

    return node;
}

//由后序序列和中序序列
template <class T>
BiNode<T>* BiTree<T>::Rebuild(T *postOrder, T *inOrder, int n) 
{
    if(n == 0) 
        return NULL;

    T c = postOrder[n-1];/*获得后序遍历的最后一个结点*/ 
    BiNode<T> *node = new BiNode<T>; /*创建根结点*/
    node->data = c;
    node->lchild = NULL;
    node->rchild = NULL;

    int i;
    for(i = 0; i < n && inOrder[i] != c; i++)/*在中序遍历序列中寻找根结点的位置*/
        ;

    int lenLeft = i;/*左子树结点个数*/
    int lenRight = n - i - 1; /*右子树结点个数*/

    if(lenLeft > 0)/*左子树不为空，重建左子树*/ 
        node->lchild = Rebuild(&postOrder[0], &inOrder[0], lenLeft);

    if(lenRight > 0)/*右子树不为空，重建右子树*/
        node->rchild = Rebuild(&postOrder[lenLeft], &inOrder[lenLeft+1], lenRight);
    return node;
}

3 二叉搜索树 / 堆 / 红黑树

系列参考

1) 《数据结构（C++）边学边做》任平红等著
2) 《剑指offer》何海涛著
3) http://bookshadow.com/weblog/2015/01/19/binary-tree-post-order-traversal/

1 顺序表

1) 定义顺序表模板类

const int MAXSIZE= 100; //顺序表最大容量
template <class T>
class SeqList
{
    public:
        SeqList() {length = 0;}             //构造函数：建立空顺序表
        SeqList(T d[], int len);            //构造函数：建立长度为len，数据为d[]的顺序表
        ~SeqList(){};                       //析构函数

        int GetLength(){return length};     //表长：获取表长
        T GetValue(int index);              //查找：根据索引获取对应数据
        int GetIndex(T x);                  //查找：根据值获得对应的索引
        void Insert(int index, T x);        //插入：在i位置，插入数据x
        void Delete(int index);             //删除：删除i位置数据
        void PrintList();                   //遍历

    private:
        int length;                         //表长
        T data[MAXSIZE];                    //存放列表元素（数组）
}

2) 成员函数实现

template <class T>
SeqList<T>::SeqList(T d[], int len) //构造函数：建立长度为len，数据为d[]的顺序表
{
    if(len<0 || len>MAXSIZE)
        throw "参数非法";

    length = len;

    for(int i=0;i<len;i++)
        data[i] = d[i];
}

template <class T>
T SeqList<T>::GetValue(int index)       //查找：根据索引获取对应数据
{
    if(index<0 || index>length-1)
        throw "参数非法";
    else
        return data[index];
}

template <class T>
int SeqList<T>::GetIndex(T x)           //查找：根据值获得对应的索引
{
    for(int i=0;i<length;i++)
        if(data[i] == x)
            return i

    return -1;
}

template <class T>
void SeqList<T>::Insert(int index, T x)//插入：在i位置，插入数据x
{
    if(length+1 > MAXSIZE)
        throw "列表已满，无法插入";

    if(index<0 || index>length)
        throw "参数非法";

    for(int i=length-1;i>index-1;i--)
            data[i+1] = data[i];        

    data[index] = x;
    length+=1;
    return;
}

template <class T>
void SeqList<T>::Delete(int index)      //删除：删除i位置数据
{
    if(0 == length)
        throw "列表为空，无法删除";

    if(index<0 || index>length-1)
        throw "参数非法";

    for(int i=index;i<length-1;i++)
            data[i] = data[i+1];

    length--;
}

template <class T>
void SeqList<T>::PrintList()            //遍历
{
    for(int i=0;i<length;i++)
        std::cout<<data[i]<<" ";
}

3) 有序表重复元素删除

template <class T>
void DelDup(SeqList<T> &L)
{
    for(int i=0;i<L.GetLength()-1;i++)
        while(L.GetValue(i)==L.GetValue(i+1))       //删除元素后，后续元素前移，因此依然是比较 i和i+1
            L.Delete(i+1);
}

4) 有序表合并

//不修改原表，假设合成的表有足够的空间容纳两个表的元素
template <class T>
void Merge(const SeqList<T> &L1, const SeqList<T> &L2，SeqList<T> &L3)
{
    int len1 = L1.GetLength();
    int len2 = L2.GetLength();
    int i=j=0;  //两个指针
    int k=0;
    while(i<len1 && j<len2)
    {
        if(L1[i] <= L2[j])
            L3.Insert(k++,L1[i++]);
        else
            L3.Insert(k++,L2[j++]);
    }
    while(i<len1)
        L3.Insert(k++,L1[i++]);

    while(j<len2)
        L3.Insert(k++,L2[j++]);

}

//在原表的基础上，添加，假设原表有足够的空间容纳添加的表
template <class T>
void Merge(SeqList<T> &L1, const SeqList<T> &L2)
{
    int len1 = L1.GetLength();
    int len2 = L2.GetLength();
    int i=len1-1;
    int j=len2-1;
    int k=len1+len2-1;

    while(i>-1 && j>-1)
    {
        if(L1[i]>L2[j])
            L1[k--]=L1[i--];
        else
            L1[k--]=L2[j--];        
    }

    while(j>-1)
        L1[k--]=L2[j--];
}

2 链表

链表与顺序表

1) 空间上，顺序表静态分配内存，结构紧凑，但需要预估内存大小，不够灵活， 另外空间连续性会导致存储碎片
2) 时间上，顺序表按位存取快，两者按值存取均为O(n)；顺序表增删数据效率不高，链表的增删时间主要花费在指针移动

单链表

data	next

表达：链表由结点构成，以头结点为链表起始，结点包括数据和下一结点的指针，头结点数据为null，尾指针为null（为使得空链表与非空链表中结点表达方式的统一，引入头结点）

1) 定义链表模板类

template <class T>
class LinkList
{
    public:
        LinkList();                         //构造函数：只有头结点的空单链表
        LinkList(T d[], int len);           //构造函数：以数组元素建立链表
        ~LinkList(){};                      //析构函数

        int GetLength();                    //表长
        T GetValue(int index);              //查找：根据索引获取对应数据
        int GetIndex(T x);                  //查找：根据值获得对应的索引
        void Insert(int index, T x);        //插入：在i位置，插入数据x
        void Delete(int index);             //删除：删除i位置数据
        void PrintList();                   //遍历

    private:
        Node<T>* first;     //头指针
}

2) 成员函数实现

表长/查找/插入/删除/构造/析构：遍历即工作指针的后移与非空的判断，在遍历的基础上计数、查找、删除，注意删除和析构中，先备份再delete

template <class T>
LinkList<T>::LinkList()             //构造函数：只有头结点的空单链表
{
    first = new Node<T>;            //生成头结点
    first->next = NULL;             //指向空值
}

template <class T>
LinkList<T>::LinkList(T d[], int len)//构造函数：以数组元素建立链表，这个算法的核心就是不断申请新的节点，申请后，再考虑数据域和指针域，最后考虑首尾的处理
{
    if(len<1)
        throw "参数非法";

    Node<T> *p,*q;
    first = new Node<T>;            //头结点，注意不是首元结点
    p = first;  

    for(int i=0;i<len;i++)
    {
        q= new Node<T>;             //新申请一个结点
        q->data = d[i];             //写入数据
        p->next = q;                //把地址给前一个结点的指针域
        p = q;                      //把当前节点更新成上一个节点
    }   
    p->next = NULL;                 //单链表的尾指针为空
}

template <class T>
LinkList<T>::~LinkList()            //析构函数
{
    Node<T> *q;
    while(first != NULL) 
    {
        q = first;
        first = first->next;
        delete q;
    }
}

template <class T>
void LinkList<T>::PrintList()       //遍历
{
    Node<T> *p = first->next;
    while(p != NULL)
    {
        cout<<p->data;
        p = p->next;
    }
}

template <class T>
int LinkList<T>::GetLength()        //表长
{
    int cnt = 0;
    Node<T> *p = first->next;
    while(p != NULL)
    {
        cnt++;
        p = p->next;
    }
    return cnt;
}

template <class T>
T LinkList<T>::GetValue(int index)  //查找：根据索引获取对应数据
{
    int i = 0;
    Node<T> *p = first->next;
    while(p!=NULL)
    {
        if(i == imdex)
            return p->data;

        i++;
        p = p->next;
    }

    throw "参数非法";
}

template <class T>
int LinkList<T>::GetIndex(T x)      //查找：根据值获得对应的索引
{
    int index = 0;
    Node<T> *p = first->next;
    while(p!=NULL)
    {
        if(p->data == x)
            return index;

        index++;
        p = p->next;
    }

    return -1;
}

template <class T>
void LinkList<T>::Insert(int index, T x)//插入：在i位置，插入数据x
{
    int i = 0;
    Node<T> *p = first->next;
    while(p!=NULL)
    {
        if((i+1) == index)      //指针定位到index结点的前一个结点
            break;

        i++;
        p = p->next;
    }

    if(p==NULL)
        throw "参数非法";

    Node<T> *q = new Node<T>;
    q->data = x;
    q->next = p->next;
    p->next = q;
}

template <class T>
void LinkList<T>::Delete(int index) //删除：删除i位置数据
{
    int i = 0;
    Node<T> *p = first->next;
    while(p!=NULL)
    {
        if((i+1) == index)      //指针定位到index结点的前一个结点
            break;

        i++;
        p = p->next;
    }

    if(p==NULL)
        throw "参数非法";

    Node<T> *q = p->next;   //备份待删除的结点的指针
    p->next = q->next;
    delete q;   
}

3) 单链表原地逆置

//接着在类里定义逆置函数
//另存当前点的后继，然后修改为前驱
template <class T>
void LinkList<T>::Reverse() //原地逆置
{
    Node<T> *pLast, *pCur, *pNext;
    pLast = first;          //上一个结点：初始化为头结点
    pCur = first->next;     //当前结点：初始化为首元结点
    pNext = NULL;

    while(pCur != NULL)
    {
        pNext = pCur->next;     //保存下一个结点的指针
        pCur->next = pLast;     //当前点把前驱作为自己的后继

        pLast = pCur;           //更细当前点和前一个点
        pCur = pNext;
    }
    first->next = pLast;
}   

4) 单链表有序性、排序、合并、删除重复

1) 有序性

template <class T>
int LinkList<T>::IsOrdering() 
{
    Node<T> *p,*q = NULL;
    p = first->next;
    int flag = 1;
    if(p) 
        q = p->next;

    /*比较相邻的结点是否逆序*/
    while((p != NULL) && (q != NULL)) 
    {
        if(p->data > q->data) 
        {
            flag = 0;
            break;
        }
        else
        {
            p = q;
            q = q->next;
        }
    }
    return flag;
}

2) 排序

//保留首元结点，从第二个结点开始依次前插
//每插入一个值，都从first开始遍历当前排好序的链表
template <class T>
void LinkList<T>::Sort() 
{
    Node<T> *p,*q,*r,*s;
    p = first->next;

    if(p != NULL) 
    {
        //在首元结点后断开
        q = p->next;
        p->next = NULL; 

        //依次将q插入到有序单链表中
        while(q)
        {
            r = q->next;    //保存后继
            s = first;      //从first开始遍历
            while((s->next) && ((s->next->data) < (q->data))) //符合顺序则s后移，逆序则退出循环，执行插入操作
                s = s->next;

            q->next = s->next;
            s->next = q;

            //q后移
            q = r; 
        }
    }    
}

3) 有序表合并

template <class T>
void Merge(LinkList<T> &L1, LinkList<T> &L2) 
{
    /*将单链表L1和L2合并至L1*/
    Node<T> *first1, *first2;
    first1 = L1.GetFirst(); /*获取单链表L1的头指针*/
    first2 = L2.GetFirst(); /*获取单链表L2的头指针*/ 
    Node<ElemType> *p,*q,*r;
    r = first1; /*单链表L1的尾指针*/
    p = first1->next;
    q = first2->next;
    while(p != NULL && q != NULL) 
    {
        if(p->data <= q->data) 
        {
            r->next = p;
            r = p;
            p = p->next;
        }
        else 
        {
            r->next = q;
            r = q;
            q = q->next;
        }
    }
    while(p != NULL) 
    {
            r->next = p;
            r = p;
            p = p->next;
    }
    while(q != NULL) 
    {
            r->next = q;
            r = q;
            q = q->next;
    }
    r->next = NULL;
}

4) 删除重复

//两个指针，比较，相等则删除后一个，删除之前要另存下下个结点
template <class T>
void LinkList<T>::LinkListDelDup() 
{
    Node<T> *p,*q,*r;
    p = first->next;
    while(p != NULL) 
    {
        q = p->next;
        while(q != NULL && p->data == q->data) 
        {
            /*删除q*/
            r = q->next;
            p->next = q->next;
            delete q;
            q = r;
        }
        p = p->next;
    }
}

5) 无序表删除重复

//对每个结点，比较后面的所有节点，只向后比较，不向前比较，O(n2)
template <class T>
void LinkList<T>::LinkListDelNormalDup() 
{
    Node<T> *p,*q,*r;
    p = first->next;
    while(p != NULL)
    {
        q = p;
        while(q->next != NULL) 
        {
            if(p->data == q->next->data) 
            {
                r = q->next;                
                q->next = r->next; 
                delete r;
            }
            else
                q = q->next;    
        }
        p = p->next;
    }
}

6) 循环链表:尾标志指向头结点

双向链表

prior	data	next

1) 插入： 指针修改顺序，未被处理的部分不断开
2) 删除

系列参考

1) 《数据结构（C++）边学边做》任平红等著
2) 《剑指offer》何海涛著