第2章 常量.pps
《第2章 常量.pps》由会员分享,可在线阅读,更多相关《第2章 常量.pps(15页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、高等学校计算机专业教材,数据结构袁平波 2007.9,1.1数据结构讨论范畴1.2数据结构相关概念1.2.1基本概念和术语1.2.2数据结构 1.2.3数据类型和抽象数据类型1.3算法及其描述和算法分析,第一章 绪论,1.1数据结构研究什么(1) 要对所加工的对象进行逻辑组织(2) 如何把加工对象存储到计算机中去?(3) 数据运算 数据结构正是讨论非数值类问题的对象描述、信息组织方法及其相应的操作 例、设有一个电话号码薄,有N个人的姓名和电话号码。要求设计一个程序,按人名查找号码,若不存在则给出不存在的信息。,1.2数据结构相关概念1.2.1基本概念和术语 数据元素、结点、数据项、关键字或主关
2、键字、 次关键字、数据对象、数据结构1.2.2数据结构 特性相同的数据元素构成的集合中,如果在数据元素之间存在一种或多种特定的关系,则称之为数据结构 。 Data-Structure=(D,S),例 linear=(D,R) D=1,2,3,4,5,6,7,8,9,10 R=, ,例tree=(D,R)D=a, b, c, d, e, f, g, h, i, j, k, lR=, ,例 graph=(D,R)D=1, 2, 3, 4, 5, 6, 7, 8, 9R=, ,1.2.3数据类型和抽象数据类型ADT=(D,S,P)其中:D是数据对象,用结点的有限集合表示;S是D上的关系的集合,用结点
3、间的序偶的集合来表示;P是对D的基本操作的集合。基本操作的 定义格式为:基本操作名(参数表)初始条件:初始条件描述 操作结果:操作结果描述,操作中的参数有两种 1)赋值参数void add (int a, int b, int * c)*c=a +b; add(2,3,1. 3 算法及其描述和算法分析1、算法:对问题求解的描述,为解决问题给出的一个确定的、有限长的操作序列。1)输入 2)输出 3)有穷性 4)可行性 5)确定性2、算法的描述:类C语言 3、算法效率衡量方法与准则 :时间复杂度:T(n)=O(f(n))空间复杂度:S(n)=O(g(n)),若f(n)是正整数n的一个函数,则xnO(f(n)表示存在一个正的常数M,使得当nn0时都满足|xn|M|f(n)|;换句话就是说这当整型自变量n趋向于无穷大时,两者的比值是一个不等于0的常数。,“O” 的形式定义,分析下列三个程序段: 、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;j1 change = TRUE / bubble_sort 时间复杂度O(n2),常见函数的增长率,
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 常量
限制150内