C++经典算法题精选 |21xrx.com

C++经典算法题精选

2023-07-02 00:47:44 深夜i -- --

C++ 算法经典题目精选

C++是一种高级程序设计语言，常用于解决计算机科学中的复杂问题。在计算机科学中，算法是一种清晰的问题解决方案，通常由一系列计算步骤组成。这篇文章会为大家介绍一些C++经典算法题，希望对大家的编程学习有所帮助。

1. 最短路径算法(Dijkstra算法)

Dijkstra算法是一种解决带权有向图或无向图的单源最短路径问题的算法。算法通过维护到源点的最短距离来不断更新其它点的最短距离。C++实现代码如下：

#include

using namespace std;

const int INF = 0x3f3f3f3f;

const int MAXN = 1e5+10;

struct edge

int to;

vector G[MAXN];

int d[MAXN];

int vis[MAXN];

void dijkstra(int s){

memset(vis, 0, sizeof(vis));

memset(d, INF, sizeof(d));

d[s] = 0;

priority_queue , vector >, greater > > q;

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

while(!q.empty()){

int x = q.top().second;

q.pop();

if(vis[x]) continue;

vis[x] = 1;

for(int i=0; i

int v = G[x][i].to, dis = G[x][i].dis;

if(d[v] > d[x] + dis){

d[v] = d[x] + dis;

if(!vis[v]) q.push(make_pair(d[v], v));

}

2.快速排序算法

快速排序算法是一种高效的排序算法，它通过划分一个数列为较小和较大两个部分，然后递归地排序两个部分。C++实现代码如下：

#include

using namespace std;

void quick_sort(int a[], int left, int right){

int i = left, j = right;

int pivot = a[left+(right-left)/2];

while(i <= j){

while(a[i] < pivot) i++;

while(a[j] > pivot) j--;

if(i <= j){

swap(a[i], a[j]);

i++;

j--;

}

if(left < j) quick_sort(a, left, j);

if(i < right) quick_sort(a, i, right);

}

3.哈希表算法(开放定址法)

哈希表是一种数据结构，它使用哈希函数将一个键映射到与之对应的值上。开放定址法是常用的哈希函数之一，它通过探查哈希表中空闲的位置来处理哈希碰撞。C++实现代码如下：

#include

using namespace std;

const int MAXN = 1e5+10;

const int DELETED = -1;

const double THRESHOLD = 0.75;

int hash_table[MAXN];

int hash_func(int key, int i){

return (key+i)%MAXN;

}

void insert(int key){

int i = 0, hash_value;

do{

hash_value = hash_func(key, i++);

if(hash_table[hash_value] == DELETED || !hash_table[hash_value]){

hash_table[hash_value] = key;

return;

}

}while(i < MAXN);

}

int main(){

memset(hash_table, DELETED, sizeof(hash_table));

//Code here

return 0;

}

以上是C++经典算法题的精选，这些算法经常出现在计算机科学的许多领域，如数据挖掘和机器学习等。希望通过这篇文章的介绍，能够对大家的C++编程学习产生帮助。

上一篇: idea打包java可执行jar包

下一篇: C++中字符串转整数的方法

评论区

()

相似文章