2005.9.4Template（模版）
z 模板使我们可以用一个代码段指定一组相关函 数（称为模板函数）或一组相关类（称为模板 类）
z 模板是C++的软件复用的功能之一函数模版 int min(int a, int b) { return a < b ? a : b; }
double min(double a, double b) { return a < b ? a : b; }
替代这种“为每个min()实例都显示定义一个函 数”的方法
Template Type min(Type a, Type b) { return a < b ? a : b; }类模版 z 类模板的用途很多，最常用的是提供具备高度 适应性的存储容器。 z template public: T1 first; T2 second; pair(T1 x, T2 y): first(x), second(y) {} };STL组件关系 容器类 迭代器 算法 vector sort 用迭代器连接容器和算法STL程序示例 #include int ia[6] = { 27, 210, 12, 47, 109, 83 }; vector } // result: 4 83 109 47 12 210 27 vec.begin() vec.end()STL中的容器 顺序容器 Sequence Containers 关联容器 Associative Containers 容器 Containers vector deque list set, multiset map, multimapSTL中的容器 容器适配器 stack queue priority _queue算法举例简介 STL中用到了各种算法：排序、查询、排 列组合、数据搬移与复制等 z 分治算法 z 动态规划 z 回溯算法 z 贪心算法参考书目 z 标准模板库自修教程与参考手册—STL进行 C++编程, D.R.Musser, G.J.Derge, A.Saini. z C++大学教程, H.M.Deitel, P.J.Deitel. z C++语言的设计和演化, Bjarne Stroustrup. z STL源码剖析, 候捷. //SGI STL z 设计模式: 可复用面向对象软件的基础, Erich Gamma 等. 练习题 z 法雷序列(Farey Series) 对任意给定的一个自然数n，将分母小于等于n的不可 约的真分数按上升的次序排列，并且在第一个分数前 加上数0/1，而在最后一个分数后加上数1/1，这个序 列被称为n级法雷序列，以Fn表示。例如，F8 为： 0/1, 1/8, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 3/8, 2/5, 3/7, 1/2, 4/7, 3/5, 5/8, 2/3, 5/7, 3/4, 4/5, 5/6, 6/7, 7/8, 1/1 如果将这些数在数轴上表示出来，它们的分布是不规 则的。 z 请编写一个用链表来求任意n级法雷序列Fn的算法， 并在机器上调试实现。要求算法能反复若干次给定不 同n，求Fn。也可用STL实现，探讨不同STL的时间 性能。 z 提示：不能直接比较实数的等与不等。作业 z 实现多项式的加、减、乘、除和mod五个函数： z 加法：(x^5+2*x^4+x^3) + (4*x^3) = x^5+2*x^4+5*x^3 z 减法：(x^5+2*x^4+x^3) - (4*x^3) = x^5+2*x^4- 3*x^3 z 乘法：(x+1) * (x+1) = x^2+2*x+1 z 除法：(x^2+2*x +2) / (x+1) = x+1 z mod：(x^2+2*x +2) ％ (x+1) = 1 z 存储采用链表。注意要考虑特殊情况下的处理。 测试程序的界面可以自由发挥。作业 1. 多项式的系数为实数。 2. 求mod的时候一定要注意结果多项式的次数 要小于除式多项式的次数。 3. 多项式为一元的。也就是只包括一个未知数 x。 4. 加减乘除是多项式的。而不是多项式带入x后 的值进行加减乘除。vector 1. 实际上就是个动态数组。 2. 随机存取任何元素都能在常数时间完成。 3. 在尾端增删元素具有较佳的性能。 STL是如何实现vector的呢vector vector for (i=v1.begin();i!=v1.end();i++) { v2.push_back(*i); //在末尾插入 } for (i=v1.begin();i!=v1.end();i++) { v2.insert(v2.begin(),*i); //指定位置插入 }vector vector vector1.pop_back();//在末尾删除 } j=find(vector1.begin(),vector1.end(),’m’); vector1.erase(j--);//指定位置删除vector z vector中的元素被C++标准限定为存储在连续 内存中，就像是一个数组 5 4 8 7 1 [0] [1] [2] [3] [4] element max_size - 1 size = 5 1. 对vector的随机访问效率很高 因为每次访问离vector起始处的位移都是固定的 2. 在任意位置，而不是在vector末尾插入（删除） 元素，效率很低 因为需要把待插入元素右边的每个元素都拷贝一 遍 3. 预留足够的空间很重要 如果旧空间不足，会重新配置一块更大的空间， 然后复制元素，再释放旧空间vector vector (const int* pInts, size_t numInts); 我们可以这样做 doSomething(&v[0], v.size()); 像操纵数组一样方便的操纵vector！deque z 也是个动态数组。 z 随机存取任何元素都能在常数时间完成(但次 于vector)。 z 在两端增删元素具有较佳的性能。 deque和vector有什么区别吗deque for(i=deque1.begin(); i!=deque1.end(); i++) { deque2.push_front(*i);//在起点插入 } deque2.pop_front();//在起点删除 deque允许常数时间内对头端进行元素的 插入或删除动作deque vector 连续的内存中 deque 实现时，deque是动态的以分段连续空间组合 而成，随时可以增加一段新的空间并连接起来 尾端增删元素具有较佳的性能 两端增删元素具有较佳的性能list z 双向链表。 z 在任何位置增删元素都能在常数时间完成。 z 不支持随机存取。 N 1 2 3 4 LeftEnd RightEnd 1. 任意位置插入和删除元素的效率都很高 指针必须被重新赋值，但是，不需要用拷贝元素 来实现移动 2. 对随机访问的支持不好 访问一个元素需要遍历中间的元素 3. 每个元素还有两个指针的额外空间开销关联容器 z set/multiset set 即集合。set中不允许相同元素，multiset 中允许存在相同的元素。 z map/multimap map与set的不同在于map中存放的是成对的 key/value。并根据key对元素进行排序，可快 速地根据key来检索元素。关联容器 关联容器绝大部分的实现是使用的红黑 树——平衡树的一种关联容器 z 平衡树vs.非平衡树 1 2 3 4 5 1 2 3 4 5 平衡树 非平衡树stack z 是项的有限序列。 z 并满足序列中被删除、检索和修改的项只能是 最近插入序列的顶。 z 即按照先进后出的原则 top PUSH top POPstack z stack既可以通过线性表实现，又可以通过链 表实现 栈顶 5 4 8 7 1 [0] [1] [2] [3] [4] element max_size - 1 size = 5 N 1 2 3 4 LeftEnd RightEnd 栈顶stack stack stack stack z 插入只可以在尾部进行。 z 删除、检索和修改只允许从头部进行。 z 按照先进先出的原则。 [0] [1] [2] [3] [4] 排队买汉堡queue z 我们可以通过线性表实现queue A B C D front rear 插入 rear 删除 front 队列的平移 B C D rear front 效率queue queue queue queue 和栈适配器的不同？ 没有vector的形式queue z queue适配器不能用于vector容器，因为 vector没有pop_front操作。 z 为什么vector不把pop_front操作包含到它的 接口中？ z 因为这种操作对于大的向量效率非常低。 z STL尽量避免低效的使用方式分治算法 z 分治策略的实例——二分搜索、归并排序 2 5 1 3 9 8 7 4 排序 2 5 1 3 9 8 7 4 2 5 1 3 9 8 7 4 2 5 1 3 9 8 7 4 STL里面的quick_sort——快速排序算法也 是用的分治策略动态规划 z 投资问题 m元钱，n项投资，fi (x)：将x元投入第i项项目 的效益 目标函数 max{f1(x1) + f2(x2) + „ + fn(xn)} 约束条件 x1 + x2 + „ + xn = m, xi N z 实例：5万元钱，4个项目，效益函数如下图 ∈动态规划 z 设Fk(x)表示x元钱投给前k个项目的最大效益 z 多步判断 z 假设知道p元钱（p≤x）投给前k-1个项目 的最大效益，决定x元钱投给前k个项目的分配 方案 z 递推方程和边界条件 z )} ( ) ( { max ) ( 1 0 k k k k x x k x x F x f x F k − + = − ≤ ≤ ) ( ) ( 1 1 x f x F = •递推公式采用自底向上的 方式，用更小的局部最优 解来表示更高层次的局部 最优解，反复递推最终达 到全局最优解动态规划 5 4 3 2 1 F4(x) x4(x) F3(x) x3(x) F2(x) x2(x) F1(x) x1(x) x 24 40 20 15 5 23 32 15 14 4 22 30 10 13 3 21 10 5 12 2 20 2 0 11 1 0 0 0 0 0 f4(x) f3(x) f2(x) f1(x) x 11 1 12 2 13 3 14 4 15 5 11 0 12 0 16 2 21 3 26 4 11 0 13 1 30 3 41 3 43 4 20 1 31 1 33 1 50 1 61 1回溯算法 z 穷举问题域的所有解，并记录其中权值最 小的解 z 时间代价最高 z 搜索空间Σ，访问每个解的平均时间是t， 总的搜索时间是： z T= |Σ| ×t z 一般是指数级时间代价回溯算法 z 四后问题 要安全的在棋盘放置4个不会 互相攻击的环后棋子回溯算法 z 巡回售货员问题 1 2 3 4 9 5 4 2 7 13 1 234 342423 434232 29 23 28 28 28 29 有一个售货员，从他所在 的城市出发去访问n-1个城 市，要求经过每个城市恰 好一次，然后返回原地问 他的路线怎样安排才最经 济（即线路最短）？贪心法 z 是回溯算法的一个特殊情况 z 在搜索解的过程中，从根结点开始，设当前结 点为A，A的所有子结点中权值最大的为B，则 选择B作为下一个结点 z 可以贪心解的问题需要满足的性质 z 贪心选择性质 z 最优子结构性质 z 时间代价多为线性贪心法 z 部分装入背包问题 一个旅行者准备随身携带一个背包。可以放入 背包的物品有n个，每个物品的重量和价值分 别为wj ，vj ，j=1,2,„,n，旅行者可以选择物品 i的全部，也可以选择i的xi 部分，0≤xi ≤1。如 果背包的重量限制是c，怎么选择放入背包的 物品以使得背包的价值最大？贪心法 z 输入：c>0, wi >0, vi >0, i=1,…, n z 输出： ,..., 2 , 1 1 0 = ≤ ≤贪心法 z 按照单位重量的价值从高到低对物品排 序，尽量装入单位重量价值最高的物品， 直到不能装入一个整物品为止，最后根据 背包重量极限装入部分物品贪心法 z 最小生成树 1 2 3 4 5 6 65 55 1 6 4 3 6 2 对图G=(V, E) 的每一条 边 赋以相应的实数 权 ，得到一个网络， 记为N=(V, E, W)设T=(V, E’)是N的一个生成树， 令，则W(T) 称为树T的权，N中权最 小的生成树称为N的最小 生成树。 E e∈ ) (e ω ∑ ∈ = ' ) ( ) ( E e e T W ω贪心法 z 最小生成树Prim算法贪心法 z 最小生成树Prim算法 1 2 3 4 5 6 65 55 1 6 4 3 6 2 1 2 3 4 5 6 3 1 6 4 4 2 2 5 5 3贪心法 z 最小生成树Kruscal算法贪心法 z 最小生成树Kruskal算法 1 2 3 4 5 6 65 55 1 6 4 3 6 2 1 2 3 4 5 6 1 2 3 4 5 因篇幅问题不能全部显示，请点此查看更多更全内容