group.jpg 

看到很多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)就好了


arrow
arrow
    全站熱搜

    finalfrank 發表在 痞客邦 留言(2) 人氣()