老男孩python全棧開發(fā)15期共145s15算法第一天數(shù)據(jù)結構

數(shù)據(jù)結構基礎什么是數(shù)據(jù)結構？數(shù)據(jù)結構是指相互之間存在著一種或多種關系的數(shù)據(jù)元素的集合和該集合中數(shù)據(jù)元素之間的關系組成。簡單來說，數(shù)據(jù)結構就是設計數(shù)據(jù)以何種方式組織并存儲在計算機中。比如：列表、集合與字典等都是一種數(shù)據(jù)結構。N.Wirth:“程序=數(shù)據(jù)結構+算法”2023年4月13日算法基礎2數(shù)據(jù)結構的分類數(shù)據(jù)結構按照其邏輯結構可分為線性結構、樹結構、圖結構線性結構：數(shù)據(jù)結構中的元素存在一對一的相互關系樹結構：數(shù)據(jù)結構中的元素存在一對多的相互關系圖結構：數(shù)據(jù)結構中的元素存在多對多的相互關系2023年4月13日算法基礎3列表列表：在其他編程語言中稱為“數(shù)組”，是一種基本的數(shù)據(jù)結構類型。關于列表的問題：列表中元素使如何存儲的？列表提供了哪些基本的操作？這些操作的時間復雜度是多少？擴展：Python的列表是如何實現(xiàn)的？2023年4月13日算法基礎4棧棧(Stack)是一個數(shù)據(jù)集合，可以理解為只能在一端進行插入或刪除操作的列表。棧的特點：后進先出（last-in,

first-out）棧的概念：棧頂棧底棧的基本操作：進棧（壓棧）：push出棧：pop取棧頂：gettop2023年4月13日算法基礎5棧的Python實現(xiàn)不需要自己定義，使用列表結構即可。進棧函數(shù)：append出棧函數(shù)：pop查看棧頂函數(shù)：li[-1]2023年4月13日算法基礎6棧的應用——括號匹配問題括號匹配問題：給一個字符串，其中包含小括號、中括號、大括號，求該字符串中的括號是否匹配。例如：()()[]{} 匹配([{()}]) 匹配[]( 不匹配[(]) 不匹配2023年4月13日算法基礎7括號匹配問題——實現(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年4月13日算法基礎8隊列隊列(Queue)是一個數(shù)據(jù)集合，僅允許在列表的一端進行插入，另一端進行刪除。進行插入的一端稱為隊尾(rear)，插入動作稱為進隊或入隊進行刪除的一端稱為隊頭(front)，刪除動作稱為出隊隊列的性質(zhì)：先進先出(First-in,

First-out)雙向隊列：隊列的兩端都允許進行進隊和出隊操作。2023年4月13日算法基礎9隊列的實現(xiàn)隊列能否簡單用列表實現(xiàn)？為什么？初步設想：列表+兩個下標指針創(chuàng)建一個列表和兩個變量，front變量指向隊首，rear變量指向隊尾。初始時，front和rear都為0。進隊操作：元素寫到li[rear]的位置，rear自增1。出隊操作：返回li[front]的元素，front自減1。2023年4月13日算法基礎10隊列的實現(xiàn)原理——環(huán)形隊列2023年4月13日算法基礎11隊列的實現(xiàn)原理——環(huán)形隊列環(huán)形隊列：當隊尾指針front

==

Maxsize

+

1時，再前進一個位置就自動到0。實現(xiàn)方式：求余數(shù)運算隊首指針前進1：front

=

(front

+

1)

%

MaxSize隊尾指針前進1：rear

=

(rear

+

1)

%

MaxSize隊空條件：rear

==

front隊滿條件：(rear

+

1)

%

MaxSize

==

front2023年4月13日算法基礎12隊列的內(nèi)置模塊使用方法：from

collections

import

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

=

deque(li)進隊：append出隊：popleft雙向隊列隊首進隊：appendleft雙向隊列隊尾進隊：pop2023年4月13日算法基礎13棧的應用——迷宮問題給一個二維列表，表示迷宮（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年4月13日算法基礎14起點終點解決思路在一個迷宮節(jié)點(x,y)上，可以進行四個方向的探查：maze[x-1][y],

maze[x+1][y],

maze[x][y-1],

maze[x][y+1]思路：從一個節(jié)點開始，任意找下一個能走的點，當找不到能走的點時，退回上一個點尋找是否有其他方向的點。方法：創(chuàng)建一個空棧，首先將入口位置進棧。當棧不空時循環(huán)：獲取棧頂元素，尋找下一個可走的相鄰方塊，如果找不到可走的相鄰方塊，說明當前位置是死胡同，進行回溯（就是講當前位置出棧，看前面的點是否還有別的出路）2023年4月13日算法基礎15迷宮問題——棧實現(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:#棧不空時循環(huán)

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

ifcurNode[0]==x2andcurNode[1]:

#到達終點

forpinstack:

print(p)

break

fordirindirs:

nextNode=dir(*curNode)

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

stack.append(nextNode)

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

break

else:

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

stack.pop()

returnFalse2023年4月13日算法基礎16隊列的應用——迷宮問題思路：從一個節(jié)點開始，尋找所有下面能繼續(xù)走的點。繼續(xù)尋找，直到找到出口。方法：創(chuàng)建一個空隊列，將起點位置進隊。在隊列不為空時循環(huán)：出隊一次。如果當前位置為出口，則結束算法；否則找出當前方塊的4個相鄰方塊中可走的方塊，全部進隊。2023年4月13日算法基礎17迷宮問題——隊列實現(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:

#到達終點

print(path)

returnTrue

fordirindirs:

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

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

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

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

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

def__init__(self,item):

self.item=item

self.next=None建立鏈表頭插法：2023年4月13日算法基礎20defcreateLinkListF(li):

l=Node()

fornuminli:

s=Node(num)

s.next=l.next

l.next=s

returnl120建立鏈表尾插法：2023年4月13日算法基礎21120t頭插法：120鏈表的遍歷遍歷鏈表：2023年4月13日算法基礎22鏈表節(jié)點的插入和刪除插入：p.next

=

curNode.nextcurNode.next

=

p刪除：p

=

curNode.nextcurNode.next

=

curNode.next.nextdel

p2023年4月13日算法基礎231325curNode132curNodep雙鏈表雙鏈表中每個節(jié)點有兩個指針：一個指向后面節(jié)點、一個指向前面節(jié)點。節(jié)點定義：2023年4月13日算法基礎24classNode(object):

def__init__(self,item=None):

self.item=item

self.next=None

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

=

curNode.nextcurNode.next.prior

=

pp.prior

=

curNodecurNode.next

=

p刪除：p

=

curNode.nextcurNode.next

=

p.nextp.next.prior

=

curNodedel

p2023年4月13日算法基礎25headcurNodep132head鏈表-復雜度分析列表與鏈表按元素值查找按下標查找在某元素后插入刪除某元素鏈表在插入和刪除的操作上明顯快于順序表鏈表的內(nèi)存可以更靈活的分配試利用鏈表重新實現(xiàn)棧和隊列鏈表這種鏈式存儲的數(shù)據(jù)結構對樹和圖的結構有很大的啟發(fā)性2023年4月13日算法基礎26哈希表哈希表一個通過哈希函數(shù)來計算數(shù)據(jù)存儲位置的數(shù)據(jù)結構，通常支持如下操作：insert(key,value)：插入鍵值對(key,value)get(key)：如果存在鍵為key的鍵值對則返回其value，否則返回空值delete(key)：刪除鍵為key的鍵值對2023年4月13日算法基礎27直接尋址表當關鍵字的全域U比較小時，直接尋址是一種簡單而有效的方法。直接尋址技術缺點：當域U很大時，需要消耗大量內(nèi)存，很不實際如果域U很大而實際出現(xiàn)的key很少，則大量空間被浪費無法處理關鍵字不是數(shù)字的情況2023年4月13日算法基礎28哈希直接尋址表：key為k的元素放到k位置上改進直接尋址表：哈希（Hashing）構建大小為m的尋址表Tkey為k的元素放到h(k)位置上h(k)是一個函數(shù)，其將域U映射到表T[0,1,...,m-1]2023年4月13日算法基礎29哈希表哈希表（Hash

Table，又稱為散列表），是一種線性表的存儲結構。哈希表由一個直接尋址表和一個哈希函數(shù)組成。哈希函數(shù)h(k)將元素關鍵字k作為自變量，返回元素的存儲下標。簡單哈希函數(shù)：除法哈希：h(k)=kmodm乘法哈希：h(k)=floor(m(kAmod1))0<A<1假設有一個長度為7的數(shù)組，哈希函數(shù)h(k)=k

mod

7。元素集合{14,22,3,5}的存儲方式如下圖。2023年4月13日算法基礎30哈希沖突由于哈希表的大小是有限的，而要存儲的值的總數(shù)量是無限的，因此對于任何哈希函數(shù)，都會出現(xiàn)兩個不同元素映射到同一個位置上的情況，這種情況叫做哈希沖突。比如：h(k)=k

mod

7,h(0)=h(7)=h(14)=...2023年4月13日算法基礎31解決哈希沖突——開放尋址法開放尋址法：如果哈希函數(shù)返回的位置已經(jīng)有值，則可以向后探查新的位置來存儲這個值。線性探查：如果位置i被占用，則探查i+1,i+2,……二次探查：如果位置i被占用，則探查i+12,i-12,i+22,i-22,……二度哈希：有n個哈希函數(shù)，當使用第1個哈希函數(shù)h1發(fā)生沖突時，則嘗試使用h2,h3,……2023年4月13日算法基礎32解決哈希沖突——拉鏈法拉鏈法：哈希表每個位置都連接一個鏈表，當沖突發(fā)生時，沖突的元素將被加到該位置鏈表的最后。2023年4月13日算法基礎33哈希表在Python中的應用字典與集合都是通過哈希表來實現(xiàn)的。在Python中的字典：a={'name':'Alex','age':18,'gender':'Man'}使用哈希表存儲字典，通過哈希函數(shù)將字典的鍵映射為下標。假設h(‘name’)

=

3,

h(‘a(chǎn)ge’)

=

1,

h(‘gender’)

=

4，則哈希表存儲為[None,

18,

None,

’Alex’,

‘Man’]2023年4月13日算法基礎34二叉樹二叉樹的鏈式存儲：將二叉樹的節(jié)點定義為一個對象，節(jié)點之間通過類似鏈表的鏈接方式來連接。節(jié)點定義：二叉樹的遍歷：前序遍歷：EACBDGF中序遍歷：ABCDEGF后序遍歷：BDCAFGE層次遍歷：EAGCFBD2023年4月13日算法基礎35classBiTreeNode:

def__init__(self,data):

self.data=data

self.lchild=None

self.rchild=None二叉搜索樹二叉搜索樹是一顆二叉樹且滿足性質(zhì)：設x是二叉樹的一個節(jié)點。如果y是x左子樹的一個節(jié)點，那么y.key≤x.key；如果y是x右子樹的一個節(jié)點，那么y.key≥x.key.二叉搜索樹的創(chuàng)建二叉搜索樹的遍歷（中序序列）二叉搜索樹的查詢、插入、刪除2023年4月13日算法基礎36二叉搜索樹——