1.3数据结构的基本概念
数据（Data）:是对客观事物的符号表示，在计算机科学中是指能输入到计算机并被计算机程序处理的符号的总称。 数据一般可分为数值数据、文本数据、图形图像数据和音响数据等。数据元素（Data Element）:是数据的基本单位，也可以称为结点，在计算机程序中通常作为一个整体进行考虑。 数据元素一般由若干数据项（Data Item）组成，数据项是构成数据元素最小的、不可分割的单位。数据处理（Data Process）:对数据进行检索、插入、删除、合并、拆分、排序、统计、计算、转换、输入、输出等的操作过程。数据结构（Data Structure）: 相互之间存在一定关系的数据的集合。 是数据及其元素之间相互关系的表示。逻辑结构：数据元素之间一般存在某种特定的关系，这种关系称为数据的逻辑结构。物理结构（存储结构）：数据结构在计算机内存中的表示形式。包括数据元素的表示和其关系的表示。顺序的方法： 用一块无空隙的存储区域存储数据称为顺序存储 顺序存储把一组结点存储在按地址相邻的顺序存储单元里，结点间的逻辑后继关系用存储单元的自然顺序关系来表达链接的方法： 利用指针，在结点的存储结构中附加指针字段称为链接法。两个结点的逻辑后继关系可以用指针的指向来表达 任意的逻辑关系，也可以使用这种指针地址来表达。一般的做法是将数据结点分为两部分: 数据字段 指针字段数据类型： 数据类型（Data Type）: 数据类型显式或隐含地规定了: 在程序执行期间变量或表达式所有可能的取值范围，以及在这些值上允许执行的操作。 即数据类型是一个值的集合和定义在这个值集上的一组操作的总称。1.4算法及其特性
算法： 是为了求解问题而给出的有限的指令序列，每条指令表示一个或多个操作。——解决问题的步骤程序： 是算法的一种实现，计算机按照程序逐步执行算法，实现对问题的求解。性质： 有穷性：一个算法必须能在执行有穷步之后结束，且每一步都可在有穷时间内完成； 确定性：算法中每一条指令必须有确切的含义，不具有二义性。 可行性：算法中描述的操作都可通过已经实现的基本运算执行有限次来实现。 输入：一个算法有零个或多个输入，这些输入取自某个特定的对象的集合； 输出：一个算法有一个或多个输出，这些输出是同输入具有某种特定关系的量。描述： 算法设计者在构思和设计了一个算法之后，必须清楚准确地将所设计的求解步骤记录下来，即描述算法。 常用的描述算法的方法有 -自然语言 -流程图 -程序设计语言 -伪代码等。算法分析： 解决同一个问题总是存在着多种算法，而算法设计者在所花费的时间和所使用的空间资源往往要两者之间采取折中，通常是采用某种以空间资源换取时间资源的策略 算法设计者可以通过算法分析，判断所提出的算法是否现实，分析算法的效率以求改进 算法分析的内容 算法运行所需要的时间，称为时间复杂性 事前估计法 事后统计法 算法运行所需要的辅助空间，称为空间复杂性事前估算法 — 时间复杂度估计： 算法的执行时间(所有语句的语句频度之和） T（n）=n+1+n（n+1）+n2=2n+2n2+1 问题规模：求解问题的输入量 lim T（n）/n2=lim(2n+2n2+1)/2n2=1 n－>∞ 当问题规模 n→∞时T(n)与某一量同阶,称作算法的渐近时间复杂度。 记作：T(n)=O(n2) O是order的简写 n 程序的执行时间: ∑ 语句 i 的执行次数×执行时间 i=1 语句频度:语句重复执行的次数 由于算法实际执行的操作往往依赖于分支条件的走向，而输入数据的取值又影响这些分支走向，因此很多算法都无法得出独立于输入数据的渐近估计。 针对这一情况，提出了最好情况估计、最坏情况估计、平均情况估计。 如： int Find(int A[], int n，int k){ for(i=0;i<n;i++) if(A[i]==k) break; return i; }算法执行时间分析： 如果数组的第一个元素恰好就是 k ，算法只要比较一个元素就行了，这是 最好情况 （最乐观的估计）； 如果数组的最后一个元素是 k ，算法就要比较 n 个元素，这是 最坏情况 （最悲观的估计）； 如果在数组中查找不同的元素 k ，假设数据是等概率分布，则平均要比较 n /2 个元素，这是 平均情况
算法的空间复杂度： 算法的空间复杂度是指在算法的执行过程中，需要的辅助空间数量。 辅助空间是除算法本身和输入输出数据所占据的空间外，算法临时开辟的存储空间。通常记作： S ( n ) = O ( f ( n )) 其中， n 为问题规模，分析方法与算法的时间复杂度类似。