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

痛定思痛。 2023-02-18 09:53 44阅读 0赞

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

更多python视频教程请到菜鸟教程https://www.piaodoo.com/

**模拟栈**

*  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</pre>

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多

茂名论坛https://www.hnthzk.com/

化州橘红http://www.sfkyty.com/

茂名论坛http://www.nrso.net/

源码搜藏网http://www.cntkd.net/