Uva-213-Message Decoding

叨叨叨：

  给你一串编码头，和几段编码，根据编码头来翻译成编码的内容。（话说这好像是格雷码，数字逻辑有学过）

  初期没有思路（还是犯了一个老毛病，就是不会运用即时输入输出，而是总想着先把输入用某种数据结构全部保存下来，然后整体做处理，再输出，结果没有一点思路）。

第一部分：编码头的读取与处理

  首先是编码头，因为和二进制扯上关系了，题目中说每个编码的最大二进制数不超过八，所需数据不多，所以先用打表法记录每个编码。我们定义一个二维数组 code[8][1<<8] ，第一个维度保存二进制长度，第二个维度保存该长度下的value。(ps:第二个维度会有很多的浪费，但是考虑到二进制长度有可能为八的情况，即会有编码头数达到最大2^8-1个，所以只能这样了。将此部分定义在函数 int make_head() 中，其中对于return 0 和return 1 的位置 有文章，需要仔细了解一下。

第二部分：输入密码的过滤‘\n’、'\r' 问题

  因为题目要求，只有输入000，才会结束本次密码的输入，所以遇到 ‘\n’ 和  '\r' 的话，必须得继续往下读，如何消除换行的影响，紫书中给出这段代码：

int readchar()
{	
	while (true)
	{
		int ch = getchar();
		if (ch != '\n' && ch != '\r')	return ch;

	}
}

还有其他方法：

int readchar()
{
	int c;
	while (( c = cin.get() )!= '\n') continue;
	return c;
}

第三部分：编码

紫书中定义了 int readint（int i）函数来进行密码的读入，而我用 int readlen（）读入编码长度，int read（int len）读入编码内容（但感觉多此一举，只是理解起来好一些，两者实现方式差不多），注意其中的即时处理。。。。

 

第四部分：细节：

  1.在进行char 到 int 的转换的时候，记得要减去 ‘0’，如果是字母，一般要减去‘A’ or ‘a’。

  2. 二进制到十进制，求最大值的话，一定是 (1 << max ) - 1 , 一定要有减一。

  3. 有时候即使题目相关是 char 类型，但还是要用 int 表达，这是因为 EOF 只能用 int 判断，如果将其强制转换为char，则不能识别EOF

  4.先写程序大体框架，然后再去实现细节，模块化思维真的很重要

 

总体代码如下：继续加油啦！

#include<iostream>
#include<string>
#include<stdio.h>
#include<string.h> 
using namespace std;

int code[8][1 << 8];	// 编码最长有八位，而对于i位来说，其二进制数可以是 1<<i -1 位
int makehead();		//读取编码头
int readchar();		//辅助函数，解决多行输入问题
int readlen();		//读入len，注意在readlen中,二进制代码全为一也是可以的
int read(int len);			//根据len的值来确定读入的二进制数个数

int main(void)
{
	while (makehead())
	{	string ss; 
//		int len, value;
		for (;;)
		{	
			int len = readlen();
			int value;
			if (len == 0)	break;
			for(;;){
				int value = read(len);
				if (value == (1 << len)-1)	break;
				ss.push_back(code[len][value]);
			}
		}
		cout << ss << endl;
	}
	return 0;
}


int readchar()
{	
	while (true)
	{
		int ch = getchar();
		if (ch != '\n' && ch != '\r')	return ch;

	}
}

int makehead()
{
	memset(code, 0, sizeof(code));		//清空数组 
	code[1][0] = readchar();
	for (int i = 2; i < 8; i++)
	{
		for (int j = 0; j < (1 << i) - 1; j++)
		{
			int c = getchar();
			if (c == EOF)	return 0;
			if (c == '\n' || c == '\r')
				return 1;
			code[i][j] = c;
//			cout << "makehead 内层循环" << endl;
		}
//		cout << "makehead 外层循环" << endl;
	}
	return 1;		//编码头长度达到最大值 
}

int readlen()
{
	int count = 3;
	int len = 0;
	while (count--)
	{
		len = len*2 + readchar() - '0';
	}
	return len;
}

int read(int len)
{
	int count = len;
	int value = 0;
	while (count--)
	{
		value = value*2 +readchar() - '0'; 
	}
	return value;
}