阅读裘宗燕老师的《数据结构与算法:python语言描述》的课件所记笔记

三、队列

1.基本概念

  • 可存入、访问、删除数据元素
  • 保证在任何时刻可访问、删除的元素都是在此之前最早存入队列而至今未删除的那个元素
  • 确定了一种由存储顺序决定的访问顺序

2.基本操作

  • 创建空队列
  • 判断队列是否为空(判断满)
  • 将元素放入队列,入列(enqueue)
  • 从队列删除,出列(dequeue)
  • 取当前元素的值(最老的,并不删除

3.队列特性

  • 保证访问或删除元素的“FIFO"原则
  • 与”时间“有关的结构
  • 只在一端插入另一端访问或删除的表
  • 出队操作的一端称为队头
  • 入队操作的一端称为队尾

4.队列实现

  • 用线性表实现,因为要在两端操作,比栈麻烦一些
  • 用链接表的话,应该考虑带尾指针的链接表
  • 环形队列
a.list实现
  • 基于python的list实现顺序表示的队列
    • 最简单的实现方法得到O(1)的enqueue和O(n)的dequeue
  • 由于python的list不提供检查元素存储区容量的机制,很难利用其自动扩充元素区的机制,但可以自己做
  • 首先,队列可能由于空而无法dequeue,定义一个异常
    class QueueUnderflow(ValueError):
    pass
    # 继承系统提供的异常
  • SQueue类的基本考虑:
    • 用SQueue对象的一个list类型的成分elems存放队里元素
    • 用head和elnum记录首元素位置的下标和表中元素个数
    • 为能判断存储区是否满以便换一个表,需要记录表长度,用len
Xb.数据不变式
  • 数据结构的之间的协调统一性,待补充

4.队列的应用

a.离散事件模拟
  • 初步分析
  • 进一步分析
  • 过程模拟
  • 总结
  • 思考:关键是理解队列的时间性,先进先出,按时间先后顺序处理

四、应用:迷宫问题

1.问题分析

  • 将迷宫直接映射到二维的0/1矩阵,用嵌套的表[[...],...,[...]]
  • 每个位置分为可通与不可通,位置用序对(m,n)描述
  • 每个位置有上右下左四个位置选择:(0,1),(1,0),(0,-1),(-1,0)
  • 防止兜圈子,因此要记录已经走过的位置
  • 2.实现方式

  • 无路可走时退回到最开始出现分支的位置上搜索另一个分支,递归
  • 无路可走时退回到最近出现分支的位置上搜索另一个分支,回溯

X3.递归实现

待补充

X4.回溯实现

待补充

a.回溯法和栈
  • 都是从一个出发点开始,设法找到目标(搜索)
  • 都需要使用一个栈,搜索过程的行为分为向前搜索和向后回溯

5.搜索性质

  • 基于栈的搜索被称为”深度优先搜索“(depth-first search)
  • 基于队列的搜索被称为”宽度优先搜索“(width-first search)
最后由 oucb 编辑于2016年05月24日 14:05