线性结构.doc

线性结构这里将讨论一些基本抽象数据类型——线性结构。所谓基本,只是相对而言,这些数据类型是最基本,最简单的,并且是实现其他抽象数据类型的基础。在下面的讨论中,首先我们将给出各种基本数据结构(ADT)的数学性质,然后在其数学模型上定义一组运算,最后将讨论如何利用基本的数据类型(数组、指针、记录等)来具体实现各种ADT。下面您将了解到以下常见的基本抽象数据类型的ADT操作以及这些操作用不同数据描述方法的具体实现:表的定义和性质一、表的定义表是由n(n≥0)个同一类型的元素(结点)a1,a2,…,an组成的有限序列。其中,元素的个数n定义为表的长度。当n=0时称为空表。当n≥l时,我们说元素ai位于该表的第i个位置,或称ai是表中第i个元素,i=1,2,…,n。根据各元素在表中的不同位置可以定义它们在表中的前后次序。我们称元素ai在元素ai+1之前或ai是ai+1的前驱(i=1,2,…,n-1)。同时,我们也称元素ai+1在元素ai之后,或ai+1是ai的后继。另外,称a1为表头(head),an为表尾(tail)。由于表的元素具有线性性质,所以又称为线性表。表是程序设计中使用得最频繁的一种ADT,也是实现其他许多ADT的基础。二、表的性质从表的定义不难看出表具有以下数学性质:除了表头和表尾外,表中的每一个元素有且仅有唯一的前驱和唯一的后继,表头有且只有一个后继,表尾有且只有一个前驱。注意:表和数组的区别从概念上来看,表是一种抽象数据类型;数组是一种具体的数据结构。从数学性质上来看,表是一个二元关系R,<x,y>∈R当且仅当x是y的前驱;如果将该二元关系用关系图(将每一个元素用一个点来表示,若x与y有关系则从x到y连一条有向线段)来表示,则得到的是一条单链a1→a2→…→an,因此表也可以看成是特殊的图或特殊的树(每个节点有且仅有一个子节点);而数组是从1..n的自然数集合到数组元素集合的一一映射,其中n是数组的长度,1..n中每一个自然数唯一地对应着一个数组元素,反之亦然。所以数组可以用来实现映射。从物理性质来看,数组中相邻的元素是连续地存储在内存中的,或者对于程序员来说可以认为它们是连续地存储在内存中的,数组的存取对程序员来说是透明的;表只是一个抽象的数学结构,并不具有具体的物理形式,表需要通过其它有具体物理形式的数据结构来实现。在表的具体实现中,表中相邻的元素不一定存储在连续的内存空间中,除非表是用数组来实现的。对于数组,可以利用其下标在一个操作内随机存取任意位置上的元素;对于表,只能根据当前元素找到其前驱或后继,因此要存取第i个位置上的元素,一般不能在一个操作内实现,除非表是用数组实现的。在实现表时需要提供足够的信息以便能够通过表中元素的位置p来存取表中的元素。表中元素的位置p是指示表中元素位置的信息,通过对p进行处理(可能是从事某种函数运算计算出该元素在内存中的位置,也可能从表头开始,依次寻找当前元素的后继,重复i次找到第i个位置的元素)可以得到表中元素在内存中的物理位置,因此不能简单地将位置p理解为类似数组下标的自然数,实际上p可以是各种类型的变量,在数学上可将p定义为一个偏序集上的变量。在具体实现表及其运算时,应区分p与p所表示的位置,以及该位置上的元素三者之间的不同含义。ADT表的操作表是一种非常简便的结构,我们可以根据需要改变表的长度,也可以在表中任何位置对元素进行访问、插人或删除等操作。我们还可以将两个表连接成一个表,或把一个表拆成几个表。表的结构在信息检索,程序设计语言的编译等许多方面有广泛的应用。在表的数学模型上,我们还要定义一组运算,才能使这一数学模型成为一个抽象数据类型表即ADT表。下面我们将给出一组典型的表运算。其中L是由类型为TElement的元素组成的一个表。x表示一个元素,p表示元素在表中的位置,其类型为TPosition。在表的不同实现方式下,TPosition可能有不同的类型定义,作为位置变量的p也可能有不同的含义。但是TPosition必须是一个偏序集,即任何两个TPosition类型的变量x,y之间可以进行比较运算,且结果只有x>y,x<y,x=y,x>=y,x<=y五种。下面我们将ADT表看作一个抽象类TList,L是该类的一个实体,ADT表的操作将定义成L的属性和方法。,我们假定表L的结束元素an之后还有一个位置,用属性end的值来表示这个位置。该属性的值为TPosition类型。,我们假定表L的开始元素a1之前还有一个位置,该为值称为哨兵位置,该位置上的元素称为哨兵元素,用属性Piquet的值来表示这个位置。该属性的值为TPosition类型。,其值为表L中第一个元素的位置。当L为空表时,值