现在的位置: 主页 > 商讯 > 文章正文

python数据结构与算法 18 无序列表的实现

作者:福州市名人视觉形象设计职业培训学校 来源:www.mrssjy.com 发布时间:2017-09-10 09:42:06
python数据结构与算法 18 无序列表的实现 无序列表的实现:链表

为了实现无序列表,先要实现我们通常称为“链表”的结构。前面说过我们保持列表元素之间的相对位置。当然,在连续存储的情况下不需要额外保存相对位置(如数组),但是如果数据以图1这样的随机方式保存,这就需要为每个元素配置额外的信息,指明它下一个元素的位置(图2),这样每个元素的相对位置,就通过一个元素到另一个元素的链接实现了。

\



图1 元素不固定物理位置

\


图2 通过明确链接维持相对关系

特别要注意,链表第一个元素的位置必须单独指定,一旦知道了第一个元素,它就能告诉我们第2个元素的位置,依次类推。链表的外部引用通常就指向它的头部。类似地,最后一个元素,也要表明他“下面没有了”。

节点类

节点(Node)是实现链表的基本模块,每个节点至少包括两个重要部分。首先,包含节点自身的数据,称为“数据域”。其次,包括对下一个节点的“引用”。下面代码是Node类的代码。为了构造节点,需要初始化节点的数据,如图3,为节点赋值并返回一个节点对象。不过图4才是一般节点的图示方式。节点类也包括访问和修改数据域及指针域的的方法。

Listing 1

classNode: def__init__(self,initdata): self.data= initdata self.next=None defgetData(self): returnself.data defgetNext(self): returnself.next defsetData(self,newdata): self.data= newdata defsetNext(self,newnext): self.next= newnext

用上述类创建一个节点对象

>>> temp= Node(93) >>> temp.getData() 93

特殊的引用值None在节点类和链表中都非常重要。对None的引用代表没有下一个节点,象构造函数中,就是创建一个节点,把并它的“引用”赋值为None。因为有时把最后一个节点称为“接地点”,我们干脆用电气上的接地符号代表None。初始化一个“引用”时,先赋值为None,是个不错的主意。

\


图3 节点对象包括数据域和对下一个节点的引用



图4 节点的典型表示法

无序列表类

如前所述,无序列表通过一个节点的集合来实现,每个节点包括对下一个节点的引用。只要我们找到第一个节点,跟着引用就能走遍每个数据项。按这个想法,无序列表类必须保存对第一个节点的引用。下面是构造方法,注意每个列表对象包含对“列表头”(head)的引用。

Listing 2

classUnorderedList: def__init__(self): self.head=None

创建列表的时候进行初始化,这里没有数据项,赋值语句

>>> mylist= UnorderedList()

创建的链表如图5所示。我们已经讨论过节点类的特殊引用None,这里用来表示head没有引用任何节点。最后,前面给出的链表例子如图6所示,head指向第一个节点,第一个节点包括第一个数据项。同样,第一个节点包括对下一个节点的引用。特别重要的是,链表类不包括任何节点对象,相反,它只包括对列表第一个元素的引用。

图5 空列表



\


图6 整数链表

下面代码段中的isEmpty方法,用来检查head引用是否是None,方法中的返回值表达式self.head==None,只有当链表中没有节点时为真。既然一个新建链表是空,构造函数和“isEmpty“函数一定保持一致,这也显示了用None来代表“结束”的优势。在python语言中,None能够和任意的引用作比较,如果两个变量引用了同一对象,他们就是相等的。今后还会经常用到这种方法。

Listing 3

defisEmpty(self): returnself.head==None 这样的话,怎样把新的数据项加入列表呢?需要实现一个新add方法。但在此之前,需要处理一个重要问题:链表把新数据项放在什么位置?既然列表是无序的,新数据项的位置与原有元素关系不大,新数据项可放在任意位置,这样的话,我们可以把新项放在最容易处理的位置。

回想链表结构只为我们提供了一个入入,即列表的head,所有其他节点都要通过引用逐个访问,这说明,最容易的处理的地方就是在head位置,或开始的位置。换个说法,新数据项总是列表的第一个项,原有数据项都通过引用依次排在它的后面。

图6显示了通过 add方法几次形成的链表。

>>> mylist.add(31) >>> mylist.add(77) >>> mylist.add(17) >>> mylist.add(93) >>> mylist.add(26) >>> mylist.add(54)

注意到31是第一个加入的数据,最终它是链表里最后一个。同样,54是最后加入的,它成为链表的第一个节点的数据

Add方法在代码4中实现。每个数据项都在节点对象内部。第2行创建一个新节点,并把数据保存在它的数据域内。然后需要把这个节点与现有结构连接起来,图7表明了两个步骤。第一步,把新节点的引用改成对原来第一个节点的引用。这样列表里其他节点就与新节点建立了链接,只要把修改head为对新节点的引用。第4行的赋值语句设置列表的head。

上面两个步骤的顺序特别重要,如果3和4反序会怎么样?如果先修改了head的引用,就象图8所示,因为head是对列表节点的唯一外部引用入口,一旦失去,所有原来的节点将从内存中消失。

Listing 4

代码4

defadd(self,item): temp = Node(item) temp.setNext(self.head) self.head= temp

\


图7 两步增加新节点

\


图8两步顺序倒置的结果

企业建站2800元起,携手武汉肥猫科技,做一个有见地的颜值派!更多优惠请戳:武汉网站设计 http://www.45qun.com

上一篇:JavaScript:设计模式之工厂模式 下一篇:最后一页