关联数组（associative array)

   关联数组（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