c++ 算法学习

1.2 函数与参数
CMakeLists.txt

cmake_minimum_required(VERSION 3.1)
project(test)
add_executable(test main.cpp)

#include 
using namespace std;
int abc(int a,int b,int c)
{return a + b * c;
}int main()
{int a = 1,b = 2,c = 3;std::cout<<abc(a,b,c)<<std::endl; //1+2*3 = 7return 0;
}

Scanning dependencies of target test
[ 50%] Building CXX object CMakeFiles/test.dir/main.cpp.o
[100%] Linking CXX executable test
[100%] Built target test
xz@xiaqiu:~/study/algorithm/c++/1/build$ ./test 
7
xz@xiaqiu:~/study/algorithm/c++/1/build$ 

模板函数

#include 
using namespace std;template <class T>
T abc(T a,T b,T c)
{return a + b * c;
}int main()
{int i1 = 1,i2 = 2,i3 = 3;double d1 = 1.0,d2 = 2.0,d3 = 3.0;std::cout<<abc(i1,i2,i3)<<std::endl;std::cout<<abc(d1,d2,d3)<<std::endl;return 0;
}

xz@xiaqiu:~/study/algorithm/c++/1/build$ ./test 
7
7
xz@xiaqiu:~/study/algorithm/c++/1/build$ 

引用参数

#include 
using namespace std;template<class T>
T abc(const T& a,const T& b, const T& c)
{return a + b * c;
}int main()
{float f1 = 1,f2 = 2, f3 = 3;cout<<abc(f1,f2,f3)<<endl;return 0;
}

#include 
using namespace std;template <class Ta ,class Tb,class Tc>
Ta abc(const Ta& a,const Tb& b, const Tc& c)
{return a + b * c;
}int main()
{double d = 1.3; int i = 2 ;float f = 3.0;cout<<abc(d , i , f)<<endl;return 0;
}

xz@xiaqiu:~/study/algorithm/c++/1/build$ make
Scanning dependencies of target test
[ 50%] Building CXX object CMakeFiles/test.dir/main3.cpp.o
[100%] Linking CXX executable test
[100%] Built target test
xz@xiaqiu:~/study/algorithm/c++/1/build$ ./test 
7.3
xz@xiaqiu:~/study/algorithm/c++/1/build$ 

计算数组的个数

#include 
struct St
{int a;int b;
};template <typename T>
size_t count(const T& a)
{return sizeof(a) / sizeof(a[0]);
}template <typename T, size_t N>
size_t count1(const T(&a)[N])
{return N;
}int main()
{int i[10];double d[10];St st[10];std::cout<<count(i)<<std::endl;std::cout<<count(d)<<std::endl;std::cout<<count(st)<<std::endl;std::cout<<count1(i)<<std::endl;std::cout<<count1(d)<<std::endl;std::cout<<count1(st)<<std::endl;return 0;
}

模板fill

#include 
using namespace std;template <typename T,size_t N>
void fill(T(&a)[N],T&& val)
{for(int i = 0;i < N;i++){a[i] = val;}
}int main()
{int array[10];fill(array,12);for(auto value : array){std::cout<<value<<" ";}cout<<endl;return 0;
}

inner_product

#include template <typename T,size_t N>
T inner_product(T(&a)[N],T(&b)[N])
{T ret = {};for(int i = 0;i < N;i++){ret += a[i] * b[i];}return ret;
}int main()
{int a[] = {1,1,1,1,1};int b[] = {2,2,2,2,2}; std::cout<<inner_product(a,b);std::cout<<std::endl;return 0;
}

iota

#include template <typename T,size_t N>
void iota(T(&a)[N],const T& value)
{for(int i = 0;i < N;i++)a[i] += value;
}int main()
{int a[] = {1,2,3,4};iota(a,10);for(auto value : a){std::cout<<value<<" ";}std::cout<<std::endl;return 0;
}

is_sorted

#include 
template <typename T,size_t N>
bool is_sorted(T(&a)[N])
{int toLow = 0;int toHigh = 0;for(int i = 0; i < N-1;i++){if(a[i]>a[i+1]){toLow++;}else if(a[i]<a[i+1]){toHigh++;}}if(toLow == N-1 || toHigh == N-1 ||(toLow == 0 && toHigh == 0)){return true;}else{return false;}
}int main()
{int a[] = {1,2,3,4,5,6};int b[] = {2,3,4,5,2};int c[] = {9,6,5,3,2,1};std::cout<<is_sorted(a)<<std::endl;std::cout<<is_sorted(b)<<std::endl;std::cout<<is_sorted(c)<<std::endl;return 0;
}

mismatch

#include 
using namespace std;template <typename T,size_t N1,size_t N2>
int mismatch(const T(&a)[N1],const T(&b)[N2])
{int len = N1 > N2? N2 : N1;for(int i = 0;i < len;i++){if(a[i] != b[i]){return i;}}return len;
}int main()
{int a[] = {1,2,3,4,5};int b[] = {1,2,3,2};int c[] = {1,2};std::cout<<mismatch(a,b)<<std::endl;std::cout<<mismatch(a,c)<<std::endl;return 0;
}

抛出异常

#include 
#include 
using namespace std;int abc(int a,int b,int c)
{if(a <= 0 || b <= 0 || c <= 0)throw std::logic_error("All parameters shold be >0");return a + b * c;
}int main()
{try{cout<<abc(1,0,2)<<endl;cout<<abc(1,2,2)<<endl;}catch(exception& e){cout<<e.what()<<endl;return 1;}return 0;
}

sum求和

#include 
template <class T,size_t N>
T sum(T(&a)[N])
{//返回数值数组元素a[0:n-1]的和T theSum = 0;for(int i = 0; i < N;i++){theSum += a[i];}return theSum;
}int main()
{double d[] = {1.2,2.,3.,4.,5.};int i[] = {2,3,4,5};std::cout<<sum(d)<<std::endl;std::cout<<sum(i)<<std::endl;return 0;
}

使用递归函数求和

#include template<class T>
T rsubm(T a[],int n)
{//返回数值数组元素a[0:n-1]的和if(n>0)return rsubm(a,n-1) + a[n-1];return 0;
}int main()
{double d[] = {1.2,2.,3.,4.,5.};int i[] = {2,3,4,5};std::cout<<rsubm(d,5)<<std::endl;std::cout<<rsubm(i,4)<<std::endl;return 0;
}

使用递归函数生成排列

#include 
#include 
#include 
using namespace std;template<class T>
void permutations(T list[],int k,int m)
{//生成 list[k:m] 的所有排列if(k == m){//list[k:m] 仅有一个排列，输出它copy(list,list+m+1,ostream_iterator<T>(cout," "));cout<<endl;}else{for(int i = k;i <= m;i++){swap(list[k],list[i]);permutations(list,k+1,m);swap(list[k],list[i]);}}
}int main()
{int a[] = {1,2,3,4};permutations(a,0,3);return 0;
}

std::accumulate

#include 
#include template<class T>
T sum(T a[],int n)
{//返回数组a[0:n-1]的累计和T theSum = 0;return std::accumulate(a, a+n, theSum);
}int main()
{int a[] = {1,2,3,4,5};std::cout<<sum(a,5)<<std::endl; //15return 0;
}

std::accumulate 乘积

#include 
#include template<class T>
T product(T a[],int n)
{//返回数组 ar[0:n-1] 的累计和T theProduct = 1;return std::accumulate(a,a+n,theProduct,std::multiplies<T>());
}int main()
{int a[] = {1,2,3,4,5};std::cout<<product(a,5)<<std::endl; //120return 0;
}

STL 算法 copy 和 next_permutation

//使用 STL 算法 next_permutation 求排列
#include 
#include 
#include 
#include 
using namespace std;template<class T>
void permutations(T list[],int k,int m)
{//生成 1ist[k:m] 的所有排列//假设k <= m//将排列逐个输出do{copy(list,list+m+1,ostream_iterator<T>(cout," "));cout<<endl;}while(next_permutation(list,list+m+1));
}int main()
{char a[] = {'a','b','c','d'};permutations(a,0,3);return 0;
}

xz@xiaqiu:~/study/algorithm/c++/1/build$ ./test 
a b c d 
a b d c 
a c b d 
a c d b 
a d b c 
a d c b 
b a c d 
b a d c 
b c a d 
b c d a 
b d a c 
b d c a 
c a b d 
c a d b 
c b a d 
c b d a 
c d a b 
c d b a 
d a b c 
d a c b 
d b a c 
d b c a 
d c a b 
d c b a 
xz@xiaqiu:~/study/algorithm/c++/1/build$ 

计数排序

#include template<class T>
void rearrange(T a[], int n, int r[])
{//使用一个附加数组 u，将元素排序T *u = new T[n]; //创建附加数组//把a中元素移到u中正确位置for(int i = 0;i < n;i++)u[r[i]] = a[i];//把u 中元素移回 afor(int i = 0;i < n;i++){a[i] = u[i];}delete []u;
}int main()
{int a[] = {4,3,9,3,7};int n[] = {2,0,4,1,3};rearrange(a,5,n);for(auto val : a){std::cout<<val<<" "; //3 3 4 7 9}std::cout<<std::endl; return 0;
}

选择排序 ( selection sort )

#include 
using namespace std;template <class T>
int indexOfMax(T a[],int n)
{//查找数组 a[0:n-1] 的最大元素if(n <= 0){cerr<<"n must be > 0";return -1;}int indexOfMax = 0;for(int i = 1;i < n;i++)if(a[indexOfMax] < a[i])indexOfMax = i;return indexOfMax;
}template <class T>
void selectionSort(T a[],int n)
{//给数组 a[0:n-1] 的 个元素排序for(int size = n;size>1;size--){int j = indexOfMax(a,size);swap(a[j],a[size - 1]);}
}int main()
{int a[] = {2,4,4,5,2,3,1,2,34,4};selectionSort(a,10);for(auto value:a){std::cout<<value<<" ";} //1 2 2 2 3 4 4 4 5 34 std::cout<<std::endl;return 0;
}

冒泡排序 ( bubble sort )

#include 
#include //一次冒泡过程
template<class T>
void bubble(T a[], int n)
{//把a[0:n-1]中最大元素移到右边for(int i = 0;i < n - 1;i++){if(a[i] > a[i+1]) std::swap(a[i],a[i+1]);}
}//冒泡排序
template<class T>
void bubbleSort(T a[],int n)
{// 对数组元素 a[0:n - 1] 使用冒泡排序for(int i = n;i>1;i--)bubble(a,i);
}int main()
{int a[] = {3,2,1,3,54,6};bubbleSort(a,6);for(auto value:a){std::cout<<value<<" "; //1 2 3 3 6 54 }std::cout<<std::endl;
}

//在一个有序数组中插入一个元素

#include 
using namespace std;template<class T>
void insert(T a[],int &n,const T& x)
{///把 x插入有序数组ar[0:n-1] 假设数组 a 的容量大于 nint i;for(i = n-1;i>=0 && x < a[i]; i--)a[i+1] = a[i];a[i+1] = x;n++;
}int main()
{int len = 5;int a[len] = {1,3,4,5,6};insert(a,len,2);for(int i = 0;i < len;i++){std::cout<<a[i]<<" "; //1 2 3 4 5 6}std::cout<<std::endl;
}

原地重排数组元素

#include 
#include template<class T>
void rearrange(T a[], int n,int r[])
{//原地重排数组元素使之有序for(int i = 0; i<n;i++){//把正确的元素移到a[i]while(r[i] != i){int t = r[i];std::swap(a[i],a[t]);std::swap(r[i],r[t]);}}
}int main()
{int a[] = {4,3,9,3,7};int n[] = {2,0,4,1,3};rearrange(a,5,n);for(auto val : a){std::cout<<val<<" "; //3 3 4 7 9}std::cout<<std::endl; return 0;
}

及时终止的选择排序

#include 
using namespace std;template<class T>
void selectionSort(T a[],int n)
{//及时终止的选择排序bool sorted = false;for(int size = n; !sorted && (size > 1);size--){int indexOfMax = 0;sorted = true;///查找最大元素for(int i = 1;i < size; i++){if(a[indexOfMax] <= a[i]) indexOfMax = i;elsesorted = false; //无序}swap(a[indexOfMax],a[size-1]);}
}int main()
{int a[] = {1,2,3,21,2,3,1};selectionSort(a,7);for(auto value : a){std::cout<<value<<" "; //1 1 2 2 3 3 21 }std::cout<<std::endl;return 0;
}

及时终止冒泡排序

#include 
using namespace std;template<class T>
bool bubble(T a[],int n)
{//把数组 a[0:n-1] 中的最大元素移到最右端bool swapped = false;// 目前为止未交换for(int i = 0; i < n-1;i++){if(a[i] > a[i+1]){swap(a[i],a[i+1]);swapped = true; //交换}}return swapped;
}template<class T>
void bubbleSort(T a[], int n)
{//及时终止冒泡排序for(int i = n; i > 1 && bubble(a,i); i--);
}int main()
{int a[] = {1,2,3,21,2,3,1};bubbleSort(a,7);for(auto value : a){std::cout<<value<<" "; //1 1 2 2 3 3 21 }std::cout<<std::endl;return 0;
}

插入排序

#include 
#include using namespace std;template<class T>
void insert(T a[],int n,const T& x)
{//把 x插入有序数组a[0:n-1]int i;for(i = n-1;i>=0 && x < a[i];i--)a[i+1] = a[i];a[i+1] = x;
}template<class T>
void insertionSort(T a[],int n)
{//对数组a[0:n-1]实施插入排序for(int i = 1; i<n;i++){T t = a[i];insert(a,i,t);}
}int main()
{int a[] = {1,2,3,21,2,3,1};insertionSort(a,7);for(auto value : a){std::cout<<value<<" "; //1 1 2 2 3 3 21 }std::cout<<std::endl;return 0;
}

程序步数

#include 
#include 
using namespace std;int stepCount = 0;template<class T>
T sum(T a[],int n)
{//返回数值数组元素a[0:n-1] 的和T theSum = 0; stepCount++; //theSum = 0 是一个程序步for(int i = 0;i<n;i++){stepCount++;//for 循环的每一次条件判断是一个程序步theSum += a[i];stepCount++;//theSum += a[i] 是一个程序步}stepCount++;stepCount++;//for 循环语句的最后一次条件判断是一个程序步//return theSum 是一个程序步return theSum;
}int main()
{int a[] = {1,2,3,21,2,3,1};std::cout<<sum(a,7)<<" "<<stepCount; //33 17std::cout<<std::endl;return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！