[数据结构与算法]C语言基础——字符串逆序（递归实现，不使用库函数）

对于这题，我们要特别注意的是：是字符串中的字符反向排列，不是逆序打印！

下面我会分别用非递归和递归的方法介绍本题。

从main()函数入手

1. 定义一个数组。
2. 调用实现字符串逆序的函数。——本题核心
3. 打印交换后的数组。

int main()
{
	char arr[] = "abcdefg";
	reverse_string(arr);
	printf("%s\n",arr);
	return 0;
}

自定义strlen()函数，计算数组长度

int my_strlen(char* arr)
{
	int count = 0;
	while (*arr!='\0')
	{
		count++;
		arr++;
	}
	return count;
}

法一（非递归）

1. 定义函数类型：这里只是交换数组，不需要参数返回，所以用void。
2. 定义两个指针：char* left和char* right，分别指向数组首元素地址和数组最后一个元素的地址。
3. 交换数组元素。

void reverse_string(char* arr)
{
	char* left = arr;
	char* right = arr + my_strlen(arr) - 1;
  
//my_strlen计算出的数组长度包括了‘\0’,因此-1获得整个数组的长度,再+arr指向最后一个元素的地址。
	
    while (left < right)
	{
		char tmp = *left;
		*left = *right;
		*right = tmp;
		left++;
		right--;
	}
}

法二 （递归）

解题思路：

1. 数组char arr[] = "a b c d e f g \0" 中，每一次都交换第一个元素和最后一个元素，再加上中间元素的交换函数。
2. 如：第一次交换 "g? reverse_string(char* arr)? a? \0"。注意：先不着急把a放入最后一个元素的地址中，令最后一个数组元素成‘\0’，a存储到临时变量tmp里。如："g? reverse_string(char* arr)??\0",?tmp=a。（原因：逆序函数传进去的是一个字符串。若不这样操作逆序函数再次调用的时候无法进行，因为此时中间剩余元素不是一个字符串）
3. 实现递归都要有一个限制条件，若没有限制条件则会出现死递归。当字符串的长度为奇数时，中间只剩一个数组元素，并不需要交换，增加限制条件if(strlen(arr)>1)，让递归最后停下。
4. 最后把第一个元素放入最后一个元素的地址中。

void reverse_string(char* arr)
{
	char* left = arr;
	char* right = arr + my_strlen(arr) - 1;
	char tmp = *left;  //临时变量，暂时存放第一个数组元素
	*left = *right;
	*right = '\0';
	if(strlen(arr)>1)
	reverse_string(arr + 1);  //left指针指向第二个数组元素
	*right = tmp;
}

代码整体实现及结果

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>

int my_strlen(char* arr)
{
	int count = 0;
	while (*arr!='\0')
	{
		count++;
		arr++;
	}
	return count;
}

非递归版本
//void reverse_string(char* arr)
//{
//	char* left = arr;
//	char* right = arr + my_strlen(arr) - 1;
//	while (left < right)
//	{
//		char tmp = *left;
//		*left = *right;
//		*right = tmp;
//		left++;
//		right--;
//	}
//}

void reverse_string(char* arr)
{
	char* left = arr;
	char* right = arr + my_strlen(arr) - 1;
	char tmp = *left;
	*left = *right;
	*right = '\0';
	if(strlen(arr)>1)
	reverse_string(arr + 1);
	*right = tmp;
}

int main()
{
	char arr[] = "abcdefg";
	reverse_string(arr);
	printf("%s\n",arr);
	return 0;
}