精华内容
下载资源
问答
  • 正则语言的 并

    千次阅读 2014-09-08 17:31:07
    正则表达式,描述的是正则语言, 学过形式语言自动机理论的人应该都知道,正则语言在并、、补运算下都是封闭的;但是,根据 Wikipedia 的描述,到目前为止,还没有任何一个已知的正则语法(Flavor)将...

    请关注我们的技术创业项目 Terark,领先的数据技术提供商


    本文转载于我自己的官方网站:nfabo.cn

    正则语言的 并 交 差

    正则表达式,描述的是正则语言, 学过形式语言与自动机理论的人应该都知道,正则语言在运算下都是封闭的;但是,根据 Wikipedia 的描述,到目前为止,还没有任何一个已知的正则语法(Flavor)将纳入正则语法。理论与实践之间竟然隔着这么巨大的鸿沟!

    虽然 Perl 正则中支持的环视(Look Around)在某种意义上可以认为是受限子集,之所以说是受限,因为你无法自由组合并交差操作。另一方面,环视在这些引擎中都是以回溯的方式实现的,效率十分低下。

    其实,不光正则语言在运算下都是封闭的,而且,用来表达正则语言的 DFA 可以比较高效地实现这些操作,对比 NFA 转 DFA 的 O(2n),并交差的复杂度是O(n*m),补的复杂度是O(n);这比  O(2n) 要乐观地多,而且,这只是最坏情况下的复杂度,现实中很多时候都是 O(n1+ε),这其中的 ε 往往接近于0,NFA 转 DFA 的最坏 O(2n)在现实中也往往是O(n1+ε),不过这个 ε 往往要大一些。

    经过一番努力,我填补了交 、 差这个鸿沟,为了语言的完备性和易用性,同时也实现了传统正则的连接重复,为了区别于传统的 RegEx,暂且把它叫 RegEx++

    在语言设计上,一方面为了避免处理无比复杂的转义、字符类、unicode之类的泥潭,另一方面也为了兼容传统的正则,我设计的 RegEx++ 语言分为两部分,一部分是去除了环视和反向引用的Perl正则(re2语法),一部分是 RegEx++ 特有的 、 连接重复

    以 BNF 范式表达

    Union  :=Inter{'||'Union}
    Inter  :=ConCat{'&&'ConCat|'&!'ConCat}
    ConCat :=Repeat{Repeat}
    Repeat :=Atom['?'|'*'|'+'|Range]
    Atom   :='{{'Regex'}}'|'('Union')'
    Range  :='{'Min[','Max]|','Max'}'

    用更通俗的方式表达

    优先级 操作符 说明
    最高 {{Plain Old Regex}} {{}}括起来的部分是传统的正则表达式,使用 re2 的 Parser 解析
    较高 (   ) 调整优先级
    ? 重复:0次或1次 语法和意义与传统正则相同
    * 重复:0次或多次
    + 重复:1次或多次
    {min,max} 重复:最少min次,最多max次
    无操作符 连接,连着写就行
    较低 && 交,x && y 表示既能匹配 x 又能匹配 y
    &! 差,x &! y 表示能匹配 x 但不能匹配 y
    最低 || 并,x || y 表达能匹配 x 或者能匹配 y

    这里面唯一比较别扭的是{{ }}括起来的 Plain Old Regex, 值得一提的是,{{ 和 }},用来括住正则表达式(re2语法),一个语法正确并且规范的正则表达式中不会出现 {{ 和 }},只有一个例外:\{{,这个例外很容易处理。其实严格讲,语法正确的正则表达式中可以出现 {{ 和 }},但这样正则表达式往往是有问题的,和 } 用作非元字符时,需要转义(\{\}),而 和 不转义时是元字符,不会出现 {{ 和 }}, Plain Old Regex 允许未转义的 { 和 } 是为了最大限度地“容忍错误”,传统正则语法甚至容忍这样的正则: [[[[]*,还有 ]{{1-2},你知道这都是什么意思吗?

    最后

    通过 这个测试页面 可以看到一些例子和相应的 DFA/NFA 状态转移图。

    展开全文
  • mysql的

    千次阅读 2018-01-08 22:43:25
    Mysql只提供了并集(union),没有提供差集,和交集,可以用union来实现.   先建两个结构一样的表table1和table2   create table table1(name varchar(20)); create table table2(name varchar(20)); ...

    Mysql只提供了并集(union),没有提供差集,和交集,可以用union来实现交和差.

     

    先建两个结构一样的表table1和table2

     

    create table table1(name varchar(20));
    
    create table table2(name varchar(20));

    插入数据

     

    #向table1中插入数据
    insert into table1 (name) values
    ('甲'),('乙'),('丙');
    #向table1中插入数据
    insert into table2 (name) values
    ('甲'),('乙'),('丁'),('戊'),('己');

     

     

     

     

     

    一个简单的并集运算(默认去除重复条目,若不去除重复条目在'union'后面加上' all'):

    select * from table1 union select * from table2;

     

    结果如下

    +------+
    | name |
    +------+
    | 甲   |
    | 乙   |
    | 丙   |
    | 丁   |
    | 戊   |
    | 己   |
    +------+

     

     

    用union来实现交:

    table1与table2交集(原理就是求table1与table2不去除重复条目的并集,然后按名字分组,取其中重复条目)

    select * from (select * from table1 union all select * from table2)temp group by name having count(*)>1; 

    结果如下

    +------+
    | name |
    +------+
    | 甲   |
    | 乙   |
    +------+

     

     

    用union来实现差:

    table1与table2差(取其中不重复条目)

    select * from (select * from table1 union all select * from table2)temp group by name having count(*)=1;

    结果如下

    +------+
    | name |
    +------+
    | 丙   |
    | 丁   |
    | 己   |
    | 戊   |
    +------+

     

     

     

    展开全文
  • 多边形求

    千次阅读 2017-11-28 15:53:31
    代码:Github:team79/PolygonOverlayAnalysis基本概念介绍多边形计算的算法的相关证明过程是很繁琐,因此在这里将直接给出算法所需的概念以及算法所用到的一些性质。具体的相关证明过程在ZHU Ya-Yin[1]论文中...

    代码:Github:team79/PolygonOverlayAnalysis

    基本概念介绍

    多边形交并差计算的算法的相关证明过程是很繁琐,因此在这里将直接给出算法所需的概念以及算法所用到的一些性质。具体的相关证明过程在ZHU Ya-Yin[1]论文中有详细证明。
    算法中的一些概念:

    • 1、∂A :多边形A 的边的集合, 或A 的边界上点的集合;
    • 2、P ↓:过点P 作的垂直向下射线;
    • 3、<:点的小于比较符, P < Q (Px < Qx )∨(Px =Qx ∧ Py < Qy);
    • 4、P x , Py :P 的横、纵坐标;
    • 5、Lp(e):e 的左端点, 即e 两端点中较小的一个;
    • 6、Rp(e):e 的右端点, 即e 两端点中较大的一个;
    • 7、I(e):e 内点(e 上除端点外的其他点)的集合;
    • 8、e , s :边;
    • 9、C(P ,∂ A):与P ↓有交点, 且右端点不在P ↓上的A 的边集合.即C(P , ∂A)={s s ∈ A , s ∩P ↓≠ , R p(s) P ↓};
    • 10、s1 >P s2 :边s1 , s2 在通过P 点的垂直线x =Px上的比较, 即s1 >P s2 (Q1 >Q2)∨ (Q1 =Q2 ∧Ks1 >Ks2), 其中点Q1 , Q2 表示边s1 , s2 与过P 点的垂线的交点, Ks1 , Ks2 分别表示s1 , s2 的斜率;
    • 11、max(C(P , ∂A)):表示C(P , ∂A)中在P 点处的最大边。

    算法所用到的定理与性质:

    • 1、对于多边形A 的任一条边,设P是e的内点, 如果C(P , ∂A)有奇数条边, 则称e是A的奇边, 简记为+e,否则称e是A的偶边,简记为-e;
    • 2、对于任意两条边s1 , s2 ∈ C(P ,∂ A), 如果s2 是在P 点处小于s1 的最大边, 即s1 >P s2 , 且不存在边e ∈ C(P ,∂ A), 使得s1 >P e , e >P s2 同时成立, 则s1 , s2 在A 中的奇偶相异;
    • 3、对于任一不在多边形A 边界上的点P , 如果过点P 所作的垂直向下的射线与多边形A
      的相交的最大边是偶边, 或没有与A 的任何边相交, 则P 在多边形A 的外域, 其逆亦然;如果射线与A 相交的最大边是奇边, 则P 在多边形A 的内域,其逆亦然;
    • 4、内边:e 的所有内点均位于A 的内域, P , P∈ I(e) P ∈ I (A);
    • 5、外边:e 的所有内点均位于A 的外域, P , P∈ I(e) P ∈ E(A);
    • 6、重叠边: s , s ∈ A , P , P ∈ e P ∈ s;
    • 7、简单边:内边、外边、重叠边;
    • 8、复杂边:不属于简单边的其他边。

    算法总体流程

    算法整体步骤如下:

    • Setp1 .在平面扫描过程中, 计算A , B 的交点(包括切点), 分解复杂边为简单边, 同时根据算法1 , 2 , 确定A , B 边的奇偶性及其拓扑类型, 并记录在数据结构中;
    • Setp2 .针对多边形交、并、差的具体计算特点,分别根据算法2-11、2-12、2-13进行边的跟踪, 输出构成A ∩B , A ∪ B , A -B 的中间多边形;
    • Setp3 .依次构造各中间多边形的Border , 确定中间多边形的方向性.根据定理与性质判断其是洞还是外接多边形;
    • Setp4 .判断洞Border 与外接多边形Border 的包含被包含关系, 确定洞归属于哪个外接多边形, 进而确定A ∩ B , A ∪ B , A -B.

    多边形求交算法

    多边形求交的伪代码表示如下表:

    I   for each e of A , B 的边{
    II  if e 没有访问过∧ (e 是内边∨ )then
    III         do{
    IV          标记e 为已访问;如果e 是重叠边, 还要标记其重叠边e′为已访问;
    V               if e 是奇边then {
    VI              把e 的左端点添加到顶点链表中;
    VII                 P →e 的右端点;
    VIII            }else {∥隐含条件e 是偶边
    IX                  把e 的右端点添加到顶点链表中;
    X                   P →e 的左端点;
    XI              }
    XII             if (在连接P 的另一输入多边形的邻边中, 存在着满足条件的内边s :
    XIII                s 是奇边且P =Lp(s), 或者s 是偶边且P =Rp(s))then e →s ;
    XIV             else e →连接P 的本输入多边形的邻边;
    XV          }until P 与顶点链表中的第1 个顶点相等;
    XVI         输出顶点链表中顶点组成的中间多边形, 并清空顶点链表;
    XVII    } ∥end if
    XVIII} ∥end fo r

    多边形求并算法

    多边形求并的伪代码表示如下表:

    I   for each e of A , B 的边{
    II  if e 没有访问过∧ (e 是外边∨ )then
    III         do{
    IV          标记e 为已访问;如果e 是重叠边, 还要标记其重叠边e′为已访问;
    V               if e 是奇边then {
    VI              把e 的左端点添加到顶点链表中;
    VII                 P →e 的右端点;
    VIII            }else {∥隐含条件e 是偶边
    IX                  把e 的右端点添加到顶点链表中;
    X                   P →e 的左端点;
    XI              }
    XII             if 连接P 的本输入多边形的邻边s 是外边then e→s;
    XIII            else if 连接P 的另一输入多边形的邻边中, 存在着外边s′then e →s′.
    XIV             else e →连接P 的本输入多边形的邻边;
    XV          }until P 与顶点链表中的第1 个顶点相等;
    XVI         输出顶点链表中顶点组成的中间多边形, 并清空顶点链表;
    XVII    } ∥end if
    XVIII} ∥end fo r

    多边形求差算法

    多边形求差的伪代码表示如下表:

    I   for each e of A , B 的边{
    II  if e 没有访问过∧ ((e 是A 的外边)∨ (e 是B 的内边))then {
    III         do{
    IV          记e 为已访问;如果e 是重叠边, 还要标记其重叠边e′为已访问;
    V               if e 是A 的奇边或是B 的偶边then {
    VI              把e 的左端点添加到顶点链表中;
    VII                 P →e 的右端点;
    VIII        }else {∥隐含条件:e 是A 的偶边或是B 的奇边
    IX                  把e 的右端点添加到顶点链表中;
    X                   P →e 的左端点;
    XI              }
    XII             if e 是A 的边, 与P 相连的属于B 的邻边中, 存在着满足条件的内边s:s 是B 的奇边且P 是s的右端点, 或者s 是偶边且P 是s 的左端点then e →s ;
    XII             else if e 是B 的边, 与P 相连的属于A 的邻边中, 存在着满足条件的外边s′:s′是奇边且P 是s′的左端点, 或s′是偶边且P 是s′的右端点then e →s′
    XIV             else e →连接P 的本输入多边形的邻边;
    XV          }until P 与顶点链表中的第1 个顶点相等;
    XVI         输出顶点链表中顶点组成的中间多边形, 并清空顶点链表;
    XVII    } ∥end if
    XVIII} ∥end fo r

    多边形:

    这里写图片描述

    交:

    这里写图片描述

    并:

    这里写图片描述

    差:

    这里写图片描述

    展开全文
  • C语言数组实现

    千次阅读 2018-09-11 21:33:45
    C语言数组实现 这个是输入数组时会检查重复并让重新输入,以小于0的整数结束数组的输入 #include&lt;stdio.h&gt; #define MAX 100 int main() { char A,B; int i=0,j=0,k=0,num=0,num_D=0,NUM=...

    C语言数组实现交并差
    这个是输入数组时会检查重复并让重新输入,以小于0的整数结束数组的输入

    #include<stdio.h>
    #define MAX 100
    int main()
    
    {
       char A,B;
       int i=0,j=0,k=0,num=0,num_D=0,NUM=0,nums=0;
       int nums_01[MAX];//第一个数组
       int nums_02[MAX];//第二个数组
       int nums_03[MAX];//记录交集数组
       int nums_04[MAX];//记录并集数组
       bool Judge=true;//用来判断是否重复
       printf("输入集合名:");
       scanf("%c",&A);
        printf("\n输入集合数字:");
       scanf("%d",&nums_01[i]);
       while(nums_01[i]>=0)
       {
            Judge=true;
            for(nums=0;nums<i;nums++)//判断是否重复
            {
                if(nums_01[i]==nums_01[nums])
                {
                    printf("输入有重复请重新输入!!!\n");
                    Judge=false; 
                    break; 
                 } 
            }
            if(Judge)//重复就跳过重新输入
            {
    
             nums_04[k]=nums_01[i];
             i++;
             k++;
            }
             scanf("%d",&nums_01[i]);
        }
       printf("\n输入集合名:");
       fflush(stdin); 
       scanf("%c",&B);
       printf("\n输入集合数字:");
       fflush(stdin);
       scanf("%d",&nums_02[j]);
       while(nums_02[j]>=0)
       {
    
            Judge=true;
            for(nums=0;nums<j;nums++)//判断是否重复
            {
                if(nums_02[j]==nums_02[nums])
                {
                    printf("输入有重复请重新输入!!!\n");
                    Judge=false; 
                    break; 
                 } 
            }
            if(Judge)//重复就跳过重新输入
            {
                nums_04[k]=nums_02[j];//记录并集
                for(num=0;num<=i;num++)//用来记录
                 {
                    if(nums_02[j]==nums_01[num])
                     {
                        nums_03[num_D]=nums_02[j];//记录交集
                        nums_01[num]=-1;//赋予-1,用来区分差集
                        num_D++;
                        k--;//因为重复所以自减覆盖这个数字来达到并集
                        break;
                    }
                  }
               j++;
               k++;
            }
           scanf("%d",&nums_02[j]);
    
       }
    printf("%c交%c:",A,B);
    for(NUM=0;NUM<=num_D-1;NUM++)
    {
       printf("%d\t", nums_03[NUM]);
    }
    printf("\n%c交%c:",A,B);
    for(NUM=0;NUM<k;NUM++)
    {
        printf("%d\t", nums_04[NUM]);
     } 
    printf("\n%c-%c:",A,B);
    for(num=0;num<i;num++)
    {
        if(nums_01[num]!=-1)
        printf("%d\t", nums_01[num]);
    }
        return 0;
    }
    展开全文
  • 用C++实现集合的并、运算的设计思路

    万次阅读 多人点赞 2018-11-28 19:49:15
    编制一个能演示执行集合的并、运算的程序。 一. 该课题研究的是:设计程序实现集合的并、和补的混合运算;同时,可以进行集合中元素的判定、集合子集的判定和求集合的补集;还可以对不同元素类型的...
  • c++实现集合的运算

    万次阅读 多人点赞 2018-12-18 09:58:14
    实现集合的运算; 如果不懂概念,请自行百度,不作复述; 代码如下: #include&lt;iostream&gt; #include&lt;cstring&gt; #include&lt;stdlib.h&gt; using namespace std; int ...
  • 集合并,,对称总结

    千次阅读 2016-05-03 19:49:58
    有关STL set关于集合并,,对称总结:  merge(), // 归并两个序列,元素总个数不变,只是将两上子有序序列归并为一个有序序列。  set_union(), // 求集合A,B的并。  set_difference(),  ...
  • 一、查询(INTERSECT) ①查询查出的数据是两个数据表中的哪块...看来不是这样的,报错提示:UNION(联合查询),INTERSECT(查询)EXCEPT(查询)必须在目标列表中有相同的数目表达式,具体什么是数目表达式,...
  • python列表的

    千次阅读 2019-05-06 16:34:54
    list1=[1,2,3] list2=[1,4,6] # 并集 a = set(list1) | set(list2) a -> {1, 2, 3, 4, 6} # 交集 b = set(list1) & set(list2) b ->...# 差集(在list1当中有,list2当中没有的元素) ...c ->...
  • SQL中的并、运算

    千次阅读 2020-07-07 00:00:50
    SQL中的并、运算 1、(对应于集合中的交集操作,A∩B) 注:返回查询结果中相同的部分既他们的交集,想保留所有的重复,必须用INTERSECT ALL代替INTERSECT (select * from table1) intersect (select * ...
  • Oracle 、并

    千次阅读 2019-04-10 10:12:27
    交集: intersect运算: SELECT * FROM t_A intersect SELECT * FROM t_B; 差集: minus运算:返回t_A表中去掉t_B的记录 SELECT * FROM t_A MINUS SELECT * FROM t_B;...where (a.ID,a.Name) not ...
  • 求集合(用单链表表示)的并、运算: 问题描述:该算法的设计,要求运行结果如下所示: (包含三种排序) 集合的运算如下: 原 集 合A: c a e h 原 集 合B: f h b g d a 有序集合A: a c e h 有序集合B: a b d f g...
  • c++语言 实现集合的

    千次阅读 2018-03-27 10:09:34
    c++语言的stl模版库中 提供了许多模板算法函数,许多函数不同的用处详细的需要我们自己把握,就拿取集合的运算来说,肯定有很多种实现方式,我们只需记得函数返回值是一个迭代器就好。/* 集合的实现 by...
  • 链表实现集合的、并、运算

    千次阅读 多人点赞 2019-07-01 21:23:34
    最近在帮大一的小学弟做数据结构的课设,感觉这个题目呀比较有意思,就发出来了。 #include <stdio.h> #include <stdlib.h> #define true 1 #define false 0 typedef struct Node ...void a...
  • 为了进行并、运算,要求运算的两个查询结果具有相同的字段个数,并且对应的字段的值要出自同一个值域,即具有相同的数据类型和取值范围  10:并运算(union)  主要将两个或者更多个查询的结果组合...
  • 集合的 补 运算

    千次阅读 2012-10-18 12:59:09
    这是离散数学上的一个实验题,让用编程实现集合的 补的运算。我这是借鉴的同学的。我自己水平还达不到啊。                                             ...
  • 集合的并、运算

    千次阅读 2016-01-15 17:21:14
    在以单链表表示的正整数的有序集合上,实现集合的并、运算。 基本要求: (1)用单链表存储集合中的数据; (2)对单链表中的数据进行排序。 测试数据要求: 数据中包含的整数,是随机产生的两位整数 #...
  • 集合的并、运算(C语言)

    千次阅读 多人点赞 2020-11-30 21:44:15
    编制一个能演示执行集合的并、运算的程序。 二、问题分析和任务定义 1. 需求分析(完成的任务、提供的功能) (1)集合的元素限定为小写字母字符 [‘a’…’z’] 。 (2)集合的元素判定和子集判定运算。 (3)求...
  • 单链表实现集合的并、运算

    千次阅读 2018-10-24 17:48:34
    带头结点的单链表实现集合的并、运算。 #include &lt;iostream&gt; //引用输入输出流库函数的头文件 using namespace std; template &lt;class T&gt; struct Node {  T data;  Node&...
  • 使用高级程序设计语言实现集合的运算

    千次阅读 多人点赞 2020-05-11 20:35:57
    利用高级语言实现集合、并操作 实验数据文件: R: a1 b1 c1 a1 b2 c2 a2 b2 c1 S: a1 b2 c2 a1 b3 c2 a2 b2 c1 实际输入数据为: 3 3 3 a1 b1 c1 a1 b2 c2 a2 b2 c1 a1 b2 c2 a1 b3 c2 a2 b2 c1 其中R的行数...
  • 为了进行并、运算,要求运算的两个查询结果具有相同的字段个数,并且对应的字段的值要出自同一个值域,即具有相同的数据类型和取值范围  10:并运算(union)  主要将两个或者更多个查询的结果组合...
  • 集合的并、运算的程序

    千次阅读 2017-07-04 08:00:51
    编制一个能演示执行集合的并、运算的程序。 【基本要求】 (1)集合的元素限定为小写字母符[′a′„.′z ′],集合的大小n。 ⑵集合输入的形式为一个以”回车符”为结束标志的字符串,串中字符顺序不限,...
  • 编译命令:g++ main.cpp -lgdal 调用命令:./a.out 输出shp名称 操作选项 注释:操作选项(1:多边形A - 多边形B,2:B - A,3:A和B的交集部分) #include "ogrsf_frmts.h" #include ... cons
  • 送人玫瑰手有余香,救人一命胜造七级浮屠,C++学生管理系统不了我就死定了,大叔大婶行行好
  • sql并--的处理

    千次阅读 2018-06-14 10:09:18
    并集:union eg: 求学过002或者003课程同学的学号: select s# from sc where c#='002' union select s# from sc where c#='003' 等同于 select s# from sc where c#='002' or c#='003'交集...
  • 顺序表集合的操作

    千次阅读 2017-10-25 16:37:09
    3.用顺序表表示集合,设计一个算法实现集合的求运算 void Diffence(SqList A,SqList B,SqList &C) { int i,j,k=0; //k记录C中的元素个数 for(i=0; i; i++) //遍历顺序表A { j=0; while(j[j]!=A.data[i...
  • 集合运算—并、运算

    千次阅读 2019-12-06 16:57:39
    已知所给集合 A 和 B,求 A B 的并集 C(C=A∪B) 已知所给集合 A 和 B,求 A B 的交集 C(C=A∩B) 已知所给集合 A 和 B,求 A B 的差集 C(C=A-B) *离散数学中的简单的集合运算,代码由C语言编写,思路...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 143,976
精华内容 57,590
关键字:

交且与差