基于python实现模拟数据结构模型
模拟栈
Stack() 创建一个空的新栈。 它不需要参数,并返回一个空栈。 push(item)将一个新项添加到栈的顶部。它需要 item 做参数并不返回任何内容。 pop() 从栈中删除顶部项。它不需要参数并返回 item 。栈被修改。 peek() 从栈返回顶部项,但不会删除它。不需要参数。 不修改栈。 isEmpty() 测试栈是否为空。不需要参数,并返回布尔值。 size() 返回栈中的 item 数量。不需要参数,并返回一个整数。class Stack(): def __init__(self): self.items = [] def push(self,item): self.items.append(item) def pop(self): return self.items.pop() def peek(self): return len(self.items) - 1 def isEmpty(self): return self.items == [] def size(self): return len(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() 返回队列中的项数。它不需要参数,并返回一个整数。class Queue(): def __init__(self): self.items = [] def enqueue(self,item): self.items.insert(0,item) def dequeue(self): return self.items.pop() def isEmpty(self): return self.items == [] def size(self): return len(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是队头位置的孩子for kid in kids: queue.enqueue(kid)while queue.size() > 1: #在7秒之内山芋会被传递6次 for i in range(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中的项数。它不需要参数,并返回一个整数。案例:回文检查
回文是一个字符串,读取首尾相同的字符,例如,radar toot madam。
def isHuiWen(s): ex = True q = Dequeue() # 将字符串的每一个字符添加到双端队列中 for ch in s: q.addFront(ch) for i in range(len(s) // 2): font = q.removeFront() rear = q.removeRear() if font != rear: ex = False break return ex
模拟链表
. is_empty():链表是否为空 . length():链表长度 . travel():遍历整个链表 . add(item):链表头部添加元素 . append(item):链表尾部添加元素 . insert(pos, item):指定位置添加元素 . remove(item):删除节点 . search(item):查找节点是否存在结点对象:
class Node(): def __init__(self,item): self.item = item self.next = None
链表对象:
class Link(): #构建出一个空的链表 def __init__(self): self._head = None #永远指向链表中的头节点 #想链表的头部插入节点 def add(self,item): node = Node(item) node.next = self._head self._head = node def travel(self): cur = self._head #链表为空则输出‘链表为空’ if self._head == None: print(’链表为空!’) while cur: print(cur.item) cur = cur.next def isEmpty(self): return self._head == None def length(self): cur = self._head count = 0 while cur: count += 1 cur = cur.next return count def search(self,item): cur = self._head find = False while cur: if cur.item == item:find = Truebreak cur = cur.next return find def append(self,item): node = Node(item) #链表为空的情况 if self._head == None: self._head = node return cur = self._head #头节点 pre = None #cur的前一个节点 while cur: pre = cur cur = cur.next pre.next = node def insert(self,pos,item): node = Node(item) if pos < 0 or pos > self.length(): print(’重新给pos赋值!!!’) return cur = self._head pre = None for i in range(pos): pre = cur cur = cur.next pre.next = node node.next = cur def remove(self,item): cur = self._head pre = None if self._head == None:#链表为空 print(’链表为空,没有可删除的节点!!1’) return #删除的是第一个节点的情况 if self._head.item == item: self._head = self._head.next return #删除的是非第一个节点的情况 while cur: pre = cur cur = cur.next if cur.item == item:pre.next = cur.nextreturn
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持好吧啦网。
相关文章:
1. 在Asp.net core项目中使用WebSocket2. ASP.NET MVC使用异步Action的方法3. JavaScript实现组件化和模块化方法详解4. SpringMVC+Jquery实现Ajax功能5. 使用vue-cli创建项目并webpack打包的操作方法6. 利用FastReport传递图片参数在报表上展示签名信息的实现方法7. python3.8.1+selenium实现登录滑块验证功能8. matplotlib如何设置坐标轴刻度的个数及标签的方法总结9. Python制作一个随机抽奖小工具的实现10. 使用python画出逻辑斯蒂映射(logistic map)中的分叉图案例