数据结构——C语言描述第1章-绪论.pptx
《数据结构——C语言描述第1章-绪论.pptx》由会员分享,可在线阅读,更多相关《数据结构——C语言描述第1章-绪论.pptx(21页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、数据结构C语言描述(慕课版)第1章 绪论编著:张同珍&学校:上海交通大学绪论数据结构定义基本操作存储结构逻辑结构算法算法的时空复杂度数据结构:数据是外界信息进入计算机,并被计算机处理的符号,数据元素是数据的基本单位。如有一组学生信息,每个学生信息是一个结构类型数据,包含了学号、姓名、年龄等字段,那么这组学生信息是数据,每一个学生信息是数据元素。数据结构:是指相互之间具有一定关系的相同类型的数据元素的集合。数据结构的研究对象:1.元素之间的关系(逻辑结构)2.元素关系操作3.元素和关系在内存中的存储(物理结构)4.在各种存储方式下关系操作的实现5.每种数据结构的典型应用研究数据的逻辑结构就是研究
2、类型相同的一组元素和元素间的关系。数据的逻辑结构集合关系:元素间呈松散关系,结构中不同元素除了同属于一个集合,相互间并无其他制约关系。如同班级里同学间的关系。线性关系:元素间呈现出你先我后的顺序,是一种一对一的关系。如队列中元素间的关系。除了队首,每个元素有且只有一个唯一的直接前驱元素;除了队尾,每个元素有且只有一个唯一的直接后继元素。树形关系:元素间呈现出一对多的关系。如家谱中人物间关系,一个人可以有多个儿子,却只能有一个父亲。即每个元素可以有多个后继,却只能有一个前驱。图关系:元素间呈现多对多的关系。如城市间通过飞机航线形成的关系,例如上海、北京、西安3个城市中,任何两个城市间都可以有直飞
3、航线。分以下几种:数据的逻辑结构:逻辑结构通常可以用二元组描述:Data_Struct=(D,R),其中D是元素的集合,R是关系的集合。例如整数110组成的有序集就是一个线性结构。D=|1 10,R=1,2 1,2。其中 1,2表示一个有序偶,即x1和x2有顺序关系,x1是直接前驱,x2是直接后继。关系操作(或称基本操作)是和数据的逻辑结构紧密相关的,它来源于关系自身的特点。构造类:在内存中建立这种数据结构。如一个空的队列。基本操作都可以分为五大类:构造类、属性类、数据操纵类、遍历类、典型应用类。属性类:对元素及元素之间的关系的各类查询。属于东瞧瞧、西看看,不影响元素及元素关系本身。数据操纵类
4、:对元素或元素关系有改变的操作,如插入或删除某个元素。修改可视作删除后插入。遍历类:对结构中的每个元素访问且只访问一遍。典型应用类:所属结构独特的应用,不同结构其典型应用各不相同。数据的逻辑结构+基本操作=抽象数据类型ADT(Abstract Data Type)。ADT和在计算机内的表示、实现无关,只和数据自身的逻辑特征相关。ADT类似高级语言中的数据类型,如整型:一个整数集合以及在这个集合中系统支持的基本操作(四则运算、比较运算等)。ADT区别于具体某种类型,只关心元素关系和关系操作,不实际要求数据的具体类型,只要元素类型一致。ADT的描述可以用自然语言也可以用伪代码,其内容包含元素集合、
5、元素关系集合、基本操作。基本操作表明生活中的一个个基本的问题,有明确的已知条件和结果要求。基本操作的具体实现依赖于数据和数据关系在内存中如何存储,在逻辑结构分析阶段并不知道存储方式,因此无法给出,也不需要考虑。顺序存储是用一块连续的空间来存储数据,同时借助这组空间在地址上的邻接及有序性来存储元素之间的关系,顺序存储的结构称顺序结构。高级语言中的数组可以实现连续空间的获取,帮助实现顺序结构。链式存储是在内存中使用多个独立的内存空间,每个独立的空间除了包括存储元素的空间,还包括附加的空间来存储元素之间的关系。链式存储的数据结构称链式结构。存储结构:也称物理结构,是指数据结构在内存中的表示。常见的存
6、储方式有顺序存储和链式存储两种。算法及其要求这里算法是指用计算机解决一个具体问题的方法和步骤。算法必须满足五个特性:一个算法中的每一步要在有限的时间内完成,而整个算法必须在有限步之后完成。有穷性:算法中的每一步都有确定的含义,没有二义性。确定性:算法中的每一步都是经过有限次基本操作就可以完成的,每一步自身没有复杂的算法问题。可行性:根据问题需要,一个算法可以有零个或者若干个输入作为解决问题的已知条件。有输入:算法执行结束后,有零个或者若干个输出作为算法运行结果。有输出:算法及其要求度量算法优劣的几个要素:准确反映并能满足具体问题的要求,即对于任意一个合法的输入,都能给出正确的结果。正确性:可供
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 语言 描述 绪论
限制150内