数据结构和算法中的基本概念

数据结构中的基本概念

1. 数据：数据是对客观事物的符号表示，所有能被输入到计算机中，且能被计算机处理的符号的总称。如，整数、实数等都是数据。

2. 数据元素：是数据的基本单位，由数据项组成，如一本书为一数据元素，其中的作者，书名等信息为数据项。

3. 数据项：是数据结构中讨论的最小单位，是数据记录中最基本的，不可分的数据单位

4. 数据对象：数据对象是性质相同的的数据元素的集合，是数据的一个子集。

5. 数据结构：指相互之间存在一种或多种特定关系的数据元素的集合，包括3方面的内容：逻辑结构，存储结构，对数据的运算

6. 数据的逻辑结构：逻辑结构使对数据之间关系的描述，与数据的存储结构无关。可分为线性结构和非线性结构

   • 线性结构：一个数据元素有序的集合，有一下四个特征：
     集合中必须存在唯一一个“第一个元素”
     集合中必须存在唯一一个“最后一个元素”
     除最后一个元素外，其他数据元素均有唯一的“后继”
     除第一个元素外，其他元素均有唯一的“前驱”
   • 非线性结构：非线性结构中的节点存在一对多的关系，可以划分为树形结构和图形结构

7. 数据的物理结构：数据的物理结构又称为存储结构，是数据的逻辑结构在计算机中的映像。数据结构中有四种存储方式：顺序存储结构、链式存储结构、索引存储结构、散列存储结构

   • 线性存储结构：该方法把逻辑上相邻的结点存储在物理位置上相邻的存储单元里，结点间的逻辑关系由存储单元的邻接关系来体现。
   • 链式存储结构：该方法不要求逻辑上相邻的结点在物理位置上亦相邻，结点间的逻辑关系由附加的指针字段表示
   • 索引存储结构：该方法通常在储存结点信息的同时，还建立附加的索引表。索引项的一般形式是： (关键字、地址) 关键字是能唯一标识一个结点的那些数据项
   • 散列存储方法： 根据结点的关键字直接计算出该结点的存储地址。

算法中的基本概念

1. 算法：由基本的运算及运算顺序所构成的完整解题步骤，或者看成按照要求设计好的有限的确切的计算序列。
   算法有以下特性：

   • 有穷性：一个算法必须保证执行有限步后结束
   • 确切性：算法的每个步骤必须有确切的定义
   • 输入：一个算法有0个或多个输入
   • 输出： 一个算法有一个或多个输出
   • 可行性：算法中执行的任何计算步骤都是可以被分解为基本的可执行的操作步，即每个计算步都可以在有限时间内完成（也称之为有效性）

   算法的设计目标：

   • 正确性：算法能够正确的执行预先规定的功能要求
   • 可读性：要求算法易于人的理解
   • 健壮性：要求算法有很好的容错性，能够对不合理的数据进行检查
   • 高效率与低存储量需求：即时间复杂度和空间复杂度

2. 时间复杂度：将算法中基本执行的次数做为算法的时间复杂度
   ** T(n) = O(f(n)中增长最快的项/此项的系数)**
   常用的时间复杂度大小比较：
   O(1)≤O(log2n)≤O(n)≤O(nlog2n)≤O(n^2)≤O(n3)≤...≤O(n^k)≤O(2n)

3. 空间复杂度：一个算法在运行过程中临时占用存储空间大小的量度