看到很多GUI繪圖軟體,都有提供「群組化」的功能
(也就是把很多個物件當作一個物件處理,當使用者點選群組中的某一個物件時,和他同一組的物件同時會被點選)
這時會很好奇是怎麼做的
有一些構思分享一下
構思1. 製作一個「群組表」的方法
所謂群組表的話呢,就是說「表1」包含了幾個物件,「表2」包含了幾個物件
資料結構像是這樣
[群組的頭] [ 該群組元件 ]
┌───┬─┐ ┌───┬─┐
│ 1 │●┼─> │ 2 │●┼─> N U L L
├───┴─┤ └───┴─┘
│ ● │
└──┼──┘
\/
┌───┬─┐
│ 2 │●┼─> N U L L (該群組沒有東西)
├───┴─┤
│ ● │
└──┼──┘
\/ [ 該群組元件 ] [ 該群組元件 ]
┌───┬─┐ ┌───┬─┐ ┌───┬─┐
│ 3 │●┼─> │ 7 │●┼─> │ 16 │●┼─> N U L L
├───┴─┤ └───┴─┘ └───┴─┘
│ ● │
└──┼──┘
\/
NULL
設計很直覺,但是這樣設計有問題
例如,你的滑鼠點選了上圖的「2」物件,
電腦怎麼知道,他究竟存在哪一個群組?
就算可以一個一個去巡,也要花很多時間,
程式撰寫也麻煩
構思2. 每一個物件都有一個所屬的群組
為了解決構思 1 的問題
我們乾脆倒過來想
就是讓每一個物件都有所屬群組,
你只要問一個物件「你是屬於哪個群組的?」
物件可以馬上回答「我是屬於X號群組的!」
資料結構像是這樣 (從構思1使用的範例轉過來)
┌───┬──┐
│ 2 │ 1 │
├───┼──┤
│ 7 │ 3 │
├───┼──┤
│ 16 │ 3 │
└───┴──┘
如此一來又省空間,又好表達
那如果有一個物件不屬於任何群組呢?
其實也不難,就把他標記群組為-1就好
而搜尋同群組的所有物件的時間也很短
只需要Linear Probing,用O(n)就好了
留言列表