目錄

一、無(wú)序列表抽象數(shù)據(jù)類(lèi)型

二、實(shí)現(xiàn)無(wú)序列表：鏈表

2.1 Node類(lèi)

2.2 UnorderedList類(lèi)

三、有序列表抽象數(shù)據(jù)類(lèi)型

四、實(shí)現(xiàn)有序列表

---

列表是元素的集合，其中每一個(gè)元素都有一個(gè)相對(duì)于其他元素的位置。更具體地說(shuō)，這種列表成為無(wú)序列表?？梢哉J(rèn)為列表有第一個(gè)元素、第二個(gè)元素。第三個(gè)元素，等等；也可以稱(chēng)第一個(gè)元素為列表的起點(diǎn)，稱(chēng)最后一個(gè)元素為列表的終點(diǎn)。為簡(jiǎn)單起見(jiàn)，我們假設(shè)列表中沒(méi)有重復(fù)的元素。

一、無(wú)序列表抽象數(shù)據(jù)類(lèi)型

如前所述，無(wú)序列表是元素的集合，其中每一個(gè)元素都有一個(gè)相對(duì)于其他元素的位置。以下是無(wú)序列表支持的操作。

• List()創(chuàng)建一個(gè)空列表。它不需要參數(shù)，且會(huì)返回一個(gè)空列表。
• add(item)假設(shè)元素item之前不在列表中，并向其中添加item。它接受一個(gè)元素作為參數(shù)，無(wú)返回值。
• remove(item)假設(shè)元素item之前已經(jīng)在列表中，并從其中移除item。它接受一個(gè)元素作為參數(shù)，并且修改列表。
• search(item)在列表中搜索元素item。它接受一個(gè)元素作為參數(shù)，并且返回布爾值。
• isEmpty()檢查列表是否為空。它不需要參數(shù)，并且返回布爾值。
• length()返回列表中元素的個(gè)數(shù)。它不需要參數(shù)，并且返回一個(gè)整數(shù)。
• append(item)假設(shè)元素item之前不在列表中，并在列表的最后位置添加item。它接受一個(gè)元素作為參數(shù)，無(wú)返回值。
• index(item)假設(shè)元素item已經(jīng)在列表中，并返回該元素在列表中的位置。它接受一個(gè)元素作為參數(shù)，并且返回該元素的下標(biāo)。
• insert(pos,item)假設(shè)元素item之前不在列表中，同時(shí)假設(shè)pos是合理的值，并在位置pos處添加元素item。它接受兩個(gè)參數(shù)，無(wú)返回值。
• pop()假設(shè)列表不為空，并移除列表中的最后一個(gè)元素。它不需要參數(shù)，且會(huì)返回一個(gè)元素。
• pop(pos)假設(shè)在指定位置pos存在元素，并移除該位置上的元素。它接受位置參數(shù)，且會(huì)返回一個(gè)元素。

二、實(shí)現(xiàn)無(wú)序列表：鏈表

為了實(shí)現(xiàn)無(wú)序列表，我們要構(gòu)建鏈表。無(wú)序列表需要維持元素之間的相對(duì)位置，但是并不需要在連續(xù)的內(nèi)存空間中維護(hù)這些位置信息。如果可以為每一個(gè)元素維護(hù)一份信息，即下一個(gè)元素的位置，那么這些元素的相對(duì)位置就能通過(guò)指向下一個(gè)元素的鏈接來(lái)表示。

需要注意的是，必須指明列表中第一個(gè)元素的位置。一旦知道第一個(gè)元素的位置，就能根據(jù)其中的鏈接信息訪問(wèn)第二個(gè)元素，接著訪問(wèn)第三個(gè)元素，依此類(lèi)推。指向鏈表第一個(gè)元素的引用被稱(chēng)作頭。最后一個(gè)元素需要知道自己沒(méi)有下一個(gè)元素。

2.1 Node類(lèi)

節(jié)點(diǎn)是構(gòu)建鏈表的基本數(shù)據(jù)結(jié)構(gòu)。每一個(gè)節(jié)點(diǎn)對(duì)象都必須持有至少兩份信息。首先，節(jié)點(diǎn)必須包含列表元素，我們稱(chēng)之為節(jié)點(diǎn)的數(shù)據(jù)變量。其次，節(jié)點(diǎn)必須保存指向下一個(gè)節(jié)點(diǎn)的引用。在構(gòu)建節(jié)點(diǎn)時(shí)，需要為其提供初始值。Node類(lèi)也包含訪問(wèn)和修改數(shù)據(jù)的方法，以及指向下一個(gè)元素的引用。

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

特殊的Python引用值None在Node類(lèi)以及之后的鏈表中起到了重要的作用。指向None的引用代表著后面沒(méi)有元素。注意，Node的構(gòu)造方法將next的初始值設(shè)為None。由于這有時(shí)被稱(chēng)為“將節(jié)點(diǎn)接地”，因此，我們使用接地符號(hào)來(lái)代表指向None的引用。將None作為next的初始值是不錯(cuò)的做法。

class Node:def __init__(self,initdata):self.data=initdataself.next=Nonedef getData(self):return self.datadef getNext(self):return self.nextdef setData(self,newdata):self.data=newdatadef setNext(self,newnext):self.next=newnext

2.2 UnorderedList類(lèi)

如前所述，無(wú)序列表是基于節(jié)點(diǎn)集合來(lái)構(gòu)建的，每一個(gè)節(jié)點(diǎn)都通過(guò)顯式的引用指向下一個(gè)節(jié)點(diǎn)。只要知道第一個(gè)節(jié)點(diǎn)的位置（第一個(gè)節(jié)點(diǎn)包含第一個(gè)元素），其后的每一個(gè)元素都能通過(guò)下一個(gè)引用找到。因此，UnorderedList類(lèi)必須包含指向第一個(gè)節(jié)點(diǎn)的引用。注意，每一個(gè)列表對(duì)象都保存了指向列表頭部的引用。

UnorderedList類(lèi)的構(gòu)造方法如下：

class UnorderedList:def __init__(self):self.head=None

最開(kāi)始構(gòu)建列表時(shí)，其中沒(méi)有元素。與在Node類(lèi)中一樣，特殊引用值None用于表明列表的頭部沒(méi)有指向任何節(jié)點(diǎn)。列表的頭部指向包含列表的第一個(gè)元素的節(jié)點(diǎn)，這個(gè)節(jié)點(diǎn)包含指向下一個(gè)節(jié)點(diǎn)（元素）的引用，依此類(lèi)推。非常重要的一點(diǎn)是，列表類(lèi)本身并不包含任何節(jié)點(diǎn)對(duì)象，而只有指向整個(gè)鏈表結(jié)構(gòu)中第一個(gè)節(jié)點(diǎn)的引用。

isEmpty方法如下：

def isEmpty(self):return self.head==None

isEmpty方法檢查列表的頭部是否為指向None的引用。布爾表達(dá)式self.head==None當(dāng)且僅當(dāng)鏈表中沒(méi)有節(jié)點(diǎn)才為真。由于新的鏈表是空的，因此構(gòu)造方法必須和檢查是否為空保持一致。這體現(xiàn)了使用None表示鏈表末尾的好處。在Python中，None可以和任何引用進(jìn)行比較。如果兩個(gè)引用都指向同一個(gè)對(duì)象，那么它們就是相等的。

由于鏈表只提供一個(gè)入口（頭部），因此其他所有節(jié)點(diǎn)都只能通過(guò)第一個(gè)節(jié)點(diǎn)以及next鏈表來(lái)訪問(wèn)。這意味著添加新節(jié)點(diǎn)最簡(jiǎn)便的位置就是頭部，或者說(shuō)鏈表的起點(diǎn)。我們把新元素作為列表的第一個(gè)元素，并且把已有的元素鏈接到該元素的后面。

add方法如下：

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

由于頭節(jié)點(diǎn)是唯一指向列表節(jié)點(diǎn)的外部引用，因此，如果顛倒第3行和第4行的順序，所有的已有節(jié)點(diǎn)都將丟失并且無(wú)法訪問(wèn)。

接下來(lái)要實(shí)現(xiàn)的方法——length、search以及remove——都基于鏈表遍歷這個(gè)技術(shù)。遍歷是指系統(tǒng)地訪問(wèn)每一個(gè)節(jié)點(diǎn)，具體做法是用一個(gè)外部引用從列表的頭節(jié)點(diǎn)開(kāi)始訪問(wèn)。隨著訪問(wèn)每一個(gè)節(jié)點(diǎn)，我們將這個(gè)外部引用通過(guò)“遍歷”下一個(gè)引用來(lái)指向下一個(gè)節(jié)點(diǎn)。

length方法：

def length(self):current=self.headcount=0while current!=None:count=count+1current=current.getNext()return count

search方法：

def search(self,item):current=self.headfound=Falsewhile current!=None and not found:if current.getData()==item:found=Trueelse:current=current.getNext()return found

remove方法：

def remove(self,item):current=self.headprevious=Nonefound=Falsewhile not found:if current.getData()==item:found=Trueelse:previous=currentcurrent=current.getNext()if previous==None:self.head=current.getNext()else:previous.setNext(current.getNext())

三、有序列表抽象數(shù)據(jù)類(lèi)型

在有序列表中，元素的相對(duì)位置取決于它們的基本特征。它們通常以升序或者降序排列，并且我們假設(shè)元素之間能進(jìn)行有意義的比較。有序列表的眾多操作與無(wú)序列表的相同。

• OrderedList()創(chuàng)建一個(gè)空的有序列表。它不需要參數(shù)，且會(huì)返回一個(gè)空列表。
• add(item)假設(shè)item之前不在列表中，并向其中添加item，同時(shí)保持整個(gè)列表的順序。它接受一個(gè)元素作為參數(shù)，無(wú)返回值。
• remove(item)假設(shè)item已經(jīng)在列表中，并從其中移除item。它接受一個(gè)元素作為參數(shù)，并且修改列表。
• search(item)假設(shè)item已經(jīng)在列表中，并從其中移除item。它接受一個(gè)元素作為參數(shù)，并且修改列表。
• search(item)在列表中搜索item。它接受一個(gè)元素作為參數(shù)，并且返回布爾值。
• isEmpty()檢查列表是否為空。它不需要參數(shù)，并且會(huì)返回布爾值。
• length()返回列表中元素的個(gè)數(shù)。它不需要參數(shù)，并且返回一個(gè)整數(shù)。
• index(item)假設(shè)item已經(jīng)在列表中國(guó)，并返回該元素在列表中的位置。它接受一個(gè)元素作為i參數(shù)，并返回該元素的下標(biāo)。
• pop()假設(shè)列表不為空，并移除列表中的最后一個(gè)元素。它不需要參數(shù)，且會(huì)返回一個(gè)元素。
• pop(pos)假設(shè)在指定位置pos存在元素，并移除該位置上的元素。它接受位置參數(shù)，且會(huì)返回一個(gè)元素。

四、實(shí)現(xiàn)有序列表

class OrderedList:def __init__(self):self.head=Nonedef search(self,item):current=self.headfound=Falsestop=Falsewhile current!=None and not found and not stop:if current.getData()==item:found=Trueelse:if current.getData()>item:stop=Trueelse:current=current.getNext()return founddef add(self,item):current=self.headprevious=Nonestop=Falsewhile current!=None and not stop:if current.getData()>item:stop=Trueelse:previous=currentcurrent=current.getNext()temp=Node(item)if previous==None:temp.setNext(self.head)self.head=tempelse:temp.setNext(current)previous.setNext(temp)

因?yàn)閕sEmpty和length僅與列表中的節(jié)點(diǎn)數(shù)目有關(guān)，而與實(shí)際的元素值無(wú)關(guān)，所以這兩個(gè)方法在有序列表中的實(shí)現(xiàn)與在無(wú)序列表中一樣。同理，由于仍然需要找到目標(biāo)元素并且通過(guò)更改鏈接來(lái)移除節(jié)點(diǎn)，因此remove方法的實(shí)現(xiàn)也一樣。剩下的兩個(gè)方法，search和add，需要做一些修改。