第27周-python3.5零基础高级项目剖析共07章节27源码数据结构

数据结构基础什么是数据结构？简单来说，数据结构就是设计数据以何种方式组织并存储在计算机中。比如：列表、集合与字典等都是一种数据结构。N.Wirth:“程序=数据结构+算法”2023年3月26日算法基础2列表列表：在其他编程语言中称为“数组”，是一种基本的数据结构类型。关于列表的问题：列表中元素使如何存储的？列表提供了哪些基本的操作？这些操作的时间复杂度是多少？2023年3月26日算法基础3栈栈(Stack)是一个数据集合，可以理解为只能在一端进行插入或删除操作的列表。栈的特点：后进先出（last-in,

first-out）栈的概念：栈顶栈底栈的基本操作：进栈（压栈）：push出栈：pop取栈顶：gettop2023年3月26日算法基础4栈的Python实现不需要自己定义，使用列表结构即可。进栈函数：append出栈函数：pop查看栈顶函数：li[-1]2023年3月26日算法基础5栈的应用——括号匹配问题括号匹配问题：给一个字符串，其中包含小括号、中括号、大括号，求该字符串中的括号是否匹配。例如：()()[]{} 匹配([{()}]) 匹配[]( 不匹配[(]) 不匹配2023年3月26日算法基础6括号匹配问题——实现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日算法基础7栈的应用——迷宫问题给一个二维列表，表示迷宫（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日算法基础8起点终点解决思路在一个迷宫节点(x,y)上，可以进行四个方向的探查：maze[x-1][y],

maze[x+1][y],

maze[x][y-1],

maze[x][y+1]思路：从一个节点开始，任意找下一个能走的点，当找不到能走的点时，退回上一个点寻找是否有其他方向的点。方法：创建一个空栈，首先将入口位置进栈。当栈不空时循环：获取栈顶元素，寻找下一个可走的相邻方块，如果找不到可走的相邻方块，说明当前位置是死胡同，进行回溯（就是讲当前位置出栈，看前面的点是否还有别的出路）2023年3月26日算法基础9迷宫问题——栈实现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:#栈不空时循环

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#标记为已经走过，防止死循环

break

else:

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

stack.pop()

returnFalse2023年3月26日算法基础10队列队列(Queue)是一个数据集合，仅允许在列表的一端进行插入，另一端进行删除。进行插入的一端称为队尾(rear)，插入动作称为进队或入队进行删除的一端称为队头(front)，删除动作称为出队队列的性质：先进先出(First-in,

First-out)双向队列：队列的两端都允许进行进队和出队操作。2023年3月26日算法基础11队列的实现队列能否简单用列表实现？为什么？使用方法：from

collections

import

deque创建队列：queue

=

deque(li)进队：append出队：popleft双向队列队首进队：appendleft双向队列队尾进队：pop2023年3月26日算法基础12队列的实现原理初步设想：列表+两个下标指针创建一个列表和两个变量，front变量指向队首，rear变量指向队尾。初始时，front和rear都为0。进队操作：元素写到li[rear]的位置，rear自增1。出队操作：返回li[front]的元素，front自减1。这种实现的问题？2023年3月26日算法基础13队列的实现原理——环形队列改进方案：将列表首尾逻辑上连接起来。2023年3月26日算法基础14队列的实现原理——环形队列环形队列：当队尾指针front

==

Maxsize

+

1时，再前进一个位置就自动到0。实现方式：求余数运算队首指针前进1：front

=

(front

+

1)

%

MaxSize队尾指针前进1：rear

=

(rear

+

1)

%

MaxSize队空条件：rear

==

front队满条件：(rear

+

1)

%

MaxSize

==

front2023年3月26日算法基础15队列的应用——迷宫问题思路：从一个节点开始，寻找所有下面能继续走的点。继续寻找，直到找到出口。方法：创建一个空队列，将起点位置进队。在队列不为空时循环：出队一次。如果当前位置为出口，则结束算法；否则找出当前方块的4个相邻方块中可走的方块，全部进队。2023年3月26日算法基础16迷宫问题——队列实现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#标记为已经走过

returnFalse2023年3月26日算法基础17链表链表中每一个元素都是一个对象，每个对象称为一个节点，包含有数据域key和指向下一个节点的指针next。通过各个节点之间的相互连接，最终串联成一个链表。节点定义：头结点2023年3月26日算法基础18classNode(object):

def__init__(self,item):

self.item=item

self.next=None链表的遍历遍历链表：2023年3月26日算法基础19deftraversal(head):

curNode=head#临时用指针

whilecurNodeisnotNone:

print(curNode.data)

curNode=curNode.next链表节点的插入和删除插入：p.next

=

curNode.nextcurNode.next

=

p删除：p

=

curNode.nextcurNode.next

=

curNode.next.nextdel

p2023年3月26日算法基础20132head5curNode132headcurNodep建立链表头插法：2023年3月26日算法基础21defcreateLinkListF(li):

l=Node()

fornuminli:

s=Node(num)

s.next=l.next

l.next=s

returnl12head建立链表尾插法：2023年3月26日算法基础2212headdefcreateLinkListR(li):

l=Node()

r=l#r指向尾节点

fornuminli:

s=Node(num)

r.next=s

r=ss双链表双链表中每个节点有两个指针：一个指向后面节点、一个指向前面节点。节点定义：2023年3月26日算法基础23classNode(object):

def__init__(self,item=None):

self.item=item

self.next=None

self.prior=None双链表节点的插入和删除插入：p.next

=

curNode.nextcurNode.next.prior

=

pp.prior

=

curNodecurNode.next

=

p删除：p

=

curNode.nextcurNode.next

=

p.nextp.next.prior

=

curNodedel

p2023年3月26日算法基础24headcurNodep132head建立双链表尾插法：2023年3月26日算法基础25defcreateLinkListR(li):

l=Node()

r=l

fornuminli:

s=Node(num)

r.next=s

s.prior=r

r=s

returnl,r链表-分析列表与链表按元素值查找按下标查找在某元素后插入删除某元素2023年3月26日算法基础26Python中的集合与字典（了解）哈希表查找哈希表（Hash

Table，又称为散列表），是一种线性表的存储结构。通过把每个对象的关键字k作为自变量，通过一个哈希函数h(k)，将k映射到下标h(k)处，并将该对象存储在这个位置。例如：数据集合{1,6,7,9}，假设存在哈希函数h(x)使得h(1)

=