数据结构知识点笔记

(有时候确实读黑书应该读原著,中文翻译著作时常有些令人琢磨不透的表达)

复杂度

O(f(N))O(f(N))表算法复杂度T(N)T(N)的函数上限,其ff增长率≥T(N)≥T(N)的增长率。

Ω(f(N))Ω(f(N))表算法复杂度T(N)T(N)的函数下限,其ff增长率≤T(N)≤T(N)的增长率。

Θ(f(N))Θ(f(N))表 ff的增长率等于TT的增长率。

o(f(N))o(f(N))表 ff的增长率>T>T的增长率。

表、栈和队列

表或者说线性表的特征在于一组有次序(非大小有序的有序,这里指前后次序的序)的元素。实现物理结构:

  • 链表
    • 带头结点的链表
    • 双链表
    • 循环链表
    • 多重表
  • 数组

栈是删除和插入都在同一端点处进行的表。物理实现同样有链表和数组。

经典题目:后缀表示式计算、中缀转后缀

队列是队尾插入,队头删除的表。物理实现:

  • 循环数组的队列

树实际上只有一个源节点的DAG。最常见的如二叉查找树(限制了子节点和节点的关系的二叉树)、AVL、哈夫曼树

算法:

  • 先序遍历、中序遍历、后序遍历
  • 二叉查找树的创建、插入、删除
  • AVL树的旋转(四种)、插入、删除(调整 )
  • 展开树(p92?)
  • m阶B树的性质
  • 哈夫曼树 (Haffman)

实现:

  • 儿子链表
  • 兄弟儿子表示法
  • 父亲表示法

经典题目:表达式树的创建

散列

散列是将关键字映射到不同的数组单元DS。三个要点:

  • 散列函数
  • 消除冲突
    • 分离链接法
    • 开放定址法
      • 线性探测法
      • 平方探测法
      • 双散列
      • 再散列是重新建表重新映射到新数组

优先队列是用堆实现的保持堆序性的完全二叉树。

算法:

  • 上浮、下滤、插入、删除;注意建堆的复杂度是O(N)O(N)。

其他数据结构(我的神啊p147?):

  • d-堆
  • 左式堆
  • 斜堆
  • 二项队列

排序

  • 插入排序
  • 希尔排序
  • 堆排序
  • 归并排序
  • 快速排序:枢纽元的一个有效选取办法就是三数中值,随机数代价高昂
  • 桶式排序
  • 外部排序: 順串的产生(优先队列 + 最小元素锚定),順串的合并(归并算法)

集合

并查集算法

图论

数据表示:邻接表、邻接矩阵、邻接多重表(无向图)、十字链表(有向图)
算法:

  • 拓扑排序

  • 最短路径

    • 无权图:遍历

    • 非负权图:Dijkstra(最小堆优化)

      Dijkstra复杂度:

      邻接矩阵实现:O(V2)O(V2)

      邻接表实现:O(V2+VE)O(V2+VE)

      堆优化实现:O(V∗log(V)+Elog(V))O(V∗log(V)+Elog(V))
      思考复杂度真是有趣

    • 负权值图:

  • 遍历:DFS,BFS

  • 网络流问题

  • 最小生成树:Prim,Kruskal

  • 非双连通性的无向图割点问题:DFS

    • 有向图?

NP问题

NP问题值非确定性多项式时间问题,如果可以在多项式时间内验证一个问题的所有“对”为正确,那么该问题就是NP问题。而NP-完全问题就是NP问题在的一个子集,所有NP问题都可以通过映射转化为NP-C问题,所以NP-C问题是最难的。(。。。。。。。)

AVL

老模板了

/** This is Code of JJ

Problem      :AVL tree
Source       :
Solution     :
AnyDetial    :

DateAndTime  :5,18
CostofTime   :17:07

**/
#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;

struct Node{
    int data, height;
    Node *lchild, *rchild;
    Node(int x)
    {
        data = x;
        height = 1;
        lchild = NULL;
        rchild = NULL;
    }
};
int getHeight(Node *root)
{
    if(!root) return 0;//! child node may be is NULL.
    else return root->height;
}
int getHeightFactor(Node *root)
{
    return getHeight(root->lchild) - getHeight(root->rchild);
}
void updateHeight(Node *root)
{
    root->height = max(getHeight(root->lchild),getHeight(root->rchild)) + 1;//!!! add 1
}

void search(Node *root, int x)
{
    if(!root) return;
    if(root->data==x)
    {
        printf("%d\n",x);
    }
    else if(root->data>x)
    {
        search(root->lchild,x);
    }
    else  search(root->rchild,x);
}

//! right rotate
void r_rotate(Node *&root)
{
    cout<<"R\n";
    Node* tmpr = root->lchild;
    root->lchild = tmpr->rchild;
    tmpr->rchild = root;
    updateHeight(root);//!!!update the height of tree
    updateHeight(tmpr);
    root = tmpr;
}
//! left rotate
void l_rotate(Node *&root)///!!! left rotating replace root with root's right child.
{
    cout<<"L\n";
    Node* tmpr = root->rchild;
    root->rchild = tmpr->lchild;
    tmpr->lchild = root;
    updateHeight(root);//!!!update the height of tree
    updateHeight(tmpr);
    root = tmpr;

}

void insert(Node *&root, int x)
{
    if(root==NULL)
    {
        root  = new Node(x);;
        return;
    }
    else if(root->data>x)
    {
        insert(root->lchild,x);
    }else{
        insert(root->rchild,x);
    }
    //!!you should update the weight after changing the number or the height of root and child;
    updateHeight(root);
    if(getHeightFactor(root)==2)
    {
        if(getHeightFactor(root->lchild)==1)
        {
            r_rotate(root);//!!! change the root
        }else if(getHeightFactor(root->lchild)==-1)
        {
            l_rotate(root->lchild);
            r_rotate(root);//!!! change the root
        }
    }
    else if(getHeightFactor(root)==-2)
    {
        if(getHeightFactor(root->rchild)==-1)
        {
            l_rotate(root);//!!! change the root
        }
        else if(getHeightFactor(root->rchild)==1)
        {
            r_rotate(root->rchild);
            l_rotate(root);//!!! change the root
        }
    }
}
 Node *create(int a[], int n)
 {
     Node * root = NULL;
     for(int i=0;i<n;i++)
     {
         insert(root,a[i]);
     }
     return root;
 }

 void preorder(Node *root)
 {
     if(!root) return;
     printf("%d ",root->data);
     preorder(root->lchild);
     preorder(root->rchild);
 }
 void pr(Node *root)
 {
     if(!root) return;
     printf("data: %3d   h:%d\n",root->data,root->height);
     pr(root->lchild);
     pr(root->rchild);
 }
int main()
{
    int a[10]={1,2,3,4,5,6,7,8,9,10};
    Node *root = create(a,10);
//    preorder(root);
    pr(root);

}

二叉查找树实现

二叉查找树的一个实现

尤其注意删除那一部分的逻辑!

/** This is Code of JJ

Problem      :
Source       :
Solution     :
AnyDetial    :
注意点:
1.递归边界是root为NULL
2.插入:
    查找失败--NULL--即为插入点
    利用插入创建时,第一个数据就是查找失败的点!
3.层序遍历:队列里存的是地址;
DateAndTime  :
CostofTime   :

**/

#include<iostream>
#include<queue>
#include<cstdio>
#include<stack>
using namespace std;

struct Node{
    int data,layer;
    Node *lchild,*rchild;
    Node()
    {
        lchild = NULL;
        rchild = NULL;
    }
    Node(int a)
    {
        data = a;
        lchild = NULL;
        rchild = NULL;
    }
}; //

Node* newnode(int a)//! create a node with new!
{
    return new Node(a);
}

//! find those nodes whose data is x and replace those data with x;
void search_node(Node* root, int key, int x)
{
    if(root==NULL) return;
    if(root->data==key) root->data = x;//! a -> data !
    search_node(root->rchild,key,x);
    search_node(root->lchild,key,x);
}

void insert(Node *&root, int x)
{
    if(root==NULL)//! The
    {
        root = newnode(x);
        return;
    }
    if(root->data>x)
    {
        insert(root->lchild,x);
    }else{
        insert(root->rchild,x);
    }
}

Node* create(int a[], int n)
{
    Node *root = NULL;//!the index begin with 0;
    for(int i=0;i<n;i++)
    {
        insert(root,a[i]);
    }
    return root;
}

void preorder(Node *root)
{
    if(root==NULL) return;!
    printf("%d ",root->data);
    preorder(root->lchild);
    preorder(root->rchild);
}
//!可用于递归赋值父节点信息和遍历输出根到所有节点的路径

Node *path[1000];
int pos = -1;
void preorder_withrint(Node *root)
{
    if(root==NULL) return;
    path[++pos] = root;
//    cout<<pos<<endl;
    for(int i=0;i<pos;i++)
        printf("%d ",path[i]->data);
    printf("%d\n",path[pos]->data);
//    printf("%d ",root->data);
    preorder_withrint(root->lchild);
    preorder_withrint(root->rchild);
    pos--;
}

void inorder(Node *root)
{
    if(root==NULL) return;
    inorder(root->lchild);
    printf("%d ",root->data);
    inorder(root->rchild);
}

//!错误代码 : 此代码无法识别已经某一节点右节点是否已经压入过栈,而陷入无限循环之中
void inoder_withrecursion(Node *root)
{
    cout<<"Worry Code!\n";
    Node *q;
    stack<Node*> s;
    s.push(root);
    while(!s.empty()){
        getchar()
        ;q = s.top();
        if(q->lchild)//!一个错误点
            s.push(q->lchild);
        else{
            printf("%d ",q->data);
            s.pop();
            if(q->rchild)
                s.push(q->rchild);
        }
    }
}
void postorder(Node *root)
{
    if(root==NULL) return;
    inorder(root->lchild);
    inorder(root->rchild);
    printf("%d ",root->data);
}
void layerorder(Node* root)
{
    if(root==NULL) return;
    queue<Node*>q;
    q.push(root);
    while(!q.empty())
    {
        Node *t = q.front();
        q.pop();
        printf("%d ",t->data);
        if(t->lchild!=NULL) q.push(t->lchild);
        if(t->rchild!=NULL) q.push(t->rchild);
    }

}
int layerorder_withlayer(Node* root)
{
    if(root==NULL) return 0 ;
    int Nol = 0,Non = 0,maxn = 0;
    queue<Node*>q;
    root -> layer = 1;
    q.push(root);
    while(!q.empty())
    {
        Node *t = q.front();
        if(t->layer!=Nol){
            Nol = t->layer;
            Non = 1;
            cout<<"?";
        }else
            Non ++;
        maxn = max(Non,maxn);
        q.pop();
        printf("%d %d\n",t->data,t->layer);
        if(t->lchild!=NULL) {
            t->lchild->layer = Nol + 1;
            q.push(t->lchild);
        }
        if(t->rchild!=NULL){
            t->rchild->layer = Nol + 1;
            q.push(t->rchild);
        }
    }
    return maxn;

}
//!前序遍历和中序遍历重建树
Node *create_in_pre( int inorder[], int inl, int inr, int preorder[], int prel, int prer)//! in[l,r], pre[l,r],
{
    if(inl>inr || prel>prer) return NULL;
    int pos_in = inl;
    for(;pos_in<=inr;pos_in++)
    {
        if(inorder[pos_in]==preorder[prel])// find the index of root
            break;
    }
    int numleft = pos_in - inl;// the number of left tree;
    Node *root = newnode(preorder[prel]);
    root->lchild = create_in_pre(inorder, inl, pos_in-1, preorder, prel+1, prel+numleft);
    root->rchild = create_in_pre(inorder, pos_in+1, inr, preorder, prel+numleft+1, prer);
    return root;
}

//!后序遍历和中序遍历重建树
Node *create_in_post(int in[],int inl, int inr, int post[], int postl, int postr)
{
    if(inl>inr) return NULL;
    Node *root = newnode(post[postr]);
    int pos = inl;
    for(;pos<inr;pos++)
    {
        if(in[pos]==root->data) break;
    }
    int k = pos - inl;
    root->lchild = create_in_post(in,inl,pos-1,post,postl,postl+k-1);
    root->rchild = create_in_post(in,pos+1,inr,post,postl+k,postr-1);
    return root;
}
int main()
{
    int a[1000] = {1,3,-2,5,7,-10,15,0} ,n = 8;
    Node *root = create(a,n);
//    preorder(root);
    cout<<endl;
    inorder(root);
    cout<<endl;
//    inoder_withrecursion(root);
    preorder_withrint(root);
    cout<<endl;
//    postorder(root);
//    cout<<endl;
//    layerorder(root);
//    cout<<endl<<"max of Layer\n"<< endl;
//    cout<<layerorder_withlayer(root);
//    cout<<endl;

//    int pre[10] = {1 ,-2 ,-10, 0, 3 ,5 ,7 ,15};
//    int in[10] = {-10, -2, 0, 1, 3, 5, 7, 15};
//    int post[10] = {-10 ,-2, 0, 3, 5, 7, 15 ,1};
//
//    Node *newroot1 = create_in_pre(in,0,7,pre,0,7);
//    Node *newroot2 = create_in_post(in,0,7,post,0,7);
//    cout<<"!recreate!\n";
//    inorder(newroot1);
//    cout<<endl;
//    inorder(newroot2);

}

堆算法和堆排序

堆排序

#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
#include<string>
using namespace std;
vector<int> a, b;
int n;
void adjustDown(vector<int> &arr, int x, int len){
    for(int p = 2 * x; p <= len; p *= 2){
        if(p < len  && arr[p] < arr[p+1]) p++;
        if(arr[x] > arr[p]) break;
        swap(arr[x], arr[p]);
        x = p;
    }
}
int main(){
    cin >> n;
    a.resize(n + 1);
    b.resize(n + 1);
    for(int i = 1;i <= n; i++) cin >> a[i];
    for(int i = 1;i <= n; i++) cin >> b[i];
    int p = 1, ch;
    while(p < n && b[p] <= b[p + 1]) p++;
    for(ch = p + 1; ch <= n && a[ch] == b[ch]; ch++);
    if(ch == n + 1){
        cout << "Insertion Sort\n";
        sort(a.begin() + 1, a.begin() + 2 + p);
    }else{
        cout << "Heap Sort\n";
        int k = n;
        while(k > 0 && b[k] > b[1]) k--;
        swap(b[1], b[k]);
        adjustDown(b, 1, k - 1);
        a = b;

    }
    for(int i = 1; i <= n; i++)
        if(i == n) printf("%d\n", a[i]);
        else  printf("%d ", a[i]);
}

完全堆排序

#include<iostream>
#include<cstdio>
using namespace std;

const int MAXN = 1e3;
int heap[MAXN] = {0,3,14,7,12,13,4,5,20};
int n = 8;
///! down
void downAdjust(int p,int len){
    for(int x = p * 2; x <= len; x += x){
        if(x < len && heap[x] < heap[x + 1]) x++;
        if(heap[x] < heap[p]) break;
        swap(heap[x], heap[p]);
        p = x;
    }
}
//    for(int i=1;i<=n/2;i++)
    //! 叶子的一个下标是 n/2向下取整+1
    //! 必须从底部开始调整,不然不能保持之前的子堆的有序性质
void buildHeap(){
    for(int i=n/2; i>=1; i--)
        downAdjust(i,n);
}
///!delete element
void deleteTop(){
    heap[1] = heap[n--];//! n--
    downAdjust(1,n);
}
///!!!up
void upAdjust(int p, int len){
    for(int x = p /2 ; x >= 1; x /= 2){
        if(heap[x] > heap[p]) break;
        swap(heap[x], heap[p]);
        p = x;
    }
}
void insert(int x)
{
    heap[++n] = x;
    upAdjust(n,n);
}
void show()
{
    for(int i=1; i<=n; i++)
        cout<<heap[i]<<" ";
    cout<<"\n";
}
///! head sort
void headSort(int n)
{
    buildHeap();
    for(int i=n; i>=2; i--)
    {
        swap(heap[1],heap[i]);
        downAdjust(1,i-1);//!! heap only have n-1 elements;
    }
}
int main()
{
    show();
    buildHeap();
    insert(25);
    show();
    headSort(n);
    show();
}

二叉树集合

(好像不怎么用心的样子呢)

/** This is Code of JJ

Problem      :
Source       :
Solution     :
AnyDetial    :
注意点:
1.递归边界是root为NULL
2.插入:
    查找失败--NULL--即为插入点
    利用插入创建时,第一个数据就是查找失败的点!
3.层序遍历:队列里存的是地址;
DateAndTime  :
CostofTime   :

**/

#include<iostream>
#include<queue>
#include<cstdio>
using namespace std;

struct Node{
    int data;
    Node *lchild,*rchild;
    Node()
    {
        lchild = NULL;
        rchild = NULL;
    }
    Node(int a)
    {
        data = a;
        lchild = NULL;
        rchild = NULL;
    }
}; //

Node* newnode(int a)//! create a node with new!
{
    return new Node(a);
}

//! find those nodes whose data is x and replace those data with x;
void search_node(Node* root, int key, int x)
{
    if(root==NULL) return;
    if(root->data==key) root->data = x;//! a -> data !
    search_node(root->rchild,key,x);
    search_node(root->lchild,key,x);
}

void insert(Node *&root, int x)
{
    if(root==NULL)//! The
    {
        root = newnode(x);
        return;
    }
    if(root->data>x)
    {
        insert(root->lchild,x);
    }else{
        insert(root->rchild,x);
    }
}

Node* create(int a[], int n)
{
    Node *root = NULL;//!the index begin with 0;
    for(int i=0;i<n;i++)
    {
        insert(root,a[i]);
    }
    return root;
}

void preorder(Node *root)
{
    if(root==NULL) return;!
    printf("%d ",root->data);
    preorder(root->lchild);
    preorder(root->rchild);
}
void inorder(Node *root)
{
    if(root==NULL) return;
    inorder(root->lchild);
    printf("%d ",root->data);
    inorder(root->rchild);
}
void postorder(Node *root)
{
    if(root==NULL) return;
    inorder(root->lchild);
    inorder(root->rchild);
    printf("%d ",root->data);
}
void layerorder(Node* root)
{
    if(root==NULL) return;
    queue<Node*>q;
    q.push(root);
    while(!q.empty())
    {
        Node *t = q.front();
        q.pop();
        printf("%d ",t->data);
        if(t->lchild!=NULL) q.push(t->lchild);
        if(t->rchild!=NULL) q.push(t->rchild);
    }

}
//!前序遍历和中序遍历重建树
Node *create_in_pre( int inorder[], int inl, int inr, int preorder[], int prel, int prer)//! in[l,r], pre[l,r],
{
    if(inl>inr || prel>prer) return NULL;
    int pos_in = inl;
    for(;pos_in<=inr;pos_in++)
    {
        if(inorder[pos_in]==preorder[prel])// find the index of root
            break;
    }
    int numleft = pos_in - inl;// the number of left tree;
    Node *root = newnode(preorder[prel]);
    root->lchild = create_in_pre(inorder, inl, pos_in-1, preorder, prel+1, prel+numleft);
    root->rchild = create_in_pre(inorder, pos_in+1, inr, preorder, prel+numleft+1, prer);
    return root;
}

//!后序遍历和中序遍历重建树
Node *create_in_post(int in[],int inl, int inr, int post[], int postl, int postr)
{
    if(inl>inr) return NULL;
    Node *root = newnode(post[postr]);
    int pos = inl;
    for(;pos<inr;pos++)
    {
        if(in[pos]==root->data) break;
    }
    int k = pos - inl;
    root->lchild = create_in_post(in,inl,pos-1,post,postl,postl+k-1);
    root->rchild = create_in_post(in,pos+1,inr,post,postl+k,postr-1);
    return root;
}
int main()
{
    int a[1000] = {1,3,-2,5,7,-10,15,0} ,n = 8;
    Node *root = create(a,n);
    preorder(root);
    cout<<endl;
    inorder(root);
    cout<<endl;
    postorder(root);
    cout<<endl;
    int pre[10] = {1 ,-2 ,-10, 0, 3 ,5 ,7 ,15};
    int in[10] = {-10, -2, 0, 1, 3, 5, 7, 15};
    int post[10] = {-10 ,-2, 0, 3, 5, 7, 15 ,1};

    Node *newroot1 = create_in_pre(in,0,7,pre,0,7);
    Node *newroot2 = create_in_post(in,0,7,post,0,7);
    cout<<"!recreate!\n";
    inorder(newroot1);
    cout<<endl;
    inorder(newroot2);

}