数据结构考试材料

一. 通用

1. cin cout加速

   std::ios::sync_with_stdio(0);
   cin.tie(0); cout.tie(0);
   

2. sscanf 格式化字符串

   int sscanf (const char *str, const char * format, ........);
   

   • sscanf()会将参数 str 的字符串根据参数 format 字符串来转换并格式化数据。格式转换形式参考scanf()。转换后的结果存于对应的参数......内

二. 常用算法

1. GCD 最大公约数

   //求最大公因数递归算法
   int gcd(int x, int y){
       return y? gcd(y, x%y) : x;
   }
   

2. 线性筛

   int visited[MAXSIZE];
   int prime[MAXSIZE];
   
   //判断是否是一个素数  visited 标记数组 index 素数个数
   int Prime(){
       int index = 0;
       for(int i = 2; i < MAXSIZE; i++){
           //如果未标记则得到一个素数
           if(visited[i] == 0) prime[++index] = i;
   
           //标记目前得到的素数的i倍为非素数
           for(int j = 1; j <= index && prime[j] * i < MAXSIZE; j++){
               visited[i * prime[j]] = 1;
               if(i % prime[j] == 0) break;
           }
       }
       return index;
   }
   

3. 汉诺塔

   void hanoi(int n, int a, int b, int c)
   {
       if (n == 1)
           printf("%d->%d\n", a, c);
       else
       {
           fun(n - 1, a, c, b);
           printf("%d->%d\n", a, c);
           fun(n - 1, b, a, c);
       }
   }
   

三. 树

3.1 基础结构

1. AVL 树

   class AVLNode {
   private:
       AVLNode* rightRotate(AVLNode *root) {
           AVLNode* newRoot = root->lc;
           root->lc = newRoot->rc;
           newRoot->rc = root;
   
           root->height = max(getHeight(root->lc), getHeight(root->rc)) + 1;
           newRoot->height = max(getHeight(newRoot->lc), getHeight(newRoot->rc))+1;
   
           return newRoot;
       }
   
       AVLNode* leftRotate(AVLNode *root) {
           AVLNode* newRoot = root->rc;
           root->rc = newRoot->lc;
           newRoot->lc = root;
   
           root->height = max(getHeight(root->lc), getHeight(root->rc)) + 1;
           newRoot->height = max(getHeight(newRoot->lc), getHeight(newRoot->rc))+1;
   
           return newRoot;
       }
   
       AVLNode* leftRightRotate(AVLNode *root) {
           root->lc = leftRotate(root->lc);
           return rightRotate(root);
       }
   
       AVLNode* rightLeftRotate(AVLNode *root) {
           root->rc = rightRotate(root->rc);
           return leftRotate(root);
       }
   
   public:
       int height;
       AVLNode *lc;
       AVLNode *rc;
       int data;
   
       AVLNode() {}
   
       AVLNode(int data) : height(1), lc(NULL), rc(NULL), data(data){}
   
       int getHeight(AVLNode *node) {
           return node == NULL ? 0 : node->height;
       }
   
       AVLNode* insert(int data, AVLNode* root) {
           if(root == NULL) return new AVLNode(data);
   
           if(data < root->data) { //在左子树中插入
               root->lc = insert(data, root->lc); //递归插入
   
               if(getHeight(root->lc) - getHeight(root->rc) == 2) { //检查高度差, 调平
                   if(data < root->lc->data) root = rightRotate(root);
                   else root = leftRightRotate(root);
               }
           } else { //在右子树中插入
               root->rc = insert(data, root->rc);
   
               if(getHeight(root->rc) - getHeight(root->lc) == 2) { //检查高度差, 调平
                   if(data > root->rc->data) root = leftRotate(root);
                   else root = rightLeftRotate(root);
               }
           }
           root->height = max(getHeight(root->lc), getHeight(root->rc)) + 1;
           return root;
       }
   
       void printRoad(const int &data) {
           AVLNode *p = this;
   
           while(p!=NULL && p->data != data) {
               cout<<p->data<<' ';
               if(data < p->data) p = p->lc;
               else p = p->rc;
           }
           cout<<data<<endl;
       }
   };
   

2. 最近公共祖先(LCA)

   • 先算出每个节点的深度

     inline void getdeep(int now,int father)//now表示当前节点，father表示它的父亲节点
     {
        deep[now]=deep[father]+1;
        fa[now][0]=father;
        for(int i=1;(1<<i)<=deep[now];i++)
            fa[now][i]=fa[fa[now][i-1]][i-1];//这个转移可以说是算法的核心之一
                            //意思是f的2^i祖先等于f的2^(i-1)祖先的2^(i-1)祖先
                            //2^i=2^(i-1)+2^(i-1)
        for(int i=head[now];i;i=edge[i].next)//注意：尽量用链式前向星来存边，速度会大大提升
        {
            if(edge[i].to==father)continue;
            getdeep(edge[i].to,now);
        }
     }
     

   • c++ int lca(int x,int y){ if(deep[x]>deep[y]) swap(x,y); for(int i=ln;i>=0;i--){ if((deep[y]-deep[x])>>i & 1!=0) y=fa[y][i]; } if(x==y) return x; for(int i=ln;i>=0;i--){ if(fa[x][i]!=fa[y][i]){ x=fa[x][i];y=fa[y][i]; } } return fa[x][0]; }

四. 并查集

1. 并查集模板

   class DisJointSet {
   private:
       vector<int> fa;
   
   public:
       DisJointSet(int n) {
           for(int i=0; i<=n; i++) {
               fa.push_back(i);
           }
       }
   
       int getFa(int v) {
           if(fa[v] == v) return v;
           else rfa[v] = getFa(fa[v]);
       }
   
       //将u合并到v上
       void merge(int u, int v) {
           int fau = getFa(u);
           int fav = getFa(v);
           fa[fau] = fav;
       }
   };
   

五. 堆

1. priority_queue 自定义排序

   • c++ struct node { String data; int priority; bool operator< (const node &b) const{ return priority > b.priority; //小根堆 } }

   • 使用 pair (dijkstra 时常用)

     typedef pair<int, int> PII; //first 距离, second 点编号
     //小根堆
     priority_queue<PII, vector<PII>, greater<PII>> heap;
     

六. 图

6.1 最短路径

1. 单源最短路径 dijkstra 堆优化版本

   struct node{
       int d, i;
       bool operator < (const node &b) const {
           //重载'<',小根堆
           return d > b.d;
       }
   };
   
   void dijkstra(int s) {
       priority_queue<node> que;
       memset(d, inf, sizeof(d));
       d[s] = 0;
       que.push({d[s], s});
   
       while(!que.empty()) {
           node t = que.top(); que.pop();
           if(d[t.i] < t.d) continue;      //如果已经搜索过,跳过
   
           for(auto i:G[t.i]) {
               edge e = i;
               if(d[e.to] > d[t.i] + e.w) {
                   d[e.to] = d[t.i] + e.w;
                   que.push({e.to, d[e.to]});
               }
           }
       }
   }