PDF《第2章算法》

? 第2章算法 启示算法: 算法是解决特定问题求解步骤的描述,在计算机中表现为指令的有限序列,并且 每条指令表示一个或多个操作.

? ? ? ? ? 数据结构 大话 2.1 开场白各位同学大家好.? 上次上完课后,有同学对我说,老师,我听了你的课,感觉数据结构没什么的, 你也太夸大它的难度了.? 是呀,我好像是强调了数据结构比较搞脑子,而上次课,其实还没拿出复杂的东 西来说道.不是不想,是没必要,第一次课就把你们糊弄晕,那以后还玩什么,逃课 的不就更多了吗?你们看,今天来的人数和第一次差不多,而且暂时还没有睡觉的.? 今天我们介绍的内容在难度上就有所增加了,做好准备了吗?? 2.2 数据结构与算法关系 我们这门课程叫数据结构,但很多时候我们会讲到算法,以及它们之间的关系. 市场上也有不少书叫 数据结构与算法分析 这样的名字.? 有人可能就要问了,那你到底是只讲数据结构呢,还是和算法一起讲?它们之间 是什么关系呢?干吗要放在一起?? 这问题怎么回答.打个比方吧,今天是你女友生日,你打算请女友去看爱情音乐 剧,到了戏院,抬头一看――《梁山伯》18:00 开演.嗯,怎么会是这样?一问才 知,今天饰演祝英台的演员生病,所以梁山伯唱独角戏.真是搞笑了,这还有什么看 头.于是你们打算去看爱情电影.到了电影院,一看海报――《罗密欧》 ,是不是名字 写错了,问了才知,原来饰演朱丽叶的演员因为嫌弃演出费用太低,中途退演了.制 片方考虑到已经开拍,于是就把电影名字定为《罗密欧》 ,主要讲男主角的心路旅程. 哎,这电影还怎么看啊?? 事实上,数据结构和算法也是类似的关系.只谈数据结构,当然是可以,我们可 以在很短的时间就把几种重要的数据结构介绍完.听完后,很可能你没什么感觉,不 知道这些数据结构有何用处.但如果我们再把相应的算法也拿来讲一讲,你就会发 现,甚至开始感慨:哦,计算机界的前辈们,的确是一些很牛很牛的人,他们使得很 多看似很难解决或者没法解决的问题,变得如此美妙和神奇.? 也许从这以后,慢慢地你们中的一部分会开始把你们的崇拜对象,从帅哥美女、 18? 第2章算法 什么 哥 什么 姐 们,转移到这些大胡子或者秃顶的老头身上,那我就非常欣慰 了.而且,这显然是一种成熟的表现,我期待你们中多一点这样的人,这样我们国家 的软件行业,也许就有得救了.? 不过话说回来,现在好多大学里,通常都是把 算法 分出一门课单独讲的,也 就是说,在《数据结构》课程中,就算谈到算法,也是为了帮助理解好数据结构,并 不会详细谈及算法的方方面面.我们的课程也是按这样的原则来展开的.? 2.3 两种算法的比较 大家都已经学过一门计算机语言,不管学的是哪一种,学得好不好,好歹是可以 写点小程序了.现在我要求你写一个求 1+2+3+……+100 结果的程序,你应该怎么写 呢?? 大多数人会马上写出下面的 C 语言代码(或者其他语言的代码) :? int i, sum = 0, n = 100;

for(i = 1;

i <

= n;

i++) { sum = sum + i;

} printf( %d , sum);

这是最简单的计算机程序之一,它就是一种算法,我不去解释这代码的含义了. 问题在于,你的第一直觉是这样写的,但这样是不是真的很好?是不是最高效?? 此时,我不得不把伟大数学家高斯的童年故事拿来说一遍,也许你们都早已经听 过,但不妨再感受一下,天才当年是如何展现天分和才华的.? 据说