精华内容
下载资源
问答
  • 理解的关键 如何分配与回收? 如下为关键理解点: 只有专用块才会被读入内存(可以把它视为第一);专用块的第一项(如果按...此时,需要该项所指向的第二,但是第二中也有一项是保存了下一信息的,需要...

    理解的关键

    如何分配与回收?
    如下为关键理解点:

    1. 只有专用块才会被读入内存(可以把它视为第一组);专用块的第一项(如果按指针从上往下,那就是最后一项),所指向的第二组,该组不被读入内存
    2. 所有的空闲块都可以被分配;所以,某些存储了下一组信息的关键块需要先保存处理。

    分配与回收的具体过程

    以专用块还剩最后一项为例:
    此时,需要该项所指向的第二组,但是第二组中也有一项是保存了下一组信息的,需要保存,所以,这一项的信息就被保存到专用块的最后一项中


    整个分配过程按照如下顺序:
    专用快 → 第二组 → 第三组……


    很自然,回收的过程正好是逆序,即:
    最后一组 → …… → 第三组 → 第二组 → 专用块


    这样就好理解了,比如,回收时,先把第三组恢复了,那么原先保存在专用块中的“第二组指向下一组的信息”就需要写回第二组,然后指向第二组的信息再写回专用块。 这有一种递归调用而后返回的感觉**

    展开全文
  • java实现堆排序链表法和数法.pdf
  • 空闲链表法空闲盘块链空闲盘区链4.位示图法5.成组链接法 0.思维导图 1.存储空间的划分与初始化 2.空闲表法 如何分配? 如何回收? 3.空闲链表法 空闲盘块链 空闲盘区链 4.位示图法 如何分配与回收? 5...


    0.思维导图

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    1.存储空间的划分与初始化

    在这里插入图片描述

    2.空闲表法

    如何分配?
    在这里插入图片描述

    在这里插入图片描述
    如何回收?
    在这里插入图片描述
    在这里插入图片描述

    3.空闲链表法

    在这里插入图片描述

    空闲盘块链

    在这里插入图片描述

    空闲盘区链

    在这里插入图片描述

    4.位示图法

    在这里插入图片描述
    如何分配与回收?

    在这里插入图片描述

    5.成组链接法

    在这里插入图片描述
    超级块的作用
    在这里插入图片描述
    如何分配?
    需要1个空闲磁盘块
    在这里插入图片描述
    在这里插入图片描述
    需要100个空心啊磁盘块
    在这里插入图片描述
    在这里插入图片描述
    如何回收?
    在这里插入图片描述
    在这里插入图片描述
    第二种情况,第一组已满
    在这里插入图片描述
    在这里插入图片描述
    参考:《王道操作系统》

    展开全文
  • 4、文件存储空间管理思维导图文件的初始化和划分文件存储空间管理方法1、存储空间管理——空闲表法2、存储空间管理——空闲链表法3、存储空间管理——位示图法4、存储空间管理——成组链接法 思维导图 文件的初始化...

    思维导图

    在这里插入图片描述

    文件的初始化和划分

    在这里插入图片描述

    物理磁盘分为多个文件卷
    文件卷分为目录区和文件区
    文件区:存放文件数据
    目录区:存放文件目录信息(FCB)、用于磁盘存储空间管理的信息

    文件存储空间管理方法

    1、存储空间管理——空闲表法

    在这里插入图片描述

    用一张表来记录磁盘中的空闲块,空间的回收和分配都只需要对该表进行操作即可

    2、存储空间管理——空闲链表法

    在这里插入图片描述

    空闲盘块链:
    在这里插入图片描述
    空闲盘区链:
    在这里插入图片描述

    3、存储空间管理——位示图法

    在这里插入图片描述
    在这里插入图片描述

    用一张位图来记录每一个物理块的空闲状态,分配和回收都对位图进行操作

    4、存储空间管理——成组链接法

    超级块
    在这里插入图片描述

    成组链接法必须要有一个超级块,作为硬盘所有物理块的头指针,指向下一组空闲磁盘块。

    在这里插入图片描述

    分配:
    在这里插入图片描述
    在这里插入图片描述

    回收:
    在这里插入图片描述
    在这里插入图片描述

    展开全文
  • 实例讲解成组链接

    万次阅读 多人点赞 2017-06-22 11:20:43
    成组链接法是一种用来记录磁盘空闲盘块的方法,它使得磁盘盘块的分配和回收都变得十分简单,而且没有空闲表法和空闲链表法它们的表太长的缺点,因此被引用到UNIX系统当中。 成组链接法介绍计算机上的文件是记录在...

    成组链接法是一种用来记录磁盘空闲盘块的方法,它使得磁盘盘块的分配和回收都变得十分简单,而且没有空闲表法和空闲链表法它们的表太长的缺点,因此被引用到UNIX系统当中。

    成组链接法介绍

    计算机上的文件是记录在磁盘上的,而磁盘空间的分配是以盘块为单位的,那么如何管理磁盘中已经被使用的块和未被使用的块是操作系统必须要考虑的问题。下面将介绍比较实用又有点复杂的成组链接法,看它是如何把磁盘中所有的空闲盘块都记录起来,又不耗费太多的内存空间。
    请看下图:
    这里写图片描述

    下面的文字来自汤氏的操作系统教材:

    1、空闲盘块的组织

    (1)空闲盘块号栈:用来存放当前可用的一组空闲盘块的盘块号(最多含100 个号),以及栈中尚有的空闲盘块号数N。顺便指出,N 还兼作栈顶指针用。例如,当N=100 时,它指向S.free(99)。由于栈是临界资源,每次只允许一个进程去访问,故系统为栈设置了一把锁。(只有这个是放在内存中的,其它是在磁盘上。)
    (2) 文件区中的所有空闲盘块被分成若干个组,比如,将每100 个盘块作为一组。假定盘上共有10 000 个盘块,每块大小为1 KB,其中第201~7999 号盘块用于存放文件,即作为文件区,这样,该区的最末一组盘块号应为7901~7999;次末组为7801~7900……;第二组的盘块号为301~400;第一组为201~300,如上图右部所示。
    (3) 将每一组含有的盘块总数N 和该组所有的盘块号记入其前一组的第一个盘块的
    S.free(0)~S.free(99)中。这样,由各组的第一个盘块可链成一条链。
    (4) 将第一组的盘块总数和所有的盘块号记入空闲盘块号栈中,作为当前可供分配的空闲盘块号。
    (5) 最末一组只有99 个盘块,其盘块号分别记入其前一组的S.free(1) ~S.free(99)中,而在S.free(0)中则存放“0”,作为空闲盘块链的结束标志。(注:最后一组的盘块数应为99,不应是100,因为这是指可供使用的空闲盘块,其编号应为(1~99),0号中放空闲盘块链的结尾标志。)

    2、空闲盘块的分配与回收

    当系统要为用户分配文件所需的盘块时,须调用盘块分配过程来完成。该过程首先检查空闲盘块号栈是否上锁,如未上锁,便从栈顶取出一空闲盘块号,将与之对应的盘块分配给用户,然后将栈顶指针下移一格。若该盘块号已是栈底,即S.free(0),这是当前栈中最后一个可分配的盘块号。由于在该盘块号所对应的盘块中记有下一组可用的盘块号,因此,须调用磁盘读过程,将栈底盘块号所对应盘块的内容读入栈中,作为新的盘块号栈的内容,并把原栈底对应的盘块分配出去(其中的有用数据已读入栈中)。然后,再分配一相应的缓冲区(作为该盘块的缓冲区)。最后,把栈中的空闲盘块数减1 并返回。
    在系统回收空闲盘块时,须调用盘块回收过程进行回收。它是将回收盘块的盘块号记入空闲盘块号栈的顶部,并执行空闲盘块数加1 操作。当栈中空闲盘块号数目已达100 时,表示栈已满,便将现有栈中的100个盘块号记入新回收的盘块中,再将其盘块号作为新栈底。

    实例讲解成组链接法

    如果对上面的讲解感到迷惑的话,请看下面的例子,这是一个很经典的练习题:
    例题.某个系统采用成组链接法来管理磁盘的空闲空间,目前磁盘的状态如图1所示。

    (1) 该磁盘中目前还有多少个空闲盘块?

    (2) 请简述磁盘块的分配过程。

    (3) 在为某个文件分配3个盘块后,系统要删除另一文件,并回收它所占的5个盘块,它们的盘块号依次为700、711、703、788、701,请画出回收后的盘块链接情况。
    图一

                                    图1:当前磁盘状态
    

    解答:
    (1):301;首先看空闲盘块号栈,此时N=2,表示有两个空闲盘块299、300,而盘块300号上面又写着有100个空闲盘块:301-400,它还有下一个链接的盘块400;在盘块400中,记录有100个空闲盘块401-500;然后又链接到500号盘块,在500号盘块中,虽然N=100,但是第一个是0,它表示空闲盘块链的结尾。因此,总共的空闲盘块有:299、300、301-400、401-500、501-599;即301个空闲盘块。
    (2):参考介绍部分。
    (3):这个是最重要的部分,也是理解整个成组链接法的关键部分,我看很多博客都没有详细写明分配和回收的过程,因此这也正是我写这篇博客的原因。
    步骤1、分配三个空闲盘块:
    分配的过程是这样的,首先看空闲盘块号栈,发现N=2,那么到达栈顶即S.free[2-1]=299,即把299号盘块分配出去了,这时磁盘状态如下:
    这里写图片描述

    然后分配第二个盘块,这时N=1,如果再分配就会变成空栈了,因为S.free[N-1]=S.free[0]!=0,所以需要将300号盘块的内容拷贝到空闲盘块号栈,并分配300号盘块(如果S.free[0]=0,则表示没有空闲盘块,将会阻塞进程):
    这里写图片描述
    接下来分配301号盘块你也会做啦:
    这里写图片描述

    回收700、711、703、788、701号盘块:
    回收的过程也是从栈顶开始的,首先看N=99,然后回收700,会将700放在S.free[N]的位置,然后将N加1变成100:
    这里写图片描述
    然后回收711号盘块,因为此时空闲栈的N=100,已经满了,如果再回收,需要将空闲盘块栈的内容移动到711号盘块上,然后将空闲盘块栈的S.free[0]设置为711,N设置为1:
    这里写图片描述
    最后回收703/788/701也是同理:
    这里写图片描述

    相信经过这样的举例说明以后,大家都对成组链接法比较了解了吧~

    展开全文
  • 成组链接

    万次阅读 多人点赞 2016-06-18 12:25:58
    成组链接法作为文件存储空间管理方法之一(主要是空闲盘区的管理),还有其他三种管理方法分别是:空闲表法、空闲链表法和位示图法,它克服了空闲链表法表太长的缺点,但是保持了其优点,即分配和回收一个盘块比较简单...
  • 给你一个链表,每 k 个节点一进行翻转,请你返回翻转后的链表。 k 是一个正整数,它的值小于或等于链表的长度。 如果节点总数不是 k 的整数倍,那么请将最后剩余的节点保持原有顺序。 示例: 给你这个链表:1->...
  • K翻转链表

    千次阅读 2016-07-14 17:07:03
    题目给你一个链表以及一个k,将这个链表从头指针开始每k个翻转一下。 链表元素个数不是k的倍数...利用k找到需要翻转的部分链表,利用头插进行翻转 注意当链表长度不足k个的时候不需要翻转,这里我是单独进行判断的。
  • 为了解决散列冲突,主要采用下如下两种方式: 2 链表法 分散链表法使用链表解决冲突,将散列值相同的元素都保存到一个链表中。当查询的时候,首先找到元素所在的链表,然后遍历链表查找对应的元素。下面是一个示意图...
  • K 个一翻转链表 给你一个链表,每 k 个节点一进行翻转,请你返回翻转后的链表。 k 是一个正整数,它的值小于或等于链表的长度。 如果节点总数不是 k 的整数倍,那么请将最后剩余的节点保持原有顺序。 示例 : ...
  • 链表——按k个结点一来反转链表

    千次阅读 2016-05-10 10:46:18
    运用反转链表的通reverse,对链表进行循环,当计数长度k不时,指针继续前进;当计数长度到达k时,将该首尾节点first和node作为参数传入翻转函数reverse进行翻转,然后重新拼接到原链表中。直至到达链表末尾。 ...
  • 组链表是一种常用的数据结构,它由数组加链表组成,往往用于信息检索中。 每个链表由n个链表结点组成,每个链表都有头结点,头结点不存放实际数据,纯粹作为一个索引。 所有链表的头结点组成一个数组,即数组的每...
  •  1、双亲表示  从树的定义可知,除根结点外,树中的每个结点都有唯一的一个双亲结点。根据这一特性,可用一连续的存储空间(一维数组)存储树中的各结点。树中的结点除保存结点本身的信息之外,...
  • 链表

    2018-01-13 22:25:00
    一、PTA实验作业 ...=9)和一(n个)升序的整数,建立单向链表,再输入一个整数 x,把 x 插入到这数据中,使该数据仍然有序。 1. 本题PTA提交列表 2. 设计思路 主函数中输入repeat,...
  • 头插相对来说是新手较为容易理解的一种建立链表的方式,众所周知,使用头插后,读取数据的顺序与生成的链表中的元素的顺序是相反的。我们根据字面意思也非常好理解,头插顾名思义就是将新结点插入到当前链表的...
  • 链表存储结构: 要建立双链表,首先要明白双链表的存储结构定义: typedef struct DLinkList{ //存储结构定义 int data; DLinkList * prior; DLinkList * next; } 思想: 该方法是将新节点插入双链表的表尾...
  • 给你一个链表,每k个节点一进行翻转,请你返回翻转后的链表。 k是一个正整数,它的值小于或等于链表的长度。 如果节点总数不是k的整数倍,那么请将最后剩余的节点保持原有顺序。 示例 : 给定这个链表:1->2...
  • 查找功能只需要沿着头节点把链表遍历一遍看看是否你要找到数据与结点中存放的数据相同。 修改信息功能可以用删除信息功能和查找信息功能组合起来完成 必须每次都要从头节点来访问链表 代码可以之后会发 还有...
  • 将给出的链表中的节点每 k 个一翻转,返回翻转后的链表 如果链表中的节点数不是 k 的倍数,将最后剩下的节点保持原样 你不能更改节点中的值,只能更改节点本身。 要求空间复杂度 O(1) 例如: 给定的链表是1→2→3...
  • 25. K 个一翻转链表

    2020-02-27 22:42:51
    问题 给你一个链表,每 k 个节点一进行翻转,请你返回翻转后的链表。...创建一个新的链表,pre表头插时的头结点,cur表尾插时的尾结点,对完整的,第一个元素使用尾插,第2个到第k个使用头插...
  • 链表的快速排序

    2017-12-01 11:48:55
    数组的快速排序/*对数中的元素按照从小到大的顺序快速排序*/ void QuickSort(int * a,int left,int right) { //设置终结递归的条件 if(left>=right) return ; int l=left,r=right; int value=left; w
  • 数据结构—链表的前插与后插

    万次阅读 多人点赞 2018-11-04 20:15:07
    在进行单链表的基本运算之前必须先建立单链表,建立单链表的常用方法有...头插建表虽然简单,但生成的链表中节点的次序和原数组的次序相反,若希望两者的次序一致,可采用尾插建立 尾插建表,该算法是将新节点...
  • k个链表利用二分为k个独立的子链表,然后两两组合,最后合并k个排序链表 时间复杂度:O(nlogk),n为单个链表的长度,k表示k个链表 题解2:优雅的暴力 利用队列queue来实现两两链表的组合,首先将队列前两个...
  • 链表排序--冒泡

    千次阅读 2016-10-17 17:43:55
    对于链表的排序,在上学期做课程设计的时候忽略了这个问题,然后在最近才进行了实际的操作,结果发现问题还挺多的,实际解决起来学到了一些东西,决定给大家分享一下。 排序的代码首先,给大家先把链表排序的代码...
  • 哈希表数组链表表示示例

    千次阅读 2015-01-06 14:25:47
    转自出处:... #include using namespace std; #define MAXSIZE 10//哈希链表 数组个数 当然可以适当的增加或者减少 ...2.解决地址冲突 本例用链表解决冲突即闭
  • ① 我们知道链表建立的头插中的元素顺序与原来的插入的顺序是相反的,所以我们可以将链表L中的元素作为逆转后L的元素来源,即将L->next设置为空,然后将头结点后的一串节点使用头插逐个插入到L中,这样新的L...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 63,678
精华内容 25,471
关键字:

成组链表法