第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ì)列、樹、鏈表、bitmap和圖。本章知識(shí)點(diǎn)數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)隊(duì)列bitmap棧鏈表圖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.1.1什么是數(shù)據(jù)結(jié)構(gòu)一個(gè)程序里面必然會(huì)有數(shù)據(jù)存在，同樣的一個(gè)或幾個(gè)數(shù)據(jù)要組織起來，可以有不同的組織方式，也就是不同的存儲(chǔ)方式。不同的組織方式就是不同的結(jié)構(gòu)，我們把這些數(shù)據(jù)組織在一起的結(jié)構(gòu)稱之為數(shù)據(jù)的結(jié)構(gòu)，也叫做數(shù)據(jù)結(jié)構(gòu)。比如，有一個(gè)字符串是"abc"，我們將其重新組織一下，比如通過list()函數(shù)將"abc"變成["a","b","c"]，那么這個(gè)時(shí)候數(shù)據(jù)就發(fā)生了重組，重組之后數(shù)據(jù)的結(jié)構(gòu)就變了。["a","b","c"]這種形式的數(shù)據(jù)的結(jié)構(gòu)被稱為列表。也就是說列表是一種數(shù)據(jù)結(jié)構(gòu)，除此之外，還有元組、字典、棧、樹等數(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)里面沒有直接定義，需要我們自己去定義實(shí)現(xiàn)，這些數(shù)據(jù)組織方式稱為Python擴(kuò)展數(shù)據(jù)結(jié)構(gòu)，比如棧和隊(duì)列。8.1.1彈出消息框使用showinfo()函數(shù)可以彈出提示消息框，方法如下showinfo(title=標(biāo)題,message=內(nèi)容)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)的，我們編寫的程序是動(dòng)態(tài)的。程序要對(duì)數(shù)據(jù)進(jìn)行運(yùn)算，運(yùn)算的方法很多，不同的運(yùn)算方法就是不同的算法。當(dāng)然算法不是憑空出來的，它必須建立在數(shù)據(jù)的基礎(chǔ)上，所以數(shù)據(jù)結(jié)構(gòu)是算法的基礎(chǔ)，但同一個(gè)數(shù)據(jù)結(jié)構(gòu)運(yùn)用不同算法的效率是不同的。8.2棧8.2.1棧的工作原理8.2.2利用Python列表實(shí)現(xiàn)棧的數(shù)據(jù)結(jié)構(gòu)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)于一端開口、一端封閉的容器。棧支持出棧和進(jìn)棧2種操作。數(shù)據(jù)移動(dòng)到棧里面的過程叫做進(jìn)棧，也叫做壓棧、入棧；數(shù)據(jù)進(jìn)入到棧里面后，就到了棧頂，同時(shí)占了棧的一個(gè)位置。當(dāng)再進(jìn)入一個(gè)數(shù)據(jù)時(shí)，新的數(shù)據(jù)就占據(jù)了棧頂?shù)奈恢茫瓉淼臄?shù)據(jù)就被新的數(shù)據(jù)壓入到棧頂?shù)南乱粋€(gè)位置里。棧只能對(duì)其棧頂?shù)臄?shù)據(jù)進(jìn)行操作，所以這個(gè)時(shí)候原來的數(shù)據(jù)就不能被操作。初始化時(shí)的棧將數(shù)據(jù)A執(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=[]2.isEmpty()函數(shù)def

isEmpty(self):returnlen(self.items)==03.push()函數(shù)defpush(self,item):self.items.append(item)4.pop()函數(shù)defpop(self):returnself.items.pop()5.peek()函數(shù)defpop(self):returnself.items.pop()6.size()函數(shù)defsize(self):returnlen(self.items)【例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.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)于兩邊都開口的容器。但是一邊只能進(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ì)。初始化時(shí)的隊(duì)列將數(shù)據(jù)A執(zhí)行入隊(duì)操作將數(shù)據(jù)B執(zhí)行入隊(duì)操作再將數(shù)據(jù)C執(zhí)行進(jìn)棧操作再將數(shù)據(jù)C執(zhí)行進(jìn)棧操作將數(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)。1.構(gòu)造函數(shù)#coding:utf8classQueue(object):def__init__(self):self.queue=[]2.isempty()函數(shù)isempty()函數(shù)用于判斷隊(duì)列是否為空。如果隊(duì)列為空，則isempty()函數(shù)返回True，否則返回False。isempty()函數(shù)的代碼如下：

def

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

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

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

deflength(self):returnlen(self.queue)【例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ì)列的大小)運(yùn)行結(jié)果如下：TrueDataADataB3FalseDataADataB28.4樹8.4.1樹的工作原理8.4.2遍歷二叉樹8.4.3在Python程序中實(shí)現(xiàn)樹的數(shù)據(jù)結(jié)構(gòu)8.4.1樹的工作原理樹的定義首先有且只有一個(gè)根節(jié)點(diǎn)，另外他有Ｎ個(gè)不相交的子集，每個(gè)子集都是一個(gè)子樹?？諛渲挥幸粋€(gè)根結(jié)點(diǎn)的二叉樹有左子樹的二叉樹只有右子樹的二叉樹2完全二叉樹8.4.2遍歷二叉樹“遍歷”是二叉樹各種操作的基礎(chǔ)。二叉樹是一種非線性結(jié)構(gòu)，遍歷二叉樹不像遍歷線性鏈表那樣容易，無法通過簡單的循環(huán)實(shí)現(xiàn)。遍歷二叉樹就是要讓樹中的所有節(jié)點(diǎn)被且僅被訪問一次，即按一定規(guī)律排列成一個(gè)線性隊(duì)列。二叉樹包含3個(gè)部分，即根結(jié)點(diǎn)、左子樹和右子樹。根據(jù)這3個(gè)部分的訪問次序?qū)Χ鏄涞谋闅v進(jìn)行分類，可以將遍歷二叉樹的方法分為3種類型，分別稱為“先序遍歷”、“中序遍歷”和“后序遍歷”。先序遍歷指先訪問根節(jié)點(diǎn)，然后再訪問左子樹，最后訪問右子樹；中序遍歷指訪問左子樹，然后再訪問根節(jié)點(diǎn)，最后訪問右子樹；中序遍歷指先訪問根節(jié)點(diǎn)，然后訪問左子樹，最后訪問右子樹；后序遍歷指訪問左子樹，然后再訪問右子樹，最后訪問根節(jié)點(diǎn)。8.4.3在Python程序中實(shí)現(xiàn)樹的數(shù)據(jù)結(jié)構(gòu)本節(jié)介紹一個(gè)Python自定義類BinaryTree，它的功能是在Python程序中實(shí)現(xiàn)樹的數(shù)據(jù)結(jié)構(gòu)。1.定義樹節(jié)點(diǎn)類Node首先，定義一個(gè)樹節(jié)點(diǎn)類Node，代碼如下：classNode(object):def__init__(self,data=-1,lchild=None,rchild=None):self.data=dataself.lchild=lchildself.rchild=rchild2.BinaryTree類的構(gòu)造函數(shù)classBinaryTree(object):def__init__(self):self.root=Node()3.BinaryTree類的add()函數(shù)defadd(self,data):#data為新節(jié)點(diǎn)的數(shù)據(jù)

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

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

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

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

tree_node=queue.pop(0)

iftree_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)4.BinaryTree類的pre_order()函數(shù)defpre_order(self,start):#start是開始遍歷的節(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)的左右子樹都為空，則返回

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

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

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

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

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

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

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

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

print'preorder:'

tree.pre_order(tree.root)print'\nin_order:'

tree.in_order(tree.root)print'\npost_order:'

tree.post_order(tree.root)運(yùn)行結(jié)果如下：[0,1,2,3,4,5,6,7,8,9]preorder:0137849256in_order:7381940526post_order:7839415620【例8-3】使用的二叉樹8.5鏈表8.5.1鏈表的工作原理8.5.2利用Python實(shí)現(xiàn)單向鏈表的數(shù)據(jù)結(jié)構(gòu)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ì)鏈表的訪問要通過順序讀取從頭部開始。通過指針連接起來，但是只能單向遍歷的內(nèi)存塊。，如圖8-16所示。單向循環(huán)鏈表單向循環(huán)鏈表的特點(diǎn)是表中最后一個(gè)結(jié)點(diǎn)的指針域指向頭結(jié)點(diǎn),整個(gè)鏈表形成一個(gè)環(huán)雙向鏈表雙向鏈表的每個(gè)數(shù)據(jù)結(jié)點(diǎn)中都有兩個(gè)指針，分別指向直接后繼和直接前驅(qū)。所以，從雙向鏈表中的任意一個(gè)結(jié)點(diǎn)開始，都可以很方便地訪問它的前驅(qū)結(jié)點(diǎn)和后繼結(jié)點(diǎn)。雙向循環(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()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=item

self._next=None#Node的指針部分默認(rèn)指向None

def

getItem(self):returnself._item

def

getNext(self):returnself._next

def

setItem(self,newitem):

self._item=newitem

def

setNext(self,newnext):

self._next=newnext2.類SinglelinkedList的初始函數(shù)classSingleLinkedList():

def__init__(self):

self._head=None#初始化鏈表為空表

self._size=03.類SinglelinkedList的isEmpty()函數(shù)defisEmpty(self):returnself._head==None4.類SinglelinkedList的add()函數(shù)defadd(self,item):temp=Node(item)temp.setNext(self._head)self._head=temp5.類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為鏈表最后的元素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'%item7.類SinglelinkedList的remove()函數(shù)defremove(self,item):current=self._headpre=Nonewhilecurrent!=None: