蓝桥杯数据压缩

【题目描述 - Problem Description】

某工业监控设备不断发回采样数据。每个数据是一个整数(0到1000之间)。各个数据间用空白字符（空格，TAB或回车换行）分隔。
这些数据以文本形式被存储在文件中。
因为大多数时候，相邻的采样间隔数据是相同的，可以利用这个特征做数据的压缩存储。

其方法是：
　　对n(n>1)个连续相同的数字只记录n和该数字本身；
　　对m(m>0)个连续不重复的数字，则记录 m*-1 和这些数字本身（之所以用负数，是为了与第一种情况区分，便于解压缩）。
例如：采样数字：
12 34 34 25 25 25 25 11 15 17 28 14 22 22 22 13
则根据上述规则变化后：
-1 12 2 34 4 25 -5 11 15 17 28 14 3 22 -1 13
下面的程序实现了这个功能。请仔细阅读分析代码，填写空白的部分。

  1 void pop(int s, int* buf, int c, FILE* fp)
  2 {
  3     int i;
  4     if (s)
  5     {
  6         fprintf(fp, "%d %d ", c, *buf);
  7     }
  8     else
  9     {
 10         fprintf(fp, "%d ", -c);
 11         for (i = 0; i < c; i++)
 12         {
 13             fprintf(fp, "%d ", buf[i]);
 14         }
 15     }
 16 }
 17 
 18 void dopack(FILE* r, FILE* w)
 19 {
 20     int buf[BUF_N];
 21 
 22     int pos = 0;  // 下一个数字在buf中将要存放的位置
 23     int c = 0;    // 当前段已读入的整数个数
 24     int pst;
 25     int cst;
 26 
 27     while (fscanf(r, "%d", buf + pos) == 1)
 28     {
 29         if (c == 0)
 30         {
 31             c = pos = 1;
 32             continue;
 33         }
 34 
 35         if (c == 1)
 36         {
 37             pst = buf[0] == buf[1];
 38             pos = pos + 1 - pst;
 39             c = 2;
 40             continue;
 41         }
 42 
 43         cst = buf[pos - 1] == buf[pos];
 44         if (pst && !cst)
 45         {
 46             pop(pst, buf, c, w);
 47             buf[0] = buf[1];
 48             c = pos = 1;
 49             pst = cst;
 50         }
 51         else if (!pst && cst || pos == BUF_N - 1)
 52         {
 53             pop(pst, buf, c - 1, w);
 54             buf[0] = buf[pos - 1];
 55             c = 2;
 56 
 57             if (!cst)
 58             {
 59                 buf[1] = buf[pos];
 60                 pos = 2;
 61             }
 62             else
 63             {
 64                 pos = 1;
 65                 pst = ______________;  // 填空1
 66             }
 67         }
 68         else
 69         {
 70             c++;
 71             if (!pst) pos++;
 72         }
 73     } // while
 74 
 75     if (c > 0) _____________________________;   // 填空2
 76 }
 77 
 78 void main()
 79 {
 80     FILE* rfp;
 81     FILE* wfp;
 82 
 83     if ((rfp = fopen(RFILE, "r")) == NULL)
 84     {
 85         printf("can not open %s!
", RFILE);
 86         exit(1);
 87     }
 88 
 89     if ((wfp = fopen(WFILE, "w")) == NULL)
 90     {
 91         printf("can not open %s!
", WFILE);
 92         fclose(rfp);
 93         exit(2);
 94     }
 95 
 96     dopack(rfp, wfp);
 97 
 98     fclose(wfp);
 99     fclose(rfp);
100 }

代码

【题解】

　　一开始百度找到题目代码都是没有头文件和宏定义的，乍看之下还以为自己碰到了假的代码。后来又比对了几个博客的题目大概确定应该就是这样没错了。直接return用多的人都不知道exit()在哪个头文件里了……原来是cstdlib…………

　　两个填空部分都是放在一个模块里了，代码量不多，直接照着模块里的代码人肉模拟即可…… 具体感觉没什么好分析了，备注直接写在代码里。

【最终结果】

1 或 cst
pop(pst, buf, c, w)

【代码 C++】

  1 #include <cstdio>
  2 #include <cstdlib>
  3 #define BUF_N 1000
  4 #define RFILE "1.txt"
  5 #define WFILE "CON"
  6 void pop(int s, int* buf, int c, FILE* fp)
  7 {
  8     int i;
  9     if (s)
 10     {
 11         fprintf(fp, "%d %d ", c, *buf);
 12     }
 13     else
 14     {
 15         fprintf(fp, "%d ", -c);
 16         for (i = 0; i<c; i++)
 17         {
 18             fprintf(fp, "%d ", buf[i]);
 19         }
 20     }
 21 }
 22 
 23 void dopack(FILE* r, FILE* w)
 24 {
 25     int buf[BUF_N];
 26 
 27     int pos = 0;  // 下一个数字在buf中将要存放的位置
 28     int c = 0;    // 当前段已读入的整数个数
 29     int pst;//-------初始状态标记
 30     int cst;//-------下次状态标记
 31 
 32     while (fscanf(r, "%d", buf + pos) == 1)
 33     {
 34         if (c == 0){//-----------------------第一个数，直接写入buf
 35             c = pos = 1;
 36             continue;
 37         }
 38 
 39         if (c == 1)//------------------------第二个数，更新初始状态
 40         {
 41             pst = buf[0] == buf[1];////判断是否重复   0不重复  1重复
 42             pos = pos + 1 - pst;
 43             c = 2;
 44             continue;
 45         }
 46         //-----------------------------------第三个数及其以后
 47         cst = buf[pos - 1] == buf[pos];////获得下次状态标记
 48         if (pst && !cst)//-------------------重复->不重复
 49         {
 50             pop(pst, buf, c, w);
 51             buf[0] = buf[1];////buf={x, y} -> buf={y}
 52             c = pos = 1;
 53             pst = cst;////恰好读取最后一个数时，防止状态没刷新
 54         }
 55         else if (!pst && cst || pos == BUF_N - 1)//----(不重复 -> 重复) || 满了
 56         {
 57             pop(pst, buf, c - 1, w);
 58             buf[0] = buf[pos - 1];
 59             c = 2;
 60 
 61             if (!cst)//-------------------------------不重复 的满了
 62             {
 63                 buf[1] = buf[pos];
 64                 pos = 2;
 65             }
 66             else//------------------------------------不重复 -> 重复
 67             {
 68                 pos = 1;
 69                 //pst = ______________;  // 填空1
 70                 pst = 1;//pst = cst;//也行，就是刷新状态
 71             }
 72         }
 73         else
 74         {
 75             c++;
 76             if (!pst) pos++;
 77         }
 78     } // while
 79 
 80     if (c > 0) //_____________________________;   // 填空2
 81         pop(pst, buf, c, w);////扫尾，最后清场
 82 }
 83 
 84 void main()
 85 {
 86     FILE* rfp;
 87     FILE* wfp;
 88 
 89     if ((rfp = fopen(RFILE, "r")) == NULL)
 90     {
 91         printf("can not open %s!
", RFILE);
 92         exit(1);
 93     }
 94 
 95     if ((wfp = fopen(WFILE, "w")) == NULL)
 96     {
 97         printf("can not open %s!
", WFILE);
 98         fclose(rfp);
 99         exit(2);
100     }
101 
102     dopack(rfp, wfp);
103 
104     fclose(wfp);
105     fclose(rfp);
106 }

蓝桥杯 数据压缩

蓝桥杯数据压缩