C數據結構

是否有一個C數據結構可以等同於下面的python結構？C數據結構

data = {'X': 1, 'Y': 2}

基本上我想要一個結構，我可以給它一個預先定義的字符串，並讓它出來一個整數。

來源

2010-09-16 rectangletangle

你說的字符串，但你的例子只是字符。如果你真的只需要字符（並且你知道它們不會是多字節字符），則數組是最簡單和最快速的方法。 – 2010-09-16 03:05:16

@R ..：我相信這是他的Python代碼的例子。在Python中，「'和」「完全相同，即聲明一個字符串，而不是一個字符。 – 2010-09-16 03:08:49

我更感興趣的是它們都是單字符字符串而不是Python語法（我承認我對此一無所知）...... – 2010-09-16 03:14:29

您正在查找的數據結構稱爲「散列表」（或「散列圖」）。你可以找到一個here的源代碼。

哈希表是一個整數（通常從一個字符串派生）到另一個值的可變映射，就像您的示例代碼實例化的Python中的dict一樣。

它被稱爲「散列表」，因爲它對字符串執行hash function以返回整數結果，然後直接使用該整數指向所需數據的地址。

該系統使訪問和更改信息的速度非常快，即使您有大量信息。這也意味着數據是無序的，因爲散列函數會返回一致的隨機結果，並使數據在整個映射中處於不可預知狀態（在完美的世界中）。

來源

2010-09-16 02:35:02

示例代碼鏈接已損壞。 – new123456 2011-07-09 02:46:55

C沒有任何集合類。 C++有std :: map。

您可能會嘗試搜索地圖的C實現，例如， http://elliottback.com/wp/hashmap-implementation-in-c/

來源

2010-09-16 02:36:43

上述數據結構是字典類型。

在C/C++ paralance中，hashmap應該是等效的，Google適用於hashmap實現。

來源

2010-09-16 02:36:51 pyfunc

在C++ STL中，它被稱爲std :: map - 它不是基於散列的。 – martineau 2010-09-16 09:49:15

'trie'或'hasmap'應該做。最簡單的實現是一個struct {char * s; int i};對。

查看'include/nscript.h'和'src/trie.c'中的'trie'：http://github.com/nikki93/nscript。將'trie_info'類型更改爲'int'。

來源

2010-09-16 02:38:14 nikki

還要注意，如果你正在做一個快速的一次散列，就像一個查找的兩個或三個靜態散列：看gperf，它會生成一個完美的散列函數併爲該散列生成簡單的代碼。

來源

2010-09-16 02:48:58

語言或標準庫本身沒有任何內容，但根據您的要求，有很多方法可以做到這一點。

如果數據集將保持相對較小，最簡單的解決方案可能是隻具有結構線沿線的一個數組：

typedef struct { 
    char *key; 
    int val; 
} tElement;

然後使用順序搜索找一找。具有插入鍵，刪除鍵和查找鍵的功能，以便在將來需要更改時，API本身不會更改。僞代碼：

def init: 
    create g.key[100] as string 
    create g.val[100] as integer 
    set g.size to 0 
def add (key,val): 
    if lookup(key) != not_found: 
     return already_exists 
    if g.size == 100: 
     return no_space 
    g.key[g.size] = key 
    g.val[g.size] = val 
    g.size = g.size + 1 
    return okay 
def del (key): 
    pos = lookup (key) 
    if pos == not_found: 
     return no_such_key 
    if pos < g.size - 1: 
     g.key[pos] = g.key[g.size-1] 
     g.val[pos] = g.val[g.size-1] 
    g.size = g.size - 1 
def find (key): 
    for pos goes from 0 to g.size-1: 
     if g.key[pos] == key: 
      return pos 
    return not_found

插入意味着確保它不存在，然後只是套結的元素結束（你會保持結構的單獨尺寸可變的）。刪除意味着找到元素，然後簡單地用最後使用的元素覆蓋它並減小尺寸變量。

現在這不是世界上最高效的方法，但您需要記住，它通常只會隨着您的數據集變得更大而產生差異。二叉樹或散列與順序搜索之間的區別與20個條目無關。我甚至對小數據集使用冒泡排序，因爲其中更高效的數據集不可用。這是因爲它大量快速編碼，性能無關緊要。

從這裏開始，您可以使用鏈接列表刪除固定的大小。由於您按順序執行搜索，所以搜索仍然效率較低，但是與上述數組解決方案相同的注意事項適用。刪除上限對於插入和刪除來說是輕微的代價。

如果您想要更多的性能和非固定的上限，可以使用二叉樹來存儲元素。這在查找鍵時擺脫了順序搜索，適用於較大的數據集。

如果你不知道如何大數據集將得到，我會認爲這是絕對極小值。

散列可能是從那裏開始的下一步。這對字符串執行一個函數來獲取一個桶號（通常被當作某種數組索引）。這是O（1）查找，但目標是擁有一個散列函數，每個存儲桶只分配一個項目，因此不需要進一步處理即可獲取該值。

「同一個存儲桶中的所有項目」的退化情況與數組或鏈接列表沒有區別。

爲了獲得最佳性能，並假設鍵是固定的，預先知道，您可以根據自己的鑰匙實際上創建自己的哈希函數。

預先了解密鑰，您可以獲得額外的信息，使您可以完全優化哈希函數以生成實際值，因此您甚至不需要使用分組 - 哈希函數生成的值可以是所需的值本身而不是從中獲取價值。

爲了將文本月份（「1月」等）轉換爲月份數，我不得不將其中的一個放在一起。您可以看到流程here。

由於您的「預定義字符串」評論，我提到了這種可能性。如果你的密鑰限制爲"X"和"Y"（如你的例子），並且你正在使用一個連續的{W,X,Y}字符的字符集（它甚至覆蓋了EBCDIC以及ASCII，但不一定是ISO允許的每個深奧字符集），但最簡單的散列函數將是：

char *s = "X"; 
int val = *s - 'W';

請注意，如果您向其提供了錯誤的數據，則此功能無法正常工作。這些對於數據已知僅限於某些值的情況非常理想。檢查數據的成本往往可以彌補這種預先優化的散列函數的節省。

來源

2010-09-16 03:02:24 paxdiablo

嘗試使用字符串或某種類型的樹作爲整數/指針類型（或可比較爲「小於」或「大於」另一個鍵的任何東西）。維基百科在這兩方面都有相當不錯的文章，並且可以用C語言實現。

來源

2010-09-16 04:42:37

回答

相關問題