基本上没有这么考的,放在这里主要是为了和后面的原地逆序做个对比。很简单,直接分配一个与原字符串等长的字符数组,然后反向拷贝一下即可。
char* Reverse(char* s)
{
//将q指向字符串最后一个字符
char* q = s ;
while( *q++ ) ;
q -= 2 ;
//分配空间,存储逆序后的字符串。
char* p = newchar[sizeof(char) * (q - s + 2)] ;
char* r = p ;
// 逆序存储
while(q >= s)
*p++ = *q-- ;
*p = '\0' ;
return r ;
}
2.原地逆序
英文叫做in-place reverse。这是最常考的,原地逆序意味着不允额外分配空间,主要有以下几种方法,思想都差不多,就是将字符串两边的字符逐个交换,如下图。给定字符串"abcdef",逆序的过程分别是交换字符a和f,交换字符b和e,交换字符c和d。
(1)设置两个指针,分别指向字符串的头部和尾部,然后交换两个指针所指的字符,并向中间移动指针直到交叉。
char* Reverse(char* s)
{
// p指向字符串头部
char* p = s ;
// q指向字符串尾部
char* q = s ;
while( *q )
++q ;
q -- ;
// 交换并移动指针,直到p和q交叉
while(q > p)
{
char t = *p ;
*p++ = *q ;
*q-- = t ;
}
return s ;
}
(2)用递归的方式,需要给定逆序的区间,调用方法:Reverse(s, 0, strlen(s)) ;
// 对字符串s在区间left和right之间进行逆序,递归法
void Reverse( char* s, int left, int right )
{
if(left >= right)
return;
char t = s[left] ;
s[left] = s[right] ;
s[right] = t ;
Reverse(s, left + 1, right - 1) ;
}
(3)非递归法,同样指定逆序区间,和方法一没有本质区别,一个使用指针,一个使用下标。
// 对字符串str在区间left和right之间进行逆序
char* Reverse( char* s, int left, int right )
{
while( left < right )
{
char t = s[left] ;
s[left++] = s[right] ;
s[right--] = t ;
}
return s ;
}