《数据结构 教学课件 ppt 作者 晋良颖 1》由会员分享，可在线阅读，更多相关《数据结构 教学课件 ppt 作者 晋良颖 1（16页珍藏版）》请在金锄头文库上搜索。
1、高等学校计算机专业教材,数据结构,第一章 绪论 1.1数据结构研究什么 1.2数据结构的发展概况和在计算机科学中的地位 1.3基本概念和术语 1.4数据类型和抽象数据类型 1.5算法和算法分析,退出,1.1数据结构研究什么 (1)、要对所加工的对象进行逻辑组织。 (2)、如何把加工对象存储到计算机中去？ (3)、数据运算。 例1、设有一个电话号码薄，有N个人的姓名和电话号码。要求设计一个程序，按人名查找号码，若不存在则给出不存在的信息。,图1-1,1.2数据结构的发展概况和在计算机科学中的地位 1.3基本概念和术语 数据元素、结点、数据项、关键字或主关键字、 次关键字、数据对象、数据结构 Da
2、ta-Structure=(D,S) 例2 linear=(D,R) D=1,2,3,4,5,6,7,8,9,10 R=, ,图1-2,例3tree=（D,R） D=a,b,c,d,e,f,g,h,i,j,k,l R=, ,图1-3,例4graph=(D,R) D=1,2,3,4,5,6,7,8,9 R=,图1-4,1.4数据类型和抽象数据类型 ADT=（D，S，P） 其中：D是数据对象，用结点的有限集合表示； S是D上的关系的集合，用结点间的序偶的集合来表示； P是对D的基本操作的集合。基本操作的 定义格式为： 基本操作名（参数表） 初始条件：初始条件描述 操作结果：操作结果描述,1. 5算
3、法和算法分析 1、算法 1）、输入、2）、输出、3）、有穷性、4）、可行性、5）、确定性 2、算法设计的要求 1）、正确性、2）、可读性、3）、健壮性、4）、高效性 3、算法的时间复杂度 T（n）=O（f(n)）,例5 直接选择排序 算法 11 如书第9页所示,分析下列三个程序段： 、x+;s=0; O（1） 、for (i=1;i=n;i+) x+;s+=x; O（n） 、for( i=1;i=n;i+) for (j=1;j=n; j+) x+; s+=x; O（n2） T(n)=2n3+5n2+7n+c;（c为某一常数），则 T（n）=O（n3）。,图1-5 常见函数的增长率,4、算法的空间复杂度（Space Complexity） S(n)=O(f(n),
