《数据结构》课件1第1章 绪论.pptx
《《数据结构》课件1第1章 绪论.pptx》由会员分享,可在线阅读,更多相关《《数据结构》课件1第1章 绪论.pptx(17页珍藏版)》请在文库网上搜索。
1、第1章 绪论数据结构的研究内容数据结构的基本概念抽象数据类型及其实现算法和算法分析1.1 数据结构的研究内容2对于数值计算问题的求解,一般经过以下几个步骤:首先从具体问题抽象出数学模型,然后设计一个求解此数学模型的算法,最后编写程序,并进行测试、调试,直到解决问题。在此过程中寻求数学模型的实质是分析问题,从中提取操作的对象,并找出这些操作对象之间的关系,然后用数学语言加以描述,即建立相应的数学方程。例如,预测人口增长情况的数学模型为常微分方程,求解数学方程的方法是计算数学研究的范畴。数据结构主要研究非数值计算问题,非数值计算问题无法用数学方程建立数学模型。非数值计算问题的数学模型不再是数学方程
2、,而是线性表、树、图等数据结构。因此,简单地说,数据结构的研究范畴主要是非数值计算问题的操作对象和它们之间的关系以及在计算机中的表示和实现。1.2 数据结构的基本概念数据数据是客观事物的符号表示,是所有能输入到计算机中并能被计算机处理的符号的总称。数据可以指数值型数据,如整数、实数、复数等;也可以是非数值型数据,如文字、图形、图像、声音、动画等。数据元素数据元素是数据的基本单位,在计算机中通常作为一个整体进行处理。在有些情况下,数据元素也称为元素、记录、结点、顶点等。数据元素用于完整地描述一个对象,例如,学生基本信息表中每个学生记录是一个数据元素。数据项数据项是组成数据元素的、有独立含义的、不
3、可分割的最小单位,是对数据元素属性的描述。例如,学生基本信息表中,每个数据元素(即学生记录)是由学号、姓名、性别、出生日期、籍贯和专业等数据项组成的数据对象数据对象是具有相同性质的数据元素的集合,是数据的一个子集。例如,整数数据对象是集合N=0,1,2,字母字符数据对象是集合C=A,B,Z,a,b,z,学生基本信息表也是一个数据对象。1.数据、数据元素、数据项和数据对象31.2 数据结构的基本概念数据结构(Data Structure)是相互之间存在着一定关系的数据元素的集合。换句话说,数据结构是带结构的数据元素的集合,结构就是指数据元素之间存在的关系。数据结构包括逻辑结构和存储结构两个层次。
4、2.数据结构4逻辑结构存储结构1.2 数据结构的基本概念n逻辑结构2.数据结构5数据的逻辑结构是指数据元素以及数据元素之间的逻辑关系,是从实际问题抽象出的数据模型,形式上可定义为一个二元组:DataStructure(D,R)其中D是一个数据元素的有限集合,R是定义在D中的数据元素之间的关系的集合。根据数据元素之间逻辑关系的不同,通常有四类基本结构:(1)集合结构:数据元素之间就是“属于同一个集合”,除此之外,没有任何关系。(2)线性结构:数据元素之间存在一对一的关系。(3)树结构:数据元素之间存在一对多的关系。(4)图结构:数据元素之间存在多对多的关系。树结构和图结构也称为非线性结构。1.2
5、 数据结构的基本概念n存储结构2.数据结构6数据的存储结构又称为物理结构,是数据对象在计算机中的存储表示。把数据对象存储到计算机时,除了存储数据元素之外,还必须隐式或显式地存储数据元素之间的逻辑关系。通常有两种存储结构:顺序存储结构和链式存储结构。顺序存储结构使用一组连续的存储单元依次存储数据元素,元素之间的逻辑关系由元素在存储器中的相对位置来表示。链式存储结构是用一组任意的存储单元存储数据元素,数据元素之间的逻辑关系用指针来表示。1.3 抽象数据类型71.数据类型数据类型是一组性质相同的值的集合以及定义在此集合上的一组操作的总称,是程序设计语言中已实现的数据结构。在程序设计语言中,每一个数据
6、都属于某种数据类型。类型显式或隐式地规定了数据的取值范围、存储方式以及允许进行的运算。2.抽象数据类型抽象数据类型一般指由用户定义的、表示应用问题的数学模型,以及定义在这个模型上的一组操作的总称。一个具体问题的抽象数据类型的定义通常采用简洁、严谨的文字描述,一般包括数据对象、数据关系和基本操作三方面的内容,描述格式如下:ADT 抽象数据类型名数据对象:数据对象的声明数据关系:数据关系的声明基本操作:基本操作的声明1.3 抽象数据类型n类的定义3.C+的类和对象8类的定义格式一般分为两大部分:声明部分和实现两部分,声明部分用来声明该类中的成员,包括数据成员和成员函数(方法或操作)。实现部分用来给
7、出说明部分中所说明的成员函数的实现和定义。class private:私有数据成员和成员函数;public:公有数据成员和成员函数;protected:保护数据成员和成员函数;C+中用关键字class来声明类,格式如下:类的成员函数是类的行为,是程序算法的具体实现。成员函数必须在类体内进行原型说明,一般情况下,不写出函数体,它们的实现写在类外。在类外定义成员函数的格式为:函数类型类名:成员函数名(参数表)函数体;【例例1.4】Complex类的定的定义n对象的定义类名对象名;或类名对象名(实参表);【例例1.5】使用使用Complex类实现复数的加减运算复数的加减运算1.3 抽象数据类型C+提
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 数据结构课件1第1章 绪论 课件