第 1 章 序言

2022.9.5

这是数据结构第一次课，介绍了序言的前两节内容，即导言和数据结构相关的根本概念和术语

1.1 导言

数据结构是什么？

“Algorithms + Data Structure = Programs”

— Niklaus Wirth

  • 程序 = 算法 + 数据结构（出自 Niklaus Wirth，PASCAL 之父，图灵奖得主）

数据结构与算法相得益彰，共同组成程序：

  • 数据结构重视数据在计算机中怎么有效地安排起来。
  • 算法重视数据怎么通过运算解决问题。

数据在计算机中的表明、存储和操作

冯诺依曼体系结构是现代计算机的基础，计算机由控制器、运算器、存储器、输入设备、输出设备五部分组成：

Ch1 绪论 (1) | 数据结构

依照与 CPU 的挨近程度，存储器分为内存储器与外存储器，简称内存与外存：

Ch1 绪论 (1) | 数据结构

CPU 与内存之间由地址总线和数据总线衔接：

Ch1 绪论 (1) | 数据结构

操作系统为每一个进程供给了一个假象，好像每个进程都在独占地使用主存。每个进程看到的存储器都是一致的，称之为虚拟地址空间。

  • 32 位系统虚拟地址空间为 4GB
  • 如地址 0x00CC0000 便是一个 8 位 16 进制数

Ch1 绪论 (1) | 数据结构

例如 Linux 进程内存地址空间：

Ch1 绪论 (1) | 数据结构

  • Text segment ：代码段（贮存程序的二进制机器码）
  • Data segment ：初始化的全局变量、静态变量等
  • BSS segment ：未初始化的全局变量和静态变量
  • Stack ：函数调用时，局部变量、参数值和回来值
  • Heap ：运行时内存分配，如 malloc 函数分配的内存

接下来老师在 CLion 中用单步调试演示了内存中数据存储的办法和指针类型的操作。

1.2 根本概念和术语

根本术语

数据（data）：信息的载体，被计算机辨认、存储和加工处理的目标。

数据元素（data element）：数据的根本单位，是数据调集中的一个个别，一个数据元素可由若干个数据项组成。

数据项（data item）：具有独立意义的标识单位，是数据不可分割的最小单位。

数据目标（data object）：性质相同的数据元素的调集，是数据的一个子集。（某种数据类型元素的调集）

数据目标可所以有限的，也可所以无限的。

例：整数的数据目标是无限的；英文字符类型的数据目标是有限的

数据结构（data structure）：相互之间存在着一种或多种特定联系的数据元素的调集。

结构（structure）：数据元素之间的联系，可以看作是从具体问题笼统出来的数学模型，与计算机无关，与数据的存储无关，也叫做逻辑结构

逻辑结构

逻辑结构可用一个二元组表明：

Data_Structure=(D,S){\rm Data\_Structure} = (D, S)

DD ：数据元素的有穷调集；SS ：D 上联系的有穷调集

Ch1 绪论 (1) | 数据结构

根据数据元素间联系的不同特性，数据的逻辑结构常分为以下四类：

Ch1 绪论 (1) | 数据结构

  • 调集结构（数据元素同归于一个调集）
  • 线性结构（数据元素之间存在一对一联系）
  • 树形结构（数据元素之间存在一对多联系）
  • 图形结构（数据元素之间存在多对多联系）

存储结构

存储结构（物理结构）是指数据结构在计算机中的映像表明。

数据元素的映像

  • 每个数据元素的映像称为结点（node）
  • 每个数据项的映射称为数据域（data field）

联系的映像

最常用的是两种根本办法：

  • 顺序：以相对的存储位置表明联系（逻辑相邻即为物理相邻）
  • 链式：以附加信息（指针）表明联系（逻辑相邻但一般不物理相邻）

数据存储的两种常用结构

顺序存储：数据元素依次放在连续的存储单元中

例如：数组

链式存储：在存储结点中增加若干指针域，记载后继或者相关结点的地址（指针）

例如：链表

运算（操作）

运算（操作）是在数据逻辑结构上界说的一组数据被使用的办法，其具体完成要在存储结构上进行。

几种常用的运算：

  • 树立数据结构
  • 铲除数据结构
  • 插入数据元素
  • 删除数据元素
  • 排序
  • 检索*
  • 更新
  • 判空和判满*
  • 求长*

带 * 操作为引证型操作，即数据值不发生改变；
其他为加工型操作。

Ch1 绪论 (1) | 数据结构

笼统数据类型

数据类型（data type）：最早在程序设计语言中表明变量所具有的数据种类，是一个值的调集和界说在这个值上的一组操作的总称。

例1 在 C 语言中，数据类型分为根本类型和构造类型

根本类型：整型、浮点型、字符型
构造类型：数组、结构、联合、指针、枚举、自界说

例2 在 Python 语言中除布尔、整数、浮点外还有字符串、列表、元组、字典等类型

笼统数据类型 ADT（Abstract Data Type）

笼统数据类型是数据类型概念的引申，指一个数学模型以及在其上界说的操作调集，与计算机无关。实际上便是对该数据结构的界说。由于它界说了一个数据的逻辑结构以及在此结构上的一组算法。

笼统数据类型可以用三元组表明：

(D,S,P)(D,S,P)

DD ：数据目标；SS ：D 上的联系集；PP ：D 的根本操作集

笼统数据类型的描绘办法

ADT 笼统数据类型名 {
    数据目标：<数据目标的界说>
    数据联系：<数据联系的界说>
    根本操作：<根本操作的界说>
}ADT 笼统数据类型名

其中根本操作的界说格局为：

根本操作名（参数表）
  初始条件：<初始条件描绘>
  操作成果：<操作成果描绘>

根本操作有两种参数：

  • 赋值参数 只为操作供给输入值
  • 引证参数 除可供给输入值外，还将回来该参数值在操作后的改变成果

初始条件 描绘了操作履行之前数据结构和参数应满意的条件，若不满意，则操作失败，并回来相应出错信息

操作成果 说明晰操作正常完成之后，数据皆否的改变情况和应回来的成果

下一节