V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
NullMan
V2EX  ›  C

C 语言题目,造轮子,看谁的轮子最厉害,有牛奶奖励。

  •  
  •   NullMan · 2017-06-22 03:14:00 +08:00 · 4781 次点击
    这是一个创建于 2707 天前的主题,其中的信息可能已经有所发展或是发生改变。

    题目:

    从字符串删除特定子字符串。

    条件

    • 不能使用任何函数。
    • 不能用数组下标。
    • 除去函数参数,函数内使用的变量不能超过 2 个。

    这题目是从“ C 和 指针”这书看到的,条件三是我自己添加的。

    函数原型:

    void del_substr(char *str, const char *substr);
    

    举例:

    char str[] = "ABCDEFG";
    char substr[] = "CDE";
    del_substr(str, substr);
    
    这个时候,str 的值就应该是"ABFG"。
    如果 substr 为 “ CDG ”, 执行该函数,str 保持不变("ABCDEFG")
    

    实现:

    以下代码乃本人所写,虽然刚学 C, 但是仍然对此代码不满意,代码行数太多了,太绕了,不直接。直觉告诉我,还可以写得更精简。望各位赐教一下,多谢!

    void del_substr(char *str, const char *substr) {
        int i = 0, j = 0;
        while (*(str+i)) {
            j = 0;
            while (*(substr+j) && *(substr+j) == *(str+i+j)) {
                j++;
            }
            if (! *(substr+j)) {
                break;
            }
            else {
                i++;
            }
        }
        if (! *(substr+j)) {
            while ((*(str+i) = *(str+i+j))) {
                i++;
            }
        }
    }
    

    奖励:

    代码写得最简单,最精炼, 我请你喝牛奶。:)

    第 1 条附言  ·  2017-06-22 18:29:25 +08:00
    个人认为 #34 楼的 @yangff 写得最牛逼!感谢各位的踊跃!感谢!
    46 条回复    2017-06-22 21:12:57 +08:00
    XYxe
        1
    XYxe  
       2017-06-22 03:18:52 +08:00 via Android
    i,j 和下标没有什么区别啊,换成对应的指针更好一点
    kyuuseiryuu
        2
    kyuuseiryuu  
       2017-06-22 03:21:04 +08:00 via Android   ❤️ 1
    markdown 也是刚学的吧。
    NullMan
        3
    NullMan  
    OP
       2017-06-22 03:24:15 +08:00
    @kyuuseiryuu 哈哈!你是怎么看出来的?
    NullMan
        4
    NullMan  
    OP
       2017-06-22 03:26:39 +08:00
    @XYxe 是的,没什么区别。但是我想不出一个变量都不用还能保持简单的写法。
    kyuuseiryuu
        5
    kyuuseiryuu  
       2017-06-22 03:29:23 +08:00 via Android
    @NullMan 代码块用行内代码表示了。正确做法是三个反引号开头跟上语言名称,回车接代码块,回车接三个反引号结束。
    NullMan
        6
    NullMan  
    OP
       2017-06-22 03:32:08 +08:00
    @kyuuseiryuu 我就是这么写的呀。不过我选的是 bash。
    kyuuseiryuu
        7
    kyuuseiryuu  
       2017-06-22 03:37:10 +08:00 via Android
    @NullMan 这就很尴尬了,果然。我用浏览器看就没问题,客户端就变成行内代码的样式了。哇~我要找个地洞钻进去!快,帮我挖个洞~逃~
    yangff
        8
    yangff  
       2017-06-22 03:55:42 +08:00
    yangff
        9
    yangff  
       2017-06-22 04:11:43 +08:00
    RqPS6rhmP3Nyn3Tm
        10
    RqPS6rhmP3Nyn3Tm  
       2017-06-22 04:37:59 +08:00 via iPad   ❤️ 2
    Void main {
    Printf("九评 xxx");
    Return 0;
    }

    真 轮子
    geelaw
        11
    geelaw  
       2017-06-22 04:58:47 +08:00
    ```c
    /* 删除所有的匹配 */
    void del_substr(char *str, char const *pattern)
    {
    char const *copy = str;
    int match;
    if (!str || !pattern || !*pattern)
    return;
    while (*copy)
    {
    for (match = 0; copy[match] && copy[match] == pattern[match]; ++match)
    ;
    if (pattern[match]) *str++ = *copy++;
    else copy += match;
    }
    *str = 0;
    }
    ```

    懒得验证了

    限制于空间要求,没法写更聪明的代码,这个算法非常地慢
    geelaw
        12
    geelaw  
       2017-06-22 04:59:54 +08:00
    另外没有理解“请你喝牛奶”是什么玩意儿
    geelaw
        13
    geelaw  
       2017-06-22 05:06:50 +08:00
    如果你只要删除第一个匹配,可以只用一个 explicit 变量,用一个 int 作为匹配长度的记录,当找到匹配的时候,循环利用 pattern 指针作为复制源位置即可。
    V3EX17
        14
    V3EX17  
       2017-06-22 07:39:19 +08:00 via iPhone
    @BXIA 返回值不应该有吧😄
    headmaster
        15
    headmaster  
       2017-06-22 07:52:44 +08:00 via iPhone
    Mark,到了公司写一个
    nutting
        16
    nutting  
       2017-06-22 08:56:16 +08:00
    喝牛奶,听起来有点邪恶
    koebehshian
        17
    koebehshian  
       2017-06-22 09:14:13 +08:00
    不能使用下标但却可以使用解引用,这两者没什么区别
    nvmhi
        18
    nvmhi  
       2017-06-22 09:18:49 +08:00
    @nutting 抓住一名怪蜀黍
    headmaster
        19
    headmaster  
       2017-06-22 09:28:44 +08:00 via iPhone
    @NullMan 想了一下,你要的应该就是 BM 算法🙈
    azh7138m
        20
    azh7138m  
       2017-06-22 09:35:42 +08:00 via Android
    搞个 int64 当俩 int32 是不是也行?最后这个条件没啥意思呐;不让用数组下标是真的滑稽:)
    bp0
        21
    bp0  
       2017-06-22 09:36:25 +08:00 via Android
    循环找到子串的起始和结束位置,

    找到起始和结束位置,则复制结束位置后面剩余的字符串即可。

    如果没有剩余字符,直接在起始位置置 0。
    bp0
        22
    bp0  
       2017-06-22 10:10:18 +08:00
    '''c
    void del_substr(char *str, const char *substr)
    {
    char *end;
    const char *rawsub;

    if (!str || !substr || !*substr)
    return ;

    end = str;
    rawsub = substr;
    while (*str) {
    if (!*substr) {
    while ( *str++ = *end++);
    } else if (*str == *substr) {
    end++;
    substr++;
    } else {
    end = ++str;
    substr = rawsub;
    }
    }
    }

    '''

    没经过测试,楼主有兴趣可以测试一下。

    另外,这个代码只能删除第一个符合要求的字串。如果要删除所有字串还需要再调整一下 while 中第一个 if 的内容。
    ryd994
        23
    ryd994  
       2017-06-22 10:15:01 +08:00
    不能使用数组下标这个要求说明出题的根本不懂 C
    C 标准规定了 arr[i] 和 *(arr+i) 必须完全等效
    bp0
        24
    bp0  
       2017-06-22 10:22:08 +08:00 via Android
    @ryd994 问题的特殊性导致,不用下标也是可以完成题目要求的。这和 are[i]和*(arr+i)是不是等效没有关系。楼主用*(arr+i),本质上就是用下标。
    misaka20038numbe
        25
    misaka20038numbe  
       2017-06-22 10:37:11 +08:00
    @bp0 经过测试,楼主和 11 楼的可以,你的不行.执行完后还是 ABCDEFG
    besto
        26
    besto  
       2017-06-22 10:39:33 +08:00
    既然看了 C 和指针,那就应该看看 C 专家编程,你的要求最后一点压根不是事情(既可以考虑位段来做,也可以考虑用位移来做,压缩变量呗)

    另外同意楼上。不然还可以写 i[arr]也完全等效。。。
    coderluan
        27
    coderluan  
       2017-06-22 11:49:26 +08:00
    严格说这个不是轮子吧,OJ 题而已,还是水题,要比也得比执行速度啊啊,想代码简单别用 C 多好。

    PS:喝牛奶是啥?
    bp0
        28
    bp0  
       2017-06-22 11:51:12 +08:00
    @misaka20038numbe 谢谢帮忙测试,更新了一下代码。这次应该没有问题了。


    ```c

    void del_substr(char *str, const char *substr)
    {
    char *end;
    const char *rawsub;

    if (!str || !substr || !*substr)
    return ;

    end = str;
    rawsub = substr;
    while (*str) {
    if (!*substr) {
    while ((*str++ = *end++));
    break;
    } else if (*end == *substr) {
    end++;
    substr++;
    } else {
    end = ++str;
    substr = rawsub;
    }
    }
    }

    ```
    yangff
        29
    yangff  
       2017-06-22 11:55:41 +08:00 via Android
    @livid 为什么我在这个帖子的回复没有出现在我自己的回复列表里。。?

    这个帖子有啥特殊的吗
    bp0
        30
    bp0  
       2017-06-22 12:41:58 +08:00
    @yangff 确实没有,貌似应该是 @Livid
    araraloren
        31
    araraloren  
       2017-06-22 15:03:23 +08:00
    @yangff 有时候别人 AT 我一样没有提示。。
    deeporist
        32
    deeporist  
       2017-06-22 15:45:57 +08:00
    嗯 之前学 scheme 时遇到过这种题目 等自己用 C 写起来才发现 难怪说 lisp 是专门针对 list 的了 一个 cdr 就能搞定这之后的千千万 c 的话还得自己往后一个一个接回去 痛苦
    ```
    # include <stdio.h>
    char str[]="ABCDEFG";
    char substr[]="CDE";
    void del_substr(char *,char *);
    int i,j;
    int main()
    {
    i=(int)sizeof(str);
    j=(int)sizeof(substr);
    del_substr(str,substr);
    printf("%s",str);
    return 0;
    }

    void del_substr(char *ori,char *tar)
    {
    if(j==1)
    {
    j=((int)sizeof(substr))-1;
    while((i--)>1)
    {*(ori-j)=*(ori);ori++;}
    *(ori-j)='\0';
    j=1;
    }

    if((*ori)==(*tar))
    {
    i--;j--;
    del_substr(ori+1,tar+1);
    }

    if(--i>1)
    del_substr(ori+1,tar);

    }

    ```

    两个变量 i j 纯粹当作计数器 sizeof 算是操作符 主要以递归形式循环

    md 就这辣鸡问题我居然还从上午折腾到现在 菜得让自己吃惊
    cnfreesw
        33
    cnfreesw  
       2017-06-22 15:46:12 +08:00
    牛奶,桶装还是试管装?
    yangff
        34
    yangff  
       2017-06-22 16:27:25 +08:00
    感觉第二种写法还是比较有潜力的
    https://gist.github.com/Yangff/f9944276a72acb3808968a2b64139db0
    最终版(大概)
    ShiHou
        35
    ShiHou  
       2017-06-22 17:03:27 +08:00
    吐槽下.. 这题写短的精髓应该是仅用一层循环而不是死命缩变量名
    JohnSmith
        36
    JohnSmith  
       2017-06-22 17:13:16 +08:00
    效率最高的是 kmp 算法
    yangff
        37
    yangff  
       2017-06-22 17:27:25 +08:00
    @ShiHou 既然你这么说的话… PlanB 的压行版(虽然我觉得这种压法还不如写两行…)

    for (int i = 0, j = 0; *str = *(str+i); (*(str+i+j) == *(substr+j) && *(substr+j)) ? (j++) : (i += !*(substr+j) * j, str += !!*(substr+j), j = 0));
    lzhCoooder
        38
    lzhCoooder  
       2017-06-22 18:04:36 +08:00
    你这么搞基本没意义,想造轮子就写个“看毛片”吧
    headmaster
        39
    headmaster  
       2017-06-22 18:23:32 +08:00 via iPhone
    @JohnSmith KMP 没有 BM 效率高吧
    NullMan
        40
    NullMan  
    OP
       2017-06-22 18:28:31 +08:00
    @yangff #34 卧槽!你这写法老牛逼了,我的只能删除第一个子字符串,你这是全都能删除!就是你了!留下收款账号,给你红包请你喝盒装牛奶,我比较穷,请不起咖啡:)
    yangff
        41
    yangff  
       2017-06-22 18:29:46 +08:00
    @NullMan eWFuZ2ZmMUBnbWFpbC5jb20=

    谢啦 w
    NullMan
        42
    NullMan  
    OP
       2017-06-22 18:31:12 +08:00
    @deeporist 听你这么一说,我就欣慰了,我可写了 2 个小时,1.5 小时在脑子里写,0.5 小时上机写,我都认为自己太菜了。
    NullMan
        43
    NullMan  
    OP
       2017-06-22 18:36:08 +08:00   ❤️ 1
    @yangff 支付宝转给你啦。
    Actrace
        44
    Actrace  
       2017-06-22 20:58:40 +08:00
    高级语言代码最重要的目的是要让人能看懂的同时让机器也能懂。
    不知各位往死里运用各种缩减有啥意义。
    lrxiao
        45
    lrxiao  
       2017-06-22 21:11:16 +08:00
    GOLF 娱乐吗..
    yangff
        46
    yangff  
       2017-06-22 21:12:57 +08:00
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   2635 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 29ms · UTC 15:45 · PVG 23:45 · LAX 07:45 · JFK 10:45
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.