经典数据结构与算法.docx
- 文档编号:8761707
- 上传时间:2023-05-14
- 格式:DOCX
- 页数:19
- 大小:20.39KB
经典数据结构与算法.docx
《经典数据结构与算法.docx》由会员分享,可在线阅读,更多相关《经典数据结构与算法.docx(19页珍藏版)》请在冰点文库上搜索。
经典数据结构与算法
经典数据结构与算法
张华
2005.9.4Template(模版)
z模板使我们可以用一个代码段指定一组相关函
数(称为模板函数)或一组相关类(称为模板
类)
z模板是C++的软件复用的功能之一函数模版
intmin(inta,intb){
returna
a:
b;
}
doublemin(doublea,doubleb){
returna
a:
b;
}
替代这种“为每个min()实例都显示定义一个函
数”的方法
Template
Typemin(Typea,Typeb){
returna
a:
b;
}类模版
z类模板的用途很多,最常用的是提供具备高度
适应性的存储容器。
ztemplate
classpair
{
public:
T1first;
T2second;
pair(T1x,T2y):
first(x),second(y){}
};STL组件关系
容器类迭代器算法
vectorsort
用迭代器连接容器和算法STL程序示例
#include
#include
#include
#include
usingnamespacestd;
intmain()
{
intia[6]={27,210,12,47,109,83};
vector
cout< not1(bind2nd(less_equal return0; } //result: 4 83109471221027 vec.begin()vec.end()STL中的容器 顺序容器 SequenceContainers 关联容器 AssociativeContainers 容器Containers vectordequelist set,multiset map,multimapSTL中的容器 容器适配器 stackqueuepriority _queue算法举例简介 STL中用到了各种算法: 排序、查询、排 列组合、数据搬移与复制等 z分治算法 z动态规划 z回溯算法 z贪心算法参考书目 z标准模板库自修教程与参考手册—STL进行 C++编程,D.R.Musser,G.J.Derge,A.Saini. zC++大学教程,H.M.Deitel,P.J.Deitel. zC++语言的设计和演化,BjarneStroustrup. zSTL源码剖析,候捷.//SGISTL z设计模式: 可复用面向对象软件的基础, ErichGamma等.练习题 z法雷序列(FareySeries) 对任意给定的一个自然数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 zmod: (x^2+2*x+2)%(x+1)=1 z存储采用链表。 注意要考虑特殊情况下的处理。 测试程序的界面可以自由发挥。 作业 1.多项式的系数为实数。 2.求mod的时候一定要注意结果多项式的次数 要小于除式多项式的次数。 3.多项式为一元的。 也就是只包括一个未知数 x。 4.加减乘除是多项式的。 而不是多项式带入x后 的值进行加减乘除。 vector 1.实际上就是个动态数组。 2.随机存取任何元素都能在常数时间完成。 3.在尾端增删元素具有较佳的性能。 STL是如何实现vector的呢vector vector vector : iteratori; 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 while(vector1.size()>0) { vector1.pop_back();//在末尾删除 } j=find(vector1.begin(),vector1.end(),’m’); vector1.erase(j--);//指定位置删除vector zvector中的元素被C++标准限定为存储在连续 内存中,就像是一个数组 54871 [0][1][2][3][4]elementmax_size-1 size=5 1.对vector的随机访问效率很高 因为每次访问离vector起始处的位移都是固定的 2.在任意位置,而不是在vector末尾插入(删除) 元素,效率很低 因为需要把待插入元素右边的每个元素都拷贝一 遍 3.预留足够的空间很重要 如果旧空间不足,会重新配置一块更大的空间, 然后复制元素,再释放旧空间vector vector voiddoSomething (constint*pInts,size_tnumInts); 我们可以这样做 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不支持随机存取。 N1234 LeftEndRightEnd 1.任意位置插入和删除元素的效率都很高 指针必须被重新赋值,但是,不需要用拷贝元素 来实现移动 2.对随机访问的支持不好 访问一个元素需要遍历中间的元素 3.每个元素还有两个指针的额外空间开销关联容器 zset/multiset set即集合。 set中不允许相同元素,multiset 中允许存在相同的元素。 zmap/multimap map与set的不同在于map中存放的是成对的 key/value。 并根据key对元素进行排序,可快 速地根据key来检索元素。 关联容器 关联容器绝大部分的实现是使用的红黑 树——平衡树的一种关联容器 z平衡树vs.非平衡树 1 23 45 1 23 4 5平衡树非平衡树stack z是项的有限序列。 z并满足序列中被删除、检索和修改的项只能是 最近插入序列的顶。 z即按照先进后出的原则 top PUSHtopPOPstack zstack既可以通过线性表实现,又可以通过链 表实现 栈顶 54871 [0][1][2][3][4]elementmax_size-1 size=5 N1234 LeftEndRightEnd 栈顶stack stack 实现 stack vector实现 stack stack deque实现queue z插入只可以在尾部进行。 z删除、检索和修改只允许从头部进行。 z按照先进先出的原则。 [0][1][2][3][4] 排队买汉堡queue z我们可以通过线性表实现queue ABCD frontrear 插入 rear 删除 front 队列的平移 BCD rearfront 效率queue queue deque实现 queue 现 queue deque实现 和栈适配器的不同? 没有vector的形式queue zqueue适配器不能用于vector容器,因为 vector没有pop_front操作。 z为什么vector不把pop_front操作包含到它的 接口中? z因为这种操作对于大的向量效率非常低。 zSTL尽量避免低效的使用方式分治算法 z分治策略的实例——二分搜索、归并排序 25139874 排序 251398742513987425139874 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 kkkk xx kxxFxfxF k −+=− ≤≤ )()(11xfxF= •递推公式采用自底向上的 方式,用更小的局部最优 解来表示更高层次的局部 最优解,反复递推最终达 到全局最优解动态规划 5 4 3 2 1 F4(x) x4(x) F3(x) x3(x) F2(x) x2(x) F1(x) x1(x) x 244020155 233215144 223010133 21105122 2020111 00000 f4(x)f3(x)f2(x)f1(x)x 111 122 133 144 155 110 120 162 213 264 110 131 303 413 434 201 311 331 501 611回溯算法 z穷举问题域的所有解,并记录其中权值最 小的解 z时间代价最高 z搜索空间Σ,访问每个解的平均时间是t, 总的搜索时间是: zT=|Σ|×t z一般是指数级时间代价回溯算法 z四后问题 要安全的在棋盘放置4个不会 互相攻击的环后棋子回溯算法 z巡回售货员问题 12 3 4 9 5 4 2 7 13 1 234 342423 434232 292328282829 有一个售货员,从他所在 的城市出发去访问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输出: ∑= n i ii xv 1 max ∑= ≤ n i ii cxw 1 nixi ...,2,110=≤≤贪心法 z按照单位重量的价值从高到低对物品排 序,尽量装入单位重量价值最高的物品, 直到不能装入一个整物品为止,最后根据 背包重量极限装入部分物品贪心法 z最小生成树 1 2 34 56 65 55 1 643 6 2 对图G=(V,E)的每一条 边赋以相应的实数 权,得到一个网络, 记为N=(V,E,W)设T=(V, E’)是N的一个生成树, 令,则W(T) 称为树T的权,N中权最 小的生成树称为N的最小 生成树。 Ee∈ )(eω ∑∈ = ' )()( Ee eTWω贪心法 z最小生成树Prim算法贪心法 z最小生成树Prim算法 1 2 34 56 65 55 1 643 6 2 1 2 34 56 3 1 6 4 4 2 25 5 3贪心法 z最小生成树Kruscal算法贪心法 z最小生成树Kruskal算法 1 2 34 56 65 55 1 643 6 2 1 2 34 56 1 234 5
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 经典 数据结构 算法