哈工大数据结构第1章-绪论 ppt课件.ppt

《哈工大数据结构第1章-绪论 ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构与算法刘扬哈尔滨工业大学计算机学院1课程简介（1/2）课程编号：T050307英文译名：DATASTRUCTUREandALGORITHMS总学时：52/12授课对象：本科生先修课程：高等数学、集合与图论、C程序设计课程要求：必修课课程分类：技术基础授课教师：刘扬答疑地点：？办公电话：86402407课程网站：正在建立2课程简介（2/2）教学目的:(1)学会分析和研究计算机处理的数据对象的特性,掌握常用数据结构内在的逻辑关系、在机内的存储表示,掌握常用数据结构上的运算操作的动态性质和执行

2、算法.(2)能够为实际应用选择适当的数据结构、存储结构和相应算法；(3)初步掌握算法性能的分析方法。考核要求：(1)考试:70%;(2)作业:10%;(3)实验:20%;(4)缺勤:-10%3第一章绪论本章主要包括内容1.1数据结构的研究对象1.2数据结构的发展状况1.3抽象数据型（ADT）1.4逐步求精的程序设计方法1.5算法及其复杂性1.6关于描述语言41.1数据结构的研究对象1.1.1基本概念和术语1.1.2四种基本的数据结构1.1.3数据结构的研究对象51.1.1基本概念和术语一.客观世

3、界与计算机世界的关系计算机科学是研究信息表示和信息处理的科学。信息在计算机内是用数据表示的。用计算机解决实际问题的实质可以用下图表示：61.1.1基本概念和术语二.基本概念和术语1.数据:数据是用于描述客观事物的数值、字符，以及一切可以输入到计算机中的并由计算机程序加以处理的符号的集合。其范围随着计算机技术的发展而不断发展。（图像、音视频等）2.数据元素数据的基本单位是数据元素，在计算机程序中通常作为一个整体进行考虑和处理。3.数据项是数据的不可分割的最小单位，一个数据元素可由若干个数据项组成。

4、4.数据对象性质相同的元素的集合叫做数据对象。71.1.1基本概念和术语二.基本概念和术语5.结点数据元素在机内的位串表示，即数据元素在计算机内的映象。6.域/字段当数据元素由若干个数据项组成时，位串中对应于各个数据项的子串称为域/字段，是数据元素中数据项在计算机中的映象。7.信息表计算机程序所作用的一组数据通常称为信息表，是数据对象在计算机中的映象。81.1.1基本概念和术语二.基本概念和术语8.数据结构数据结构指的是数据元素之间的相互关系，这种关系是抽象的，即并不涉及数据元素的具体内容。是数

5、据元素及其相互间的关系的数学描述。9.逻辑结构和存储结构(1)逻辑结构数据结构中描述的是数据元素之间的抽象关系(逻辑关系)，称为逻辑结构。(2)存储结构/物理结构数据结构在计算机中的表示（映象）称为存储结构/物理结构。91.1.1基本概念和术语二.基本概念和术语数据元素之间的（逻辑结构）关系在计算机中有两种表示方法：顺序映象(表示)和非顺序映象(表示)，从而导致两种不同的存储结构：顺序结构和链式结构。顺序映象（表示）的特点是借助数据元素在存储器中的相对位置来表示数据元素之间的逻辑关系。非顺序映象

6、（表示）的特点是借助指示数据元素存储地址的指针来表示数据元素之间的逻辑关系。101.1.2四种基本的逻辑结构1.集合结构结构中的数据元素之间除了<属于同一个集合>的关系之外，别无其它关系。关系比较松散，可用其它结构来表示。2.线性结构结构中的数据元素之间存在一个对一个的关系，即线性关系，每个元素至多有一个直接前导和后继。111.1.2四种基本的逻辑结构3.树形结构结构中的数据元素之间存在一个对多个的关系，即层次关系，即每一层上的元素可能与下层的多个元素相关，而至多与上层的一个元素相关。4.网状/

7、图形结构结构中的数据元素之间存在多个对多个的关系，即任意关系，任何元素之间都可能有关系。一般将逻辑结构分为线性结构（2）和非线性结构（1，2，3）两种。121.1.3数据结构的研究对象（内容）1.数据对象的结构形式,各种数据结构的性质(逻辑结构);2.数据对象和“关系”在计算机中的表示(物理结构/存储结构);3.数据结构上定义的基本操作(算法);4.算法的效率;5.数据结构的应用,如数据分类,检索.131.2数据结构的发展状况和作用1.程序设计方法学的发展极大地促进了数据结构的发展(1)计算机科

8、学及其应用的发展使数据结构成为独立学科.(2)以数据为中心的程序设计方法推动了数据结构的发展.（a）面向过程的程序设计的特点是以程序为中心，侧重于建立程序，程序在简单的数据结构上进行复杂的运算，软件设计的主要工作就是设计求解问题的过程。注重于程序设计技巧，适合于数值计算。（例如FORTRAN语言）（b）结构化特别是面向对象的程序设计以数据(结构)为中心，系统采用复杂的数据结构来描述系统状态，程序围绕数据结构进行加工。这种编程语言更适合于非数值计算。2.数据结构的地位(1)是计算机科学的一门专业基