基本数据结构

（1）栈和队列

     栈：主要作用表现为一种数据结构，是只能在某一端插入和删除的特殊线性表。它按照后进先出的原则存储数据，先进入的数据被压入栈底，最后的数据在栈顶，需要读数据的时候从栈顶开始弹出数据（最后一个数据被第一个读出来）。

     栈的java实现代码：http://shaojiashuai123456.iteye.com/admin/blogs/1426428

 

    队列：

    队列是一种特殊的线性表，它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作。进行插入操作的端称为队尾，进行删除操作的端称为队头。队列中没有元素时，称为空队列。

（2）链表

      链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。 相比于线性表顺序结构，链表比较方便插入和删除操作。

    链表分为单链表和双链表，现在linux2.6内核中使用了更为高效的链表方式，传统节点为：

      struct element

      {

                struct element  *pre;

                 struct element  *next;

                 void                   *value;

      };

      内核中使用：

     

      struct element

      {

                struct element  *pre;

                 struct element  **next;

                 void                   *value;

      };

    

     链表实现c语言代码：http://shaojiashuai123456.iteye.com/admin/blogs/1415886

 

（3）散列表

    

（4）二叉树查找树

 

       二叉排序树（Binary Sort Tree）又称二叉查找树。 它或者是一棵空树；或者是具有下列性质的二叉树：

        1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值；

        2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值；

        3）左、右子树也分别为二叉排序树；

 

       二叉查找树删除最为复杂，因此在此详细介绍下删除，删除三种类型如下图：

     

 

      (1)第一种情况如图a），要删除的节点左右子树都为空，此时只要删除掉此节点即可。

      (2)第二种情况如图b)，只有右子树，此时只要删除掉此节点，并将此节点右子树返回给上层节点.（只有左子树情况同理）

      (3)第三章情况如图c)，既有左子树，又有右子树，这种情况最为复杂：

              我们删除的其实不是节点，而是节点中存储的数据，所以替换数据也就是删除，所以在这种情况下我们采用替换数据的方式来解决。

              选取替换的数据有两种方法，一是在左子树中找到最大的数据，二是在右子树中找到最大的数据，只有这样的数据才能保证还是排序树。

              步骤如下：

                    1） 需要找到左子树中最大的数
                    2）替换到要删除的值
                    3）然后在左子树中删除最大的节点
                    4）返回节点

               二叉查找树c语言实现代码：http://shaojiashuai123456.iteye.com/admin/blogs/1426432

               二叉查找树java语言实现代码： http://shaojiashuai123456.iteye.com/admin/blogs/1430098

 

（5）红黑树

 

红黑树由来：

      他是在1972年 由Rudolf Bayer发明的，他称之为“对称二叉B树”，它现代的名字是Leo J. Guibas和 Robert Sedgewick 于1978年写的一篇论文中获得的。它是复杂的，但它的操作有着良好的最坏情况运行时间，并且在实践中是高效的: 它可以在O(log n)时间内做查找，

      插入和删除，这里的n 是树中元素的数目。

 

红黑树性质：

     1. 每个结点或红或黑。

 

     2. 根结点为黑色。

     3. 每个叶结点(实际上就是NULL指针)都是黑色的。

     4. 如果一个结点是红色的,那么它的周边3个节点都是黑色的。

     5. 对于每个结点,从该结点到其所有子孙叶结点的路径中所包含的黑色结点个数都一样。 

 

     红黑树原理详解（上）：   http://hi.baidu.com/20065562/blog/item/93b2d17fd6f391320dd7da44.html

     红黑树原理详解（下）：   http://hi.baidu.com/20065562/blog/item/8777467e5292f30229388a0f.html

 

（6）字典树

      又称单词查找树，Trie树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：利用字符串的公共前缀来节约存储空间，最大限度地减少无谓的字符串比较，查询效率比哈希表高。

      字典树c语言实现代码： http://shaojiashuai123456.iteye.com/admin/blogs/1471945

      

 （6）B树，B+树,B-树

       

 

      B树，B+树，B-树，R树 ： http://blog.csdn.net/v_JULY_v/article/details/6530142