从宏观上理解数据结构
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)，然而在现实中由于关键字的变化范围实在太大，理想散列表实现需要大量的空间，造成严重浪费，因此出现了可以将不同的关键字映射到同一位置的散列函数，那么问题就又来了，既然将不同的关键字映射到了同一位置，那么该如何处理这种冲突呢？处理这种冲突的两种常见方式是线