《算法十二》（个人笔记）

STL：标准模板库
Standard Template Library

	STL概述:
		序列式容器：数据无序
			vector数组
			list双向链表
			deque双向动态队列
		关系式容器：数据有序
			map 
			set
			multimap
			multiset
		
		容器都有的功能：增删改查
		容器都有的函数：
			构造、析构、插入、删除
			查找、拷贝构造、元素个数......
		
		迭代器：返回地址
			迭代器：用来定位容器中某个元素
					数组：下标
					链表：next指针
					容器：智能指针
					
			迭代器返回值：是容器中元素的地址
						  因此每次使用最好初始化begin()
			
			迭代器.begin()：指向第一个元素的地址
			迭代器.end()：指向最后一个元素的后面
			容器.insert(迭代器, 数据)：插入
			如果容器发生改变，迭代器会失效
			
		List：双向动态链表
		
		数组&&链表：数组查找高效
					链表插入删除高效
					数组连续，链表不连续
		
		deque：双向动态队列
			   介于数组和链表之间
	
	排序算法：shell排序/基数排序/桶排序
		shell排序：
			1.优化后的插入排序
			2.按步长step分组：步长一开始设置为元素个数/2
			3.组内插入排序
			4.步长=步长/2
			
		基数排序：
			1.创建临时数组
			2.初始化临时数组
			3.临时数组排序
			4.将临时数组值赋值回原数组
			5.delete临时数组
			限制：1.不能有重复运算
				  2.空间浪费大
			优点：不需要经过比较

		桶排序：基数排序的升级
			1.根据数据范围获取排序次数
			2.制作桶并且初始化
			3.遍历a数组并且按照排序依据将a数组元素存到桶里
			4.放回原来数组里
		总结：希尔排序速度快，不稳定
			  桶排序速度快，稳定，但是空间复杂度高
		
		
		分治：分而治之
		二分查找：折半查找
		归并排序：两个有序数组合并为一个有序数组
		
		归并排序：
			递归的拆分+合并
			合并：
				1.准备临时数组
				2.将数据元素依序放到临时数组中
				3.将数据元素从临时数组拷贝回到原数组中，释放临时数组
				
		二分查找：有序数组按照二分方式来查找数据
			递归方法：int mid = l + (r-l)/2;//中间 
					  if(l==r) return -1;//没有找到的情况,此时l==r 
					  if(finddata==a[mid]) return mid;
					  if(finddata>a[mid]) half_find(a, mid+1, r, finddata);
					  if(finddata<a[mid]) half_find(a, l, mid, finddata);
					  
			非递归方法：int mid;
						int left = l;
						int right = r;
						while(left < right){
							mid = left + (right-left)/2;
							if(finddata == a[mid]) return mid;
							if(finddata > a[mid]){
								left = mid+1;
							}else{
								right = mid;
							}
						}
						return -1;//没有找到的情况,此时left==right 
		
			递归练习之汉诺塔问题：
				if(num<1) return;//num不符合实际的情况 
				han_nuo(num-1, A, C, B);
				printf("%c-->%c \n", A, C);
				han_nuo(num-1, B, A, C);
			
			二分查找与归并排序总结：
				都是分治思想
				二分：每次排除一半
				归并：拆分成为2个，递归的进行拆分直到都成为有序数组
					  然后合并有序数组————>排序成功
				
		
		N叉树：
			一棵树有多个分叉
			森林：多棵树
			节点：树中的元素，子树
			枝干，叶子节点，路径长度
			层：根节点到某些结点的路径长度相同，同一层
			
			N叉树的增删改查
			
		
		有序二叉树：
			二叉树：每个节点有且只有2个孩子
			有序二叉树：左孩子<根<右孩子
			叶子节点：没有孩子的节点
			
		
		
		寻路算法：
		1.深度寻路算法：
			二维地图：二维数组
				二维数组上标识特定数值作为地图上对象	
			
			应用于RGB游戏中比较广泛
			缺点：1.二维地图，只可以走直线
				  2.不一定能找到最佳路径
				  
		
		2.广度寻路算法：
			遍历整个地图中所有可以走的点
			并且将其存入到一颗四叉树里
			之后从起点开始搜索这棵树查找终点即可
		
		小总结：
			深度寻路：
				有回退	循环少   适用于宽阔大地图   不一定能找到最短路径
			广度寻路：
				没有回退  循环多   适用与小地图     一定能找到最短路径
			但是都只能走直线
			
		3.A星寻路：
			结构：N叉树
			直线代价斜线代价：符合勾股定理
			代价：每走一步,距离终点所付出的
			 f = g + h + w;
			 f : 当前点到终点的代价
			 g : 起点到当前点的代价
			 h : 当前点到终点的预估代价（只计算直线距离，并忽略障碍）
			 w : 权重  路：   平地    上坡路  丘陵  沼泽   坑 
			
		
	动态规划：
		使用动态规划：重叠子问题
		最优值，最佳解
		斐波那契数列问题
		
	背包问题：
		当背包重量==0：什么也不能偷
		B(i, j):i代表还有几件商品可以偷
				j代表还剩下的背包空间是多少