2013-03-13 63 views
0

我有一個類似的樹數據找到了樹的葉子:如何從平面數據

[0] => 
     id = 5, 
     name = "TV", 
     parent_id = 1, 
     children => 
        [0] => 
         id = 6, 
         name = "PLASMA", 
         parent_id = 5, 
         children = null 
        [1] => 
         id = 7, 
         name = "LCD", 
         parent_id = 5, 
         children => 
            [0] => 
              id = 8, 
              name = "Gloss", 
              parent_id = 7, 
              children = null 
            [1] => 
              id = 9, 
              name = "Matte", 
              parent_id = 7, 
              children = null 
[1] => 
     id = 4, 
     name = "Printers", 
     parent_id = 1, 
     children => 
       .... 

而且我有一個平坦的字符串數據,如:

  • 電視
  • TV_PLASMA_Gloss
  • TV_LCD

'_'是一個subc的分隔符ategory。

什麼是尋找類別ID數組的最佳算法?

示例輸入:

  1. 電視
  2. TV_PLASMA_Gloss
  3. TV_LCD

輸出示例:

  1. 陣列:5
  2. 陣列:5,6,8
  3. 陣列:5,7

語言並不重要 - 它只是一個算法 - 但在這種情況下,我會選擇C#。

謝謝。

回答

0

使用HashMapDictionary<string, int>在這種情況下可以),遍歷樹並添加(name,id)對到HashMap。

對於您在輸入字符串和散列映射中傳遞的任何輸入。

  • 分割字符串的分隔符,在這種情況下「_」(input.Split(new char[]{'_'})
  • 對於每個弦形部分,查找其ID在HashMap中,並把它添加到一個輸出串或陣列

*

public int[] GetIDsFromString(string input, Dictionary<string, int> lookup) 
{ 
    string stringParts = input.Split(new char[]{'_'}); 
    int[] retval = new int[stringParts.Length]; 
    int retIndex = 0; 
    foreach(var s in stringParts) 
    if (lookup.contains(s)) 
     retval[retIndex++] = lookup[s]; 
    else 
     throw new Exception(string.format("string contained invalid item {0}", s)); 
    return retval; 
} 
0

使用字典的ID的(反向)查找相關的名稱

Dictionary<string,int> ids = new Dictionary<string,int>(); 
ids.Add("TV", 5); 
ids.Add("PLASMA", 6); 
// And so on 

現在,仰視IDS

string input = "TV_PLASMA_Gloss"; 
string[] categories = input.Split('_'); 
int[] result = new int[categories.Length]; 
for (int i = 0; i < categories.Length; i++) { 
    int id; 
    if (ids.TryGetValue(categories[i], out id)) { 
     result[i] = id; 
    } else { 
     result[i] = -1; // Unknown category 
    } 
} 
0

那一路前拆分輸入字符串,我會用遞歸做到這一點:

定義一個函數,該函數的字符串數組和你的結構/對象數組或其他。 字符串數組調用函數之前解析:

string = "TV_PLASMA_Gloss" 
array[0] = "TV" 
array[1] = "PLASMA" 
array[2] = "Gloss" 

數組中的第一串將針對所有的「頂層」的條目進行測試。如果有匹配的條目,則將使用剩餘的數組和匹配的條目再次調用該函數。

如果數組中只剩下一個字符串,我們返回找到的條目的ID。這樣我們就可以繼續遞歸調用並構建我們想要的整數id數組。

調用層次結構將類似於:

-> function({"TV","PLASMA","Gloss"}, entry) 
    -> function({"PLASMA","Gloss"}, matched_entry) 
     -> function({"Gloss"}, matched_entry) 
     <- id = 8 
    <- id = 6,8 
<- id = 5,6,8