【数据结构入门精讲 | 第一篇】打开数据结构之门

数据结构与算法是计算机科学中的核心概念，也与现实生活如算法岗息息相关。鉴于全网数据结构文章良莠不齐且集成度不高，故开设本专栏，为初学者提供指引。

基本概念

数据结构（data structure）是一种具有一定逻辑关系，在计算机中应用某种存储结构，并且封装了相应操作的数据元素集合。它包含三方面的内容，逻辑关系、存储关系及操作。

不同种类的数据结构适合于不同种类的应用，而部分甚至专门用于特定的作业任务。例如，计算机网络依赖于路由表运作，B 树高度适用于数据库的封装。

数据结构为何面世

随着应用程序变得越来越复杂和数据越来越丰富，几百万、几十亿甚至几百亿的数据就会出现，而对这么大对数据进行搜索、插入或者排序等的操作就越来越慢，数据结构就是用来解决这些问题的。

算法

算法是在一类特定的数据模型上定义所有运算并以解决一类特定问题为目标的一个有限的运算序列，它与数据结构是息息相关的。

算法实现的三要素

    数据：算法需要处理的数据是算法的输入，也是算法的输出。数据包括各种数据类型（如整数、浮点数、字符串、数组、链表、树等），以及数据结构（如栈、队列、堆、图等）。

    运算：算法的核心是运算，包括各种基本运算（如加、减、乘、除、取模等）、比较运算（如大于、小于、等于等）、逻辑运算（如与、或、非等）等。此外，算法还可以包括一些高级运算（如快速幂、快速排序、动态规划等），以及各种库函数的调用。

    控制：算法的执行流程需要通过控制来实现。控制包括顺序结构、选择结构、循环结构和函数调用等。顺序结构表示按照代码的书写顺序依次执行各个语句；选择结构包括if语句和switch语句，用于根据条件选择不同的分支；循环结构包括for循环、while循环和do-while循环，用于重复执行某个代码块；函数调用用于将代码分解成多个可重用的模块，提高代码的可读性和可维护性。

算法的描述载体：自然语言、数据流图、程序语言或者伪代码

算法的五大特征

输入：具有零个或多个输入，这些输入取自特定的数据对象集合

输出：至少具有一个或多个输出，这些输出同输入之间存在某种特定的关系

确定性（双重含义）：组成算法的每条指令是清晰的、无歧义的；无二义性，对应相同的输入仅有唯一的一条算法执行路径

有限性：序列项数有限且每一项运算时间有限

可行性：?合法输入 ?正确输出

注意：程序可以不满足有限性，即程序可以无限循环执行，而算法必须是有限的

基本数据类型

数据类型是指高级程序设计语言中，用以刻划程序中操作对象的特性。类型显式地或隐含地规定了在程序执行期间变量或表达式所有可能的取值范围，以及在这些值上允许进行的操作。

抽象数据类型

抽象数据类型是基本数据类型概念的引伸和发展，指操作对象的一个数据模型以及定义在该模型上的一组操作。 也就是说，对于抽象数据类型的描述，除了必须描述它的数据结构外，还必须描述定义在它上面的运算(过程或函数)。

抽象数据类型的定义取决于它的一组逻辑特性，而与其在计算机内部如何表示和实现无关。

抽象数据类型的内容需要：约定抽象数据类型的名字 、约定在该类型上定义的一组运算的各个运算的名字 、明确各个运算分别有多少个参数、这些参数的含义和顺序以及运算的功能

抽象数据类型的目标：

把数据类型的表示和数据类型上运算的实现，与其在程序中的应用分开，相互独立 ；顶层和底层都与抽象数据类型的定义打交道；算法底层的设计就是数据结构的设计和函数的设计

使用抽象数据类型的好处

顶层设计和底层实现分离、算法设计和数据结构设计分离 、数据模型和运算的内在统一于抽象数据类型之中、局部化、模块化、编出来的程序结构清晰，层次分明，便于程序正确性的证明和复杂性的分析

数据结构

数据结构的结构指的是数据之间的逻辑关系以及数据在计算机中的存储方式。数据的逻辑结构是从具体问题抽象出来的数学模型，反映成分数据之间的逻辑关系，它与数据的存储无关。数据的物理结构是在计算机中的存储和实现方法，包括数据结构中元素的表示及元素间关系的表示。

常见的数据结构

栈（Stack）： 栈是一种特殊的线性表，它只能在一个表的一个固定端进行数据结点的插入和删除操作。

队列（Queue）： 队列和栈类似，也是一种特殊的线性表。和栈不同的是，队列只允许在表的一端进行插入操作，而在另一端进行删除操作。

数组（Array）： 数组是一种聚合数据类型，它是将具有相同类型的若干变量有序地组织在一起的集合。

链表（Linked List）： 链表是一种数据元素按照链式存储结构进行存储的数据结构，这种存储结构具有在物理上存在非连续的特点。

树（Tree）： 树是典型的非线性结构，它是包括 2 个结点的有穷集合 K。

图（Graph）： 图是另一种非线性数据结构。在图结构中，数据结点一般称为顶点，而边是顶点的有序偶对。

堆（Heap）： 堆是一种特殊的树形数据结构，一般讨论的堆都是二叉堆。

散列表（Hash table）： 散列表源自于散列函数(Hash function)，其思想是如果在结构中存在关键字和T相等的记录，那么必定在F(T)的存储位置可以找到该记录，这样就可以不用进行比较操作而直接取得所查记录。

常用算法

数据结构研究的内容就是如何按一定的逻辑结构，把数据组织起来，并选择适当的存储表示方法把逻辑结构组织好的数据存储到计算机的存储器里。算法研究的目的是为了更有效的处理数据，提高数据运算效率。数据的运算是定义在数据的逻辑结构上，但运算的具体实现要在存储结构上进行。一般有以下几种常用运算：

• 检索： 检索就是在数据结构里查找满足一定条件的节点。一般是给定一个某字段的值，找具有该字段值的节点。
• 插入： 往数据结构中增加新的节点。
• 删除： 把指定的结点从数据结构中去掉。
• 更新： 改变指定节点的一个或多个字段的值。
• 排序： 把节点按某种指定的顺序重新排列。例如递增或递减。

基础性概念介绍完毕，不同数据结构的实现会在后面的文章中阐发。