?? 關(guān)聯(lián)數(shù)組（associative array )是一種常用的抽象數(shù)據(jù)類型。它有很多別名，例如associative container , map , mapping , dictionary , finite map , table,index 等。它的特點(diǎn)是由一個(gè)關(guān)鍵字和其他各種屬性組成的集合。典型的操作包括插入，刪除和查找等。而用于描述關(guān)聯(lián)數(shù)組最常用的是哈希表 （hash table ）和自平衡二叉搜索樹(shù)（self-balanced binary search tree )(包括紅黑樹(shù) （red-black tree ）和avl樹(shù) （avl tree ），有時(shí)可能使用B-tree (適用于關(guān)聯(lián)數(shù)組太大的情況，比如數(shù)據(jù)庫(kù)等））。哈希表和自平衡二叉搜索樹(shù)的性能對(duì)比如下：平均情況下哈希表的查找和插入操作的復(fù)雜度為O（1），而自平 衡二叉搜索樹(shù)的查找和插入操作的復(fù)雜度為O（log(n))。而最壞情況下平衡二叉搜索樹(shù)的查找和插入操作的復(fù)雜度仍為O(log(n))，而哈希表的查 找和插入操作的復(fù)雜度可能達(dá)到O（n）。

?? 相關(guān)鏈接直接參考維基百科中內(nèi)容即可，另有一篇中文的文章也不錯(cuò)，鏈接：

?? 紅黑樹(shù)的介紹和實(shí)現(xiàn)

?? 由于c語(yǔ)言標(biāo)準(zhǔn)庫(kù)中缺乏對(duì)各種抽象數(shù)據(jù)類型的支持，c語(yǔ)言下對(duì)各種抽象數(shù)據(jù)類型的操作比較麻煩，從網(wǎng)上找了一些C語(yǔ)言的數(shù)據(jù)結(jié)構(gòu)庫(kù)，感興趣的可以看看：

?? GDSL

?? GNUlib

?? sglib

?? attractive chaos 's klib

?? c-geniric-library

?? cbase

?? libwayne

?? uthash （hash table）

?? ccan

總結(jié)

以上是生活随笔為你收集整理的关联数组（associative array)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。