数据结构全部课件.pptVIP

ONLY FOUR POINTS Enjoy Studying Be Honest to Yourself Attitude is Everything Harmonious Class 算法A的程序代码如下： For x = 1 To 100 For y = 1 To 100 For z = 1 To 100 If (x+y+z=100) And (5* x + 3 * y + z/3 = 100) Then List1.AddItem Str(x) + + Str(y) + + Str(z) End If 算法B程序代码如下： For x = 1 To 20 For y = 1 To 33 Z=100-x-y If 5* x +3* y + z/3 = 100 Then List1.AddItem Str(x) + + Str(y) + + Str(z) End If How to read？How to comprehend？ 世界上如果男人没有了女人怎么办？ 算法的确定性（无二义性） 4 算法及算法分析 定义1-1 若存在两个正的常数c和n0，对于任意n≥n0，都有Ｔ（n）≤c×f (n)，则称Ｔ(n)=O(f(n)) （或称算法在O(f(n))中）。 最好、最坏和平均情况 （例） 4 算法及算法分析 3 算法分析举例 定理1-1 若A(n)=amnm+am-1nm-1+?+a1n+a0是一个m次多项式，则A（n）=O（nm）。 说明：在计算算法时间复杂度时，可以忽略所有低次幂和最高次幂的系数。 例1-5—1-9 4 算法及算法分析 例：在一维整型数组A[n]中顺序查找与给定值k相等的元素（假设该数组中有且仅有一个元素值为k），顺序查找算法如下： int Find(int A[ ], int n) { for (i=0; in; i++) if (A[i]= =k) break; return i; } Knuth介绍 1938.01.10 诞生。1956 进入凯思工学院学习物理。 1960 毕业后进入加州理工学院研究所，转向数学领域。 1963 拿到 Ph.D.，并留校任教。 1968 开始任教于 Stanford 大学,同年开始撰写名闻遐迩的 TAOCP。有人曾说，看了这部书，往后对写程序的话题都会变得谦虚。 1974年荣获图灵奖。 1977 自行开发 TeX 排版系统。 1986 荣获 ACM 软件系统奖。 A person does not really understand something until after teaching it to a computer . 无结构阶段 结构化阶段 面向对象阶段 应用领域：科学计算；程序设计面向计算机 应用领域：科学计算与非数值处理； 算法＋数据结构=程序 应用领域：更多地应用于非数值处理； （算法＋数据结构）=程序 数据结构的发展历程 N.Wirth介绍 世界闻名的计算机科学家。苏黎世联邦理工学院教授，1970年发明了Pascal语言及其它几种计算机语言而著名。提出计算机界非常有名的“数据结构十算法= 程序”著名公式，提出“结构化程序设计”这一概念，为新软件技术“结构化编程”的开发做出了贡献。开发了世界最早的个人计算机之一，名为“Lilith”(1978-80)。获奖情况：1983年，获 电气和电子工程师协会（IEEE）Emanuel Piore 奖；1984年，获图灵奖；1987年，获美国计算机学会（ACM）计算机科学教育杰出贡献奖；1989年，获IBM欧洲杰出科学技术奖。 本章总结 绪 论 数据结构 算 法 基本概念 逻辑结构 存储结构 ⑴数据 ⑵数据元素 ⑶数据对象 ⑷ADT ⑴逻辑结构 ⑵数据结构 的分类 ⑴存储结构 ⑵常用存储 方法 基本概念 算法分析 ⑴算法 ⑵算法特性 ⑶评价算法 ⑷描述算法 ⑴问题规模 ⑵基本语句 ⑶时间复杂度 ⑷大O记号 关 系 小结 第一次作业： 公元5世纪末，我国古代数学家张丘建在它所撰定的《算经》中，提出