012-算法模式讲解.ppt

合肥工业大学 计算机与信息学院 * 数 据 结 构 （第十二章 算法模式和STL） Data Structures 张晶 计算机与信息学院 * * 第12章 算法模式 分治算法（自顶向下求解策略） 动态规划法（自底向上求解策略） 蛮干算法和贪心算法（直接求解策略） 简单回溯算法和分支界限算法（回溯策略） 蒙特卡罗算法和模拟退火法（随机化策略） …… 经典问题 n阶楼梯，每次上一层或两层，问共有几种走法。 #include stdio.hlong step(int n){ if (n==1) return(1); if (n==2) return(2); if ( n2 ) return(step(n-1)+step(n-2));} void main(){ int n; long sum; long step(int); scanf(%d,n); sum=step(n); printf(%ld\n,sum);} * STL * STL 在C++标准中，STL被组织为下面的13个头文件： algorithm deque functional iterator vector list map memory numeric queue set stack utility STL可分为 容器(containers) 迭代器(iterators) 空间配置器(allocator) 配接器(adaptors) 算法(algorithms) 仿函数(functors) 六个部分 * STL——容器 容器部分主要由头文件vector,list,deque,set,map,stack和queue组成 向量(vector) 连续存储的元素vector 列表(list) 由节点组成的双向链表，每个结点包含着一个元素list 双队列(deque) 连续存储的指向不同元素的指针所组成的数组deque 集合(set) 由节点组成的红黑树，每个节点都包含着一个元素，节点之间以某种作用于元素对的谓词排列，没有两个不同的元素能够拥有相同的次序 set 多重集合(multiset) 允许存在两个次序相等的元素的集合 set 映射(map) 由{键，值}对组成的集合，以某种作用于键对上的谓词排列 map 多重映射(multimap) 允许键对有相等的次序的映射 map 栈(stack) 后进先出的值的排列 stack 队列(queue) 先进先出的执的排列 queue 优先队列(priority_queue) 元素的次序是由作用于所存储的值对上的某种谓词决定的的一种队列 queue * 顺序容器 关联容器 容器适配器 STL——迭代器 迭代器在STL中用来将算法和容器联系起来，起着一种黏和剂的作用。几乎STL提供的所有算法都是通过迭代器存取元素序列进行工作的，每一个容器都定义了其本身所专有的迭代器，用以存取容器中的元素。 迭代器部分主要由头文件utility,iterator和memory组成。 utility是一个很小的头文件，它包括了贯穿使用在STL中的几个模板的声明 iterator中提供了迭代器使用的许多方法 memory的描述则十分的困难，它以不同寻常的方式为容器中的元素分配存储空间，同时也为某些算法执行期间产生的临时对象提供机制,memory中的主要部分是模板类allocator，它负责产生所有容器中的默认分配器。 * STL——迭代器 迭代器(Iterator)是指针(pointer)的泛化，它允许程序员以相同的方式处理不同的数据结构(容器)。STL 中有5 中类型的迭代器，它们分别满足一定的要求。不同的迭代器要求定义的操作不一样。 * STL——算法 * * 合肥工业大学 计算机与信息学院 *