精华内容
下载资源
问答
  • 磁盘文件结构

    2021-07-28 04:49:24
    文件结构是文件存放在磁盘等存储设备上的组织方法。主要体现在对文件和目录的组织上。在文件管理中,任何一个文件都存在着两种形式的结构:文件的逻辑结构和文件的物理结构。磁盘属于外存,磁盘文件结构是指文件在...

    文件结构是文件存放在磁盘等存储设备上的组织方法。主要体现在对文件和目录的组织上。在文件管理中,任何一个文件都存在着两种形式的结构:文件的逻辑结构和文件的物理结构。磁盘属于外存,磁盘文件结构是指文件在磁盘上的分配方式,采用不同的分配方式,会形成不同的文件物理结构。

    中文名

    磁盘文件结构

    外文名

    Disk File Structure

    学    科

    计算机定    义

    文件在磁盘上的分配方式

    种    类

    链接式文件结构、索引式文件结构

    领    域

    文件管理

    磁盘文件结构简介

    编辑

    语音

    磁盘文件结构是指文件在磁盘上的分配方式。属于文件外存分配方式,文件的物理结构直接与外存分配方式有关。在采用不同的分配方式时,将形成不同的文件物理结构。例如,在采用连续分配方式时的文件物理结构,将是顺序式的文件结构;链接分配方式将形成链接式文件结构;而索引分配方式则将形成索引式文件结构。

    磁盘文件结构文件结构

    编辑

    语音

    文件是由一系列的记录组成的。文件系统设计的关键要素,是指将这些记录构成一个文件的方法,以及将一个文件存储到外存上的方法。事实上,对于任何一个文件,都存在着以下两种形式的结构:

    (1) 文件的逻辑结构(File Logical Structure)。这是从用户观点出发所观察到的文件组织形式, 是用户可以直接处理的数据及其结构, 它独立于文件的物理特性, 又称为文件组织(FileOrganization)。

    (2) 文件的物理结构,又称为文件的存储结构,是指文件在外存上的存储组织形式。这不仅与存储介质的存储性能有关,而且与所采用的外存分配方式有关。

    无论是文件的逻辑结构,还是其物理结构,都会影响对文件的检索速度。

    磁盘文件结构磁盘文件结构的种类

    编辑

    语音

    磁盘文件结构顺序式的文件结构

    7bd778bb29701b33e9d5b409df7860ec.png

    图1顺序式的文件结构即文件采用连续分配方式,连续分配(Continuous Allocation)要求为每一个文件分配一组相邻接的盘块。 一组盘块的地址定义了磁盘上的一段线性地址。例如,第一个盘块的地址为 b,则第二个盘块的地址为b+1,第三个盘块的地址为 b+2……。通常,它们都位于一条磁道上,在进行读/写时,不必移动磁头,仅当访问到一条磁道的最后一个盘块后,才需要移到下一条磁道,于是又去连续地读/写多个盘块。在采用连续分配方式时,可把逻辑文件中的记录顺序地存储到邻接的各物理盘块中,这样所形成的文件结构称为顺序文件结构,此时的物理文件称为顺序文件。这种分配方式保证了逻辑文件中的记录顺序与存储器中文件占用盘块的顺序的一致性。为使系统能找到文件存放的地址,应在目录项的“文件物理地址”字段中,记录该文件第一个记录所在的盘块号和文件长度(以盘块数进行计量)。图 1示出了连续分配的情况。图中假定了记录与盘块的大小相同。Count 文件的第一个盘块号是 0,文件长度为 2,因此是在盘块号为 0 和 1 的两盘块中存放文件 1 的数据。

    连续分配的主要优点如下:

    (1) 顺序访问容易。访问一个占有连续空间的文件非常容易。系统可从目录中找到该顺序文件所在的第一个盘块号,从此开始顺序地、逐个盘块地往下读/写。连续分配也支持直接存取。例如,要访问一个从 b 块开始存放的文件中的第 i 个盘块的内容,就可直接访问b+i 号盘块。

    (2) 顺序访问速度快。因为由连续分配所装入的文件,其所占用的盘块可能是位于一条或几条相邻的磁道上,这时,磁头的移动距离最少,因此,这种对文件访问的速度是几种存储空间分配方式中最高的一种。

    连续分配的主要缺点如下:

    (1) 要求有连续的存储空间。要为每一个文件分配一段连续的存储空间,这样,便会产生出许多外部碎片,严重地降低了外存空间的利用率。如果是定期地利用紧凑方法来消除碎片,则又需花费大量的机器时间。

    (2) 必须事先知道文件的长度。要将一个文件装入一个连续的存储区中,必须事先知道文件的大小,然后根据其大小,在存储空间中找出一块其大小足够的存储区,将文件装入。在有些情况下,知道文件的大小是件非常容易的事,如可拷贝一个已存文件。但有时却很难,在此情况下,只能靠估算。如果估计的文件大小比实际文件小,就可能因存储空间不足而中止文件的拷贝,须再要求用户重新估算,然后再次执行。这样,显然既费时又麻烦。这就促使用户往往将文件长度估得比实际的大,甚至使所计算的文件长度比实际长度大得多,显然,这会严重地浪费外存空间。对于那些动态增长的文件,由于开始时文件很小,在运行中逐渐增大,比如,这种增长要经历几天、几个月。在此情况下,即使事先知道[1]

    磁盘文件结构链接式文件结构

    链接式文件结构即文件采用链接分配方式,如同内存管理一样, 连续分配所存在的问题就在于: 必须为一个文件分配连续的磁盘空间。如果在将一个逻辑文件存储到外存上时,并不要求为整个文件分配一块连续的空间,而是可以将文件装到多个离散的盘块中,这样也就可以消除上述缺点。在采用链接分配(Chained Allocation)方式时,可通过在每个盘块上的链接指针,将同属于一个文件的多个离散的盘块链接成一个链表,把这样形成的物理文件称为链接文件。由于链接分配是采取离散分配方式,消除了外部碎片,故而显著地提高了外存空间的利用率;又因为是根据文件的当前需要,为它分配必需的盘块,当文件动态增长时,可动态地再为它分配盘块,故而无需事先知道文件的大小。此外,对文件的增、删、改也十分方便。

    链接方式又可分为隐式链接和显式链接两种形式。

    隐式链接

    7cd66fd4c54b61d50ee9346278f7fa9e.png

    图2在采用隐式链接分配方式时,在文件目录的每个目录项中,都须含有指向链接文件第一个盘块和最后一个盘块的指针。图 2 中示出了一个占用 5 个盘块的链接式文件。在相应的目录项中,指示了其第一个盘块号是 9,最后一个盘块号是 25。而在每个盘块中都含有一个指向下一个盘块的指针,如在第一个盘块 9 中设置了第二个盘块的盘块号是 16;在16 号盘块中又设置了第三个盘块的盘块号 1。如果指针占用 4 个字节,对于盘块大小为 512字节的磁盘,则每个盘块中只有 508 个字节可供用户使用。

    隐式链接分配方式的主要问题在于:它只适合于顺序访问,它对随机访问是极其低效的。如果要访问文件所在的第 i 个盘块,则必须先读出文件的第一个盘块……,就这样顺序地查找直至第 i 块。当 i=100 时,须启动 100 次磁盘去实现读盘块的操作,平均每次都要花费几十毫秒。可见,随机访问的速度相当低。此外,只通过链接指针来将一大批离散的盘块链接起来,其可靠性较差,因为只要其中的任何一个指针出现问题,都会导致整个链的断开。

    为了提高检索速度和减小指针所占用的存储空间, 可以将几个盘块组成一个簇(cluster)。比如,一个簇可包含 4 个盘块,在进行盘块分配时,是以簇为单位进行的。在链接文件中的每个元素也是以簇为单位的。这样将会成倍地减小查找指定块的时间,而且也可减小指针所占用的存储空间,但却增大了内部碎片,而且这种改进也是非常有限的。

    显式链接

    0cabf5f03febe9c72775a821fba7c77e.png

    图3这是指把用于链接文件各物理块的指针,显式地存放在内存的一张链接表中。该表在整个磁盘仅设置一张,如图 3所示。表的序号是物理盘块号,从 0 开始,直至 N-1;N 为盘块总数。在每个表项中存放链接指针,即下一个盘块号。在该表中,凡是属于某一文件的第一个盘块号,或者说是每一条链的链首指针所对应的盘块号,均作为文件地址被填入相应文件的 FCB 的“物理地址”字段中。由于查找记录的过程是在内存中进行的,因而不仅显著地提高了检索速度,而且大大减少了访问磁盘的次数。由于分配给文件的所有盘块号都放在该表中,故把该表称为文件分配表 FAT(File Allocation Table)。

    磁盘文件结构索引式文件结构

    索引式文件结构即文件采用索引分配方式,一般分为单级索引分配、多级索引分配、混合索引分配方式。

    单级索引分配

    链接分配方式虽然解决了连续分配方式所存在的问题,但又出现了下述另外两个问题:

    (1) 不能支持高效的直接存取。 要对一个较大的文件进行直接存取, 须首先在 FAT 中顺序地查找许多盘块号。

    4aefa880081b0f2dd0f3bbea767135f3.png

    图4(2) FAT 需占用较大的内存空间。由于一个文件所占用盘块的盘块号是随机地分布在FAT 中的, 因而只有将整个 FAT 调入内存, 才能保证在 FAT 中找到一个文件的所有盘块号。当磁盘容量较大时,FAT 可能要占用数兆字节以上的内存空间,这是令人难以接受的。事实上,在打开某个文件时,只需把该文件占用的盘块的编号调入内存即可,完全没有必要将整个 FAT 调入内存。为此,应将每个文件所对应的盘块号集中地放在一起。索引分配方法就是基于这种想法所形成的一种分配方法。它为每个文件分配一个索引块(表),再把分配给该文件的所有盘块号都记录在该索引块中,因而该索引块就是一个含有许多盘块号的数组。在建立一个文件时,只需在为之建立的目录项中填上指向该索引块的指针。图4示出了磁盘空间的索引分配图。

    索引分配方式支持直接访问。当要读文件的第 i 个盘块时,可以方便地直接从索引块中找到第 i 个盘块的盘块号;此外,索引分配方式也不会产生外部碎片。当文件较大时,索引分配方式无疑要优于链接分配方式。

    索引分配方式的主要问题是:可能要花费较多的外存空间。每当建立一个文件时,便须为之分配一个索引块,将分配给该文件的所有盘块号记录于其中。但在一般情况下,总是中、小型文件居多,甚至有不少文件只需 1~2 个盘块,这时如果采用链接分配方式,只需设置 1~2 个指针。如果采用索引分配方式,则同样仍须为之分配一索引块。通常是采用一个专门的盘块作为索引块,其中可存放成百个、甚至上千个盘块号。可见,对于小文件采用索引分配方式时,其索引块的利用率将是极低的。

    多级索引分配

    当 OS 为一个大文件分配磁盘空间时, 如果所分配出去的盘块的盘块号已经装满一个索引块时, OS 便为该文件分配另一个索引块, 用于将以后继续为之分配的盘块号记录于其中。依此类推,再通过链指针将各索引块按序链接起来。显然,当文件太大,其索引块太多时,这种方法是低效的。此时,应为这些索引块再建立一级索引,称为第一级索引,即系统再分配一个索引块,作为第一级索引的索引块,将第一块、第二块……等索引块的盘块号填入到此索引表中,这样便形成了两级索引分配方式。如果文件非常大时,还可用三级、四级索引分配方式。

    混合索引分配方式

    7daf1c4de1e9f07ef7056a592250aa8e.png

    图5所谓混合索引分配方式,是指将多种索引分配方式相结合而形成的一种分配方式。例如,系统既采用了直接地址,又采用了一级索引分配方式,或两级索引分配方式,甚至还采用了三级索引分配方式。 这种混合索引分配方式已在 UNIX 系统中采用。 在 UNIX SystemⅤ的索引结点中, 共设置了13个地址项, 即iaddr(0)~iaddr(12), 如图5所示。 在BSD UNIX的索引结点中,共设置了 13 个地址项,它们都把所有的地址项分成两类,即直接地址和间接地址。

    词条图册

    更多图册

    参考资料

    1.

    汤小丹.计算机操作系统:西安电子科技大学出版社,2010

    展开全文
  • 数学结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及他们之间的关系和操作等学科。        描述非数值问题的数学模型不是数学方程,而是诸如表、树和图之类的...

           数学结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及他们之间的关系和操作等学科。
           描述非数值问题的数学模型不是数学方程,而是诸如表、树和图之类的具有逻辑关系的数据。


    1. 基本概念

    1.1 数据(data)

    数据是能输入计算机且能被计算机处理的各种符号的集合
    它是信息的载体,是对客观事物符号化的表示,能够被计算机识别、存储和加工。
    包括:
           数值型的数据:整数、实数等
           非数值的数据:文字、图像、图形、声音等

    1.2 数据元素(data element)

    数据元素是数据的基本单位,在计算机程序中通常作为一个整体进行考虑和处理。
    一个数据元素可由若干个数据项(data item)组成。
    数据项是数据的不可分割的最小单位。

    1.3 数据对象(data object)

    数据对象是性质相同的数据元素的集合,是数据的一个子集。

    1.4 数据元素和数据对象与数据的关系

    数据元素————组成数据的基本单位
           与数据的关系:是集合的个体
    数据对象————性质相同的数据元素的集合
           与数据的关系:是集合的子集

    2. 数据结构(data structure)

           数据结构是相互之间存在一种或多种特定关系的数据元素的集合;或者说数据结构是带结构的数据元素的集合。
           数据元素都不是孤立存在的,他们之间存在着某种关系,这种数据元素相互之间的关系成为结构。

    2.1 数据结构包括以下三个方面的内容:

    • 数据元素之间的逻辑关系,又称为数据的逻辑结构
    • 数据结构在计算机中的表示(又称映像)称为数据的物理结构,又称存储结构
    • 数据的运算和实现,即对数据元素可以施加的操作以及这些操作在相应的存储结构上的实现。

    2.2 数据结构的两个层次

    2.2.1 逻辑结构

    • 描述数据元素之间的逻辑关系
    • 与数据的存储无关,独立于计算机
    • 是从具体问题抽象出来的数学模型

    2.2.2 存储结构

    • 数据元素及其关系在计算机存储器中的结构(存储方式)
    • 是数据结构在计算机中的表示

    2.2.3 逻辑结构与存储结构的关系

    • 存储结构是逻辑关系的映像与元素本身的映像
    • 逻辑结构是数据结构的抽象,存储结构是数据结构的实现
    • 两者综合起来建立了数据元素之间的结构关系

    3. 逻辑结构

    3.1 划分方式一:

    (1). 线性结构(一对一)
           有且仅有一个开始和一个终端结点,并且所有结点都最多只有一个直接前趋和一个直接后继
           例如:线性表、栈、队列、串。
    (2). 非线性结构(一对多,多对多)
           一个结点可能有多个直接前趋和直接后继
           例如:树、图。

    3.2 划分方式二:

    (1). 集合:结构中的数据元素有且只有同属于一个集合的关系。
    (2). 线性结构:结构中的数据元素之间存在一对一的关系。
    (3). 树形结构:结构中的数据元素之间存在一对多的关系。
    (4). 图状结构或网状结构:结构中的数据元素之间存在多对多的关系。
    请添加图片描述

    4. 存储结构

    4.1 存储结构的种类

    • 顺序存储结构
    • 链式存储结构
    • 索引存储结构
    • 散列存储结构

    其中前两个为重点,后两个了解即可(暂时)。

    4.2 顺序存储结构

           用一组连续的存储单元依次存储数据元素、数据元素之间的逻辑关系有元素的存储位置来表示
           C语言中用数组来实现顺序存储结构。
           例如:(bat,cat,eat,…)
    请添加图片描述

    4.3 链式存储结构

           用一组任意的存储单元存储数据元素,数据元素之间的逻辑关系用指针来表示
           C语言中用指针来实现链式存储结构
           例如:(bat,cat,eat,…,mat)
    请添加图片描述

    4.4 索引和散列存储结构

    请添加图片描述

    字体略微有点草率,请见谅!!!

    展开全文
  • 之前介绍的所有的数据结构都是线性存储结构。本章所介绍的树结构是一种非线性存储结构存储的是具有“一对多”关系的数据元素的集合。(A) (B)图 1 树的示例图 1(A) 是使用树结构存储的集合 {A,B,C,D,E,F,G,H,I,J,K,...

    之前介绍的所有的数据结构都是线性存储结构。本章所介绍的树结构是一种非线性存储结构,存储的是具有“一对多”关系的数据元素的集合。

    387b1be7923aef93ff208ee45b5d7549.png

    (A)                                                                        (B)

    图 1 树的示例

    图 1(A) 是使用树结构存储的集合 {A,B,C,D,E,F,G,H,I,J,K,L,M} 的示意图。对于数据 A 来说,和数据 B、C、D 有关系;对于数据 B 来说,和 E、F 有关系。这就是“一对多”的关系。

    将具有“一对多”关系的集合中的数据元素按照图 1(A)的形式进行存储,整个存储形状在逻辑结构上看,类似于实际生活中倒着的树(图 1(B)倒过来),所以称这种存储结构为“树型”存储结构。

    树的结点

    结点:使用树结构存储的每一个数据元素都被称为“结点”。例如,图 1(A)中,数据元素 A 就是一个结点;

    父结点(双亲结点)、子结点和兄弟结点:对于图 1(A)中的结点 A、B、C、D 来说,A 是 B、C、D 结点的父结点(也称为“双亲结点”),而 B、C、D 都是 A 结点的子结点(也称“孩子结点”)。对于 B、C、D 来说,它们都有相同的父结点,所以它们互为兄弟结点。

    树根结点(简称“根结点”):每一个非空树都有且只有一个被称为根的结点。图 1(A)中,结点 A 就是整棵树的根结点。

    树根的判断依据为:如果一个结点没有父结点,那么这个结点就是整棵树的根结点。

    叶子结点:如果结点没有任何子结点,那么此结点称为叶子结点(叶结点)。例如图 1(A)中,结点 K、L、F、G、M、I、J 都是这棵树的叶子结点。

    子树和空树

    子树:如图 1(A)中,整棵树的根结点为结点 A,而如果单看结点 B、E、F、K、L 组成的部分来说,也是棵树,而且节点 B 为这棵树的根结点。所以称 B、E、F、K、L 这几个结点组成的树为整棵树的子树;同样,结点 E、K、L 构成的也是一棵子树,根结点为 E。

    注意:单个结点也是一棵树,只不过根结点就是它本身。图 1(A)中,结点 K、L、F 等都是树,且都是整棵树的子树。

    知道了子树的概念后,树也可以这样定义:树是由根结点和若干棵子树构成的。

    空树:如果集合本身为空,那么构成的树就被称为空树。空树中没有结点。

    补充:在树结构中,对于具有同一个根结点的各个子树,相互之间不能有交集。例如,图 1(A)中,除了根结点 A,其余元素又各自构成了三个子树,根结点分别为 B、C、D,这三个子树相互之间没有相同的结点。如果有,就破坏了树的结构,不能算做是一棵树。

    结点的度和层次

    对于一个结点,拥有的子树数(结点有多少分支)称为结点的度(Degree)。例如,图 1(A)中,根结点 A 下分出了 3 个子树,所以,结点 A 的度为 3。

    一棵树的度是树内各结点的度的最大值。图 1(A)表示的树中,各个结点的度的最大值为 3,所以,整棵树的度的值是 3。

    结点的层次:从一棵树的树根开始,树根所在层为第一层,根的孩子结点所在的层为第二层,依次类推。对于图 1(A)来说,A 结点在第一层,B、C、D 为第二层,E、F、G、H、I、J 在第三层,K、L、M 在第四层。

    一棵树的深度(高度)是树中结点所在的最大的层次。图 1(A)树的深度为 4。

    如果两个结点的父结点虽不相同,但是它们的父结点处在同一层次上,那么这两个结点互为堂兄弟。例如,图 1(A)中,结点 G 和 E、F、H、I、J 的父结点都在第二层,所以之间为堂兄弟的关系。

    有序树和无序树

    如果树中结点的子树从左到右看,谁在左边,谁在右边,是有规定的,这棵树称为有序树;反之称为无序树。

    在有序树中,一个结点最左边的子树称为"第一个孩子",最右边的称为"最后一个孩子"。

    拿图 1(A)来说,如果是其本身是一棵有序树,则以结点 B 为根结点的子树为整棵树的第一个孩子,以结点 D 为根结点的子树为整棵树的最后一个孩子。

    森林

    由 m(m >= 0)个互不相交的树组成的集合被称为森林。图 1(A)中,分别以 B、C、D 为根结点的三棵子树就可以称为森林。

    前面讲到,树可以理解为是由根结点和若干子树构成的,而这若干子树本身是一个森林,所以,树还可以理解为是由根结点和森林组成的。用一个式子表示为:

    Tree =(root,F)

    其中,root 表示树的根结点,F 表示由 m(m >= 0)棵树组成的森林。

    树的表示方法

    除了图 1(A)表示树的方法外,还有其他表示方法:

    64ee6ee26b225f40f27eb3beb39c8ed9.png

    (A)                                         (B)

    图2 树的表示形式

    图 2(A)是以嵌套的集合的形式表示的(集合之间绝不能相交,即图中任意两个圈不能相交)。

    图 2(B)使用的是凹入表示法(了解即可),表示方式是:最长条为根结点,相同长度的表示在同一层次。例如 B、C、D 长度相同,都为 A 的子结点,E 和 F 长度相同,为 B 的子结点,K 和 L 长度相同,为 E 的子结点,依此类推。

    最常用的表示方法是使用广义表的方式。图 1(A)用广义表表示为:

    (A , ( B ( E ( K , L ) , F ) , C ( G ) , D ( H ( M ) , I , J ) ) )

    总结

    树型存储结构类似于家族的族谱,各个结点之间也同样可能具有父子、兄弟、表兄弟的关系。本节中,要重点理解树的根结点和子树的定义,同时要会计算树中各个结点的度和层次,以及树的深度。

    展开全文
  • 在计算机中用一组地址连续的存储单元依次存储线性表的各个数据元素,称作线性表的顺序存储结构。特点: 随机存取表中元素。 插入和删除操作需要移动元素。 链接存储 在计算机中用一组任意的存储单元存储...

    -顺序结构-和-链接结构-适用在内存结构中-

    -索引结构-和-散列结构-适用在外存与内存交互结构-

    顺序存储

    在计算机中用一组地址连续的-存储单元-依次存储线性表的各个数据元素,称作线性表的-顺序存储结构-。特点:
    随机存取表中元素。
    插入和删除操作-需要移动元素。

    链接存储

    在计算机中用一组任意的--存储单元--存储--线性表--的数据元素(这组存储单元可以是连续的,也可以是不连续的)。它不要求逻辑上相邻的元素在物理位置上也相邻.因此它没有-顺序存储结构-所具有的弱点,但也同时失去了-顺序表-可随机存取的优点。特点:
    比-顺序存储结构-的存储密度小 (每个节点都由数据域和指针域组成,所以相同空间内假设全存满的话-顺序比链式存储更多-)。
    逻辑上-相邻的节点物理上不必相邻。
    插入、删除灵活 (不必移动节点,只要改变节点中的指针)。
    查找结点时-链式存储要比顺序存储慢。
    每个结点是由数据域和指针域组成。

    索引存储

    除建立存储结点信息外,还建立附加的索引表来标识结点的地址。索引表由若干索引项组成。特点:
    索引存储结构-是用结点的索引号来确定--结点存储地址,其优点是检索速度快,缺点是增加了附加的-索引表-,会占用较多的存储空间。在-数据表-中,就是用索引键来进行存储与检索的。

    散列存储

    散列存储:又称--hash存储,是一种力图将数据元素的存储位置与关键码之间建立确定对应关系的查找技术。
    散列法存储的基本思想是:由节点的关键码值决定节点的存储地址。散列技术-除了可以用于查找外,还可以用于存储。特点:
    散列是--数组存储方式的一种发展,相比数组,散列的数据访问速度要高于数组,因为可以依据存储数据的部分内容找到数据在数组中的存储位置,进而能够快速实现数据的访问,理想的散列访问速度是非常迅速的,而不像在数组中的遍历过程,采用存储数组中内容的部分元素作为映射函数的输入,映射函数的输出就是存储数据的位置,这样的访问速度就省去了遍历数组的实现,因此时间复杂度可以认为为O(1),而数组遍历的时间复杂度为O(n)。
    散列(hashing)----是一种-重要的存储方法-,也是一种常见的查找方法。
    基本思想:以结点的关键字k为自变量,通过一个确定的函数关系f,计算出对应的函数值,吧这个函数值解释--为结点的存储地址,将结点存入到f(k)所指示的存储位置上,在查找时再根据要查找的关键字,用同样的函数计算地址,然后到相应的单元中读取。散列法又被成为关键字——地址转换法。
    顺序表--的特点是:寻址容易,插入和删除困难; 而-链表-的特点是:寻址困难,插入和删除容易。 这个世界上有没有一种能够综合两者优点的,既寻址容易又插入和删除容易的数据结构--Yes,它就是Hash表。
    哈希表:
    用散列法存储的线性表被称为哈希表,使用的函数被称为*散列函数或者哈希函数,f(k)被称为散列地址或者哈希地址。通常情况下,散列表的存储空间是一个一维数组,而其哈希地址为数组的下标
    哈希函数的选择原则:
    若哈希函数是一个一一对应的函数,则在查找时,只需要根据哈希函数对给定关键字的某种运算得到待查找结点的--存储位置-,无需进行比较
    一般情况下,散列表的空间--要比结点的集合大,虽然-浪费了一部分空间但是却提高了查找的效率,散列表空间为m,-填入表中结点数为n,则比值n/m成为--哈希表--的装填因子-,一般取0.65~0.9之间
    哈希函数应当尽量简单,其值域必须--在表长的-范围之内,尽量不要产生“冲突”(两个关键字得到相同的哈希地址)
    Hash表优缺点:
    Hash表存在的优点显而易见,能够在-常数级的时间复杂度上进行查找,并且插入数据和删除数据比较容易。但是它也有某些缺点,比如--不支持排序,一般比用线性表存储需要-更多的空间,并且记录的关键字不能重复。
    C++的STL中Hashmap和map的区别:
    hash_map的用法和map是一样的,提供了 insert,size,count等操作,并且里面的元素也是以pair类型来存贮的。-虽然对外部提供的函数和数据类型是一致的,但是其底层实现是完全不同的,map底层的数据结构是rb_tree(红黑树)而,-hansh_map却是哈希表来实现的。
    总体来说,-hash_map 查找速度会比map快,而且查找速度基本和数据量大小无关,属于常数级别;而map的查找速度是log(n)级别。hash还有-hash函数-的耗时。当有100w条记录的时候,map也只需要20次的比较,200w也只需要21次的比较!所以并不一定常数就比log(n) 小!
    hash_map对空间的要求--要-比map高很多,所以是--以空间换时间--的方法,而且,hash_map如果hash函数和hash因子选择不好的话,也许不会达到你要的效果,所以至于用map,还是hash_map,从3个方面来权衡:查找速度,- 数据量, 内存使用,还有一个就是你的经验!没有特别的标准
    C++ HashTable和HashMap的区别:
    HashTable的应用非常广泛,HashMap是新框架中用来代替HashTable的类,也就是说建议使用HashMap,-不要使用--HashTable。可能你觉得HashTable很好用,为什么不用呢?--这里简单分析他们的区别。
    HashTable--的方法是--同步--的,HashMap未经同步,所以在多线程场合要手动同步HashMap这个区别--就像Vector和ArrayList一样。
    HashTable不允许null值(key和value都不可以),HashMap允许null值(key和value都可以)。
    HashTable有一个contains(Object value),功能和containsValue(Object value)功能一样。
    HashTable使用Enumeration,HashMap使用Iterator。
    HashTable中hash数组--默认--大小是11,增加的方式是 old*2+1。HashMap中hash数组的默认大小是16,而且一定是2的指数。
    哈希值的使用不同,HashTable直接使用对象的hashCode
    展开全文
  • 数据的四种存储结构

    千次阅读 2021-07-28 08:35:42
    大家好,我是时间财富网智能客服时间君,上述问题将由我为大家进行解答。...顺序存储方式也称为顺序存储结构,一般采用数组或结构数组来描述。2、链接存储链接存储方式比较灵活,不要求逻辑上相邻的节点在物理位置...
  • :俗话说的好,运算的定义是针对逻辑结构的,运算的实现是针对存储结构的 L:好深奥啊!什么运算定义,运算实现?? ????:运算定义简单来说就是:你在脑海里打算怎么对这6个英文字母排序,总的来说就只有以下四种...
  • 数据存储结构

    2021-04-08 17:45:41
    数据的逻辑结构在计算机存储空间中的存放形式称为数据的物理结构(也称为存储结构)。一般来说,一种数据结构的逻辑结构根据需要可以表示成多种存储结构,常用的存储结构有顺序存储、链式存储、索引存储和哈希存储等。...
  • 我们知道,数据之间的关系有 3 种,分别是 "一对一"、"一对多" 和 "多对多",前两种关系的数据可分别用线性表和树结构存储,本节学习存储具有"多对多"逻辑关系数据的结构——图存储结构。 图 1 图存储结构示意...
  • 数据库的存储结构

    2021-02-08 06:46:52
    数据库的存储结构数据库的存储结构是怎样的?记录是按照行存储的,但是数据库的读取不是以行为单位,否则一次读取只能处理一行,效率很低。因此数据库,无论是读一行,还是读取多行,都是将这些行所在的页进行加载。...
  • 在广义表中,ai可以是单元素也可以是广义表,它们分别称为广义表的原子和子表。显然,广义表的定义时递归的。 一般用大写字母表示广义表的子表,用小写字母表述广义表的原子。当广义表GL非空时,第一个元素a1为GL的...
  • 之前介绍的所有的数据结构都是线性存储结构。本章所介绍的树结构是一种非线性存储结构存储的是具有“一对多”关系的数据元素的集合。(A) (B)图 1(A) 是使用树结构存储的集合 {A,B,C,D,E,F,G,H,I,J,K,L,M} 的示意图...
  • 链式存储结构
  • 本节我们学习二叉树的链式存储结构。 正文 图 1 普通二叉树示意图 如图 1 所示,此为一棵普通的二叉树,若将其采用链式存储,则只需从树的根节点开始,将各个节点及其左右孩子使用链表存储即可。因此,图 1 对应的...
  • 数据结构-链式存储结构
  • 存储体系结构

    2021-06-27 03:53:04
    特别INTERNET的快速发展、在线数据存储的快速增长、电子商务等众多需求,原来以服务器为中心的存储技术已经不适合今天的存储需求了,现在一般采用网络存储体系结构存储体系结构是以存储为中心的存储技术。中文名...
  • 树的存储结构(C++)

    2021-03-29 11:33:45
    在树中,除了根节点外的任意一个结点都有一个唯一的双亲结点,因此可以考虑使用一组连续的储存空间储存树中的每一个结点,数组中的一个元素可以表示为树中的一个结点。在数组元素中除包含结点元素本身,还包含它的...
  • 这里写目录标题算法时间复杂度数据的存储结构 算法时间复杂度 1<log2n<n<n2 数据的存储结构 数据的存储结构一般有四种方式: 1、顺序存储方式 2、链式存储方式 3、索引存储方式 4、散列存储方式 计算机...
  • } } 数据结构4:顺序表(线性表的顺序存储结构)及C语言实现 逻辑结构上呈线性分布的数据元素在实际的物理存储结构中也同样相互之间紧挨着,这种存储结构称为线性表的顺序存储结构. 也就是说,逻辑上具有线性关系的数据...
  • 称为单链表 为了正确表示结点间的逻辑关系,在存储每个结点值的同时,还必须 存储指示其直接后继结点的地址(或位置),称为指针(pointer)或链(link), 这两部分组成了链表中的结点结构 链表结点结构 data :数据域,...
  • 存储系统的层次结构

    千次阅读 2021-04-29 15:33:54
    目录一.背景二.层次结构(1)结构(2)原理 一.背景 现在我们使用的计算机系统结构是冯诺依曼体系结构,它的一个特点就是中央处理器CPU(控制器+算数运算器)与存储器相...所以就有了我们接下来的存储系统层次结构
  • 数据结构(线性存储)

    2021-08-12 10:46:33
    1.将数据依次存储在连续的整块物理空间中,这种存储结构称为顺序存储结构(简称顺序表); 2.数据分散的存储在物理空间中,通过一根线保存着它们之间的逻辑关系,这种存储结构称为链式存储结构(简称链表); 以上...
  • 一、链式存储结构 由于顺序存储二叉树的空间利用率较低,因此二叉树一般都采用链式存储结构,用链表结点来存储二叉树中的每个结点。在二叉树中,结点结构通过包括若干数据域和若干指针域,二叉链表至少包含3个域:...
  • 链式存储结构

    2021-09-17 14:15:48
    存储的地址,称为指针,也称为链。 由这样的若干个结点构成的就是链表,他们通过指针连接在一起。 记录第一个元素的地址,称为头指针。通常不会知道每个元素具体的存储位置在哪里,只需要画出示意箭头。单链表...
  • 数据对象在计算机中的存储表示称为数据的存储结构,也称为物理结构。把数据对象存储到 计算机时,通常要求既要存储各数据元素的数据,存储数据元素之间的逻辑关系,数据元素 在计算机内用一个结点来表示。数据...
  • Oracle数据库的存储结构(StorageStructure)分为物理存储结构和逻辑存储结构两种,分别描述了在操作系统中和数据库系统内部数据的组织管理方式。其中,物理存储结构表现为操作系统中一系列文件)逻...
  • (1) 集合结构结构中的数据元素之间除了同...1.顺序存储结构:借助数据元素之间的相对位置来表示元素之间的逻辑结构.(vector动态数组、deque双端队列、stack栈容器、queue队列容器) 2.链式存储结构:借助数据元..
  • 为了有效地组织、管理数据,提高数据库的逻辑独立性和物理独立性,人们为数据所设计了一个严谨的体系结构,数据库领域公认的标准结构是三级模式结构,包括外模式、模式和内模式,根据对象不同,可分为面向用户或...
  • 树形结构存储方法的选择 简单的方法跟踪多级回复构成的树形分支:parent_id 一开始的思路 使用parent_id跟踪分支 使用先找出所有节点,按照一定顺序整合成树形结构 缺陷: 在深度过深时仅用parent_id需要执行很多...
  • 与线性表一样,二叉树也有顺序存储结构与链式存储结构 二叉树的顺序存储
  • 2.图中每个顶点v的所有邻接点构成一个线性表,由于邻接点的个数不定,所以用单链表存储,无向图称为顶点v的边表,有向图则称为顶点v作为弧尾的出边表。 例如图7-4-6所示的就是一个无向图的邻接表结构。 从图中我们...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 664,909
精华内容 265,963
关键字:

存储结构又称为