python随机生成无序列表_python实现无序列表：链表
介紹鏈表前我們先了解下什么是列表。
在對基本數(shù)據(jù)結(jié)構(gòu)的討論中，我們使用 Python 列表來實現(xiàn)所呈現(xiàn)的抽象數(shù)據(jù)類型。列表是一個強(qiáng)大但簡單的收集機(jī)制，為程序員提供了各種各樣的操作。然而，不是所有的編程語言都包括列表集合。在這些情況下，列表的概念必須由程序員實現(xiàn)。
列表是項的集合，其中每個項保持相對于其他項的相對位置。更具體地，我們將這種類型的列表稱為無序列表。我們可以將列表視為具有第一項，第二項，第三項等等。我們還可以引用列表的開頭(第一個項)或列表的結(jié)尾(最后一個項)。為了簡單起見，我們假設(shè)列表不能包含重復(fù)項。
例如，整數(shù) 54,26,93,17,77 和 31 的集合可以表示考試分?jǐn)?shù)的簡單無序列表。請注意，我們將它們用逗號分隔，這是列表結(jié)構(gòu)的常用方式。當(dāng)然，Python 會顯示這個列表為 [54,26,93,17,77,31]。
1 無序列表抽象數(shù)據(jù)類型
如上所述，無序列表的結(jié)構(gòu)是項的集合，其中每個項保持相對于其他項的相對位置。下面給出了一些可能的無序列表操作。
List() 創(chuàng)建一個新的空列表。它不需要參數(shù)，并返回一個空列表。
add(item) 向列表中添加一個新項。它需要 item 作為參數(shù)，并不返回任何內(nèi)容。假定該 item 不在列表中。
remove(item) 從列表中刪除該項。它需要 item 作為參數(shù)并修改列表。假設(shè)項存在于列表中。
search(item) 搜索列表中的項目。它需要 item 作為參數(shù)，并返回一個布爾值。
isEmpty() 檢查列表是否為空。它不需要參數(shù)，并返回布爾值。
size()返回列表中的項數(shù)。它不需要參數(shù)，并返回一個整數(shù)。
append(item) 將一個新項添加到列表的末尾，使其成為集合中的最后一項。它需要 item
作為參數(shù)，并不返回任何內(nèi)容。假定該項不在列表中。
index(item) 返回項在列表中的位置。它需要 item 作為參數(shù)并返回索引。假定該項在列表中。
insert(pos，item) 在位置 pos 處向列表中添加一個新項。它需要 item作為參數(shù)并不返回任何內(nèi)容。假設(shè)該項不在列表中，并且有足夠的現(xiàn)有項使其有 pos 的位置。
pop() 刪除并返回列表中的最后一個項。假設(shè)該列表至少有一個項。
pop(pos) 刪除并返回位置 pos 處的項。它需要 pos 作為參數(shù)并返回項。假定該項在列表中。
2 python實現(xiàn)無序列表
為了實現(xiàn)無序列表，我們將構(gòu)造通常所知的鏈表，外部引用通常被稱為鏈表的頭。
2.1 Node類
節(jié)點(Node)是鏈表實現(xiàn)的基本構(gòu)造，由列表項(item，數(shù)據(jù)字段)和對下一個節(jié)點的引用組成。Node 類包括訪問，修改數(shù)據(jù)和訪問下一個引用等常用方法。類的代碼如下：
class Node:
def __init__(self,initdata):
self.data = initdata
self.next = None
def getData(self):
return self.data
def getNext(self):
return self.next
def setData(self,newdata):
self.data = newdata
def setNext(self,newnext):
self.next = newnext
我們創(chuàng)建一個 Node 對象
temp=Node(93)
Python 引用值 None 將在 Node 類和鏈表本身發(fā)揮重要作用。引用 None 代表沒有下一個節(jié)點。請注意在構(gòu)造函數(shù)中，最初創(chuàng)建的節(jié)點 next 被設(shè)置為 None。有時這被稱為 接地節(jié)點，因此我們使用標(biāo)準(zhǔn)接地符號表示對 None 的引用，如下圖：
2.2 Unordered List 類
如上所述，無序列表將從一組節(jié)點構(gòu)建，每個節(jié)點通過顯式引用鏈接到下一個節(jié)點。只要我們知道在哪里找到第一個節(jié)點(包含第一個項)，之后的每個項可以通過連續(xù)跟隨下一個鏈接找到。考慮到這一點，UnorderedList 類必須保持對第一個節(jié)點的引用，如下圖所示，實現(xiàn)代碼如下：
class UnorderedList:
def __init__(self):
self.head = None
def isEmpty(self):
return self.head == None
def add(self,item):
temp = Node(item)
#更改新節(jié)點的下一個引用以引用舊鏈表的第一個節(jié)點
temp.setNext(self.head)
#賦值語句設(shè)置列表的頭
self.head = temp
#訪問和賦值的順序不能顛倒，因為head是鏈表節(jié)點唯一的外部引用，顛倒將導(dǎo)致所有原始節(jié)點丟失并且不能再被訪問
def size(self):
current = self.head
count = 0
while current != None:
count = count + 1
current = current.getNext()
return count
def search(self,item):
current = self.head
found = False
while current != None and not found:
if current.getData() == item:
found = True
else:
current = current.getNext()
return found
def remove(self,item):
current = self.head
previous = None
found = False
while not found:
if current.getData() == item:
found = True
#previous 必須先將一個節(jié)點移動到 current 的位置。此時，才可以移動current
else:
previous = current
current = current.getNext()
#如果要刪除的項目恰好是鏈表中的第一個項，鏈表的 head 需要改變
if previous == None:
self.head = current.getNext()
else:
previous.setNext(current.getNext())
2.2.1 add function
鏈表結(jié)構(gòu)只為我們提供了一個入口點，即鏈表的頭部。所有其他節(jié)點只能通過訪問第一個節(jié)點，然后跟隨下一個鏈接到達(dá)。這意味著添加新節(jié)點的最簡單的地方就在鏈表的頭部。 換句話說，我們將新項作為鏈表的第一項，現(xiàn)有項將需要鏈接到這個新項后。
2.2.2 鏈表遍歷技術(shù)——size，search，remove方法
size方法實現(xiàn)思路如下圖：
remove方法實現(xiàn)思路如下圖：
remove 方法需要兩個邏輯步驟。
第一步搜索，第二部刪除。
但是current實際指向的是目標(biāo)節(jié)點的引用，直接刪除會刪除前一個節(jié)點，因此引入previous這個外部引用。
參考資料：《problem-solving-with-algorithms-and-data-structure-using-python》
http://www.pythonworks.org/pythonds
總結(jié)
以上是生活随笔為你收集整理的python随机生成无序列表_python实现无序列表：链表的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 举个栗子！Tableau 技巧（95）：
- 下一篇： 求最大公因数的三种算法及简要说明