首页 > 代码库 > ZOJ 3481. Expand Tab
ZOJ 3481. Expand Tab
题目：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=4278
题意：
给出一些文本片段，把文本中的 Tab 字符根据配置，替换成一定数量的空格。
配置分为两种，一种是只提供一个 ts 值，则需要缩进到的位置是一个等比数列。另一种是提供一个 ts 的有限集合，指定一些给定 ts 值，在逻辑上这个集合是无限的，当列位置超出集合中的数字时，后续的 tabstop 位置为连续的以 1 个空格进行递增。
分析：
本题目本身是比较简单的。但是值得注意的是：
（1）当给定一个 ts 序列时，ts 序列的数字无序且可能重复（如果去重，可能会导致数组中只剩下一个数字，这时候不能当做等比数列来处理。如果不去重就不必在意这个问题）。所以不能假设序列有序，可以对这个序列进行一次排序。
（2）当只提供一个 ts 值，这时为等比数列。最开始我使用了类似图像的行对齐公式来计算 stop 位置，结果这在一些情况下，结果会多考虑一个 ts 值。实际上的索引为 iCol 的列的 tabstop 值，公式仅仅是 (iCol / ts + 1) * ts 即可。由于我在这里编码心态过急，犯下这个低级失误，导致我不断的 PE N 次，差点崩溃。回到家里我慢慢查看这些步骤才找到这个错误。
代码：
#include <stdio.h>#include <string.h>#include <stdlib.h>typedef struct _TabStop { int count; int ts[500]; char delimit[1024];} TABSTOP, *LPTABSTOP;//解析配置信息void ParseTabStop(char *line, LPTABSTOP pTS);//获取 tab stop 位置int GetStopCol(int iCol, LPTABSTOP pTS);//排序用的比较函数int cmp(const void* p1, const void* p2);TABSTOP g_TS;int main() { int i, T, col, stopCol; char line[1024], *p; scanf("%ld\n", &T); for(i = 0; i < T; i++) { gets(line); memset(&g_TS, 0, sizeof(TABSTOP)); ParseTabStop(line, &g_TS); while(true) { gets(line); if(strcmp(line, g_TS.delimit) == 0) { gets(line); /*case结尾的空行*/ printf("\n"); break; } col = 0; p = line; while(*p) { if(*p == ‘\t‘) { stopCol = GetStopCol(col, &g_TS); while(col < stopCol) { printf(" "); ++col; } } else { printf("%c", *p); ++col; } ++p; } printf("\n"); } } return 0;}//解析 tabstop 配置void ParseTabStop(char *line, LPTABSTOP pTS){ /*expand tab-stops-configuration <<delimiting-identifier*/ char *p = line + 7; char ch; int index = 0; while(*p) { ch = *p; if(ch >= ‘0‘ && ch <= ‘9‘) pTS->ts[index] = pTS->ts[index] * 10 + (*p - ‘0‘); else if(ch == ‘,‘) ++index; else if(ch == ‘<‘) { strcpy(pTS->delimit, p + 2); break; } ++p; } pTS->count = index + 1; qsort(pTS->ts, pTS->count, sizeof(int), cmp);}//获取当前列的 tabstop 位置int GetStopCol(int iCol, LPTABSTOP pTS){ int i; if(pTS->count == 1) { return (iCol / pTS->ts[0] + 1) * pTS->ts[0]; } else { if(pTS->ts[pTS->count-1] <= iCol) return iCol + 1; for(i = 0; i < pTS->count; i++) { if(iCol < pTS->ts[i]) return pTS->ts[i]; } } return iCol + 1;}int cmp(const void* p1, const void* p2){ int *pX1 = (int*)p1; int *pX2 = (int*)p2; return *pX1 - *pX2;}
补充：
当然，如果不对序列进行排序，也是可以的。区别只是在获取 tabstop 位置时，每次都要完整的线性遍历这个集合（在有序的情况下可以提前结束遍历，或者进一步的用二分查找快速定位），尝试找到满足条件 ts > iCol 的所有 ts 中的最小值即可。
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。