1.1数据结构的基本概念

1.1.1 基本概念和术语

• 数据
  • 数据是信息的载体，是描述客观事物属性的数、字符及所有能输入到计算机中并被计算机程序识别 和处理的符号的集合。数据是计算机程序加工的原料。
• 数据元素、数据项
  • 数据元素是数据的基本单位，通常作为一个整体进行考虑和处理。
  • 一个数据元素可由若干数据项组成，数据项是构成数据元素的不可分割的最小单位。

• 数据对象
  • 数据对象是具有相同性质数据元素的集合，是数据的子集
  • 全国所有门店的排队顾客信息

• 数据类型

  • 数据类型是一个值的集合以及定义在此集合上一组操作的总称
    数据类型=数据元素+数据操作

  • 原子类型 eg:int

  • 结构类型 eg:结构体

  • 抽象数据类型ADT：只需关心逻辑结构，无需关心具体实现、存储结构

    ADT 抽象数据类型
    {
    数据对象（数据对象的定义）
    数据关系（数据关系的定义）
    基本操作（基本操作的定义）
    }ADT 抽象数据类型名
    

• 数据结构

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

1.1.2数据结构的三要素

• 数据的逻辑结构

  • 集合：数据元素同属一个集合，别无其他关系
    线性结构：一对一
    树：一对多
    图：多对多

  

• 数据的存储结构

  

• 知识点回顾

1.2 算法与算法评价

算法的特性

• 有穷性。一个算法必须总在执行有穷步之后结束，且每一步都可在有穷时间内完成。

• 确定性：相同输入得到相同输出。

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

• 输入：一个算法有零个或多个输入，这些输入取自于某个特定的对象的集合。

• 输出：一个算法有一个或多个输出，这些输出是与输入有着某种特定关系的量。

算法的时间复杂度

算法的空间复杂度