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< 
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 
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< 
xz@xiaqiu:~/study/algorithm/c++/1/build$ ./test 
7
7
xz@xiaqiu:~/study/algorithm/c++/1/build$ 

 
引用参数 
#include 
using namespace std;

template
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< 
#include 
using namespace std;

template 
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< 
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 
size_t count(const T& a)
{
	return sizeof(a) / sizeof(a[0]);
}

template 
size_t count1(const T(&a)[N])
{
	return N;
}

int main()
{
	int i[10];
	double d[10];
	St st[10];
	std::cout< 
模板fill 
#include 
using namespace std;

template 
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< 
inner_product 
#include 

template 
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< 
iota 
#include 

template 
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< 
is_sorted 
#include 
template 
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] 
mismatch 
#include 
using namespace std;

template 
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< 
抛出异常 
#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< 
sum求和 
#include 
template 
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< 
使用递归函数求和 
#include 

template
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< 
使用递归函数生成排列 
#include 
#include 
#include 
using namespace std;

template
void permutations(T list[],int k,int m)
{
	//生成 list[k:m] 的所有排列
	if(k == m)
	{
		//list[k:m] 仅有一个排列，输出它
		copy(list,list+m+1,ostream_iterator(cout," "));
		cout< 
std::accumulate 
#include 
#include 

template
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< 
std::accumulate 乘积 
#include 
#include 

template
T product(T a[],int n)
{
	//返回数组 ar[0:n-1] 的累计和
	T theProduct = 1;
	return std::accumulate(a,a+n,theProduct,std::multiplies());
}

int main()
{
	int a[] = {1,2,3,4,5};
	std::cout< 
STL 算法 copy 和 next_permutation 
//使用 STL 算法 next_permutation 求排列
#include 
#include 
#include 
#include 
using namespace std;

template
void permutations(T list[],int k,int m)
{
	//生成 1ist[k:m] 的所有排列
	//假设k <= m
	//将排列逐个输出
	do{
		copy(list,list+m+1,ostream_iterator(cout," "));
		cout< 
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
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 中元素移回 a
	for(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< 
选择排序 ( selection sort ) 
#include 
using namespace std;

template 
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 
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< 
冒泡排序 ( bubble sort ) 
#include 
#include 

//一次冒泡过程
template
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
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< 
//在一个有序数组中插入一个元素 
#include 
using namespace std;

template
void insert(T a[],int &n,const T& x)
{
	///把 x插入有序数组ar[0:n-1]
	 假设数组 a 的容量大于 n
	int 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< 
原地重排数组元素 
#include 
#include 

template
void rearrange(T a[], int n,int r[])
{
	//原地重排数组元素使之有序
	for(int i = 0; i 
及时终止的选择排序 
#include 
using namespace std;

template
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;
			else
				sorted = 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< 
及时终止冒泡排序 
#include 
using namespace std;

template
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
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< 
插入排序 
#include 
#include 

using namespace std;

template
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
void insertionSort(T a[],int n)
{
	//对数组a[0:n-1]实施插入排序
	for(int i = 1; i 
程序步数 
#include 
#include 
using namespace std;

int stepCount = 0;

template
T sum(T a[],int n)
{
	//返回数值数组元素a[0:n-1] 的和
	T theSum = 0; 
	stepCount++; //theSum = 0 是一个程序步
	for(int i = 0;i

c++ 算法学习

C/C++/C#相关栏目本月热门文章