《线性结构Word版》由会员分享，可在线阅读，更多相关《线性结构Word版（63页珍藏版）》请在金锄头文库上搜索。
1、线性结构这里将讨论一些基本抽象数据类型线性结构。所谓基本，只是相对而言，这些数据类型是最基本，最简单的，并且是实现其他抽象数据类型的基础。在下面的讨论中，首先我们将给出各种基本数据结构（ADT）的数学性质，然后在其数学模型上定义一组运算，最后将讨论如何利用基本的数据类型（数组、指针、记录等）来具体实现各种ADT。下面您将了解到以下常见的基本抽象数据类型的ADT操作以及这些操作用不同数据描述方法的具体实现：表的定义和性质一、表的定义表是由n(n0)个同一类型的元素（结点）a1,a2,an组成的有限序列。其中，元素的个数n定义为表的长度。当n=0时称为空表。当nl时，我们说元素ai位于该表的第i个
2、位置，或称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的基础。二、表的性质从表的定义不难看出表具有以下数学性质：除了表头和表尾外，表中的每一个元素有且仅有唯一的前驱和唯一的后继，表头有且只有一个后继，表尾有且只有一个前驱。注意：表和数组的区别
3、从概念上来看，表是一种抽象数据类型；数组是一种具体的数据结构。从数学性质上来看，表是一个二元关系R，R 当且仅当x是y的前驱；如果将该二元关系用关系图（将每一个元素用一个点来表示，若x与y有关系则从x到y连一条有向线段）来表示，则得到的是一条单链a1a2an ，因此表也可以看成是特殊的图或特殊的树（每个节点有且仅有一个子节点）；而数组是从1.n的自然数集合到数组元素集合的一一映射，其中n是数组的长度，1.n中每一个自然数唯一地对应着一个数组元素，反之亦然。所以数组可以用来实现映射。整理为word格式从物理性质来看，数组中相邻的元素是连续地存储在内存中的，或者对于程序员来说可以认为它们是连续地存
4、储在内存中的，数组的存取对程序员来说是透明的；表只是一个抽象的数学结构，并不具有具体的物理形式，表需要通过其它有具体物理形式的数据结构来实现。在表的具体实现中，表中相邻的元素不一定存储在连续的内存空间中，除非表是用数组来实现的。对于数组，可以利用其下标在一个操作内随机存取任意位置上的元素；对于表，只能根据当前元素找到其前驱或后继，因此要存取第i个位置上的元素，一般不能在一个操作内实现，除非表是用数组实现的。在实现表时需要提供足够的信息以便能够通过表中元素的位置p来存取表中的元素。表中元素的位置p是指示表中元素位置的信息，通过对p进行处理（可能是从事某种函数运算计算出该元素在内存中的位置，也可能
5、从表头开始，依次寻找当前元素的后继，重复i次找到第i个位置的元素）可以得到表中元素在内存中的物理位置，因此不能简单地将位置p理解为类似数组下标的自然数，实际上p可以是各种类型的变量，在数学上可将p定义为一个偏序集上的变量。在具体实现表及其运算时，应区分p与p所表示的位置，以及该位置上的元素三者之间的不同含义。ADT表的操作表是一种非常简便的结构，我们可以根据需要改变表的长度，也可以在表中任何位置对元素进行访问、插人或删除等操作。我们还可以将两个表连接成一个表，或把一个表拆成几个表。表的结构在信息检索，程序设计语言的编译等许多方面有广泛的应用。在表的数学模型上，我们还要定义一组运算，才能使这一数
6、学模型成为一个抽象数据类型表即ADT表。下面我们将给出一组典型的表运算。其中L是由类型为 TElement 的元素组成的一个表。x表示一个元素，p表示元素在表中的位置，其类型为TPosition。在表的不同实现方式下，TPosition可能有不同的类型定义，作为位置变量的p也可能有不同的含义。但是TPosition必须是一个偏序集，即任何两个TPosition类型的变量x,y之间可以进行比较运算，且结果只有xy,x=y,x=y五种。下面我们将ADT表看作一个抽象类TList，L是该类的一个实体，ADT表的操作将定义成L的属性和方法。ADT表的基本运算运算含义L.end为了方便，我们假定表L的结
7、束元素an之后还有一个位置，用属性end的值来表示这个位置。该属性的值为TPosition类型。L.piquet为了方便，我们假定表L的开始元素a1之前还有一个位置，该为值称为哨兵位置，该位置上的元素称为哨兵元素，用属性Piquet的值来表示这个位置。该属性的值为TPosition类型。L.first这是一个属性，其值为表L中第一个元素的位置。当L为空表时，值为L.end。整理为word格式L.last这是一个属性，其值为表L中最后一个元素的位置。当L为空表时，值为L.end。L.length返回表L的长度，即元素个数。L.IsEmpty()如果表L为空表(长度为0)则返回true，否则返回f
8、alse。L.next(p)这是一个函数，函数值为表L中位置p的后继位置。如果p是L中结束元素的位置，则L.Next(p)=L.end。当L中没有位置p或p=L.end时，该运算无定义。L.prev(p)这是一个函数，函数值为表L中位置p的前驱位置。当L中没有位置p或p是L中开始元素的位置时，该运算无定义。L.get(p)这是一个函数，函数值为L中位置p处的元素。当p=L.end或L中没有位置p时，该运算无定义。L.put(x,p)该方法将元素x放置到表L的位置p处，如果位置p处已有元素，则用x取代该元素；如果p=L.end或者L中没有位置p，则该运算无定义。L.insert(x,p)在表L的
9、位置p处插入元素x，并将原来占据位置p的元素及其后面的元素都向后推移一个位置。例如，设L为a1,a2,an，那么在执行L.insert(x,p)后，表L变为a1,a2,ap-1,x,ap,an 。若p为L.end，那么表L变为a1,a2,an,x 。若表L中没有位置p，则该运算无定义。L.delete(p)从表L中删除位置p处的元素。例如，当L为a1,a2,an时，执行L.delete(p)后，L变为a1,a2,ap-1,ap+1,an 。当L中没有位置p或p=L.end时，该运算无定义。L.locate(x)这是一个函数，函数值为元素x在L中的位置。若x在L中重复出现多次，则函数值为x第一次
10、出现的位置。当x不在L中时，函数值为L.end。L.MakeEmpty这是一个将L变为空表的方法。L.print将表L中所有元素按位置的先后次序打印输出。在表的数学模型上，定义了上述运算后，我们就定义了抽象数据类型（抽象类）TList。当然，并非任何时候都需要同时执行以上运算。在有些问题中只需要上述的一部分运算，因此也可以用上述运算的其中几个来定义适合特殊目的的抽象数据类型。上述表的运算是一些最基本的运算，对于实际问题中涉及的关于表的更复杂的运算，可以用这些基本运算的组合来实现。例如，我们可以利用上述基本运算写一个过程Purge，来清除一个表L中重复出现的元素。其中 p,q为TPosition
11、类型的变量。=下面是Pascal语言描述的代码=整理为word格式Procedure Purge(var L:TList) var p,q:TPosition; begin 1 p:=L.first; 2 while pL.end do begin 3 q:=L.next(p); 4 while qL.end do 5 if Equal(L.get(p),L.get(q) then L.delete(q) 6 else q:=L.next(q); 7 p:=L.next(p); end end;=下面是C+语言描述的代码=void Purge(TList& L) TPosition p,q;1
12、. p=L.first();2. while (p!=L.end() 3. q=L.next(p);4. while (q!=L.end() 5. if (Equal(L.get(p),L.get(q) L.delete(q);6. else q=L.next(q); 整理为word格式7. p=L.next(p); 上述过程的参数是一个表L，其元素类型为TElement。过程中用到的函数Equal(x,y)的两个自变量均为TElement类型的元素。若x与y相同，则函数值为true，否则为false。这里所说的相同的含义要根据具体元素的类型来确定。例如，当TElement为实型时，当且仅当x
13、=y时Equal(x,y)=true。但是如果TElement是一个有用户帐号、姓名及地址等多个域的记录，如:=下面是Pascal语言描述的代码=type TElement=record ID: integer; Name: string20; Address: string50; end;=下面是C+语言描述的代码=typedef struct TElement int ID; char Name20; char Address50;这时我们可以规定，Equal(x,y)=true当且仅当x.ID=y.ID，即x与y的帐号相同时成立；也可以规定3个域的值都相同时Equal(x,y)=true
14、。在Purge过程中，变量p与q是表L的两个位置变量，第2-7行是关于变量p的循环。在循环中逐个检查位置p后面的每一个位置q，如果这两个位置上的元素相同，则将位置q的元素从表L中删去。当q遍历了p后面的所有位置之后，p变为下一个位置，再开始新的循环。在过程的第4-6行的内循环中，有一点值得注意：当执行到第5行删除了位置q的元素以后，表中原来在位置q+l,q+2，的各元素都要向前移动一个位置。特别地，如果q恰好是结束元素的位置，那么在第5行删除了位置q的元素后，q值将变为L.end。因此内循环体第5和第6行的语句必须并行而不能串行，不然，可能会出现无定义的语句q=L.next(L.end)（即第6行的语句不用else而单独作为一个语句会出错）。在后文中，我们要给出TList和TPosition的适当类型说明，并讨论实现表运算的方法。整理为word格式下面我们用抽象类来定义ADT表。=下面是C+语言描述的代码=
