数据结构

基础概念

  • 数据：描述客观失误的数值、字符、以及能输入机器且能被储存的各种符号集合

  • 数据元素：组成数据的基本单位，是数据集合的个体

  • 数据对象：数据对象是性质相同的数据元素的集合,是数据的一个子集。

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

  • 数据类型：数据类型是一-组性质相同的值集合以及定义在这个值集合上的–组操作的总称。

  • 抽象数据类型

    1. 数据的抽象

    2. 抽象数据类型ADT（abstract data type），包括数据对象、数据元素间的结构关系、操作三部分

    3. 最重要的特点：数据抽象和信息隐蔽

    4. 特征：使用与实现分离,实现封装和信息隐蔽,也就是说,在抽象数据类型设计时,类型的定义与其实现分离。

基本内容

  • 逻辑结构：

    1. 集合结构
    2. 线性结构
    3. 树状结构
    4. 图状/网状结构

  • 存储结构：

    1. 顺序存储（顺序映像）
    2. 非顺序存储（非顺序映像）

算法

  • 特征：
  1. 有限性
  2. 确定性
  3. 可行性
  4. 输入
  5. 输出

  • （1，2，3为最基本）

  • 要求：

    1. 正确性
    2. 可读性
    3. 健壮性（鲁棒性）
    4. 高效率，低存储

评价算法

  • 语句频度：一个语句重复执行的次数。一个算法的时间耗费就是算法中所有语句频度之和

  • 时间复杂度：算法中语句总执行次数f(n)和问题规模n的关系（仅关注数量级）

  • 渐进时间复杂度：和时间复杂度往往不加区分

  • 常见时间复杂度：
    O ( 1 ) , O ( n ) , O ( n 2 ) , O ( n 3 ) , O ( 2 n ) , O ( l o g 2 n ) , O ( l o g 2 n ) O(1), O(n) , O(n^2), O(n^3) , O(2^n) , O(log_{2}n), O(log_{2}n) O(1),O(n),O(n2),O(n3),O(2n),O(log2​n),O(log2​n)

  • 最坏时间复杂度：时间复杂度一般指最坏时间复杂度

结构化程序设计与函数的模块化设计

  • 结构化程序设计

    • 目的：以程序良好的静态结构来保证程序动态执行的正确性

    • 方法：

      1. 自顶向下，逐步求精
      2. 独立功能，一个入口，一个出口
      3. 仅用三种基本控制结构

面向对象与抽象数据类型

  • 面向对象 = 对象 + 类 + 继承 + 通信

  • 面向对象的概念

    • 对象：在应用事件中出现的各种实体、事件、规格说明，由一组属性和这组值上的一组服务构成的,其中属性值确定了对象的状态。

    • 类:把具有相同属性和服务的对象归到同一类,而把一个类中的每一个对象称为该类的一个实例,它们具有相同的服务。

    • 继承:面向对象方法的最有特色的方面。

    • 各个类的对象间通过消息进行通信。

  • 面向对象程序设计的特点是封装性(Encapsulation),继承性(Inheritance)和多态性( Polymorphism)。可以看出,与数据结构密切相关的是定义在数据结构上的一组操作。操作的种类和数目不同,即使逻辑结构相同,这个数据结构的用途也可能大不相同。定义在数据结构上的操作的种类是没有限制的,可以根据具体需要而定义。

  • 基本操作主要为：插入，删除，更新，查找，排序。操作可以分为两类：加工型（改变结构的值），引用型（不改变值）

  • 面向对象的开发方法首先着眼于应用问题所涉及的对象，包括对象、对象属性、要求的操作，从而建立对象结构和为解决问题需要执行的事件序列,据此建立类的继承层次结构,通过各个类的实例之间的消息连接实现所需的功能。类的定义充分体现了抽象数据类型的思想,基于类的体系结构可以把对程序的修改局部化,如果系统功能的需求发生变化，只需修改类中的服务即可,此时类所代表的对象基本不变,从而确保系统不致因修改而退化。

抽象数据类型

  • 基本原则：分解，抽象，信息隐藏

  • 一个抽象数据类型确定了一个模型，但是隐藏实现细节
    定义一组运算，但是隐藏运算的实现过程