理解数据结构

 从宏观上理解数据结构
    1.数据结构对编程为什么如此重要？

    现在就根据我自己的体会来为大家阐述一下数据结构对我们编程为什么如此重要。记得在开始学习编程的时候，对数据结构没什么概念，感觉编程就是那么回事，不用数据结构也能编出一大堆程序，然而我只能说那都是些小孩子过家家玩的小程序而已，程序中几乎没有用到多少数据，无论你怎么存储，程序运行起来都是很快的。然而当你为工程应用去编写程序的时候，那都是处理大批的数据，那时候就不能随便乱存储数据了，必须根据实际情况选择一种合适的数据结构来存储数据，从而能够大大提高数据的处理效率。举个例子，我们平时经常用到的排序也算是对数据的处理，我们选择不同的排序算法效率是不同的，当数据量很小时，我们感觉不出它们的差异，然而当我们对大量数据进行排序时就能感觉出它们的效率来。当然在排序时排序策略是很重要的，然而这些策略有时是依赖于必要的数据结构的。如插入排序、选择排序、快速排序等可能依赖的只是线性表，而堆排序就依赖于堆了。因此选择一种好的数据结构可能会大大提高程序的运行效率，而且解决问题时的某中策略可能也要依赖于具体的数据结构。 

2.什么是数据结构？

    我们知道了数据结构对编程的重要性，那究竟什么是数据结构呢？首先来看一下数据结构诞生的目的。在现实世界中存在着大量的数据，而这些数据不管以何种方式存储，都需要使用一种结构来表示，而这种结构不仅能够表示数据元素本身，还能够表示数据元素之间的关系，最好这种结构还能占据较少的存储空间。然而这里所说的数据结构也只能说是数据的逻辑结构，即它只是抽象的存在于我们的脑海中，而在具体的存储中还需要将这种逻辑结构用现实事物表示出来。由于我们的计算机大部分功能都跟存储数据和处理数据有关，因此计算机作为数据的载体与数据结构的关系也就相当大了，计算机就可以根据我们要求的数据结构来存储数据了。至此，我们可以给数据结构下一个比较学术的定义：数据结构是用来描述数据元素集合及各个数据元素之间关系的逻辑结构。当然在很多数据结构的书籍中对数据结构的定义是不同的，有的书籍将对数据结构处理的简单运算也归为数据结构的内容，当然这看你如何理解了，毕竟数据结构和算法是不分家的。  

3.计算机描述数据的方式

    前边描述了什么是数据结构，那计算机都可以通过哪些基本的手段来描述我们的数据呢？首先我们知道在计算机中大部分数据都存在于磁盘上和内存里，而CPU处理数据又必须将数据从磁盘读取到内存中，由于内存资源比较珍贵，我们采取合适的数据结构在内存中存储数据以节省内存空间是必要的。谈到内存对数据的存储，我们程序员都应该知道，我们的程序在计算机上运行需要一定的内存空间，该空间可以简单分为代码区和数据区。代码区是存放我们程序代码的地方，那部分空间我们无法管理。但是数据区是存放我们程序需要处理的数据的地方，而我们就是采取合理的方式将数据存储到那个地方。

    我们都知道计算机管理内存的方式为每个字节的空间赋予一个地址，这样我们就可以通过地址来访问内存的数据了。当我们存放数据时，我们可以通过将数据存放到指定地址的空间中去，当我们取数据时，可以根据地址找到相应的数据，这种方式称为直接寻址方式；另外还有间接寻址方式，这种方式我们通过地址找到的数据不是数据本身，而是数据存放的位置，通过它再去找才能找到真正的数据，当然，间接寻址可以间接很多次，这就是多维指针的由来。说了大半天的直接寻址和间接寻址，那跟数据结构有什么关系呢？当然有关系了，因为这是计算机组织数据的两种最基本的方式，正是通过这两种基本方式，我们的数据才被存放到内存中，而存放的时候可能是连续的地址空间，也可能是离散的地址空间。正因为这样，才出现了计算机对数据的不同描述形式。常见的描述形式有：公式化描述、链表描述、间接描述和模拟指针。

    公式化描述是通过公式计算出元素的位置，从而能够直接访问到这个元素。但这种描述方式必须保证所使用的空间是连续的，因为只有连续的地址空间，才能通过一个固定的偏移量一次找到数据的地址。就拿各种编程语言实现的数组来说，每个数组都有一个连续的空间，而数组名又标志着这个连续空间的首地址，因此若想访问这个数组的某个元素直接通过首地址加偏移量就找到了。因此数组就是一种公式化描述的数据结构，描述公式为f(i)=location(i-1)，其中i是表示数组中的第几个元素。对于多维数组，内存中实际也是一个连续的空间，只不过编译器也是以公式化的方式来描述这个数据结构的，如在C++中是采用行主映射方式来映射的，二维数组的公式为f(i,j)=i*n+j；其中i表示行号，j表示列号，n表示列数。当然采用公式化描述的数据结构有很多，如散列表、完全二叉树等，这种描述方式优点就是很多情况能够节省空间，并且提高访问数据的速度。但这种描述方式也有缺点就是经常受限，毕竟很多问题是用公式没法描述的；还有通过公式化描述需要连续的空间有时也显得不够灵活。例如对数据的插入删除操作需要移动数据。

    链表描述方式是将数据存储在离散的空间上，既然空间是离散的，那通过固定的偏移量就没法访问元素了。因此可将每个元素的地址保存到上一个元素中，这样就形成了链表。链表由于采用了离散存储，因此在有些数据操作上就显得比较灵活。但这也导致了它的不足，比如说不能随机访问某个节点，另外还占用了额外的指针空间等。

    间接描述方式是将数据的地址保存到一张表中，实际的数据离散的存储在内存中，当需要访问数据时，首先查找表找到数据的地址然后再去访问实际数据。这种描述方式很多时候是公式化描述和链表描述方式的结合。当实际的数据元素比较大时是适合用这种方式来描述的。

    模拟指针这种方式是通过用整数来模拟指针访问数据，也算是离散存储在内存中，但这种离散是限定在一定范围内的，因为我们在实现模拟指针时需要申请一块连续的空间模拟堆区，并根据实际需要将这块连续的空间重新编号，以便使用整数表示它的地址。与此同时还要维护两个链表，空闲链表和有数据的链表。这相当于我们替操作系统为程序分配内存的工作。 

4.各种数据结构的宏观理解

    为了便于将各种数据结构联系起来，本人对常见的数据结构分为了三大类：线性表，树，图。万变不离其宗，其他的数据结构都是在这三种上根据实际需要进行的扩展。当然，如果三大类还觉得有点多，那就再来个万剑归综到图，任何数据结构都可以说成是图，不过各有各的特点罢了。下面就针对常见的数据结构在三大类上进行分析，由于本文只是从宏观上理解数据结构，因此对各种数据结构所实现的细节不会做太多的说明，想要了解可参看数据结构的相关书籍。 

4.1线性表

    线性表的数据结构有很多，如数组、矩阵、链表、堆栈、队列、跳表、散列表等。一维数组是典型的线性表，多维数组可以看成是多个线性表的组合，数组的描述方式一般采用公式化描述方式。对于矩阵可以看成是二维数组，但是由于矩阵有很多种，比如三角矩阵，稀疏矩阵，像对这样矩阵的描述为了节省空间，可采用合理的描述方式，如采用链表的方式，只将非零元素保存到节点上。堆栈和队列实际上是对线性表添加某种限制而形成的， 堆栈是后进先出，队列是先进先出，实际上它们是一种特殊的优先队列，只不过对优先权的规定是不一样的。可以使用公式化描述它们也可以使用链表描述它们，但是效率是不同的。对于堆栈采取公式化描述是比较好的，进出效率都为O(1)，若用链表描述就显得有点浪费空间了，不过如果是多个堆栈的话，用链表描述是比较好的。对于队列适合用链表来描述，因为对于链表无论是从头部添加元素还是从尾部删除元素效率都是O(1)，然而如果采用公式化描述的话，每次删除需要移动元素，无疑增加了开销。

    跳表和散列表是经常用来描述字典的两种数据结构。字典常见的操作有查找、插入、删除、按序输出等。虽然字典也能用普通的数组链表实现，但效率不高。跳表是对链表的一种改进。链表本身优点就是插入、删除效率比数组高，然而查找效率低，因此可以通过添加额外的指针来提高查找效率。跳表的原理是根据二分查找的思想，我们知道在一个有序数组上二分查找的时间复杂度为O(logn),因此可以通过在有序链表上添加额外的指针来实现这样的搜索方法。然而仔细分析，我们会发现，要想实现真正的二分查找并非易事，因为跳表中的元素并非是一成不变的，因此该在哪个元素上添加额外的指针并且把该元素应该视为几级链表上的元素，都是不可预测的，因此这就增加了实现跳表的复杂度，在实际中可采用随机的方式将某一个元素定为几级链上的元素，具体的实现细节可参看数据结构的相关书籍。

    散列表是通过散列函数根据关键字来确定元素的位置，也算是公式化的描述方式。在理想情况下，散列表在查找、插入、删除的时间复杂度都能达到O(1)，然而在现实中由于关键字的变化范围实在太大，理想散列表实现需要大量的空间，造成严重浪费，因此出现了可以将不同的关键字映射到同一位置的散列函数，那么问题就又来了，既然将不同的关键字映射到了同一位置，那么该如何处理这种冲突呢？处理这种冲突的两种常见方式是线性开型寻址散列和链表散列，线性开型寻址散列是将相同关键字的元素尽可能的放到函数映射的位置上，如果该位置已存在，则向后查找最近的空桶；而链表散列是将冲突的元素放到一个链表上，这两种方式各有自己的优缺点。

    对于描述字典的这两种数据结构进行性能分析，跳表在最好状态下查找、插入、删除的时间复杂度都为O(k+logn)其中k为链的级数,最差则为O(k+n),而对于采取了将多个关键字映射到同一位置的散列表来说，最好状态下查找、插入、删除的时间复杂度都为O(1)，然而最差状态却达到O(n),这么来说散列表是否都一直优于跳表呢，当然还得依赖于实际的问题，例如在按序输出时，跳表明显优于散列表。

    在线性表这几种数据结构中会发现，他们都是对普通的线性表改造而成，有的是添加规则上的限制，有的是添加额外的辅助信息，还有的是对多个线性表的组合。但无论怎样变化，终究还是线性表。因此我们在实际开发中，可以根据不同数据结构的特点来选择他们。  

  4.2树

    树可以用来描述具有层次结构的事物，树这种结构真是太神奇了，通过对树添加不同的限制就形成了不同的数据结构。如对只有左右孩子的树我们称之为二叉树，在二叉树下通过添加各种限制又产生了很多数据结构，如完全二叉树、堆、左高树、AVL树、红黑树、二叉搜索树等。下面就来详细描述一下这些关于树的数据结构。

    首先考虑一个问题在计算机内存中为什么多采用二叉树来存储数据，而不采用多叉树呢？当然也是为了提高速度处理效率，在搜索二叉树的一个节点时当然是比较的次数越少越好。试考虑在一个有序数组中进行二分查找要比三分查找、四分查找乃至更多分的查找效率更高呢？这个问题自然也就明白了。

    完全二叉树是对二叉树结构层次限制比较大的数据结构，那这种数据结构有什么好处呢，其中一个好处是这种数据结构采用公式化描述是非常方便的，而且大大的节省空间。

    将完全二叉树限制为最大树就形成了堆，而堆这种数据结构对于描述优先队列是非常高效的，使用堆来描述优先队列插入、删除的效率都为O(logn)，而且采用公式化描述的话非常节省空间。当然优先队列还可以用线性表来描述，然而那毕竟是低效的。然而如果想将两个优先队列合并，用堆来描述就非常低效了，就需要选择另外一种数据结构。左高树是对左右子树进行优先权限制的二叉树，至于选择什么作为优先权的评价因素，可以把高度作为评价因素，也可以把节点数量作为评价因素，那就分别形成了高度优先左高树和重量优先左高树。之所以对左右的子树进行优先权限制，那是因为进行了这样的限制后，将两棵左高树合并为一棵左高树就很容易了。将左高树再次添加最大树的限制条件就形成了最大左高树，最大(小)左高树同样可以描述优先队列，而且适合两棵树的合并，不过在存储效率方面不如堆节省空间了。

    接下来讨论一下搜索树，搜索树是另一种可以描述字典的高效的数据结构。先来分析一下二叉搜索树，二叉搜索树是对二叉树节点上的值进行限制，要求每个节点的值比左子树的值大并且比右子树的小，加上这一限制，对某一元素的搜索效率就比较高了，在最好情况下查找，插入，删除操作的时间复杂度都能够达到O(logn)，然而最坏情况下达到了O(n)，导致最坏情况是由于二叉树的极度不平衡造成的，为了解决这个问题，平衡树又掺和进来了，平衡二叉搜索树不就很好的解决了这个问题吗？然而在每次插入删除操作后AVL树为了维持平衡的特性需要进行多次旋转，因而这又降低了效率。红黑树的出现就很好的解决了这个问题，红黑树虽然不是完全平衡的二叉树但也算的上是基本平衡，然而红黑树对于插入删除操作后维持红黑树的特性花费的代价并不高。在现实应用中，很多字典都是用红黑树来进行描述的。除了二叉搜索树，多叉搜索树在很多地方也有应用，例如在读取磁盘数据时，可以采用B-树来建立索引，由于每次读取磁盘花费的代价比较大，因此读取的磁盘次数越少越好，从理论上也就是说树的高度越矮越好。又如为了提高索引速度，很多数据库采用B+树建立索引。另外，由于英语单词一般是用字母拼凑而成，因此将英语单词存放在多叉树中可以大大提高搜索单词的效率，这就是著名的Trie树。

    通过以上对各种由树产生的数据结构来看，通过对树添加各种限制来维持一种固定的数据结构对解决某些特定的问题是非常高效的，因此在现实应用中，我们应该根据实际的需要选择合适的数据结构或对某些数据结构进行改造，变成真正适合自己的数据结构。 

 4.3图

    用图来描述万千事物极其联系是最方便不过的了，然而根据具体的问题所产生的图也是不一样的，如有的事物用有向图描述比较合适，有的用无向图描述比较合适，有的用完全图描述比较合适，有的用连通图描述比较合适，有的用二分图描述比较合适，不管怎样要根据实际的问题使用不同的方式，当然在解决实际问题时，往往需要结合必要的算法。

    对于图的描述经常采用的是邻接矩阵和邻接链表来描述。