基于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 = 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

以上是 基于python实现模拟数据结构模型 的全部内容, 来源链接: utcz.com/z/327984.html

回到顶部