科技企业网站,中等职业学校专业建设规划,多元网站建设,短网址恢复写在前面#xff1a;
本系列专栏主要介绍C的相关知识#xff0c;思路以下面的参考链接教程为主#xff0c;大部分笔记也出自该教程#xff0c;笔者的原创部分主要在示例代码的注释部分。除了参考下面的链接教程以外#xff0c;笔者还参考了其它的一些C教材#xff08;比… 写在前面
本系列专栏主要介绍C的相关知识思路以下面的参考链接教程为主大部分笔记也出自该教程笔者的原创部分主要在示例代码的注释部分。除了参考下面的链接教程以外笔者还参考了其它的一些C教材比如计算机二级教材和C语言教材笔者认为重要的部分大多都会用粗体标注未被标注出的部分可能全是重点可根据相关部分的示例代码量和注释量判断或者根据实际经验判断。如有错漏欢迎指出。
参考教程黑马程序员匠心之作|C教程从0到1入门编程,学习编程不再难_哔哩哔哩_bilibili
一、概述
算法主要是由头文件algorithm functional numeric组成
1algorithm是所有STL头文件中最大的一个范围涉及到比较、交换、查找、遍历操作、复制、修改等等。
2numeric体积很小只包括几个在序列上面进行简单数学运算的模板函数。
3functional定义了一些模板类用以声明函数对象。
二、常用遍历算法
1、算法简介 for_each //遍历容器 transform //将容器中的元素搬运到另一个容器中 2、for_each for_each(iterator beg, iterator end, _func); //遍历容器 // beg——开始迭代器 // end——结束迭代器 // _func——函数或者函数对象 #includeiostream
#includevector
#includealgorithm
using namespace std;void print01(int val)
{cout val ;
}
class print02
{
public:void operator()(int val){cout val ;}
};void test01()
{vectorintv;for (int i 0; i 10; i){v.push_back(i);}for_each(v.begin(), v.end(), print01);cout endl;for_each(v.begin(), v.end(), print02());cout endl;
}int main() {test01();system(pause);return 0;
}
3、transform transform(iterator beg1, iterator end1, iterator beg2, _func); // beg1——源容器开始迭代器 // end1——源容器结束迭代器 // beg2——目标容器开始迭代器 #includeiostream
#includevector
#includealgorithm
using namespace std;class Transform
{
public:int operator()(int v){return v; //可以对v做运算比如v100}
};
class Print
{
public:void operator()(int v){cout v ;}
};void test01()
{vectorintv;for (int i 0; i 10; i){v.push_back(i);}vectorintvTarget;vTarget.resize(v.size()); //目标容器需要提前开辟空间transform(v.begin(), v.end(), vTarget.begin(), Transform());for_each(vTarget.begin(), vTarget.end(), Print());cout endl;
}int main() {test01();system(pause);return 0;
}
三、常用查找算法
1、算法简介 find //查找元素 find_if //按条件查找元素 adjacent_find //查找相邻重复元素 binary_search //二分查找法 count //统计元素个数 count_if //按条件统计元素个数 //_func 函数或者函数对象 2、find
1功能描述查找指定元素找到返回指定元素的迭代器找不到则返回结束迭代器end()。
2函数原型 find(iterator beg, iterator end, value); // beg——开始迭代器 // end——结束迭代器 // value——查找的元素 #includeiostream
using namespace std;
#includealgorithm
#includevector
#includestringvoid test01()
{vectorint v;for (int i 0; i 10; i) {v.push_back(i 1);}//查找容器中是否有 5 这个元素vectorint::iterator it find(v.begin(), v.end(), 5);if (it v.end()){cout 没有找到! endl;}else{cout 找到: *it endl;}
}class Person
{
public:Person(string name, int age){this-m_Name name;this-m_Age age;}//重载bool operator(const Person p){if (this-m_Name p.m_Name this-m_Age p.m_Age){return true;}return false;}
public:string m_Name;int m_Age;
};void test02()
{vectorPerson v;//创建数据Person p1(aaa, 10);Person p2(bbb, 20);Person p3(ccc, 30);Person p4(ddd, 40);v.push_back(p1);v.push_back(p2);v.push_back(p3);v.push_back(p4);vectorPerson::iterator it find(v.begin(), v.end(), p2);if (it v.end()){cout 没有找到! endl;}else{cout 找到姓名: it-m_Name 年龄: it-m_Age endl;}
}int main() {test01();test02();system(pause);return 0;
}
3、find_if
1功能描述按条件查找元素找到返回指定位置迭代器找不到返回结束迭代器位置。
2函数原型 find_if(iterator beg, iterator end, _Pred); // beg——开始迭代器 // end——结束迭代器 // _Pred——函数或者谓词返回bool类型的仿函数 #includeiostream
#includevector
#includealgorithm
#includestring
using namespace std;class GreaterFive
{
public:bool operator()(int val){return val 5;}
};void test01()
{vectorintv;for (int i 0; i 10; i){v.push_back(i);}vectorint::iterator it;it find_if(v.begin(), v.end(), GreaterFive());if (it v.end()){cout 没有找到大于5的数 endl;}else{cout *it endl;}
}class Person
{
public:int m_Age;string m_Name;Person(int age, string name){this-m_Age age;this-m_Name name;}
};
class Greater20
{
public:bool operator()(Person p){return p.m_Age 20;}
};
void test02()
{vectorPersonv;Person p1(10 ,aaa);Person p2(20 ,bbb);Person p3(30 ,ccc);Person p4(40 ,ddd);v.push_back(p1);v.push_back(p2);v.push_back(p3);v.push_back(p4);vectorPerson::iterator it;it find_if(v.begin(), v.end(), Greater20());if (it v.end()){cout 没有找到年龄大于20的人 endl;}else{cout 找到力 endl;}
}int main() {test01();test02();system(pause);return 0;
}
4、adjacent_find
1功能描述查找相邻重复元素返回相邻元素的第一个位置的迭代器。
2函数原型 adjacent_find(iterator beg, iterator end); // beg——开始迭代器 // end——结束迭代器 #includeiostream
using namespace std;
#includealgorithm
#includevectorvoid test01()
{vectorint v;v.push_back(0);v.push_back(2);v.push_back(0);v.push_back(3);v.push_back(1);v.push_back(4);v.push_back(3);v.push_back(3);v.push_back(0);vectorint::iterator it;it adjacent_find(v.begin(), v.end());if (it v.end()){cout 未找到相邻重复元素 endl;}else{cout 找到相邻重复元素 *it endl;}
}int main() {test01();system(pause);return 0;
}
5、binary_search
1功能描述查找指定元素是否存在查到就返回true否则返回false。
2函数原型 bool binary_search(iterator beg, iterator end, value); // beg——开始迭代器 // end——结束迭代器 // value——查找的元素 // 注意: 虽然它查找效率高但是在无序序列中不可用 #includeiostream
using namespace std;
#includealgorithm
#includevectorvoid test01()
{vectorint v;for (int i 0; i 10; i){v.push_back(i); //如果容器不是有序的序列那么返回的结果可能会不准确}bool ret binary_search(v.begin(), v.end(), 9);if (ret){cout 找到元素9 endl;}else{cout 未找到元素9 endl;}
}int main() {test01();system(pause);return 0;
}
6、count
1功能描述统计元素个数统计元素出现次数。
2函数原型 count(iterator beg, iterator end, value); // beg——开始迭代器 // end——结束迭代器 // value——统计的元素 #includeiostream
using namespace std;
#includealgorithm
#includevectorvoid test01()
{vectorint v;v.push_back(1);v.push_back(2);v.push_back(4);v.push_back(5);v.push_back(3);v.push_back(4);v.push_back(4);cout 4元素个数为 count(v.begin(), v.end(), 4) endl;
}class Person
{
public:int m_Age;int m_Age2;Person(int a1, int a2){m_Age a1;m_Age2 a2;}bool operator(const Person p){if (m_Age2 p.m_Age2){return true;}else{return false;}}
};
void test02()
{vectorPersonv;Person p1(1, 10);Person p2(1, 10);Person p3(2, 10);Person p4(1, 20);v.push_back(p1);v.push_back(p2);v.push_back(p3);v.push_back(p4);cout 与p1同Age2的人数为 count(v.begin(), v.end(), p1)-1 endl;
}int main()
{test01();test02();system(pause);return 0;
}
7、count_if
1功能描述按条件统计元素个数元素出现次数。
2函数原型 count_if(iterator beg, iterator end, _Pred); // beg——开始迭代器 // end——结束迭代器 // _Pred——谓词 #includeiostream
using namespace std;
#includealgorithm
#includevectorclass Greater4
{
public:bool operator()(int val){return val 4;}
};
void test01()
{vectorint v;v.push_back(1);v.push_back(2);v.push_back(6);v.push_back(5);v.push_back(3);v.push_back(4);v.push_back(4);cout 大于4的元素个数为 count_if(v.begin(), v.end(), Greater4()) endl;
}class Person
{
public:int m_Age;int m_Age2;Person(int a1, int a2){m_Age a1;m_Age2 a2;}bool operator(const Person p){if (p.m_Age2 m_Age2){return true;}return false;}
};
class Greater15
{
public:bool operator()(const Person p){return p.m_Age2 15;}
};
void test02()
{vectorPersonv;Person p1(1, 10);Person p2(1, 10);Person p3(2, 30);Person p4(1, 20);v.push_back(p1);v.push_back(p2);v.push_back(p3);v.push_back(p4);cout Age215的人数为 count_if(v.begin(), v.end(), Greater15()) endl;
}int main()
{test01();test02();system(pause);return 0;
}
四、常用排序算法
1、算法简介 sort //对容器内元素进行排序 random_shuffle //洗牌指定范围内的元素随机调整次序 merge //容器元素合并并存储到另一容器中 reverse //反转指定范围的元素 2、sort
1功能描述对容器内元素进行排序。
2函数原型 sort(iterator beg, iterator end, _Pred); // beg——开始迭代器 // end——结束迭代器 // _Pred——谓词 #includeiostream
using namespace std;
#includealgorithm
#includevectorvoid myPrint(int val)
{cout val ;
}void test01()
{vectorint v;v.push_back(1);v.push_back(2);v.push_back(6);v.push_back(5);v.push_back(3);v.push_back(4);v.push_back(4);sort(v.begin(), v.end());for_each(v.begin(), v.end(), myPrint);cout endl;sort(v.begin(), v.end(),greaterint()); //改成降序for_each(v.begin(), v.end(), myPrint);cout endl;
}int main()
{test01();system(pause);return 0;
}
3、random_shuffle
1功能描述洗牌指定范围内的元素随机调整次序。
2函数原型 random_shuffle(iterator beg, iterator end); // beg——开始迭代器 // end——结束迭代器 #includeiostream
using namespace std;
#includealgorithm
#includevector
#includectimevoid myPrint(int val)
{cout val ;
}void test01()
{vectorint v;v.push_back(1);v.push_back(2);v.push_back(6);v.push_back(5);v.push_back(3);v.push_back(4);v.push_back(4);sort(v.begin(), v.end()); //升序排列for_each(v.begin(), v.end(), myPrint);cout endl;random_shuffle(v.begin(), v.end()); //打乱for_each(v.begin(), v.end(), myPrint);cout endl;
}int main()
{srand((unsigned int)time(NULL));test01();system(pause);return 0;
}
4、merge
1功能描述两个容器元素合并并存储到另一容器中两个容器必须是有序的。
2函数原型 merge(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest); // begx——容器x的开始迭代器 // endx——容器x的结束迭代器 // dest——目标容器的开始迭代器 #includeiostream
using namespace std;
#includealgorithm
#includevectorvoid myPrint(int val)
{cout val ;
}void test01()
{vectorint v;vectorint v2;for (int i 0; i 10; i){v.push_back(i);v2.push_back(i 1);}vectorintv3;v3.resize(v.size() v2.size()); //提前给目标容器分配空间merge(v.begin(), v.end(), v2.begin(), v2.end(), v3.begin());for_each(v3.begin(), v3.end(), myPrint);cout endl;
}int main()
{test01();system(pause);return 0;
}
5、reverse
1功能描述将容器内指定范围的元素进行反转。
2函数原型 reverse(iterator beg, iterator end); // beg——开始迭代器 // end——结束迭代器 #includeiostream
using namespace std;
#includealgorithm
#includevectorvoid myPrint(int val)
{cout val ;
}void test01()
{vectorint v;v.push_back(10);v.push_back(30);v.push_back(20);v.push_back(50);v.push_back(40);for_each(v.begin(), v.end(), myPrint);cout endl;reverse(v.begin(), v.end()); //首尾对调反转for_each(v.begin(), v.end(), myPrint);cout endl;
}int main()
{test01();system(pause);return 0;
}
五、常用拷贝和替换算法
1、算法简介 copy //容器内指定范围的元素拷贝到另一容器中 replace //将容器内指定范围的旧元素修改为新元素 replace_if //容器内指定范围满足条件的元素替换为新元素 swap //互换两个容器的元素 2、copy
1功能描述容器内指定范围的元素拷贝到另一容器中。
2函数原型 copy(iterator beg, iterator end, iterator dest); // beg——开始迭代器 // end——结束迭代器 // dest——目标容器的起始迭代器 #includeiostream
using namespace std;
#includealgorithm
#includevectorvoid myPrint(int val)
{cout val ;
}void test01()
{vectorint v;v.push_back(10);v.push_back(30);v.push_back(20);v.push_back(50);v.push_back(40);vectorintv2;v2.resize(v.size());copy(v.begin(), v.end(), v2.begin());for_each(v2.begin(), v2.end(), myPrint);cout endl;
}int main()
{test01();system(pause);return 0;
}
3、replace
1功能描述将容器内指定范围的旧元素修改为新元素。
2函数原型 replace(iterator beg, iterator end, oldvalue, newvalue); // beg——开始迭代器 // end——结束迭代器 // oldvalue——旧元素 // newvalue——新元素 #includeiostream
using namespace std;
#includealgorithm
#includevectorvoid myPrint(int val)
{cout val ;
}void test01()
{vectorint v;v.push_back(10);v.push_back(30);v.push_back(20);v.push_back(50);v.push_back(40);v.push_back(20);replace(v.begin(), v.end(), 20, 60);for_each(v.begin(), v.end(), myPrint);cout endl;
}int main()
{test01();system(pause);return 0;
}
4、replace_if
1功能描述将区间内满足条件的元素替换成指定元素。
2函数原型 replace_if(iterator beg, iterator end, _pred, newvalue); // beg——开始迭代器 // end——结束迭代器 // _pred——谓词 // newvalue——新元素 #includeiostream
using namespace std;
#includealgorithm
#includevectorvoid myPrint(int val)
{cout val ;
}class Greater25
{
public:bool operator()(int val){return val 25; //大于25的元素全部替换为60}
};
void test01()
{vectorint v;v.push_back(10);v.push_back(30);v.push_back(20);v.push_back(50);v.push_back(40);v.push_back(20);replace_if(v.begin(), v.end(), Greater25(), 60);for_each(v.begin(), v.end(), myPrint);cout endl;
}int main()
{test01();system(pause);return 0;
}
5、swap
1功能描述互换两个容器的元素交换的容器元素类型要相同。
2函数原型 swap(container c1, container c2); // c1——容器1 // c2——容器2 #includeiostream
using namespace std;
#includealgorithm
#includevectorvoid myPrint(int val)
{cout val ;
}void test01()
{vectorint v;vectorint v2;for (int i 0; i 10; i){v.push_back(i);v2.push_back(i 100);}for_each(v.begin(), v.end(), myPrint);cout endl;for_each(v2.begin(), v2.end(), myPrint);cout endl;cout ----------------------- endl;v.swap(v2);for_each(v.begin(), v.end(), myPrint);cout endl;for_each(v2.begin(), v2.end(), myPrint);cout endl;
}int main()
{test01();system(pause);return 0;
}
六、常用算术生成算法
1、算法简介
算术生成算法属于小型算法使用时包含的头文件为 numeric。 accumulate //计算容器元素累计总和 fill //向容器中添加元素 2、accumulate
1功能描述计算区间内容器元素累计总和。
2函数原型 accumulate(iterator beg, iterator end, value); // beg——开始迭代器 // end——结束迭代器 // value——起始值 #includeiostream
using namespace std;
#includealgorithm
#includevector
#includenumericvoid test01()
{vectorint v;for (int i 0; i 100; i){v.push_back(i);}cout accumulate(v.begin(), v.end(), 1000) endl; //1000 容器v中元素的总和
}int main()
{test01();system(pause);return 0;
}
3、fill
1功能描述向容器中填充指定的元素。
2函数原型 fill(iterator beg, iterator end, value); // beg——开始迭代器 // end——结束迭代器 // value——填充值 #includeiostream
using namespace std;
#includealgorithm
#includevector
#includenumericvoid myPrint(int val)
{cout val ;
}void test01()
{vectorint v;v.resize(10);fill(v.begin(), v.end(), 100);for_each(v.begin(), v.end(), myPrint);
}int main()
{test01();system(pause);return 0;
}
七、常用集合算法
1、算法简介 set_intersection //求两个容器的交集 set_union //求两个容器的并集 set_difference //求两个容器的差集 2、set_intersection
1功能描述求两个容器的交集两个集合必须是有序序列返回值是交集中最后一个元素的位置。
2函数原型 set_intersection(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest); // begx——容器x的开始迭代器 // endx——容器x的结束迭代器 // dest——目标容器的开始迭代器 #includeiostream
using namespace std;
#includealgorithm
#includevector
#includenumericvoid myPrint(int val)
{cout val ;
}void test01()
{vectorint v1;vectorint v2;for (int i 0; i 10; i){v1.push_back(i); //0-9v2.push_back(i 5); //5-14}vectorint v3;v3.resize(min(v1.size(), v2.size()));vectorint::iterator itEnd set_intersection(v1.begin(), v1.end(), v2.begin(), v2.end(), v3.begin());for_each(v3.begin(), itEnd, myPrint); //输出的是交集cout endl;for_each(v3.begin(), v3.end(), myPrint); //给v3开辟空间时可能会有多余cout endl;
}int main()
{test01();system(pause);return 0;
}
3、set_union
1功能描述求两个集合的并集两个集合必须是有序序列返回值是并集中最后一个元素的位置。
2函数原型 set_union(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest); // begx——容器x的开始迭代器 // endx——容器x的结束迭代器 // dest——目标容器的开始迭代器 //目标容器需要开辟的空间大小为两个容器空间的相加结果 #includeiostream
using namespace std;
#includealgorithm
#includevector
#includenumericvoid myPrint(int val)
{cout val ;
}void test01()
{vectorint v1;vectorint v2;for (int i 0; i 10; i){v1.push_back(i); //0-9v2.push_back(i 5); //5-14}vectorint v3;v3.resize(v1.size() v2.size());vectorint::iterator itEnd set_union(v1.begin(), v1.end(), v2.begin(), v2.end(), v3.begin());for_each(v3.begin(), itEnd, myPrint); //输出的是并集cout endl;for_each(v3.begin(), v3.end(), myPrint); //给v3开辟空间时可能会有多余cout endl;
}int main()
{test01();system(pause);return 0;
}
4、set_difference
1功能描述求两个集合的差集两个集合必须是有序序列返回值是差集中最后一个元素的位置。
2函数原型 set_difference(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest); // begx——容器x的开始迭代器 // endx——容器x的结束迭代器 // dest——目标容器的开始迭代器 //目标容器需要开辟的空间大小为两个容器空间的较大值 #includeiostream
using namespace std;
#include vector
#include algorithmclass myPrint
{
public:void operator()(int val){cout val ;}
};void test01()
{vectorint v1;vectorint v2;for (int i 0; i 10; i) {v1.push_back(i);v2.push_back(i 5);}vectorint vTarget;//取两个里面较大的值给目标容器开辟空间vTarget.resize(max(v1.size(), v2.size()));//返回目标容器的最后一个元素的迭代器地址cout v1与v2的差集为 endl;vectorint::iterator itEnd set_difference(v1.begin(), v1.end(), v2.begin(), v2.end(), vTarget.begin());for_each(vTarget.begin(), itEnd, myPrint());cout endl;cout v2与v1的差集为 endl;itEnd set_difference(v2.begin(), v2.end(), v1.begin(), v1.end(), vTarget.begin());for_each(vTarget.begin(), itEnd, myPrint());cout endl;
}int main() {test01();system(pause);return 0;
}
