第27周-python3.5零基礎(chǔ)高級(jí)項(xiàng)目剖析共07章節(jié)27源碼數(shù)據(jù)結(jié)構(gòu)

數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)什么是數(shù)據(jù)結(jié)構(gòu)？簡(jiǎn)單來說，數(shù)據(jù)結(jié)構(gòu)就是設(shè)計(jì)數(shù)據(jù)以何種方式組織并存儲(chǔ)在計(jì)算機(jī)中。比如：列表、集合與字典等都是一種數(shù)據(jù)結(jié)構(gòu)。N.Wirth:“程序=數(shù)據(jù)結(jié)構(gòu)+算法”2023年3月26日算法基礎(chǔ)2列表列表：在其他編程語言中稱為“數(shù)組”，是一種基本的數(shù)據(jù)結(jié)構(gòu)類型。關(guān)于列表的問題：列表中元素使如何存儲(chǔ)的？列表提供了哪些基本的操作？這些操作的時(shí)間復(fù)雜度是多少？2023年3月26日算法基礎(chǔ)3棧棧(Stack)是一個(gè)數(shù)據(jù)集合，可以理解為只能在一端進(jìn)行插入或刪除操作的列表。棧的特點(diǎn)：后進(jìn)先出（last-in,

first-out）棧的概念：棧頂棧底棧的基本操作：進(jìn)棧（壓棧）：push出棧：pop取棧頂：gettop2023年3月26日算法基礎(chǔ)4棧的Python實(shí)現(xiàn)不需要自己定義，使用列表結(jié)構(gòu)即可。進(jìn)棧函數(shù)：append出棧函數(shù)：pop查看棧頂函數(shù)：li[-1]2023年3月26日算法基礎(chǔ)5棧的應(yīng)用——括號(hào)匹配問題括號(hào)匹配問題：給一個(gè)字符串，其中包含小括號(hào)、中括號(hào)、大括號(hào)，求該字符串中的括號(hào)是否匹配。例如：()()[]{} 匹配([{()}]) 匹配[]( 不匹配[(]) 不匹配2023年3月26日算法基礎(chǔ)6括號(hào)匹配問題——實(shí)現(xiàn)defcheck_kuohao(s):

stack=[]

forcharins:

ifcharin{'(','[','{'}:

stack.append(char)

elifchar==')':

iflen(stack)>0andstack[-1]=='(':

stack.pop()

else:

returnFalse

elifchar==']':

iflen(stack)>0andstack[-1]=='[':

stack.pop()

else:

returnFalse

elifchar=='}':

iflen(stack)>0andstack[-1]=='{':

stack.pop()

else:

returnFalse

iflen(stack)==0:

returnTrue

else:

returnFalse2023年3月26日算法基礎(chǔ)7棧的應(yīng)用——迷宮問題給一個(gè)二維列表，表示迷宮（0表示通道，1表示圍墻）。給出算法，求一條走出迷宮的路徑。maze=[

[1,1,1,1,1,1,1,1,1,1],

[1,0,0,1,0,0,0,1,0,1],

[1,0,0,1,0,0,0,1,0,1],

[1,0,0,0,0,1,1,0,0,1],

[1,0,1,1,1,0,0,0,0,1],

[1,0,0,0,1,0,0,0,0,1],

[1,0,1,0,0,0,1,0,0,1],

[1,0,1,1,1,0,1,1,0,1],

[1,1,0,0,0,0,0,0,0,1],

[1,1,1,1,1,1,1,1,1,1]

]2023年3月26日算法基礎(chǔ)8起點(diǎn)終點(diǎn)解決思路在一個(gè)迷宮節(jié)點(diǎn)(x,y)上，可以進(jìn)行四個(gè)方向的探查：maze[x-1][y],

maze[x+1][y],

maze[x][y-1],

maze[x][y+1]思路：從一個(gè)節(jié)點(diǎn)開始，任意找下一個(gè)能走的點(diǎn)，當(dāng)找不到能走的點(diǎn)時(shí)，退回上一個(gè)點(diǎn)尋找是否有其他方向的點(diǎn)。方法：創(chuàng)建一個(gè)空棧，首先將入口位置進(jìn)棧。當(dāng)棧不空時(shí)循環(huán)：獲取棧頂元素，尋找下一個(gè)可走的相鄰方塊，如果找不到可走的相鄰方塊，說明當(dāng)前位置是死胡同，進(jìn)行回溯（就是講當(dāng)前位置出棧，看前面的點(diǎn)是否還有別的出路）2023年3月26日算法基礎(chǔ)9迷宮問題——棧實(shí)現(xiàn)dirs=[lambdax,y:(x+1,y),lambdax,y:(x-1,y),lambdax,y:(x,y-1),lambdax,y:(x,y+1)]

defmgpath(x1,y1,x2,y2):

stack=[]

stack.append((x1,y1))

whilelen(stack)>0:#棧不空時(shí)循環(huán)

curNode=stack[-1]#查看棧頂元素

ifcurNode[0]==x2andcurNode[1]:

#到達(dá)終點(diǎn)

forpinstack:

print(p)

break

fordirindirs:

nextNode=dir(*curNode)

ifmg[nextNode[0]][nextNode[1]]==0:#找到了下一個(gè)方塊

stack.append(nextNode)

mg[nextNode[0]][nextNode[1]]=-1#標(biāo)記為已經(jīng)走過，防止死循環(huán)

break

else:

mg[curNode[0]][curNode[1]]=-1#死路一條

stack.pop()

returnFalse2023年3月26日算法基礎(chǔ)10隊(duì)列隊(duì)列(Queue)是一個(gè)數(shù)據(jù)集合，僅允許在列表的一端進(jìn)行插入，另一端進(jìn)行刪除。進(jìn)行插入的一端稱為隊(duì)尾(rear)，插入動(dòng)作稱為進(jìn)隊(duì)或入隊(duì)進(jìn)行刪除的一端稱為隊(duì)頭(front)，刪除動(dòng)作稱為出隊(duì)隊(duì)列的性質(zhì)：先進(jìn)先出(First-in,

First-out)雙向隊(duì)列：隊(duì)列的兩端都允許進(jìn)行進(jìn)隊(duì)和出隊(duì)操作。2023年3月26日算法基礎(chǔ)11隊(duì)列的實(shí)現(xiàn)隊(duì)列能否簡(jiǎn)單用列表實(shí)現(xiàn)？為什么？使用方法：from

collections

import

deque創(chuàng)建隊(duì)列：queue

=

deque(li)進(jìn)隊(duì)：append出隊(duì)：popleft雙向隊(duì)列隊(duì)首進(jìn)隊(duì)：appendleft雙向隊(duì)列隊(duì)尾進(jìn)隊(duì)：pop2023年3月26日算法基礎(chǔ)12隊(duì)列的實(shí)現(xiàn)原理初步設(shè)想：列表+兩個(gè)下標(biāo)指針創(chuàng)建一個(gè)列表和兩個(gè)變量，front變量指向隊(duì)首，rear變量指向隊(duì)尾。初始時(shí)，front和rear都為0。進(jìn)隊(duì)操作：元素寫到li[rear]的位置，rear自增1。出隊(duì)操作：返回li[front]的元素，front自減1。這種實(shí)現(xiàn)的問題？2023年3月26日算法基礎(chǔ)13隊(duì)列的實(shí)現(xiàn)原理——環(huán)形隊(duì)列改進(jìn)方案：將列表首尾邏輯上連接起來。2023年3月26日算法基礎(chǔ)14隊(duì)列的實(shí)現(xiàn)原理——環(huán)形隊(duì)列環(huán)形隊(duì)列：當(dāng)隊(duì)尾指針front

==

Maxsize

+

1時(shí)，再前進(jìn)一個(gè)位置就自動(dòng)到0。實(shí)現(xiàn)方式：求余數(shù)運(yùn)算隊(duì)首指針前進(jìn)1：front

=

(front

+

1)

%

MaxSize隊(duì)尾指針前進(jìn)1：rear

=

(rear

+

1)

%

MaxSize隊(duì)空條件：rear

==

front隊(duì)滿條件：(rear

+

1)

%

MaxSize

==

front2023年3月26日算法基礎(chǔ)15隊(duì)列的應(yīng)用——迷宮問題思路：從一個(gè)節(jié)點(diǎn)開始，尋找所有下面能繼續(xù)走的點(diǎn)。繼續(xù)尋找，直到找到出口。方法：創(chuàng)建一個(gè)空隊(duì)列，將起點(diǎn)位置進(jìn)隊(duì)。在隊(duì)列不為空時(shí)循環(huán)：出隊(duì)一次。如果當(dāng)前位置為出口，則結(jié)束算法；否則找出當(dāng)前方塊的4個(gè)相鄰方塊中可走的方塊，全部進(jìn)隊(duì)。2023年3月26日算法基礎(chǔ)16迷宮問題——隊(duì)列實(shí)現(xiàn)defmgpath(x1,y1,x2,y2):

queue=deque()

path=[]

queue.append((x1,y1,-1))

whilelen(queue)>0:

curNode=queue.popleft()

path.append(curNode)

ifcurNode[0]==x2andcurNode[1]==y2:

#到達(dá)終點(diǎn)

print(path)

returnTrue

fordirindirs:

nextNode=dir(curNode[0],curNode[1])

ifmg[nextNode[0]][nextNode[1]]==0:#找到下一個(gè)方塊

queue.append((*nextNode,len(path)-1))

mg[nextNode[0]][nextNode[1]]=-1#標(biāo)記為已經(jīng)走過

returnFalse2023年3月26日算法基礎(chǔ)17鏈表鏈表中每一個(gè)元素都是一個(gè)對(duì)象，每個(gè)對(duì)象稱為一個(gè)節(jié)點(diǎn)，包含有數(shù)據(jù)域key和指向下一個(gè)節(jié)點(diǎn)的指針next。通過各個(gè)節(jié)點(diǎn)之間的相互連接，最終串聯(lián)成一個(gè)鏈表。節(jié)點(diǎn)定義：頭結(jié)點(diǎn)2023年3月26日算法基礎(chǔ)18classNode(object):

def__init__(self,item):

self.item=item

self.next=None鏈表的遍歷遍歷鏈表：2023年3月26日算法基礎(chǔ)19deftraversal(head):

curNode=head#臨時(shí)用指針

whilecurNodeisnotNone:

print(curNode.data)

curNode=curNode.next鏈表節(jié)點(diǎn)的插入和刪除插入：p.next

=

curNode.nextcurNode.next

=

p刪除：p

=

curNode.nextcurNode.next

=

curNode.next.nextdel

p2023年3月26日算法基礎(chǔ)20132head5curNode132headcurNodep建立鏈表頭插法：2023年3月26日算法基礎(chǔ)21defcreateLinkListF(li):

l=Node()

fornuminli:

s=Node(num)

s.next=l.next

l.next=s

returnl12head建立鏈表尾插法：2023年3月26日算法基礎(chǔ)2212headdefcreateLinkListR(li):

l=Node()

r=l#r指向尾節(jié)點(diǎn)

fornuminli:

s=Node(num)

r.next=s

r=ss雙鏈表雙鏈表中每個(gè)節(jié)點(diǎn)有兩個(gè)指針：一個(gè)指向后面節(jié)點(diǎn)、一個(gè)指向前面節(jié)點(diǎn)。節(jié)點(diǎn)定義：2023年3月26日算法基礎(chǔ)23classNode(object):

def__init__(self,item=None):

self.item=item

self.next=None

self.prior=None雙鏈表節(jié)點(diǎn)的插入和刪除插入：p.next

=

curNode.nextcurNode.next.prior

=

pp.prior

=

curNodecurNode.next

=

p刪除：p

=

curNode.nextcurNode.next

=

p.nextp.next.prior

=

curNodedel

p2023年3月26日算法基礎(chǔ)24headcurNodep132head建立雙鏈表尾插法：2023年3月26日算法基礎(chǔ)25defcreateLinkListR(li):

l=Node()

r=l

fornuminli:

s=Node(num)

r.next=s

s.prior=r

r=s

returnl,r鏈表-分析列表與鏈表按元素值查找按下標(biāo)查找在某元素后插入刪除某元素2023年3月26日算法基礎(chǔ)26Python中的集合與字典（了解）哈希表查找哈希表（Hash

Table，又稱為散列表），是一種線性表的存儲(chǔ)結(jié)構(gòu)。通過把每個(gè)對(duì)象的關(guān)鍵字k作為自變量，通過一個(gè)哈希函數(shù)h(k)，將k映射到下標(biāo)h(k)處，并將該對(duì)象存儲(chǔ)在這個(gè)位置。例如：數(shù)據(jù)集合{1,6,7,9}，假設(shè)存在哈希函數(shù)h(x)使得h(1)

=