行程长度编码

前言

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