数据结构笔记——概述

数据结构——概述

——2017.12.21

一、线性表：

这个是为了解决单线存储而出现的，数组就是最简单粗暴的存储方法。就是直接拉出一大块数据存在那里。数组的快速存取其实只是一个副作用，因为所有的数据都在一起，可以直接算出来数据的地址。链表则是为了解决可以无线增长的需求的。因为找不到一大块可以连续的存入数据，甚至也不知道程序可能使用的数据总量，所以就没办法划分一块数据来使用，划小了不够用，划大了浪费。所以必须想办法解决问题。最后采用的方法就是从入口开始，每一个数据块不仅仅有数据，还会有指向下一个数据块的线索，用来寻找下一个数据。这就是链表。所谓的双向链表，只是加了一个向前的线索的链表。队列，栈，都是线性表的特殊形态。进行了操作上的限制。

二、树：

树是为了解决单一入口下的非线性关联性的数据存储或者排序这样的功能而来的。

最常见的应用是编程时候的map，就是利用了二叉树的可排序和可以快速插入并且保持序列完整的特性来构建键值数据对，来实现数据的插入增加以及快速查找的能力的。

还有做语法解析，文字处理等等很多场景也会用到树。

三、图：

图其实就是把线性表进一步扩展，每个节点会有不止一个前置和后缀节点，而且前置和后缀的概念也不再明晰，变成了关联节点。具体的应用主要是一些特殊的算法和图形学上的一些使用。总之数据结构的前期学习要重理解。以倒推的方式，搞清楚每种数据结构产生的目标。多画画图，思考一下，理解透彻以后。再去做练习题会事半功倍。