当前位置:首页 > 开发 > 编程语言 > 编程 > 正文

关联数组(associative array)

发表于: 2011-07-16   作者:codePrac   来源:转载   浏览:
摘要:    关联数组(associative array )是一种常用的抽象数据类型。它有很多别名,例如associative container , map , mapping , dictionary , finite map , table,index 等。它的特点是由一个关键字和其他各种属性组成的集合。典型的操作包括插入,删除和查找等。而用于描述关联数组最常用的是哈希表 (h

   关联数组(associative array )是一种常用的抽象数据类型。它有很多别名,例如associative container , map , mapping , dictionary , finite map , table,index 等。它的特点是由一个关键字和其他各种属性组成的集合。典型的操作包括插入,删除和查找等。而用于描述关联数组最常用的是哈希表hash table )和自平衡二叉搜索树(self-balanced binary search tree )(包括红黑树red-black tree )和avl树avl tree ),有时可能使用B-tree (适用于关联数组太大的情况,比如数据库等))。哈希表和自平衡二叉搜索树的性能对比如下:平均情况下哈希表的查找和插入操作的复杂度为O(1),而自平 衡二叉搜索树的查找和插入操作的复杂度为O(log(n))。而最坏情况下平衡二叉搜索树的查找和插入操作的复杂度仍为O(log(n)),而哈希表的查 找和插入操作的复杂度可能达到O(n)。

   相关链接直接参考维基百科中内容即可,另有一篇中文的文章也不错,链接:

   红黑树的介绍和实现

   由于c语言标准库中缺乏对各种抽象数据类型的支持,c语言下对各种抽象数据类型的操作比较麻烦,从网上找了一些C语言的数据结构库,感兴趣的可以看看:

   GDSL

   GNUlib

   sglib

   attractive chaos 's klib

   c-geniric-library

   cbase

   libwayne

   uthash (hash table)

   ccan

关联数组(associative array)

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号