本文主要讲述了数据结构的基本概念及相关的理论基础，是“由远及近”认识数据结构的简要浏览.
目录（更新中）
第一章 绪论
(1) 数据结构的基本概念
第二章 线性表
参考资料
[1] 王红梅编著. 数据结构（C++版本）（第2版）. 北京：清华大学出版社，2011.
程序设计与数据结构
计算机不能分析问题并产生解决问题的方案，必须由人（程序设计者）分析问题，确定问题的解决方案，编写程序，让计算机执行从而获得问题的解. 从问题的给出到计算机程序的编写执行，便是程序设计的一般过程.
分析问题的过程中，需要抽象出具体的数据模型（待处理的数据以及数据之间的关系，即数据结构），形成问题求解的基本思路.
这个由图灵奖获得者沃思给出的，广为流传的公式，说明了程序设计的核心.
具体来讲，数据结构到底是什么呢？如何从问题中抽象呢？
非数值问题
计算机能够求解的问题一般可分为数值和非数值问题.
数值问题抽象出的数据模型通常是数学方程，这一过程对于做过数学应用题的人来讲都是容易理解的，如小学用方程组解“鸡兔同笼”问题，其中线性方程组便是对问题中数据的抽象模型.
非数值问题抽象出的数据模型通常是线性表、树、图等数据结构，其抽象过程虽然仍然有其数学理论基础，但对大多数人来说并不了解、或有难度，故一般而言，数据结构教程通常着重于分析和解决非数值问题，即重点在于线性表、树和图这三种数据结构. 例如学籍管理、人机对弈、教学计划编排问题可以分别抽象出线性结构、树结构、图结构.
数据结构的基本概念
数据结构
数据（data) 是信息的载体，在计算机科学中是指所有能输入到计算机中并能被计算机程序识别和处理的符号集合.
数据元素（data element）是数据的基本单位.
数据结构（data structure）是指相互之间存在一定关系的数据元素的集合.
按照视点不同，数据结构分为逻辑结构和存储结构.
数据的逻辑结构（logical structrue)
数据的逻辑结构是指数据元素之间逻辑关系的整体。数据的逻辑结构在形式上可以定义为一个二元组(2-tuple)：
其中
根据数据元素之间逻辑关系的不同，数据结构分为以下四类：
- 集合：数据元素之间就是“属于同一个集合”，除此之外，没有任何关系.
- 线性结构：数据元素之间存在着一对一的线性关系.
- 树结构：数据元素之间存在着一对多的层次关系.
- 图结构：数据之间存在着多对多的任意关系.
树结构和图结构也称为非线性结构.
数据的逻辑结构常用逻辑关系图来描述：
- 将每一个数据元素看作一个结点，用圆圈表示；
- 元素间的逻辑关系用结点之间的连线表示;
- 如果强调关系的方向性，则用带箭头的连线表示.
数据的存储结构（storage structure）
数据的存储结构又称为物理结构，是数据及其逻辑结构在计算机中的表示. 存储结构除了存储数据元素外，必须隐式或显式的存储数据元素之间的逻辑关系.
通常有两种存储结构：顺序存储结构和链接存储结构.
顺序存储结构：用一组连续的存储单元依次存储数据元素，数据源之间的逻辑关系由元素的存储位置（隐式）表示.
链接存储结构：用一组任意的存储单元存储数据元素，数据元素之间的逻辑关系用指针（显式）来表示.
例如，分别使用顺序和链接存储结构存储线性表
再谈数据的逻辑结构和存储结构
数据的逻辑结构是从具体问题抽象出来的数据模型，是面向问题的，反映了数据元素之间的关联方式或邻接关系。
数据的存储结构是面向计算机的，其基本目标是将数据及其逻辑关系存储到计算机的内存中。
因此，有必要强调，除非同时提到数据的逻辑结构和物理结构，一般的情况下“数据结构”指的即是数据的逻辑结构。如“线性表是一种数据结构”，即指线性表是一种逻辑结构——无论它采用了何种存储结构（顺序或链接）.
抽象数据类型（Abstract Data Type)
数据类型（Data Type）
数据类型是一组值的集合以及定义在这个集合上的一组操作的总称.
于是数据类型规定了该类型数据的取值范围和对这些数据所能采取的操作.
例如，C++ 语言中整型是一种数据类型，则规定了整型变量只能取计算机所能表示的最小负整数和最大正整数之间的任意一个整数，并只允许进行算术运算、关系运算和逻辑运算等.
抽象（Abstract）
所谓抽象就是抽出问题本质的特征而忽略非本质的细节，是对具体事物的一个概括.
比如地图是对它所描述地域的一种抽象，物体受力分析图是对真实世界中某具体物体的抽象.
很显然，使用数学知识解决实际问题时，我们提取关键因素，忽略非关键的因素，来建立对应的数学模型，这是典型的抽象过程.
抽象的原因在于：一旦一个抽象的问题得到解决，则很多同类的具体问题便可迎刃而解.
算法的设计需要抽象，同时在编程语言层面，抽象的思想仍然发挥作用：实现封装和信息的隐藏.
例如，我们常把能够完成某种功能并可重复执行的一段代码抽象为函数，在需要执行这种功能时调用这个函数，从而将“做什么”抽象出来，与“怎么做”相分离，实现了算法细节和数据内部结构的隐藏.
抽象数据类型
抽象数据类型简称 ADT，是一个数据结构以及定义在该结构上的一组操作的总称.
ADT 可理解为对编程语言本身提供的基本数据类型进行的进一步抽象，因此 ADT 和数据类型的区别仅在于：数据类型是高级编程语言支持的基本数据类型，而 ADT 指的是自定义的数据类型.
在设计 ADT 时，把 ADT 的定义和实现分开. 定义部分只包含数据的逻辑结构和所允许的操作集合：一方面，使用者依据这些定义来使用 ADT；另一方面，实现者依据这些定义完成该 ADT 的各种操作的具体实现.
ADT 提供了定义和实现的不同试图，实现了封装和信息隐藏. 例如各种语言都提供了整数类型和具体实现，尽管它们的实现方法各有不同，但由于其 ADT 相同，在用户看来都是相同的.
一个 ADT 的定义不涉及实现细节，形式上可简可繁. 如下例中对 ADT 的定义包括抽象数据类型名、数据元素之间的逻辑关系的定义、每种基本操作的接口：
1 | |
以上定义体现了契约式编程的思想.
容易体会，面向对象语言的“类”体现了抽象数据类型的思想.
