目录实现
标签: 操作系统
学习人数: 5484

目录实现的基本方法有线性列表和哈希表两种。

 

1.线性列表

最简单的目录实现方法是使用存储文件名和数据块指针的线性表。创建新文件时,必须首先搜索目录表以确定没有同名的文件存在,然后在目录表后增加一个目录项。若删除文件则根据给定的文件名搜索目录表,接着释放分配给它的空间。若要重用目录项,有许多方法: 可以将目录项标记为不再使用,或者将它加到空闲目录项表上,还可以将目录表中最后一个目录项复制到空闲位置,并降低目录表长度。釆用链表结构可以减少删除文件的时间。其优点在于实现简单,不过由于线性表需要采用顺序方法查找特定的项,比较费时。

 

2.哈希表(散列表)

哈希表根据文件名得到一个值,并返回一个指向线性列表中元素的指针。这种方法的优点是查找非常迅速,插入和删除也较简单,不过需要一些预备措施来避免冲突。这种方法的特点是哈希表长度固定以及哈希函数对表长的依赖性。

 



课后作业


登录后发布评论

暂无评论,来抢沙发