数据结构一二三

俗语讲书到用时方恨少，真正感觉数据结构知识不够用时在看yaffs代码的时候，在那之前写的单片机程序基本上使用数组、链表就够用了。

适当需要的时候，选择适当的数据结构。前提是要对数据结构很熟悉。

数组应用：在AD7705采集数据的FIFO、串口通讯的FIFO都是使用循环数据实现。
链表应用：uCosII中大部分内核数据结构都是以链表的形式来组织。
表驱动法应用：uCosII查找最高优先级任务的算法、RTC S390A驱动中BCD与HEX的转换。

二分法和hash应用：
floating做汉王录音电话项目时，让我写了一个二分法查找的函数。后来但电话记录到达几万条的时候，这个二分法查成了性能上的一个瓶颈。
后来floating和我相继离职的时候，这个问题还没有得到解决。不知道汉王这个项目最后怎么样了。
如果但是使用hash表重新设计查找算法的话，性能应该可以到达汉王要求的性能。
CPRM算法中也使用了大量的hash算法，不过当时是yoyo同学负责，而我主要的精力在做SD卡驱动没有太多的关注。

AVL树应用：
AVL最大的优势在于查找速度非常快。haiyang在做zigbee时采用树型网络，应该就是类AVL树。
通过巧妙的算法分配节点的，使得可以通过计算得到目标节点的路径。这种树型网络比网状网络实现起来简单很多。

二叉堆应用：
二叉堆的堆序性只要求父节点关键字值不大于子节点，没有AVL树那么严格。插入、删除操作比AVL数要方便。
举个例子：
我们使用二叉堆设计一个基于优先级的调度算法--关键字就是优先级。我们开看下几种操作的实现方法。
查找最小(高)优先级的任务--根节点关键字值最小，直接返回根节点就是。
令一个任务进入就绪状态--将该任务插入到二叉堆中。
删除一个任务--将该任务从二叉堆中删除
令一个任务进入睡眠状态--将该任务关键字值提升到到比IDLE任务还大。

未完，待续...