Python版数据结构速成
数据结构
文章目录
基本数据结构类型
栈，队列，双端队列，和列表，这四种数据集合的项的由添加或删除的方式整合在一起。当添加一个项目时，它就被放在这样一个位置：在之前存在的项与后来要加入的项之间。像这样的数据集合常被称为线性数据
栈
定义 一个栈（有时称“叠加栈”）是一个项的有序集合。添加项和移除项都发生在同一“端”。这一端通常被称为“顶”。另一端的顶部被称为“底”。特征是后进先出
栈的操作
| Stack() | 创建一个新的空栈。它不需要参数，并返回一个空栈。 |
|---|---|
| Push(item | )将新项添加到堆栈的顶部。它需要参数item 并且没有返回值。 |
| pop() | 从栈顶删除项目。它不需要参数,返回item。栈被修改。 |
| peek() | 返回栈顶的项，不删除它。它不需要参数。堆栈不被修改。 |
| isEmpty() | 测试看栈是否为空。它不需要参数，返回一个布尔值。 |
| size() | 返回栈的项目数。它不需要参数，返回一个整数。 |
栈的代码实现
class Stack:
def __init__(self):
self.item=[];
def Push(self,val):
self.item.append(val)
def pop(self):
try:
return self.item.pop()
except:
return None
def peek(self):
try:
return self.item[-1]
except:
return None
def isEmpty(self):
return len(self.item)==0
def size(self):
return len(self.item)
队列
定义 队列（Queue）是一系列有顺序的元素的集合，新元素的加入在队列的一端，这一端叫做“队尾”（rear），已有元素的移除发生在队列的另一端，叫做“队首”（front），特点是先进先出
队列的操作
| Queue() | 创建一个空队列对象，无需参数，返回空的队列； |
|---|---|
| enqueue(item) | 将数据项添加到队尾，无返回值； |
| dequeue() | 从队首移除数据项，无需参数，返回值为队首数据项； |
| isEmpty() | 测试是否为空队列，无需参数，返回值为布尔值； |
| size() | 返回队列中的数据项的个数，无需参数。 |
队列的代码实现
class Queue:
def __init__(self):
self.item = []
def enqueue(self,val):
self.item.insert(0,val)
def dequeue(self):
return self.pop()
def isEmpty(self):
return len(self.item)==0
def size(self):
return len(self.item)
队列的应用
热土豆游戏
在这个游戏中小孩子们围成一个圆圈并以最快的速度接连传递物品，并在游戏的一个特定时刻停止传递，这时手中拿着物品的小孩就离开圆圈，游戏进行至只剩下一个小孩。
问题分析 这个游戏涉及以下几个问题：1.如何模拟圆圈；2.如何模拟时间走动
对于问题1 我们使用队列对圆圈进行模拟，圆圈并不是本质的，而是在时间走动时，可以出现一种循环,我们可以通过不断的进站出站来实现这个过程
from pythonds.basic.queue import Queue #引用pythonds中已经写好的队列类
from random import randint
def hotpotato(namelist):#热土豆游戏
simqueue = Queue()
for name in namelist:
simqueue.enqueue(name)#所有的成员进入队列
m = 1
while simqueue.size()>1:#开始游戏
number = randint(1, simqueue.size());#随机决定停止的位置
for i in range(number):
simqueue.enqueue(simqueue.dequeue())#从队首出，队尾进
print('第%s轮淘汰的是%s'%(m,simqueue.dequeue()))#时间到，队首人员淘汰
m = m+1
else:
print('最后的胜利者是%s'%simqueue.dequeue())
namelist=('军哥','GP','老权','爸爸我','希特勒','蔡徐坤','李云龙','周杰伦')
hotpotato(namelist)
运行得到：
第1轮淘汰的是GP
第2轮淘汰的是周杰伦
第3轮淘汰的是老权
第4轮淘汰的是李云龙
第5轮淘汰的是爸爸我
第6轮淘汰的是蔡徐坤
第7轮淘汰的是希特勒
最后的胜利者是军哥
双端队列
双端队列（deque 或 double-ended queue）与队列类似，也是一系列元素的有序组合。其两端称为队首（front）和队尾（rear）特点是元素可以从两端插入，也可以从两端删，拥有栈和队列各自拥有的所有功能
双端队列的操作
| Deque() | 创建一个空双端队列，无参数，返回值为 Deque 对象。 |
|---|---|
| addFront(item) | 在队首插入一个元素，参数为待插入元素，无返回值。 |
| addRear(item) | 在队尾插入一个元素，参数为待插入元素，无返回值 |
| removeFront() | 在队首移除一个元素，无参数，返回值为该元素。双端队列 |
| removeRear() | 在队尾移除一个元素，无参数，返回值为该元素。双端队列会 |
| isEmpty() | 判断双端队列是否为空，无参数，返回布尔值。 |
| size() | 返回双端队列中数据项的个数，无参数，返回值为整型数值。 |
双端队列的代码实现
class Deque:
def __init__(self):
self.item=[]
def addRear(self,item):
self.item.insert(0,item)
def addFront(self,item):
self.item.append(item)
def removeFront(self):
if self.item:
return self.item.pop()
else:
return print('The deque is empty')
def removeRear(self):
if self.item:
return self.item.pop(0)
else:
return print('The deque is empty')
def isEmpty(self):
return self.item==[]
def size(self):
return len(self.item)
双端队列的应用
“ 回文词” 判定
回文词指的是正读和反读都一样的词，如：radar、toot 和madam。我们想要编写一个算法来检查放入的字符串是否为回文词。
**思路分析：**我们在栈的介绍时，提到过栈可以用来反转顺序，而双端队列，具有‘顺序’，‘逆序’两种性质，所以我们可以通过队列来实现回文词的判断
代码实现
def palchecker(aString):
d=Deque()
for i in aString:#使词进队
d.addRear(i)
while d.size()>1:#进行判断
if d.removeFront()==d.removeRear():
pass
else:
return False
else:
return True
**评：**上述代码虽然可以实现，但是最好时在判断的过程中加入标记，使得代码有更好的维护性
def palchecker(aString):
d=Deque()
for i in aString:#使词进队
d.addRear(i)
stillEqual = True
while d.size()>1:#进行判断
if d.removeFront()==d.removeRear():
pass
else:
stillEqual = False
return stillEqual
无序列表列表(链表)
无序列表结构是一个由各个元素组成的集合，在其中的每个元素拥有一个不同于其它元素的相对位置，无序列表，其实仍有序，只不过是成为了相对序，举例来说，电影院里坐着一排人，你可以说，”喂，快看1排 6号的迪丽热巴！“，但是如果走在街上的话，比较合适的描述是”喂，快看前面黄毛古惑仔，旁边的如花！”
无序列表列表的操作
| list() | 创建一个新的空列表。它不需要参数，而返回一个空列表。 |
|---|---|
| add(item) | 将新项添加到列表，没有返回值。假设元素不在列表中。 |
| remove(item) | 从列表中删除元素。需要一个参数，并会修改列表。此处假设元素在列表中。 |
| search(item) | 搜索列表中的元素。需要一个参数，并返回一个布尔值。 |
| isEmpty() | 判断列表是否为空。不需要参数，并返回一个布尔值。 |
| size() | 返回列表的元素数。不需要参数，并返回一个整数。 |
| append(item) | 在列表末端添加一个新的元素。它需要一个参数，没有返回值 |
| index(item) | 此处假设该元素原本在列表中， 返回元素在列表中的位置。它需要一个参数，并返回位置索引值。 |
| insert(pos,item) | 在指定的位置添加一个新元素。它需要两个参数，没有返回值 |
| pop() | 从列表末端移除一个元素并返回它。它不需要参数，返回一个元素。 |
| pop(pos) | 从指定的位置移除列表元素并返回它。它需要一个位置参数，并返回值 |
无序列表（链表）的实现
为了实现无序列表，我们将构建一个链表，每个项目的相对位置就可以通过以下简单的链接从一个项目到下一个来确定，链表实现的基本模块是节点
节点
节点必须包含列表元素本身。我们将这称为该节点的“数据区”（data field）。此外，每个节点必须保持到下一个节点的引用
节点代码实现
class Node:
def __init__(self,initdate):
self.data=initdate
self.next=None
def getData(self):
return self.data
def getNext(self):
return self.next
def setData(self,newdata):
self.data=newdata
def setNext(self,newnext):
self.Next=newnext
无序列表（链表）的代码实现
无序列表将由一个节点集合组
只要我们知道第一个节点的位置（包含第一项），在这之后的每个元素都可以通过以下链
接找到下一个节点。为实现这个想法，UnorderedList 类必须保持一个对第一节点的引用
节点就像一个机器人有两个机械臂，左臂小，右臂大，大到和机器人的身体一样大，链表就相当于一系列机器人，这些机器人左手拿着val,右手要么空着，要么抓着另一个机器人
class UnorderedList:
def __init__(self):
self.head = None
def add(self,item):
temp=Node(item)
temp.setNext(self.head)
self.head=temp
def append(self,item):
last=self.head
while last.getNext()!=None:
last=last.getNext()
temp=Node(item)
last.setNext(temp)
def isEmpty(self):
return self.head==None
def size(self):
current=self.head
count = 0
while current!=None:
count =count+1
current=current.getNext()
return count
def search(self,item):
current=self.head
found=False
while current!=None and not found:
if current.getData()==item:
found=True
else:
current=current.getNext()
return found
def search_pos(self,item):
current=self.head
previous=None
found=False
while current!=None and not found:
if current.getData()==item:
found=True
else:
previous=current
current=current.getNext()
return current
def remove(self,item):
current=self.head
previous=None
found=False
while not found:
if current.getData()==item:
found = True
else:
previous=current
current=current.getNext()
if previous==None:#如果找到的节点在第一项
self.head=current.getNext()
else:
previous.setNext(current.getNext())
def index(self,item):
previous=None
current=self.head
while current!=None and current.getData()!=item:
previous=current
current=current.getNext()
print("The last item of %s is %s"%(str(item),str(previous.getData())))
def insert(self,pos,item):
temp_0=self.search_pos(pos)
temp_1=Node(item)
temp_1.setNext(temp_0.getNext())
temp_0.setNext(temp_1)
def pop(self,pos=None):
current=self.head
previous=None
if pos==None:
while current.getNext()!=None:
previous=current
current=current.getNext()
if previous==None:
self.head=None
else:
previous.setNext(None)
return current.getData()
else:
self.remove(pos)
return pos
有序列表
有序列表的结构是一个数据的集合体，在集合体中，每个元素相对其他元素有一个基于元素的
某些基本性质的位置，举例来说，一个班级排队，一开始大家都是随便排，只产生一种相对位置，比如说小花后面是狗蛋，此时队伍就是一个无序列表；如果此时老师要求按身高进行排队，就产生了一种关于属性的位置，此时我们就说队伍是一个有序列
有序列表的操作
| OrderedList() | 创建一个新的空有序列表。它返回一个空有序列表并且不需要传递任何参数。 |
|---|---|
| add(item) | 在保持原有顺序的情况下向列表中添加一个新的元素，新的元素作为参数传递进函数无返回值 |
| remove(item) | 从列表中删除某个元素。欲删除的元素作为参数，并且会修改原列表 |
| search(item) | 在列表中搜索某个元素，被搜索元素作为参数，返回一个布尔值。 |
| isEmpty() | 测试列表是否为空，不需要输入参数并且其返回一个布尔值。 |
| size()： | 返回列表中元素的数量。不需要参数，返回一个整数。 |
| index(item) | 返回元素在列表中的位置。需要被搜索的元素作为参数输入，返回此元素的索引 |
| pop() | 删除并返回列表中的最后一项。不需要参数，返回删除的元素。假设列表中至少有一个 |
| pop(pos) | 删除并返回索引pos 指定项。需要被删除元素的索引值作为参数，并且返回这个元素 |
关于数字大小有序列表的代码实现
在有序列表中除了add，search外，其他所有函数的实现都和无序列表相同
class OrderedList:
def __init__(self):
self.head = None
def add(self,item):
current=self.head
previous=None
stop=False
while current!=None and not stop:
if current.getData()>item:
stop=True
else:
previous=current
current=current.getNext()
temp=Node(item)
if previous==None:
temp.setNext(self.head)
self.head=temp
else:
temp.setNext(current)
previous.setNext(temp)
def search(self,item):
current=self.head
found=False
stop=False
while current!=None and not found and not stop:
if current.getData()==item:
found=True
else:
if current.getData()>item:
stop=True
else:
current=current.getNext()
return found
def print(self):
current=self.head
s=[]
if current==None:
return None
else:
while current!=None:
s.append(current.getData())
current=current.getNext()
return s
实例
w=OrderedList()
w.add(1)
w.add(19)
w.add(20)
w.add(17)
w.print()
运行得到：
[1, 17, 19, 20]
递归
定义 递归是一种解决问题的方法，它把一个问题分解为越来越小的子问题，直到问题的规模小到
可以被很简单直接解决
通常为了达到分解问题的效果，递归过程中要引入一个调用自身的函数
递归三大定律
● 递归算法必须有个基本结束条件
● 递归算法必须改变自己的状态并向基本结束条件演进
● 递归算法必须递归地调用自身
实例
对列表中的元素做加法
def list_sum(num_list):
if len(num_list) == 1:
return num_list[0]#1.结束条件
else:
return num_list[0] + list_sum(num_list[1:])#3.调用自身并2.向基本结束条件演进
print(list_sum([1,3,5,7,9]))
计算一个整数的阶乘
def fact(n:int):
if n>0:#结束条件
return n*fact(n-1) #调用自身，并向基本结束条件演进
else:
return 1
整数转化成任意进制表示的字符串形式
def to_str(n,base=17):
convert_string="0123456789ABCDEFG"
if n<base:#结束条件
return convert_string[n]
else:
return to_str(n//base,base)+convert_string[n%base] #调用自身，并向基本结束条件演进
反转字符串
def reverse(Str):
if len(Str)>1:#结束条件
return Str[-1]+reverse(Str[:-1]) #调用自身，并向基本结束条件演进
else:
return Str[0]
判断回文词
这一题目我们曾在双端队列中做过
def judge_rev(Str):
judge=False
if len(Str)>1:#结束条件
if Str[0]==Str[-1]:
return judge_rev(Str[1:-1])#调用自身，并向基本结束条件演进
else:
return judge
else:
judge=True
return judge
**注意：**在调用函数本身后，最外层的数据一定要对调用结果有引用，否则容易出错
判断句子是否是构成回文词
一些优秀的回文也可以是短语,但是你需要在验证前删除空格和标点符号。例如:madam i’m adam 是个回文
def clearingstr(Str):
Str=Str.lower()#将字母都换为小写
if len(Str)>1:#结束条件
if not Str[0].isalpha() and not Str[0].isdigit():
Str=Str[1:]
return clearingstr(Str) #调用自身，并向基本结束条件演进
else:
return Str[0]+clearingstr(Str[1:])#调用自身，并向基本结束条件演进
else:
if not Str[0].isalpha() and not Str[0].isdigit():
return ''
else:
return Str
字符串的几个常用切片函数
| 函数名 | 语法 | 返回值 |
|---|---|---|
| strip() | str.strip([chars]); | 返回移除字符串头尾指定的字符生成的新字符串。 |
| replace() | str.replace(old, new[, max])#old – 将被替换的子字符串; new – 新字符串，用于替换old子字符串; max – 可选字符串, 替换不超过 max 次 | 替换后的新字符串 |
| split() | str.split(str="", num=string.count(str))#str–分隔符，默认为所有的空字符，包括空格、换行(\n)、制表符(\t)等。num–分割次数。默认为 -1, 即分隔所有。 | 返回分割后的字符串列表 |