算法笔记·2

基本数据结构

线性结构(linear structure)

  • 有序数据项的集合
  • 每个数据项都有唯一的前驱和后继(第一个和最后一个除外)

根据数据项增减的方式构成了数据结构

  • 栈(Stack)--仅在表尾进行插入和删除操作的线性表
  • 队列(Queue)--只允许在表的前端(front)进行删除操作,而在表的后端(rear)进行插入操作
  • 双端队列(Deque)--限定插入和删除操作在表的两端进行的线性表
  • 列表(List)--

进行操作的一端为栈顶,另一端为栈底
栈的特点:后进先出LIFO

3fPlFJ.png

栈通过python的实现可以借助list的数据类型

栈的应用

括号匹配--基本思路

8psmYd.png

括号匹配与之前图灵机的模型有些相似;

  • 括号匹配可以用用于爬虫HTML数据的爬取;另外该方法也可通过正则表达式实现。

十进制与二进制的转换

十进制转换二进制是余数的连续求取,并将求得的余数倒过来书写。通过栈后进先出的特性可以实现。

同时由此可以进行十进制到其他进制的转换。当转换的进制为十一禁进制以上时,可以使用数组来保存其中的字母

    digits = "0123456789ABC"

表达式转换

根据表达式操作符的的位置分为中缀、前缀和后缀,距离操作数最近的操作符先执行

  • 中缀表达式转换为前缀和后缀表达式
    将表达式转换为全括号形式,将内部每个运算符移到对应的左括号或右括号处边可以转换为前缀、后缀表达式

  • 中缀转后缀算法

从左到右扫描过程中,采用栈来暂存为处理的操作符,当遇到一个新的操作符,就需要跟栈顶的操作符比较下优先级,再行处理。

算法流程

从左到右扫描

  • 当遇到操作数,直接输出至列表末尾
  • 当遇到左括号压入栈顶
  • 当遇到右括号,反复弹出栈顶加入至输出列表末尾,直到碰到左括号
  • 当遇到操作符,与栈顶其他操作符比较。栈顶操作符高于或等于它,则将输出栈顶的操作符直到优先级低于它

后缀表达式的求值

后缀表达式的操作符在操作数的后面,因此要暂存操作数,直到碰到操作符才进行运算(从这可以利用栈的特性)

在实际运算时,先弹出的时右操作数然后才是左操作数,对于‘-’和‘/’要注意两个操作数的位置

算法流程

  • 创建空栈用于暂存操作数

  • 从左到右扫面单词列表

    1. 如果是操作数,压入栈顶
    2. 如果是操作符,从栈顶弹出两个操作数,进行计算。(注意操作数的位置)
  • 最后扫描结束后,表达式的值被存在栈顶(如果表达式正确,则栈中仅有最后的结果一个元素)

引用

暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇