标题:北理工习题
只看楼主
蒟蒻
Rank: 1
等 级:新手上路
帖 子:20
专家分:0
注 册:2019-11-11
结帖率:71.43%
已结贴  问题点数:20 回复次数:6 
北理工习题
压缩是一种有效的减小数据量的方法,目前已经被广泛应用于各种类型的信息系统之中。

    一种压缩文本文件(假设文件中不包含数字)的方法如下:

    1. 原始文本文件中的非字母的字符,直接拷贝到压缩文件中;

    2. 原始文件中的词(全部由字母组成),如果是第一次出现,则将该词加入到一个词的列表中,并拷贝到压缩文件中;否则该词不拷贝到压缩文件中,而是将该词在词的列表中的位置拷贝到压缩文件中。

    3. 词的列表的起始位置为 1 。 词的定义为文本中由大小写字母组成的最大序列。大写字母和小写字母认为是不同的字母,即 abc 和 Abc 是不同的词。词的例子如下: x-ray 包括两个词 x 和 ray;mary's 包括两个词 mary 和 s;a c-Dec 包括三个词 a 和 c 和 Dec 编写一个程序,输入为一组字符串,输出为压缩后的文本。

输入:

    输入为一段文本,可以假设输入中不会出现数字、每行的长度不会超过 80 个字符,并且输入文本的大小不会超过 10M。

输出:

压缩后的文本。
   代码尽量写得易懂,谢谢!
搜索更多相关主题的帖子: 压缩 字母 文本 输入 文件 
2019-11-25 17:00
rjsp
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
等 级:版主
威 望:507
帖 子:8890
专家分:53117
注 册:2011-1-18
得分:20 
我只想问问,是原题就没有“样例输入输出”呐,还是你不肯贴“样例输入输出”?
2019-11-25 17:09
蒟蒻
Rank: 1
等 级:新手上路
帖 子:20
专家分:0
注 册:2019-11-11
得分:0 
回复 2楼 rjsp
输入:
    Please, please do it--it would please Mary very,↵
    very much.↵
    ↵
    Thanks↵
输出:
    Please, please do it--4 would 2 Mary very,↵
    7 much.↵
    ↵
    Thanks↵
2019-11-26 15:11
rjsp
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
等 级:版主
威 望:507
帖 子:8890
专家分:53117
注 册:2011-1-18
得分:0 
每行的长度不会超过 80 个字符,并且输入文本的大小不会超过 10M。
每行的长度不会超过80个字符,那么也就是说单词最大长度是80;
文本的大小不会超过10M,假设4个字母一行,那么有 10M/(4+1) = 2M 行;
4个字母最多有 52^4=7311616=6.97M 种不同的可能
也就是说为了记录不同的单词,就至少需要 2M*80 的内存。
不是不可以写,而是题目缺少限定,如果严格按照题目来做,不但费时费力还运行时间过长,被老师打个最低分;若不按题目要求来做,那就只能瞎猜,没意义。

2019-11-26 16:19
rjsp
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
等 级:版主
威 望:507
帖 子:8890
专家分:53117
注 册:2011-1-18
得分:0 
搭个C语言的框架吧
程序代码:
#include <stdio.h>
#include <stdlib.h>

int main( void )
{
    char* buf = (char*)malloc( 10485760+1 ); // 题目限制“输入文本的大小不会超过 10M”
    int len;
    scanf( "%10485760c%n", buf, &len );
    buf[len] = '\0';

    void foo( const char* );
    foo( buf );

    free( buf );
}

void foo( const char* s )
{
    for( ; ; )
    {
        int len = 0;
        int n = sscanf(s,"%*[^A-Za-z]%n",&len);
        if( n == EOF )
            break;
        fwrite( s, 1, len, stdout );
        s += len;

        len = 0;
        n = sscanf(s,"%*[A-Za-z]%n",&len);
        if( n == EOF )
            break;
        fwrite( s, 1, len, stdout ); // 这个地方改为查找 s(长度len) 是否存在,若不存在……,若存在……
        s += len;
    }
}

2019-11-26 16:35
rjsp
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
等 级:版主
威 望:507
帖 子:8890
专家分:53117
注 册:2011-1-18
得分:0 
用 C++语言 写了一个

程序代码:
#include <iostream>
#include <iterator>
#include <string>
#include <unordered_map>
#include <algorithm>
using namespace std;

class foo
{
public:
    void operator()( const char* s )
    {
        for( ; ; )
        {
            int len = 0;
            int n = sscanf(s,"%*[^A-Za-z]%n",&len);
            if( n == EOF )
                break;
            fwrite( s, 1, len, stdout );
            s += len;

            len = 0;
            n = sscanf(s,"%*[A-Za-z]%n",&len);
            if( n == EOF )
                break;
            {
                std::string word(s,len);
                auto itor = hashtable.find(word);
                if( itor == hashtable.end() )
                {
                    hashtable.insert( std::make_pair(word,hashtable.size()+1) );
                    fwrite( s, 1, len, stdout );
                }
                else
                {
                    fputs( to_string(itor->second).c_str(), stdout );
                }
            }
            s += len;
        }
    }
private:
    unordered_map<string,unsigned> hashtable;
};

int main( void )
{
    string s;
    s.reserve( 10*1024*1024 );
    copy( std::istreambuf_iterator<char>(cin), std::istreambuf_iterator<char>(), std::back_inserter(s) );

    foo()( s.c_str() );
}

2019-11-26 17:11
rjsp
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
等 级:版主
威 望:507
帖 子:8890
专家分:53117
注 册:2011-1-18
得分:0 
回复 6楼 rjsp
代码还可以改进,完全不需要存储 string,可以直接用 string_view
2019-11-26 17:14



参与讨论请移步原网站贴子:https://bbs.bccn.net/thread-498072-1-1.html




关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.063345 second(s), 8 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved