数据结构第一章绪论(1)PPT教学课件

2020/12/10
7
二、 数据结构（ Data Structure ）
★ 数据结构是相互之间存在一种或多种特定关系的 数据元素的集合
◆ 数据结构＝数据＋结构（关系）
2020/12/10
8
数据结构的描述方式
1、逻辑结构
★ 是对数据元素之间逻辑关系（抛开具体的关系 含义以及存储方式等）的描述
◆ 它可以用一个数据元素的集合和定义在此集合 上的几个关系来表示
第一章 绪论
第一节 什么是数据结构 ★ 数据结构（Data Structure）
2020/12/10
1
什么是数据结构
★ 数据结构作为一门独立的课程在国外是从1968年 才开始设立的
◆ 当时，数据结构几乎和图论，特别是和表、树的 理论成为同义语
2020/12/10
2
什么是数据结构
◆ 但对于数据结构的概念，至今尚未有一个被一致 公认的定义
2020/12/10
9
★ 数据结构通常可用图形表示 圆圈表示数据元素，箭头表示关系
数据元素
数据元素
Ei
关系
E i+1
数据结构的描述方式
2、物理结构（存储结构）
★ 数据结构在计算机中的具体表示（representation） 和实现 （implementation）
2020/12/10
11
数据结构的分类 1、按逻辑结构分类 ★ 集合、线性结构、树型结构、图状结构 2、按物理结构分类 ★ 顺序存储结构、链式存储结构、索引存储结构
2020/12/10
12
数据结构的概念
★ 数据结构的形式定义为
◆ 数据结构是一个二元组 Data_Structure=（D，S）
◆ 其中：D是数据元素的有限集， S是D上关系的有限集
2020/12/10
13
典例1： linear=（D，R） D={1，2，3，4，5，6，7，8，9，10} R={<1，2>，<2，3>，<3，4>，<4，5>，<5，6>，
★ 数据结构是介于数学、计算机硬件和计算机软件 三者之间的一门核心课程
2020/12/10
3
第二节 基本概念和术语 一、 基本概念和术语 1、 数据（data） ★ 所有能输入到计算机中并被计算机程序处理的
符号的总称（如数值、文字、声音、图像等）
2020/12/10
4
学生成绩表
学号
姓名 张卓 刘忠赏 胡孝臣
★ Knowing the representation of the objects of a data type can be useful and dangerous. knowing the representation we can often write algorithms （算法）that make use of it.
<2，8>，<3，2>，<3，4>，<4，5>，<5，7>， <6，7>，<6，9>，<7，9>，<8，9>}
三、 数据类型（Data Type） ★ 数据类型的定义
◆ A data type is a collection of objects and a set of operations that act on those objects
◆ However，if we want to change the representation of the objects， we also must change the routines that make use of it.
2020/12/10
21
四、 抽象数据类型（ Abstract Data Type，ADT ）
<6，7>， <7，8>，<8，9>，<9，10>}
典例2： tree=（D，R） D={a，b，c，d，e，f，g，h，i，j，k，l} R={<a，b>，<a，c>，<a，d>，<b，e>，<b，f>，<b，
g>，<c，h>，<c，i>，<c，j>，<d，k>，<d，l>}
典例3： graph=（D，R） D={1，2，3，4，5，6，7，8，9} R={<1，2>，<1，3>，<2，4>，<2，5>，<2，6>，
成绩 100 95 86
2、 数据元素（data element）
★ 数据元素是数据的基本单位，在计算机程序 中通常作为一个整体进行考虑和处理
◆ 数据也称节点（node）或记录（record）
2020/12/10
6
3、 数据项（data item） ★ 有独立含义的数据最小单位，也称域（field） ◆ 数据元素由若干数据项组成
◆ objects and operations
2020/12/10
18
数据类型
★ For example， the data type int consists of the objects [0,+1,-1,+2,-2,…,INT_MAX,INT_MIN], where INT_MAX and INT_MIN are the largest and smallest integers that can be represented on your machine.（They are defined in limits.h）
◆ The operations on integers include the arithmetic operators（操作符） ＋，－，×，/，％
2020/12/10
19
数据类型
★ In addition to knowing all of the facts about the operations on a data type，we might also want to know about how the objects of the data type are represented.
◆ 数据类型是一个对象的集合和定义（或施加）在 这些对象上的一组操作的总称
2020/12/10
17
数据类型
★ Whether your program is dealing with predefined （预定义）data types or user-defined data types， these two aspects must be considered: