数据结构绪.ppt

本章目录



*
第一页，共七十七页。
基本概念
1. 数据结构历史七十七页。
计算机处理问题的一般过程
问题
数学模型
建模
实现
求精
机外表示
处理要求
逻辑结构
基本运算
存储结构
算法
*
第十四页，共七十七页。
数据结构研究范畴
(1) 建立数据模型
逻辑结构
(2) 计算机中的表示
物理/存储结构
(3) 操作在计算机中的实现
算法
*
第十五页，共七十七页。
表1-1
数据结构的核心技术是分解与抽象。通过分解可以划分出数据的三个层次；
通过抽象，舍弃数据元素的具体内容，就得到逻辑结构。
通过分解将处理要求划分成各种功能
通过抽象舍弃实现细节，就得到运算的定义。
方面
层次
数据表示
数据处理
抽象
逻辑结构
基本运算
实现
物理结构
算法
评价
不同数据结构的比较及算法分析
数据结构课程内容体系
数据结构的内容包括三个层次的五个“要素”，如表1-1所示。
*
第十六页，共七十七页。
数据结构地位
*
第十七页，共七十七页。
有关概念和术语
数据：所有能输入到计算机中并能被计算机程序识别和处理的符号集合。
数值数据：整数、实数等
非数值数据：图形、图象、声音、文字等
数据元素：数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。
数据项：构成数据元素的不可分割的最小单位。
关键字：是指能识别一个或多个数据元素的数据项。若能起唯一识别的作用，则称之为 "主" 关键字，否则称之为 "次" 关键字。
数据对象：具有相同性质的数据元素的集合。
*
第十八页，共七十七页。
数据、数据元素、数据项之间的关系
包含关系：数据是由数据元素组成，数据元素是由数据项组成。
数据元素是讨论数据结构时涉及的最小数据单位，其中的数据项一般不予考虑。
姓名
学号
性别
班号
出生日期
入学成绩
年
月
日
*
第十九页，共七十七页。
数据结构：相互之间存在一定关系的数据元素的集合。按照视点的不同，数据结构分为逻辑结构和存储结构。
逻辑结构：指数据元素之间逻辑关系的整体。
关联方式或邻接关系
数据的逻辑结构是从具体问题抽象出来的数据模型
数据结构
存储结构：又称为物理结构，是数据及其逻辑结构在计算机中的表示。
实质上是内存分配，
在具体实现时，依赖于计算机语言。
*
第二十页，共七十七页。
典型逻辑结构
2. 线性表：数据元素之间存在着一对一的线性关系；
3. 树：数据元素之间存在
着一对多的层次关系
A
B
C
D
E
F
G
H
I
J
M
K
L
4. 图：数据元素之间存在
着多对多的任意关系。
B
A
C
D
F
E
1. 集合：数据元素之间就是 “属于同一个集合”
*
第二十一页，共七十七页。
数据结构的形式定义
Data_Structure ＝（D，R） （1-1）
D是数据元素的有限集，R是D上关系的有限集。
D={父亲，儿子，女儿，孙子，孙女}
R={（父亲,儿子）,（父亲,女儿）,
（儿子,孙子）， (儿子,孙女）}
：
F=(D, R)
*
第二十二页，共七十七页。
数组的形式定义
例：一维数组，A[6]={a1, a2, a3, a4, a5, a6}
R= {<ai, ai+1>| i=1, 2, 3, 4, 5}
D= {a1, a2, a3, a4, a5, a6}
a1
a2
a3
a4
a5
a6
例：二维数组
D={a1, a2, a3, a4, a5, a6}
R={row,col}
row = {<a1,a2>,<a2,a3>,<a4,a5>,<a5,a6>}
col = {<a1,a4>,<a2,a5>,<a3,a6>}
*
第二十三页，共七十七页。
存储结构
数据结构在计算机中的表示（又称映像）称为数据的物理结构，或称存储结构。它所研究的是数据结构在计算机中的实现方法，包括数据结构中元素的表示及元素间关系的表示。
1. 顺序存储
2. 链式存储
3. 散列存储
4. 索引存储
*
第二十四页，共七十七页。
顺序存储方法
顺序存储方法：把逻辑上