第 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 笼统数据类型名

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

根本操作名(参数表)
  初始条件:<初始条件描绘>
  操作成果:<操作成果描绘>

根本操作有两种参数:

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

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

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

下一节