- 浏览: 318266 次
- 性别:
- 来自: 南京
文章分类
最新评论
-
huangyunbin:
swc.advance(); 这个什么时候被调用是最核心的 ...
滑动窗口计数java实现 -
80后的童年2:
深入浅出MongoDB应用实战开发网盘地址:https://p ...
MongoDB 从入门到精通专题教程 -
rryymmoK:
深入浅出MongoDB应用实战开发下载地址:http://pa ...
MongoDB 从入门到精通专题教程 -
u012352249:
怎么支持多个窗口啊?
滑动窗口计数java实现 -
rryymmoK:
深入浅出MongoDB应用实战开发百度网盘下载:链接:http ...
MongoDB 从入门到精通专题教程
* 冒泡排序
一轮比较所有相邻数据对,如果顺序不合适就交换,本轮只要发生过交换就再来一轮.
---------------------------------------
* 插入法排序
1,将头两个元素排序
2,接下来依次将每一个元素排到正确的位置
3,直到所有的元素都排完
-------------------------------
* 快速排序法
效率最高的排序方法
选出一个分界值,把数组分成两个部分
对于分成的两个部分分别再做同样的操作
选出分界值的方法:把第一个,中间,最后一个拿出来,取中间值
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
=============================================
* 模板
+ 自定义模板
+ 标准模板库(STL)
c++是一种强类型语言,一个变量类型一旦定义终身不变.
由此,模板编程又称为通用类型编程,也叫泛型编程.
一般情况按一般处理,特殊情况特殊处理.
编译器优先选用非模板函数.
模板声明和定义不要分开.(标准里是可以的,但是几乎所有的编译器都不支持)
注意函数模板要放在头文件中,声明和定义都要放在头文件中.因为模板就是一个样板.
模板名<类型实参> 共同构成类名.
========================================
* 标准模板库(STL)
+ 类模板叫容器,java里叫集合
+ 函数模板叫通用算法.
几乎所有的容器都有一个内部类:iterator(迭代器)
迭代器把类模板和函数模板联系在一起形成一个体系就是标准模板库(STL)
iterator里的封装了指针,但它又模仿指针操作.又称智能指针
在标准库里从来不直接用指针,用迭代来替代指针操作.
容器的区间是半开半闭的,*end不属于区间
* 容器的分类:
+ 序列式容器
- (重要)vector动态数组,重载的'[]'运算符
- deque(double end queue) 双端队列,首尾插入/删除数据方便
- (重要)list 双向链表
+ 关联式容器
- 所有的关联式容器都是二叉查找树模板
- map 映射 不允许重复
- multimap 多映射允许重复
- set 数据集 不允许重复
- multiset 多数据集 允许重复
* 容器的共性
+ 构造函数:都有无参,拷贝,区间构造函数
- 区间是由两个迭代器界定的一个范围.vector<int> v(beg,end)
+ 运算符的重载
- 包括: =,>,>=,<.<=,==,!=
- insert(迭代器,元素/*总是复制一份*/)//用迭代器指位置,而不是指针
- size() //容器中已经有的元素个数
- empty() //判断容器是否为空
- max_size() //这一种容器最大容量
- clear() //清空整个容器
- swap(c2) //跟另一个容器交换,swap(c1,c2)不是成员函数
+ 头文件的名字跟容器的名字一致
+ begin() //返回指向第一个元素的迭代器
+ end() //指向最后一个元素之后,因此end()指向的元素不属于这个容器
一轮比较所有相邻数据对,如果顺序不合适就交换,本轮只要发生过交换就再来一轮.
#include <iostream> using namespace std; #include <ctime> typedef int T ; void sort(T a[], int n) { bool bSwap = false; do{ bSwap = false; for(int i=1;i<n;i++){ if(a[i] < a[i-1]){ swap(a[i],a[i-1]); bSwap = true; } } }while(bSwap); } int main() { int N=10240; int a[N]; for(int i=0;i<N;i++) a[i] = N-i; time_t t1 = time(NULL); sort(a,N); time_t t2 = time(NULL); cout << "time:" << t2-t1 << endl; for(int i=0;i<10;i++) cout << a[i] << ' '; cout << endl; }
---------------------------------------
* 插入法排序
1,将头两个元素排序
2,接下来依次将每一个元素排到正确的位置
3,直到所有的元素都排完
void sort(T a[], int n) { int temp; int p; for(int i=1;i<n;i++){ temp = a[i]; for(p=i;p>0&&a[p-1]>temp;p--) a[p] = a[p-1]; a[p] = temp; } }
-------------------------------
* 快速排序法
效率最高的排序方法
选出一个分界值,把数组分成两个部分
对于分成的两个部分分别再做同样的操作
选出分界值的方法:把第一个,中间,最后一个拿出来,取中间值
//快速排序法完整方法(比较难) void sort(T a[], int n){ if(n<=1) return ; swap(*a,a[n>>1]); T* L = a+1; T* R = a+n-1; T v = *a; while(L<R){ while(*L<v&&L<R) L++; while(*R>=v&&R>a) R--; if(L<R) swap(*L,*R); } if(v>*R) swap(*a,*R); sort(a,R-a); sort(R+1,n-(R-a)-1); }
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
=============================================
* 模板
+ 自定义模板
+ 标准模板库(STL)
c++是一种强类型语言,一个变量类型一旦定义终身不变.
//sort.cc //函数模板 #include <iostream> using namespace std; template<typename/*可写成class*/ T> //模板头 void sort(T* a, int n){ //code.. } void sort(char* a[], int n){ //优先考虑非模板函数 //code... } template<typename T> //模板头 void disp(T* a, int n){ //code... } int main() { double ad[5] = { ... }; int ai[7] = { ... }; char ac[4] = { ... }; sort(ad,5); sort(ai,7); sort<char>(ac,4); disp(ad,5);//或disp<double>(ad,5); disp(ai,7); } //end main
由此,模板编程又称为通用类型编程,也叫泛型编程.
一般情况按一般处理,特殊情况特殊处理.
编译器优先选用非模板函数.
模板声明和定义不要分开.(标准里是可以的,但是几乎所有的编译器都不支持)
#include <iostream> using namespace std; template<typename T> T max(T* a, int n ){ T max = *a; for(int i=0; i<n; i++){ if(a[i]>max) swap(max,a[i]); } return max; } int main() { int a[3] = {1,2,3}; cout << max(a,3) << endl; double b[3] = {1.1,2.2,3.3}; cout << max(b,3) << endl; }
注意函数模板要放在头文件中,声明和定义都要放在头文件中.因为模板就是一个样板.
//类模板 template<typename T> class Stack{ //..... template<typename T> void show(Stack<T> s){ //code } int main() { Stack<int> si; //因为创建对象时不一定会传递参数,编译器不能确定类型 //在使用时,必须指定类型.其中传过去的类型也叫模板形参. //在确定模板类型的过程称为模板的实例化. //实例化类模板之后才会变成类,才能创建对象 Stack<double> sd; Stack<char> sc; //Stack<char>是类名 cout << sizeof(si) << endl;//输出结果会不一样 cout << sizeof(sd) << endl; cout << sizeof(sc) << endl;//所以它们不是同一个类型 }
模板名<类型实参> 共同构成类名.
#include <iostream> #include <string> using namespace std; template<typename T,typename U>//类模板 struct Pairs{ T first; U second; Pairs():first(T()),second(U()){ } Pairs(const T& t,const U& u):first(t),second(u){ } }; template<typename T, typename U>//函数模板 void show(Pairs<T,U> p){ cout << p.first << ',' << p.second << endl; } template<typename T, typename U>//函数模板 Pairs<T,U> mkpair(T t, U u) { return Pairs<T,U>(t,u); } int main() { Pairs<int, double> p1; Pairs<int, string> p2(100,"Hi"); //p1,p2是来自同一个模板的不同类型 show(p1); show(p2); show(Pairs<char,int>('A',33)); show(mkpair('A',33) ); }
========================================
* 标准模板库(STL)
+ 类模板叫容器,java里叫集合
+ 函数模板叫通用算法.
几乎所有的容器都有一个内部类:iterator(迭代器)
迭代器把类模板和函数模板联系在一起形成一个体系就是标准模板库(STL)
iterator里的封装了指针,但它又模仿指针操作.又称智能指针
在标准库里从来不直接用指针,用迭代来替代指针操作.
class iterator{ T* p; public: iterator(){ } iterator(const interator& i){ } iterator(T* q){ } operator*(){ } operator->(){ } operator++(){ } operator==(){ } operator!=(){ } };//它是一个内部类
容器的区间是半开半闭的,*end不属于区间
* 容器的分类:
+ 序列式容器
- (重要)vector动态数组,重载的'[]'运算符
- deque(double end queue) 双端队列,首尾插入/删除数据方便
- (重要)list 双向链表
+ 关联式容器
- 所有的关联式容器都是二叉查找树模板
- map 映射 不允许重复
- multimap 多映射允许重复
- set 数据集 不允许重复
- multiset 多数据集 允许重复
* 容器的共性
+ 构造函数:都有无参,拷贝,区间构造函数
- 区间是由两个迭代器界定的一个范围.vector<int> v(beg,end)
+ 运算符的重载
- 包括: =,>,>=,<.<=,==,!=
- insert(迭代器,元素/*总是复制一份*/)//用迭代器指位置,而不是指针
- size() //容器中已经有的元素个数
- empty() //判断容器是否为空
- max_size() //这一种容器最大容量
- clear() //清空整个容器
- swap(c2) //跟另一个容器交换,swap(c1,c2)不是成员函数
+ 头文件的名字跟容器的名字一致
+ begin() //返回指向第一个元素的迭代器
+ end() //指向最后一个元素之后,因此end()指向的元素不属于这个容器
//容器例子 #include <iostream> #include <list> using namespace std; int main() { list<int> l1; int a[5] = {3,4,5,6,7}; list<int> l2(a,a+5); cout << "l1.size():" << l1.size() << endl; cout << "l2.size():" << l2.size() << endl; list<int>::iterator it; for(it=l2.begin();it!=l2.end();it++) cout << *it << ' '; cout << endl; it = l2.begin(); it ++; l2.erase(it); l2.insert(l2.begin(),100); l2.insert(l2.end(),200); for(it=l2.begin();it!=l2.end();it++) cout << *it << ' '; cout << endl; }
发表评论
-
UC++之目录和文件操作
2009-06-05 11:55 1253* UC + 文件系统 - 目 ... -
用c++实现二叉树增删改查和快速排序算法
2009-06-02 13:18 2588//快速排序 #include <iostream ... -
快速排序完整示例
2009-06-01 21:04 1080#include <iostream> usin ... -
C++容器与迭代器
2009-06-01 17:55 1981* 容器的迭代器还有几种: + iterator:正常迭 ... -
C++算法与二叉树的实现
2009-05-30 18:35 2488* 输出格式控制 + 成员函数:width fill pr ... -
c++链表 异常 内部类 输出格式控制
2009-05-29 21:36 1682C(控制台) F(文件) ------------- ... -
C++之I/O
2009-05-27 21:26 1858* 重载 + 拷贝构造函数A(const A& o ... -
C++拷贝构造函数与运算符重载
2009-05-26 20:32 2405拷贝构造函数与运算符的重载 * 多态 - 前堤:继承,虚函 ... -
C++多态与类型转换
2009-05-25 17:10 1847c++中字符串的处理,用string进行处理,实际上它是一个类 ... -
类的继承
2009-05-24 09:42 9821,如何定义,实现一个类 ... -
面向对象编程
2009-05-23 19:20 703//倒计时 #include <iostr ... -
C++ 面向对象
2009-05-23 15:40 928* 指针简单总结 //接受命令行参数的函数 int main ... -
C与C++中的time相关函数
2009-05-23 14:03 1302本文从介绍基础概念入手,探讨了在C/C++中对日期和时间操作所 ... -
c++指针续
2009-05-23 11:16 964//常指针,或叫定指针:指 ... -
C++指针
2009-05-22 19:22 1162C++ 里有字符串类型string ,最大可支持1G,可用st ... -
数组本质
2009-05-21 18:52 1217数组是一片连续的内存空间,定义时一般指明大小和类型,这样编译器 ... -
C++用递归解决汉诺塔问题(续)
2009-05-19 12:16 920#include <iostream.h> ... -
c++ 递归实例二
2009-05-18 22:37 1650#include <iostream.h> ... -
C++用递归解决汉诺塔问题
2009-05-18 21:54 2541递归确实是一个不错的算法,可以将原来很复杂的问题简化.这里要注 ... -
C++ 入门
2009-05-15 21:31 0一次性修改LINUX环境变量:(bash)export $PA ...
相关推荐
STL 是一些常用数据结构(如链表、可变长数组、排序二叉树)和算法(如排序、查找)的模板的结合,主要由 Alex Stepanov 主持开发,于 1998 年被加入 C++ 标准。 有了 STL,程序员就不必编写大多数常用的数据结构和...
一个成员取得下一个成员,从头到尾“走过”结构中的元素〔就象排序算法不关心元素是存 放在数组中或是线性表中)。Stepanov 研究过一些算法可以用一种抽象的方式实现,而且不 会影响效率。 1.2 STL 历史 1985 年,...
讲述递归的实现和若干常用的排序算法。书中对讨论的每一种数据结构都给出了应用示例和运行结果。全书含有大量的例题,读者可以从这些例题中学习程序设计技巧和使用数据结构求解问题的方法。 本书内容丰富,取材新颖...
算法由模板函数体现,这些函数不是容器类的成员函数,是独立的函数,它们可以用于STL容器,也可以用于普通的C++数组等. 头文件:#include 在STL的泛型算法中有4类基本的算法: 1)变序型队列算法: 可以改变容器内的数据...
第23章 排序算法 339 23.1 元素入堆push_heap 339 23.2 创建堆make_heap 343 23.3 元素出堆pop_heap 348 23.4 堆排序sort_heap 351 23.5 是否为堆is_heap 352 23.6 局部排序partial_sort 354 23.7 ...
新版书着重利用标准模板库(STL),把书中开发的数据结构和算法与相应的STL实现方法相互关联。本书还增加了很多新的实例和练习题。 书中的应用实例是它的特色。Sahni博士为每一个数据结构和算法都提供了若干个应用...
18.4.2 排序算法的下限 第19章 动态规划 19.1 算法思想 19.2 应用 19.2.1 0/1背包问题 19.2.2 矩阵乘法链 19.2.3 所有顶点对之间的最短路径 19.2.4 带有负值的单源最短路径 19.2.5 网组的无交叉子集 19.3 参考及推荐...
c++ STL模板实现简单排序及元素的交换实例 本实例实现的排序方法是在开发中常用的排序算法模式
第23章 排序算法 339 23.1 元素入堆push_heap 339 23.2 创建堆make_heap 343 23.3 元素出堆pop_heap 348 23.4 堆排序sort_heap 351 23.5 是否为堆is_heap 352 23.6 局部排序partial_sort 354 23.7 ...
你将看到各种算法(排序、搜寻、排列组合、数据移动与复制…)的实现;你甚至将看到底层的memory pool 和高阶抽象的traits 机制的实现。那些数据结构、那些算法、那些重要观念、那些编程实务中最重要最根本的珍宝,...
10.3.5常用的排序算法 154 10.3.6常用的拷贝和替换算法 156 10.3.7常用的算术和生成算法 157 10.3.8常用的集合算法 158 10.4 STL综合案例 159 10.4.1案例学校演讲比赛 159 10.4.2案例:足球比赛 161
9.9 排序算法 111 9.9.1 对所有元素排序 111 9.9.2 局部排序 112 9.9.3 根据第n个元素排序 113 9.9.4 heap算法 114 9.10 已序区间算法 115 9.10.1 搜寻元素 115 9.10.2 合并元素 117 9.11 数值算法 120 9.11.1 加工...
JGL实现了许多功能,可满足对一个集合库的大多数常规需求,它与C++的模板机制非常相似。JGL包括相互链接起来的列表、设置、队列、映射、堆栈、序列以及反复器,它们的功能比Enumeration(枚举)强多了。同时提供了...
算法 一个排序可以用的C++函数模板,无意间需要对字符串集合CStringArray进行排序,但标准模板库STL提供的函数模板sort虽然功能强大,不过有些不便,可能我不太习惯吧,于是才想着要自编一个排序函数模板,方便和我...
第23章 排序算法 339 23.1 元素入堆push_heap 339 23.2 创建堆make_heap 343 23.3 元素出堆pop_heap 348 23.4 堆排序sort_heap 351 23.5 是否为堆is_heap 352 23.6 局部排序partial_sort 354 23.7 ...
1.6 C和C++ 1.7 简单的C程序介绍 1.8 输入和输出函数 1.9 C源程序的结构特点 1.10 书写程序时应遵循的规则 1.11 C语言的字符集 1.12 C语言词汇 1.13 Turbo C 2.0 集成开发环境的使用 1.13.1 Turbo C 2.0 ...
第二篇C++ STL 技术原理和组成 第3 章STL 技术原理· · · · · · · · · · · · · · · · · ·................................. 103 3-1 模板概述· · · · · · • · · · · · · · · · ·...
STL是C++中一个非常重要的库,它提供了许多基本数据结构和算法,如向量、列表、堆、排序等等。使用STL可以让程序员更加高效地编写代码,同时也可以提高代码的可读性和可维护性。 C++的应用范围非常广泛。在游戏
对于C++的STL的双向链表,排序算法有的模板并没有实现,因此给出来,大家参考。
7.3 一些简单排序算法的下界 7.4 谢尔排序 7.5 堆排序 7.6 归并排序 7.7 快速排序 7.7.1 选取枢纽元 7.7.2 分割策略 7.7.3 小数组 7.7.4 实际的快速排序例程 ...