1.数据结构--基本概念和术语

数据结构基本概念和术语

基本概念

• 数据(data): 对客观事物的符号表示,在计算机科学中指所有能输入到计算机中并被计算机程序处理的符号的总称;
• 数据元素(date element): 数据的基本单位,在计算程序中通常作为一个整体进行考虑和处理,有时,一个数据元素可由若干个数据项(data item)组成; 如:一本书的数目信息为一个数据元素, 而书目信息的每一项(书名、作者名等)为一个数据项, 数据项是数据不可分割的最小单位.
• 数据对象(data object): 是性质相同的数据元素的集合,是数据的一个子集;
  如:整数数据对象N = {0, ±1, ±2, ±3, …},字母字符数据对象C = {‘A’, ‘B’, ‘C’, …, ‘Z’}
• 数据结构(data structure): 是相互之间存在的一种或者多种特定关系的数据元素的集合.(通常有四类基本结构)
  
  • 集合: 结构中的数据元素除了”同属于一个集合”的关系外,别无其他关系;
  • 线性结构: 结构中的数据元素之前存在一对一关系
  • 树形结构: 结构中的数据元素之间存在一对多关系
  • 图状或网状结构: 结构中的数据元素存在多对多关系

基本结构图示

数据结构的形式定义为:数据结构是一个二元组 Data_Structure = (D,S),其中:D是数据元素的有限集,S是D上关系的有限集.

例: 在计算机科学中,复数可取如下定义:复数是一种数据结构Complex = (C, R)其中,C是含两个实数的集合{c1, c2}; R = {P},而P是定义在集合C上的一种关系{

数据元素之间的关系

• 逻辑结构与存储结构
  
  • 逻辑结构: 描述的是数据元素之间的逻辑关系,因此又称为数据的逻辑结构
  • 存储结构: 数据结构在计算机的表示(又称映像)称为数据的物理结构,又称存储结构,它包括数据元素的表示和关系的表示. 在计算机中表示信息的最小单位是二进制数的一位,叫做位(bit). 在计算机中,我们可以用一个由若干位组合起来形成的一个位串表示一个数据元素,通常称这个位串为元素(element)或者结点(node). 当数据元素由若干个数据项组成时,位串中对应于各个数据项的子位串成为数据域(data field).因此,元素或者节点可以看成是数据元素在计算机中的映像.数据元素之间的关系在计算机中有两种不同的表示方法:顺序映像和非顺序映像,并有此得到两种不同的存储结构:顺序存储结构和链式存储结构
    
    • 顺序映像:借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系.
    • 非顺序映像:借助指示元素存储地址的指针(pointer)表示数据元素之间的逻辑关系

数据的逻辑结构和物理结构是密切相关的两个方面, 任何一个算法的设计取决于选定的数据(逻辑)结构.而算法的实现依赖于采用的存储结构.

数据类型

• 数据类型(data type): 一个值的集合和定义在这个值集上的一组操作的总称(例如,C语言中的整型变量,其值集为某个区间上的整数),定义在其上的操作为加减乘数模运算等算术运算),按”值”的不同特性,高级程序语言中的数据类型可分为两类:
  
  • 非结构的原子类型: 原子类型是不可分解的.例如:C的基本类型(整型,实型,字符型和枚举类型)、指针类型和空类型.
  • 结构类型: 结构类型的值是由若干成为按照某种结构组成的,因此是可以分解的,并且它的成分可以是非结构的,也可以是结构的. 例如:数组的值由若干分量组成,每个分量可以是整数,可以是数组等.在某种意义上,数据结构可以看成是”一组具有相同结构的值”,则数据结构可以看成由一种数据结构和定义在其上的一组操作组成.
  • 抽象数据类型(Abstract Data Type, ADT): 指一个数学模型及定义在该模型上的一组操作.抽象数据类型的定义仅取决于它的一组逻辑特性,而与其在计算机内部表示和实现无关,即无论其内部结构如何变化,只要它的数学特性不变,都不影响其外部的使用.

抽象数据类型

一个含抽象数据类型的软件模块通常应包含”定义,表示和实现“3个部分
抽象数据类型的定义由一个值域和定义在该值域的一组操作组成.若按照其值的不同特性,可分为3种类型

• 原子类型(atomic data type)属原子类型的变量的值是不可分解的.这类抽象数据类型较少,因为一般情况下,已有的固有数据类型足以满足需求,但有时也有必要定义新的原子数据类型,例如整位为100的整数;
• 结构类型
  
  • 固定聚合类型(fixed-aggregate data type)属该类型的变量,其值由确定数目的成分按某种结构组成.例如,复数是两个实数依确定的次序关系组成.
  • 可变聚合类型(variable-aggregate date type)和固定聚合类型相比较,构成可变聚合类型”值”的成分的数目是不确定.例如,可定义一个”有序整数序列”的抽象数据类型,其中序列的长度是可变的.固定聚合类型与可变聚合类型可以统称为
• 多形数据类型(polymorphic data type)是指其值的成分不确定的数据类型,抽象数据类型中,不论其元素具有何种特性,元素之间的关系相同,基本操作也相同,从抽象数据类型的角度看,具有相同的数学抽象特性,故称之为多形数据类型.

和数据结构的形式定义相对应,抽象数据类型可用以下三元组表示(D, S, P)
其中D是数据的对象,S是D上的关系集,P是对D的基本操作集

定义抽象数据类型

ADT抽象数据类型名 {
    数据对象:<数据对象的定义>
    数据关系:<数据关系的定义>
    基本操作:<基本操作的定义>  
}ADT抽象数据类型名

其中,数据对象和数据关系的定义用伪代码描述,基本操作的定义格式为

基本操作名(参数表)  -->  赋值参数只为操作提供输入值;引用参数以&打头,除可提供输入值外,还将返回操作结果.
    初始条件:<初始条件描述>  -->  描述操作执行之前数据结构和参数应满足的条件,若不满足,则操作失败,返回对应出错信息,
    操作结果:<操作结果描述>  -->  操作结果说明了操作正常之后,数据结构变化状况和应返回的结果,若初始条件为空,则省略之