数据结构

绪论

数据

数据(Data) ：是客观事物的符号表示。在计算机科学中指的是所有能输入 到计算机中并被计算机程序处理的符号的总称。
数据元素(Data Element) ：是数据的基本单位，在程序中通常作为一个整 体来进行考虑和处理。有时，一个数据元素可由若干数据项组成。
一个数据元素可由若干个数据项(Data Item)组成。数据项是数据的不可分 割的最小单位。是数据记录中最基本的。不可分的数据单位。
数据对象(Data Object)：是性质相同的数据元素的集合，是数据的一个子 集。如数组、链表等。

数据结构(Data Structure)：是指相互之间存在一种或多种特定关系的数据元 素的集合。数据结构包括3个方面：逻辑结构、存储结构和数据的运算。
逻辑结构是对数据之间关系的描述，与数据的存储结构无关。分为两大类：线性 和非线性。
数据元素之间的逻辑结构有四种基本类型：
① 集合：结构中的数据元素除了“同属于一个集合”外，没有其它关系。
② 线性结构：结构中的数据元素之间存在一对一的关系。
③ 树型结构：结构中的数据元素之间存在一对多的关系。
④ 图状结构或网状结构：结构中的数据元素之间存在多对多的关系。

物理结构/存储结构：是数据的逻辑结构在计算机中的表示（又称映像）。 物理结构是描述数据具体在内存中的存储
数据结构中常见的4种存储方式：
顺序存储：顺序存储方法是存储结构类型中的一种,该方法是把逻辑上相邻的结 点存储在物理位置上相邻的存储单元中,结点之间的逻辑关系由存储单元的邻接 关系来体现。由此得到的存储结构称为顺序存储结构,通常顺序存储结构是借助 于计算机程序设计语言(如C/C++)的数组来描述的。
链式存储：链式存储方法不要求逻辑上相邻的结点在物理位置上也相邻,结点间
的逻辑关系是由附加的指针字段表示的。由此得到的存储结构表示称为链式存 储结构,通常借助于计算机程序设计语言(如C/C++)的指针类型来描述它。

索引存储：索引存储方法在存储结点信息时除建立存储结点信息外,还建 立附加的索引表来标识结点的地址。索引项的一般形式是<关键字,地址> 关键字标识唯一一个结点,地址作为指向结点的指针

散列存储：散列存储方法的基本思想是根据结点的关键字通过散列函数直 接计算出该结点的存储地址。这种存储方法本质上是顺序存储方法的扩展。

算法

算法是由基本运算及规定的运算顺序所构成的完成的解题步骤，或者看成按照 要求设计好的有限的确切的计算序列。
算法的五个特征：
有穷性：指算法在执行有限的步骤之后，自动结束而不会出现无限循环， 并且每一个步骤在可接受的时间内完成。
确定性：算法的每一步骤都具有确定的含义，不会出现二义性。
可行性：算法中描述的操作都是可以通过已经实现的基本运算执行有限次 来实现。
输入：一个算法有零个或多个输入。 输出：一个算法有一个或多个输出。

算法设计要求

评价一个好的算法有以下几个标准：
正确性(Correctness )： 算法应满足具体问题的需求。
可读性(Readability)： 算法应容易供人阅读和交流。可读性好的算法有助于对 算法的理解和修改。
健壮性(Robustness)： 算法应具有容错处理。当输入非法或错误数据时，算法 应能适当地作出反应或进行处理，而不会产生莫名其妙的输出结果。
通用性(Generality)： 算法应具有一般性，即算法的处理结果对于一般的数据 集合都成立。

算法评估

1、事后统计法
比较不同算法对同一组输入数据的运行处理时间
缺陷：为了获得不同算法的运行时间必须编写相应程序。
运行时间严重依赖硬件以及运行时的环境因素；算法的测试数据的选取 相当困难。
事后统计法虽然直观，但是实施困难且缺陷多。
2、事前分析估算
依据统计的方法对算法效率进行估算 影响算法效率的主要因素：
算法采用的策略和方法；问题的输入规模； 编译器所产生的代码；计算机执行速度。