526互联

重要代码片段

发布时间 2023-10-22 20:57:58作者: 汀洲杜若

重要代码片段

基础操作

asm volatile("mfence" ::: "memory") // x64屏障
x & 1                        // 奇偶性
x & (x-1)                    // x是否是2的幂次
(x + pow2 - 1) & ~(pow2 - 1) // x向上对齐到pow2
x |= x >> 1; //
x |= x >> 2; //
x |= x >> 4; //
x |= x >> 8; //
x |= x >> 16;//
x++;         // x向上对齐到最近的2的幂次
ones = 0;        //
while(x){        //
  x &= x - 1;    //
  ones++;        //
}                // 1的个数
其它以后再说

没有getline()

char *my_getline(size_t *_nread, size_t *_nalloc) {
    char line[MAXLINE], * heap = NULL, *temp;
    size_t n, nalloc = 0, hlen = 0;
    bool end = false;
    while (!end) {
        if (!(fgets(line, MAXLINE, stdin))) goto fail;
        if ((n = strlen(line)) == 0) goto fail;
        if (line[n - 1] == '\n') {
            line[n - 1] = '\0';
            end = true;
        }
        if (n > nalloc - hlen) {
            temp = (char*)realloc(heap, sizeof(char) * (n + hlen));
            if (!temp) goto fail;
            heap = temp;
            nalloc = n + hlen;
        }
        memcpy(heap + hlen, line, n);
        hlen += n - 1;
    }
    if (_nalloc) *_nalloc = nalloc;
    if (_nread)  *_nread  = hlen;
    return heap;
fail:
    if(heap) free(heap);
    return NULL;
}

排序

// 作为例子，全部排序整数，且非递减
// 冒泡排序
void bubble_sort(int *a, int n) {
  for(int i = n - 1; i > 0; i--) {
    BOOL ok = TRUE;
    for(int j = 0; j < i; j++) {
      if(a[j] > a[j+1]) {
        a[j] <-> a[j+1]; //交换
        ok = FALSE;
      }
    }
    if(ok) return;
  }
}
// 选择排序
void selection_sort(int *a, int n) {
  for(int i = 0; i < n-1; i++) {
    int minvalue = a[i], pos = i;
    for(int j = i+1; j < n; j++)
      if(a[j] < minvalue)
        minvalue = a[j], pos = j;
    a[pos] = a[i], a[i] = minvalue;
  }
}
// 插入排序
void insertion_sort(int *a, int n) {
  for(int i = 1; i < n; i++) {
    int temp = a[i];
    for(j = i; j > 0 && temp < a[j-1]; --j)
      a[j] = a[j-1];
    a[j] = temp;
  }
}
// 快速排序
int _partition(int *a, int n) {
  int temp, p, j, i = rand() % n;
  p = a[i], a[i] <-> a[0];      // 随便选一个数和[0]换位
  for(i = 1, j = 0; i < n; i++) // [0..j]始终均不大于[0]
    if(a[i] <= p)
      if(++j != i)
        a[j] <-> a[i];
  if(j > 0)
    a[0] = a[j], a[j] = p;      // [0]与[j]换位
  return j;
}
void quick_sort(int *a, int n) {
  if(n < 7) {
    insertion_sort(a, n);
  }else{
    int mid = _partition(a, n); // [mid]左边不大于右边
    quick_sort(a, mid);
    quick_sort(a + mid + 1, n - mid - 1);
  }
}
// 合并排序
void _do_merge(int *a, int first, int mid, int to, int *mem) {
  int ia = first, ib = mid, ic = 0;
  while(ia < mid && ib < to) {
    if(a[ia] <= a[ib])          // 不是'<' ！
      mem[ic++] = a[ia++];
    else
      mem[ic++] = a[ib++];
  }
  while(ia < mid) mem[ic++] = a[ia++];
  while(ib < to)  mem[ic++] = a[ib++];
  memcpy(a + first, mem, sizeof(int) * (to - first));
}
void _merge_sort(int *a, int m, int n, int *M) {
  if(n - m < 7)
    insertion_sort(a + m, n - m);
  else{
    int mid = (m + n) / 2;
    _merge_sort(a, m, mid, M);
    _merge_sort(a, mid, n, M);
    _do_merge(a, m, mid, n, M);//[m..mid-1]与[mid,n-1]合并，借助 `M`
  }
}
void merge_sort(int *a, int n) {
  M = (int*) malloc(sizeof(int) * n);// if(!M)...
  _merge_sort(a, 0, n, M);           // [0..n-1], 借助存储空间 `M`
  free(M);
}
// 堆排序
void _heap_adjust(int *a, int m, int n) {
  int p, save;
  for(save = a[m-1], p = m*2; p <= n; p *= 2) {
    if(p < n && a[p] > a[p-1]) ++p; // [p-1]是[m-1]的最大孩子节点
    if(a[p-1] <= save)
      break;
    a[m-1] = a[p-1];
    m = p;
  }
  a[m-1] = save;
}
void heap_sort(int *a, int n) {
  for(int i = n / 2; i > 0; --i)    //从最后一个分支节点[i-1]开始
    _heap_adjust(a, i, n);          //将[i-1..n-1]构建成大顶堆
  for(int i = n - 1; i > 0; --i) {
    a[0] <-> a[i];                  //[i..n-1]非递减，i减到1即完成
    _heap_adjust(a, 1, i);          //重新构建[0..i-1]为大顶堆
  }
}
其它以后再说

图相关

//为了简单说明这里一律使用邻接矩阵
struct gra_s {
  int vn;                // 顶点数
  int en;                // 边数目
  char *vnames[V_MAX];   // 各点的名字
  int mat[V_MAX][V_MAX]; // 邻接矩阵
};
// 正向DFS遍历
void _dfs(gra_t *G, int v, int *visited, int *order, int count) {
  int j = 0;
  order[count++] = v;
  visited[v] = TRUE;
next_adjacent_v:
  while(j < G->vn && G->mat[v][j] != 1) j++;
  if(j == G->vn) return;
  if(visited[j] == FALSE)
    _dfs(G, j, visited, order, count);
  ++j;
  goto next_adjacent_v;
}
//从G中顶点[v]开始沿各有向边做逆向DFS遍历，count是起始顺序序号
//返回从[v]遍历到的顶点个数
int _reverse_dfs(gra_t *G, int v, int *visited, int count) {
  int j = 0;
  if(++count > 1)
    putchar(',');
  printf("%s", G->vnames[v]);
  visited[v] = TRUE;
next:
  while(j < G->vn && G->mat[j][v] == 0) ++j;
  if(j == G->vn) return count;
  if(visited[j] == FALSE)
    _reverse_dfs(G, j, visited, count);
  ++j;
  goto next;
}
// 计算有向图G的强连通分量：先进行DFS遍历，记下访问顺序，
// 记为：<v_k1, v_k2, ... ,v_k?>，再从`v_k?`往前做反向DFS遍历
void components(gra_t *G) {
  int fin[V_MAX], order[V_MAX], i, count;
  if(!G) return;
  for(i = 0; i < G->vn; i++)   fin[i] = FALSE;
  for(i = 0; i < G->vn; i++) order[i] = 0;
  count = 0;
  for(i = 0; i < G->vn; i++)
    if(fin[i] == FALSE)
      _dfs(G, i, fin, order, count);
//这时得到order,即顶点被访问的顺序。order[x]=V代表：
//做正向DFS遍历时，第x个访问的顶点在G->vnames中的位置是V
  printf("** compoments: {");
  for(i = 0; i < G->vn; i++) fin[i] = FALSE;
  count = 0;           // 保存被访问过的顶点的个数
  for(i = G->vn - 1; i >= 0; i--)
    if(fin[i] == FALSE) {
      putchar('[');
      count += _reverse_dfs(G, i, fin, 0);
      putchar(']');
      if(count < G->vn) putchar(',');//还有别的分量
    }
  puts("}");
}
// 无向图的Kruskal算法
struct item{ int j, k, w; } *arcs = NULL; // 三元组<j,k,w>: 边<j,k>的权重是：w
void _heap_adjust(struct item *A, int p, int length){
  struct item temp;
  int ino, j;
  if(length <= 1) return;
  for(ino = p * 2, temp = A[p - 1];; ino <= length; ino = p * 2) {
    j = ino;
    if(ino < length && A[ino].w < A[ino - 1].w) j++;
    if(A[j - 1].w >= temp.w) break;
    A[p - 1] = A[j - 1];
    p = j;
  }
  A[p - 1] = temp;
}
void _make_heap(struct item *A, int length) {
  for(int i = length / 2; i > 0; --i)
    _heap_adjust(A, i, length);
}
BOOL Kruskal(gra_t *G, char *start_point) {
  int E[V_MAX], i, j, k, pj, pk, total;
  if(!G || !start_point) return FALSE;
  if(!(arcs=(struct item*)malloc(sizeof(struct item) * G->en)))
    return FALSE;
  for(i = 0; i < G->vn; i++) E[i] = -1; //各个顶点自成一个定价类
  k = 0;
  for(i = 1; i < G->vn; i++) //装填三元组<i,j,w>到arcs
    for(j = 0; j < i; j++)
      if(G->mat[i][j] != 0) {
        arcs[k].j = i, arcs[k].k = j, arcs[k].w = G->mat[i][j];
        k++;
      }
  _make_heap(arcs, G->en); //按边的权建小顶堆
  total = 0;               //最小生成树各边的权重和
  for(i = 1; i <= G->en; i++) {
    j = arcs[0].j, k = arcs[0].k; //堆顶是权重最小的边，选择它arcs[0]
    // 看看两个顶点[j],[k]是否在同一个等价类中
    for(pj = j; E[pj] >= 0; pj = E[pj]);
    for(pk = k; E[pk] >= 0; pk = E[pk]);
    // 如果不在同一个等价类中，则边<j,k>是最小生成树的一支
    if(pj != pk) {
      total += arcs[0].w;
      if(i > 1) putchar(',');
      printf("%s-%s", G->vnames[j], G->vnames[k]);
      if(E[pj] > E[pk])     //合并这两个等价类
        E[pj] = pk, E[pk]--;
      else
        E[pk] = pj, E[pj]--;
    }
    arcs[0] = arcs[G->en - i];       //抛弃这条边(arcs[0])
    _heap_adjust(arcs, 1, G->en - i);//重建小顶堆
  }
  if(arcs) free(arcs);
  printf(", total=%d\n", total);
  return TRUE;
}