Tanky WooRSS

《算法导论》学习总结 — 10. 第10章(略) && 第11章 散列表

29 Apr 2011
这篇博客是从旧博客 WordPress 迁移过来,内容可能存在转换异常。

建议先看看前言:http://www.wutianqi.com/?p=2298

第10章没法说,数据结构还是看严奶奶的比较好,所以《算法导论》上的这一章我随便瞄了几眼就过去了,不过话说回来,数据结构非常重要!!!所以,大家最好把严蔚敏的《数据结构》认认真真的看N遍!!!

另外,推荐看看这个:

数据结构的源码实现:http://www.cppleyuan.com/viewthread.php?tid=418

第11章散列表也属于数据结构方面的知识,第10章只是讲了最基本的几个结构。这一章也很简单,其实就是介绍了一些概念及思想,很容易理解。(你可以把散列表想象成平时用的英语字典,26个英文字母就是下标,通过它来定位你要查的单词。)

所以这一章我就不重复去打出概念了,我把几个散列函数和处理碰撞的方法放在图表里方便对比。

①.散列表的优点:出色的期望性能。

②.引出:

直接寻址表(P132)的缺点:

1.全域U也许会很大。

2.实际关键字域K也许相对于U会很小。

由此引出了散列表。

以下是我总结对比的表:

sanlie1

sanlie4

这一章我也不知道该怎么说,表面上感觉比较简单,但是如果深入研究,会发现它的内容太多了,而且很好很强大。所以还是建议大家看看书也许以后深入了解了我会再补充。

Tanky Woo 标签: 散列表hash table