数据结构与算法起步

整理一下数据结构与算法方面的概念和代码。

• 数据结构与算法起步
• 线性表
• 栈和队列

概念

研究对象：数据结构课程是研究非数值计算的程序设计问题中计算机处理对象及它们之间关系和操作的学科。简单地说，数据结构是计算机组织数据和存储数据的方式。更进一步地说，数据结构是指一组相互之间的存在一种或多种特定关系的的数据组织方式或它们在计算机内的存储方式，以及在该组数据上的一组操作。

概念术语

• 数据（Data）：是信息的载体，它是能够被计算机识别、存储和处理的对象；
• 数据元素（Data Element）：是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。数据元素是运算的基本单位，通常具有完整确定的意义。数据元素常常又简称元素。一个数据元素可由若干个数据项（Data Item）组成。在不同的条件下，数据元素又可称为元素、结点、顶点、记录等；
• 数据项（Data Item）：是指不可分割的、具有独立意义的最小数据单位，在数据库中数据项又称为字段（field）或域。数据项是数据的不可分割的最小标识单位；
• 数据结构（Data Structure）：是指互相之间存在着一种或多种关系的数据元素的集合。它包括数据的逻辑结构、数据的存储结构和数据的基本运算；
• 数据类型（Data Type）：一是限定了数据的取值范围（实际上与存储形式有关）；二是规定了数据能够进行的一组操作（运算）；
  • 数据类型可分为两类：一类是非结构的原子类型，原子类型的值是不可再分解的（整型、实型等）；另一类是结构类型，它的成分可以由多个结构类型组成，并可以分解；结构类型的成分可以是非结构的，也可以是结构的（数组的值由若干分量组成，每个分量可以是整数等基本类型，也可以是数组等结构类型）；
• 抽象数据类型（Abstract Data Type）：指一个数学模型及定义在该模型上的一组操作；抽象数据类型的定义取决于它的一组逻辑特性，而与其在计算机内部如何表示和实现无关；

数据的逻辑结构

数据的逻辑结构：指数据元素之间的逻辑关系，即数据元素之间的关系方式或「邻接关系」，分为线性结构（表、栈、队、串等）和非线性结构（树、图、网等）。

数据的逻辑结构的四种分类：

• 集合结构：数据元素之间的关系是「属于同一个集合」。数据元素之间除了同属一个集合外，不存在其他关系；任何两个结点之间都没有邻接关系，组织形式松散；
• 线性结构：数据元素除了同属于一个集合外，数据元素之间还存在着一对一的顺序关系；其中结点按逻辑关系依次排列形成一条「链」，结点之间一个一个依次相邻接；
• 树形结构：数据元素之间存在着一对多的层次关系；具有分支、层次特性，其形态像自然界中的树，上层的结点可以和下层的结点相邻接，但下层的结点只能和上层的一个结点相邻接；
• 图状结构：数据元素之间存在着多对多的任意关系，图状结构也称为网状结构；其中任何两个结点的都可以相邻接；

数据的存储结构

数据的存储结构：指数据的逻辑结构在计算机中的实现，也称数据的物理结构（或数据的存储结构）。

数据的存储结构的两个部分：

• 存储数据的元素；
• 数据元素之间的关联方式；

数据的存储结构的四种方式：

• 顺序存储：指所有存储结点存放在一个连续的存储区里；利用结点在存储器中的相对位置来表示数据元素之间的逻辑关系；
• 链式存储：批每个存储结点除了含有一个数据元素外，还包含指针，每个指针指向一个与本结点有逻辑关系的结点，用指针表示数据元素之间的逻辑关系；
• 索引存储：指通过建立存储结点信息，以及建立附加的索引表来标识结点的地址的存储方法；
• 散列存储：又称 Hash 存储，是一种力图将数据元素的存储位置与关键码之间建立确定对应关系的查找方式；

数据的逻辑结构与数据的存储结构的关系

• 数据的逻辑结构只是一种数据模型，体现了数据的组织方式，要在计算机中实现逻辑结构，还依赖它在计算机中的存储结构；
• 数据的逻辑结构在计算机中的实现称为数据的存储结构（或物理结构）。一般情况下，一个存储结构包括存储数据的元素和数据元素之间的关系方式；
• 一种逻辑结构可以采用一种或几种存储方式来表达数据元素之间的逻辑关系，相应的存储结构称为给定逻辑结构的存储实现或存储映像；

运算

运算：指在某种逻辑结构上施加的操作，即对逻辑结构的加工。这种加工以数据的逻辑结构为对象，运算的实现就是对该运算的算法。

数据结构上的基本操作：

• 创建：建立某种所需的数据结构；
• 插入：在指定位置上添加新的数据元素；
• 删除：删去指定位置上对应的数据元素；
• 更新：修改某个数据元素的值；
• 查找：寻找满足特定条件的数据元素所在的位置；
• 读取：读出指定位置上数据元素的内容；

算法

算法特性

算法（Algorithm）：是对特定问题求解步骤的一种描述，是指令的有限序列。其中每一条指令表示一个或多个操作。

算法的特性：

• 有穷性：一个算法必须在有穷步之后结束，即必须在有限时间内完成；
• 确定性：算法的每一步必须有确切的定义，无二义性，且在任何条件下算法只有唯一一条执行路径，即对于相同的输入只能得出相同的输出；
• 可行性：算法中的每一步都可以通过已经实现的基本运算的有限次执行得以实现；
• 输入：一个算法具有零个或多个输入，这些输入取自特定的数据对象集合；
• 输出：一个算法具有一个或多个输出，这些输出同输入之间存在某种特定的关系；

算法好坏的因素：

• 正确性：能正确地实现预定的功能，满足具体问题的需要；
• 易读性：易于阅读、理解和交流，便于调试、修改和扩充；
• 健壮性：即使输入非法数据，算法也能适当地做出反应或进行处理，不会产生预料不到的运行结果；
• 时空性：算法的时间性能（或时间效率）尽可能快和空间性能（或空间效率）尽可能少，时间性能考量计算量，空间性能考量存储量；

算法的描述

• 自然语言算法描述：用人类自然语言（如中文、英文等）来描述算法，同时还可插入一些程序设计语言中的语句来描述，这种方法也称为非形式算法描述。其优点是不需要专门学习，任何人都可以直接阅读和理解，但直观性很差，复杂的算法难写难读；
• 框图算法描述：这是一种图示法，可以采用方框图、流程图、N-S 图等来描述算法，这种描述方法在算法研究的早期曾流行过。它的优点是直观、易懂，但用来描述比较复杂的算法就显得不够方便，也不够清晰简洁；
• 伪代码算法描述：如类 C 语言算法描述。这种算法描述很像程序，但它不能直接在计算机上编译、运行。这种方法很容易编写、阅读算法，而且格式统一，结构清晰，专业设计人员经常使用类 C 语言来描述算法；
• 高级程序设计语言编写的程序或函数：这是直接用高级语言来描述算法，它可在计算机上运行并获得结果，使给定问题能在有限时间内被求解，通常这种算法描述也称为程序；

算法分析

算法被转换成程序并在计算机上执行时，其运行所需要的时间一般取决于下列几个因素：

• 硬件的速度；
• 实现算法的程序设计语言；
• 编译程序所生成目标代码的质量；
• 算法所采用的策略；
• 问题的规模；

时间复杂度

Know Thy Complexities

时间复杂度（Time Complexity）：指该程序的运行时间与问题规模的对应关系。大 Ο 表示法也称为算法的渐进表示法，它不考虑具体的运行时间，只给出算法在问题规模 n 下执行时间的上界。T(n) = O(f(n)) 称为算法的渐进时间复杂度（Asymptotic Time Complexity），简称时间复杂度。

大 O 记号表示法定义：如果存在两个正常数 c 和 n₀，使得对所有的 n(n>=n₀)，有 T(n) <= c*f(n)，则：T(n)=O(f(n))。

最坏时间复杂度：指对于相同输入数据量的不同输入数据，算法时间用量的最大值。

平均时间复杂度：指对所有相同输入数据量的各种不同输入数据，算法时间用量的平均值。

常见的渐进时间复杂度（按时间效率从高到底）：O(1) > O(log₂n > O(n) > O(nlog₂n) > O(n²) > O(n³) > O(2ⁿ)。

空间复杂度

空间复杂度（Space Complexity）：指程序运行从开始到结束所需的存储量与问题规模的对应关系。记做：S(n)=O(g(n))。

空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度。一个算法在执行期间所需要的存储空间量应包括以下三个部分：

• 程序代码所占用的空间；
• 输入数据所占用的空间；
• 辅助变量所占用的空间；