行程长度编码

发布时间:2024年01月15日

前言

NWAFU 2023阶段二 A


一、题目描述

题目描述

“行程长度编码(Run-Length Encoding,RLE)”是一种无损压缩编码方法,其核心思想是依次记录符号序列中的每个字符(忽略大小写)及其重复出现的次数。例如用户输入字符序列(字符串)AaABBBbCBB,则其RLE编码的结果为3A4B1C2B。
下面的代码实现对输入字符串的RLE编码,现要求在函数int rle(char *code, const char *seq);及函数readSeq(char *seq, int n);定义中的五个空白处填充适当的表达式,完成程序功能。
其中:rle()函数形参seq为长度在(0, 80]间(strlen(seq)>0&&strlen(seq)≤80)的全部由大小写英文字母组成的字符串指针,形参code为RLE编码后的结果字符串指针。编码正常结束函数返回0;如字符串指针seq为空或字符串长度不合法时,不进行编码函数直接返回-1;当字符串seq中出现非英文字母的其他字符时,也不进行编码函数直接返回-2。
readSeq()从键盘读取最多n个字符到seq字符串中,以回车符或EOF字符为结束标志。
请使用wget从http://202.117.179.201/attach/P1551.c获取需要填空的代码。完成设计rle()、readSeq()等函数,并在本地完成测试后,仅提交rle()、readSeq()函数及其调用的自定义函数的实现代码

#include <stdio.h>
#include <string.h>

#define MAX_SEQ_LEN 80

int rle(char *code, const char *seq);
int readSeq(char *seq, int n);

int main()
{
    char seq[MAX_SEQ_LEN + 1] = { 0 };
    char code[2 * MAX_SEQ_LEN + 1];
    int r;

    readSeq(seq, MAX_SEQ_LEN);
    r = rle(code, seq);
    switch (r) {
    case 0:
        printf("%s\n", code);
        break;
    case -1:
        printf("Length is inValid.\n");
        break;
    case -2:
        printf("Has inValid character.\n");
        break;
    }
    return 0;
}
/* 以上代码禁止提交 */
int readSeq(char *seq, int n)
{
    int ch, k;
    k = 0;

    while ((ch = getchar())) {
        if (__________(1)_________)
            break;
        seq[k++] = ch;
    }

    _____(2)______;
    return k;
}

int rle(char *code, const char *seq)
{
    int i, len = 0;
    char *p;

    if (__________(3)____________)
        return -1;
    p = (char *)seq;
    len = 0;
    while (____(4)____) {
        char token = *p;
        i = 1;
        token &= 0xDF;
        if (token > 'Z' || token < 'A')
            return -2;
        while (_________(5)__________) {
            i++;
        }
        len = sprintf(code, "%d%c", i, token);
        code += len;
    }
    *code = '\0';
    return 0;
}
样例输入
KAAAEE
样例输出
1K3A2E

二、设计步骤

分析程序结构,通过readSeq函数读入seq字符串,在rle函数中对字符串编码并将结果输出到code中。

readSeq函数与我们日常使用的s_gets()和Readline()完全相同,考查读入条件和在结尾添加空字符,在此不再赘述。

rle函数为该程序核心块。我们在解决问题“删除子串”时为了避免破坏原串,对原串进行了一次拷贝,然后在其拷贝上进行操作。而这个函数在对字符串进行操作时用了一个巧妙的方法:它定义了一个指针常量p(注:指针常量不能修改地址指向的,但可以修改指针指向的地址)并将seq的首地址赋给p,通过再循环内对p自增实现遍历操作,有效保证了程序稳定并避免了内存的浪费。

因此如何对p进行合理的自增操作便成为了一个难点。p在每个外层while循环里的的自增长度取决于 i,而 i 的初始化是在循环内完成的,显然不能在(4)中进行此操作。因此我们将p自增语句填在(5)中,同时加上一个判断条件(这里不熟悉 & 0xDF 的同学可以复习一下位运算)。

调试过程中出现的运行错误是忽略了seq为NULL的情况,在这种情形下,我们如果没有在rle函数循环开始前剔除它,那么在把seq的首地址赋给p后,p在第二个while循环中会进行一次自增,此时p就会访问一处未经声明的空间,出现运行错误。

题解:

int readSeq(char *seq, int n)
{
    int ch, k;
    k = 0;
 
    while ((ch = getchar()))
    {                    
        if (k == n || ch =='\n' || ch == EOF)   //(1)   
             break;
        seq[k++] = ch;
    }
    seq[k] = '\0';        //(2)
    return k;
}

int rle(char *code, const char *seq)
{
    int i, len = 0;
    const char *p;
 
    if (seq == NULL || strlen(seq) == 0 || strlen(seq) > 80)      //(3)
        return -1;
    p = seq;
    len = 0;
    while (*p)                                        //(4)
    {
        char token = *p;
        i = 1;
        token &= 0xDF;
        if (token > 'Z' || token < 'A')
            return -2;
        while (*++p && (*p & 0xDF) == token)         //(5)
        {
            i++;
        }
        len = sprintf(code, "%d%c", i, token);
        code += len;
    }
    *code = '\0';
    return 0;
}

欢迎在评论区讨论!?


总结

NWAFU 2023阶段二 A

文章来源:https://blog.csdn.net/2301_79520789/article/details/135584062
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。