常见数据结构的总结

数据结构：

———————————————————————————————————————————————————

单链表：链表：使用节点存储数据元素，节点的地址可以连续也可以不连续

单链表中一个节点的组成：数据域+指针域，指针于中存放的是是一个指针，指向下一个节点的地址。

双链表即双向链表

链表中每个节点有两个指针，分别指向节点的直接前驱和直接后躯。

特点：从双链表的任一节点开始，都可以非常方便的访问他的前驱节点和后继节点。这也是单链表的缺点，单链表可以方便的访问某一节点的后继节点，但没法访问他的前驱节点。
双链表的定义及其操作于单链表类似，要注意的就是每个节点的两个指针域。

当链表的每个结点只包含一个指针域时，我们称此链表为单链表。
关于单链表的存取，有时候我们在单链表的第一个结点（有效元素）之前附设一个结点，称之为头结点；指向头结点的指针，称之为头指针；对单链表的存取必须从头指针开始进行，由于单链表的最后一个数据元素没有直接后继，则指针为NULL。

则定义LinkList L;时，L为链表的头指针。

此处返回给L的是一个指针，并且赋给了头指针。

小结关于头指针：

● 在线性表的链式存储结构中，头指针是指链表指向第一个结点的指针，若链表有头结点，则头指针就是指向链表头结点的指针。
● 头指针具有标识作用，故常用头指针冠以链表的名字。
● 无论链表是否为空，头指针均不为空。头指针是链表的必要元素。
关于头结点：
● 头结点是为了操作的统一与方便而设立的，放在第一个元素结点之前，其数据域一般无意义（当然有些情况下也可存放链表的长度、用做监视哨等等）。
● 有了头结点后，对在第一个元素结点前插入结点和删除第一个结点，其操作与对其它结点的操作统一了。
● 首元结点也就是第一个元素的结点，它是头结点后边的第一个结点。
● 头结点不是链表所必需的。

头指针比头节点方便 节省内存
头节点的data域可以用来保存链表的一些信息 比如长度

头指针方便操作链表，是必须的。
头结点可有可无，如果有，则使得链表开始结点的删除更加方便并统一了删除结点的方式；如果没有，反之。

———————————————————————————————————————————————————

栈

一种只允许在一端进行插入和删除的线性表。向栈中插入元素叫进栈，从栈中删除数据元素叫出栈。
栈有顺序存储和链式存储，顺序存储需要事先分配栈的内存空间。

栈是一种单链表，但跟单链表不同的是，对栈的操作只需要栈顶即可，即不需要访问栈中其他位置。
1.栈的初始化：将栈顶指针置为NULL
2.判断栈是否为空：查看栈顶指针是否为空，而不是查看栈顶是否为空。
3.进栈：进栈时栈顶指针后移，怎么理解呢栈顶不变，将要入栈的节点放在栈顶下面，即栈顶指针只想入栈的节点，每次进栈时都放在栈的最上面。
4.出栈：栈顶指针前移。就是将栈顶下面的节点删除掉，每次出栈都将栈最上面的节点删除掉。
注：出栈时要将出栈的那块内存空间释放掉，最后，将栈清空后，还要将栈顶的内存空间也释放掉。
———————————————————————————————————————————————————

队列

先进先出的线性表，它只允许在一端(队尾)进行插入操作，在另一端（队首）进行删除操作。与栈的插入和删除都在栈顶进行不同。

1.队列定义：这里除了定义队列中节点的数据结构，还专门定义了队首和队尾，方便对队列操作，这样一来，队列的操作就只需要对pointer结构体中的对手指真和队尾指针进行。
2.判断是否为空
当队首指针和队尾指针只想同一块地址时，队列为空，队列为空就是说队列中没有数据元素。注意队首front只是队列的头结点，并不代表队列的实际队首，在队列不为空时，队列的实际队首应该是头结点的下一个节点。
3.插入数据元素
插入在队尾进行，插入后，新插入的节点就成为了队尾。
4.删除数据元素
删除在队首进行，需要注意的是，当实际的队首也是队尾时，删除队列中的一个数据后队列就成为了空队列（rear=front）。最后不要忘了将删除的数据的内存空间释放掉。

循环队列

队列的顺序存储就是所谓的循环队列，队列的顺序存储导致实际空间还剩余，但数据已存储到数组的末尾，故采用首尾相连的方法，这样解决了空间不足的问题
如果使用顺序表作为队列的话，当处于右图状态则不能继续插入新的队尾元素，否则会因为数组越界而导致程序代码被破坏。

B+的特性：

1).所有关键字都出现在叶子结点的链表中（稠密索引），且链表中的关键字恰好是有序的；
2).不可能在非叶子结点命中；
3).非叶子结点相当于是叶子结点的索引（稀疏索引），叶子结点相当于是存储（关键字）数据的数据层；
4).更适合文件索引系统；

2.B+树的基本操作

1)查找操作

对B+树可以进行两种查找运算：
　　a.从最小关键字起顺序查找；
　　b.从根结点开始，进行随机查找。
在查找时，若非终端结点上的剧组机等于给定值，并不终止，而是继续向下直到叶子结点。因此，在B+树中，不管查找成功与否，每次查找都是走了一条从根到叶子结点的路径。其余同B-树的查找类似。

2).插入操作

B+树的插入与B树的插入过程类似。不同的是B+树在叶结点上进行，如果叶结点中的关键码个数超过m，就必须分裂成关键码数目大致相同的两个结点，并保证上层结点中有这两个结点的最大关键码。

3)删除操作

B+树的删除也仅在叶子结点进行，当叶子结点中的最大关键字被删除时，其在非终端结点中的值可以作为一个“分界关键字”存在。若因删除而使结点中关键字的个数少于m/2 （m/2结果取上界，如5/2结果为3）时，其和兄弟结点的合并过程亦和B-树类似。

PS:
a.不同于B+树只适合随机检索，B+树同时支持随机检索和顺序检索，在实际中应用比较多.
b.为什么说B+树比B 树更适合实际应用中操作系统的文件索引和数据库索引p>

1) B+树的磁盘读写代价更低

B+树的内部结点并没有指向关键字具体信息的指针。因此其内部结点相对B 树更小。如果把所有同一内部结点的关键字存放在同一盘块中，那么盘块所能容纳的关键字数量也越多。一次性读入内存中的需要查找的关键字也就越多。相对来说IO读写次数也就降低了。

举个例子，假设磁盘中的一个盘块容纳16bytes，而一个关键字2bytes，一个关键字具体信息指针2bytes。一棵9阶B-tree(一个结点最多8个关键字)的内部结点需要2个盘快。而B+树内部结点只需要1个盘快(全部关键字都在叶结点的缘故当需要把内部结点读入内存中的时候，B-树就比B+树多一次盘块查找时间(在磁盘中就是盘片旋转的时间)(B+树的内结点只有索引的作用，何来“把内部结点读入内存”…,对于B+树找到叶结点就可以，另外B+树可以顺序查找)。

2) B+树的查询效率更加稳定

由于非终结点并不是最终指向文件内容的结点，而只是叶子结点中关键字的索引。所以任何关键字的查找必须走一条从根结点到叶子结点的路。所有关键字查询的路径长度相同，导致每一个数据的查询效率相当。

B+树和B-树最大的不同点是：

1).B-树的关键字和记录是放在一起的，叶子节点可以看作外部节点，不包含任何信息；B+树的非叶子节点中只有关键字和指向下一个节点的索引，记录只放在叶子节点中。

2).在B-树中，越靠近根节点的记录查找时间越快，只要找到关键字即可确定记录的存在；而B+树中每个记录的查找时间基本是一样的，都需要从根节点走到叶子节点，而且在叶子节点中还要再比较关键字。从这个角度看B-树的性能好像要比B+树好，而在实际应用中却是B+树的性能要好些。因为B+树的非叶子节点不存放实际的数据，这样每个节点可容纳的元素个数比B-树多，树高比B-树小，这样带来的好处是减少磁盘访问次数。尽管B+树找到一个记录所需的比较次数要比B-树多，但是一次磁盘访问的时间相当于成百上千次内存比较的时间，因此实际中B+树的性能可能还会好些，而且B+树的叶子节点使用指针连接在一起，方便顺序遍历(例如查看一个目录下的所有文件，一个表中的所有记录等)，这也是很多数据库和文件系统使用B+树的缘故。

B*树 (这个 上介绍的甚少，教科书我也没有找到细致的介绍)

B*Tree是B+树的变体，在B+Tree的非根和非叶子结点(内结点)再增加指向兄弟的指针

trie 中的键通常是字符串，但也可以是其它的结构。trie 的算法可以很容易地修改为处理其它结构的有序序列，比如一串数字或者形状的排列。比如，bitwise trie 中的键是一串位元，可以用于表示整数或者内存地

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

字典树与字典很相似,当你要查一个单词是不是在字典树中,首先看单词的第一个字母是不是在字典的第一层,如果不在,说明字典树里没有该单词,如果在就在该字母的孩子节点里找是不是有单词的第二个字母,没有说明没有该单词,有的话用同样的方法继续查找.字典树不仅可以用来储存字母,也可以储存数字等其它数据。

相对来说,Trie树是一种比较简单的数据结构.理解起来比较简单,正所谓简单的东西也得付出代价.故Trie树也有它的缺点,Trie树的内存消耗非常大.当然,或许用左儿子右兄弟的方法建树的话,可能会好点.

其基本性质可以归纳为：

1. 根节点不包含字符，除根节点外每一个节点都只包含一个字符。
2. 从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串。
3. 每个节点的所有子节点包含的字符都不相同。

其基本操作有:查找 插入和删除,当然删除操作比较少见.我在这里只是实现了对整个树的删除操作,至于单个word的删除操作也很简单.

搜索字典项目的方法为：

(1) 从根结点开始一次搜索；
(2) 取得要查找关键词的第一个字母，并根据该字母选择对应的子树并转到该子树继续进行检索；
(3) 在相应的子树上，取得要查找关键词的第二个字母,并进一步选择对应的子树进行检索。
(4) 迭代过程……
(5) 在某个结点处，关键词的所有字母已被取出，则读取附在该结点上的信息，即完成查找。

———————————————————————————————————————————————————

hash表

1、定义

有时候也被称为散列表。个人认为，hash表是介于链表和二叉树之间的一种中间结构。链表使用十分方便，但是数据查找十分麻烦；二叉树中的数据严格有序，但是这是以多一个指针作为代价的结果。hash表既满足了数据的查找方便，同时不占用太多的内容空间，使用也十分方便。
打个比方来说，所有的数据就好像许许多多的书本。如果这些书本是一本一本堆起来的，就好像链表或者线性表一样，整个数据会显得非常的无序和凌乱，在你找到自己需要的书之前，你要经历许多的查询过程；而如果你对所有的书本进行编 ，并且把这些书本按次序进行排列的话，那么如果你要寻找的书本编 是n，那么经过二分查找，你很快就会找到自己需要的书本；但是如果你每一个种类的书本都不是很多，那么你就可以对这些书本进行归类，哪些是文学类，哪些是艺术类，哪些是工科的，哪些是理科的，你只要对这些书本进行简单的归类，那么寻找一本书也会变得非常简单，比如说如果你要找的书是计算机方面的书，那么你就会到工科一类当中去寻找，这样查找起来也会显得麻烦。

Hash表也称散列表，也有直接译作哈希表，Hash表是一种特殊的数据结构，它同数组、链表以及二叉排序树等相比较有很明显的区别，它能够快速定位到想要查找的记录，而不是与表中存在的记录的关键字进行比较来进行查找。这个源于Hash表设计的特殊性，它采用了函数映射的思想将记录的存储位置与记录的关键字关联起来，从而能够很快速地进行查找。

通常有以下几种构造Hash函数的方法：

1)直接定址法
　　取关键字或者关键字的某个线性函数为Hash地址，即address(key)=a*key+b;如知道学生的学 从2000开始，最大为4000，则可以将address(key)=key-2000作为Hash地址。
　　
2)平方取中法
　　对关键字进行平方运算，然后取结果的中间几位作为Hash地址。假如有以下关键字序列{421，423，436}，平方之后的结果为{177241，178929，190096}，那么可以取{72，89，00}作为Hash地址。
　　
3)折叠法
　　将关键字拆分成几部分，然后将这几部分组合在一起，以特定的方式进行转化形成Hash地址。假如知道图书的ISBN 为8903-241-23，可以将address(key)=89+03+24+12+3作为Hash地址。
　　
4)除留取余法
　　如果知道Hash表的最大长度为m，可以取不大于m的最大质数p，然后对关键字进行取余运算，address(key)=key%p。
　　在这里p的选取非常关键，p选择的好的话，能够最大程度地减少冲突，p一般取不大于m的最大质数。

2.Hash表大小的确定

Hash表大小的确定也非常关键，如果Hash表的空间远远大于最后实际存储的记录个数，则造成了很大的空间浪费，如果选取小了的话，则容易造成冲突。在实际情况中，一般需要根据最终记录存储个数和关键字的分布特点来确定Hash表的大小。还有一种情况时可能事先不知道最终需要存储的记录个数，则需要动态维护Hash表的容量，此时可能需要重新计算Hash地址。

3.冲突的解决

在上述例子中，发生了冲突现象，因此需要办法来解决，否则记录无法进行正确的存储。通常情况下有2种解决办法：

1)开放定址法
　　即当一个关键字和另一个关键字发生冲突时，使用某种探测技术在Hash表中形成一个探测序列，然后沿着这个探测序列依次查找下去，当碰到一个空的单元时，则插入其中。比较常用的探测方法有线性探测法，比如有一组关键字{12，13，25，23，38，34，6，84，91}，Hash表长为14，Hash函数为address(key)=key%11，当插入12，13，25时可以直接插入，而当插入23时，地址1被占用了，因此沿着地址1依次往下探测(探测步长可以根据情况而定)，直到探测到地址4，发现为空，则将23插入其中。

2)链地址法
　　采用数组和链表相结合的办法，将Hash地址相同的记录存储在一张线性表中，而每张表的表头的序 即为计算得到的Hash地址。如上述例子中，采用链地址法形成的Hash表存储表示为：

*当n较大，则应采用时间复杂度为O(nlog2n)的排序方法：快速排序、堆排序或归并排序序。
快速排序：是目前基于比较的内部排序中被认为是最好的方法，当待排序的关键字是随机分布时，快速排序的平均时间最短；
———————————————————————————————————————————————————

排序算法大体可分为两种：

一种是比较排序，时间复杂度O(nlogn) ~ O(n^2)，主要有：冒泡排序，选择排序，插入排序，归并排序，堆排序，快速排序等。

另一种是非比较排序，时间复杂度可以达到O(n)，主要有：计数排序，基数排序，桶排序等。
这里我们来探讨一下常用的比较排序算法，非比较排序算法将在下一篇文章中介绍。下表给出了常见比较排序算法的性能：

我们比较时间复杂度函数的情况：

时间复杂度来说：

(1)平方阶(O(n2))排序
　　各类简单排序:直接插入、直接选择和冒泡排序；
　　
(2)线性对数阶(O(nlog2n))排序
　　快速排序、堆排序和归并排序；
　　
(3)O(n1+§))排序,§是介于0和1之间的常数。
希尔排序

(4)线性阶(O(n))排序
　　基数排序，此外还有桶、箱排序。
　　
说明：
当原表有序或基本有序时，直接插入排序和冒泡排序将大大减少比较次数和移动记录的次数，时间复杂度可降至O（n）；
而快速排序则相反，当原表基本有序时，将蜕化为冒泡排序，时间复杂度提高为O（n2）；
原表是否有序，对简单选择排序、堆排序、归并排序和基数排序的时间复杂度影响不大。

稳定性：

排序算法的稳定性:若待排序的序列中，存在多个具有相同关键字的记录，经过排序， 这些记录的相对次序保持不变，则称该算法是稳定的；若经排序后，记录的相对 次序发生了改变，则称该算法是不稳定的。

稳定性的好处：排序算法如果是稳定的，那么从一个键上排序，然后再从另一个键上排序，第一个键排序的结果可以为第二个键排序所用。基数排序就是这样，先按低位排序，逐次按高位排序，低位相同的元素其顺序再高位也相同时是不会改变的。另外，如果排序算法稳定，可以避免多余的比较；

稳定的排序算法：冒泡排序、插入排序、归并排序和基数排序

不是稳定的排序算法：选择排序、快速排序、希尔排序、堆排序

选择排序算法准则：

每种排序算法都各有优缺点。因此，在实用时需根据不同情况适当选用，甚至可以将多种方法结合起来使用。
选择排序算法的依据

影响排序的因素有很多，平均时间复杂度低的算法并不一定就是最优的。相反，有时平均时间复杂度高的算法可能更适合某些特殊情况。同时，选择算法时还得考虑它的可读性，以利于软件的维护。一般而言，需要考虑的因素有以下四点：

1．待排序的记录数目n的大小；
2．记录本身数据量的大小，也就是记录中除关键字外的其他信息量的大小；
3．关键字的结构及其分布情况；
4．对排序稳定性的要求。

设待排序元素的个数为n.
1）当n较大，则应采用时间复杂度为O(nlog2n)的排序方法：快速排序、堆排序或归并排序序。
快速排序：是目前基于比较的内部排序中被认为是最好的方法，当待排序的关键字是随机分布时，快速排序的平均时间最短；
堆排序 ： 如果内存空间允许且要求稳定性的，
归并排序：它有一定数量的数据移动，所以我们可能过与插入排序组合，先获得一定长度的序列，然后再合并，在效率上将有所提高。

2） 当n较大，内存空间允许，且要求稳定性 =》归并排序

3）当n较小，可采用直接插入或直接选择排序。
直接插入排序：当元素分布有序，直接插入排序将大大减少比较次数和移动记录的次数。
直接选择排序 ：元素分布有序，如果不要求稳定性，选择直接选择排序

4）一般不使用或不直接使用传统的冒泡排序。

5）基数排序
它是一种稳定的排序算法，但有一定的局限性：
　　1、关键字可分解。
　　2、记录的关键字位数较少，如果密集更好
　　3、如果是数字时，最好是无符 的，否则将增加相应的映射复杂度，可先将其正负分开排序。

文章知识点与官方知识档案匹配，可进一步学习相关知识算法技能树首页概览34664 人正在系统学习中