绪论

数据结构是指相互之间存在着一种或多种关系的数据元素的集合和该集合中数据元素之间的关系组成。数据结构包括三个方面的内容，数据的逻辑结构，数据的存储结构和数据的运算。数据的逻辑结构和存储（物理）结构是密不可分的两个方面，一个算法的设计取决于所选定的逻辑结构，而算法的实现依赖于所采用的存储结构。 ## 一.数据结构的三要素 ### 1.1数据的逻辑结构 数据的逻辑结构是指数据元素之间的逻辑关系，即从逻辑关系上描述数据，它与数据的存储无关，独立于计算机。 常见的逻辑结构主要分为线性关系和非线性关系，其中线性表是典型的线性结构；集合，二叉树，图时典型的非线性结构 - 线性结构：数据结构中的元素存在一对一的相互关系； - 树形结构：数据结构中的元素存在一对多的相互关系； - 图（网）状结构：数据结构中的元素存在多对多的相互关系 ### 1.2数据的存储（物理）结构 数据的存储结构是指数据结构在计算机中的表示（又称映像），也称为物理结构。它包括数据元素的表示和关系的表示。数据的存储结构是逻辑结构用计算机语言的实现，依赖于计算机语言。 常见的物理结构主要有：顺序存储，链式存储，索引存储和散列存储。 - 顺序存储：把逻辑上相邻的元素存储在物理位置相邻的存储单元里，元素间的逻辑关系由存储单元的邻接关系来体现，由此得到的存储表示称为顺序存储结构。顺序存储结构是一种最基本的存储表示方法，通常借助于程序设计语言中的数组来实现。 优点是可以实现随机存取，每个元素占用最少的存储空间； 缺点是只能使用相邻的一整块存储单元，因此可能产生较多的外部碎片。 - 链接存储：不要求逻辑上相邻的元素在物理位置上亦相邻，元素间的逻辑关系是由附加的指针字段表示的。由此得到的存储表示称为链式存储结构，链式存储结构通常借助于程序设计语言中的指针类型来实现。 优点是不会出现碎片现象，充分利用所有存储单元； 缺点是每个元素因存储指针而占用额外的存储空间，并且只能实现顺序存取。 - 索引存储：在存储元素信息的同时，还建立附加的索引表来标识元素的地址。索引表中的每一项称为索引项，索引项的一般形式是：（关键字，地址）。 优点是检索速度快； 缺点是增加了附加的索引表，会占用较多的存储空间，此外，在增加和删除数据时要修改索引表，因此会花费较多的时间。 - 散列存储：根据元素的关键字直接计算出该元素的存储地址，又称为Hash存储。 优点是检索，增加和删除元素的操作都很快； 缺点是如果选择的散列函数不当，会造成元素存储单元的冲突，而解决冲突又会增加额外的时间和空间开销。 ### 1.3数据的运算 施加在数据上的运算包括运算的定义和实现。运算的定义是针对于逻辑结构的，指出运算的功能；运算的实现时针对于存储结构的，指出运算的具体步骤。 ## 二.数据结构三要素小结 如下图所示：  ## 三.算法 ### 3.1算法的基本概念 算法（Algorithm）是对特定问题求解步骤的一种描述，是指令的有限序列，其中每一条指令表示一个或多个操作。 ### 3.2算法的特性 1. 有穷性：一个算法必须总是（对于任何合法的输入值）在执行有限步骤后结束，且每一步都可在有穷时间内完成。 1. 确定性：算法的每一条指令必须有确切的含义，读者理解时不会产生二义性。即对相同的输入只能得到相同的输出。 1. 可行性：一个算法是可执行的，即算法中描述的操作都可以通过已经实现的基本运算执行有限次来实现（也称之为有效性）。 1. 输入：一个算法有零个或多个输入，这些输入取自某个特定的对象的集合。 1. 输出：一个算法有一个或多个输出，这些输出是同输入有着某种特定关系的量。 ### 3.3算法的目标 1. 正确性：算法应当能够正确的解决所需求解的问题。 1. 可读性：算法应当具有良好的可读性，以助于人们理解。 1. 健壮性：当输入非法数据时，算法也能适当的做出反应或进行处理，而不会产生莫名其妙的输出结果。 1. 效率与低存储量需求：效率是指算法执行的时间，存储量是指算法执行过程中所需的最大存储空间，这两者均与问题的规模有关。 ### 3.4算法效率的度量 算法效率的度量时通过时间复杂度和空间复杂度来描述的。 ### 3.4.1时间复杂度 算法的时间复杂度是指算法需要消耗的时间资源。一般来说，计算机算法是问题规模n的函数f(n)，算法的时间复杂度也因此记做T(n)=O(f(n)),算法执行时间的增长率与f(n)的增长率正相关，称作渐近时间复杂度，简称时间复杂度。 这里应该注意到时间复杂度有三种： - 最坏时间复杂度：最坏情况下，算法的时间复杂度； - 平均时间复杂度：所有可能输入实例在等概率出现的情况下，算法的期望运行时间； - 最佳时间复杂度：在最佳情况下，算法的时间复杂度。 此处应该注意，我们一般所说的时间复杂度其实是指最坏时间复杂度。 在考虑一个算法的时间复杂度时，有以下两条规则： > a) 加法规则 T(n)=T1(n)+T2(n)=O(f(n))+O(g(n))=O(max(f(n),g(n))) b) 乘法规则 T(n)=T1(n)×T2(n)=O(f(n))×O(g(n))=O(f(n)×g(n)) 常见的渐近时间复杂度有： > O(1) ';