随笔-19  评论-21  文章-0  trackbacks-0
 要找工作了,终于觉得是时候总结一下数据结构了(ps: 对于数组,链表这样简单常用的结构就不总结了,此文会持续更新),总结有助于更好地思考。

1. 位图
    位图的威力可以在<编程珠玑>的开头就体会到。另外在Find an integer not among four billion given ones中的运用也很精彩。

2. 堆
   在<编程珠玑>里重点运用了该结构,直接导致我以后经常想到并使用该结构。
   不得不说,它真的很有用,如:找N个数中最大/最小的k个数。
   实现优先级队列时也有用。

3. 树
     二叉搜索树:是一个很容易就能想到的结构,只要让一棵二叉树满足以下一个特性就可以了:对于任一结点N,其左子树结点left满足key(x) <= key(N),其右子树结点right满足key(y) >= key(N),其优点是操作简单,缺点是插入,删除结点的复杂度高,为O(N)
     二叉搜索树复杂度高的原因为:树的高度不确定/不稳定,有可能为n,所以问题的关键是:如何控制树的高度
     很多人灵机一动:产生了一系列平衡二叉树,如:AVL树,Red-Black树,Treap
     也产生了很多平衡二叉树的变种,如:Weight balanced tree,k-neighbor tree等
     Skip List 也是平衡二叉树之外的另一种选择
     Trie树 用来存储一个字典,然后用来查找某个字符串还是很方便的(A trie can be seen as a deterministic finite automaton.) 另外可以看看Suffix_tree后缀树。

4. hash
    hash的两个关键点在于:a. hash桶大小的设定(一般为一个素数) b. 冲突处理机制,如可以用一个链表处理hash值相同的元素。
    我很少考虑hash,觉得复杂度不好把握。以后倒是可以考虑用用,如:在问题“判断两个链表是否相交”有可以使用hash;“判断链表有没有环”用hash也很给力。
posted on 2011-08-24 20:15 hex108 阅读(303) 评论(0)  编辑 收藏 引用 所属分类: Algorithm

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理