408

一、概述

基本概念（以一份excel表格为例）

  • 数据

    • 有含义的数字、字符及符号（要求能被计算机识别和处理）的集合。
    • 也即整份 excel 中的全部内容

  • 数据元素

    • 数据的基本单位
    • 由若干数据项组成
    • 通常作为一个整体进行考虑和处理
    • 也即 excel 表中的一行

  • 数据项

    • 构成数据元素的不可分割的最小单位
    • 也即 excel 表中的一个单元格

  • 数据对象

    • 具有相同性质的数据元素的集合
    • 是数据的一个子集
    • 对 excel 表进行筛选操作，筛选出来的所有行可构成一个数据对象

  • 数据类型

    • 书上抽象的描述如下：

      1
      数据类型是一个值的集合和定义在此集合上的一组操作的总称
      • 说白了就是按种类划分，int是一个整数种类，它有它自己的取值范围；double也是一个种类，有它自己的取值范围；而任意一个结构体类型也自成一个种类；可以简单将基本数据类型理解为”姓名“、”年龄“、”身高“等听上去比较单纯的属性，将结构体理解为”学生“等听上去比较复杂的属性（复杂在学生还可以划分出”学号“、”学校“、”“学院”、年级“、”班级“等单纯属性）

    • 原子类型

      1
      其值不可再分的数据类型
      • 这个描述有些问题，但可以简单理解为上面说的比较单纯的属性，或者在408里可以直接当作基本数据类型如 int、double、float等类型的集合

    • 结构类型

      1
      其值可以再分的数据类型
      • 可以简单理解为上面说的比较复杂的属性

    • 抽象数据类型（ADT）

      1
      2
      一个数学模型及其定义在该数学模型上的一组操作。它通常是对数据的某种抽象，定义了数据的取值范围及其结构形式，以及对数据操作的集合。
      抽象数据类型侧重于描述数据的逻辑结构和操作接口，而不涉及具体的实现细节。它定义了数据类型的一组数据元素和可以对这些数据元素进行的操作，但不描述这些操作是如何实现的。

      • 根据上述定义，栈、队列、列表等均属于抽象数据类型

        1
        2
        3
        4
        5
        6
        7
        以栈为例（这里方便起见，用 C++ 中STL容器中的 stack 来进行说明）
        我们任取一个栈 stack<int>，则：
        栈中元素的取值范围：同 int 型变量的取值范围
        栈中元素的结构形式：
        	1、线性结构
        	2、后进先出
        	3、采用顺序存储或链式存储

数据结构三要素

  • 逻辑（结构）

    • 用于表示元素之间的逻辑关系（逻辑关系是抽象出来的 如果你不够抽象，请移步孙吧学习）
    • 与数据的存储无关（表现为数据的存储位置、存储方式都不会影响元素间的逻辑关系，甚至于如果将存在于你幻想中的对象和存在于现实中的你抽象成两个数据元素的话，即使存在方式不同，也不会影响你们之间一对一（或许是一对多？）且单向连接的逻辑关系）
    • 逻辑结构分为线性结构和非线性结构
      • 线性结构包括：线性表（408也就考到这，其他的就不列了）
      • 非线性结构包括：树、图、集合（集合可以忽略掉）

  • 存储（结构）

    • 是数据结构在计算机中的表示（或称映像），也可以叫做物理结构
    • 可以看作用计算机语言实现的逻辑结构，或者简单理解为我们在编写程序的时候，想要将数据以什么方式存起来
    • 主要包括：顺序存储（一般由数组实现），链式存储（要借助指针实现），索引存储（不会），散列存储（也叫哈希，后面的章节会提到）

  • 运算

    • 包括运算的定义和运算的实现
    • 定义针对逻辑结构，如栈的入栈、出栈、取栈顶元素、判空等操作均叫做栈的运算
    • 实现针对存储结构，如顺序栈（顺序存储的栈）和链栈（链式存储的栈）的相同操作（出入栈等）实现时的具体步骤不同