第4章数据的组织.ppt

1、第4章数据组织，主要内容，4.1数据结构，4.2文件结构，1。基本概念、数据：它是信息的物理符号和信息的载体，可以被计算机识别、存储和处理。结构：数据元素之间的关系。数据结构：指数据元素之间有一个或多个关系的集合。主要研究内容数据的逻辑结构；数据的存储结构；对各种数据结构的操作，包括插入、删除、搜索、排序等。数据的逻辑结构和数据元素之间逻辑关系的描述称为数据的逻辑结构。集合结构：的结构中的数据元素除了属于同一集合之外，没有其他关系。线性结构：中的数据元素之间存在一对一的线性关系。树形结构：结构中的数据元素之间有一对多的层次关系。图形(网格)结构：结构中的数据元素之间存在多对多的任意关系。数据的

2、存储结构和数据的逻辑结构在计算机存储空间中的存储形式称为数据的物理结构(或存储结构)。顺序存储结构链存储结构，数据结构类型，线性结构(一对一)非线性结构，1。线性表是由n(n=0)个数据元素组成的有限序列，除了第一个元素之外，它只有一个前置元素，除了最后一个元素之外，它只有一个后续元素。它可以表示为：(a1，a2，ai，an)，其中ai是具有相同属性的数据元素，也称为线性表中的节点。线性表的顺序存储结构线性表的顺序存储结构的基本特征：线性表中所有元素所占的存储空间是连续的；线性表中的每个元素都以逻辑顺序存储在存储空间中。a1，a2，ai，an，1，2，n，I，长度为n 1的线性表在长度为n的线

3、性表的第I个元素ai之前插入新元素x后为(a1，a2，x，ai，an)。实现方法：在第I个元素之前插入新元素x，从最后一个(即第n个)元素开始，直到第I个元素之间的第n-i个元素依次向后移动一个位置，移动后在第I个位置写入新元素x。插入后，表的长度增加1。线性表删除操作删除长度为n的线性表(a1，a2，ai，an)中的第I个元素ai，然后成为长度为n-1的线性表(a1，a2，ai-1，ai-1，an)。实现方法：要删除第i (1=i=n)个元素，必须从第i 1个元素开始，直到最后一个(即第N个)元素之间的第n-i个元素依次向前移动一个位置。删除后，表格长度减少1。堆叠：用桶把物品堆叠起来，先把

4、它们放进去，压在底部，然后一个接一个地放上去。当你把它拿走的时候，你只能从上面一个一个地拿走。放和拿是在顶部进行的，而底部通常是不动的。堆栈的概念，一个只允许在一端插入和删除的表被称为堆栈的顶部，另一端被称为底部特征后进先出。栈的基本操作是放入栈中：首先判断，如果栈满了，不能放入栈中，就会发生溢出错误；如果不满意，将新元素插入堆栈的顶部位置，然后修改顶部指针top。堆栈：首先判断是否为空，如果堆栈为空，则出现“下溢”错误；当顶部指针不为空时，修改顶部指针，并将顶部元素分配给指定的变量。队列，队列，队列是一个线性表，只能在表的一端插入，在另一端删除。它根据“先进先出”的原则组织数据。允许插入的表

5、的末端称为队列尾部，允许删除的末端称为队列头部。队列的基本操作是入队：首先判断队列已满，如果队列已满，则不能入队，出现“溢出”错误；队列之外：队列首先为空。如果队列为空，您就不能离开队列，并且会出现“下溢”错误；树形结构是一种简单的非线性结构。每个节点只有一个前身，称为父节点；只有一个没有前驱的节点，称为根节点；每个节点可以有多个后继节点，称为该节点的子节点；没有后继的节点称为叶节点。一个节点所拥有的后继数称为该节点的度；所有节点的最大度数称为树的度数；根节点位于第一层，树的最高层称为树的深度。(1)树的基本术语，(2)二叉树，它只有一个根节点，每个节点最多有两个子树(度只能是0，1，2)，严

6、格区分它是左子树还是右子树。二叉树的五种基本形式空二叉树只有一个根节点，右子树是空的，左子树是空的，左子树和右子树都不是空的。(3)二叉树的基本性质。二叉树的第I层最多有2i-1(i=1)个节点。深度为k的二叉树的最大节点数是2k-1。(4)深度为k的完全二叉树有2k-1个节点(即属性2中允许的最大值)。(5)除最后一层外，整个二叉树的每层节点数达到最大，最后一层只缺少右边的几个节点。二叉树遍历，序遍历：首先访问根节点，然后遍历序中的左子树，最后遍历序中的右子树。中间顺序遍历(围绕根):首先以中间顺序遍历左边的子树，然后访问根节点，最后以中间顺序遍历右边的子树。(左根右)后序遍历(LRD):依

7、次遍历左子树，然后依次遍历右子树，最后访问根节点。(左根和右根)，遍历意味着沿着特定的搜索路径依次访问树中的每个节点一次和仅一次。遍历序列：ABDECFGH，遍历序列：DEBFCGAH，EDFGCBHA，文件结构，文件是作为一个单元处理的相关数据的外部集合，其主要目的是存储数据。当计算机关闭时，主存储器中的内容将会丢失，因此有必要使用文件作为永久存储数据的方式。设计文档的关键是将来如何从文档中检索信息(特定记录)。常用的检索方法包括顺序检索和随机检索，它们由访问方法决定。顺序访问：如果您需要按顺序访问文档(从头到尾一个一个地记录)，您应该使用顺序访问文档结构。随机访问：如果您想访问一个特定的记

8、录而不搜索所有以前的记录，您应该使用随机访问文件结构。文件结构分类，1。顺序文件，其记录只能按顺序从开始到结束逐一访问。记录被一个接一个地存储在辅助存储器中，并且在所有记录之后添加电渗流作为文件结束标记。2.索引文件。为了支持对文件的随机访问，您必须知道记录的地址。索引文件由数据文件和索引组成，数据文件是顺序文件(根据记录存储数据)。索引占用的空间非常小，只有两个字段，一个是对应于记录的键，另一个是磁盘上对应记录的地址。3。索引文件，4。哈希文件。在索引文件中，索引是文件的一部分，密钥通过索引映射到地址。哈希文件不存储键和地址的映射表，而是通过函数完成映射，用户给出键，函数根据键临时计算地址，然