逆序数组（递归和非递归）(详细)

ゝ一纸荒年。 2024-04-01 15:04 66阅读 0赞

#### 逆序数组 递归和非递归 ####

*  一.非递归
 *  二.递归

![在这里插入图片描述][9eb6c2857a754336aa88f1c20710df19.png]

## 一.非递归 ##

> **思路：将第一个元素和最后一个元素交换，再将第二个元素和倒数第二个元素交换…直到所有元素全部交换**

*假设有一个数组arr\[\]=“abcdef”,我们令它的第一个元素为arr\[left\],最后一个元素为arr\[right\],那么我们就需要如下交换*  
![在这里插入图片描述][cd7fec8c0f724c9f8868b5957c985254.png]![在这里插入图片描述][ae9fa5485d114ae0a8944279d04fda02.png]

> **从上面的流程图可以看出当left<right时 ，便进行下一步交换，反之，就结束程序，这里直接上代码**

void Reverse(char* arr)
    {
        
    	int left = 0;
    	int right = strlen(arr) - 1;//strlen用于求数组长度，但由于数组下标
    	while (right > left)       //是从0开始的，所以最后一个元素的下标是
    	{
                                 //数组长度-1，6-1=5
    		char tmp = arr[left];
    		arr[left] = arr[right];
    		arr[right] = tmp;//以上三步是将arr[left]和arr[right]交换
    		right--;//右坐标向左移1
    		left++;//左坐标向右移1
    	}//当left不再小于right时表明已经逆移完全，结束循环
    
    }
    int main()
    {
        
    	char arr[] = "abcdef";
    	Reverse(arr);
    	printf("%s", arr);
    	return 0;
    }

## 二.递归 ##

> **思路：我们可以把这个问题拆成两步。第一步：交换a和f。第二步:再用函数Reverse交换bcde**  
> ![在这里插入图片描述][2d7a78f5c0a54079988cada9c40f7a36.png]

*这里我们首先将a和 f交换*

int left = 0;
    	int right = strlen(arr)-1;
    	char tmp = arr[left];
    	//这里有缺陷
    	arr[left] = arr[right];
    	arr[right] = tmp;
    	//这里有缺陷
    	Reverse(arr + 1);

***逆序完第一次后我们需要让左坐标+1，所以我们传Reverse(arr+1),但在这里有个问题，逆序完第一次时，再逆序第二次时，你的left确实+1，但right并未改变，因为 right = strlen(arr)-1，而strlen是遇到’\\0’,才会停下，但你这里’\\0’但位置并未发生改变，所以right永远指向同一位置。***  
![在这里插入图片描述][cee9ccb516444552948df9d5894928c7.png]  
***想要解决它，其实只需要将a的位置变为’\\0’就可以了,所以我们需要令arr\[5\]=‘\\0’ (这里为了方便，我直接写的下标)。但还是有个问题，就是如果先交换再赋值的话，那么a就会变为’\\0’，得不到正确答案，所以我们需要一个临时变量先将a储存起来，再赋值’\\0’,这样arr\[5\]=‘\\0’,再进行Rverse(arr+1),right就指向e,最后再将a给arr\[5\]。***  
![在这里插入图片描述][1069904c40bd47f5831b76fab0e622b2.png]  
***最后赋值***  
![在这里插入图片描述][4165b45eb7e440188b44bccb781c71fc.png]

int left = 0;
    	int right = strlen(arr)-1;
    	char tmp = arr[left];//把a存到tmp里
    	arr[right] = arr[left];//把f交换到原来a的位置（也就是arr[0]）
    	arr[right] = '\0';//令原来放f的位置（也就是arr[5]）放'\0'
    	Reverse(arr+1);
    	
    	arr[right] = tmp;//再把a给放'\0'的位置(也就是arr[5])

***这样是不是就可以运行了呢？其实还有一个问题，就是递归如果没有限制条件的话，那么就会成为死递归，导致系统崩溃，所以我们需要加入限制条件：***

![在这里插入图片描述][eb9cc6c9e42b4f75a48d1815ede2207e.png]

if (strlen(arr + 1) >= 2)
    	{
        
    		Reverse(arr + 1);
    	}

这样的话程序就完成啦，来看看完整代码

void Reverse(char* arr)
    {
        
    	int left = 0;
    	int right = strlen(arr)-1;
    	char tmp = arr[left];
    	arr[left] = arr[right];
    	arr[right] = '\0';
    	if (strlen(arr + 1) >= 2)
    	{
        
    		Reverse(arr + 1);
    	}
    	 arr[right]= tmp;
    
    
    }
    int main()
    {
        
    	char arr[] = "abcdef";
    	Reverse(arr);
    	printf("%s", arr);
    	return 0;
    }

![在这里插入图片描述][f504c588f290456a984642ddad2adb10.png]  
![在这里插入图片描述][72e5ba5c71404c049c61305311730c8f.png]

[9eb6c2857a754336aa88f1c20710df19.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/248c2942817a46fc8a25d3a1ad59da31.png
[cd7fec8c0f724c9f8868b5957c985254.png]: https://img-blog.csdnimg.cn/cd7fec8c0f724c9f8868b5957c985254.png
[ae9fa5485d114ae0a8944279d04fda02.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/244d13e998db43f5906df9fb3359ec11.png
[2d7a78f5c0a54079988cada9c40f7a36.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/a31dbf2b466440508e0051cd5876e76e.png
[cee9ccb516444552948df9d5894928c7.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/15fce68d2c5043edbf18f146f0418794.png
[1069904c40bd47f5831b76fab0e622b2.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/50cd51b8739e4ddd94399f6ec8fd29a4.png
[4165b45eb7e440188b44bccb781c71fc.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/cc22849532ad484dbd03d9f2a3db4b83.png
[eb9cc6c9e42b4f75a48d1815ede2207e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/de7fc748af614874bd52782efa4f8650.png
[f504c588f290456a984642ddad2adb10.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/12967c5f3a604a3bb0259a4d9f97a545.png
[72e5ba5c71404c049c61305311730c8f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/1764a489c7d1467caaa2525c06d6f5cc.png