数据结构的术语

• 数据(Data)：信息
• 数据元素(Data Element)：数据的基本单位，由若干数据项组成。
• 数据项(Data Item)：具有独立含义的最小单位。
• 数据对象(Data Object)：元素的集合
• 数据结构(Data Structure)：三要素（逻辑结构、存储结构、数据运算：增、删、改、查）
• 逻辑结构：数据元素之间的关系（逻辑结构形式上用二元组，B=（K,R），K是结点的集合，R是K上关系的集合，例如<k,k’>代表k是k’前驱，k’是k的后继，为相邻结点）。
• 逻辑结构：分为线性结构和非线性结构，逻辑结构独立于存储结构。
  （1）线性结构：有且只有一个开始结点和一个终端结点，并且所有结点都最多只有一个直接前驱和一个直接后继(1对1),典型的有：线性表、栈、队列、数组、串。
  （2）非线性结构：每个结点可以有不止一个直接前驱和直接后继(非1对1)，典型的树、图、集合。
• 存储结构：数据元素及其逻辑结构在计算机中的表示，存储结构是逻辑关系的映象与元素本身的映象，存储结构实质上是内存分配。
• 存储结构：分为顺序存储结构、链式存储结构、索引存储方式、散列存储方式。
  （1）顺序存储结构把逻辑上相连的结点存储在物理位置上相邻的存储单元里，结点间的逻辑关系由存储单元的邻接关系来体现。一般采用数组或者结构体数组来描述。
  （2）链式存储结构不要求逻辑上相邻的结点，在物理位置上相邻，结点间的逻辑关系由附加的引用字段表示。一个结点的引用字段往往指向下一个结点的存放位置。一般采用链表来描述。
  （3）索引存储方式是采用附加的索引表的方式来存储节点信息的一种存储方式。索引表由若干索引项组成。索引项的一般形式为(关键字、地址)。其中，关键字是能够唯一标识一个节点的数据项。
  （4）散列存储方式根据结点的关键字通过散列函数直接计算出该结点的存储地址。
• 逻辑和存储的搭配
  （1）线性结构：顺序存储，链式存储
  （2）非线性结构：多种存储方式
• 数据类型(Data Type)：类型
• 抽象数据类型 (Abstract Data Type，ADT)：模型、类型
• 非结构原子型： 原子类型的值是不可分解的。C语言中的标准类型（整型、实型、字符型、枚举型）及指针和空类型。
• 结构类型：结构类型的值是由若干成分按某种结构组成的，因此是可以分解的，并且它的成分可以是原子型或结构型。C语言中的数组、结构体、共用体。
• 算法特性
  （1）有限性：算法必须在执行有穷步之后结束，而每一步都必须在有穷时间内完成。
  （2）确定性：算法中每一步操作的含义都必须是确定的，不能有二义性。
  （3）输入：一个算法可以有零个或多个输入。
  （4）输出：一个算法有一个或多个输出。
  （5）可行性：一个算法必须是可行的，即算法中每一操作都能通过已知的一组基本操作来实现。
• 算法目标
  （1）正确性(Correctness) ：算法应当能够正确的解决求解问题
  （2）可读性(Readability) ：良好的可读性，有助于人理解
  （3）健壮性(Robustness) 、鲁棒性(Robustness) ：非法输入时，算法可以适当的做出反应
  （4）高效性(Efficiency)：不错的效率和低存储
• 时间复杂度(time complexity)，时间复杂度依赖于问题规模，和数据的初始状态。
  （1）算法执行时间 ：一个算法的执行时间大致上等于其所有语句执行时间的总和，对于语句的执行时间是指该条语句的执行次数和执行一次所需时间的乘积。
  （2）语句频度：指该语句在一个算法中重复执行的次数，算法中所有语句频度之和记作T(n)，基本运算（最深层循环内的语句）频度为f(n)，T(n)=O(f(n)) 表示随问题规模n的增大，算法的执行时间的增长率和f(n)的增长率相同，称作算法的渐进时间复杂度，简称时间复杂度,所以算时间复杂度相当于基本运算频度。
  选取T(n)=O(f(n))中增长速度最快的项，且系数得写1，如果f(n)跟n没有关系时，即频度是个常量，即可以明确表示的数字时，写O(1)。 规则：一般计算最深层循环内的语句频度，
  1）T(n)=T1(n)+T2(n)=O(f(n)+g(n))=O(max(f(n),g(n))
  2）T(n)=T1(n)*T2(n)=O(f(n)*g(n))=O(f(n)*g(n))
  常用的时间复杂度：O(1) <O(log2n) < O(n) < O(n log2n) < O(n2) < O(n3) < O(2n) < O(n!) < O(nn)
• 空间复杂度(space complexity)
  采用空间复杂度作为算法所需存储空间的度量S，记作： S(n)=O(f(n)) ，其中，n为问题的规模，O表示数量级。
  对于输入数据所占的具体存储量只取决于问题本身，与算法无关。因此，只需分析算法在实现时所需辅助空间即可。若所需辅助空间相对于输入数据而言是个常数，则称该算法为原地工作，辅助空间为O(1) 。

谢谢阅读。

文章来源: blog.csdn.net，作者：WongKyunban，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/weixin_40763897/article/details/103275771