UVa 245 Uncompress-编程实验室

题目分析

本题要求实现一个解压缩程序，根据给定的压缩文件恢复原始文件。压缩规则如下：

原始文件中包含单词（连续的字母序列）和非字母字符。
对于第一次出现的单词，直接输出该单词，并将其放入一个列表中（放在列表最前面）。
对于后续出现的单词，不输出单词本身，而是输出该单词在列表中的位置（从1 11开始编号），然后将该单词移动到列表最前面。
非字母字符（如标点符号、空格、换行等）直接原样输出，不进行压缩处理。
输入以单独一行的一个数字0 00表示结束，该0 00不参与输出。

需要注意的是，本题解压缩的输入文件实际上是一个压缩后的文件，其中包含了数字（表示单词在列表中的位置）和原始的非字母字符。我们需要根据这些数字和保留的单词信息，还原出原始的未压缩文本。

例如，在样例输入中：

Dear Sally, Please, please do it- - 1 would 4 Mary very, 1 much. And 4 6 8 everything in 5's power to make 14 pay off for you. Thank 2 18 18- - 0

我们需要正确解析其中的数字，将其替换为对应的单词，并更新单词列表的顺序。

解题思路

核心数据结构

由于单词需要频繁进行“移动到列表最前面”的操作，并且需要根据位置快速访问单词，我们可以选择list \texttt{list}list（双向链表）作为存储单词列表的数据结构。list \texttt{list}list支持O ( 1 ) O(1)O(1)时间在头部插入元素，也支持在任意位置删除元素（通过迭代器），非常适合本题的需求。

算法步骤

初始化一个空的list<string> words \texttt{list<string> words}list<string> words，用于存储已经出现过的单词，最新出现的单词放在链表头部。
逐行读入输入，直到遇到单独的一行"0"为止。
对于每一行文本，逐个字符处理：
- 如果当前字符是数字：
  - 连续读取数字字符，组成一个完整的数字字符串。
  - 将该数字转换为整数n nn。
  - 从words \texttt{words}words链表中找到第n nn个单词（注意位置从1 11开始）。
  - 将该单词输出到结果中。
  - 从链表中删除该单词。
  - 将该单词插入到链表的最前面（因为单词被再次使用，需要移动到列表头部）。
- 如果当前字符是字母：
  - 连续读取字母字符，组成一个完整的单词。
  - 将该单词输出到结果中。
  - 将该单词插入到链表的最前面（因为是第一次出现，或者即使之前出现过但根据规则，这里实际上也是第一次出现的情况，因为压缩文件中如果是重复出现的单词，会用数字代替，不会出现字母序列）。
  - 注意：根据压缩规则，输入中的单词都是第一次出现的情况，因为在压缩过程中，只有第一次出现的单词才会被原样保留，重复的单词已经被替换为数字。所以这里我们不需要检查单词是否已经存在于链表中，直接插入即可。
- 如果当前字符既不是数字也不是字母：
  - 直接将该字符输出到结果中。
每处理完一行，输出一个换行符。

关键细节

单词的定义：单词是连续的字母序列（大小写敏感），"abc"和"Abc"被视为不同的单词。因此我们直接使用字符串比较即可，不需要额外处理大小写。
数字的解析：数字可能不止一位，需要连续读取。例如样例中的18是一个完整的数字，表示列表中的第18 1818个单词。
边界情况：当数字对应的单词被取出后，原位置被删除，链表的长度减1 11。然后将该单词插入头部，链表长度又恢复为原长度。列表中的单词顺序会随着每次“使用”而动态变化。
输入终止：遇到单独一行的"0"时停止处理，"0"本身不输出。

复杂度分析

设原始文件中的单词总数为N NN，输入文件中的字符总数为M MM。每个单词插入头部是O ( 1 ) O(1)O(1)时间，根据位置查找单词需要O ( N ) O(N)O(N)时间（因为list \texttt{list}list不支持随机访问，需要通过迭代器移动）。最坏情况下，总时间复杂度为O ( N × M ) O(N \times M)O(N×M)，但由于本题没有给出明确的上限，且数据规模通常较小，该做法可以通过。如果需要优化，可以使用vector \texttt{vector}vector配合哈希表记录位置，但list \texttt{list}list的实现简洁且满足题目要求。

代码实现

// Uncompress// UVa ID: 245// Verdict: Accepted// Submission Date: 2016-05-12// UVa Run Time: 0.060s//// 版权所有（C）2016，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;intmain(intargc,char*argv[]){cin.tie(0);cout.sync_with_stdio(false);string line;list<string>words;// 存储单词列表，头部为最近使用的单词// 逐行读入，直到遇到单独的 "0"while(getline(cin,line),line!="0"){// 遍历当前行的每一个字符for(inti=0;i<line.length();i++){// 情况1：遇到数字，表示要解压缩为一个之前出现过的单词if(isdigit(line[i])){string number;number+=line[i++];// 读取第一个数字字符// 继续读取连续的数字字符while(i<line.length()&&isdigit(line[i]))number+=line[i++];// 将数字字符串转换为整数，得到单词在列表中的位置（从1开始）autoit=words.begin();advance(it,stoi(number)-1);// 移动到第 number 个单词// 取出该单词string word=*it;words.erase(it);// 从原位置删除// 输出该单词（解压缩结果）cout<<word;// 将该单词移动到列表头部words.insert(words.begin(),word);i--;// 因为外层循环会自增，这里回退一位}// 情况2：遇到字母，表示这是一个第一次出现的单词elseif(isalpha(line[i])){string word;word+=line[i++];// 读取第一个字母字符// 继续读取连续的字母字符while(i<line.length()&&isalpha(line[i]))word+=line[i++];// 将单词插入列表头部（表示最近使用）words.insert(words.begin(),word);// 直接输出该单词cout<<word;i--;// 回退一位}// 情况3：其他字符（标点、空格等），直接原样输出elsecout<<line[i];}// 每行处理完毕，输出换行符cout<<"\n";}return0;}

总结

本题通过模拟压缩过程中的单词列表维护来实现解压缩，核心在于正确识别输入中的数字和字母序列，并利用list \texttt{list}list高效地完成单词的查询、删除和插入操作。理解压缩与解压缩的对称性是解决本题的关键，即：压缩时第一次出现的单词保留原词并加入列表头部，重复出现的单词用列表位置编号代替；解压缩时遇到数字就去列表中查找对应位置的单词并输出，同时更新列表顺序。