21xrx.com
2024-12-22 15:03:31 Sunday
登录
文章检索 我的文章 写文章
C++经典算法代码
2023-07-05 15:42:09 深夜i     --     --
C++ 经典算法 代码 编程实践 数据结构

C++作为一种强大的编程语言,包含了很多经典的算法代码。这些算法代码在计算机科学和计算机编程领域都有着重要的应用。下面我们来看看其中的一些常见的算法。

1. 快速排序算法:快速排序是一种非常常用的排序算法,它的核心思想是通过划分不同的子序列,以最终实现排序。快速排序算法的代码如下:

void quicksort(int arr[], int left, int right)

{

  if (left < right) {

    int i = left, j = right, x = arr[left];

    while (i < j) {

      while (i < j && arr[j] >= x)

        j--;

      if (i < j)

        arr[i++] = arr[j];

      while (i < j && arr[i] < x)

        i++;

      if (i < j)

        arr[j--] = arr[i];

    }

    arr[i] = x;

    quicksort(arr, left, i - 1);

    quicksort(arr, i + 1, right);

  }

}

2. 最大公约数算法:最大公约数算法是求两个数的最大公约数,常见的解法有辗转相减和辗转相除。下面是辗转相除法的代码:

int gcd(int a, int b)

{

  if (b == 0)

    return a;

  else

    return gcd(b, a % b);

}

3. 线性求解方程组算法:线性求解方程组是计算机科学中的一项基础运算,可以通过矩阵的方法求解。线性方程组的代码如下:

void gauss_elimination(matrix &a, vector &b)

{

  int n = a.size(), m = a[0].size();

  for (int row = 0, col = 0; row < n && col < m; col++) {

    int pivot = -1;

    for (int i = row; i < n; i++) {

      if (a[i][col] != 0) {

        pivot = i;

        break;

      }

    }

    if (pivot == -1)

      continue;

    if (pivot != row)

      swap(a[pivot], a[row]), swap(b[pivot], b[row]);

    for (int i = row + 1; i < n; i++) {

      int factor = a[i][col] / a[row][col];

      b[i] -= factor * b[row];

      for (int j = col; j < m; j++) {

        a[i][j] -= factor * a[row][j];

      }

    }

    row++;

  }

}

4.迪杰斯特拉算法:迪杰斯特拉算法是解决图中最短路径问题的算法,它采用了贪心策略来寻找最短路径。迪杰斯特拉算法的代码如下:

const int INF = 0x3f3f3f3f;

typedef pair P;

int dijkstra(int s, int t)

{

  priority_queue , greater

> que;

  memset(dist, INF, sizeof(dist));

  memset(used, false, sizeof(used));

  dist[s] = 0;

  que.push(make_pair(0, s));

  while (!que.empty()) {

    P p = que.top();

    que.pop();

    int v = p.second;

    if (used[v])

      continue;

    used[v] = true;

    for (int i = 0; i < G[v].size(); i++) {

      edge e = G[v][i];

      if (dist[e.to] > dist[v] + e.cost) {

        dist[e.to] = dist[v] + e.cost;

        que.push(make_pair(dist[e.to], e.to));

      }

    }

  }

  return dist[t];

}

总之,C++中包含了很多经典的算法代码,这些算法可以用于各种计算机科学和计算机编程领域,如排序、最大公约数、线性方程组、最短路径等问题。程序员可以根据自己的需要选择使用其中的算法代码,以有效地解决各种计算机问题。

  
  

评论区

{{item['qq_nickname']}}
()
回复
回复