Re: [問題] 演算法
> ==>發信人: MasterChang.bbs@ptt.cc (我愛ASM), 信區: programming
> ※ 引述《haryewkun (Har)》之銘言：
> : 換題目玩玩。
> : 如果我們不要走漏洞，而是真的當作是實用的情況，然後把題目修改一點，
> : 必須要找出最小、而又沒有被使用的數字，那麼除了排序之外，還有沒有其
> : 他更快捷的方法？
> : 討論區真的有這個問題。就是十萬個用戶，注冊了從 1到100000的 UID，然
> : 後版主刪掉中間五萬名會員，所以就零零散散地斷層了。如果新用戶注冊，
> : 就必須用 100001 的UID。
> : 如果是這樣的問題，除了排序之外，還有沒有別的辦法？
> 假設UID為1~100,000，沒有比100,000 更高的狀況了。有沒有辦法
> 在不用排序的狀況下知道哪些是空的 UID？或是一開始就維護一個
> 有序的UID，包含使用中的UID及未使用的UID？
> 維護兩個資料結構，一個使用中並已序之UID ，一個為未使用並已
> 序之UID ，兩者長度總和可透過共用區塊維護。(此例總長為100,000，
> 並假設不會增加了...就算增加也是比照辦理)
> 這樣可行嗎？I don't know. 不過因為資料結構為已序，所以未使
> 用之UID不用排序就可以馬上知道。
======
Disk Block number 就是 數字編號
File Allocation Table , 那個 file 就是由那些 block member 組成,
撥給空位 取回空位 就是 disk block allocation.
假如 一個 file (如 人名) 限使用一個 block (如 member 代號) 就是
上面要的狀況.
已知最常用的就是 UNIX 用的方法 index table 與 allocation-bit-map
分離, 其次就是 IBM-PC FAT , index-list 與 allocation array map
合用.
當然, 檔案比較像是 group name 由很多單一 member block number 集合
而成, 這個例是一個檔案(名稱)只佔用單一的 block number.
先參考這些 "舊輪胎" 吧 !
--
◎ Origin: 中央松濤站□bbs.csie.ncu.edu.tw From: 140.115.6.234
討論串 (同標題文章)