数据结构期末复习

chapter1.0 Introduction

• 数据结构：包含数据对象D以及彼此之间的关系R。
  分为逻辑结构和物理结构：逻辑结构面向用户（线性表），物理结构面向硬件（数组、链表）
• 递归：包含base case，即终止条件；making progress：递归调用。
• 泛型：

chapter2.0 Algorithm analysis

• $\mathcal{O}$:$\leq$上界 $\Omega$:$\geq$下界 $\mathcal{o}$:精确上界
• 分治：分阶段把问题分成两个大致相等的子问题，然后递归求解。治阶段将两个子问题的解合并，之后做少量工作得到整个问题的解。
• 桶排序 3.0 最后

chapter3.0 List

• 带表头节点的单链表优点是便于维护
• new ListNode(element,ListNode next_node)
• 循环链表解决约瑟夫问题，rear永远指向出队前一个人，p永远指向最新出队的人，head指向第一个出队的人

  for (int i = 1; i < n; i++)
    for (int j = 1; j < k; j++) rear = rear.next;
    if (i == 1){
      head.next = rear.next;
      p = rear.next;
    }
    else{
      p.next = rear.next;
      p = rear.next;
    }
    rear.next = p.next;
  p.next = rear; rear.next = null;
  

• 单链表反转，用三个指针

  a,b,c = head,head.next,head.next.next; //若a,b为null则直接返回
  a.next = null;
  while(c != null){
    b.next = a;
    a = b;
    b = c;
    c = c.next;
  }
  b.next = a;
  header.next = b; //如果采用头指针 
  

• 静态链表：用一个二维数组实现链表的功能，单元包含element和next（存下一个元素的下标）
• 单链表双链表插入删除元素，注意不要出现t = x.left.right这种左右混淆的错误。

chapter3.1 Stack & Queue

• 栈：后进先出（LIFO）可以用链表和数组实现
• 队列：先进先出（FIFO）其中进入的位置为rear，出队列的位置为front
• 循环队列代码：front = (rear - length + 1 + m) % m = (rear + length - 1) % m

chapter4.0 非线性的数据结构--树

• 树的基本性质：
  • 节点的度：一个节点所含有的子树个数。树中最大的节点的度为数的度。
  • 树叶：度为0的节点。树枝：度不为0的节点。
  • 高度：根节点的高度一般为0，向下递增。
• 二叉树的性质：二叉树的度可能为0（空树）
  • 每个节点都有左右两个子节点（可能为空）。有序分为左右子树，普通的树的子树是无序的。
  • n节点的二叉树含有n-1条边，即树中无环。
  • 高为h的二叉树至少有$h+1$个节点，至多有$2^{h+1}-1$个节点。
  • 满二叉树：包含$2^{h+1}-1$个节点的二叉树。
  • 完全二叉树：删除完全二叉树最后几个元素，叶子只出现在最下面两层。
  • $n_0= n_2 + 1$，树的高度至少为$\lceil\log_2(n+1)\rceil -1$，至多为$n-1$
• 用前序中序建树：（若已知中后序类似，但前后序不唯一）

  void CreateBT(String pres,ins,BinaryNode t){
    if(pres.length() == 0) t = null;
    else{
        t = new BinaryNode(pres[0]);
        inpos = 0;
        while(ins.ch[inpos] != pres[0]) inpos++;
        CreateBT(pres(1,inpos),ins(0,inpos-1),t.left);
        CreateBT(pres(inpos+1,pres.length()-1),ins(inpos+1,,pres.length()-1),t.right);
    }
  }
  

• 构造线索树：存储时增加两个标记域区分存的是子女还是前驱后继,利用线索遍历时第一步找到第一个元素，之后进行迭代。

  void Inthread(Node p, Node pre){
    if(p != null){
      Inthread(p.left, pre);
      if(p.left == null){
        p.left = pre;
        p.leftthread = 1;
      }
      if(pre != null && pre.right == null){
        pre.right = p;
        pre.rightthread = 1;
      }
      pre = p;
      Inthread(p.right,pre);
    }
  }
  

• 森林的遍历：森林使用左子女右兄弟的方式将多个树连成一个二叉树，各树之间用右链相连。森林的先跟中跟后跟和树一致。注意森林的层次遍历节点和其右子节点是一个层次。
• 二叉搜索树
  • 没有两个键值相等，左孩子小于根节点小于右孩子，leftsize = leftsubtree nodes + 1。搜索树的删除操作：

    BinaryNode remove(x, Node t){ //t = root
      if (t == null) return t;
      if (x < t.element){t.left = remove(x,t.left);}
      elif(x > t.element){t.right = remove(x,t.right);}
      elif(t.left != null && t.right != null){
        t.element =  findMin(t.right);
        t.right = remove(t.element,t.right);
      }
      else{t = t.left == null ? t.right : t.left;}
      return t;
    }
    

• AVL树
  • 左左、右右：单旋转；
  • 左右、右左：双旋转，且先转下面的
  • 代码，看一遍ppt
• B树：平衡的m路搜索树，每个节点至少包含$\lceil m/2\rceil$个孩子，所有external nodes（空的）在同一层，且个数为keywords+1.
  • B树的插入如果子树数量超过了要求，则把中间的keyword向上提，直到都符合要求。
  • B树删除如果删除后不符合要求优先向右兄弟借，右兄弟不够则跟父节点三者一起合并。没有右兄弟向左兄弟借。

chapter5.0 Hash

• 哈希函数：取余,平方取中
• 线性探查，平方探查，双哈希($h_1(key) = k;h_2(key) = d,k+d,k+2d,\cdots$)

chapter6.0 Heap

• 本节中数组第一个位置为空。
• 堆的插入和删除

  void insert(x){
    int i = ++current_size;
    while(i != 1 && a[i/2]<x){
      a[i] = a[i/2];
      i /= 2;
    }
    a[i] = x;
  }
  void perc(int i){ //下滤，删除操作直接将最后元素赋给根，然后下滤
    for(temp = a[i]; 2*i+1 < current_size; i = child){ //i = child在一次循环最后进行
      child = 2*i+1; //假设从0开始算
      if (child != current_size-1; a[child]< a[child+1]) child++;
      if (temp < a[child]) a[i] = a[child];
    }
    a[child] = temp;
  }
  

• 建堆，堆排序：建堆直接加一个循环调用$n/2$次下滤操作即可，堆排序首先建堆，之后调用n-1次下滤，每次都把最后一个元素和根互换。

chapter7.0 Disjoint set

• 一个细节：数组中第一个位置为空。
• 两个操作：Union和find。分别有基础版本和路径压缩版本。
  • find基础版本:

    int find(int e){
        while(parent[e]) e = parent[e];
        return e;
    }
    

  • find 路径压缩版本：即找到parent后将路上所有元素直接连到root

    int find(int e){
        if (parents[e] < 0){return e;}
        else{return parents[e] = find(parents[e]);}
    }
    

  • union基础版本:int union(int root1,int root2){s[root1] = root2;}
  • union路径压缩版本：把短的挂到长的，少的挂到多的

    int union(int r1,int r2){//C版本，增加bool数组，parent[r]表示节点数目
        if(parent[r1] < parent[r2]){
            root[r1] = false; //r1不再是根节点
            parent[r2] += parent[r1];
            parent[r1] = r2;
        }
        else{...}
    }
    //可以令parent[root]为负数表示树的高度
    

chapter8.0 非线性数据结构--图

• 图$<V,E>$的性质：
  • 极大强连通子图称为强连通分量
  • 邻接矩阵$A_{i,j}$表示从i到j的权重，对称矩阵，对角元素一般为0
  • 邻接表：用链表表示所有的边(E)，需要V个链表
• 图的遍历：深度优先 广度优先

  void dfs(int v,visited){
    print(v)
    visited[v] = 1;
    w = first_neighbor(v)
    if (w != -1){
      if (visited[w] != 1) dfs(w);
      w = next_neighbor(v,w);
    }
  }
  void bfs(int v){
    visited[v] = 1;
    q.enquene(v);
    while(!q.isempty()){
      v = q.dequene();
      w = first_neighbor(v);
      while(w != -1){
        if (visited[w] != 1){
          print(w)
          visited[w] = 1;
          q.enquene(w);
        }
        w = next_neighbor(v,w);
      }
    }
  }
  

• 最小生成树算法：
  • kruscal: 将边排序（堆排序），每次取最短的且不成环

    void kruscal(){
      MinHeap H; DisjSet s;
      for (int i = 0; i < num_vertices;i++){
        e = H.deleteMin();
        u = s.find(e.u);
        v = s.find(e.v);
        if (u != v){ans++; s.union(u,v);} 
      }
    }
    

  • Prim: 从任意一点出发，每次选择最短的边，用到了nearvex和lowcost两个数组

    void prim(){
      for (int i = 1; i < n; i++){
        lowcost[i] = Edge[0][i];
        nearvex[i] = 0;
      }
      for (int i = 1; i < n; i++)
        int v = 0, min = MAXINT;
        for (int j = 1; j < n; j++)
          if (nearvex[j] != -1 && lowcost[j] < min){
            v = j;
            min = lowcost[j];
          }
        if (v){
          span_tree.insert(v)
          nearvex[v] = -1;
          for (int j = 1; j < n; j++)
            if (nearvex[j] != -1 && lowcost[j] > Edge[v][j]){
              nearvex[j] = v;
              lowcost[j] = Edge[v][j];
            }
        }
    }
    

• 最短路径：
  • Dijkstra: 每次选取最短的dist作为最优路径，即贪心,dist数组和path数组，s数组表示未被加入最短路的点

    void dijkstra(int v, int n){
      s[v] = 1;
      for (int i = 0; i < n-1; i++){
        min = MAXINT, u = v
        for (int j = 0; j < n; j++)
          if (!s[j] && dist[j] < min){u = j; min = dist[j];}
        s[u] = 1;
        for (int w = 0; w < n; w++)
          if (!s[w] && dist[w] > dist[u] + Edge[u][w]){
            dist[w] = dist[u] + Edge[u][w]; 
            path[w] = u;
          }
      }
    }
    

  • Bellman-Ford:考虑到终点经过$0,1,\cdots,n-2$个点的情况。

    void bellman(int v){
      for (int i= 0; i < n; i++)//这里就考虑了经过0个点的情况
        dist[i] = Edge[v][i];
        if (i != v && dist[i] < MAXINT)  path[i] = v;
        else path[i] = -1;
      for(int k = 2; k < n; k++)
        for(int u = 0; u < n; u++)
          if (u != v){
            for (int i = 0; i < n; i++)
              if (Edge[i][u] < MAXINT && dist[u] > dist[i]+ Edge[i][u]){
                dist[u] = dist[i]+ Edge[i][u];
                path[u] = i;
              }
          }
    }
    

  • floyed:简单的三重循环，距离数组a和path数组，后者存由i到j的路径倒数第二个节点。

    void floyed(){
      init operation;//初始化a，把存在的边存进去，相关信息也存到path里
      for(int k = 0; k < n; k++)
        for(int i = 0; i < n; i++)
          for(int j = 0; j < n; j++)
            if (a[i][k] + a[k][j] < a[i][j]){
              a[i][j] = a[i][k] + a[k][j];
              path[i][j] = path[k][j];
            }
    }
    

• 活动网络：
  • AOV 每次删除入度为零的点，删除其出边
  • AOE 关键路径：最长的路径

chapter9.0 Sort

• rank sort 第二章18页 先得到一个rank数组表示每个数字排名，之后遍历一轮按照rank进行swapwhile(r[i] != i){t = r[i]; swap(a[t],a[i]); swap(r[t],r[i])}
  一次swap表示一次数据交换，3次数据移动。时间复杂度为$\mathcal{O}(n^2)$
• 线性时间非比较类排序：稳定的
  • 基数排序（radix）:个十百千依次排序
  • 桶排序：分成若干区间，数据放进对应区间，分别快排，再连起来
• 选择排序 不稳定
  • 简单选择：每次选一个最大（小）的放到前面
  • 锦标赛：每次两两比较得到最优的，将其取出后原位置置为inf，再次进行排序，以此类推
  • 堆排序：见第六章
• 插入排序 稳定
  • 简单插入$\mathcal{O}(n^2)$ 折半插入：插入已有序列$\mathcal{O}(n\log n)$
  • shell：给定一个步长序列，每个步长得到的分组进行直接插入。$\mathcal{O}(n^{1.3})$
• 交换排序
  • 冒泡：$\mathcal{O}(n^2)$ 稳定
  • 快排:$\mathcal{O}(n\log n)$最坏$\mathcal{O}(n^2)$ 不稳定

    void quicksort(a,left,right){
      pivot = median3(a,left,right);
      for (;;){
        while(a[++i] < pivot)
        while(a[--j] > pivot)
        if (i < j) swap(a,i,j)
        else break;
      }
      swap(a,i,right-1);
      quicksort(a,0,i-1);
      quicksort(a,i+1,right);
    }
    

• 归并排序 $\mathcal{O}(n\log n)$稳定

题目整理

• 图的深度优先遍历和广度优先遍历：邻接表$\mathcal{O}(n + e)$ 邻接矩阵$\mathcal{O}(n^2)$
• 图的深度优先遍历可以用来判断有向（无向）图中是否有环，广度优先遍历只能判断无向图是否有环，拓扑排序可判断有向图是否有环。
• 直接选择排序的比较次数为：$\frac{n(n-1)}{2}$ 折半插入排序的比较次数为：$n\log_2 n$
• 改进冒泡排序：最好：$n-1$ 最坏：$\frac{n^2}{2}$
• 直接插入排序：最好：$n-1$ 最坏：$\frac{n(n-1)}{2}$