上一篇的blog地址为：http://www.cnblogs.com/life91/p/3313868.html
这几天又参加了一个家公司的笔试题，在最后的编程题中竟然出现了去哪儿网开发的第一题，也就是简化路径值。但是这次做题后，我发现我上次写的那个简化源码有很多问题，并且在这次笔试过程中也没有答对。闲话说完了，进入正题。
上次源码出现的BUG：
1. 将连续重复的多个’/’字符视为一个。例如，”/abac/def//////ef”->”/abac/def/ef”。
2. 根目录的开始字符为’/’，并且根目录的上级目录以及上上级目录都是本身。例如，”/../../../”->”/”。
3. 字符’.’作为后缀名的分割符号出现。例如，”/abc/ef.gif”->”/abc/ef.gif”
4. 以字符’/’作为起始字符。
上述是上次源码出现的BUG。在修正这些BUG中，将增加一个临时空间用于存储原始路径。在拷贝过程中将连续重复出现的’/’变为一个’/’，并且删除”/./”这种情况。同时检查参数路径是否合法，目前仅考虑一种情况：当’.’个数超过2个时，将退出。
// preprocess.
while ( index < len )
{
// merge duplicate character -- '/'
for ( cnt = ;
index < len && path[index] == '/';
++index, ++cnt );
if ( cnt > )
{
tmp_path[top++] = '/';
} // delete only dot
for ( cnt = ;
index < len && path[index] == '.';
++index, ++cnt );
// Case 1: delete one dot.
if ( top > && tmp_path[top - ] == '/' && cnt == )
{
++index;
}
// Case 2: copy two dots.
else if ( cnt == )
{
index -= cnt;
}
// Case 3: if more than two dots, it is error.
else if ( cnt > )
{
fprintf( stderr, "Error.\n" );
// Remember: after free memory, this function could leave.
free( tmp_path ), tmp_path = NULL;
free( result ), result = NULL;
return NULL;
} // copy other characters.
while ( index < len && path[index] != '/' )
{
tmp_path[top++] = path[index++];
}
}
请注意：在异常退出函数时，需要将已分配的两个内存空间释放掉，并且将原始的指针指向NULL。防止内存泄漏问题。
在后续的处理过程中，使用栈的思想来处理。当遇到连续的两个’.’时，将栈中元素弹出。如果当栈中元素全部退出的时候，将重置top节点。
// Case 1: the number of '.' is 2;
if ( top > && cnt == )
{
--top;
while ( --top > && result[top] != '/' );
}
// Case 2: "game.gif"
else if ( top > && result[top - ] != '/' && cnt == )
{
result[top++] = '.';
}
// Case 3: "/../../../" -> "/"
else if ( top == )
{
++top;
}
完整的源码并提供简单的测试源码：
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h> char *normalize_path( const char *path )
{
char *result = NULL;
char *tmp_path = NULL;
int top = ;
int cnt = ;
int index = ;
int len = ; assert( path != NULL && path[index] != '\0' && path[index] == '/' );
len = strlen( path );
result = (char *) malloc( sizeof(char) * (len + ) );
assert( result != NULL ); tmp_path = (char *) malloc( sizeof(char) * (len + ) );
if ( tmp_path == NULL )
{
free( result ), result = NULL;
return NULL;
} // preprocess.
while ( index < len )
{
// merge duplicate character -- '/'
for ( cnt = ;
index < len && path[index] == '/';
++index, ++cnt );
if ( cnt > )
{
tmp_path[top++] = '/';
} // delete only dot
for ( cnt = ;
index < len && path[index] == '.';
++index, ++cnt );
// Case 1: delete one dot.
if ( top > && tmp_path[top - ] == '/' && cnt == )
{
++index;
}
// Case 2: copy two dots.
else if ( cnt == )
{
index -= cnt;
}
// Case 3: if more than two dots, it is error.
else if ( cnt > )
{
fprintf( stderr, "Error.\n" );
// Remember: after free memory, this function could leave.
free( tmp_path ), tmp_path = NULL;
free( result ), result = NULL;
return NULL;
} // copy other characters.
while ( index < len && path[index] != '/' )
{
tmp_path[top++] = path[index++];
}
} // other operators.
tmp_path[top] = '\0';
len = top;
for ( index = , top = ; index < len; )
{
// copy other characters except '.'
while ( index < len && tmp_path[index] != '.' )
{
result[top++] = tmp_path[index++];
} // count of point
for ( cnt = ; index < len && tmp_path[index] == '.'; ++index, ++cnt ); // Case 1: the number of '.' is 2;
if ( top > && cnt == )
{
--top;
while ( --top > && result[top] != '/' );
}
// Case 2: "game.gif"
else if ( top > && result[top - ] != '/' && cnt == )
{
result[top++] = '.';
}
// Case 3: "/../../../" -> "/"
else if ( top == )
{
++top;
} }
result[top] = '\0'; // free memory
free( tmp_path ), tmp_path = NULL; return result;
} void output( const char *path )
{
char *result = NULL; result = normalize_path( path );
printf( "Original is %s\nResult is %s\n\n", path, result );
free( result ), result = NULL; free( result );
result = NULL;
} int main()
{
char *path1 = "/home/news/./../tmp/game/../";
char *path2 = "/../../../abc";
char *path3 = "/game/gif.big";
char *path4 = "///abc//..//edf/game.f"; output( path1 );
output( path2 );
output( path3 );
output( path4 ); return ;
}
normalize_path