内蒙古大学《算法与数据结构》讲义03数据描述

下载第3章数 据 描 述从本章开始我们进行数据结构的研究，一直到第1 2章为止。尽管本章的重点是介绍线性表，但一个主要目标是为了使大家明白， 数据可以用不同的形式进行描述或存储在计算机存储器中。最常见的数据描述方法有：公式化描述、链接描述、间接寻址和模拟指针。公式化描述借助数学公式来确定元素表中的每个元素分别存储在何处（如存储器地址） 。最简单的情形就是把所有元素依次连续存储在一片连续的存储空间中，这就是通常所说的连续线性表。在链接描述中，元素表中的每个元素可以存储在存储器的不同区域中，每个元素都包含一个指向下一个元素的指针。同样，在间接寻址方式中，元素表中的每个元素也可以存储在存储器的不同区域中，不同的是，此时必须保存一张表，该表的第 i项指向元素表中的第 i个元素，所以这张表是一个用来存储元素地址的表。在公式化描述中，元素地址是由数学公式来确定的；在链接描述中，元素地址分布在每一个表元素中；而在间接寻址方式下，元素地址则被收集在一张表中。模拟指针非常类似于链接描述，区别在于它用整数代替了 C + +指针，整数所扮演的角色与指针所扮演的角色完全相同。本章介绍了线性表的四种描述形式，通过考察常见表操作（如插入、删除）的复杂性，给出了每种描述方法的优缺点。在本章中还将学习如何用数组来模拟 C + +指针。本章所给出的有关数据结构的概念如下： 抽象数据类型。 公式化描述、链接描述、间接寻址和模拟指针。 单向链表、循环链表和双向链表。本章的应用部分集中介绍了链表的应用，之所以这样做，是因为第 1章和第2章中所给出的所有程序都采用了公式化的数据表示形式，而现在希望采用链表形式来改写其中的部分程序。二叉排序、基数排序和等价类应用都使用了链表，而凸面体应用则采用了双向链表。二叉排序和基数排序可用来对n 个元素进行排序，如果关键值介于一个“合适的范围”内，排序所需要的时间为(n)。虽然在第2章中所给出的排序算法需要耗时O (n2)，但它不需要将关键值限制在一个“合适的范围”内。当关键值介于一个“合适的范围”内时，二叉排序和基数排序要比第2章所给出的排序算法快出许多。在二叉排序的应用中还可以看到如何把函数名作为一个参数传递给C + +函数。3.1 引言数据对象（data object）即一组实例或值，例如： B o o l e a n =false, true 第二部分数 据 结 构 Digit = 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 L e t t e r = A, B, C, , Z, a, b, , z NaturalNumber = 0, 1, 2, Integer = 0, 1, 2, 3, String = a, b, , aa, ab, ac, B o o l e a n，D i g i t，L e t t e r，N a t u r a l N u m b e r，I n t e g e r和S t r i n g都是数据对象，t r u e和f a l s e是B o o l e a n的实例，而 0, 1, , 和9 都是Digit 的实例。数据对象的每个实例要么是一个原语（p r i m i t i v e） （或原子（a t o m i c） ） ，要么是由其他数据对象的实例复合而成。在后一种情形下，用术语“元素（e l e m e n t） ”来表示对象实例的单个组件。例如，数据对象NaturalNumber 的每个实例均可以视为原子，在这种情况下，不必考虑对这些实例做进一步的分解。另一种观点是把NaturalNumber 的每个实例看成是由D i g i t数据对象的若干实例复合而成。按照这种观点，整数6 7 5是由数字6，7和5按顺序组成。数据对象S t r i n g是所有可能的串实例的集合，每个实例均由字符组成。串实例的一些具体例子如：good, a trip to Hawaii, going down hill和a b c a b c d a b c d e。其中第一个串由四个元素 g, o,o 和d 按序构成，而每个元素又都是数据对象L e t t e r的一个实例。数据对象的实例以及构成实例的元素通常都有某种相关性，例如，自然数 0是最小的自然数，1是仅比0大的自然数，而2是1之后的下一个自然数。在自然数 6 7 5中, 6是最高有效位， 7在其次，而5是最低有效位。在串good 中，g 是第一字母，o 是第二和第三个字母，而d 是最后一个字母。除了相互关联之外，对于任一个数据对象通常都有一组相关的函数。这些函数可以把对象的某个实例转换成该对象的另外一个实例，或转换成另一个数据对象的实例，或者同时进行上述两种转换。函数也可以简单地创建一个新的实例，而不必对一个新创建的实例进行转换。例如，进行自然数相加的函数将创建一个新的自然数，该自然数是两个相加数之和，两个参与加操作的自然数本身不会发生任何变化。数据结构（data structure）包括数据对象和实例以及构成实例的每个元素之间所存在的各种关系。这些关系可由相关的函数来实现。当我们研究数据结构时，关心的是数据对象（实际上是实例）的描述以及与数据对象相关函数的具体实现。数据对象的良好描述可以有效地促进函数的高效实现。最常使用的数据对象以及函数都已经在 C + +中被当作标准的数据类型加以实现，如整数对象( i n t )、实数对象( f l o a t )、布尔对象( b o o l )等。所有其他的数据对象均可以采用标准数据类型、枚举类型以及由C + +的类、数组和指针特性所提供的组合功能来描述。例如，可以用一个字符数组s 来描述String 的实例：char sMaxSize;有关数据结构的研究包括两个部分。本章按照数据的各种描述方法进行组织，即基于公式的描述、链表描述、简接寻址和模拟指针。我们利用数据对象线性表来演示这些方法。在后续章节中将研究其他流行的数据描述方法，如矩阵、栈、队列、字典、优先队列和图。3.2 线性表线性表（linear list）是这样的数据对象，其实例形式为：(e1 , e2 ,. en )，其中n 是有穷自然数。ei是表中的元素，n 是表的长度。元素可以被视为原子，因为它们本身的结构与线性表的结构无关。当n = 0 时，表为空；当n 0时，e1是第一个元素，en是最后一个元素，可以认为el优先于e2，e2优先于e3，如此等等。除了这种优先关系之外，在线性表中不再有其他的结构。7 6第二部分数 据 结 构下载我们用s 表示每个元素ei所需要的字节数，因此，s 是一个元素的大小。以下是一些线性表的例子： 1) 一个班级学生姓名按字母顺序排列的列表； 2) 按递增次序排列的考试分数表；3) 按字母顺序排列的会议列表； 4) 奥林匹克男子篮球比赛中金牌获得者按年代次序排列的列表。根据这些例子可知对于线性表有必要执行下列操作 ： 创建一个线性表。 确定线性表是否为空。 确定线性表的长度。 查找第k个元素。 查找指定的元素。 删除第k个元素。 在第k个元素之后插入一个新元素。可以用一个抽象数据类型 (abstract data type, ADT) 来说明线性表，它给出了实例及相关操作的描述(见ADT 3-1)。请注意，这种抽象数据类型说明与C+ 的类定义之间具有很多相似性。抽象数据类型说明独立于我们已提到的任何描述方法。抽象数据类型的描述方法必须满足抽象数据类型说明，而说明又反过来保证了描述方法的合法性。除此以外，所有满足说明的描述方法都可以在数据类型应用中替换使用。ADT 3-1 线性表的抽象数据类型描述抽象数据类型LinearList 实例0或多个元素的有序集合操作C reate (): 创建一个空线性表D e s t roy (): 删除表I s E m p t y(): 如果表为空则返回t r u e，否则返回false Length (): 返回表的大小 (即表中元素个数)Find (k,x): 寻找表中第k 个元素，并把它保存到x 中；如果不存在，则返回f a l s eS e a rch (x): 返回元素x在表中的位置；如果x 不在表中，则返回0Delete (k,x): 删除表中第k 个元素，并把它保存到x 中；函数返回修改后的线性表I n s e rt (k,x): 在第k个元素之后插入x；函数返回修改后的线性表Output (o u t): 把线性表放入输出流out 之中除了用ADT 3-1中非正式的自然语言来说明抽象数据类型外，还可以使用 C + +的抽象类来说明抽象数据类型。在该方法中需使用派生类、抽象类和虚拟函数，我们将在第 5章和第1 2章中详细讨论这些话题，目前还只能使用非正式的自然语言。如果你已经很熟悉派生类和抽象类，可以查阅1 2 . 9 . 4节看看如何用C + +抽象类来说明线性表抽象数据类型。3.3 公式化描述3.3.1 基本概念公式化描述（f o r m a l a - b a s e d）采用数组来表示一个对象的实例，数组中的每个位置被称之第3章数 据 描 述7 7下载为单元（c e l l）或节点（n o d e） ，每个数组单元应该足够大，以便能够容纳数据对象实例中的任意一个元素。在某些情况下，每个实例可分别用一个独立的数组来描述，而在其他情况下，可能要使用一个数组来描述几个实例。实例中每个元素在数组中的位置可以用一个数学公式来指明。假定使用一个数组来描述表，需要把表中的每个元素映射到数组的具体位置上。第一个元素在什么地方？第二个元素在什么地方？在公式化描述中，可用一个数学公式来确定每个元素的位置。一个简单的映射公式如下：l o c a t i on(i )= i- 1（3 - 1）公式（3 - 1）指明表中第i 个元素（如果存在的话）位于数组中 i- 1位置处。图3-1a 给出了一个利用公式（3 - 1）作为映射公式，在数组e l e m e n t中描述一个5元素线性表的例子。 （一个更简洁的公式是：l o c a t i o n(i) =i，它不使用0位置，在练习8至练习1 3中将使用这个公式） 。为了完整地描述线性表，需要了解表的当前长度或大小，为此，使用变量 l e n g t h作为表的长度。当表为空时，l e n g t h为0。程序3 - 1给出了相应的C + +类定义。由于表元素的数据类型随着应用的变化而变化，所以定义了一个模板类，在该模板类中，用户指定元素的数据类型为 T。数据成员l e n g t h、M a x S i z e和e l e m e n t都是私有成员，其他成员均为共享成员。 I n s e r t和D e l e t e均返回一个线性表的引用。我们将要看到，具体实现时首先会修改表 * t h i s，然后返回一个引用（指向修改后的表） 。因此，同时组合多个表操作是可行的，如X . I n s e r t ( 0 , a ) . D e l e t e ( 3 , b )。图3-1 线性表程序3-1 基于公式的类 L i n e a r L i s ttemplateclass LinearList p u b l i c :LinearList(int MaxListSize = 10); /构造函数LinearList() delete element; /析构函数bool IsEmpty() const return length = 0;int Length() const return length;bool Find(int k, T& x) const; /返回第k个元素至x中int Search(const T& x) const; / 返回x所在位置7 8第二部分数 据 结 构下载a) b) c) LinearList& Delete(int k, T& x); / 删除第k个元素并将它返回至x中LinearList& Insert(int k, const T& x); / 在第k个元素之