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

回答

相关问题