软件技术基础课件

27-1第2章基本数据结构2.1数据结构的基本概念1.什么是数据结构2.数据结构的表示27-2数据、数据元素、数据项和数据结构1.基本术语数据(data)--反映客观事物的信息的集合，是信息的载体，它能够被计算机识别、存储和加工处理。数据元素(dataelement)--集合中的个体，数据的基本单位，一个数据元素可以由多个数据项组成（字段、域、属性）数据项—是具有独立含义的最小数据单位。数据对象(dataobject)相同特性的数据元素的集合--数据的子集★2.1数据结构的基本概念27-3数据、数据元素、数据项和数据结构数据结构(datastructure)—互相关联的数据元素的集合[二要素:B=(D,R)]，其中：数据元素之间的逻辑关系，也称为数据的逻辑结构，数据元素极其关系在计算机存储器内的表示，称为数据的存储结构（物理结构）数据的运算，即对数据施加的操作，即算法数据结构可以嵌套定义逻辑结构与物理结构及其两类映象数据类型(datatype)--与机器、运算有关的属性思考题：二要素（D,R)各自在计算机中如何表现？★27-4数据举例：身份证数据的管理在身份证管理应用层次的视图数据元素：每个身份证信息是一个数据元素，包括姓名、性别、身份证号和相片等数据项数据项：姓名、性别、身份证号和相片都是数据项数据结构：身份证信息之间的关系：逻辑结构：（线性）表结构物理结构：数组操作：增加、删除、查找数据结构的嵌套：例如：相片是一个图象数据，具有图象数据结构，它可以作为一个数据项嵌套在每个人的数据项中。27-51.数据的逻辑结构数据的逻辑结构特征从逻辑关系上描述数据，与数据的存储无关从具体问题抽象出来的数据模型与数据元素本身的形式、内容无关分类线性结构：线性表非线性结构：树、图★27-6数据结构四个基本的数据结构集合结构：关系集合是空集

顶点元素间无任何关系，R={}空集27-7线性结构和非线性结构线性结构：元素间的关系是1对1

1)有且只有一个初始节点2)最多有一个前区驱,最多有一个后继(也可以无)3)插入或删除一个节点后仍满足1),2)非线性结构:元素间的关系是1对多不满足线性结构特点的通称为非线性结构树型结构：一般树、二叉树、森林

一个结点可以有多个直接后继（除叶子结点外），

但只有一个直接前驱（除根结点外）★27-8图状结构图状结构：元素间的关系是多对多

一个结点可以有多个直接后继，也可以有多个直接前驱★27-9逻辑结构举例以班级数据为例，数据元素是学生，学生有学号、姓名和性别等数据项。学生同属于一个班级的关系构成集合结构按学号排列的学生关系构成线性结构如果学生分组管理，班长-组长-普通学生，那么学生的上下级关系则构成层次结构学生之间的朋友关系构成一个网状结构27-10例1、学生基本情况登记表。学号姓名 专业政治面藐

001 王洪 计算机党员002孙文计算机团员003 谢军 计算机团员004 李辉 计算机团员005 沈祥福计算机党员006 余斌 计算机团员007 巩力计算机团员008 孔令辉计算机团员

00100300200400600500007学号关系是一种线性结构关系逻辑结构举例27-112.数据的存储结构数据结构在计算机中的表示—为数据元素分配存储单元将数据元素间的逻辑关系映射到存储位置关系上依赖于程序设计语言所提供的数据类型和存储形式1.顺序存储结构等长；等间隔逻辑上相邻-->物理上相邻,关系自然确定易于描述线性结构，也可存储经过线性化处理的非线性结构主要数据类型:向量（表格存储结构）,数组高级计算机语言以数据类型的方式提供了一个基本数据结构集的存储和操作。影响选择的因素：数据的访问效率和存储空间占用的权衡。★27-1227-13顺序结构数据的存取27-14

2.链式存储结构每个节点由两部分组成:数据域,位置指示域(指针域)即可实现线性结构,又可表示非线性结构特点:可以表示任意复杂的结构存储空间不连续存储顺序与结构顺序不一致不能随机访问访问效率不均等主要形式:

单链表、双链表、多重链表、循环链表3.索引存储结构—顺序与链式存储结构的组合4.散列存储结构—位置信息通过关键字解析★data

单元节点P27-15链式存储示例data

dca10001001100210031004100510061007100101003链式存储单元节点PP27-16数据的逻辑结构与存储结构的关系1.数据的逻辑结构必定要有某种存储结构实现2.两种结构的关联既不固定，也不唯一。3.常用数据结构的分类可以定义在逻辑结构上，也可以定义在存储结构上，还可以定义在存储方法上。★27-172.1.3数据结构的图形表示逻辑结构的表示符号的表示

B=(D,R)

B-数据结构,D-数据元素的集合,

R-D上的一个关系图形的表示d2d3d1d4d5根节点内部节点终节点关系描述★27-18例、家族的族谱

家族的族谱反映的是家族成员之间的血缘关系，假设某家族有10个成员：A、B、C、D、E、F、G、H、I、J，他们之间的血缘关系可以用如下图表示。这种分支结构关系被称为树结构，它很象一棵倒置的树，A是树的根。非线性结构的图形表示JIACHGFE家族树的图示表示血缘关系是一种非线性结构关系BD27-19数据结构的研究对象及本课程讨论的问题数据结构的研究对象：非数值数据之间的结构关系，不一定能在分析数学范畴内建立解析模型运算操作以插入、删除、查找、更改为主。本课程讨论的问题：

应用中常用的几种数据结构，以及如何存储,如何处理它们。★27-20

操作与数据结构的定义密切相关。主要算法涉及到以下操作：①插入：在数据结构中的指定位置插入新的数据元素。②删除：删去数据结构中的指定的数据元素。③更新：改变数据结构中某个数据元素的值。④查找：在数据结构中寻找满足某个特定要求的数据元素。（返回位置或值）⑤排序：在线性数据结构中重新安排数据元素之间的逻辑顺序关系。数据结构的基本操作27-21算法与数据结构的对应性1.行为特性设计---算法设计信息结构特性设计---数据结构设计2.不能离开数据结构去抽象地分析程序的算法；也不能脱离算法去孤立地研究程序的数据结构，而只能从算法与数据结构的统一上去认识程序。27-22数据结构对算法影响一个算法的效率与数据的表示形式直接有关，对程序质量的影响极大。数据的构成和表示方式数据的存储方式数据的类型选择★27-23离散问题中的算法与数据结构27-24离散问题中的算法与数据结构27-25算法与程序设计的关系。程序就是在数据的某些特定的表示方式和结构基础上对抽象算法的计算机语言具体表述。数据结构是对数据的抽象，独立于具体数据算法是对处理过程的抽象，独立于具体处