查找算法

顺序查找

适合线性表
- 存储结构为数组或链表
时间复杂度O(n)

  int seq_search(int[] a, int key, int n){
    for(int index = 0; index <n; index++){
      if(a[index] == key){
        return index;
      }
    }
    return -1;
  }

带哨兵的优化查找方法

  int seq_search(int[] a, int key, int n){
    int i;
    
    a[0] = key;
    
    for(i = n; a[0] != a[i]; i--){

    }
    return i;
  }

二分查找

要求：元素必须有序
时间复杂度O(logn)

  int binary_search(int[] a, int key, int n){
    int left = 0;
    int right = n - 1;
    int mid;
    while(left <= right){
      mid = left + (right - left) / 2;
      if(a[mid] == key){
        return mid;
      }
      else if (a[mid] > key){
        right = mid - 1;
      }
      else{
        left + mid + 1;
      }
    }
    return -1;
  }

递归方法

  int binary_search(int[] a, int key, int left, int right){
    int mid = left + (right - left) / 2;
    if(a[mid] == key){
      return mid;
    }
    else if (a[mid] > key){
      binary_search(a, key, left, mid - 1);
    }
    else{
      binary_search(a, key, mid + 1, right);
    }
  }

插值查找

在二分查找中每次都是从中间走，自主性较差
- 对于插值查找其中mid = low + (key - a[low])/(a[high]- a[low]) *(high - low)来自适应选择

  int insert_search(int[] a, int key, int left, int right){
    int mid = left + (right - left)* (key - a[left])/(a[right] - a[left]); 
    if(a[mid] == key){
      return mid;
    }
    else if (a[mid] > key){
      binary_search(a, key, left, mid - 1);
    }
    else{
      binary_search(a, key, mid + 1, right);
    }
  }

二叉查找树

性质
- 当某节点左子树不为空，则左子树上所有节点均小于根节点
- 当某节点右子树不为空，则右子树上所有节点均大于根节点
- 任意节点的左右子树也分别为二叉搜索树
复杂度
- 插入和查找时间复杂度均为O(logn)，最坏情况下为O(n)

二叉树查找

  BSTree* search(BSTree pTree, int key){
    if(pTree == nullptr || pTree->data == key){
      return pTree;
    }
    if(pTree->data > key){
      return BSTree(pTree->left, key);
    }
    if(pTree->data < key){
      return BSTree(pTree->right, key);
    }
  } 

分块查找

把元素放在不同块，每个块内部元素不必有序，但是块之间有序
先用二分查找查找在哪个块，然后在进行顺序查找

  typedef struct{
    int key;
    int start;
    int stop;
  }Node;

  typedef struct{
    Node idx[10];
    int len;
  }IdxTable;

  IdxTable table;

  int block_search(int[] a, int key){
    int low = 1;
    int high = table.len;
    int mid;
    while(low <= high){
      mid = low + (high - low) / 2;
      if(key <= table.idx[mid].key){
        if(key <= table.idx[mid-1].key){
          high = mid -1;
        }
        else{
          for(int i = table.idx[mid].start; i <=table.idx[mid].end; i++){
            if(key == a[i]){
              return (i+1);
            }
          }
          return -1;
        }
      }
      else{
        low = mid + 1;
      }
    }
    return -1;
  }

哈希查找

key-value键值对查找，是一种时间换空间的查找方法

非递归遍历二叉树

先序遍历

  void pre_traverse(BinaryTree* T){}
    if(T == nullptr){
      return;
    }
    printf(T->data);
    pre_traverse(T->left);
    pre_traverse(T->right);

中序遍历

  void mid_traverse(BinaryTree* T){}
    if(T == nullptr){
      return;
    }
    pre_traverse(T->left);
    printf(T->data);
    pre_traverse(T->right);

后序遍历

  void mid_traverse(BinaryTree* T){}
    if(T == nullptr){
      return;
    }
    pre_traverse(T->left);
    pre_traverse(T->right);
    printf(T->data);

层序遍历

  void layer_traverse(TreeNode* Tree){
    queue<TreeNode*> s;
    if(Tree == nullptr){
      return;
    }
    s.push(Tree);
    while(!s.empty()){
      TreeNode* cur = s.front();
      cout << cur->val;
      if(cur->left != nullptr){
        s.push(cur->left);
      }
      if(cur->right != nullptr){
        s.push(cur->right);
      }
      s.pop();
    }
  }

KMP算法

KMP算法传统的字符串匹配是通过暴力算法得到，为了减少匹配次数，对待匹配子串建立next数组通过next数组确定跳转位置

next数组是pattern串的属性，next[i]表示字符串前i+1位前缀和后缀相同的位数

如abcabd的next[0] =0、next[1]为前两位ab，前后缀无相同项，next[3]表示abca，其中前缀a和后缀a相同，next[3] = 1，最终next = [0,0,0,1,2,0]

    void get_next(string a, int* next){
      next[0] = 0;
      for(int i = 1; i < a.size(); i++){
        while(j > 0 && a[i] != a[j]){
          j = next[j-1];
        }
        if(a[i] == a[j]){
          j++;
        }
        next[i] = j;

      }
    }
    int kmp(string cur, string pattern){
      int length = pattern.size();
      int* next = int[length];
      get_next(pattern, next);
      for(int i = 0, j = 0; i < cur.size(); i++){
          while(j >0 && a[i] != a[j]){
            j = next[j-1];
          }

        if(s[i] == s[j]){
          j++;
        }
        if(j == pattern.size()) return i - j + 1;
        if(i = cur.size()) return -1;
      }
    }

最小生成树——Prim

一些宏

  const int MAXN = 1000, INF = 0x3f3f3f3f; // 定义一个INF表示无穷大
  int g[MAXN][MAXN], dist[MAXN],n,m,res;
  // 使用g[][]数组存储图，dist[]存储到集合S的距离，res保存结果
  bool book[MAXN];
  // 存储某个点是否保存到集合S

main

  int main()
  {
      cin>>n>>m;  //读入图点数 n 和边数 m

      for(int i = 1; i<= n; i++)
      {
          for(int j = 1; j <= n; j++)
          {
              g[i][j] = INF;  //初始化任意两个点之间的距离为正无穷（表示这两个点之间没有边）
          }
          dist[i] = INF;  //初始化所有点到集合S的距离都是正无穷
      }
      
      for(int i = 1; i <= m; i++)
      {
          int a, b, w;
          cin >> a >> b >> w;  //读入a，b两个点之间的边
          g[a][b] = g[b][a] = w;  //由于是无向边，我们对g[a][b]和g[b][a]都要赋值
      }

      prim();  //调用prim函数
      if(res==INF)  //如果res的值是正无穷，表示不能该图不能转化成一棵树，输出orz
          cout<<"orz";
      else
          cout<<res;//否则就输出结果res
      return 0;
  }

prim实现

  void prim(){
    dist[1] = 0;
    book[1] = true;
    for(int i = 2; i <= n; i++){
      dist[i] = min(dist[i], g[1][i]);
    }
    for(int i = 2; i <= n ;i++){
      int temp = INF;
      int index = -1;
      for(int j = 2; j <= n; j++){
        if(!book[j] && dist[j] < temp){
          temp = dist[j];
          index = j;
        }
      }
      if(index == -1){
        res = INF;
        return;
      }
      book[index] = true;
      res += dist[index];
      for(int j = 2; j <= n; j++){
        dist[j] = min(dist[j], g[index][j]);
      }
    }
  }

最小生成树 Kruskal

类型定义

  #define MAXEDGE 100
  #define MAXVERTEX 100

    typedef struct Edge{
      int begin;
      int end;
      int weight;
    } Edge;

    typedef struct Graph{
      char vertex[MAXVERTEX];
      Edge edges[MAXEDGE];
      int numvertex, numedges;
    } MGraph;

main

  int main(){
    MGraph G;
    CreateGraph(&G);
    Kruskal(&G);
    
    return 0;
  }

CreateGraph

  void CreateGraph(MGraph* G){
    scanf("%d%d",&G->numvertex, &G->numedges);
    for(int i = 0; i < G->numvertex; i++){
      scanf("%c",&G->vertex[i]);
    }
    for(int k = 0; k < G->numedges; k++){
      Edge edge;
      scanf("%d%d%d",&edge->begin,&edge->end, &edge->weight);
      G->edges[k] = e;
    }
  }

Kruskal算法

重要的是其中的find函数用于判断是否有环，parent实际内容指向下一个节点

  void Kruskal(MGraph* G){
    int parent[MAXVERTEX];
    for(int i = 0; i <G->numvertex; i++){
      parent[i] = 0;
    }
    for(int i = 0 ;i < G->numedges; i++){
      int m = find(parent, G, G->edges[i].begin);
      int n = find(parent, G, G->edges[i].end);
      if(m != n){
        parent[m] = n;
        printf("%d%d%d",G->edges[i].begin,G->edges[i].end,G->edges[i].weight);
      }
    }
  }

  int find(int* parent, int edgepo){
    while(parent[edgepo] >0){
      edgepo = parent[edgepo];
    }
    return edgepo;
  }

上篇数据结构

下篇特殊数据结构