数据结构选课学习笔记

这是数据结构选课的课内笔记,和 $OI$ 的高难数据结构关系不是很大,主要是记一些怕忘的定义.

ADL语言

算法 SM(A,n,&min,&max)

max<-min<a[1]
FOR i=2 TO n DO
    if A[i]>max THEN max<-a[i]
    if A[i]<min THEN min<-a[i]

举例

$$ADL:a\leftrightarrow b$$

a^=b^=a^=b

(实际数据结构笔试的时候可以写c++,完全不用看ADL语言)

算法的鲁棒性

自动识别错误数据(并纠正)的能力.

算法测试 :两种,
黑盒测试:测试点.
白盒测试:语句覆盖,分支覆盖.

时间复杂度

$O$ ,读音:big-oh;表示上界,小于等于.
$ο$ ,读音:small-oh;表示上界,小于.
$\Theta$ ,读音:theta、西塔;既是上界也是下界,称为确界,等于.
$\omega$ ,读音:small omega;表示下界,大于.
$\Omega$ ,读音:big omega、欧米伽;表示下界,大于等于.

Ο是渐进上界,Ω是渐进下界.Θ需同时满足大Ο和Ω,故称为确界.Ο极其有用,因为它表示了最差性能.

时空积分

$$W=\int_0^tf(x)\mathrm dx$$

多维数组寻址

$$*=dat+\sum_{j=1}^{n-1}(i_j\times\prod^{n}_{p=k+1} m_p)*C$$

C代表sizeof,大乘号其实就是前缀积

矩阵三元组表转置

Q:为啥PPT说的是 $O(nt)$ 的?
这个可以做到 $O(t\log t)$ .

二叉树

满二叉树:顾名思义,节点全满,非常均匀.
完全二叉树:节点全的,末层缺失(注意从右侧缺失)

线索二叉树

节点

val,l,r,   pred,succ

后面这俩存根,先根或者后根, 可以存前根,中根或者后根 ,故又称前序,中序或者后序线索二叉树.

哈夫曼树

扩充二叉树:二叉树所有原来有空位的加子节点.

路径长度:

$$w=\sum_{i=1}^nw_id_i$$

其中w代表权值(就是存的那个数),然后d是路径长(深度-1),这个w最小的叫最优二叉树.

哈夫曼编码:左儿子是0,右儿子是1,直接走,走到哪编码.

压缩:开一个map统计出现频率,然后建立哈夫曼树,直接译码. $O(n\log n)$ .
解码:先读哈夫曼树,然后直接译码即可.

哈夫曼树构造

所有节点都是一个森林,然后每次选权值最小的根组成一个新树,产生一个新节点,加入其中,直到剩一个根.

表达式树

中缀表达式树.一看例子就明白了.

(a+b)*(c+d)-e
        -
       / \
      *   e
     / \
    +   -
   / \ / \
   a b c d

图

连通子图:顾名思义.
连通分量:把所有联通块抽出来就是.

拓扑排序

每次选一个入度为0的,然后删掉边,循环.

拓扑排序是 $O(n+e)$ 的.

希尔排序(Shell)

直接插入排序的改进.作为最先冲破 $O(n^2)$ 的排序算法,值得借鉴.

每次把增量分成n>>1,然后每个区间暴力插入排序.直到最后

基数分布和值分布

基数排序,是模按照指定位数进行排序的算法,计数排序就是俗称的桶排序.

基数排序:先开十个链表,然后取最后一位看剩下的数.按照这个顺序先排起来.
然后取第二位接着排,直到元素有序.

板子

下面的是Flu的离线stl库.

如果有人做数据结构作业不让使用stl库,也许可以参考一下.

注意, JLU 实际上是可以使用stl库的,因为无论是程序作业还是考试都有一堆爆零的.

栈

一度让我觉得没有封装的必要…但是既然数据结构提了那就写一个吧…

template<typename T>
struct sstack{
    T* dat;
    int ttop;
    sstack(int n=100010){dat=new T[n];ttop=0;}
    void push(T val){dat[++ttop]=val;}
    T top(){if(ttop>0)return dat[ttop];return -114514;}
    int size(){return ttop;}
    int pop(){if(ttop==0)return -114514;ttop--;return 0;}
    char empty(){return ttop<=0;}
};//所有操作不合法会返回-114514

双端队列 队列

因为双端队列兼容队列,所以就不再写队列的模板了.

template<typename T>
struct ddeque{
    T* dat;
    int ttop,l;
    ddeque(int n=200010){dat=new T[n];ttop=(n>>1);l=(n>>1)+1;}
    int size(){return ttop-l+1;}
    T front(){if(ttop<l)return -114514;return dat[ttop];}
    T back(){if(ttop<l)return -114514;return dat[l];}
    int pop_front(){if(ttop<l)return -114514;ttop--;return 0;}
    int pop_back(){if(ttop<l)return -114514;l++;return 0;}
    void push_front(T val){dat[++ttop]=val;}
    void push_back(T val){dat[--l]=val;}
    char empty(){return (ttop-l+1)<=0;}
};

动态数组

推测vector怎么用.

template<typename T>
struct vvector{
    static constexpr int base[]={0,20,110,1010,10010,100010,200010,1000010,2000010,10000010};
    T* dat;
    int sz,top;//当前块指向,顶端元素(Flu比较喜欢闭区间)
    vvector(int size=0,T val=0){sz=size;dat=new T[base[size]];for(int i=0;i<base[size];++i){dat[i]=val;}top=-1;}
    int size(){return top+1;}
    void push_back(T val){if((top+1)>=base[sz]){T* p=new T[base[sz+1]];for(int i=0;i<base[sz];++i){p[i]=dat[i];}p[++top]=val;sz++;delete[]dat;dat=p;}else{dat[++top]=val;}}
    void clear(){top=-1;}
    T& operator[](int io){return dat[io];}
};

哈希表

低配版umap,只支持 long long 的哈希,但是够用了

template<typename T>
struct uunordered_map{
    struct node{
        long long first;
        T second;
        node *next,*nnext;
        node(long long a,T b,node* p=nullptr,node* pp=nullptr):first(a),second(b),next(p),nnext(pp){}
    };
    node** dat;
    node* pp00;
    const long long mmod=1000003;
    int sz;
    uunordered_map(){
        sz=0;
        pp00=nullptr;
        dat=new node*[mmod];
        for(int i=0;i<mmod;++i){
            dat[i]=nullptr;
        }
    }
    long long qqp(long long b,int po){
        long long res=1;
        while(po>0){
            if(po&1)
                res=res*b%mmod;
            b=b*b%mmod;
            po>>=1;
        }
        return res;
    }
    int hash(long long val){
        return qqp(val,5);
    }
    int size(){
        return sz;
    }
    T& operator[](const long long& io){
        int h=hash(io);
        node* i=dat[h];
        for(;i!=nullptr;i=i->next){
            if(i->first==io)
                return i->second;
        }
        sz++;
        node* j=new node(io,0,dat[h],pp00);
        pp00=j;
        dat[h]=j;
        return j->second;
    }
    void triverse(){
        for(node* i=pp00;i!=nullptr;i=i->nnext){
            //i->first键 i->second键值
            //这是遍历所有元素的过程
            //do something
            //
            //
            //
        }
    }
    char empty(){
        return sz<=0;
    }
};

priority_queue

自定义类需要写比较函数 < ,记得输入0或者1表明建立小根堆还是大根堆,默认是0大根堆.

template<class T>
struct ppriority_queue{
    T* dat;
    int sz,ff;/*ff0大根堆1小根堆*/
    ppriority_queue(int flag=0,int n=100010):sz(0),ff(flag){
        dat=new T[n];
    }
    ppriority_queue(T* arr,int num,int flag=0,int n=100010):sz(num),ff(flag){
        dat=new T[n];
        for(int i=0;i<num;++i){
            dat[i+1]=dat[i];
        }
        maintain(1);
    }
    void push(T val){
        dat[++sz]=val;
        maintaindown(sz);
    }
    void maintaindown(int num){
        int fa=num>>1;
        if((dat[fa]<dat[num])^ff){
            sswap(dat[fa],dat[num]);
            maintaindown(fa);
        }
    }
    int pop(){
        if(sz<=0)return -114514;
        dat[1]=dat[sz--];
        maintainup(1);
        return 0;
    }
    void maintainup(int num){
        int ls=num<<1,rs=(num<<1)+1,gg=0;
        if(rs<=sz)gg+=2;
        if(ls<=sz)gg++;
        switch(gg){
            case 0:{
                return;
            }case 1:{
                if((dat[num]<dat[ls])^ff){
                    sswap(dat[num],dat[ls]);
                }
                return;
            }case 3:{
                if((dat[ls]<dat[rs])^ff){
                    if((dat[num]<dat[rs])^ff){
                        sswap(dat[num],dat[rs]);
                        maintainup(rs);
                    }
                }else{
                    if((dat[num]<dat[ls])^ff){
                        sswap(dat[num],dat[ls]);
                        maintainup(ls);
                    }
                }
                break;
            }
        }
    }
    T top(){
        return dat[1];
    }
    int size(){
        return sz;
    }
    void sswap(T& a,T& b){
        T _tmp=a;
        a=b;
        b=_tmp;
    }
    void maintain(int num){/*O(n)建堆*/
        int ls=num<<1,rs=(num<<1)+1,gg=0;
        if(ls<=sz)maintain(ls),gg++;
        if(rs<=sz)maintain(rs),gg+=2;
        switch(gg){
            case 0:{
                return;
            }case 1:{
                if((dat[num]<dat[ls])^ff){
                    sswap(dat[num],dat[ls]);
                }
                return;
            }case 3:{
                if((dat[ls]<dat[rs])^ff){
                    if((dat[num]<dat[rs])^ff){
                        sswap(dat[num],dat[rs]);
                    }
                }else{
                    if((dat[num]<dat[ls])^ff){
                        sswap(dat[num],dat[ls]);
                    }
                }
                break;
            }
        }
    }
    char empty(){
        return sz<=0;
    }
};

ppair

单纯模仿用的…

template<typename T1,typename T2>
struct ppair{
    T1 first;
    T2 second;
    ppair(){}
    ppair(T1 a,T2 b):first(a),second(b){}
    ppair& operator =(const ppair& io){
        first=io.first;
        second=io.second;
        return *this;
    }
    char operator ==(const ppair& io)const{
        return (first==io.first)&&(second==io.second);
    }
    void swap(ppair& io){
        ppair tmp=io;
        io=*this;
        *this=tmp;
    }
};

list

十分暴力的链表.

template<typename T>
struct llist{
    int cnt,top;/*top目前链表占用多大空间,cnt链表有多少个元素*/
    T* dat;
    int* nxt;
    llist(int n=200010):cnt(0),top(1){
        dat=new T[n];
        nxt=new int[n];
        for(int i=0;i<n;++i){
            nxt[i]=0;
        }
    }
    llist(T* ddat,int num,int n=200010):cnt(num),top(1+num){
        dat=new T[n];
        nxt=new int[n];
        for(int i=0;i<num;++i){/*[0,num)*/
            dat[i+2]=ddat[i];
            nxt[i+1]=i+2;
        }
    }
    void _add(int pre,T val){
        for(int i=0,j=1;;++i,j=nxt[j]){
            if(i==pre){
                nxt[++top]=nxt[j];
                nxt[j]=top;
                dat[top]=val;
                cnt++;
                return;
            }
        }
    }
    int add(int pos,T val){
        if(pos<0||cnt<pos)return -114514;
        _add(pos,val);
        return 0;
    }
    void _del(int pre){
        for(int i=0,j=1;;++i,j=nxt[j]){
            if(i==pre){
                nxt[j]=nxt[nxt[j]];
                cnt--;
                return;
            }
        }
    }
    int del(int pos){
        if(pos<=0||cnt<pos)return -114514;
        _del(pos-1);
        return 0;
    }
    void triverse(){
        for(int i=1,j=nxt[1];j!=0;++i,j=nxt[j]){
            /*i是序号,j是当前元素指针*/
            //do something...


        }
    }
};

高精度

懒得写,高精度维护起来太麻烦了.

ALL

namespace Flu{
    template<typename T>
    struct ddeque{
        T* dat;
        int ttop,l;
        ddeque(int n=200010){dat=new T[n];ttop=(n>>1);l=(n>>1)+1;}
        int size(){return ttop-l+1;}
        T front(){if(ttop<l)return 0x0d000721;return dat[ttop];}
        T back(){if(ttop<l)return 0x0d000721;return dat[l];}
        int pop_front(){if(ttop<l)return 0x0d000721;ttop--;return 0;}
        int pop_back(){if(ttop<l)return 0x0d000721;l++;return 0;}
        void push_front(T val){dat[++ttop]=val;}
        void push_back(T val){dat[--l]=val;}
        char empty(){return (ttop-l+1)<=0;}
    };
    template<typename T>
    struct vvector{
        static constexpr int base[]={0,20,110,1010,10010,100010,200010,1000010,2000010,10000010};
        T* dat;
        int sz,top;//当前块指向,顶端元素(Flu比较喜欢闭区间)
        vvector(int size=0,T val=0){sz=size;dat=new T[base[size]];for(int i=0;i<base[size];++i){dat[i]=val;}top=-1;}
        int size(){return top+1;}
        void push_back(T val){if((top+1)>=base[sz]){T* p=new T[base[sz+1]];for(int i=0;i<base[sz];++i){p[i]=dat[i];}p[++top]=val;sz++;delete[]dat;dat=p;}else{dat[++top]=val;}}
        void clear(){top=-1;}
        T& operator[](int io){return dat[io];}
    };
    template<class T>
    struct ppriority_queue{
        T* dat;
        int sz,ff;/*ff0大根堆1小根堆*/
        ppriority_queue(int flag=0,int n=100010):sz(0),ff(flag){dat=new T[n];}
        ppriority_queue(T* arr,int num,int flag=0,int n=100010):sz(num),ff(flag){dat=new T[n];for(int i=0;i<num;++i){dat[i+1]=dat[i];}maintain(1);}
        void push(T val){dat[++sz]=val;maintaindown(sz);}
        void maintaindown(int num){int fa=num>>1;if((dat[fa]<dat[num])^ff){sswap(dat[fa],dat[num]);maintaindown(fa);}}
        int pop(){if(sz<=0)return 0x0d000721;dat[1]=dat[sz--];maintainup(1);return 0;}
        void maintainup(int num){int ls=num<<1,rs=(num<<1)+1,gg=0;if(rs<=sz)gg+=2;if(ls<=sz)gg++;switch(gg){case 0:{return;}case 1:{if((dat[num]<dat[ls])^ff){sswap(dat[num],dat[ls]);}return;}case 3:{if((dat[ls]<dat[rs])^ff){if((dat[num]<dat[rs])^ff){sswap(dat[num],dat[rs]);maintainup(rs);}}else{if((dat[num]<dat[ls])^ff){sswap(dat[num],dat[ls]);maintainup(ls);}}break;}}}
        T top(){return dat[1];}
        int size(){return sz;}
        void sswap(T& a,T& b){T _tmp=a;a=b;b=_tmp;}
        void maintain(int num){/*O(n)建堆*/int ls=num<<1,rs=(num<<1)+1,gg=0;if(ls<=sz)maintain(ls),gg++;if(rs<=sz)maintain(rs),gg+=2;switch(gg){case 0:{return;}case 1:{if((dat[num]<dat[ls])^ff){sswap(dat[num],dat[ls]);}return;}case 3:{if((dat[ls]<dat[rs])^ff){if((dat[num]<dat[rs])^ff){sswap(dat[num],dat[rs]);}}else{if((dat[num]<dat[ls])^ff){sswap(dat[num],dat[ls]);}}break;}}}
        char empty(){return sz<=0;}
    };
    template<typename T>
    struct llist{
        int cnt,top;/*top目前链表占用多大空间,cnt链表有多少个元素*/
        T* dat;
        int* nxt;
        llist(int n=200010):cnt(0),top(1){dat=new T[n];nxt=new int[n];for(int i=0;i<n;++i){nxt[i]=0;}}
        llist(T* ddat,int num,int n=200010):cnt(num),top(1+num){dat=new T[n];nxt=new int[n];for(int i=0;i<num;++i){/*[0,num)*/dat[i+2]=ddat[i];nxt[i+1]=i+2;}}
        void _add(int pre,T val){for(int i=0,j=1;;++i,j=nxt[j]){if(i==pre){nxt[++top]=nxt[j];nxt[j]=top;dat[top]=val;cnt++;return;}}}
        int add(int pos,T val){if(pos<0||cnt<pos)return 0x0d000721;_add(pos,val);return 0;}
        void _del(int pre){for(int i=0,j=1;;++i,j=nxt[j]){if(i==pre){nxt[j]=nxt[nxt[j]];cnt--;return;}}}
        int del(int pos){if(pos<=0||cnt<pos)return 0x0d000721;_del(pos-1);return 0;}
        void triverse(){
            for(int i=1,j=nxt[1];j!=0;++i,j=nxt[j]){
                /*i是序号,j是当前元素指针*/
                //do something...
                //
                //
                //
            }
        }
    };
    template<typename T>
    struct uunordered_map{
        struct node{
            long long first;
            T second;
            node *next,*nnext;
            node(long long a,T b,node* p=nullptr,node* pp=nullptr):first(a),second(b),next(p),nnext(pp){}
        };
        node** dat;
        node* pp00;
        const long long mmod=1000003;
        int sz;
        uunordered_map(){sz=0;pp00=nullptr;dat=new node*[mmod];for(int i=0;i<mmod;++i){dat[i]=nullptr;}}
        long long qqp(long long b,int po){long long res=1;while(po>0){if(po&1)res=res*b%mmod;b=b*b%mmod;po>>=1;}return res;}
        int hash(long long val){return qqp(val<0?(-val):val,5);}
        int size(){return sz;}
        T& operator[](const long long& io){int h=hash(io);node* i=dat[h];for(;i!=nullptr;i=i->next){if(i->first==io)return i->second;}sz++;node* j=new node(io,0,dat[h],pp00);pp00=j;dat[h]=j;return j->second;}
        char empty(){return sz<=0;}
        void triverse(){
            for(node* i=pp00;i!=nullptr;i=i->nnext){
                //i->first键 i->second键值
                //这是遍历所有元素的过程
                //do something
                //
                //
                //
            }
        }
    };
}

做题

背板

数据结构包含哪方面内容?数据存储方法有多少种?

数据的逻辑结构,物理结构,存储结构.

存储表示方法有四种:

1. 顺序存储(逻辑相邻存储在物理相邻的单元中)
2. 链接存储(不要求物理相邻,节点间的关系使用指针表示)
3. 索引存储(除了存储节点信息还添加索引表示节点地址)
4. 散列存储(根据关键字计算出存储地址)

数组

一定要看清行优先存储还是列优先存储!!!

排序

内外排序的区别是,外排序数据很大,一次读不完需要好几次IO,此时限制IO次数比较重要.(听说外排序可以用归并)

快排辅助空间是O(logn)的,选择排序是不稳定的排序算法,快排,堆都是不稳定的排序算法.

快排的 划分 :依照某个元素把整个数组拆成两半的过程.
然而有个坑:在划分的时候元素顺序可能有锅:考虑选择某个元素,然后这个元素就能动了,然后朝不能动的那端进行比较,确保不需要额外空间.比如

46 79 56 38 40 84 快排选择头节点
__ 79 56 38 40 __ (84) 84这个时候和46比较决定放在哪里
__ 79 56 38 __ 84 (40) 40这个时候和46比较决定放在哪里
40 __ 56 38 __ 84 (79) 79这个时候和46比较决定放在哪里
...这样类推,最后的放原来比较元素

堆排序 :建堆的时候是先从子树开始维护堆序性(建堆),然后弹出元素的时候是从头开始到链维护堆序性.

归并排序 :一组记录的关键字是(25,50,15,35,80,85,20,40,36,70)其中含有5个长度为2的有序表,用归并排序算法进行一趟归并的结果是啥

给的有序表可以直接合并,所以就是[25,50]和[15,35]合并,[80,85]和[20,40]合并,[36,70]不动,答案出来了.

查找

判定树:节点的值是当前位置元素的值.

比如5,12,17,19,23,25,30,36的判定树是

    19
   / \
  12   25
 / \   /\
6  19 23 30
          \
           36

这个时候的成功查找长度是每个节点的高度(根节点高度定义为1)平均值

不成功的ASL计算: \sum深度空指针乘深度个数/指针个数 ,在这里看图,深度为3的节点有6 19 23 30,他们贡献7个空指针,36深度为4贡献2个空指针,加一起:

$$\frac{3\times7+4\times2}{9}=3.2222$$

队列

两点:1.一定要注意队列是否为空!!然后就是,队列是加在队列末尾,队列前端先出.

2.循环队列元素公式 $(end-front+M)\mod M$

树论

迷惑问题:若完全二叉树的某节点无左孩子节点,则他必是叶子节点(T)
争议项:只有一个根,这个根已经是根了,还能是叶子吗???

课本教的”树转二叉树”,”二叉树转森林”,”森林转二叉树”的算法统称 自然对应法 :

树转二叉树 :一个节点的所有子节点之间连线,然后只保留最靠左的一条线,其余删掉.比如

  1           1           1
 /|\         /|\         /
2 3 4   ->  2-3-4   ->  2-3-4
 /|\         /|\         /
5 6 7       5-6-7       5-6-7

二叉树转树 :逆过程,记住左儿子右兄弟即可恢复.根节点的右兄弟直接砍掉,此时会变成森林.

二叉树转森林 :第一棵树的根的右孩子连其他树的根,然后以此类推.(注意到自然对应出来的二叉树的根只有一个左子树,所以可以大胆搞)

森林转二叉树 :根节点开始,一直向右走的链全部断开即可.

图论

前驱节点:就是树或者图能到达该点的几个节点.
后继节点:该点能到达的所有节点.(在图中,这俩想有多少个能有多少个).

AOV网:就是DAG(有向无环图)
AOE网:带权的DAG.

广度优先序列:直接遍历即可.
深度优先序列:dfs.复杂度O(n+e)别写错

关键路径 :从源点到汇点的权值 最长 的路径.

邻接矩阵存储:

$$\begin{bmatrix}0&\infty&5\\ \infty&0&4\\ \infty&3&0 \end{bmatrix}$$

注意自己连自己是0,没边填infty.

平衡树

平衡的定义是 |左子树-右子树|<=1 ,否则旋转.

平衡树删除就是直接挪到底端然后删除.

散列

给一个数组,制作哈希表:

拉链法:每个点都是一个链表.
开点法:顺延该点.

下面讨论拉链法的平均查找长度:
假设函数是%11,数列33,21,8,22,43,17,12,13,11,构造表如下:

0	1	2	3	4	5	6	7	8	9	10
33	12	13				17		8		21
22										43
11

成功:(每个元素的深度)/数列元素个数,上面 $ASL_{SUCC}=\frac{1\times6+2\times2+3}9=1.4444$
失败:(哈希表每个深度+1)/哈希表值域多宽,上面 $ASL_{UNSUCC}=\frac{4+2+2+1+1+1+2+1+2+1+3}{11}=1.8182$

待解决的问题

背kmp板子,失配指针是干什么的

背堆板子.