第1章概述 自从1946年第一台计算机问世以来,计算机技术的发展日新月异。其应用已不再局限 科学计算,而是更多地用干控制、管理及数据处理等非数值计算的处理工作,与此相应,计 算机加工处理的对象由纯粹的数值发展到字符、表格和图像等各种具有一定结构的数据数 据结构就是研究数据组织、存储和运算的一般方法的学科。本章讨论数据结构的基本概念及 相关题解。 1.1基本概念 数据是信息的载体,在计算机科学中是指所有能输入到计算机中并由计算机程序处理 的符号的总称。 1.1.1数据结构 数据结构是指同一数据元素类中各数据元素之间存在的关系。数据结构又可以分为下 述三个组成部分,它们分别是数据的逻辑结构数据的存储结构和数据的运算 数据的逻辑结构是对数据之间关系的描述,所以有时就把数据的逻辑结构简称为数据 结构。逻辑结构形式上用一个二元组 B=(KR) 来表示,其中K是结点即数据元素的有限集合,即K是由有限个结点所构成的集合,R是K 上的关系的有限集合即R是由有限个关系所构成的集合而每个关系都是从K到K的关 系。设r是一个K到K的关系,r∈R,若k,k∈K,且<k,k>∈r,则称k是k的后续,k是 k'的前驱,这时k和k是相邻的结点(相对r而言);如果不存在一个k使<k,k>∈r,则 称k为r的终端结点;如果不存在一个k'使<k',k>∈r,则称k为r的开始结点;如果k既 不是终端结点也不是开始结点,则称k是内部结点。 数据的存储结构是数据的逻辑结构在计算机存储器中的实现,逻辑结构是从逻辑关系 上观察数据,它与数据的存储无关,即独立于计算机,而存储结构是依赖于计算机的计算机 存储器是由有限多个存储单元组成的,每个存储单元有唯一的地址,各存储单元的地址是连 续编码的每个存储单元Z都有唯一的后续单元Z=suc(Z),Z和Z’称为相邻单元。一片 相邻的存储单元的整体叫做存储区域,记做M。把B存储在计算机中,首先必须建立一个从 K的结点到M的单元的映象S:K→M即对于每一个k∈K,都有唯一的Z∈M使得S(k ZZ为K中结点所占存储空间中的起始单元。通常有四种基本的存储映象方法,即顺序方 法,链接方法、索引方法和散列方法 数据的运算是在数据的逻辑结构上定义的操作算法,如检索、插入、删除、更新和排序