欢迎！

Python 中的数据结构与算法

Miriam Antona

Software Engineer

算法与数据结构的重要性

• 通过数据结构与算法可
  • 用高效代码解决日常问题
• 课程可用任意编程语言讲授

算法与数据结构

• 算法：解决问题的一组指令

  1. 设计

     

  2. 编码

     

• 数据结构： 在执行算法时存储和处理数据
  • 高级数据结构：链表、栈、队列…

链表

• 通过链接连接的数据序列

链表——结构

链表——结构

链表——结构

链表——结构

链表——结构

链表——结构

链表——结构

链表——结构

• 数据无需存放在连续内存块中
• 数据可位于任意可用内存地址

单链表

• 单个链接：单链表

双向链表

• 双向两个链接：双向链表

链表——实际用途

• 实现其他数据结构：
  • 栈
  • 队列
  • 图
• 通过前后导航访问信息
  • 浏览器
  • 音乐播放列表

链表——Node 类

class Node:
  def __init__(self, data):
    self.data = data
    self.next = None

链表——LinkedList 类

class LinkedList:
  def __init__(self):
    self.head = None
    self.tail = None

链表——方法

• insert_at_beginning()
• remove_at_beginning()
• insert_at_end()
• remove_at_end()
• insert_at()
• remove_at()
• search()
• …

链表——insert_at_beginning

链表——insert_at_beginning

 def insert_at_beginning(self, data):
    new_node = Node(data)

    if self.head:

链表——insert_at_beginning

 def insert_at_beginning(self, data):
    new_node = Node(data)
    if self.head:
      new_node.next = self.head

链表——insert_at_beginning

 def insert_at_beginning(self, data):
    new_node = Node(data)
    if self.head:
      new_node.next = self.head
      self.head = new_node

链表——insert_at_beginning

 def insert_at_beginning(self, data):
    new_node = Node(data)
    if self.head:
      new_node.next = self.head
      self.head = new_node
    else:

      self.tail = new_node      
      self.head = new_node

链表——insert_at_end

  def insert_at_end(self, data):
    new_node = Node(data)
    if self.head:  

      self.tail.next = new_node

      self.tail = new_node

    else:

      self.head = new_node
      self.tail = new_node

链表——search

def search(self, data):

  current_node = self.head

  while current_node:

    if current_node.data == data:

      return True

链表——search

def search(self, data):
  current_node = self.head
  while current_node:
    if current_node.data == data:
      return True
    else:
      current_node = current_node.next

链表——search

def search(self, data):
  current_node = self.head
  while current_node:
    if current_node.data == data:
      return True
    else:
      current_node = current_node.next

  return False

链表——示例

sushi_preparation = LinkedList()

sushi_preparation.insert_at_end("prepare")

链表——示例

sushi_preparation = LinkedList()  
sushi_preparation.insert_at_end("prepare")
sushi_preparation.insert_at_end("roll") 

链表——示例

sushi_preparation = LinkedList()  
sushi_preparation.insert_at_end("prepare")
sushi_preparation.insert_at_end("roll") 
sushi_preparation.insert_at_beginning("assemble")

链表——示例

sushi_preparation.search("roll")

True

sushi_preparation.search("mixing")

False

Ayo berlatih!

Python 中的数据结构与算法