C++学习笔记
-------------------------------------------------------------------
给一个无单向不循环链表的首结点l，编写程序反转链表，并返回反转后的链表首结点
struct llist_node {
int val;
struct llist_node *next;
};
struct llist_node *func(struct llist_node *l)
{
struct llist_node *cur = l;
struct llist_node *prev = NULL; // 指向链表当前节点的上一个节点
struct llist_node *next = NULL; // 指向链表当前节点的下一个节点
while (cur) {
next = cur->next;
cur->next = prev;
prev = cur;
cur = next;
}
return cur;
}-------------------------------------------------------------------
二、STL模板库----算法（algorithm）
我们所有的算法都是在algorithm头文件中声明，所以在使用前需要包含头文件
#include<algorithm>
1、排序
1）sort()（基于快排实现）
/* sort --- 对[first,last)范围内的成员进行排序（默认升序排序） first ：一种随机访问迭代器，用于指定要排序范围的起始成员 last ：一种随机访问迭代器，用于指定要排序范围的最后一个成员的下一个位置 */ template <class RandomAccessIterator> void sort (RandomAccessIterator first, RandomAccessIterator last); /* sort --- 对[first,last)范围内的成员进行排序（默认升序排序） first ：一种随机访问迭代器，用于指定要排序范围的起始成员 last ：一种随机访问迭代器，用于指定要排序范围的最后一个成员的下一个位置 comp ：调用者自己定义的排序方法 */ template <class RandomAccessIterator, class Compare> void sort (RandomAccessIterator first, RandomAccessIterator last, Compare comp);/*
ps:
时间复杂度为：
，N为first与last之间的距离
1、容器支持的迭代器类型必须是随机访问迭代器，这意味着，sort()只对array、vector、deque这3个容器提供支持。
2、如果对容器中指定范围的成员做默认升序排序，必须保证该成员类型支持<运算符的运算。
3、sort()函数在实现排序时，需要交换容器中元素的存储位置，这种情况下，如果容器中存储的是自定义的类对象，则该类内部必须提供移动构造函数和移动赋值运算符。
*/
2）stable_sort（基于归并实现）
/* stable_sort--- 对[first,last)范围内的成员进行排序（默认升序排序） first ：一种随机访问迭代器，用于指定要排序范围的起始成员 last ：一种随机访问迭代器，用于指定要排序范围的最后一个成员的下一个位置 */ template <class RandomAccessIterator> void stable_sort(RandomAccessIterator first, RandomAccessIterator last); /* stable_sort--- 对[first,last)范围内的成员进行排序（默认升序排序） first ：一种随机访问迭代器，用于指定要排序范围的起始成员 last ：一种随机访问迭代器，用于指定要排序范围的最后一个成员的下一个位置 comp ：调用者自己定义的排序方法 */ template <class RandomAccessIterator, class Compare> void stable_sort(RandomAccessIterator first, RandomAccessIterator last, Compare comp);/*
ps:
空间足够：时间复杂度为：
空间不足：时间复杂度为：
，N为first与last之间的距离
1、同sort()函数
2、可以保证不改变相等元素的相对位置。
*/
3）partial_sort（基于交换元素存储位置实现）
/* partial_sort--- 对[first,last)范围内的数据进行筛选并排序（默认升序排序） first ：一种随机访问迭代器，用于指定要排序范围的起始成员 middle ：一种随机访问迭代器，用于指定要排序的子范围的最后一个成员的下一个位置 last ：一种随机访问迭代器，用于指定要排序范围的最后一个成员的下一个位置 */ template <class RandomAccessIterator> void partial_sort (RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last);/* partial_sort--- 对[first,last)范围内的数据进行筛选并排序（默认升序排序） first ：一种随机访问迭代器，用于指定要排序范围的起始成员 middle ：一种随机访问迭代器，用于指定要排序的子范围的最后一个成员的下一个位置 last ：一种随机访问迭代器，用于指定要排序范围的最后一个成员的下一个位置 comp ：调用者自己定义的排序方法 */ template <class RandomAccessIterator, class Compare> void partial_sort (RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last, Compare comp);/*
ps:
时间复杂度为：
其中 N 指的是 [first, last) 范围的长度，M 指的是 [first, middle) 范围的长度。
1、同sort()函数
2、partial_sort() 会将 [first, last) 范围内最小（或最大）的 middle-first 个元素移动到 [first, middle) 区域中，并对这部分元素做升序（或降序）排序。剩余的元素不一定保持原来相对顺序。
*/
2、查找
1）find（基于==运算符）
/* find --- 在[first,last)范围内找到和目标元素值相等的第一个元素 first ：一种输入迭代器，用于指定要排序范围的起始成员 last ：一种输入迭代器，用于指定要排序范围的最后一个成员的下一个位置 val : 要查找的值 return ： successed --- 返回一个输入迭代器，指向查找到的第一个元素 failed --- 返回一个输入迭代器，与last指向相同 */ template <class InputIterator, class T> InputIterator find (InputIterator first, InputIterator last, const T& val);/*底层实现*/
template<class InputIterator, class T> InputIterator find (InputIterator first, InputIterator last, const T& val) { while (first!=last) { if (*first==val) return first; ++first; } return last; }/*
ps:
1、使用find()函数时，必须保证查找的元素支持==运算符
*/
2）find_if（基于==运算符）
/* find_if --- 在[first,last)范围内找到第一个符合查找规则（返回true）的元素 first ：一种输入迭代器，用于指定要排序范围的起始成员 last ：一种输入迭代器，用于指定要排序范围的最后一个成员的下一个位置 pred : 用户自定义的查找规则 return &
原文地址：https://blog.csdn.net/qq_45882170/article/details/140573731
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！