精华内容
下载资源
问答
  • 有限状态机(FSM)是一个根据输入改变状态的机器或程序。用图表示 FSM 相当简明, 下图中的矩形(或圆形)称为节点节点之间带箭头的线段称为...一个或多个状态可以指定为终止状态,用粗框矩形表示。终止状态表示程序无...

    有限状态机(FSM)是一个根据输入改变状态的机器或程序。用图表示 FSM 相当简明, 下图中的矩形(或圆形)称为节点,节点之间带箭头的线段称为边(或弧)。

    dc6e11088d48f412ca60aae30806aa9f.png

    上图给出了一个简单的例子。每个节点代表一个程序状态,每个边代表从一个状态到另一个状态的转换。一个节点被指定为初始状态,在图中用一个输入箭头指出。其余的状态可以用数字或字母来标示。一个或多个状态可以指定为终止状态,用粗框矩形表示。终止状态表示程序无出错的结束状态。

    FSM 是一种被称为有向图的更一般结构的特例。有向图就是一组节点,它们用具有特定方向的边进行连接。

    验证输入字符串

    读取输入流的程序往往要通过执行一定量的错误检查来验证它们的输入。比如,编程语言编译器可以用 FSM 来扫描程序,将文字和符号转换为记号(通常是指关键字、算法运算符和标识符)。

    用 FSM 来验证输入字符串时,常常是按字符进行读取。每一个字符都用图中的一条边(转换)来表示。FSM 有两种方法检测非法输入序列:

    下一个输入字符没有对应到当前状态的任何一个转换。

    输入已经终止,但是当前状态是非终止状态。

    字符串示例现在根据下面两条原则来验证一个输入字符串:

    该字符串必须以字母“x”开始,以字母“z”结束。

    第一个和最后一个字符之间可以有零个或多个字母,但其范围必须是 {a,....,y}。

    下图的 FSM 显示了上述语法。每一个转换都是由特定类型的输入来标识。比如,仅当从输入流中读取字母 x 时,才能完成状态 A 到状态 B 的转换。输入任何非“z”的字母,都会使得状态 B 转换为其自身。而仅当从输入流中读取字母 z 时,才会发生状态 B 到状态 C 的转换。

    c693e93439c1a5f3f189f6a3bb85e670.gif

    如果输入流已经结束,而程序只出现了状态 A 和状态 B,那么就生成出错条件,因为只有状态 C 才能标记终止状态。下述输入字符串能被该 FSM 认可:

    xaabcdefgz

    xz

    xyyqqrrstuvz

    验证有符号整数

    下图表示的是 FSM 解析一个有符号整数。输入包括一个可选的前置符号,其后跟一串数字。图中没有对数字个数进行限制。

    51170baebca326da3998ad9b053f702a.gif

    有限状态机很容易转换为汇编代码。图中的每个状态(A、B、C…)代表了一段有标号的程序。每个标号执行的操作如下:

    1) 调用输入程序读入下一个输入字符。

    2)    如果是终止状态,则检查用户是否按下 Enter 键来结束输入。

    3)    一个或多个比较指令检查从状态发岀的所有可能的转换。每个比较指令后面跟一个条件跳转指令。

    比如,在状态 A,如下代码读取下一个输入字符并检查到状态 B 的可能的转换:

    StateA:

    Cal1 Getnext ;读取下一个字符,并送入 AL

    cmp al, '+' ;前置+ ?

    je StateB ;到状态 b

    cmp al, '-' ;前置 - ?

    je StateB ;到状态 B

    call IsDigit ;如果 AL 包含数字,则 ZF = 1

    jz StateC ;到状态 C

    call DisplayErrorMsg ;发现非法输入

    jmp Quit

    下面来更详细地检查这段代码。首先,代码调用 Getnext,从控制台输入读取下一个字符,送入 AL 寄存器。接着检查前置 + 或 -,先将 AL 的值与符号“+”进行比较,如果匹配,就发生到标号 StateB 的跳转:

    StateA:

    call Getnext ;读取下一个字符,并送入 al

    cmp al, ' + ' ;前置 + ?

    je StateB ;到状态 B

    现在,再次查看上图,发现只有输入 + 或 - 时,才发生状态 A 到状态 B 的转换。所以,代码还需检查减号:

    cmp al, '-' ;前置 - ?

    je StateB ;到状态 B

    如果无法发生到状态 B 的转换,就可以检查 AL 寄存器中是否为数字,这可以导致到状态 C 的转换。调用 IsDigit 子程序,当 AL 包含数字时,零标志位置 1:

    call IsDigit ;如果AL包含数字,贝U ZF=1

    jz StateC ;到状态 C

    最后,状态 A 没有其他可能的转换。如果发现 AL 中的字符既不是前置符号,又不是数字,程序就会调用 DisplayErrorMsg (在控制台上显示一条错误消息)子程序,并跳转到标号 Quit 处:

    call DisplayErrorMsg ;发现非法输入

    jmp Quit

    标号 Quit 标识程序的出口,位于主程序的结尾:

    Quit:

    call Crlf

    exit

    main ENDP

    完整的有限状态机程序

    如下程序实现上图所示的有符号整数 FSM:

    ; 有限状态机 (Finite.asm)

    INCLUDE Irvine32.inc

    ENTER_KEY = 13

    .data

    InvalidInputMsg BYTE "Invalid input",13,10,0

    .code

    main PROC

    call Clrscr

    StateA:

    call Getnext ; 读取下一个字符,并送入AL

    cmp al,'+' ; 前置+ ?

    je StateB ; 到状态 B

    cmp al,'-' ; 前置 - ?

    je StateB ; 到状态 B

    call IsDigit ; 如果 AL 包含数字 ,则 ZF = 1

    jz StateC ; 到状态 C

    call DisplayErrorMsg ; 发现非法输入

    jmp Quit

    StateB:

    call Getnext ; 读取下一个字符,并送入AL

    call IsDigit ; 如果AL包含数字,则 ZF = 1

    jz StateC

    call DisplayErrorMsg ; 发现非法输入

    jmp Quit

    StateC:

    call Getnext ; 读取下一个字符,并送入AL

    call IsDigit ; 如果AL包含数字,则 ZF = 1

    jz StateC

    cmp al,ENTER_KEY ; 按下Enter键?

    je Quit ; 是:Quit

    call DisplayErrorMsg ; 否: 发现非法输入

    jmp Quit

    Quit:

    call Crlf

    exit

    main ENDP

    ;-----------------------------------------------

    Getnext PROC

    ;

    ; 从标准输入读取一个字符

    ; 接收: 无

    ; 返回: 字符保存在AL中

    ;-----------------------------------------------

    call ReadChar ; 从键盘输入

    call WriteChar ; 显示在屏幕上

    ret

    Getnext ENDP

    ;-----------------------------------------------

    DisplayErrorMsg PROC

    ;

    ; 显示一个错误消息以表示

    ; 输入流中包含非法输入

    ; 接收: 无.

    ; 返回: 无

    ;-----------------------------------------------

    push edx

    mov edx,OFFSET InvalidInputMsg

    call WriteString

    pop edx

    ret

    DisplayErrorMsg ENDP

    END main

    IsDigit子程序

    有限状态机示例程序调用 IsDigit 子程序,该子程序属于本教程的链接库。现在来看看 IsDigit 的源程序,程序把 AL 寄存器作为输入,其返回值设置零标志位:

    ;----------------------------------------------------

    IsDigit PROC

    ;

    ;确定 AL 中的字符是否为有效的十进制数字。

    ;接收:AL= 字符

    ;返回:若 AL 为有效的十进制字符,ZF=1;否则,ZF=0

    ;---------------------------------------------------

    cmp al,'0'

    jb ID1 ;跳转发生,ZF=0

    cmp al, '9'

    ja ID1 ;跳转发生,ZF = 0

    test ax, 0 ;设置 ZF=1

    ID1: ret

    IsDigit ENDP

    在查看 IsDigit 的代码之前,先回顾十进制数字的十六进制 ASCII 码,如下表所示。由于这些值是连续的,因此,只需要检查第一个和最后一个值:

    字符

    '0'

    '1'

    '2'

    '3'

    '4'

    '5'

    '6'

    '7'

    '8'

    '9'

    ASCII 码(十六进制)

    30

    31

    32

    33

    34

    35

    36

    37

    38

    39

    IsDigit 子程序中,开始的两条指令将 AL 寄存器中字符的值与数字 0 的 ASCII 码进行比较。如果字符的 ASCII 码小于 0 的 ASCII 码,程序跳转到标号 ID1:

    cmp al, '0'

    jb ID1 ;跳转发生,ZF=0

    但是有人可能会问了,如果 JB 将控制传递给标号 ID1,那么,怎么知道零标志位的状态呢?答案就在 CMP 指令的执行方式里——它执行一个隐含的减法操作,从 AL 寄存器的字符中减去 0 的 ASCII 码(30h)。如果 AL 中的值较小,那么进位标志位置 1,零标志位清除(你可能想用调试器来单步执行这段代码来验证这个事实)。JB 指令的目的是,当 CF=1 且 ZF=0 时,将控制传递给一个标号。

    接下来,IsDigit 子程序代码把 AL 与数字 9 的 ASCII 码进行比较。如果 AL 的值较大,代码跳转到同一个标号:

    cmp al, '9'

    ja ID1 ;跳转发生,ZF=0

    如果 AL 中字符的 ASCII 码大于数字 9 的 ASCII 码(39h),清除进位标志位和零标志位。这也正好是使得 JA 指令将控制传递到目的标号的标志位组合。

    如果没有跳转发生(JA 或 JE),又假设 AL 中的字符确实是一个数字,则插入一条指令确保将零标志位置 1。将 0 与任何数值进行 test 操作,就意味着执行一次隐含的与全 0 的 AND 运算。其结果必然为 0:

    test ax, 0          ; 置 ZF=1

    前面 IsDigit 中的 JA 和 JB 指令跳转到了 TEST 指令后面的标号。所以,如果发生跳转,零标志位将清零。下面再次给出完整的过程:

    Isdigit PROC

    cmp al,'0'

    jb ID1 ;若跳转发生,则 ZF=0

    cmp al,'9'

    ja ID1 ;若跳转发生,则 ZF=0

    test ax,0 ;置 zf=1

    ID1: ret

    Isdigit ENDP

    在实时或高性能应用中,程序员常常利用硬件特性的优势,来对其代码进行充分优化。IsDigit 过程就是这种方法的例子,它利用 JB、JA 和 TEST 对标志的设置,实际上返回的是一个布尔结果。

    展开全文
  • 你必须知道的495C语言问题

    千次下载 热门讨论 2015-05-08 11:09:25
    然后又使用一些内存分配技巧使namestr数组用起来好像有多个元素,namelen记录了元素个数。它是怎样工作的?这样是合法的和可移植的吗? 2.8 我听说结构可以赋给变量也可以对函数传入和传出。为什么K&R1却明确说明...
  • 《你必须知道的495C语言问题》

    热门讨论 2010-03-20 16:41:18
    书中列出了C用户经常问的400多个经典问题,涵盖了初始化、数组、指针、字符串、内存分配、库函数、C预处理器等各个方面的主题,并分别给出了解答,而且结合代码示例阐明要点。 《你必须知道的495个C语言问题》结构...
  • 然后又使用一些内存分配技巧使namestr数组用起来好像有多个元素,namelen记录了元素个数。它是怎样工作的?这样是合法的和可移植的吗? 23  2.8 我听说结构可以赋给变量也可以对函数传入和传出。为什么K&R1却明确...
  • 数据结构之二叉树

    2018-03-05 14:27:31
    递归的有点在简化思路,程序员只需要考虑当前步骤需要做什么,我的理解中递归的实现需要的是可重复的步骤以及递归的终止条件,在实际情况中,很问题用循环实现会很难实现,简单的例子就是快速排序算法,使用递归...

    二叉树结构


    1.递归思想

    大学时期对递归一直不是很清晰,其实大部分情况下能通循环最好就使用循环,因为递归不断调用函数会导致程序运行效率下降。递归的有点在简化思路,程序员只需要考虑当前步骤需要做什么,我的理解中递归的实现需要的是可重复的步骤以及递归的终止条件,在实际情况中,很多问题用循环实现会很难实现,简单的例子就是快速排序算法,使用递归思路很简单,而使用循环。。。那可能还需要一个栈的数据结构存放节点。


    前几天看到的找零问题就可以使用递归的思路,轻松解决问题。
    题目是这样的:

    小易准备去魔法王国采购魔法神器,购买魔法神器需要使用魔法币,但是小易现在一枚魔法币都没有,但是小易有两台魔法机器可以通过投入x(x可以为0)个魔法币产生更多的魔法币。
    魔法机器1:如果投入x个魔法币,魔法机器会将其变为2x+1个魔法币 魔法机器2:如果投入x个魔法币,魔法机器会将其变为2x+2个魔法币
    小易采购魔法神器总共需要n个魔法币,所以小易只能通过两台魔法机器产生恰好n个魔法币,小易需要你帮他设计一个投入方案使他最后恰好拥有n个魔法币。

    只看算法部分:

    def Exchange(target):
        if target==0:
            return
        elif target%2:
            target=(target-1)/2
            Exchange(target)
            print(1)
        else:
            target=(target-2)/2
            Exchange(target)
            print(2)

    只需要从最后一步开始,每一步向前推进一个步骤,函数只需要考虑当前步骤需要做的事情即可。

    2.二叉树的定义

    二叉树是一个连通的无环图,并且每一个顶点的度不大于3。有根二叉树还要满足根结点的度不大于2。有了根结点之后,每个顶点定义了唯一的父结点,和最多2个子结点。然而,没有足够的信息来区分左结点和右结点。如果不考虑连通性,允许图中有多个连通分量,这样的结构叫做森林。

    基本节点

    二叉树的五种基本形态
    1. 空二叉树
    2. 只有一个根节点
    3. 根节点只有左子树
    4. 根节点只有右子树
    5. 根节点既有左子树又有右子树

    3.二叉树相关性质


    1. 在二叉树第i层上最多有2^(i-1)个节点。
    2. 深度为k的二叉树最多有2^k-1个节点
    3. 对于任何一个二叉树T,如果其终端节点数为n0,度为二的根节点数为n2则n0=n2+1
    4. 具有n个节点的完全二叉树的深度为\log 2_n +1

    4.二叉树的遍历

    这里写图片描述

    前序遍历
    总是先查找根节点,之后查找左子树,最后查找右子树。(根左右)
    上图按照前序遍历应该为:ABDEC

    中序遍历
    总是先查找左子树,再查找根,最后查找右子树。(左根右)
    上图按照中序遍历就应该为:DBEAC

    后序遍历
    总是先查找左子树,再查找右子树,最后查找根节点。(左右根)
    上图按照后序遍历就应该为:DEBCA

    出了前序遍历和后序遍历的组合外,任意两个遍历方法值都能确定一个二叉树。

    5.建立二叉树


    因为一种遍历方式的值并不能唯一确定一个二叉树,所以需要用两种遍历值来确定,当然还有一种更简单的方法,空出来的节点用一个特殊字符表示,这里选择用’#’来表示空的节点。上图进行变换后应该如下图所示。
    这里写图片描述
    此时如果采用前序遍历那么结果应该是:ABD##E##C##,此时该二叉树是唯一确定的。


    采用前序遍历的结果作为生成二叉树的依据。
    **构建时采用递归思路,每一个步骤都是写入根节点,开辟左节点内存,右节点内存,进入左节点,进入右节点。
    终止条件是:当该节点的值为’#’时,写入根节点,不再开辟左右几点内存,返回**

    C/C++实现如下:

    //节点类
    class TreeNode
    {
    public:
        int date;
        TreeNode*LeftChild;
        TreeNode*RightChild;
    };

    二叉树类型:

    class BiTree
    {
    public:
        TreeNode*Root;
        void CreateTree(TreeNode**ptr,int *s);
        int Deepth(TreeNode*ptr);
        BiTree(int*s);//构造函数 使用int数组来构造树
        int GetDeepth();//获得二叉树的深度
    };

    这里为了后面的搜索二叉树,存放的不再是字符(char类型)而换成了(int类型),-1代表空,也就是说将’#’换成-1。

    构造方法:

    BiTree::BiTree(int*s)
    {
        Root = new TreeNode;
        CreateTree(&Root,s);
    }
    
    void BiTree::CreateTree(TreeNode**ptr, int*s)
    {
        static int index = 0;
        if (s[index] == -1)
        {
            (*ptr)->date = -1;
            (*ptr)->LeftChild = NULL;
            (*ptr)->RightChild = NULL;
            index++;
        }
        else
        {//根左右的前序遍历方法
            (*ptr)->LeftChild = new TreeNode;
            (*ptr)->RightChild = new TreeNode;
            (*ptr)->date = s[index++];
            CreateTree(&(*ptr)->LeftChild, s);
            CreateTree(&(*ptr)->RightChild, s);
        }
    }

    该构造函数需要输入的int数组是正确符合前序遍历的,否则可能出现数组越界问题。


    获取二叉树深度

    int BiTree::GetDeepth()
    {
        return Deepth(Root);
    }
    
    int BiTree::Deepth(TreeNode*ptr)
    {
        if (ptr->date == -1)
        {
            return 0;
        }
        int nLeft = Deepth(ptr->LeftChild);
        int nRight = Deepth(ptr->RightChild);
        return nLeft > nRight ? nLeft + 1 : nRight + 1;
    }
    展开全文
  • 垃圾收集(中英文).pdf

    热门讨论 2011-12-06 08:04:18
    7.3.1 多个分代 7.3.2 提升的闽值 7.3.3 standard ml of new jersey收集器 7.3.4 自适应提升 7.4 分代组织和年龄记录 7.4.1 每个分代一个半区 7.4.2 创建空间 7.4.3 记录年龄 7.4.4 大型...
  • 一个可行解一般由多个元素构成,那么这每一个元素就被称为染色体上的一个“基因”。 比如说,对于如下函数而言,[1,2,3]、[1,3,2]、[3,2,1]均是这个函数的可行解(代进去成立即为可行解),那么这些可行解在遗传算法...
  • 7.3.1 多个分代 7.3.2 提升的阈值 7.3.3 Standard ML of New Jersey收集器 7.3.4 自适应提升 7.4 分代组织和年龄记录 7.4.1 每个分代一个半区 7.4.2 创建空间 7.4.3 记录年龄 7.4.4 大型对象区域 7.5 分代间指针 ...
  • 7.3.1 多个分代 7.3.2 提升的阈值 7.3.3 Standard ML of New Jersey收集器 7.3.4 自适应提升 7.4 分代组织和年龄记录 7.4.1 每个分代一个半区 7.4.2 创建空间 7.4.3 记录年龄 7.4.4 大型对象区域 7.5 分代间指针 ...
  • Unix/Linux 编程实践教程.PDF

    千次下载 热门讨论 2010-09-03 18:34:12
    4.6 多个文件系统的组合:由多棵树构成的树 4.6.1 装载点 4.6.2 多重 i- 节点号和设备交叉链接 4.6.3 符号链接 小结 第五章 连接控制:学习 stty 5.1 为设备编程 5.2 设备就像文件 5.2.1 设备具有文件名 ...
  • 14.5 协议DAYTIME服务器的例子 122 14.6 共享代码的概念 125 14.7 并发协议服务器 125 14.8 小结 126 深入研究 126 习题 126 第15章 服务服务器(TCP,UDP) 127 15.1 引言 127 15.2 合并服务器 127 ...
  • Unix操作系统设计

    2015-06-16 22:50:24
    8.1.3 进程调度的例子 8.1.4 进程优先权的控制 8.1.5 公平共享调度 8.1.6 实时处理 8.2 有关时间的系统调用 8.3 时钟 8.3.1 重新启动时钟 8.3.2 系统的内部定时 8.3.3 直方图分析 8.3.4 记帐和统计 8.3.5 计时 8.4 ...
  • Unix操作系统设计2000

    2015-06-16 22:53:53
    8.1.3 进程调度的例子 8.1.4 进程优先权的控制 8.1.5 公平共享调度 8.1.6 实时处理 8.2 有关时间的系统调用 8.3 时钟 8.3.1 重新启动时钟 8.3.2 系统的内部定时 8.3.3 直方图分析 8.3.4 记帐和统计 8.3.5 ...
  • 8.1.3 进程调度的例子 8.1.4 进程优先权的控制 8.1.5 公平共享调度 8.1.6 实时处理 8.2 有关时间的系统调用 8.3 时钟 8.3.1 重新启动时钟 8.3.2 系统的内部定时 8.3.3 直方图分析 8.3.4 记帐和统计 8.3.5 ...
  • 7.11 例子分析 7.11.1 SVR 4.2/MP 7.11.2 Digital UNIX 7.11.3 其他实现 7.12 小结 7.13 练习 7.14 参考文献 第8 章 文件系统接口和框架(191) 8.1 简介 8.2 文件的用户接口 8.2.1 文件和目录 8.2.2 文件属性 8.2.3 ...
  • 16.4 与多个服务器的并发联系 167 16.5 实现并发的客户端 168 16.6 单线程实现 169 16.7 使用ECHO的并发客户端例子 170 16.8 并发客户端的执行 175 16.9 计时器的管理 176 16.10 输出举例 176 16.11 例子...
  • Flink自带WordCount例子,它通过socket读取text数据,并且统计每单词出现的次数。 WordCount案例:Java Scala 1、基本API 以上为Flink的运行模型(和Spark基本一致),Flink的程序主要由三部分构成,分别为...
  • 1.2.3 邦弗朗尼原理的一个例子 1.2.4 习题 1.3 相关知识 1.3.1 词语在文档中的重要性 1.3.2 哈希函数 1.3.3 索引 1.3.4 二级存储器 1.3.5 自然对数的底e 1.3.6 幂定律 1.3.7 习题 1.4 本书概要 1.5 小结...
  • 1.2.3 邦弗朗尼原理的一个例子 1.2.4 习题 1.3 相关知识 1.3.1 词语在文档中的重要性 1.3.2 哈希函数 1.3.3 索引 1.3.4 二级存储器 1.3.5 自然对数的底e 1.3.6 幂定律 1.3.7 习题 1.4 本书概要 1.5 小结...
  • 与开发人员在测试组环境次重复以上步骤,发现11群的计次表话单有时正常,有时其出中继群号就为一随机值,发生异常的频率比较高。为什么其它群的话单正常,唯独11群不正常呢?11群是四群中最小的群,其中继计...
  • 为了解决开发者维护多个 App 升级繁琐,重复逻辑过多,管理不便的问题,升级中心uni-upgrade-center应运而生。 提供了简单、易用、统一的 App 管理、App 版本管理、安装包发布管理,升级检测更新管理。 升级中心...
  • 为了解决开发者维护多个 App 升级繁琐,重复逻辑过多,管理不便的问题,升级中心uni-upgrade-center应运而生。 提供了简单、易用、统一的 App 管理、App 版本管理、安装包发布管理,升级检测更新管理。 升级中心...
  • 实例174 捕获多个异常 第8章 枚举与泛型的应用 8.1 枚举使用的简介 实例175 查看枚举类型的定义 实例176 枚举类型的基本特性 实例177 增加枚举元素的信息 实例178 选择合适的枚举元素 实例179 高效的枚举...

空空如也

空空如也

1 2 3
收藏数 46
精华内容 18
关键字:

多个终止节点例子