1.1 数据结构基础知识
1.2 算法复杂度
1.3 一棋盘麦子
1.4 神奇魔鬼序列
1.5 本章要点
著名的瑞士科学家Niklaus Wirth教授提出：数据结构+算法＝程序。数据结构是程序的骨架，算法是程序的灵魂。
学习数据结构首先从认识以下几个概念开始。
1．数据
数据是指所有能输入到计算机中的描述客观事物的符号，包括文本、声音、图像、符号等。我们经常使用的“扫一扫”的二维码，也是数据。
2．数据元素
数据元素是数据的基本单位，也称节点或记录，如图1-1所示。
图1-1 数据元素
3．数据项
数据项表示有独立含义的数据最小单位，也称域。若干个数据项构成一个数据元素，数据项是不可分割的最小单位，如图1-1所示的“86”。
4．数据对象
数据对象是指相同特性的数据元素的集合，是数据的一个子集。
5．数据结构
数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。
数据结构是带“结构”的数据元素的集合，“结构”是指数据元素之间存在的关系。数据结构研究的问题是将带有关系的数据存储在计算机中，并进行相关操作。数据结构包含逻辑结构、存储结构和运算三个要素。
6．逻辑结构和存储结构
逻辑结构是数据元素之间的关系，存储结构是数据元素及其关系在计算机中的存储方式。例如，小明和小勇是表兄弟，这是他们之间的逻辑关系；他们在教室里面的位置是他们的存储结构。无论他们的座位怎样安排，是挨着坐，还是分开坐，都不影响他们的表兄弟关系。
逻辑结构：数据元素间抽象化的相互关系，与数据的存储无关，独立于计算机，它是从具体问题中抽象出来的数学模型。
数据结构的逻辑结构共有以下4种。
（1）集合——数据元素间除“同属于一个集合”外，无其他关系。
集合中的元素是离散、无序的，就像鸡圈中的小鸡一样，可以随意走动，它们之间没有什么关系，唯一的亲密关系就是在同一个鸡圈里，如图1-2所示。数据结构重点研究的是数据之间的关系，而集合中的元素是离散的，没有什么关系。因此，集合虽然是一种数据结构，但在数据结构书中不讲，在离散数学的集合论部分有重点讲述。
图1-2 集合
（2）线性结构——一个对一个，如线性表、栈、队列、数组、广义表。
线性结构就像穿珠子，是一条线，不会分叉，如图1-3所示。有唯一的开始和唯一的结束，除了第一个元素外，每个元素都有唯一的直接前驱（前面那个）；除了最后一个元素外，每个元素都有唯一的直接后继（后面那个）。
图1-3 线性结构
（3）树形结构——一个对多个，如树。
树形结构就像一棵倒立的树，树根可以发出多个分支，每个每支也可以继续发出分支，树枝和树枝之间是不相交的，如图1-4所示。
图1-4 树形结构
（4）图形结构——多个对多个，如图、网。
图形结构就像我们经常见到的地图，任何一个节点都可能和其他节点有关系，就像一张错综复杂的网，如图1-5所示。
图1-5 图形结构
存储结构：数据元素及其关系在计算机中的存储方式。
存储结构可以分为4种：顺序存储、链式存储、散列存储和索引存储。很多数据结构类书籍只介绍了前两种基本的存储结构，这里加上后两种，以便读者了解。
（1）顺序存储
顺序存储是指逻辑上相邻的元素在计算机内的存储位置也是相邻的。例如，张小明是哥哥，张小波是弟弟，他们的逻辑关系是兄弟，如果他们住的房子是前后院，也是相邻的，就可以说他们是顺序存储，如图1-6所示。
图1-6 兄弟两家前后相邻
顺序存储采用一段连续的存储空间，将逻辑上相邻的元素存储在连续的空间内，中间不允许有空。顺序存储可以快速定位第几个元素的地址，但是插入和删除时需要移动大量元素，如图1-7所示。
图1-7 顺序存储
（2）链式存储
链式存储是指逻辑上相邻的元素在计算机内的存储位置不一定是相邻的。例如，哥哥张小明因为工作调动去了北京，弟弟仍然在郑州，他们的位置是不相邻的，但是哥哥有弟弟家的地址，很容易可以找到弟弟，就可以说他们是链式存储，如图1-8所示。