经典数据结构与算法.docx

经典数据结构与算法.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>vec（ia,ia+6）;

cout<

not1（bind2nd（less_equal（）,40）））;

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

vectorv1,v2;

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

vectorvector1;

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

vectorv;

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是类型为T的栈，默认情况下以deque

实现

stack>是类型为T的栈，以

vector实现

stack>是类型为T的栈，以list实现

stack>是类型为T的栈，以

deque实现queue

z插入只可以在尾部进行。

z删除、检索和修改只允许从头部进行。

z按照先进先出的原则。

[0][1][2][3][4]

排队买汉堡queue

z我们可以通过线性表实现queue

ABCD

frontrear

插入

rear

删除

front

队列的平移

BCD

rearfront

效率queue

queue是类型为T的队列，默认情况下以

deque实现

queue>是类型为T的队列，以list实

现

queue>是类型为T的队列，以

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