亲宝软件园·资讯

展开

python模拟数据结构 基于python实现模拟数据结构模型

Hedger_Lee 人气:0

模拟栈

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())

模拟队列

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())

模拟双端队列

同同列相比,有两个头部和尾部。可以在双端进行数据的插入和删除,提供了单数据结构中栈和队列的特性

案例:回文检查

回文是一个字符串,读取首尾相同的字符,例如,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

模拟链表

结点对象:

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 = True
        break
      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.next
        return

加载全部内容

相关教程
猜你喜欢
用户评论