爲多級遍歷數據結構

我具有與在下面的結構的數據涉及的應用程序：爲多級遍歷數據結構

struct Message 
{ 
    int time; 
    string name; 
    string details; 
};

例如，我可以具有數據集如下所示：

9:00:00 Bob <Info> 
9:01:00 John <Info> 
9:05:00 Bob <Info> 
9:11:00 Mary <Info> 
9:17:00 John <Info> 
9:25:00 Mary <Info> 
9:30:00 Bob <Info>

而且我將列出代表數據集中每行的Message結構。

有些操作我需要在這個數據確實包括：

收集的所有數據按照時間順序和dostuff()
從時間順序John（或任何人），並dostuff()

收集所有數據

因此，我需要一種遍歷列表的方式，以便我可以按時間順序傳遞每封郵件，並且還可以選擇一個人，並按照時間順序僅傳遞其郵件。

我的想法是有這樣的結構：

struct Node 
{ 
    Message* message; 
    Node* next_time; 
    Node* next_name; 
};

在這next_time點，按時間順序排列的下一個Node，並且next_name分屬於message->name下一個Node。一個Root結構指向每種類型的第一個。

struct Root 
{ 
    Node* first_time; 
    Node* first_bob; 
    Node* first_john; 
    Node* first_mary; 

    Node* last_time; 
    Node* last_bob; 
    Node* last_john; 
    Node* last_mary; 
};

這是一張圖片來說明這一點。

enter image description here

這種結構可以讓我的每封郵件很容易穿越的，或只通過Bob的郵件，或者只約翰等

不過，我很擔心，也許這是比它更復雜需要是。我也擔心維護（見下文）。我需要搜索/選擇/讀取操作非常快，我認爲他們是。我需要插入操作相當快。但是現在，我插入每個Message，我必須（1）更新一些next_time指針和（2）更新一些next_name指針。

我的問題是：是否存在提供此類功能的數據結構？如果沒有，我是否正確接近這個問題？

請儘可能在C++或C＃中提供任何代碼示例。

謝謝。

附加：稍後假設我想添加到我的Message結構中。假設我添加一個名爲City的字段。現在，我可能要做到這一點：

從時間順序，在特定City和dostuff()

收集所有數據。這將需要新增一個next_city，然後每次插入，我將不得不更新next_time,next_name和next_city。

此外，假設我要做到這一點：

從特定City和時間順序，在特定name和dostuff()

我認爲這使得問題令人難以置信更難收集所有數據除非我選擇遍歷每個Message並跳過我不關心的那些。

來源

2011-08-02 user807566

多少不同的用戶會有嗎？如果這個數字很小，那麼只需跳過你不感興趣的郵件就可以逃脫。 – takteek

@takteek：我想過 - 人數/用戶/名稱是任意的，並且會有點小，但每個人的「消息」數量將非常大。有可能我會跳過大量的'Messages' – user807566

你需要高效的隨機插入還是隻需追加？ –

所有消息的簡單鏈接列表（按時間排序）。

struct Node 
{ 
    Message* message; 
    Node* next_name; 
};

這將滿足REQ 1.您可以在O add（）和GETALL（）（1）

使用用戶的關鍵和作爲值節點*的列表的單獨的散列映射。

Hashmap 
{key = User, value = List(Message*)}

這將滿足REQ 2.您可以將新條目添加到特定用戶的O列表的末尾（1）和getAllOfUser（）也可以在O（1）運行

來源

2011-08-02 01:56:28 naren

我可能會創建一個類來表示一個用戶，通過一些標識符（如名稱）將用戶存儲在一個哈希表中，然後讓每個用戶按時間順序存放一個列表，這些列表也存儲在一個單獨的全球列表，它按時間順序包含每個人的Message。對於每個添加的Message，您都必須在每個列表中插入一次（按列表我的意思是某個集合），這可能是log n時間，或者不如n，具體取決於數據結構。

來源

2011-08-02 01:49:06

爲多級遍歷數據結構

回答

相關問題