数据结构笔记

数据结构

（1）数据是对客观事物的符号表示，如图像、声音等。

（2）数据元素是数据的基本单位。

（3）数据项是构成数据元素的不可分割的最小单位。

一个数据元素可由若干个数据项组成，例如，一位学生的信息记录为一个数据元素，它是由学号、姓名、性别等数据项组成。

（4）数据对象是具有相同性质的数据元素的集合。

（5）数据结构是相互之间存在一种或多种特定关系的数据元素的集合。

数据结构包括三方面的内容：逻辑结构、存储结构和数据的运算。

数据结构的形式定义为：数据结构是一个二元组 Data_Structure=(D,S)

其中：D数据元素的有限集，S是D上关系的有限集。

逻辑结构是指数据元素之间的逻辑关系，与数据的存储无关，独立于计算机。

存储结构（物理结构）是指数据结构在计算机中的表示，它包括数据元素的表示和关系的表示。

顺序存储：把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中，元素之间的关系由存储单元的邻接关系来体现。

链式存储：借助指示元素存储地址的指针来表示元素之间的逻辑关系。

索引存储：在存储元素信息的同时，还建立附加的索引表。

散列存储：根据元素的关键字直接计算出该元素的存储地址，又称哈希（hash）存储。

算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中的每条指令表示一个或多个操作。此外，一个算法还具有下列个重要特性：

（1）有穷性。一个算法必须总是在执行有穷步后结束，且每一步都是在有穷时间内完成。

（2）确定性。算法中每条指令必须有确切的含义，且相同的输入只能得到相同的输出。

（3）可行性。算法中描述的操作都可以通过已经实现的基本运算执行有限次来实现。

（4）输入。一个算法有零个或多个输入。

（5）输出。一个算法有一个或多个输出。

通常设计一个“好”的算法应考虑达到以下目标：

（1）正确性。算法应能够正确地求解问题。

（2）可读性。算法能具有良好的可读性，以帮助人们理解。

（3）健壮性。输入非法数据时，算法能适当地做出反应或进行处理，而不会产生莫名其妙的输出结果。

（4）效率与低存储量需求。效率是指算法执行的时间，存储量需求是指算法执行过程中所需的最大存储空间。

算法效率的度量是通过时间复杂度和空间复杂度来描述的。

一个语句的频度是指该语句在算法中被重复执行的次数。

算法中所有语句的频度之和记为$T(n)$，它是该算法问题规模$n$的函数，时间复杂度主要分析$T(n)$的数量级。