绪论
“数据结构”这门学科形成和发展的背景：自1946年第一台计算机问世以来，计算机产业的飞速发展已远远超出人们对它的预料，在某些生产线上，甚至几秒钟就能产出一台微型计算机，常量猛增，价格低廉，使得它的应用范围迅速扩展。如今，计算机已深入到人类社会的各个领域。
计算机的应用已不再局限于科学计算，而更多地用于控制，管理及数据处理等非数值计算的处理工作。与此相应，计算机加工处理的对象由纯粹的数值发展到字符、表格和图像等各种具有一定结构的数据，这就给程序设计带来一些新问题。为编写出一个“好”的程序，必须分析待处理的对象的特征以及各处理对象之间存在的关系。
用计算机解决一个具体问题时，大致需要经过下列几个步骤：首先要从具体问题抽象出一个适当的数字模型，然后设计一个解此数学模型的算法，最后编出程序，进行测试，调整直至得到最终解答。寻求数学模型的实质是分析问题，从中提取操作的对象，并找出这些操作对象之间含有的关系，然后用数学的语言加以描述。
简单来说，数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作 等的学科。
可以认为“数据结构”是介于数学、计算机硬件和计算机软件三者之间的一门核心课程。
“数据结构”的概念起源于1968年美国计算机科学家 唐纳德·克努特(Donald Ecvin Knuth)教授所著的《计算机程序设计艺术》(The Art of Computer Programming)。在该书的第一卷《基本算法》中，他开创了数据结构的最初体系，较系统地阐述了数据的逻辑结构和存储结构及其操作。
在计算机科学中，研究数据结构对设计出高性能的算法和软件至关重要。数据结构课程不仅是程序设计的基础，而且是设计和实现编译程序、操作系统、数据库系统及其他应用程序的重要基础。
数据结构的基本概念
数据(date)是对客观事物的符号表示，在计算机科学中指所有能输入到计算机中并被计算机程序处理的符号的总称。它是计算机程序加工的“原料”。
数据元素(data element)是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。
数据对象(data object)是性质相同的元素的集合，是数据的一个子集。
数据结构(data structure)是相互之间存在一种或多种特定关系的数据元素的集合。在任何问题中，数据元素都不是孤立存在的，它们之间存在某种关系，这种数据元素之间的关系称为*结构(Structure)*。 数据结构包括三方面的内容：逻辑结构、存储结构和数据的运算。
数据的逻辑结构
逻辑结构是指数据元素之间的逻辑关系，即从逻辑关系上描述数据。它与数据的存储无关，是独立于计算机的。
数据的存储结构
存储结构是指数据结构在计算机中的表示(又称印象)，也称物理结构。它包括数据元素的表示和关系的表示。数据的存储结构是用计算机语言实现的逻辑结构，它依赖于计算机语言。
数据的运算
施加在数据上的运算包括运算的定义和实现。运算的定义是针对逻辑结构的，指出运算的功能；运算的实现是针对存储结构的，指出运算的具体操作步骤。
不存在只体现存储结构而不体现逻辑结构的表述，所以可以认为：逻辑结构独立于存储结构。
数据类型：是一个值的集合和定义在这个值集上的一组操作的总称。
抽象数据类型(Abstract Data Type,简称 ADT):指一个数学模型以及在该模型上的一组操作。
算法和算法分析
算法
算法(algorithm)是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作；此外算法还具有下列5个重要特性：
(1)有穷性。一个算法必须总是(对于任何合法的输入值)在执行有穷步之后结束，且每一步都可在有穷时间内完成。
(2)确定性。算法中每一条指令必须确切的含义，读者理解时不会产生二义性。并且，在任何条件下，算法只有唯一的一条执行路径，即对于相同的输入只能得出相同的输出。
(3)可行性。一个算法是可行的，即算法中描述的操作都是可以通过实现的基本运算执行有限次来实现的。
(4)输入。一个算法有零个或多个输入，这些输入取自于某特定的对象的集合。
(5)输出。一个算法有一个或多个输出，这些输出是同输入有着某些特定关系的量。
算法设计的要求
(1)正确性。算法应能够正确地解决求解问题。
(2)可读性。算法应具有良好的可读性，以帮助人们理解。
(3)健壮性。输入非法数据时，算法能适当地做出反应或进行处理，而不会产生莫名其妙的输出结果。
(4)效率与底存储量需求。效率是指算法执行的时间，存储量需求是指算法执行过程中所需要的最大存储空间，这两者都与问题的规模有关。
算法效率的度量
算法效率的度量是通过时间复杂度和空间复杂度来描述的。
时间复杂度
一个语句的频度是指该语句在算法中被重复执行的次数。算法中所有语句的频度之和记为T(n)，它是该算法问题规模n的函数，时间复杂度主要分析T(n)的数量级。
算法中基本运算(最深层循环内的语句)的频度与T(n)同数量级，因此通常采用基本运算的频度f(n)来分析算法的时间复杂度。因此，算法的时间复杂度记为 T(n)=O(f(n))
式中，O的含义是T(n)的数量级，其严格的数学定义是：若T(n)和f(n)是定义在正整数集合上的两个函数，则存在正常数C和n_0 ,使得当n>= n_0时，都满足0<=T(n)<=Cf(n)
最坏时间复杂度是指在最坏情况下，算法的时间复杂度。
平均时间复杂度是指所有可能输入实列在等概率出现的情况下，算法的期望运行时间。
最好时间复杂度是指在最好情况下，算法的时间复杂度。
在分析一个程序的时间复杂性时，有以下两条规则：
(a)加法规则 T(n)=T_1(n)+T_2(n) = O(f(n))+O(g(n)) = O(max(f(n),g(n)))
(b)乘法规则 T(n)=T_1(n)×T_2(n) = O(f(n))×O(g(n)) = O(f(n)×g(n))
常见的渐进时间复杂度为
O(1)<O(log_2 n)<O(n)<O(nlog_2 n)<O(n^2)<O(n^3)<O(2^n)<O(n!)<O(n^n)
记法：常对幂指阶
空间复杂度
算法的空间复杂度S(n)定义为该算法所耗费的存储空间，它是问题规模n的函数。记作 S(n) = O(f(n))
一个程序在执行时需要存储空间来存放本身所用的指令，常数、变量和输入数据外，还需要一些对于数据进行操作的工作单元和存储一些为实现计算所需信息的辅助空间。
若输入数据所占空间只取决于问题本身，和算法无关，则只需分析除输入和程序之外的额外空间。
算法原地工作是指 算法 所需的辅助空间 为常量，即O(1)。
版权声明
Scholar’s Blog by scholargeek is licensed under a Creative Commons BY-NC-ND 4.0 International License.
由董仕麟创作并维护的scholargeek博客采用创作共用保留署名-非商业-禁止演绎4.0国际许可证。
本文首发于Scholar’s Blog博客，版权所有，侵权必究。
本文永久链接：https://scholargeek.github.io/2018/06/01/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E5%AD%A6%E4%B9%A0/