大数据

当前位置:首页 > 大数据

《算法导论》第十章

数据结构

集合作为计算机科学的基础,就如同它们在数学中所起的作用。数学中的集合是不变的,而由算法操作的集合却在整个过程中能增大、缩小或发生其他变化。我们]称这样的集合是动态的。下面的五章将介绍在计算机上表示和操作有限动态集合的一些基本技术。

不同的算法可能需要对集合执行不同的操作。例如,许多算法只需要能在一个集合中插入和删除元素,以及测试元素是否属于集合。支持这些操作的动态集合称为字典(dictionary)。其他一些算法需 要更复杂的操作。

例如,第6章堆数据结构这部分中介绍的最小优先队列,它支持向集合插入一个元素和从中取出一个最小元素的操作。实现动态集合的关键取决于必须支持的一些集合操作。

动态集合的元素

在动态集合的典型实现中,每个元素都由一个对象来表示,如果有一个指向对象的指针,就能对其各个属性进行检查和操作。(10. 3节讨论了在编程环境中对象和指针的实现,而这些对象和指针并没有作为基本的数据类型。)一些类型的动态集合假定对象中的一个属性为标识关键字(key)。如果关键字全不相同,可以将动态集合视为一个关键字值的集合。对象可能包含卫星数据,它们与其他对象属性一起移动,除此之外,集合实现不使用它们。对象也可以有由集合操作使用的属性;这些属性可能包含有关集合中其他对象的数据或指针。

一些动态集合以其关键字来自于某个全序集为前提条件,比如实数集合或按通常字典序排序的所有单词。例如,全序关系允许定义一个集合的最小元素,也可以确定比集合中一个给定元素大的下一个元素。

动态集合上的操作

动态集合上的操作可以分为两类:简单返回有关集合信息的查询操作和改变集合的修改操作。下面列出一些标准操作。任何具体应用通常只需要这些操作中的若千个就可以实现。

SEARCH(S, k):一个查询操作,给定一个集合S和关键字k,返回指向s中某个元素的指针x,使得x. key=k;如果S中没有这样的元素,则返回NIL。

INSERT(S, x):一个修改操作,将由x指向的元素加入到集合S中。通常假定元素x中集合S所需要的每个属性都已经被初始化好了。

DELETE(S, x):一个修改操作,给定指针x指向集合S中的一个元素,从S中删除xo,(注意,这个操作取一个指向元素x的指针作为输入,而不是一个关键字的值)

MINIMUM(S):一个查询操作,在全序集S上返回一个指向S中具有最小关键字元素的指针。

MAXIMUM(S):一个查询操作,在全序集S上返回一个指向s中具有最大关键字元素的指针。

SUCCESSOR(S, x):一个查询操作,给定关键字属于全序集S的一个元素x,返回S中比x大的下一个元素的指针;如果x为最大元素,则返回NIL。

PREDECESSOR(S, x):一个查询操作,给定关键字属于全序集S的一个元素x,返回S中比x小的前一个元素的指针;如果x为最小元素,则返回NIL。

在某些情况下,能够将SUCCESSOR和PREDECESSOR查询操作推广应用到一些具有相同关键字的集合上。对于一个有n个关键字的集合,通常的假设是调用一次MAXIMUM后再调用n-1次SUCCESSOR,就可以按序枚举出该集合中的所有元素。

度量一个集合操作的执行时间通常要对照这个集合的大小。例如,第13章描述了一种数据结构,对于规模为n的集合,它能在时间O(lgn)内完成上面列出的每个操作。

第三部分概览

第10~14章描述能够用于实现动态集合的几种数据结构;本书后面将使用其中多种构造解决各种不同问题的有效算法。另一种重要的堆数据结构在第6章中已经介绍过了。

第10章给出一些简单数据结构的使用基础,如栈、队列、链表和有根树。本章还要说明在不支持对象和指针作为基本类型的编程环境中如何实现它们。如果读者学习过编程课程或相关入门课程,那么对其中的大部分内容应该是熟悉的。

第11章介绍散列表,它支持字典操作INSERT、DELETE和SEARCH。最坏情况下,散列表上完成一次SEARCH操作需要Θ(n)时间,但散列表上操作的期望时间为0(1)。散列分析依赖于概率论,不过本章的大部分内容并不需要这方面的背景知识。

第12章介绍二叉搜索树,它受持上面所列出的所有动态集合操作。最坏情况下,在有n个

元素的一棵树上,一次操作需要Θ(n)时间;然而在随机构建的一棵二C叉搜索树上,其一次操作的期望时间为O(lgn)。二叉搜索树作为其他许多数据结构的基础。

第13章介绍红黑树,这是二叉搜索树的一个变种。与普通的二叉搜索树不同,红黑树保证了较好的性能:最坏情况下各种操作只需要O(lgn)时间。一棵红黑树是一种平衡搜索树;第五部分中的第18章给出了另一种类型的平衡搜索树,称为B树。虽然红黑树的工作机制有点复杂,但是不用仔细研究这些机制也能了解大部分性质。然而,读者通览一下本章的代码还是非常有益处的。

第14章给出如何将红黑树进行扩张,使其支持上面所列基本操作之外的一些操作。 首先,对红黑树进行扩张,使得对关键字集合能够动态地维护顺序统计量。接着,给出红黑树的另一种不同扩张方式,用于实数区间的维护。


第十章  基本数据结构


在本章中,我们要讨论如何通过使用指针的简单数据结构来表示动态集合。虽然运用指针可以构造多种复杂的数据结构,但这里只介绍几种基本的结构:栈、队列、链表和有根树。此外,我们还要介绍由数组构造对象和指针的方法。


10. 1 栈和队列

栈和队列都是动态集合,且在其上进行DELETE操作所移除的元素是预先设定的。在栈(stack)中,被删除的是最近插入的元素:栈实现的是一种后进先出(last-in, first-out, LIFO) 策略。类似地,在队列(queue)中,被删去的总是在集合中存在时间最长的那个元素:队列实现的是一种先进先出(first-in, first-out, FIFO)策略。在计算机上实现栈和队列有几种有效方式。本节将介绍如何利用一个简单的数组实现这两种结构。

栈上的INSERT操作称为压入(PUSH),而无元素参数的DELETE操作称为弹出(POP)。这两个名称使人联想到现实中的栈,比如餐馆里装有弹簧的摞盘子的栈。盘子从栈中弹出的次序刚好同它们压入的次序相反,这是因为只有最上面的盘子才能被取下来。

如图10-1所示,可以用一个数组S[1.. n]来实现一个最多可容纳n个元素的栈。该数组有一个属性S. top,指向最新插入的云素化榴中包含的元素为S[1.. s. top],其中S[1]是栈底元素,而S[S. top. ]是栈顶元素。

QQ截图20220512155633.jpg

图10-1栈S的数组实现。只有出现在浅灰色格子里的才是栈内元素。(a)栈S有4个元素。栈顶元素为9。(b)调用PUSH(S, 17)和PUSH(S, 3)后的栈S。(c)调用POP(S)并返回最后压入的元素3的栈S。虽然元素3仍在数组里,但它已不在栈内了,此时在栈顶的是元素17

当s. top=0时,栈中不包含任何元素,即栈是空(empty)的。要测试一个栈是否为空可以用查询操作STACK-EMPTY。如果试图对一个空栈执行弹出操作,则称栈下溢(underflow),这通常是一个错误。如果s. top超过了n,则称栈上溢(overlow)。(在下面的伪代码实现中,我们不考虑栈的上溢问题。)

栈的几种操作只需分别用几行代码来实现:

QQ截图20220512155835.jpg

QQ截图20220512155847.jpg

图10-1所示为修改后的PUSH和POP操作的执行结果。三种栈操作的执行时间都为0(1)。

队列

队列上的INSERT操作称为入队( ENQUEUE),DELETE操作称为出队(DEQUEUE);正如栈的POP操作一样,DEQUEUE操作也没有元素参数。队列的先进先出特性类似于收银台前排队等待结账的一排顾客。队列有队头(head)和队尾(ail),当有一个元素入队时,它被放在队尾的位置,就像一个新到来的顾客排在队伍末端一样。而出队的元素则总是在队头的那个,就像排在队伍前面等待最久的那个顾客一样。

QQ截图20220512160101.jpg

图10-2 利用数组Q[1..12]实现一个队列。只有出现在浅灰色格子里的才是队列的元素。(a) 队列包含5个元素,位于Q[7..11]。 (b)依次调用ENQUEUE( Q,17 )、ENQUEUE (Q,3) 和ENQUEUE(Q, 5) 后队列的构成。(c)在 调用DEQUEUE(Q并返回原队头的关键字值15后,队列的构成。此时新的队头元素的关键字为6

图10-2表明利用数组Q[1..n]来实现一个最多容纳n-1个元素的队列的一种方式。该队列有一个属性Q.head指向队头元素。而属性Qtail则指向下一个新元素将要插入的位置。队列中的元素存放在位置Q.head, Q.head+1, ...,Q.tail-1,并在,最后的位置“环绕”,感觉好像位置1紧邻在位置n后面形成一个环序。当Q.head =Q.tail时,队列为空。初始时有Q. head=Q. tail=1。如果试图从空队列中删除一个元素,则队列发生下溢。当Q.head=Q.tail+1时,队列是满的,此时若试图插入一个元素,则队列发生上溢。

在下面ENQUEUE和DEQUEUE程序中,我们省略了对下溢和上溢的检查。(练习10. 1-4要求读者给出检查两种错误情况的代码。)在下列伪代码中,假设n= Q. length。

QQ截图20220512160709.jpg

图10-2所示为ENQUEUE和DEQUEUE操作的执行结果。两种操作的执行时间都为0(1)。


练习

10. 1-1  仿照图 10-1,画图表示依次执行操作PUSH(S, 4)、PUSH(S,1)、 PUSH(S, 3)、POP(S)、PUSH(S,8)和POP(S)每一步的结果,栈S初始为空,存储于数组S[1.. 6]中。

10. 1-2  说明如何在一个数组A[1.. n]中实现两个栈,使得当两个栈的元素个数之和不为n时,两者都不会发生上溢。要求PUSH和POP操作的运行时间为0(1)。

10.1-3  仿照图10-2, 画图表示依次执行操作ENQUEUE(Q, 4)、ENQUEUE(Q, 1)、ENQUEUE(Q,3)、 DEQUEUE(Q)、ENQUEUE(Q,8)和DEQUEUE(Q)每一步的结果,队列初始为空,存储于数组Q[1.. 6]中。

10. 1-4  重写ENQUEUE和DEQUEUE的代码,使之能处理队列的下溢和上溢。

10.1-5  栈插入和删除元素 只能在同一端进行, 队列的插入操作和删除操作分别在两端进行,与它们不同的,有一种双端队列(deque),其插入和删除操作都可以在两端进行。写出4个时间均为0(1)的过程,分别实现在双端队列的两端插入和删除元素的操作,该队列是用一个数组实现的。

10.1-6  说明如何用两个栈实现一个队列,并分析相关队列操作的运行时间。

10. 1-7  说明如何用两个队列实现一个栈, 并分析相关栈操作的运行时间。


10.2 链表

链表(linkedlist)是一种这样的数据结构,其中的各对象按线性顺序排列。数组的线性顺序是由数组下标决定的,然而与数组不同的是,链表的顺序是由各个对象里的指针决定的。链表为动态集合提供了一种简单而灵活的表示方法,并且能支持10. 1节中列出的所有操作(但未必非常有效)。

如图10-3所示,双向链表(doubly linked list)L的每个元素都是一个对象,每个对象有一个关键字key和两个指针:next和prev。对象中还可以包含其他的辅助数据(或称卫星数据)。设x为链表的一个元素,x. next指向它在链表中的后继元素,x. prev则指向它的前驱元素。如果x. prev=NIL,则元素x没有前驱,因此是链表的第一个元素,即链表的头(head)。如果x.next=NIL,则元素x没有后继,因此是链表的最后一个元素,即链表的尾(tail)。属性L. head指向链表的第一个元素。如果L. head= NIL,则链表为空。

QQ截图20220512170531.jpg

图10-3 (a)表示动态集合{1, 4, 9, 16}的双向链表L。链表中的每个元素都是一个对象,拥有关键字和指向前后对象的指针(用箭头表示)。表尾的next属性和表头的prev属性都是NIL,用一个斜杠表示。属性L. head指向表头元素。(b)在执行LIST-INSERT(L, X)之后(这里x. key=25),链表以关键字为25的新对象作为新的表头。该新对象指向原来关键字为9的表头元素。(c)随后调用LIST-DELETE(L, X)的结果,其中x指向关键字为4的对象

链表可以有多种形式。它可以是单链接的或双链接的,可以是已排序的或未排序的,可以是循环的或非循环的。如果一个链表是单链接的(singly linked),则省略每个元素中的prev指针。如果链表是已排序(sorted)的,则链表的线性顺序与链表元素中关键字的线性顺序一致;据此,最小的元素就是表头元素,而最大的元素则是表尾元素。如果链表是未排序(unsorted)的,则各元素可以以任何顺序出现。在循环链表(circular list)中,表头元素的prev指针指向表尾元素,而表尾元素的next 指针则指向表头元素。我们可以将循环链表想象成一个各元素组成的圆环。在本节余下的部分中,我们假设所处理的链表都是未排序的且是双链接的。

链表的搜索

过程LIST SEARCH(L, k)采用简单的线性搜索方法,用于查找链表L中第一个关键字为k的元素,并返回指向该元素的指针。如果链表中没有关键字为k的对象,则该过程返回NIL。对于图10-3(a)中的链表,调用LIST-SEARCH(L, 4)返回指向第三个元素的指针,而调用LIST-

SEARCH(L, 7)则返回NIL。

QQ截图20220512170828.jpg

要搜索一个有n个对象的链表,过程LIST-SEARCH在最坏情况下的运行时间为Θ(n),因为可能需要搜索整个链表。

链表的插入

给定一个已设置好关键字key的元素x,过程LIST-INSERT将x“连接人”到链表的前端,如图10-3(b)所示。

QQ截图20220512170950.jpg

图10-3(c)展示了从链表中删除一个元素的操作。LIST-DELETE 的运行时间为0(1)。但如果要删除具有给定关键字的元素,则最坏情况下需要的时间为Θ(n),因为需要先调用LIST-SEARCH找到该元素。

哨兵

如果可以忽视表头和表尾处的边界条件,则LIST-DELETE的代码可以更简单些:

QQ截图20220512171101.jpg

哨兵(sentinel)是一个哑对象,其作用是简化边界条件的处理。例如,假设在链表L中设置一个对象L.nil,该对象代表NIL,但也具有和其他对象相同的各个属性。对于链表代码中出现的每一处对NIL的引用,都代之以对哨兵L.nil的引用。如图10-4所示,这样的调整将一个常

规的双向链表转变为一个有哨兵的双向循环链表( circular, doubly linked list with a sentinel),哨兵L. nil位于表头和表尾之间。属性L. nil. next指向表头,L. nil. prev指向表尾。类似地,表尾的next属性和表头的prev属性同时指向L.nil。因为L. nil. next指向表头,我们就可以去掉属性L. head,并把对它的引用代替为对L. nil. next的引用。图10-4(a)显示,一个空的链表只由一个哨兵构成,L. nil. next和L. nil. prerv同时指向L. nil。

QQ截图20220512171240.jpg

图10-4带哨兵的双向循环链表。 哨兵L. nil位于表头和表尾之间。由于可通过L. nil. next访问表头,属性L. head就不需要了。(a)空链表。(b)图 10-3(a)中的链表,表头关键字为9,表尾关键字为1。(c)执行LIST-INSERT'(L, x)后的链表,其中x. key=25。新插入的对象成为表头。(d) 删除关键字为1的对象后的链表。新的表尾是关键字为4的对象

LIST-SEARCH的代码和之前基本保持不变,只是将对NIL和L. head的引用如前所述加以调整:

QQ截图20220512171415.jpg

我们使用前述的仅含两行代码的过程LIST-DELETE'可以实现元素的删除。下面的过程则实现元素的插入:

QQ截图20220512171458.jpg

图10-4|展示了LIST-INSERT和LIST-DELETE在该链表实例上的执行结果。

哨兵基本不能降低数据结构相关操作的渐近时间界,但可以降低常数因子。在循环语句中使用哨兵的好处往往在于可以使代码简洁,而非提高速度。举例来说,使用哨兵使链表的代码变得简洁了,但在LIST-INSERT'和LIST-DELETE'过程上仅节约了0(1)的时间。然而,在另一

些情况下,哨兵的使用使循环语句的代码更紧凑,从而降低了运行时间中n或n2等项的系数。

我们应当慎用哨兵。假如有许多个很短的链表,它们的哨兵所占用的额外的存储空间会造成严重的存储浪费。本书中,仅当可以真正简化代码时才使用哨兵。


练习

10.2-1  单链表 上的动态集合操作INSERT能否在0(1)时间内实现?DELETE操作呢?

10.2-2  用一个单链表 L实现一个栈。要求操作PUSH和POP的运行时间仍为O(1)。

10.2-3  用一个单链表L实现一个队列。要求操作ENQUEUE和DEQUEUE的运行时间仍为0(1)。

10.2-4  如前所述, LIST-SEARCH 过程中的每一次循环迭代都需要两个测试:一是检查 x≠L.nil,另一个是检查x. key≠k。试说明如何在每次迭代中省略对x≠L. nil的检查。

10.2-5  使用单向循环链表实现字典操作INSERT、DELETE和SEARCH,并给出所写过程的运行时间。

10.2-6  动态集合 操作UNION以两个不相交的集合S1和S2作为输入,并返回集合S=S1 US2,包含S1和S2的所有元素。该操作通常会破坏集合S1和S2。试说明如何选用一种合适的表类数据结构,来支持O(1)时间的UNION操作。

10.2-7  给出一个0(n)时间的非递归过程,实现对一个含n个元素的单链表的逆转。要求除存储链表本身所需的空间外,该过程只能使用固定大小的存储空间。

*10. 2-8 说明如何在每个元素仅使用一个指针x. np(而不是通常的两个指针next和prev)的情况下实现双向链表。假设所有指针的值都可视为k位的整型数,且定义x.np=x.next XORxprev,即xnext和x.prer的k位异或。(NIL的值用0表示。)注意要说明获取表头所需的信息,并说明如何在该表上实现SEARCH、INSERT和DELETE操作,以及如何在0(1)时间内实现该表的逆转。

相关内容

文章评论

表情

共 0 条评论,查看全部
  • 这篇文章还没有收到评论,赶紧来抢沙发吧~