基于python实现模拟数据结构模型
模拟栈
- Stack()创建一个空的新栈。它不需要参数，并返回一个空栈。
- push(item)将一个新项添加到栈的顶部。它需要item做参数并不返回任何内容。
- pop()从栈中删除顶部项。它不需要参数并返回item。栈被修改。
- peek()从栈返回顶部项，但不会删除它。不需要参数。不修改栈。
- isEmpty()测试栈是否为空。不需要参数，并返回布尔值。
- size()返回栈中的item数量。不需要参数，并返回一个整数。
classStack(): def__init__(self): self.items=[] defpush(self,item): self.items.append(item) defpop(self): returnself.items.pop() defpeek(self): returnlen(self.items)-1 defisEmpty(self): returnself.items==[] defsize(self): returnlen(self.items) s=Stack() s.push(1) s.push(2) s.push(3) print(s.pop()) print(s.pop()) print(s.pop()) print(s.isEmpty())
模拟队列
- Queue()创建一个空的新队列。它不需要参数，并返回一个空队列。
- enqueue(item)将新项添加到队尾。它需要item作为参数，并不返回任何内容。
- dequeue()从队首移除项。它不需要参数并返回item。队列被修改。
- isEmpty()查看队列是否为空。它不需要参数，并返回布尔值。
- size()返回队列中的项数。它不需要参数，并返回一个整数。
classQueue(): def__init__(self): self.items=[] defenqueue(self,item): self.items.insert(0,item) defdequeue(self): returnself.items.pop() defisEmpty(self): returnself.items==[] defsize(self): returnlen(self.items) q=Queue() q.enqueue(1) q.enqueue(2) q.enqueue(3) print(q.dequeue()) print(q.dequeue()) print(q.dequeue())
案例：烫手山芋
烫手山芋游戏介绍：6个孩子围城一个圈，排列顺序孩子们自己指定。第一个孩子手里有一个烫手的山芋，需要在计时器计时1秒后将山芋传递给下一个孩子，依次类推。规则是，在计时器每计时7秒时，手里有山芋的孩子退出游戏。该游戏直到剩下一个孩子时结束，最后剩下的孩子获胜。请使用队列实现该游戏策略，排在第几个位置最终会获胜。
准则：队头孩子的手里永远要有山芋。
queue=Queue()
kids=['A','B','C','D','E','F']
#将六个孩子添加到队列中，A是队头位置的孩子
forkidinkids:
queue.enqueue(kid)
whilequeue.size()>1:
#在7秒之内山芋会被传递6次
foriinrange(6):
kid=queue.dequeue()
queue.enqueue(kid)
queue.dequeue()
print('获胜者为：',queue.dequeue())
模拟双端队列
同同列相比，有两个头部和尾部。可以在双端进行数据的插入和删除，提供了单数据结构中栈和队列的特性
- Deque()创建一个空的新deque。它不需要参数，并返回空的deque。
- addFront(item)将一个新项添加到deque的首部。它需要item参数并不返回任何内容。
- addRear(item)将一个新项添加到deque的尾部。它需要item参数并不返回任何内容。
- removeFront()从deque中删除首项。它不需要参数并返回item。deque被修改。
- removeRear()从deque中删除尾项。它不需要参数并返回item。deque被修改。
- isEmpty()测试deque是否为空。它不需要参数，并返回布尔值。
- size()返回deque中的项数。它不需要参数，并返回一个整数。
案例：回文检查
回文是一个字符串，读取首尾相同的字符，例如，radartootmadam。
defisHuiWen(s): ex=True q=Dequeue() #将字符串的每一个字符添加到双端队列中 forchins: q.addFront(ch) foriinrange(len(s)//2): font=q.removeFront() rear=q.removeRear() iffont!=rear: ex=False break returnex
模拟链表
- .is_empty()：链表是否为空
- .length()：链表长度
- .travel()：遍历整个链表
- .add(item)：链表头部添加元素
- .append(item)：链表尾部添加元素
- .insert(pos,item)：指定位置添加元素
- .remove(item)：删除节点
- .search(item)：查找节点是否存在
结点对象：
classNode(): def__init__(self,item): self.item=item self.next=None
链表对象：
classLink():
#构建出一个空的链表
def__init__(self):
self._head=None#永远指向链表中的头节点
#想链表的头部插入节点
defadd(self,item):
node=Node(item)
node.next=self._head
self._head=node
deftravel(self):
cur=self._head
#链表为空则输出‘链表为空'
ifself._head==None:
print('链表为空！')
whilecur:
print(cur.item)
cur=cur.next
defisEmpty(self):
returnself._head==None
deflength(self):
cur=self._head
count=0
whilecur:
count+=1
cur=cur.next
returncount
defsearch(self,item):
cur=self._head
find=False
whilecur:
ifcur.item==item:
find=True
break
cur=cur.next
returnfind
defappend(self,item):
node=Node(item)
#链表为空的情况
ifself._head==None:
self._head=node
return
cur=self._head#头节点
pre=None#cur的前一个节点
whilecur:
pre=cur
cur=cur.next
pre.next=node
definsert(self,pos,item):
node=Node(item)
ifpos<0orpos>self.length():
print('重新给pos赋值！！！')
return
cur=self._head
pre=None
foriinrange(pos):
pre=cur
cur=cur.next
pre.next=node
node.next=cur
defremove(self,item):
cur=self._head
pre=None
ifself._head==None:#链表为空
print('链表为空，没有可删除的节点！！1')
return
#删除的是第一个节点的情况
ifself._head.item==item:
self._head=self._head.next
return
#删除的是非第一个节点的情况
whilecur:
pre=cur
cur=cur.next
ifcur.item==item:
pre.next=cur.next
return
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持毛票票。