第8章Python數(shù)據(jù)結(jié)構(gòu)課程描述數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)存儲(chǔ)和組織數(shù)據(jù)的方式，指相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。數(shù)據(jù)結(jié)構(gòu)往往與高效的檢索算法和索引技術(shù)有關(guān)。本節(jié)介紹Python中的一些常用數(shù)據(jù)結(jié)構(gòu)的用法，包括棧、隊(duì)列、樹(shù)、鏈表、bitmap和圖。第8章Python數(shù)據(jù)結(jié)構(gòu)課程描述本章知識(shí)點(diǎn)數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)隊(duì)列bitmap棧鏈表圖本章知識(shí)點(diǎn)數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)8.1Python數(shù)據(jù)結(jié)構(gòu)概述8.1.1什么是數(shù)據(jù)結(jié)構(gòu)8.1.2數(shù)據(jù)結(jié)構(gòu)和算法的關(guān)系8.1Python數(shù)據(jù)結(jié)構(gòu)概述8.1.1什么是數(shù)據(jù)結(jié)8.1.1什么是數(shù)據(jù)結(jié)構(gòu)一個(gè)程序里面必然會(huì)有數(shù)據(jù)存在，同樣的一個(gè)或幾個(gè)數(shù)據(jù)要組織起來(lái)，可以有不同的組織方式，也就是不同的存儲(chǔ)方式。不同的組織方式就是不同的結(jié)構(gòu)，我們把這些數(shù)據(jù)組織在一起的結(jié)構(gòu)稱之為數(shù)據(jù)的結(jié)構(gòu)，也叫做數(shù)據(jù)結(jié)構(gòu)。比如，有一個(gè)字符串是"abc"，我們將其重新組織一下，比如通過(guò)list()函數(shù)將"abc"變成["a","b","c"]，那么這個(gè)時(shí)候數(shù)據(jù)就發(fā)生了重組，重組之后數(shù)據(jù)的結(jié)構(gòu)就變了。["a","b","c"]這種形式的數(shù)據(jù)的結(jié)構(gòu)被稱為列表。也就是說(shuō)列表是一種數(shù)據(jù)結(jié)構(gòu)，除此之外，還有元組、字典、棧、樹(shù)等數(shù)據(jù)結(jié)構(gòu)。Python的數(shù)據(jù)結(jié)構(gòu)有很多類型。其中有Python系統(tǒng)自己定義好的，不需要我們自己去定義。這種數(shù)據(jù)結(jié)構(gòu)被稱為Python的內(nèi)置數(shù)據(jù)結(jié)構(gòu)，比如列表、元組、字典等。而有些數(shù)據(jù)組織方式，Python系統(tǒng)里面沒(méi)有直接定義，需要我們自己去定義實(shí)現(xiàn)，這些數(shù)據(jù)組織方式稱為Python擴(kuò)展數(shù)據(jù)結(jié)構(gòu)，比如棧和隊(duì)列。8.1.1什么是數(shù)據(jù)結(jié)構(gòu)一個(gè)程序里面必然會(huì)有數(shù)據(jù)存在，同8.1.1彈出消息框使用showinfo()函數(shù)可以彈出提示消息框，方法如下showinfo(title=標(biāo)題,message=內(nèi)容)8.1.1彈出消息框使用showinfo()函數(shù)可以彈出提8.1.2數(shù)據(jù)結(jié)構(gòu)和算法的關(guān)系數(shù)據(jù)結(jié)構(gòu)和算法有著密切的聯(lián)系。因?yàn)閿?shù)據(jù)結(jié)構(gòu)是數(shù)據(jù)的組織方式，也就是數(shù)據(jù)的存儲(chǔ)方式。算法是指運(yùn)算方法，通俗地講，算法就是思維。數(shù)據(jù)結(jié)構(gòu)是靜態(tài)的，我們編寫(xiě)的程序是動(dòng)態(tài)的。程序要對(duì)數(shù)據(jù)進(jìn)行運(yùn)算，運(yùn)算的方法很多，不同的運(yùn)算方法就是不同的算法。當(dāng)然算法不是憑空出來(lái)的，它必須建立在數(shù)據(jù)的基礎(chǔ)上，所以數(shù)據(jù)結(jié)構(gòu)是算法的基礎(chǔ)，但同一個(gè)數(shù)據(jù)結(jié)構(gòu)運(yùn)用不同算法的效率是不同的。8.1.2數(shù)據(jù)結(jié)構(gòu)和算法的關(guān)系數(shù)據(jù)結(jié)構(gòu)和算法有著密切的聯(lián)8.2棧8.2.1棧的工作原理8.2.2利用Python列表實(shí)現(xiàn)棧的數(shù)據(jù)結(jié)構(gòu)8.2棧8.2.1棧的工作原理8.2.1棧的工作原理?xiàng)Ｊ且环N經(jīng)典的數(shù)據(jù)結(jié)構(gòu)，但它并不是Python的內(nèi)置數(shù)據(jù)結(jié)構(gòu)，而是屬于擴(kuò)展數(shù)據(jù)結(jié)構(gòu)。棧相當(dāng)于一端開(kāi)口、一端封閉的容器。棧支持出棧和進(jìn)棧2種操作。數(shù)據(jù)移動(dòng)到棧里面的過(guò)程叫做進(jìn)棧，也叫做壓棧、入棧；數(shù)據(jù)進(jìn)入到棧里面后，就到了棧頂，同時(shí)占了棧的一個(gè)位置。當(dāng)再進(jìn)入一個(gè)數(shù)據(jù)時(shí)，新的數(shù)據(jù)就占據(jù)了棧頂?shù)奈恢茫瓉?lái)的數(shù)據(jù)就被新的數(shù)據(jù)壓入到棧頂?shù)南乱粋€(gè)位置里。棧只能對(duì)其棧頂?shù)臄?shù)據(jù)進(jìn)行操作，所以這個(gè)時(shí)候原來(lái)的數(shù)據(jù)就不能被操作。8.2.1棧的工作原理?xiàng)Ｊ且环N經(jīng)典的數(shù)據(jù)結(jié)構(gòu)，但它并不是初始化時(shí)的棧初始化時(shí)的棧將數(shù)據(jù)A執(zhí)行進(jìn)棧操作將數(shù)據(jù)A執(zhí)行進(jìn)棧操作再將數(shù)據(jù)B執(zhí)行進(jìn)棧操作再將數(shù)據(jù)B執(zhí)行進(jìn)棧操作8.2.2利用Python列表實(shí)現(xiàn)棧的數(shù)據(jù)結(jié)構(gòu)1.構(gòu)造函數(shù)首先，在構(gòu)造函數(shù)中定義一個(gè)列表items用于實(shí)現(xiàn)棧的容器，代碼如下：#coding:utf8classStack:"""模擬棧"""def__init__(self):self.items=[]8.2.2利用Python列表實(shí)現(xiàn)棧的數(shù)據(jù)結(jié)構(gòu)1.構(gòu)造2.isEmpty()函數(shù)defisEmpty(self):returnlen(self.items)==02.isEmpty()函數(shù)defisEmpty(self3.push()函數(shù)defpush(self,item):self.items.append(item)3.push()函數(shù)defpush(self,item4.pop()函數(shù)defpop(self):returnself.items.pop()4.pop()函數(shù)defpop(self):5.peek()函數(shù)defpop(self):returnself.items.pop()5.peek()函數(shù)defpop(self):6.size()函數(shù)defsize(self):returnlen(self.items)6.size()函數(shù)defsize(self):【例8-1】s=Stack()#創(chuàng)建棧對(duì)象print(s.isEmpty())#打印棧是否為空s.push('DataA')#進(jìn)棧DataAs.push('DataB')#進(jìn)棧DataAprint(s.peek())#打印棧頂元素s.push('DataC')#進(jìn)棧DataCprint(s.size())#打印棧的大小print(s.isEmpty())#打印棧是否為空s.push('DataD')#進(jìn)棧DataDprint(s.pop())#出棧print(s.pop())#出棧print(s.size())#打印棧的大小)【例8-1】s=Stack()#創(chuàng)建棧對(duì)象8.3隊(duì)列隊(duì)列是一種經(jīng)典的數(shù)據(jù)結(jié)構(gòu)，它也不是Python的內(nèi)置數(shù)據(jù)結(jié)構(gòu)，而是屬于擴(kuò)展數(shù)據(jù)結(jié)構(gòu)。隊(duì)列相當(dāng)于兩邊都開(kāi)口的容器。但是一邊只能進(jìn)行刪除操作，而不能進(jìn)行插入操作；另一邊只能進(jìn)行插入操作，而不能進(jìn)行刪除操作。進(jìn)行插入操作的這一端叫做隊(duì)尾，進(jìn)行刪除操作的這一端叫做隊(duì)首。所以，隊(duì)列中的數(shù)據(jù)是從隊(duì)尾進(jìn)隊(duì)首出的。隊(duì)列的數(shù)據(jù)元素又稱為隊(duì)列元素。在隊(duì)列中插入一個(gè)隊(duì)列元素稱為入隊(duì)，從隊(duì)列中刪除一個(gè)隊(duì)列元素成為出隊(duì)。8.3隊(duì)列隊(duì)列是一種經(jīng)典的數(shù)據(jù)結(jié)構(gòu)，它也不是Python初始化時(shí)的隊(duì)列初始化時(shí)的隊(duì)列將數(shù)據(jù)A執(zhí)行入隊(duì)操作將數(shù)據(jù)A執(zhí)行入隊(duì)操作將數(shù)據(jù)B執(zhí)行入隊(duì)操作將數(shù)據(jù)B執(zhí)行入隊(duì)操作再將數(shù)據(jù)C執(zhí)行進(jìn)棧操作再將數(shù)據(jù)C執(zhí)行進(jìn)棧操作再將數(shù)據(jù)C執(zhí)行進(jìn)棧操作再將數(shù)據(jù)C執(zhí)行進(jìn)棧操作將數(shù)據(jù)A執(zhí)行出隊(duì)操作將數(shù)據(jù)A執(zhí)行出隊(duì)操作8.3.2利用Python列表實(shí)現(xiàn)隊(duì)列的數(shù)據(jù)結(jié)構(gòu)本節(jié)介紹一個(gè)Python自定義類Queue，它的功能是利用Python列表實(shí)現(xiàn)隊(duì)列的數(shù)據(jù)結(jié)構(gòu)。8.3.2利用Python列表實(shí)現(xiàn)隊(duì)列的數(shù)據(jù)結(jié)構(gòu)本節(jié)介紹1.構(gòu)造函數(shù)#coding:utf8classQueue(object):def__init__(self):self.queue=[]1.構(gòu)造函數(shù)#coding:utf82.isempty()函數(shù)isempty()函數(shù)用于判斷隊(duì)列是否為空。如果隊(duì)列為空，則isempty()函數(shù)返回True，否則返回False。isempty()函數(shù)的代碼如下：

defisempty(self):returnself.queue==[]2.isempty()函數(shù)isempty()函數(shù)用于判斷隊(duì)3.enqueue()函數(shù)defenqueue(self,item):self.queue.append(item)3.enqueue()函數(shù)defenqueue(sel4.dequeue()函數(shù)defdequeue(self):ifself.queue!=[]:returnself.queue.pop(0)else:returnNone4.dequeue()函數(shù)defdequeue(sel5.head()函數(shù)head()函數(shù)用于返回隊(duì)首元素，但并不刪除該元素。代碼如下：

defhead(self):ifself.queue!=[]:returnself.queue[0]else:returnNone5.head()函數(shù)head()函數(shù)用于返回隊(duì)首元素，6.tail()函數(shù)tail()函數(shù)用于返回隊(duì)尾元素，但并不刪除該元素。代碼如下：

deftail(self):ifself.queue!=[]:returnself.queue[-1]else:returnNone6.tail()函數(shù)tail()函數(shù)用于返回隊(duì)尾元素，7.length()函數(shù)length()函數(shù)用于返回隊(duì)列的大小。代碼如下：

deflength(self):returnlen(self.queue)7.length()函數(shù)length()函數(shù)用于返回隊(duì)列的【例8-2】q=Queue()#創(chuàng)建隊(duì)列對(duì)象print(q.isempty())#打印隊(duì)列是否為空q.enqueue('DataA')#入隊(duì)DataAq.enqueue('DataB')#入隊(duì)DataAprint(q.head())#打印對(duì)首元素print(q.tail())#打印隊(duì)尾元素q.enqueue('DataC')#入隊(duì)DataCprint(q.length())#打印隊(duì)列的大小print(q.isempty())#打印隊(duì)列是否為空q.enqueue('DataD')#入隊(duì)DataDprint(q.dequeue())#出隊(duì)print(q.dequeue())#出隊(duì)print(q.length())#打印隊(duì)列的大小)【例8-2】q=Queue()#創(chuàng)建隊(duì)列對(duì)象運(yùn)行結(jié)果如下：TrueDataADataB3FalseDataADataB2運(yùn)行結(jié)果如下：True8.4樹(shù)8.4.1樹(shù)的工作原理8.4.2遍歷二叉樹(shù)8.4.3在Python程序中實(shí)現(xiàn)樹(shù)的數(shù)據(jù)結(jié)構(gòu)8.4樹(shù)8.4.1樹(shù)的工作原理8.4.1樹(shù)的工作原理樹(shù)的定義首先有且只有一個(gè)根節(jié)點(diǎn)，另外他有Ｎ個(gè)不相交的子集，每個(gè)子集都是一個(gè)子樹(shù)。8.4.1樹(shù)的工作原理樹(shù)的定義首先有且只有一個(gè)根節(jié)點(diǎn)，另空樹(shù)空樹(shù)只有一個(gè)根結(jié)點(diǎn)的二叉樹(shù)只有一個(gè)根結(jié)點(diǎn)的二叉樹(shù)有左子樹(shù)的二叉樹(shù)有左子樹(shù)的二叉樹(shù)只有右子樹(shù)的二叉樹(shù)只有右子樹(shù)的二叉樹(shù)2完全二叉樹(shù)2完全二叉樹(shù)8.4.2遍歷二叉樹(shù)“遍歷”是二叉樹(shù)各種操作的基礎(chǔ)。二叉樹(shù)是一種非線性結(jié)構(gòu)，遍歷二叉樹(shù)不像遍歷線性鏈表那樣容易，無(wú)法通過(guò)簡(jiǎn)單的循環(huán)實(shí)現(xiàn)。遍歷二叉樹(shù)就是要讓樹(shù)中的所有節(jié)點(diǎn)被且僅被訪問(wèn)一次，即按一定規(guī)律排列成一個(gè)線性隊(duì)列。二叉樹(shù)包含3個(gè)部分，即根結(jié)點(diǎn)、左子樹(shù)和右子樹(shù)。根據(jù)這3個(gè)部分的訪問(wèn)次序?qū)Χ鏄?shù)的遍歷進(jìn)行分類，可以將遍歷二叉樹(shù)的方法分為3種類型，分別稱為“先序遍歷”、“中序遍歷”和“后序遍歷”。先序遍歷指先訪問(wèn)根節(jié)點(diǎn)，然后再訪問(wèn)左子樹(shù)，最后訪問(wèn)右子樹(shù)；中序遍歷指訪問(wèn)左子樹(shù)，然后再訪問(wèn)根節(jié)點(diǎn)，最后訪問(wèn)右子樹(shù)；中序遍歷指先訪問(wèn)根節(jié)點(diǎn)，然后訪問(wèn)左子樹(shù)，最后訪問(wèn)右子樹(shù)；后序遍歷指訪問(wèn)左子樹(shù)，然后再訪問(wèn)右子樹(shù)，最后訪問(wèn)根節(jié)點(diǎn)。8.4.2遍歷二叉樹(shù)“遍歷”是二叉樹(shù)各種操作的基礎(chǔ)。二8.4.3在Python程序中實(shí)現(xiàn)樹(shù)的數(shù)據(jù)結(jié)構(gòu)本節(jié)介紹一個(gè)Python自定義類BinaryTree，它的功能是在Python程序中實(shí)現(xiàn)樹(shù)的數(shù)據(jù)結(jié)構(gòu)。8.4.3在Python程序中實(shí)現(xiàn)樹(shù)的數(shù)據(jù)結(jié)構(gòu)本節(jié)介紹一1.定義樹(shù)節(jié)點(diǎn)類Node首先，定義一個(gè)樹(shù)節(jié)點(diǎn)類Node，代碼如下：classNode(object):def__init__(self,data=-1,lchild=None,rchild=None):self.data=dataself.lchild=lchildself.rchild=rchild1.定義樹(shù)節(jié)點(diǎn)類Node首先，定義一個(gè)樹(shù)節(jié)點(diǎn)類Node，代2.BinaryTree類的構(gòu)造函數(shù)classBinaryTree(object):def__init__(self):self.root=Node()2.BinaryTree類的構(gòu)造函數(shù)classBin3.BinaryTree類的add()函數(shù)defadd(self,data):#data為新節(jié)點(diǎn)的數(shù)據(jù)

node=Node(data)#創(chuàng)建新節(jié)點(diǎn)

ifself.isEmpty():#如果二叉樹(shù)為空，則將新節(jié)點(diǎn)作為二叉樹(shù)的根節(jié)點(diǎn)

self.root=nodeelse:tree_node=self.rootqueue=[]#以列表存儲(chǔ)二叉樹(shù)

queue.append(self.root)whilequeue:#遍歷二叉樹(shù)

tree_node=queue.pop(0)

3.BinaryTree類的add()函數(shù)defadiftree_node.lchild==None:#如果當(dāng)前節(jié)點(diǎn)的左孩子為空，則將新節(jié)點(diǎn)作為當(dāng)前節(jié)點(diǎn)的左孩子

tree_node.lchild=nodereturneliftree_node.rchild==None:#如果當(dāng)前節(jié)點(diǎn)的右孩子為空，則將新節(jié)點(diǎn)作為當(dāng)前節(jié)點(diǎn)的右孩子

tree_node.rchild=nodereturnelse:queue.append(tree_node.lchild)queue.append(tree_node.rchild)iftree_node.lchild==None:4.BinaryTree類的pre_order()函數(shù)defpre_order(self,start):#start是開(kāi)始遍歷的節(jié)點(diǎn)

node=startifnode==None:#如果當(dāng)前節(jié)點(diǎn)為空，則返回

returnprintnode.data,#打印當(dāng)前節(jié)點(diǎn)的數(shù)據(jù)

#如果當(dāng)前節(jié)點(diǎn)的左右子樹(shù)都為空，則返回

ifnode.lchild==Noneandnode.rchild==None:returnself.pre_order(node.lchild)#從當(dāng)前節(jié)點(diǎn)的左子樹(shù)開(kāi)始先序遍歷

self.pre_order(node.rchild)#從當(dāng)前節(jié)點(diǎn)的右子樹(shù)開(kāi)始先序遍歷4.BinaryTree類的pre_order()函數(shù)5.BinaryTree類的in_order()函數(shù)defin_order(self,start):#start是開(kāi)始遍歷的節(jié)點(diǎn)

node=startifnode==None:returnself.in_order(node.lchild)#從當(dāng)前節(jié)點(diǎn)的左子樹(shù)開(kāi)始中序遍歷

printnode.data,#打印當(dāng)前節(jié)點(diǎn)的數(shù)據(jù)

self.in_order(node.rchild)#從當(dāng)前節(jié)點(diǎn)的右子樹(shù)開(kāi)始中序遍歷5.BinaryTree類的in_order()函數(shù)d6.post_order()函數(shù)defpost_order(self,start):#start是開(kāi)始遍歷的節(jié)點(diǎn)

node=startifnode==None:returnself.post_order(node.lchild)#從當(dāng)前節(jié)點(diǎn)的左子樹(shù)開(kāi)始后序遍歷

self.post_order(node.rchild)#從當(dāng)前節(jié)點(diǎn)的右子樹(shù)開(kāi)始后序遍歷

printnode.data,#打印當(dāng)前節(jié)點(diǎn)的數(shù)據(jù)6.post_order()函數(shù)defpost_ord7.isEmpty()函數(shù)fromtkinterimport*root=Tk()cv=Canvas(root,bg='red',width=200,height=100)cv.pack()root.mainloop()7.isEmpty()函數(shù)fromtkinterim8.length()函數(shù)deflength(self):returnlen(self.queue)8.length()函數(shù)deflength(self)【例8-3】if__name__=='__main__':arr=[]foriinrange(10):arr.append(i)printarrtree=BinaryTree()foriinarr:tree.add(i)

【例8-3】if__name__=='__main__print'preorder:'tree.pre_order(tree.root)print'\nin_order:'tree.in_order(tree.root)print'\npost_order:'tree.post_order(tree.root)print'preorder:'運(yùn)行結(jié)果如下：[0,1,2,3,4,5,6,7,8,9]preorder:0137849256in_order:7381940526post_order:7839415620運(yùn)行結(jié)果如下：[0,1,2,3,4,5,6,7【例8-3】使用的二叉樹(shù)【例8-3】使用的二叉樹(shù)8.5鏈表8.5.1鏈表的工作原理8.5.2利用Python實(shí)現(xiàn)單向鏈表的數(shù)據(jù)結(jié)構(gòu)8.5鏈表8.5.1鏈表的工作原理8.5.1鏈表的工作原理鏈表是一種非連續(xù)、非順序的存儲(chǔ)方式。鏈表由一系列結(jié)點(diǎn)組成，每個(gè)結(jié)點(diǎn)包括兩個(gè)部分，一部分是數(shù)據(jù)域，另一部分是指向下一個(gè)結(jié)點(diǎn)的指針域。鏈表可以分為單向鏈表、單向循環(huán)鏈表、雙向鏈表、雙向循環(huán)鏈表。單向鏈表是鏈表的一種，其特點(diǎn)是鏈表的鏈接方向是單向的，對(duì)鏈表的訪問(wèn)要通過(guò)順序讀取從頭部開(kāi)始。通過(guò)指針連接起來(lái)，但是只能單向遍歷的內(nèi)存塊。，如圖8-16所示。8.5.1鏈表的工作原理鏈表是一種非連續(xù)、非順序的存儲(chǔ)方單向循環(huán)鏈表單向循環(huán)鏈表的特點(diǎn)是表中最后一個(gè)結(jié)點(diǎn)的指針域指向頭結(jié)點(diǎn),整個(gè)鏈表形成一個(gè)環(huán)單向循環(huán)鏈表單向循環(huán)鏈表的特點(diǎn)是表中最后一個(gè)結(jié)點(diǎn)的指針域指向雙向鏈表雙向鏈表的每個(gè)數(shù)據(jù)結(jié)點(diǎn)中都有兩個(gè)指針，分別指向直接后繼和直接前驅(qū)。所以，從雙向鏈表中的任意一個(gè)結(jié)點(diǎn)開(kāi)始，都可以很方便地訪問(wèn)它的前驅(qū)結(jié)點(diǎn)和后繼結(jié)點(diǎn)。雙向鏈表雙向鏈表的每個(gè)數(shù)據(jù)結(jié)點(diǎn)中都有兩個(gè)指針，分別指向直接后雙向循環(huán)鏈表fromtkinterimport*root=Tk()cv=Canvas(root,bg='white',width=200,height=100)cv.create_rectangle(10,10,100,80,outline='blue',fill='red',width=2,stipple='gray12',)cv.pack()root.mainloop()雙向循環(huán)鏈表fromtkinterimport*8.5.2利用Python實(shí)現(xiàn)單向鏈表的數(shù)據(jù)結(jié)構(gòu)首先，定義一個(gè)鏈表節(jié)點(diǎn)類Node，代碼如下：classNode():__slots__=['_item','_next']#限定Node實(shí)例的屬性

def__init__(self,item):self._item=itemself._next=None#Node的指針部分默認(rèn)指向NonedefgetItem(self):returnself._itemdefgetNext(self):returnself._nextdefsetItem(self,newitem):self._item=newitemdefsetNext(self,newnext):self._next=newnext8.5.2利用Python實(shí)現(xiàn)單向鏈表的數(shù)據(jù)結(jié)構(gòu)首先，定2.類SinglelinkedList的初始函數(shù)classSingleLinkedList():def__init__(self):self._head=None#初始化鏈表為空表

self._size=02.類SinglelinkedList的初始函數(shù)class3.類SinglelinkedList的isEmpty()函數(shù)defisEmpty(self):returnself._head==None3.類SinglelinkedList的isEmpty()4.類SinglelinkedList的add()函數(shù)defadd(self,item):temp=Node(item)temp.setNext(self._head)self._head=temp4.類SinglelinkedList的add()函數(shù)5.類SinglelinkedList的append()函數(shù)defappend(self,item):temp=Node(item)ifself.isEmpty():self._head=temp#若為空表，將添加的元素設(shè)為第一個(gè)元素

else:current=self._headwhilecurrent.getNext()!=None:current=current.getNext()#遍歷鏈表

current.setNext(temp)#此時(shí)current為鏈表最后的元素5.類SinglelinkedList的append()6.類SinglelinkedList的index()函數(shù)defindex(self,item):current=self._headcount=0found=Nonewhilecurrent!=Noneandnotfound:count+=1ifcurrent.getItem()==item:found=Trueelse:current=current.getNext()iffound:returncountelse:raiseValueError,'%sisnotinlinkedlist'%item6.類SinglelinkedList的index()函7.類SinglelinkedList的remove()函數(shù)defremove(self,item):current=self._headpre=Nonewhilecurrent!=None:ifcurrent.getItem()==item:ifnotpre:self._head=current.getNext()else:pre.setNext(current.getNext())breakelse:pre=currentcurrent=current.getNext()7.類SinglelinkedList的remove()函8.類SinglelinkedList的insert()函數(shù)definsert(self,pos,item):ifpos<=1:self.add(item)elifpos>self.size():self.append(item)else:temp=Node(item)count=1pre=Nonecurrent=self._headwhilecount<pos:count+=1pre=currentcurrent=current.getNext()pre.setNext(temp)temp.setNext(current)8.類SinglelinkedList的insert()【例8-4】使用類SinglelinkedList的例子if__name__=='__main__':a=SingleLinkedList()#定義單向鏈表對(duì)象aforiinrange(1,10):#向單向鏈表對(duì)象a中添加10個(gè)元素a.append(i)printa.size()#打印單向鏈表的大小()#打印單向鏈表的大小printa.index(5)#打印位置5的元素a.remove(4)#移除位置4的元素()#遍歷鏈表a.insert(4,100)#在位置4插入元素100()#遍歷鏈表【例8-4】使用類SinglelinkedList的例子第8章Python數(shù)據(jù)結(jié)構(gòu)課程描述數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)存儲(chǔ)和組織數(shù)據(jù)的方式，指相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。數(shù)據(jù)結(jié)構(gòu)往往與高效的檢索算法和索引技術(shù)有關(guān)。本節(jié)介紹Python中的一些常用數(shù)據(jù)結(jié)構(gòu)的用法，包括棧、隊(duì)列、樹(shù)、鏈表、bitmap和圖。第8章Python數(shù)據(jù)結(jié)構(gòu)課程描述本章知識(shí)點(diǎn)數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)隊(duì)列bitmap棧鏈表圖本章知識(shí)點(diǎn)數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)8.1Python數(shù)據(jù)結(jié)構(gòu)概述8.1.1什么是數(shù)據(jù)結(jié)構(gòu)8.1.2數(shù)據(jù)結(jié)構(gòu)和算法的關(guān)系8.1Python數(shù)據(jù)結(jié)構(gòu)概述8.1.1什么是數(shù)據(jù)結(jié)8.1.1什么是數(shù)據(jù)結(jié)構(gòu)一個(gè)程序里面必然會(huì)有數(shù)據(jù)存在，同樣的一個(gè)或幾個(gè)數(shù)據(jù)要組織起來(lái)，可以有不同的組織方式，也就是不同的存儲(chǔ)方式。不同的組織方式就是不同的結(jié)構(gòu)，我們把這些數(shù)據(jù)組織在一起的結(jié)構(gòu)稱之為數(shù)據(jù)的結(jié)構(gòu)，也叫做數(shù)據(jù)結(jié)構(gòu)。比如，有一個(gè)字符串是"abc"，我們將其重新組織一下，比如通過(guò)list()函數(shù)將"abc"變成["a","b","c"]，那么這個(gè)時(shí)候數(shù)據(jù)就發(fā)生了重組，重組之后數(shù)據(jù)的結(jié)構(gòu)就變了。["a","b","c"]這種形式的數(shù)據(jù)的結(jié)構(gòu)被稱為列表。也就是說(shuō)列表是一種數(shù)據(jù)結(jié)構(gòu)，除此之外，還有元組、字典、棧、樹(shù)等數(shù)據(jù)結(jié)構(gòu)。Python的數(shù)據(jù)結(jié)構(gòu)有很多類型。其中有Python系統(tǒng)自己定義好的，不需要我們自己去定義。這種數(shù)據(jù)結(jié)構(gòu)被稱為Python的內(nèi)置數(shù)據(jù)結(jié)構(gòu)，比如列表、元組、字典等。而有些數(shù)據(jù)組織方式，Python系統(tǒng)里面沒(méi)有直接定義，需要我們自己去定義實(shí)現(xiàn)，這些數(shù)據(jù)組織方式稱為Python擴(kuò)展數(shù)據(jù)結(jié)構(gòu)，比如棧和隊(duì)列。8.1.1什么是數(shù)據(jù)結(jié)構(gòu)一個(gè)程序里面必然會(huì)有數(shù)據(jù)存在，同8.1.1彈出消息框使用showinfo()函數(shù)可以彈出提示消息框，方法如下showinfo(title=標(biāo)題,message=內(nèi)容)8.1.1彈出消息框使用showinfo()函數(shù)可以彈出提8.1.2數(shù)據(jù)結(jié)構(gòu)和算法的關(guān)系數(shù)據(jù)結(jié)構(gòu)和算法有著密切的聯(lián)系。因?yàn)閿?shù)據(jù)結(jié)構(gòu)是數(shù)據(jù)的組織方式，也就是數(shù)據(jù)的存儲(chǔ)方式。算法是指運(yùn)算方法，通俗地講，算法就是思維。數(shù)據(jù)結(jié)構(gòu)是靜態(tài)的，我們編寫(xiě)的程序是動(dòng)態(tài)的。程序要對(duì)數(shù)據(jù)進(jìn)行運(yùn)算，運(yùn)算的方法很多，不同的運(yùn)算方法就是不同的算法。當(dāng)然算法不是憑空出來(lái)的，它必須建立在數(shù)據(jù)的基礎(chǔ)上，所以數(shù)據(jù)結(jié)構(gòu)是算法的基礎(chǔ)，但同一個(gè)數(shù)據(jù)結(jié)構(gòu)運(yùn)用不同算法的效率是不同的。8.1.2數(shù)據(jù)結(jié)構(gòu)和算法的關(guān)系數(shù)據(jù)結(jié)構(gòu)和算法有著密切的聯(lián)8.2棧8.2.1棧的工作原理8.2.2利用Python列表實(shí)現(xiàn)棧的數(shù)據(jù)結(jié)構(gòu)8.2棧8.2.1棧的工作原理8.2.1棧的工作原理?xiàng)Ｊ且环N經(jīng)典的數(shù)據(jù)結(jié)構(gòu)，但它并不是Python的內(nèi)置數(shù)據(jù)結(jié)構(gòu)，而是屬于擴(kuò)展數(shù)據(jù)結(jié)構(gòu)。棧相當(dāng)于一端開(kāi)口、一端封閉的容器。棧支持出棧和進(jìn)棧2種操作。數(shù)據(jù)移動(dòng)到棧里面的過(guò)程叫做進(jìn)棧，也叫做壓棧、入棧；數(shù)據(jù)進(jìn)入到棧里面后，就到了棧頂，同時(shí)占了棧的一個(gè)位置。當(dāng)再進(jìn)入一個(gè)數(shù)據(jù)時(shí)，新的數(shù)據(jù)就占據(jù)了棧頂?shù)奈恢茫瓉?lái)的數(shù)據(jù)就被新的數(shù)據(jù)壓入到棧頂?shù)南乱粋€(gè)位置里。棧只能對(duì)其棧頂?shù)臄?shù)據(jù)進(jìn)行操作，所以這個(gè)時(shí)候原來(lái)的數(shù)據(jù)就不能被操作。8.2.1棧的工作原理?xiàng)Ｊ且环N經(jīng)典的數(shù)據(jù)結(jié)構(gòu)，但它并不是初始化時(shí)的棧初始化時(shí)的棧將數(shù)據(jù)A執(zhí)行進(jìn)棧操作將數(shù)據(jù)A執(zhí)行進(jìn)棧操作再將數(shù)據(jù)B執(zhí)行進(jìn)棧操作再將數(shù)據(jù)B執(zhí)行進(jìn)棧操作8.2.2利用Python列表實(shí)現(xiàn)棧的數(shù)據(jù)結(jié)構(gòu)1.構(gòu)造函數(shù)首先，在構(gòu)造函數(shù)中定義一個(gè)列表items用于實(shí)現(xiàn)棧的容器，代碼如下：#coding:utf8classStack:"""模擬棧"""def__init__(self):self.items=[]8.2.2利用Python列表實(shí)現(xiàn)棧的數(shù)據(jù)結(jié)構(gòu)1.構(gòu)造2.isEmpty()函數(shù)defisEmpty(self):returnlen(self.items)==02.isEmpty()函數(shù)defisEmpty(self3.push()函數(shù)defpush(self,item):self.items.append(item)3.push()函數(shù)defpush(self,item4.pop()函數(shù)defpop(self):returnself.items.pop()4.pop()函數(shù)defpop(self):5.peek()函數(shù)defpop(self):returnself.items.pop()5.peek()函數(shù)defpop(self):6.size()函數(shù)defsize(self):returnlen(self.items)6.size()函數(shù)defsize(self):【例8-1】s=Stack()#創(chuàng)建棧對(duì)象print(s.isEmpty())#打印棧是否為空s.push('DataA')#進(jìn)棧DataAs.push('DataB')#進(jìn)棧DataAprint(s.peek())#打印棧頂元素s.push('DataC')#進(jìn)棧DataCprint(s.size())#打印棧的大小print(s.isEmpty())#打印棧是否為空s.push('DataD')#進(jìn)棧DataDprint(s.pop())#出棧print(s.pop())#出棧print(s.size())#打印棧的大小)【例8-1】s=Stack()#創(chuàng)建棧對(duì)象8.3隊(duì)列隊(duì)列是一種經(jīng)典的數(shù)據(jù)結(jié)構(gòu)，它也不是Python的內(nèi)置數(shù)據(jù)結(jié)構(gòu)，而是屬于擴(kuò)展數(shù)據(jù)結(jié)構(gòu)。隊(duì)列相當(dāng)于兩邊都開(kāi)口的容器。但是一邊只能進(jìn)行刪除操作，而不能進(jìn)行插入操作；另一邊只能進(jìn)行插入操作，而不能進(jìn)行刪除操作。進(jìn)行插入操作的這一端叫做隊(duì)尾，進(jìn)行刪除操作的這一端叫做隊(duì)首。所以，隊(duì)列中的數(shù)據(jù)是從隊(duì)尾進(jìn)隊(duì)首出的。隊(duì)列的數(shù)據(jù)元素又稱為隊(duì)列元素。在隊(duì)列中插入一個(gè)隊(duì)列元素稱為入隊(duì)，從隊(duì)列中刪除一個(gè)隊(duì)列元素成為出隊(duì)。8.3隊(duì)列隊(duì)列是一種經(jīng)典的數(shù)據(jù)結(jié)構(gòu)，它也不是Python初始化時(shí)的隊(duì)列初始化時(shí)的隊(duì)列將數(shù)據(jù)A執(zhí)行入隊(duì)操作將數(shù)據(jù)A執(zhí)行入隊(duì)操作將數(shù)據(jù)B執(zhí)行入隊(duì)操作將數(shù)據(jù)B執(zhí)行入隊(duì)操作再將數(shù)據(jù)C執(zhí)行進(jìn)棧操作再將數(shù)據(jù)C執(zhí)行進(jìn)棧操作再將數(shù)據(jù)C執(zhí)行進(jìn)棧操作再將數(shù)據(jù)C執(zhí)行進(jìn)棧操作將數(shù)據(jù)A執(zhí)行出隊(duì)操作將數(shù)據(jù)A執(zhí)行出隊(duì)操作8.3.2利用Python列表實(shí)現(xiàn)隊(duì)列的數(shù)據(jù)結(jié)構(gòu)本節(jié)介紹一個(gè)Python自定義類Queue，它的功能是利用Python列表實(shí)現(xiàn)隊(duì)列的數(shù)據(jù)結(jié)構(gòu)。8.3.2利用Python列表實(shí)現(xiàn)隊(duì)列的數(shù)據(jù)結(jié)構(gòu)本節(jié)介紹1.構(gòu)造函數(shù)#coding:utf8classQueue(object):def__init__(self):self.queue=[]1.構(gòu)造函數(shù)#coding:utf82.isempty()函數(shù)isempty()函數(shù)用于判斷隊(duì)列是否為空。如果隊(duì)列為空，則isempty()函數(shù)返回True，否則返回False。isempty()函數(shù)的代碼如下：

defisempty(self):returnself.queue==[]2.isempty()函數(shù)isempty()函數(shù)用于判斷隊(duì)3.enqueue()函數(shù)defenqueue(self,item):self.queue.append(item)3.enqueue()函數(shù)defenqueue(sel4.dequeue()函數(shù)defdequeue(self):ifself.queue!=[]:returnself.queue.pop(0)else:returnNone4.dequeue()函數(shù)defdequeue(sel5.head()函數(shù)head()函數(shù)用于返回隊(duì)首元素，但并不刪除該元素。代碼如下：

defhead(self):ifself.queue!=[]:returnself.queue[0]else:returnNone5.head()函數(shù)head()函數(shù)用于返回隊(duì)首元素，6.tail()函數(shù)tail()函數(shù)用于返回隊(duì)尾元素，但并不刪除該元素。代碼如下：

deftail(self):ifself.queue!=[]:returnself.queue[-1]else:returnNone6.tail()函數(shù)tail()函數(shù)用于返回隊(duì)尾元素，7.length()函數(shù)length()函數(shù)用于返回隊(duì)列的大小。代碼如下：

deflength(self):returnlen(self.queue)7.length()函數(shù)length()函數(shù)用于返回隊(duì)列的【例8-2】q=Queue()#創(chuàng)建隊(duì)列對(duì)象print(q.isempty())#打印隊(duì)列是否為空q.enqueue('DataA')#入隊(duì)DataAq.enqueue('DataB')#入隊(duì)DataAprint(q.head())#打印對(duì)首元素print(q.tail())#打印隊(duì)尾元素q.enqueue('DataC')#入隊(duì)DataCprint(q.length())#打印隊(duì)列的大小print(q.isempty())#打印隊(duì)列是否為空q.enqueue('DataD')#入隊(duì)DataDprint(q.dequeue())#出隊(duì)print(q.dequeue())#出隊(duì)print(q.length())#打印隊(duì)列的大小)【例8-2】q=Queue()#創(chuàng)建隊(duì)列對(duì)象運(yùn)行結(jié)果如下：TrueDataADataB3FalseDataADataB2運(yùn)行結(jié)果如下：True8.4樹(shù)8.4.1樹(shù)的工作原理8.4.2遍歷二叉樹(shù)8.4.3在Python程序中實(shí)現(xiàn)樹(shù)的數(shù)據(jù)結(jié)構(gòu)8.4樹(shù)8.4.1樹(shù)的工作原理8.4.1樹(shù)的工作原理樹(shù)的定義首先有且只有一個(gè)根節(jié)點(diǎn)，另外他有Ｎ個(gè)不相交的子集，每個(gè)子集都是一個(gè)子樹(shù)。8.4.1樹(shù)的工作原理樹(shù)的定義首先有且只有一個(gè)根節(jié)點(diǎn)，另空樹(shù)空樹(shù)只有一個(gè)根結(jié)點(diǎn)的二叉樹(shù)只有一個(gè)根結(jié)點(diǎn)的二叉樹(shù)有左子樹(shù)的二叉樹(shù)有左子樹(shù)的二叉樹(shù)只有右子樹(shù)的二叉樹(shù)只有右子樹(shù)的二叉樹(shù)2完全二叉樹(shù)2完全二叉樹(shù)8.4.2遍歷二叉樹(shù)“遍歷”是二叉樹(shù)各種操作的基礎(chǔ)。二叉樹(shù)是一種非線性結(jié)構(gòu)，遍歷二叉樹(shù)不像遍歷線性鏈表那樣容易，無(wú)法通過(guò)簡(jiǎn)單的循環(huán)實(shí)現(xiàn)。遍歷二叉樹(shù)就是要讓樹(shù)中的所有節(jié)點(diǎn)被且僅被訪問(wèn)一次，即按一定規(guī)律排列成一個(gè)線性隊(duì)列。二叉樹(shù)包含3個(gè)部分，即根結(jié)點(diǎn)、左子樹(shù)和右子樹(shù)。根據(jù)這3個(gè)部分的訪問(wèn)次序?qū)Χ鏄?shù)的遍歷進(jìn)行分類，可以將遍歷二叉樹(shù)的方法分為3種類型，分別稱為“先序遍歷”、“中序遍歷”和“后序遍歷”。先序遍歷指先訪問(wèn)根節(jié)點(diǎn)，然后再訪問(wèn)左子樹(shù)，最后訪問(wèn)右子樹(shù)；中序遍歷指訪問(wèn)左子樹(shù)，然后再訪問(wèn)根節(jié)點(diǎn)，最后訪問(wèn)右子樹(shù)；中序遍歷指先訪問(wèn)根節(jié)點(diǎn)，然后訪問(wèn)左子樹(shù)，最后訪問(wèn)右子樹(shù)；后序遍歷指訪問(wèn)左子樹(shù)，然后再訪問(wèn)右子樹(shù)，最后訪問(wèn)根節(jié)點(diǎn)。8.4.2遍歷二叉樹(shù)“遍歷”是二叉樹(shù)各種操作的基礎(chǔ)。二8.4.3在Python程序中實(shí)現(xiàn)樹(shù)的數(shù)據(jù)結(jié)構(gòu)本節(jié)介紹一個(gè)Python自定義類BinaryTree，它的功能是在Python程序中實(shí)現(xiàn)樹(shù)的數(shù)據(jù)結(jié)構(gòu)。8.4.3在Python程序中實(shí)現(xiàn)樹(shù)的數(shù)據(jù)結(jié)構(gòu)本節(jié)介紹一1.定義樹(shù)節(jié)點(diǎn)類Node首先，定義一個(gè)樹(shù)節(jié)點(diǎn)類Node，代碼如下：classNode(object):def__init__(self,data=-1,lchild=None,rchild=None):self.data=dataself.lchild=lchildself.rchild=rchild1.定義樹(shù)節(jié)點(diǎn)類Node首先，定義一個(gè)樹(shù)節(jié)點(diǎn)類Node，代2.BinaryTree類的構(gòu)造函數(shù)classBinaryTree(object):def__init__(self):self.root=Node()2.BinaryTree類的構(gòu)造函數(shù)classBin3.BinaryTree類的add()函數(shù)defadd(self,data):#data為新節(jié)點(diǎn)的數(shù)據(jù)

node=Node(data)#創(chuàng)建新節(jié)點(diǎn)

ifself.isEmpty():#如果二叉樹(shù)為空，則將新節(jié)點(diǎn)作為二叉樹(shù)的根節(jié)點(diǎn)

self.root=nodeelse:tree_node=self.rootqueue=[]#以列表存儲(chǔ)二叉樹(shù)

queue.append(self.root)whilequeue:#遍歷二叉樹(shù)

tree_node=queue.pop(0)

3.BinaryTree類的add()函數(shù)defadiftree_node.lchild==None:#如果當(dāng)前節(jié)點(diǎn)的左孩子為空，則將新節(jié)點(diǎn)作為當(dāng)前節(jié)點(diǎn)的左孩子

tree_node.lchild=nodereturneliftree_node.rchild==None:#如果當(dāng)前節(jié)點(diǎn)的右孩子為空，則將新節(jié)點(diǎn)作為當(dāng)前節(jié)點(diǎn)的右孩子

tree_node.rchild=nodereturnelse:queue.append(tree_node.lchild)queue.append(tree_node.rchild)iftree_node.lchild==None:4.BinaryTree類的pre_order()函數(shù)defpre_order(self,start):#start是開(kāi)始遍歷的節(jié)點(diǎn)

node=startifnode==None:#如果當(dāng)前節(jié)點(diǎn)為空，則返回

returnprintnode.data,#打印當(dāng)前節(jié)點(diǎn)的數(shù)據(jù)

#如果當(dāng)前節(jié)點(diǎn)的左右子樹(shù)都為空，則返回

ifnode.lchild==Noneandnode.rchild==None:returnself.pre_order(node.lchild)#從當(dāng)前節(jié)點(diǎn)的左子樹(shù)開(kāi)始先序遍歷

self.pre_order(node.rchild)#從當(dāng)前節(jié)點(diǎn)的右子樹(shù)開(kāi)始先序遍歷4.BinaryTree類的pre_order()函數(shù)5.BinaryTree類的in_order()函數(shù)defin_order(self,start):#start是開(kāi)始遍歷的節(jié)點(diǎn)

node=startifnode==None:returnself.in_order(node.lchild)#從當(dāng)前節(jié)點(diǎn)的左子樹(shù)開(kāi)始中序遍歷

printnode.data,#打印當(dāng)前節(jié)點(diǎn)的數(shù)據(jù)

self.in_order(node.rchild)#從當(dāng)前節(jié)點(diǎn)的右子樹(shù)開(kāi)始中序遍歷5.BinaryTree類的in_order()函數(shù)d6.post_order()函數(shù)defpost_order(self,start):#start是開(kāi)始遍歷的節(jié)點(diǎn)

node=startifnode==None:returnself.post_order(node.lchild)#從當(dāng)前節(jié)點(diǎn)的左子樹(shù)開(kāi)始后序遍歷

self.post_order(node.rchild)#從當(dāng)前節(jié)點(diǎn)的右子樹(shù)開(kāi)始后序遍歷

printnode.data,#打印當(dāng)前節(jié)點(diǎn)的數(shù)據(jù)6.post_order()函數(shù)defpost_ord7.isEmpty()函數(shù)fromtkinterimport*root=Tk()cv=Canvas(root,bg='red',width=200,height=100)cv.pack()root.mainloop()7.isEmpty()函數(shù)fromtkinterim8.length()函數(shù)deflength(self):returnlen(self.queue)8.length()函數(shù)deflength(self)【例8-3】if__name__=='__main__':arr=[]foriinrange(10):arr.append(i)printarrtree=BinaryTree()foriinarr:tree.add(i)

【例8-3】if__name__=='__main__print'preorder:'tree.pre_order(tree.root)print'\nin_order:'tree.in_order(tree.root)print'\npost_order:'tree.post_order(tree.root)print'preorder:'運(yùn)行結(jié)果如下：[0,1,2,3,4,5,6,7,8,9]preorder:0137849256in_order:7381940526post_order:7839415620運(yùn)行結(jié)果如下：[0,1,2,3,4,5,6,7【例8-3】使用的二叉樹(shù)【例8-3】使用的二叉樹(shù)8.5鏈表8.5.1鏈表的工作原理8.5.2利用Python實(shí)現(xiàn)單向鏈表的數(shù)據(jù)結(jié)構(gòu)8.5鏈表8.5.1鏈表的工作原理8.5.1鏈表的工作原理鏈表是一種非連續(xù)、非順序的存儲(chǔ)方式。鏈表由一系列結(jié)點(diǎn)組成，每個(gè)結(jié)點(diǎn)包括兩個(gè)部分，一部分是數(shù)據(jù)域，另一部分是指向下一個(gè)結(jié)點(diǎn)的指針域。鏈表可以分為單向鏈表、單向循環(huán)鏈表、雙向鏈表、雙向循環(huán)鏈表。單向鏈表是鏈表的一種，其特點(diǎn)是鏈表的鏈接方向是單向的，對(duì)鏈表的訪問(wèn)要通過(guò)順序讀取從頭部開(kāi)始。通過(guò)指針連接起來(lái)，但是只能單向遍歷的內(nèi)存塊。，如圖8-16所示。8.5.1鏈表的工作原理鏈表是一種非連續(xù)、非順序的存儲(chǔ)方單向循環(huán)鏈表單向循環(huán)鏈表的特點(diǎn)是表中最后一個(gè)結(jié)點(diǎn)的指針域指向頭結(jié)點(diǎn),整個(gè)鏈表形成一個(gè)環(huán)單向循環(huán)鏈表單向循環(huán)鏈表的特點(diǎn)是表中最后一個(gè)結(jié)點(diǎn)的指針域指向雙向鏈表雙向鏈表的每個(gè)數(shù)據(jù)結(jié)點(diǎn)中都有兩個(gè)指針，分別指向直接后繼和直接前驅(qū)。所以，從雙向鏈表中的任意一個(gè)結(jié)點(diǎn)開(kāi)始，都可以很方便地訪問(wèn)它的前驅(qū)結(jié)點(diǎn)和后繼結(jié)點(diǎn)。雙向鏈表雙向鏈表的每個(gè)數(shù)據(jù)結(jié)點(diǎn)中都有兩個(gè)指針，分別指向直接后雙向循環(huán)鏈表fromtkinterimport*root=Tk()cv=Canvas(root,bg='white',width=200,height=100)cv.create_rectangle(10,10,100,80,outline='blue',fill='red',width=2,stipple='gray12',)cv.pack()root.mainloop()雙向循環(huán)鏈表fromtkinterimport*8.5.2利用Python實(shí)現(xiàn)單向鏈表的數(shù)據(jù)結(jié)構(gòu)首先，定義一個(gè)鏈表節(jié)點(diǎn)類Node，代碼如下：classNode():__slots__=['_item','_next']#限定Node實(shí)例的屬性

def__init__(self,item):self._item=itemself._next=None#Node的指針部分默認(rèn)指向NonedefgetItem(self):returnself._itemdefgetNext(self):returnself._nextdefsetItem(self,newitem):self._item=newitemdefsetNext(self,newnext):self._next=newnext8.5.2利用Python實(shí)現(xiàn)單向鏈表的數(shù)據(jù)結(jié)構(gòu)首先，定2.類Singlelin