[计算机导论——以计算思维为导向（第4版）][董卫军 等]第3章 复杂问题的存储与管理.pptx

XXX第3复杂问题的存储与管理3.1数据结构概述数据结构的概念计算机解决问题的一般步骤数学模型设计算法编写程序问题数据结构数据结构主要研究数据的组织、存储和运算。数据组织运算存储元素及其关系在计算机中的表示。对数据元素进行的操作处理(插入、删除、修改、查找、排序)。数据元素以及元素之间的关系。能被计算机程序处理的符号的集合。数据结构的地位计算机科学的核心内容之一。介于数学、计算机硬件和计算机软件三者之间。不仅是一般程序设计的基础，而且是设计和实现编译程序、操作系统、数据库系统及其他系统程序的重要基础。数据结构的研究内容问题的抽象：基本构成（元素），以及它们之间的关系。 逻辑结构研究三个问题逻辑结构在计算机中的存储：存储元素以及元素之间的关系。 存储结构如何解决问题，满足管理需求。 运算逻辑结构逻辑结构的概念数据的逻辑结构是指反映数据元素之间逻辑关系的数据结构。数据的逻辑结构包含：（1）表示数据元素的信息；（2）表示各数据元素之间的关系。数据元素是数据的基本单位，即数据集合中的个体。有时一个数据元数可由若干数据项(Data Item)组成。数据项是数据的最小单位。数据元素亦称结点或记录。数据元素数据项逻辑数据结构的描述数据结构可描述为： Group=（D，R）有限个数据元素的集合。 D数据元素之间关系的集合。 R例：1. 一年四季的数据结构 B=(D,R) D={春，夏，秋，冬} R={(春，夏) ,(夏，秋),(秋，冬)}2. 家庭成员的数据结构 B=(D,R) D={父亲，儿子，女儿} R={(父亲，儿子) ,(父亲，女儿)}数据结构的图形表示春夏秋冬父亲儿子女儿学号姓名成绩2018161109张卓872018161107刘雨涵952018161103胡敏86常见的逻辑结构（1）线性结构 结点间是线性关系。A , B , C , ······· ，X ,Y , Z学 生 成 绩 表ABCDEFGH（2）树形结构ABCDEFGH全校学生档案管理的组织方式树形结构 —— 结点间具有分层关系1423123 （3）图形结构 D={ 1 , 2 , 3 , 4} R={(1,2) , (1,3) , (1,4) , (2,3), (2,4) , (3,4) } D={ 1 , 2 , 3 } R={ (1,2) , (2,3) , (3,2) , (1,3) }存储结构存储结构的概念 存储结构指逻辑结构在计算机存储空间中的具体实现。存储所有元素；存储元素之间的关系一种逻辑结构可以有多种存储结构。常见的存储结构顺序存储链式存储一种逻辑结构：可以表示成一种或多种存储结构。常见存储结构索引存储散列存储3.2 顺序存储与链式存储存储地址存储内容Lo顺序存储元素1Lo+m元素2采用连续存储空间存储数据元素；元素之间的关系通过存储位置的关系来表示。……..Lo+(i-1)*m元素i……..Lo+（n-1)*m元素n有关键字序列： 32 75 70 63 48 94 25 36 18a[0]a[1]a[2]a[3]a[4]a[5]a[6]a[7]a[8]a[9]327570634894253618父节点32i18632i2i+1右孩子左孩子8259050a[0]a[1]a[2]a[3]a[4]a[5]a[6]a[7]a[8]a[9]73218638255090优点：易于定位每个元素所占用的存储单元个数Loc(a)=Lo+（i-1)*m不足之处：作插入或删除操作时，需移动大量元素。长度变化较大时，需按最大空间分配。容量难以扩充。h1345链式存储73134685153635 ∧1001400每个结点都由两部分组成：数据域和指针域。数据域存放元素本身的数据，指针域存放下一个结点的地址。数据元素之间逻辑上的联系由指针来体现。链接存储结构特点：逻辑上相邻的节点物理上不必相邻。插入、删除灵活 (不必移动节点，只要改变结点中的指针)。不能直接定位，必须从头向后遍历。3.3 索引存储与散列存储索引方式存储结点信息的同时，建立附加的索引表。索引表中的每一项称为一个索引项，索引项的一般形式：关键字：能唯一标识一个结点的那些数据项。地址：同值关键字结点的起始位置。稠密索引：每个结点在索引表中都有一个索引项。稀疏索引：一组结点在索引表中只对应一个索引项地址关键字散列方式分配连续存储空间，元素的存储位置由元素的关键字计算得到。有关键字序列： 32 75 70 63 48 94 25 36 18存储空间大小：11地址计算规则：L=K MOD 11冲突解决机制：L+1计算存储位置：K327570634894253618L1094846337A10948?A01234567