基础数据结构与算法

Posted on 2025-05-01

基础数据结构与算法

第一章：线性结构

顺序表

对于一个顺序表，我们可以不需要因为结点逻辑关系额外增加开销，逻辑结构和存储结构一致；
做到$O(1)$随机存取访问与修改，但是只能在$O(n)$实现删除与插入，平均移动约一半的元素，并且预先分配空间过小容易溢出，过大容易浪费；

顺序表模板类

#pragma once
template<typename T> class SeqList{//动态顺序表,希望能实现类似vector容器
private:
    #define _OVERFLOW 3
    #define _ERROR -1
    #define _OUT_OF_RANGE -1
    #define _MAXSIZE 1024
    #define _FAIL -1
    T *elem;
    int _size=0;
    int _capacity=0;

public:
    SeqList(){//无参数构造
        elem=new T[_MAXSIZE];
        if(!elem){
            std::cout<<"OVERFLOW"<<std::endl;
            exit(_OVERFLOW);
        }
        _size=0;
        _capacity=_MAXSIZE;
    }

    ~SeqList(){//销毁
        delete[] elem;
        elem=nullptr;//避免悬垂指针
    }

    const void clear(){//清空，保持头部指针和容量不变
        _size=0;
        _capacity=_MAXSIZE;
    }

    int size()const{//返回容器的大小
        return _size;
    }

    bool empty()const{
        return _size==0;
    }

    const T& at(int index)const{
        if(index<0||index>_size){
            std::cout<<"ERROR:ArrayIndexOutOfBoundsException"<<std::endl;
            exit(_OUT_OF_RANGE);
        }
        return *(elem+index);
    }
    const T* begin()const{//第一个元素的指针，并没有整个iterator
        return elem;
    }
    const T* end()const{//末尾元素的下一个位置
        return elem+_size;
    }
    const T& front()const{//头部元素的引用
        return *elem;
    }
    const T& back()const{//末尾元素的引用
        return *(elem+_size-1);
    }
    T& operator[] (int index){//重载[]访问与修改元素，不给出越界提示
        return *(elem+index);
    }
    const T& operator[](int index)const{//允许对const对象的访问
        return *(elem+index);
    }
    const T* find(const T* beg,const T* end,const T& value)const{
        for(const T* tmp=beg;tmp!=end;tmp++){
            if(*tmp==value) return tmp;
        }
        return this->end();//找不到返回表尾，默认分支
    }
    int capacity()const{return _capacity;}

    SeqList(const SeqList& x) {//拷贝构造
        _size = x.size();
        _capacity = x.capacity();
        elem = new T[_capacity];
        if(!elem){
            std::cout<<"OVERFLOW"<<std::endl;
            exit(_OVERFLOW);
        }
        for (int i = 0; i < x.size(); i++) {
            elem[i] = x[i];
        }
    }

    bool operator==(const SeqList&r)const{
        if(this->_size!=r._size) return false;//容量不同其他相同应该视为相同的顺序表
        for(int i=0;i<this->_size;i++) {
            if(this->elem[i]!=r.elem[i]) return false;
        }
        return true;
    }
    bool operator!=(const SeqList&r)const{
        return !((*this)==r);
    }
    SeqList<T>& operator=(const SeqList<T>& x){
        if(this!=&x){
            delete[] elem;
            _size=x.size();
            _capacity=x.capacity();
            elem=new T[_capacity];
            if(!elem){
                std::cout<<"OVERFLOW"<<std::endl;
                (_OVERFLOW);
            }
            for(int i=0;i<x.size();i++){
                elem[i]=x[i];
            }
            return *this;
        }
    }

    //在顺序表L中第i个位置数据元素之前插入数据元素e，可以实现头尾插入 
    void insert(int pos,T value){
        if(_size==_capacity) {//size变化可能会触发扩容机制
            _capacity*=2;
            T* upd_elem=new T[_capacity];
            if(!elem){
                std::cout<<"OVERFLOW"<<std::endl;
                exit(_OVERFLOW);
            }
            for(int i=0;i<_size;i++){
                upd_elem[i]=elem[i];
            }
            delete elem;
            elem=upd_elem;
        }
        if(pos>=_MAXSIZE) {
            std::cout<<"OVERFLOW"<<std::endl;
            exit(_OVERFLOW);
        }
        else if(pos<0||pos>_size) {
            std::cout<<"ERROR:ArrayIndexOutOfBoundsException"<<std::endl;
            exit(_OUT_OF_RANGE);
        }
        for(int i=_size;i>pos;i--){
            elem[i]=elem[i-1];
        }//增加数据应该从后面开始移动
        elem[pos]=value;
        _size++;
    }
    void push_back(T& value){
        insert(this->_size,value);
    }
 
    //删除指定位置pos的数据
    void erase(int pos){
        if(pos>=_MAXSIZE) {
            std::cout<<"OVERFLOW"<<std::endl;
            exit(_OVERFLOW);
        }
        else if(pos<0||pos>=_size) {
            std::cout<<"ERROR:ArrayIndexOutOfBoundsException"<<std::endl;
            exit(_OUT_OF_RANGE);
        }
        for(int i=pos;i<_size;i++){
            elem[i]=elem[i+1];
        }
        _size--;
    }
};

单链表

对于一个头部带哑结点的单链表，指针必须遍历整个单链表，最坏时间复杂度为$O(N)$，在查找效率上比顺序表更慢；
尽管对于单链表的插入与删除操作的复杂度为$O(N)$，但是省去了对元素的移动操作，并且在已知附近结点的情况下只需要修改几个指针就可以完成插入操作，在频繁插入与删除首尾位置，单链表表现出比顺序表更加优越的性能；

对于单链表的各个变形都稍微分析优缺点：

不带头部的单链表：在实际实现中，对于结点是否是第一个需要反复判断，特殊处理；并且由于有头部节点的存在，使得空表和只有头结点的表处理起来一样；
循环单链表:

在最后一个结点指针域存放第一个结点的地址，形成一个环；

判断遍历是否终止条件改为 p->next==head;
带尾指针的循环单链表

在合并两个循环单链表的场景可以将复杂度将为$O(1)$;
双向链表：是STL中 std::list容器的底层实现，支持高效寻找前驱的操作，是以时间换空间的策略；
静态链表：喜闻乐见的比赛专用，码量小，静态空间；

下面给出单链表和双向链表的模板类实现：

单链表模板类

#pragma once
template<typename T>class ListNode{
private:
    ListNode<T>* _next;
    T _data;
public:
    friend class List;//声明友元
    ListNode(const T& item,const ListNode<T>& ptr=nullptr){
        this->_data=item; 
        this->_next=ptr;
    }
    ListNode(const T& item=0) {this->_data=item;this->_next=nullptr;}
    ~ListNode(){//无需检查next为空
        _data=0;
        delete _next;
        _next=nullptr;
    }
    T& data(){return this->_data;}
    void data(const T item){this->_data=item;}
    ListNode<T>* next(){return this->_next;}
    void next(const ListNode<T>* ptr){this->_next=ptr;}
};

//头节点是哑结点(数据域不包含有效信息)、记录长度的单链表实现
template<typename T>class List{
private:
    ListNode<T>* _head;
    int _size;
    #define _INVALID_INDEX -1
    #define _FAIL -1
    #define _OVERFLOW 3
public:
    friend class ListNode;
    List(){
        this->_head=new ListNode<T>;
        _head->data=0;
        _head->next=nullptr;
        _size=0;
    }//无参数构造

    ListNode<T>* head()const{return this->_head;}
    const int size()const{return this->_size;}
    bool empty()const{return (this->_head)->_next==nullptr;}

    const T& at(int pos){//查找位置在pos的结点,返回引用
        ListNode<T>* tmp=this->_head;
        int cnt=0;
        while(tmp){
            if(cnt==pos) return tmp->_data;
            cnt++;
            tmp=tmp->_next;
        }
        std::cout<<"INVALID_INDEX"<<std::endl;
        exit(_INVALID_INDEX); 
    }
    T& operator[](int pos){
        ListNode<T>* tmp=this->_head;
        int cnt=0;
        while(tmp){
            if(cnt==pos) return tmp->_data;
            cnt++;
            tmp=tmp->_next;
        }
        exit(_INVALID_INDEX); 
    }
    const T&  operator[](int pos)const{//查找位置在pos的结点
        ListNode<T>* tmp=this->_head;
        int cnt=0;
        while(tmp){
            if(cnt==pos) return tmp->_data;
            cnt++;
            tmp=tmp->_next;
        }
        exit(_INVALID_INDEX); 
    }

    ListNode<T>* at_pos_ptr(int pos){
        ListNode<T>* tmp=this->_head;
        int cnt=0;
        while(tmp){
            if(cnt==pos) return tmp;
            cnt++;
            tmp=tmp->_next;
        }
        std::cout<<"INVALID_INDEX"<<std::endl;
        exit(_INVALID_INDEX); 
    }

    ListNode<T>* find(int value){
        ListNode<T>* tmp=_head->_next;
        while(tmp){
            if(tmp->_data==value) return tmp;
            else tmp=tmp->_next;
        }
        if(!tmp) {
            std::cout<<"FAIL"<<std::endl;
            exit(_FAIL);
        }
    }

    void insert(int pos,T value){
        ListNode<T>* pre=this->at(pos-1);//若pos不合法将退出
        ListNode<T>* tmp =new ListNode<T>(value); //参数构造结点实例
        tmp->_next=pre->_next;
        pre->_next=tmp;
        this->_size++;//头节点记录长度发生变化
    }//尽管复杂度为O(n)，但是速度仍然比插入顺序表整体移动元素更快
    
    void erase(int pos){
        ListNode<T>* pre=this->at(pos-1);
        ListNode<T>* now=pre->_next;
        ListNode<T>* nxt=now->_next;
        pre->next=nxt;
        delete now;
    }


    List(const List<T>& x){
        this->_head=new ListNode<T>;
        ListNode<T>* tmp=_head->_next;
        ListNode<T>*tmpx=x._head->_next;
        while(tmp){
            tmp->_data=tmpx._data;
            tmp->_next=tmpx._next;
            tmp=tmp->_next;
            tmpx=tmpx._next;
        }
        return *this;
    };//拷贝构造,不应该连头结点一起拷贝
    bool operator==(const List<T>&r)const{
        if(this->_size!=r._size) return false;
        ListNode<T>* local=this->_head;
        ListNode<T>* out=r._head;
        while(out!=nullptr){
            if(out->data!=local->data)return false;
            out=out->_next;
            local=local->_next;
        }
        return true;
    } 
    bool operator!=(const List<T>&r)const{
        return !((*this)==r);
    }
    const List<T>& operator=(const List<T>& x){
        if(this!=&x){
            delete _head;
            _head=new ListNode<T>;
            ListNode<T>* tmp=_head->_next;
            ListNode<T>*tmpx=x._head->_next;
            while(tmp){
                tmp->_data=tmpx._data;
                tmp->_next=tmpx._next;
                tmp=tmp->_next;
                tmpx=tmpx._next;
            }
            return *this;
        }
    }


    List(T& elem[],int n){
        for(int i=n-1;i>=0;i--){
            this->insert(1,elem[i]);
        }
    }

    void clear(){
        while(_head->_next) erase(1);
    }
    ~List(){
        this->clear();
        delete this->_head;
        this->_head=nullptr;
        this->_size=0;
    }
};

双向链表模板类（未测试）

template<typename T>
class Node {
public:
    T data;
    Node<T>* next;
    Node<T>* prev;

    Node(T data = T(0), Node<T>* next = nullptr, Node<T>* prev = nullptr)
        : data(data), next(next), prev(prev) {}
};

template<typename T>
class List {
private:
    Node<T>* head;
    Node<T>* tail;
    int size;

public:
    //default constructor
    List(): head(nullptr), tail(nullptr), size(0){}
    
    //add data to the front of the list
    void push_front(T data) {
        Node<T>* node = new Node<T>(data, head);
        if (head != nullptr)
            head->prev = node;
        head = node;
        if (tail == nullptr)
            tail = head;
        size++;
    }
    
    //add data to the back of the list
    void push_back(T data) {
        Node<T>* node = new Node<T>(data, nullptr, tail);
        if (tail != nullptr)
            tail->next = node;
        tail = node;
        if (head == nullptr)
            head = tail;
        size++;
    }

    //remove data from the front of the list
    void pop_front() {
        if (head == nullptr)
            return;
        Node<T>* node = head;
        head = node->next;
        if (head != nullptr)
            head->prev = nullptr;
        delete node;
        size--;
    }

    //remove data from the back of the list
    void pop_back() {
        if (tail == nullptr)
            return;
        Node<T>* node = tail;
        tail = node->prev;
        if (tail != nullptr)
            tail->next = nullptr;
        delete node;
        size--;
    }

    //return number of the elements in the list
    int length() {
        return this->size;
    }

    //return true if the list is empty, false otherwise
    bool empty() {
        return size == 0;
    }

    //destructor
    ~List() {
        while (head != nullptr) {
            Node<T>* node = head;
            head = node->next;
            delete node;
        }
        tail = nullptr;
        size = 0;
    }
};

顺序栈

实现从略（留坑，期末要复习不完力）；

链式栈

实现从略（留坑，期末要复习不完力）；

队列

实现从略（留坑，期末要复习不完力）；

查找

顺序查找

依次检查顺序表的每一个关键字，空间复杂度为$O(1)$,时间复杂度为$O(N)$；

等概率查找成功的$ASL=\frac{\sum_{i=1}^{n}(n-i+1)}{n}=\frac{n+1}{2}$;

考虑查找失败情况，$ASL=\frac{n+\frac{n+1}{2}}{2}=\frac{3n+1}{4}$;

索引查找

将数据分成两个关键字，对总体分块，对每一个块使用顺序查找；

不考虑查找失败的情况下，假设数据分成$b$块，每块数据有$s$个元素,近似看成$N=sb$；

$ASL=\frac{b+1}{2}+\frac{s+1}{2}=\frac{1}{2}(s+\frac{n}{s})+1=O(\sqrt{n})$;

明显在分$\sqrt{n}$块时算法最优；

哈希查找

为降低查找的时间复杂度，可以考虑建立储存数据与储存地址的哈希函数（映射关系）：假设要将$m$个关键字$K_i$存储到长度为$n$的表中，建立的哈希函数为$H$，$1\le H(K_i)\le n$,一个计算简单的哈希函数很难保证是单射，想要避免哈希冲突很难保证简单好算，下提供几种建立哈希函数的思路：

线性哈希：$H(K)=aK+b$;
数字分析哈希：
- 对关键字按照某种规则分解成一组数字（比如按位数），对组内每一个数字哈希，再重新组合得到新的值作为哈希值；
- 需要关键字有某种规律才好；
平方取中：
- 将关键字平方得到的，取中间几位作为哈希值；
- 处理比较连续的数据效果比较好，冲突可能性低；
折叠哈希：
- 将关键字拆分成等长的部分，按照某种规则（预处理）加起来得到哈希值；当然可以多次折叠形成多哈；
- 处理大数据映射到小数据效果较好，对相似数据处理较差；
模数哈希：
- $H(K)=K \ mod\ p$，$p$可以取小于$m$的质数（如果有因子$d$,关键字模$p$的余数都是$d$的倍数，增加了冲突的可能性；
- 目前用的比较多，可以多重哈希；
- 可能需要解决自然溢出等哈希冲突的问题；
比如写一个对长度不超过8的字符串小写字母单词存储进长度为11000的表的哈希函数
1
2
3
4
5
int myHash(const char* x){
int hashval=0;
while(*x!='\0') hashval+=(hashval<<5)+*x-'a';
return hashval;
}

哈希冲突处理

开放地址

对于$H(K_0)=K_0 %p=A$,现发生第$i$次冲突$H(K_1)=A$,引入再散列$d_i$，$H(K_1)=(A+d_i)%p$;

线性探测再散列：$d_i=1,2,…,p-1$;
二次探测再散列：$d_i=1^2,-1^2,2^2,-2^2,…,(p/2)^2,-(p/2)^2$;
伪随机探测再散列：$d_i=i\cdot H_i(Key)$;

多哈希

设置$n$级哈希函数，由第$i$级哈希函数处理第$i$次哈希函数的地址；

链地址法

将冲突记录到同一个线性链表中；

公共溢出法

设置HashTable和OverTable；
OverTable顺序记录每一个溢出的值；

哈希表查找、性能分析

排序

接下来的排序默认为不减序；

直接插入排序

保持左边序列有序，插入当前的数到左边序列合适的位置；

具体来说，假设$a[0]…a[i-1]$有序,依次比较当前数$now=a[i]$与$a[i-1],a[i-2],…a[0]$.假设$a[k]>now$，将$a[k]$后移一位，更新$a[k] \gets now$,否则停止循环；

空间复杂度为$O(1)$，时间复杂度为$O(N^2)$;

适用于数据量较小的、或者几乎已经排好序的数组，此时几乎只需要遍历一遍，时间复杂度接近$O(N)$;

插入排序

void insert_sort(int *s,int n){//插入排序
    for(int i=1;i<n;i++){
        if(s[i]>=s[i-1]) continue;
        int tmp=s[i];
        for(int j=i-1;s[j]>tmp&&j>=0;j--){
            s[j+1]=s[j];
            s[j]=tmp;
        }
        
    }
}

Shell排序

Shell排序是一种不稳定的排序，平均复杂度为$O(N^{1.25})$,但可以适当地选取序列，使得复杂度升到$O(N^2)$,根据不同间距序列的选取，使得Shell排序有着不同的复杂度表现；

Shell排序可以分成三步：

选取一个间距$L$，将原来序列划分为间距为$L$的所有子序列；
对每个子序列进行插入排序；
减小要选取的间距；

Shell排序

void ShellSort(int *s,int n){
    int l=1;
    while(l<n) l=3*l+1;
    while(l>=1){
        for(int i=l;i<n;i++){
            for(int j=i;j>=l&&s[j-l]>s[j];j-=l){
                std::swap(s[j],s[j-l]);
            }
        }
        l/=3;
    }
    return ;
}

冒泡排序

在每一趟冒泡中，比较相邻两个元素，若逆序则交换，（优化）记录每一趟冒泡最后一次交换发生的位置；

冒泡排序是稳定的，但是时间复杂度为$O(N^2)$,不优化之前的总比较次数和交换次数为$\frac{1}{2}N(N-1)$;

冒泡排序

void bubble_sort(int *s,int n){
    int idx=n-1;
    while(idx>0){
        int expos=0;
        for(int i=0;i<idx;i++){
            if(s[i]>s[i+1]){
                std::swap(s[i],s[i+1]);
                expos=i;
            }
        }
        idx=expos;
    }
    retrun ;
}

选择排序

每一趟找到前面无序部分中最大的数，将它交换到后面有序部分的头部；

选择排序是不稳定的，最坏复杂度为$O(N^2)$

选择排序

void selection_sort(int *s,int n){
    for(int i=n;i>1;i--){
        int Maxpos=0;
        for(int j=0;j<i;j++){
            if(s[j]>s[Maxpos]) Maxpos=j;
        }
        std::swap(s[Maxpos],s[i-1]);
    }
    return ;
}

基数排序

第二章：递归与分治

主方法

对$T(N)=aT(N/b)+f(N),N>b$,那么分三类讨论；
$$
T(N) = \begin{cases}\Theta(N^{\log_b a}) & f(N) = O(N^{\log_b a-\epsilon}),\epsilon > 0 \ \Theta(f(N)) & f(N) = \Omega(N^{\log_b a+\epsilon}),\epsilon\ge 0\ \Theta(N^{\log_b a}\log^{k+1} N) & f(N)=\Theta(N^{\log_b a}\log^k N),k\ge 0 \end{cases}
$$
第一种情况表明合并子问题复杂度很低，解决问题主要复杂度来源是解决若干个子问题；

第二种情况表明合并子问题复杂度很高，解决问题主要复杂度来源是合并子问题；

第三种情况是合并和解决子问题比较均衡，递归深度为$logN$;

二分查找

表有序，不经常变动且查找频繁，记录按关键字排序
维护查找范围的左端点和右端点，每次检查中间的数是否在表中；
如果在表中，则查找成功；如果不在，那么按大小缩小到具体要查找左边区间还是右边区间；

使用二分查找关键字如下（找不到返回-1）：

typedef bool(*fun)(int*,int,int) ;
bool judg(int*a,int m,int key){
    return a[m]==key;
}
int Find(int*a,int n,fun judg,int key){
    int l=0;
    int r=n-1;
    while(r>=l){
        int m=l+((r-l)>>1);
        if(judg(a,m,key)) return m;
        if(key<a[m]) r=m-1 ;
        else l=m+1;
    }
    return -1;
}
int main(){
    int n=11;
    int a[11]={2,7,10,12,16,20,26,32,44,56,62};
    int idx=Find(a,n,judg,32);
    std::cout<<idx<<" ";
    return 0;
}

二分查找的性能分析：

假设有序表长度为$n=2^k-1$,二叉判定树高$k=log_2(n+1)$，每个记录查找概率相等，第$i$层有$2^{i-1}$个结点；

平均查找长度为$\frac{1}{n}(\sum_{i=1}^{k}i\cdot2^{i-1})=\frac{n+1}{n}log_2(n+1)-1$;

即复杂度为$O(logN)$

归并排序

divide：将数组分成均匀两半
sort：递归解决每个半部分
merge：把两部分合并起来组成一个新的排序

一个简单的对整数数组归并排序如下：

void MergeSort(int*a,int l,int r){
    if(r-l<1) return ;
    if(r-l==1) {
        if(a[l]>a[r]) std::swap(a[l],a[r]);
        return ;
    }

    int m=l+((r-l)>>1);
    MergeSort(a,l,m);
    MergeSort(a,m+1,r);

    int tmp[r-l+1]={0};
    int p=0,pa=l,pb=m+1;
    while(pa<=m&&pb<=r){
        if(a[pa]<a[pb]){
            tmp[p]=a[pa];
            pa++;
            p++;
        }
        else{
            tmp[p]=a[pb];
            pb++;
            p++;
        }
    }
    while(pa<=m) {
         tmp[p]=a[pa];
         p++;
         pa++;
    }
    while(pb<=r) {
         tmp[p]=a[pb];
         p++;
         pb++;
    }
    for(int i=0;i<r-l+1;i++){
        a[l+i]=tmp[i];
    }
    return ;
}

归并排序时一种稳定的算法，可以看到使用$T(n)$来表示排列$n$个数所需要用的比较次数，得到$T(n)=O(nlog\ n)$,因为有地递推关系：

$$
T(n)= \begin{cases}
0 & n=1 \
T(n/2)+n & n>1
\end{cases}
$$

快速排序

选取基准元素pivot；
找到基准元素排序后的位置（实现操作后左边元素均小于它，右边元素均大于它）；
- 维护左端指针low和右端指针high；
- high向左扫描，遇到小于pivot元素时停止，交换pivot和该元素；
- low向右扫描，遇到大于pivot元素停止，交换pivot和该元素；
- high向右扫描..
- low向左扫描…
- …
- 直到low==high，基准元素到达这个位置，结束；
划分成子序列，递归地解决问题；

以下是一个对整数数组进行的快速排序代码；

 void QuickSort(int *a,int low,int high){
    if(low<high){
        int pivot=a[low];
        int l=low;
        int r=high;
        while(l<r){
            while(l<r&&a[r]>=pivot) r--;
            a[l]=a[r];
            while(l<r&&a[l]<=pivot) l++;
            a[r]=a[l];
        }
        int idx=l;
        a[idx]=pivot;

        QuickSort(a,low,idx-1);
        QuickSort(a,idx+1,high);
    }
}

由于快速排序时一种不稳定的算法，空间平均复杂度为$O(logN)$，最坏复杂度$O(N^2)$;

大数乘法

对于$X=A\cdot2^{n/2}+B,Y=C\cdot2^{n/2}+D,X\cdot Y=AC\cdot2^n-((A-B)(C-D)-AC-BD)\cdot2^{n/2}+BD$;

将大数乘法分解成更小的数，由于移位复杂度是线性的，分治得到复杂度递推式为$T(N)=3T(N/2)+O(N)$;

得到$T(N)=O(3^{log_2N})=O(N^{1.58})$;

由于涉及存储结构和常数优化等问题可能实现还不如常规算法，并且将整数看作多项式利用FFT可以实现$O(NlogN)$解决,这里就不贴代码了；

Straseen矩阵乘法

分形

Koch曲线
Mandelbrot集合

Hanota问题

在经典汉诺塔问题中，有 3 根柱子及 N 个不同大小的穿孔圆盘，盘子可以滑入任意一根柱子。一开始，所有盘子自上而下按升序依次套在第一根柱子上(即每一个盘子只能放在更大的盘子上面)。移动圆盘时受到以下限制:
(1) 每次只能移动一个盘子;
(2) 盘子只能从柱子顶端滑出移到下一根柱子;
(3) 盘子只能叠在比它大的盘子上。

题解：

class Solution {
public:
void move(std::vector<int>&A,std::vector<int>&B){
        if(A.empty())return;
        B.push_back(A.back());
        A.pop_back();
        return ;
}
void Hanota(int n,std::vector<int>&A,std::vector<int>&B,std::vector<int>&C){
    if(n==1) {
        move(A,C);
        return ;
    }
    Hanota(n-1,A,C,B);
    move(A,C);
    Hanota(n-1,B,A,C);
}
void hanota(std::vector<int>& A, std::vector<int>& B, std::vector<int>& C) {
    Hanota(A.size(),A,B,C);
}
};

第三章：树与图

二叉树

第$i$层上至多有$2^{i-1}$个结点,至少一个结点;
深度为$k$的二叉树至多有$2^k-1$个结点，至少$k$个结点;
二叉树边数为$B$,顶点数为$N$,二度顶点数为$n_2$,一度顶点数为$n_1$,叶子数为$n_0$,有如下关系式
- $B=N-1$
- $N=n_2+n_1+n_0$
- $B=2n_2+n_1$
- $n_2=n_0-1$

满二叉树、完全二叉树

满二叉树：一棵深度为$k$且有$2^k -1$个结点的二叉树;

完全二叉树：深度为$k$的，有$n$个结点的二叉树，当且仅当其每一个结点都与深度为$k$的满二叉树中编号从$1$至$n$的结点一一对应;

满二叉树是叶子一个也不少的树，完全二叉树只有最后一层叶子不满，且全部集中在左边，换言之，满二叉树最后一层全是叶子，完全二叉树只有倒数第一层和倒数第二层有叶子；
具有$n$个结点的完全二叉树的深度必为$⌊log_2n⌋+1 $;
对完全二叉树，若从上至下、从左至右编号，则编号为$i$ 的结点，其左孩子编号必为$2i$，其右孩子编号必为$2i+1$；其双亲的编号必为$⌊i/2⌋$;

二叉树的存储

顺序存储

结点间关系蕴含在其存储位置中，浪费空间，适于存满二叉树和完全二叉树；

链式存储

由数据域、左指针域、右指针域构成；

遍历

三种方式：先序遍历，中序遍历，后序遍历；

时间复杂度为$O(N)$,空间复杂度为$O(N)$;

访问路径是相同的，只是访问结点的时机不同：

第1次经过时访问＝先序遍历

第2次经过时访问＝中序遍历

第3次经过时访问＝后序遍历

重要结论：

由二叉树的前序序列+中序序列，或由其后序序列+中序序列均能唯一地确定一棵二叉树，

但由前序序列+后序序列却不一定能唯一地确定一棵二叉树。

树、二叉树、森林相互转换

树$\to$二叉树

加线：将兄弟结点用线相连

抹线：保留双亲与最左边孩子的连线，去掉双亲和其他孩子的连线

旋转：将经过加线和去线以后的结果，进行旋转处理得到转换后的二叉树

树转换成的二叉树，根结点的右子树一定为空

注意，就算是二叉树，通过这种方式转化，结构也可能发生变化；

二叉树$\to$树

加线：将结点和其左孩子结点的右孩子以及右孩子的右孩子加线相连

抹线：去掉结点和右孩子的连线

旋转：将加线、去线后的结果，进行旋转处理，就得到转换后的树

森林$\to$二叉树

将每棵树分别转换成二叉树,将每棵树的根结点用线相连

以第一棵树根结点为二叉树的根，再以根结点为轴心，顺时针旋转，构成二叉树型结构;

二叉树$\to$森林

抹线：将二叉树中根结点与其右孩子连线，及沿右分支搜索到的所有右孩子间连线全部抹掉，使之变成孤立的二叉树

还原：将孤立的二叉树还原成树;

二叉树模板类

以下是一个简单的二叉树模板类（未测试）；

#include <iostream>
#include <queue>
#include <map>
#include <functional>
template<typename T>class BTNode{
private:
    T data;
    BTNode<T>* l;
    BTNode<T>* r;
    friend class BT;
public:
    BTNode(int val=0,BTNode<T>* a=nullptr,BTNode<T>* b=nullptr)
    :data(val),l(a),r(b){};

    ~BTNode(){
        delete l;
        delete r;
    }

    T data() {return this->data;}
    T leftson(){return this->l;}
    T rightson(){return this->r;}

};
template<typename T>class BT{
private:
    BTNode<T>* root;
public:
    BT(BTNode<T>* x=nullptr):root(x){};

    DLR(T*out){
        if(!this->root) return ;
        *out++=root.data();
        root->l.DLR(out);
        root->r.DLR(out);
    }
    LDR(T*out){
        if(!this->root) return ;
        root->l.LDR(out);
        *out++=root.data();
        root->r.LDR(out);
    }
    LRD(T*out){
        if(!this->root)return ;
        root->l.LRD(out);
        root->r.LRD(out);
        *out++=root.data();
    }

    LevalTraval(T*out){
        std::queue<BTNode<T>* > q;
        BTNode<T>* now=this->root;
        q.push_back(now);
        while(!now) {
            *out++=now->data();
            q.pop_front();
            if(now->l) q.push_back(now->l);
            if(now->r) q.push_back(now->r);
        }
    } 
    build(int n,T* pre,T* in){
        std::map<int,T> f;
        for(int i=0;i<n;i++) f[in[i]]=i;

        std::function<void(std::map<int,T>,T*,T*,int,int,int,int)>
        build_tmp=[](std::map<int,T>f,T *pre,T* in,int l,int r,int x,int y){
            BTNode* now=new BTNode<T>(pre[l]);
            this=BT(now);
            int m=f[pre[l]];
            if(m!=x) now->l.build_tmp(f,pre,in,l+1,l+m-x,x,m-1);
            if(m!=y) now->r.build_tmp(f,pre,in,r-y+m+1,r,m+1,y);
        };
        build_tmp(f,pre,in,0,n-1,0,n-1);
    }

    int leavesNumber(){
        if(!this) return 0;
        if(!root->l&&!root->r) return 1;
        return root->l->leavesNumber()+root->r->leavesNumber();
    }

    int depth(){
        if(!this)return 0;
        if(!root->l&&!root->r) return 1;
        return 1+std::max(root->l->depth(),root->r->depth());
    }

    
};

树、森林的遍历

二叉排序树BST

若其左子树非空，则左子树上所有结点的值均小于根结点的值；
若其右子树非空，则右子树上所有结点的值均大于等于根结点的值；
其左右子树本身又各是一棵二叉排序树；
中序遍历二叉排序树后，得到一个关键字的递增有序序列

查找

若二叉排序树为空，则查找失败，返回空指针；

若查找的关键字等于根结点，成功，返回根结点地址；否则

若小于根结点，查其左子树
若大于根结点，查其右子树

平均查找性能：最好$O(logN)$,最坏$O(N)$;

插入

（插入的元素一定在叶结点上）

若二叉排序树为空，则插入结点应为根结点；

否则，继续在其左、右子树上查找

树中已有，不再插入
否则，查找直至某个结点的左子树或右子树为空为止，则插入结点应为该结点的左孩子或右孩子

建树

从空树出发，经过一系列的查找、插入操作之后，可生成一棵二叉排序树；

删除

删除叶结点：只需将其双亲结点指向它的指针清零，再释放它即可。
被删结点缺右子树：可以拿它的左孩子结点顶替它的位置，再释放它。
被删结点缺左子树：可以拿它的右孩子结点顶替它的位置，再释放它。
被删结点左、右子树都存在：
- 可以在它的右子树中寻找中序下的第一个结点(后继填充法),
- 或是在它的左子树中寻找中序下的最后一个结点(前驱填充法)，
- 用它的值填补到被删结点中，再来处理这个结点的删除问题。

平衡二叉树AVL

对所有结点，$|\text{左、右子树深度之差(平衡因子)}|≤ 1$

对于一个二叉平衡排序树，无论是删除结点还是插入结点，先当作一棵普通的二叉排序树处理，再进行关键的平衡性调整（下面四张图至关重要）；

找到最小不平衡子树$T$；
确定$T$根节点到最远叶结点这条路径上前三个结点$R>D>L$(排序是指关键字大小)；
按照下图旋转（四种可能情况）

实现从略（留坑，期末要复习不完力）；

红黑树RBT

特点：利用对树中的结点 “红黑着色”的要求，降低了平衡性的条件，达到局部平衡，有着良好的最坏情况运行时间，它可以在$O(logN)$时间内做查找，插入和删除，这里的N是树中元素的数目;

实现从略（留坑，期末要复习不完力）；

最优二叉树HuffmanTre

根据给定的n个权值{w1,w2,……wn}，构造n棵只有根结点的二叉树。
在森林中选取两棵根结点权值最小的树作左右子树，构造一棵新的二叉树，置新二叉树根结点权值为其左右子树根结点权值之和。
在森林中删除这两棵树，同时将新得到的二叉树加入森林中。
重复上述两步，直到只含一棵树为止，这棵树即霍夫曼树。

实现从略（留坑，期末要复习不完力）；

性质：一棵有$N$个叶子结点的Huffman树有 $2N-1$个结点

图的存储

邻接矩阵

邻接矩阵AdjMartrix[n][n],其中AdjMartrix[u][v]表示边$u \to v$的信息（头，尾，权重），空间复杂度为$O(N^2)$，适合对稠密图存储

int vertex[_MAXSIZE];//顶点，一维数组
class edge{//边
public:
    int head;
    int to;
    int weight;
    char *info;
};
edge AdjMartrix[_MAXSIZE][_MAXSIZE];//邻接矩阵

邻接表

由顶点表、边表和基本信息组成（点数，边数）组成，其中边表记录头结点、边权和头结点指向的下一条边；

顶点表记录想要访问的头结点以及顶点信息；

优点：空间效率高，容易寻找顶点的邻接点；

缺点：判断两顶点间是否有边，需搜索两结点对应的单链表，没有邻接矩阵方便

class AdjNode{
public:
    int adjvex;
    AdjNode *next;
    int weight;
};
class AdjHead{
public:
    int adjvex;
    AdjNode * next;
    int len;
};
class AdjList{//邻接表
public:
    AdjHead head[_MAXSIZE];
    int vernum;
    int edgenum;
};

十字链表

将邻接表和逆邻接表拼在一起，查询更加方便；

class edge_{
public:
    int head;
    int to;
    int weight;
    edge* hlink;//下一条入边
    edge* tlink;//下一条出边
};
class vertex_{
public:
    int vertex;
    edge* firstin;
    edge* firstout;
};
vertex_ crossLink[_MAXSIZE];//十字链表

class _edge_{
public:
    bool vis;
    int head;
    int to;
    _edge_* hlink;
    _edge_* tlink;
};
class _vertex_{
public:
    int first;
    _edge_* next;
};
_vertex_ node_[_MAXSIZE];//临界多重表

深度优先搜索DFS

一种用于遍历或搜索树或图的算法。所谓深度优先，就是说每次都尝试向更深的节点走；

时间复杂度为$O(|V|+|E|)$;

bool vis[_MAXSIZE];
void DFS(AdjList gra,int now){//基于邻接表的深搜
    vis[now]=true;
    AdjHead Now= gra.head[now];
    for(AdjNode* Nxt=Now.next;Nxt;Nxt=Nxt->next){
        int nxt=Nxt->adjvex;
        if(!vis[nxt]){
            DFS(gra,nxt);
        }
    }
    return ;
}

广度优先搜索BFS

所谓宽度优先。就是每次都尝试访问同一层的节点。如果同一层都访问完了，再访问下一层。

这样做的结果是，BFS 算法找到的路径是从起点开始的最短合法路径。换言之，这条路径所包含的边数最小。

在 BFS 结束时，每个节点都是通过从起点到该点的最短路径访问的。

时间复杂度为$O(|V|+|E|)$;

void BFS(AdjList gra,int now){
    std::queue<int> q;
    q.push(now);
    AdjHead Now= gra.head[now];
    while(!q.empty()){
        vis[q.front()]=true;
        q.pop();
        for(AdjNode* Nxt=Now.next;Nxt;Nxt=Nxt->next) q.push(Nxt->adjvex);
    }
}

有向无环图DAG，拓扑排序

经典的Kahn算法

所有入度为0的顶点进队列
栈非空时，输出栈顶元素并退栈；在邻接表中查找它的直接后继$x$，把$x$的入度减1；若$x$的入度为0则进栈
重复上述操作直至栈空为止；
若栈空时输出的顶点个数不是n，则有向图有环；否则，拓扑排序完毕

时间复杂度：$O(|V|+|E|)$空间复杂度：$O(|V|)$

求字典序最大/最小的拓扑排序:将 Kahn 算法中的队列替换成最大堆/最小堆实现的优先队列即可，此时总的时间复杂度为$O(E+V \log{V})$;

bool TopoSort(int*out,int* indegree,std::vector<int> Adj[],int n){
    //out为输出序列,indegree记录每个结点的入度,Adj记录每个结点的出邻点,1~n为结点
    //由于直接传图可能会改变图的结构,所以传这些可能更改的信息即可
    std::queue<int> q;
    for(int i=1;i<n;i++) if(!indegree[i]) q.push(i);
    int cnt=0;
    while(!q.empty()){
        int now=q.front();
        *out++=now;
        cnt++;
        q.pop();
        for(int j=0;j<Adj[now].size();j++) 
            if(!--indegree[Adj[now][j]]) 
                q.push(Adj[now][j]);
    }
    return cnt==n;//判断是否是DAG,拓扑序列是out
}

最小生成树

Prim算法

将顶点u0看作G的极小连通子图T；
选择一个端点u在T上，另一个端点v不在T上的权重最小的边(u,v)；将边(u,v)和顶点v添加到T上；
重复步骤2，直到T包含n个顶点；

Kruskal算法

删除图G=(V,E)的所有边，得到只有n个顶点、没有边的非连通图T=(V,Æ)，每个顶点自成一个连通分量
将E中所有的边按照权重从小到大排序；
按照权重从小到大的顺序考察E中每一条边，如果它的两个端点落在不同的连通分量上，则将其加入T中；
重复步骤2，直到所有顶点都在同一连通分量上

最短路径

Dijkstra算法

对于每个点v均维护一个「当前最短距离数组」dis[v]以及「访问数组」vis[v]，首先将

dis[u]初始化为0，将其他点的距离初始化为无穷，并将所有点初始化为未访问的。记

e[i]:u-v的边权e[i].w。然后进行以下步骤：
1. 从所有未访问的点中，找出当前距离最小的,并将其标记为已访问的;
2. 调整所有出边连接但尚未访问的点，转移状态；
3. 重复1和2步骤，直到所有点都已访问，因为所有边权权值均为正的，所以用之后访问的结点是不能更新已经访问过的结点的（因为贪婪算法下若可以更新的话必定在还在之前就已经更新过了）；
4. 可以用pre[y]=i维护最短的路径（点边关系）；

Floyd算法

考虑对每个$k$值，「$i$到$j$ 的路径只允许经过标号不大于$k$的点」中最短路径长度$dis[i][j]$，明显$k=n$是我们所求问题的答案；

初始$k=0$，所欲值都是正无穷；
递归的说，对于已有的$k-1 $允许的最短路径，新的最短路径要么经过$k$,要么维持不变；
状态转移方程为
$$
dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]),for\ all\ (i,j)s
$$
时间复杂度为$O(|V|^3)$;

基础数据结构与算法

第一章：线性结构

顺序表

单链表

顺序栈

链式栈

队列

查找

顺序查找

索引查找

哈希查找

哈希冲突处理

开放地址

多哈希

链地址法

公共溢出法

哈希表查找、性能分析

排序

直接插入排序

Shell排序

冒泡排序

选择排序

第二章：递归与分治

主方法

二分查找

归并排序

快速排序

大数乘法

Straseen矩阵乘法

分形

Hanota问题

第三章：树与图

二叉树

满二叉树、完全二叉树

二叉树的存储

顺序存储

链式存储

遍历

树、二叉树、森林相互转换

二叉树模板类

树、森林的遍历

二叉排序树BST

查找

插入

建树

删除

平衡二叉树AVL

红黑树RBT

最优二叉树HuffmanTre

图的存储

深度优先搜索DFS

广度优先搜索BFS

有向无环图DAG，拓扑排序

最小生成树

Prim算法

Kruskal算法

最短路径

Dijkstra算法

Floyd算法

第四章：线性规划