第二章 数据结构基础.pptxVIP

数据的组织 数据结构——数据之间的关系 数据 数值、字符、图像、声音等 计算机存储、加工的对象 信息的表达形式 数据元素 数据项 11:55 1 数据的组成 【讨论】：观察学生档案管理的方法，每个学生都有学号、姓名、性别、出生日期、入学年份、所在学院等各种信息，这些信息是如何组织的？同学和同学之间的信息是如何区分的？在档案室中，学生的档案信息是如何存放的？如果要查找信息，该如何进行呢？ 11:55 2 数据元素 数据由数据元素组成 数据元素：作为一个整体进行组织和管理 其他称呼 元素（Element） 结点（Node） 记录（Record） 11:55 3 数据项 【讨论】：一个学生的档案表中包含的信息由哪些部分组成？ 学号、姓名、性别、专业、出生年月、入学年份、所在学院、照片等 数据项（Data Item） 组成数据元素的每一项 也称为字段 11:55 4 数据组织的三个层次 11:55 5 数据 数据元素1 数据项1 数据项2 。。。 数据元素2 数据项1 数据项2 。。。 。。。 数据的逻辑结构 计算机所处理的信息由若干个数据元素组成，而具有相同特征的数据元素之间往往会有一定的联系——数据的逻辑结构 【讨论】：数据一周7天的数据元素是什么？这些元素之间的联系是如何的？ 11:55 6 元素之间联系的描述 前趋 紧邻某个元素（E）之前的元素称为元素E的前趋，也称为直接前趋或前件 后继 紧邻元素（E）之后的元素称为元素E的后继，也称为直接后继或后件 11:55 7 数据的逻辑结构 数据元素之间前趋和后继的数量决定了数据元素之间不同的联系类型 一个数据的逻辑结构应包含两部分内容 数据元素的集合，用D表示 元素之间的前趋和后继关系的集合，用R表示 11:55 8 数据结构的表示 数据结构（Data Structure,DS）可以表示为：DS=(D,R) R可以用一个二元组的形式表示，如（E1，E2）表示元素E1和E2之间的先后关系 11:55 9 数据结构表示举例 一家三口 DS=(D,R) D={父亲，母亲，孩子} R={（父亲，孩子），（母亲，孩子）} 11:55 10 数据的逻辑结构分类 线性结构 数据元素之间的前趋和后继都是一对一的关系，各结点按逻辑关系形成了一条“链”，元素之间存在着明显的先后顺序 非线性结构 树形结构 图结构 11:55 11 数据的逻辑结构分类 线性结构 非线性结构 树形结构 数据元素中只有一个没有直接前趋，被称为根结点，其他每个数据元素都有并且仅有一个直接前趋，后继则没有个数限制。 图结构 11:55 12 数据的逻辑结构分类 线性结构 非线性结构 树形结构 图结构 每个数据元素都可以有任意多个前趋和后继，任何两个结点之间都可能邻接。 11:55 13 数据的物理结构 对数据元素之间关系的抽象描述，体现了数据的组织形式——数据的逻辑结构。 当使用计算机进行数据处理时，就要考虑数据在存储器中的存放方式——数据的物理结构 11:55 14 数据的物理结构 【讨论】：选课后某班级有来自不同专业不同年级的30位学生，学号不连续，安排在一间有50个座位的机房上课，机房中的座位编号为1到50，有哪些不同的安排方式？它们各有什么特点？ 1.写出有哪些方案 2.写出这些方案的优缺点 11:55 15 计算机存储空间的特点 计算机的内存是由一个个存储单元组成的 每个单元都有一个内存单元地址 内存地址从0开始编号 将数据保存在内存中，内存单元怎样分配？ 11:55 16 数据的物理结构 数据元素及其关系在计算机存储器中的存放形式——数据的物理结构 也称为存储结构 是数据元素本身及元素之间的逻辑关系在存储空间中的映像。 11:55 17 物理结构的种类 顺序存储结构 链式存储结构 索引存储结构 散列存储结构 11:55 18 顺序存储结构 数据元素按某种顺序存储在一组连续的存储单元中。 元素存储位置间的关系反映了元素间的逻辑关系，即逻辑上相邻的元素存放在物理位置相邻的存储单元中。 优点：存储空间利用率高 缺点：在插入、删除数据元素时，将引起该元素之后的大量元素的移动。 11:55 19 链式存储结构 数据元素存放在若干不一定连续的存储单元中，通过在元素中附加信息来表示与其相关的一个或多个其他元素的物理地址，从而建立元素之间的逻辑关系。 这种结构的存储空间利用率低，但插入、删除数据元素时，不会引起其他数据元素的移动。 11:55 20 索引存储结构 将数据元素排成一个序列：E1、E2、E3、…、En，每个元素Ei在序列中都有对应的位置值i，即元素的索引，建立附加的索引表，索引表中的第i个值就是第i个元素Ei的存储地址 11:55 21 散列存储结构 每个数据元素依照一定的规则存放在存储区中，在数据元素与其在存储器中的存储