逆序字符串（递归和非递归）

2023-06-03 05:06| 来源: 网络整理| 查看: 265

采用递归和非递归两种方式逆序一个字符串的内容非递归方法一方法二递归方法一方法二

非递归方法一

思路：将字符串的第一个字符和最后一个字符交换，接着将第二个字符和倒数第二个字符交换，以此类推，直到所有的对应字符交换完，具体操作如下： 1、采用两个下标left和right分别指向字符串的第一个字符和最后一个字符 2、交换left和right所指元素，接着left向后走一步指向第二个字符，right向前走一步指向倒数第二个字符 3、重复第2步，直到所有对应字符交换完

核心代码：

void reverseStr(char* str) //逆序字符串的函数 { int left = 0; //初始化，指向字符串第一个字符 int right = strlen(str) - 1; //初始化，指向字符串最后一个字符 while (left int len = strlen(str); //求字符串的长度 int i = 0; for (i = 0; i if (*str && *(str + 1)) //字符串至少还有两个元素 { reverseStr(str + 1); //逆序当前字符串中第一个字符后面的字符串 //将第一个字符放在上一步逆序的字符串后面（具体操作就是：将上一步逆序的字符串整体往前移动一位，再将第一个字符放到最后面） char tmp = *str; //先保存第一个字符，以免被覆盖 char* p = str + 1; //操作指针 while (*p) //整体前移字符串，遇到'\0'停止 { *(p - 1) = *p; p++; } *(p - 1) = tmp; //第一个元素放到最后面 } }

方法二

思路：先将第一个字符和最后一个字符中间的字符串逆序，然后再将第一个字符和最后一个字符交换，而要逆序中间的字符串继续采用相同的方式逆序，这样一直递归下去，直到中间的字符串为空或者只剩一个字符的时候终止递归。

问题来了：对于上述思路，当我需要逆序中间字符串的时候，我每次要怎么确定中间字符串的区间呢（每次往下递归的时候，区间都是不一样的）？下面介绍了两种写法：

写法一：采用两个下标left和right分别指向字符串两端，每次逆序中间字符串的时候只需要将left加1，right减1即可，直到left大于或者等于right的时候停止

核心代码：

void reverseStr(char* str, int left, int right) //逆序left和right中间区域的字符串（不包括left和right所指字符） { if (left int len = strlen(str); if (len >= 2) //字符串至少应有两个字符才能递归 { char tmp = str[0]; //保存第一个字符 str[0] = str[len - 1]; //将当前字符串中最后一个字符赋值给第一个字符 str[len - 1] = '\0'; //将最后一个字符赋值为'\0' reverseStr(str + 1); //逆序中间的字符串 str[len - 1] = tmp; //将保存的第一个字符赋值给最后一个字符 } }

总结： 1、采用非递归的方式逆序字符串效率比递归方式高 2、递归方式中，方法一相对于方法二要慢一些，主要是因为要移动大量的元素， 3、我个人在考虑递归问题的时候，我会先心里定义一个函数，我不知道这个函数的实现，我会把这个函数当作一个别人已经写好的函数并且具有解决这个问题的功能，然后带着这个函数从问题出发梳理清楚逻辑，把这个函数用到解决这个问题的代码中，最后所写的代码就是最终的这个递归函数

【本文地址】

逆序字符串（递归和非递归）

逆序字符串（递归和非递归）

今日新闻

推荐新闻