KWIC-C/C++实现

吐槽

最近我们 JavaJava 老师不知道为啥非要我用 C/C++C/C++ 来实现 KWICKWIC,但是因为没有上过课,不知道这个东西是干嘛的,所以想网上 downloaddownload 一下,然而,百度后发现,实在是没有什么能看的过眼的代码,修改他们的代码难度比自己写要大好多,于是,决定找一下定义自己动手实现一下。

描述

KWICKWIC 索引系统接受一些行,每行有若干字,每个字由若干字符组成;每行都可以循环移位,亦即重复地把第一个字删除,然后接到行末;KWICKWIC 把所有行的各种移位情况按照字母表顺序输出。

分析

上述关于 KWICKWIC 的描述猛一看有些懵逼,因为并不知道这样做有啥子卵用,这种操作到底有啥存在的价值呢?为什么那么多软件设计课程要把他定为课堂讲义的经典呢?这些都不得而知了,为了让自己更好的理解,我找到了一个比较好的图解。

看到这里的样例,我想应该很容易理解了,首先按照行来读取,每行由若干单词组成,然后将所有行所有的可能移位结果放在一起进行排序,最后输出即可。需求很简单,不过这里的排序我并没有搞清楚具体什么排序规则……于是我就简操作,略微偷个懒,直接按照所有移位结果的单词的字典序进行比较,不考虑空格,考虑大小写的区别。代码很简单,区区一百行足矣,实在是搞不懂网上的那些大佬们为毛子要用二三百行来实现……

代码

#include <iostream>
#include <cstring>
#include <vector>

using namespace std;

struct line
{
    vector<string> vs;
} L;

vector<line> vl;

struct words
{
    int vl_pos, vs_pos;
};

vector<words> vw;

bool cmp(const words &a, const words &b)
{
    line La, Lb;
    for (int i = a.vs_pos; i < vl[a.vl_pos].vs.size(); i++)
    {
        La.vs.push_back(vl[a.vl_pos].vs[i]);
    }
    for (int i = 0; i < a.vs_pos; i++)
    {
        La.vs.push_back(vl[a.vl_pos].vs[i]);
    }

    for (int i = b.vs_pos; i < vl[b.vl_pos].vs.size(); i++)
    {
        Lb.vs.push_back(vl[b.vl_pos].vs[i]);
    }
    for (int i = 0; i < b.vs_pos; i++)
    {
        Lb.vs.push_back(vl[b.vl_pos].vs[i]);
    }

    int len = min((int)La.vs.size(), (int)Lb.vs.size());
    for (int i = 0; i < len; i++)
    {
        if (La.vs[i] != Lb.vs[i])
        {
            return La.vs[i] < Lb.vs[i];
        }
    }

    return La.vs.size() < Lb.vs.size();
}

string word;

int main()
{
    while (cin >> word)
    {
        L.vs.push_back(word);
        if (getchar() == '\n')
        {
            vl.push_back(L);
            L.vs.clear();   //  此处可以优化
        }
    }

    for (int i = 0; i < vl.size(); i++)
    {
        for (int j = 0; j < vl[i].vs.size(); j++)
        {
            vw.push_back({i, j});
        }
    }

    sort(vw.begin(), vw.end(), cmp);

    for (int i = 0; i < vw.size(); i++)
    {
        int vl_pos = vw[i].vl_pos, vs_pos = vw[i].vs_pos;
        int vs_sz = (int)vl[vw[i].vl_pos].vs.size(), c = 0;
        for (int j = vs_pos; j < vs_sz; j++)
        {
            c++;
            cout << vl[vl_pos].vs[j] << (c == vs_sz ? '\n' : ' ');
        }
        for (int j = 0; j < vs_pos; j++)
        {
            c++;
            cout << vl[vl_pos].vs[j] << (c == vs_sz ? '\n' : ' ');
        }
    }

    return 0;
}

测试

按照上述图解里的样例进行测试,测试结果正确。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏java一日一条

重构 改善既有代码的设计--笔记

查看一个类是否“过大”,这里有一个小技巧分享给大家。就是看两点:1)这个类实例变量太多,必然会有Duplicated Code(重复代码) 2)类内如果有太多代...

1084
来自专栏码洞

编程的智慧

编程是一种创造性的工作,是一门艺术。精通任何一门艺术,都需要很多的练习和领悟,所以这里提出的“智慧”,并不是号称一天瘦十斤的减肥药,它并不能代替你自己的勤奋。然...

571
来自专栏java一日一条

哪些因素影响Java调用的性能?

这得从一个小故事说起。我在一个Java核心库的邮件列表中提交了一个修改 ——重写了一些本是 final 的方法。一石激起千层浪,这一改动引发了几番讨论。而其中一...

1111
来自专栏编程

浅谈Java学习方法和后期面试技巧 含学习笔记

下面简单列举一下大家学习java的一个系统知识点的一些介绍: 一、java基础部分:java基础的时候,有些知识点是非常重要的,比如循环系列。For,while...

2008
来自专栏Java帮帮-微信公众号-技术文章全总结

Java基础-day05-超市收银系统案例题

Java基础-day05-超市收银系统案例题 案例描述 将超市购物小票案例中,键盘录入部分封装为方法。 将switch语句完成的三个分支代码逻辑封装为3个方法 ...

5474
来自专栏阿杜的世界

《重构》阅读笔记-代码的坏味道

开发者必须通过实践培养自己的经验和直觉,培养出自己的判断力:学会判断一个类内有多少个实例变量算是太大、学会判断一个函数内有多少行代码才算太长。

742
来自专栏Java技术栈

跟我学 Java 8 新特性之 Stream 流(四)并行流

在开始讨论并行流之前,我先引发一下大家的思考,就你看到这篇文章的时间,你们是不是经常听到,Intel i7 CPU什么8核16线程,什么Android手机8核4...

902
来自专栏编程

Java 最困扰你的那些事

啊哈Reddit(某知名国外在线问答社区),没了你我们还能在哪里从鱼目混珠的网络中提炼真正的精华?就在这杂乱无章的论坛中,的的确确存在着这样一些精辟的讨论。 比...

2088
来自专栏Albert陈凯

2018-11-08 杀死If Else switch case(策略模式+工厂模式+map)套餐 Kill 项目中的switch case

为了便于理解,举个没有业务逻辑的例子,基于这个例子上进行优化。 现在是12:47,举个饭后吃水果的例子哈哈哈(逃 假设我们可以选择的水果有香蕉、西瓜和苹果。吃香...

1453
来自专栏C语言及其他语言

C语言中的宏陷阱 #define SQU(x) x*x

有同学写过或者想写这样的宏定义吗? 求两个或几个数的乘积: #define SQU(x) x*x 我们正常使用没有问题: ? 但如果这样写呢? ? 哎呀,...

3785

扫码关注云+社区

领取腾讯云代金券