网站建设排版规定,html网页设计实训报告范文,网页版传奇制作教程,网站建设有哪些名词实现线性表的另一种常用方式就是基于链接结构#xff0c;用链接关系显式表示元素之间的顺序关联。基于链接技术实现的线性表称为链接表或者链表。 采用链接方式实现线性表的基本想法如下:
把表中的元素分别存储在一批独立的存储块#xff08;称为表的结点#xff09;里。保… 实现线性表的另一种常用方式就是基于链接结构用链接关系显式表示元素之间的顺序关联。基于链接技术实现的线性表称为链接表或者链表。 采用链接方式实现线性表的基本想法如下:
把表中的元素分别存储在一批独立的存储块称为表的结点里。保证从组成表结构中的任一个结点可找到与其相关的下一个结点。在前一结点里用链接的方式显式地记录与下一结点之间的关联。 这样只要能找到组成一个表结构的第一个结点就能顺序找到属于这个表的其他结点。从这些结点里可以看到这个表中的所有元素。 链接技术是一类非常灵活的数据组织技术实现链表有多种不同的方式。下面首先讨论最简单的单链表其中在每个表结点里记录着存储下一个表元素的结点的标识(引用/链接)。后面将介绍另外一些结构的链表它们各有所长支持不同的需要。在下面的讨论中将把“存储着下一个表元素的结点”简称为“下一结点”。
1 单链表 单向链接表下面将简称为单链表或者链表的结点是一个二元组形式如下图a所示其表元素域 elem 保存着作为表元素的数据项或者数据项的关联信息链接域 next 里保存同一个表里的下一个结点的标识。 在最常见形式的单链表里与表里的n个元素对应的n个结点通过链接形成一条结点链如上图b所示。从引用表中首结点的变量上图b中变量p可以找到这个表的首结点从表中任一结点可以找到保存着该表下一个元素的结点表中下一结点这样从p出发就能找到这个表里的任一个结点。 要想掌握一个单链表就需要也只需要掌握这个表的首结点从它出发可以找到这个表里的第一个元素即在这个表结点里保存的数据保存在它的 elem域中还可以找到这个表里的下一结点有关信息保存在这个结点的 next 域中。按照同样的方式继续下去就可以找到表里的所有数据元素。 也就是说为了掌握一个表只需要用一个变量保存着这个表的首结点的引用标识或称为链接。今后将把这样的变量称为表头变量或表头指针。
小结一下
—个单链表由一些具体的表结点构成。每个结点是一个对象有自己的标识下面也常称其为该结点的链接。结点之间通过结点链接建立起单向的顺序联系。 为了表示一个链表的结束只需给表的最后结点表尾结点的链接域设置一个不会作为结点对象标识的值称为空链接在 Python 里自然可以用系统常量 None 表示这种情况在上图里用接地符号“丄”表示链表结束下面将一直这样表示。 通过判断一个域或变量的值是否为空链接可知是否已到链表的结束。在顺序扫描表结点时应该用这种方法确定操作是否完成。如果一个表头指针的值是空链接就说明“它所引用的链表已经结束”这是没有元素就已结束说明该表是空表。 在实现链表上的算法时并不需要关心在某个具体的表里各结点的具体链接值是什么虽然保存在表结构里的值都是具体的只需要关心链表的逻辑结构。对链表的操作也只需要根据链表的逻辑结构考虑和实现。 为方便下面的讨论现在定义个简单的表结点类
class ListNode:def __init__(self, elem0, nextNone):self.elem elem self.next next1.1 基本操作 创建空链表 只需要把相应的表头变量设置为空链接在Python语言中将其设置为None在其他语言里也有惯用值例如有的语言里用0作为这个特殊值。 删除链表 应丢弃这个链表里的所有结点。这个操作的实现与具体的语言环境有关。在一些语言如C语言里需要通过明确的操作释放一个个结点所用的存储。在Python语言中这个操作很简单只需简单地将表指针赋值为None就抛弃了链表原有的所有结点。Python解释器的存储管理系统会自动回收不用的存储。 判断表是否为空 将表头变量的值与空链接比较。在Python语言中就是检查相应变量的值是否为None. 判断表是否满 一般而言链表不会满除非程序用完了所有可用的存储空间。
加入元素 现在考虑给单链表加入元素的操作同样有插入位置问题可以做首端插入、尾端插人或者定位插人。不同位置的操作复杂度可能不同。 首先应该注意在链表里加入新元素时并不需要移动已有的数据只需为新元素安排一个新结点然后根据操作要求把新结点连在表中的正确位置。也就是说插入新元素的操作是通过修改链接接入新结点从而改变表结构的方式实现的。 表首端插入 首端插入元素要求把新数据元素插入表中作为表的第一个元素这是最简单的情况。这一操作需要通过三步完成
创建一个新结点并存入数据下图a表示要向表头变量 head 的链表加入新首元素13为它创建了新结点变量q指着该结点。这是实际插入前的状态。 把原链表首结点的链接存入新结点的链接域 next这一操作将原表的一串结点链接在刚创建的新结点之后。 修改表头变量使之指向新结点这个操作使新结点实际成为表头变量所指的结点即表的首结点上图b表示设置链接的这两步操作完成后的状态新结点已成为 head 所指链表的首结点13成为这个表的首元素。注意示意图中链接指针的长度和形状都不表示任何意义只有图中的链接指向关系有意义。 注意即使在插入前head指向的是空表上面三步也能正确完成工作。这个插人只是一次安排新存储和几次赋值操作具有常量时间复杂度。
示例代码段
q ListNode(13)
q.next head.next
head q一般情况的元素插入 要想在单链表里的某位置插入一个新结点必须先找到该位置之前的那个结点因为新结点需要插入在它的后面需要修改它的next 域。如何找到这个结点的问题将在后面讨论先看已经找到了这个结点之后怎样插入元素。 设变量pre已指向要插入元素位置的前一结点操作也分为三步:
创建一个新结点并存入数据下图a是实际插入前的状态。把 pre 所指结点 next 域的值存入新结点的链接域 next这个操作将原表在 pre 所指结点之后的一段链接到新结点之后。修改 pre 的 next 域使之指向新结点这个操作把新结点链入被操作的表整个操作完成后的状态如下图b所示。 注意即使在插入前 pre 所指结点是表中最后一个结点上述操作也能将新结点正确接入作为新的表尾结点。
q ListNode(13)
q.next pre.next
pre.next q删除元素 删除链表中元素也可通过调整表结构删除表中结点的方式完成。这里也区分两种情况删除表头结点的操作可以直接完成删除其他结点也需要掌握其前一结点。 删除表首元素 删除表中第一个元素对应于删除表的第一个结点为此只需修改表头指针令其指向表中第二个结点。丢弃不用的结点将被Python解释器自动回收。
head head.next一般情况的元素删除一般情况删除须先找到要删元素所在结点的前一结点设用变量pre指向然后修改pre的next域使之指向被删结点的下一结点。
pre.next pre.next.next显然这两个操作都要求被删结点存在。 如果在其他编程语言里删除结点还可能要自己释放存储。Python的自动存储管理机制能自动处理这方面的问题使编程工作更简单也保证了安全性。
扫描、定位和遍历 在一般情况下插入和删除元素都要求找到被删结点的前一结点。另外程序里也可能需要定位链表中的元素、修改元素、逐个处理其中元素等。这些操作都需要检查链表的内容实际上是检查表中的一些或全部结点。 由于单链表只有一个方向的链接开始情况下只有表头变量在掌握中所以对表内容的一切检查都只能从表头变量开始沿着表中链接逐步进行。这种操作过程称为链表的扫描这种过程的基本操作模式是:
p head
while p is not None and 还需继续的其他条件:对p所指结点里的数据做所需操作p p.next根据Python语言的规定这里的 p is not None 可以简单地只写一个 p。 循环的继续或结束条件、循环中的操作由具体问题决定。循环中使用的辅助变量p称为扫描指针。注意每个扫描循环必须用一个扫描指针作为控制变量每步迭代前必须检查其值是否为None保证随后操作的合法性。这与连续表的越界检查类似。 上面表扫描模式是最一般的链表操作模式下面介绍几个常用操作的实现。 按下标定位 按 Python 惯例链表首结点的元素应看作下标0其他元素依次排列。确定第i个元素所在结点的操作称为按下标定位可以参考表扫描模式写出:
p head
while p is not NOne and i 0:i - 1p p.next假设循环前变量i已有所需的值循环结束时可能出现两种情况或者扫描完表中所有结点还没有找到第i个结点或者p所指结点就是所需。通过检查 p 值是否为None可以区分这两种情况。显然如果现在需要删除第k个结点可以先将i设置为k-1循环后检查i是0且p.next不是None就可以执行删除了。 按元素定位 假设需要在链表里找到满足谓词pred的元素。同样可以参考上面的表扫描模式写出的检索循环如下:
p head
while p is not None and not pred(p.elem):p p.next循环结束时或者p是None或者 pred(p.elem) 是 True找到了所需元素。 完整的扫描称为遍历这样做通常是需要对表中每个元素做一些事情例如:
p head
while p is not None:print(p.elem)p p.next这个循环依次输出表中各元素。只以条件 p is not None 控制循环就能完成一遍完整的遍历。同样模式可用于做其他工作。
链表操作的复杂度 总结一下链表操作的时间复杂度。 创建空表O(1)O(1)O(1)。 删除表在Python里是O(1)O(1)O(1)。当然Python 解释器做存储管理也需要时间。 判断空表O(1)O(1)O(1)。 加入元素都需要加一个T(分配)的时间 首端加入元素O(1)O(1)O(1)。尾端加入元素O(n)O(n)O(n)、因为需要找到表的最后结点。定位加人元素O(n)O(n)O(n)平均情况和最坏情况。 删除元素: 首端删除元素O(1)O(1)O(1)。尾端删除元素O(n)O(n)O(n)。定位删除元素O(n)O(n)O(n)平均情况和最坏情况。其他册除通常需要扫描整个表或其一部分O(n)O(n)O(n)。 扫描、定位或遍历操作都需要检查一批表结点其复杂度受到表结点数的约束都是 O(n)O(n)O(n) 操作。其他在工作中有此类行为的操作也至少具有 O(n)O(n)O(n) 时间复杂度。
求表的长度 在使用链表时经常需要求表的长度为此可以定义一个函数:
p, n head, 0
while p is not None:n 1p p.next
return n这个函数采用表扫描模式遍历表中所有结点完成计数。显然这个求表长度的算法所用时间与表结点个数成正比具有 O(n)O(n)O(n) 时间复杂度。
实现方式的变化 以求表的长度为例如果程序经常需要调用上面函数O(n)O(n)O(n) 复杂度就可能成为效率问题。如果表很长执行该函数就可能造成可察觉的停顿。解决这个问题的一种方法是改造单链表的实现结构增加一个表长度记录。显然这个记录不属于任何表元素是有关表的整体的信息。表示这件事的恰当方法是定义一种链表对象把表的长度和表中的结点链表都作为这个表对象的数据成分如下图所示。 图中变星p指向表对象这个对象的一个数据域记录表中元素个数图中的20表示这个表当时有20个结点另一个域引用着该表的结点链。采用了这种表示方式求表长度的操作就可以简单返回元素计数域的值。但另一方面这种表的每个变动操作都需要维护计数值。从整体看有得有失。这种调整消除了一个线性时间操作可能在一些应用中很有意义。
1.2 单链表类的实现
自定义异常 为能合理地处理一些链表操作中遇到的错误状态例如方法执行时遇到了无法操作的错误参数首先为链表类定义一个新的异常类:
class LinkedListUnderflow(ValueError):pass这里把LinkedListUnderflow定义为标准异常类valueError的子类准备在空表访问元索等场合抛出这个异常。在这些情况下抛出 valueError 也没问题但定义了自己的异常类就可以写专门的异常处理器在一些情况下可能有用。
LList类的定义初始化函数和简单操作 现在基于结点类 ListNode 定义一个单链表对象的类在这种表对象里只有一个引用链接结点的_head域初始化为None表示建立的是一个空表。判断表空的操作检查_head在表头插入数据的操作是prepend它把包含新元素的结点链接在最前面操作 pop 删除表头结点并返回这个结点里的数据
class LList:def __init__(self):self._head Nonedef is_empty(self):return self._head is Nonedef prepend(self, elem):self._head ListNode(elem, self._head)def pop(self):if self._head is None: # 无结点引发异常raise LinkedListUnorderflow(in pop)e self._head.elemself._head self._head.nextreturn e这里把 LList 对象的 _head 域作为对象的内部表示不希望外部使用。上面定义里的几个操作都很简单只有 pop 操作需要检查对象的状态表中无元素时引发异常。
后端操作 在链表的最后插入元素必须先找到链表的最后一个结点。其实现首先是一个扫描循环找到相应结点后把包含新元素的结点插入在其后。下面是定义:
def append(self, elem):if self._head is None:self._head ListNone(elem)return p self._headwhile p.next is not None:p p.nextp.next ListNode(elem)这里需要区分两种情况如果原表为空引用新结点的就应该是表对象的_head域否则就是已有的最后结点的next域。两种情况下需要修改的数据域不一样。许多链表变动操作都会遇到这个问题只有表首端插入/删除可以统一处理。 现在考虑删除表中最后元素的操作也就是要删除最后的结点。前面说过要从单链表中删除一个结点就必须找到它的前一结点。在尾端删除操作里扫描循环应该找到表中倒数第二个结点也就是找到p.next.next为None的p。下面定义的pop_last函数不仅删去表中最后元素还把它返回与pop统一。 在开始一般性扫描之前需要处理两个特殊情况如果表空没有可返回的元素时应该引发异常。表中只有一个元素的情况需要特殊处理因为这时应该修改表头指针。一般情况是先通过循环找到位置取出最后结点的数据后将其删除
def pop_last(self):if self._head is None: # 空表raise LinkeListUnderflow(in pop_last)p self._headif p.next is None: # 表中只有一个元素e p.elemself._head Nonereturn ewhile p.next.next is not None: # 直到p.next是最后结点p p.nexte p.next.elemp.next Nonereturn eLList类的下一个方法是找到满足给定条件的表元素。这个方法有一个参数调用时通过参数提供一个判断谓词该方法返回第一个满足谓词的表元素。显然这个操作也需要采用前面的基本扫描模式。定义如下
def find(self, pred):p self._headwhile p is not None:if pred(p.elem):return p.elemp p.next最后一个方法非常简单但实际中可能很有用。在开发一个表类的过程中人们会经常想看看被操作的表的当时情况
def print_all(self):p self._headwhile p is not None:print(p.elem, end)if p.next is not None:print(, , end)p p.nextprint()2 循环单链表 单链表的另一常见变形是循环单链表简称循环链表其中最后一个结点的next域不用None而是指向表的第一个结点如下图a所示。但如果仔细考虑就会发现在链表对象里记录表尾结点更合适如下图b这样可以同时支持 O(1)O(1)O(1) 时间的表头/表尾插入和 O(1)O(1)O(1) 时间的表头删除。当然由于循环链表里的结点连成一个圈哪个结点算是表头或表尾主要是概念问题从表的内部形态上无法区分。 循环单链表操作与普通单链表的差异就在于扫描循环的结束控制。易见一些不变操作的实现也要修改如 printall。 这种表对象只需一个数据域 _rear它在逻辑上始终引用着表的尾结点。前端加入结点就是在尾结点和首结点之间加人新的首结点尾结点引用不变。通过尾结点引用很容易实现这个操作。另一方面尾端加入结点也是在原尾结点之后与首结点之间插人新结点只是插入后要把它作为新的尾结点因此需要更新尾结点引用。这两个操作都要考虑空表插入的特殊情况。对于输出表元素的操作关键在于循环结束的控制。下面实现中比较扫描指针与表头结点的标识到达了表头结点就结束。前端弹出操作也很容易实现后端弹出操作需要通过一个扫描循环确定位置。 下面循环单链表类定义只实现了几个典型方法供参考
class LCList: # 循环单链表类def __init__(self):self._rear Nonedef is_empty(self):return self._rear is Nonedef prepend(self, elem): # 前端插入p LNode(elem)if self._rear is None:p.next p # 建立一个结点的环self._rear pelse:p.next self._rear.nextself.rear.next pdef append(self, elem): # 尾插入self.prepend(elem)self._rear self._rear.nextdef pop(self): # 前端弹出if self._rear is None:raise LinkedListUnderflow(in pop of CLList)p self._rear.nextif self._rear is p:self._rear Noneelse:self._rear.next p.nextreturn p.elemdef printall(self): # 输出元素if self.is_empty():returnp self._rear.nextwhile True:print(p.elem)if p is self._rear:breakp p.next3 双链表 单链表只有一个方向的链接只能做一个方向的扫描和逐步操作。即使增加了尾结点引用也只能支持 O(1)O(1)O(1) 时间的首端元素加入/删除和尾端加入。如果希望两端插入和删除操作都能高效完成就必须修改结点从而也是链表的基本设计加入另一方向的链接。这样就得到了双向链接表简称双链表。有了结点之间的双向链接不仅能支持两端的高效操作一般结点操作也会更加方便。当然这样做也需要付出代价每个结点都需要增加一个链接域,增加的空间开销与结点数成正比是 O(n)O(n)O(n)。如果每个表结点里的数据规模比较大新增加的开销可能就显得不太重要了。 为了支持首尾两端的高效操作双链表应该采用下图所示的结构包含一个尾结点引用域。易见从双链表中任一结点出发可以直接找到其前后的相邻结点都是 O(1)O(1)O(1) 操作。而对单链表而言只能方便地找到下一个结点要找前一结点就必须从表头开始逐一检查通过一次扫描。 可以直接找到当前结点的前后结点使得双链表的许多操作都很容易地进行。下面假定结点的下一结点引用域是next前一结点引用域是prev。
结点操作 先考虑结点删除。实际上只要掌握着双链表里一个结点就可以把它从表中取下并把其余结点正确链接好。下图说明了这个操作。示例代码是 p.prev.next p.next
p.next.prev p.prev这两个语句使p所指结点从表中退出其余结点保持顺序和链接。如果要考虑前后可能无结点的情况只需增加适当的条件判断。 在任一结点的前后加入结点的操作也很容易局部完成只需掌握确定加入位置的这个结点。易见加入一个结点需要做四次引用赋值。
