题目要求：写一个递归算法来实现字符串的逆序存储，要求不另设存储空间
首先我们定一个一个存放字符串的结构体
typedef struct String { ElemType * data; int length; }String,*PString; //创建字符串的结构体
其中typedef 声明后的String 相当于 struct String,PString 相当于 struct String * 。ElemType是自定义的数据类型 由我们自己来定义
#define MaxSize 10 #define ElemType char
定义好一个字符串的数据结构我们首先对该结构体进行一个初始化的操作，我们需要一开始将长度定为0 代表目前字符串为空;
void Init_String(PString S) { S->data = (ElemType *)malloc(sizeof(ElemType)*MaxSize); //创建一个内存为10的int型数组空间 S->length=0; }
初始化完成之后，我们就需要创建字符串，实现函数如下
其中 char temp = getchar() 这句 是为了避免程序接收输入字符串后面的结束标志'\0'而导致出现bug，所以以防万一最好加上这句;
而一般字符串我们都喜欢从1开始数起，所以一般从索引为1的地址为存入数据的起始地址，需要将索引为0的内存浪费掉
void Create_Stirng(PString S) { printf("input the element of your string : \n"); char str; scanf_s("%c",&str); char temp = getchar(); while (str !='/')//end flag { S->length++; S->data[S->length] = str; scanf_s("%c",&str); temp = getchar(); } }
定义完了创建之后，我们就可以相继的定义辅助函数，列如遍历操作和交换操作，具体函数代码如下
遍历
void Traverse(PString S)
{
for (int i = 1; i <=S->length; i++)
{
printf("%c ",S->data[i]);
}
}交换
需要注意的是，这里交换的时候需要传入值的地址，因为如果单传入的是值，那么只是形参接收数据进行改变，而不会改变实参的值；
void swap(char *x,char *y)
{
char temp = *x;
*x = *y;
*y = temp;
}完成以上的操作后，就可以开始我们的主要功能了，就是逆序存放字符串
很简单 假设一个字符串 a b c d e f g 我们如果想通过递归来实现逆序，那么我们只要设置一个标识符len 来记录当前访问是第几个元素，我们只需要访问到字符串一半的位置 也就是'd' 这个位置 我们就可以通过传入当前位置和当前位置对称的位置的地址到swap()函数中 就可以将两个地址的值发生交换
这里的 len值 就可以看做字符所在的索引值
void Reverse_Str(PString S) { //判断字符串的长度 int flag = (S->length)/2; int r = (S->length)%2; if(len<flag+r) //如果没有到达一半的位置 { len++; Reverse_Str(S); } //swap swap(&S->data[len],&S->data[S->length+1-len]); len--; }
如果看不懂 &S->data[len],&S->data[S->length+1-len 这句，没有关系，听我来给你分析
假设我们要传入的字符串为 a b c d e f g 那么该字符串的长度就为7，我们使用递归算法遍历到 ‘d’
这个位置结束，那么d的对应位置就是该字符串的总长度->7+1 减去 当前d所在的索引值 -> 4 得到的对应位置就是 4 那么d因为是中间的值那么他的对应元素就是他本身。
当d结束变换位置后 函数退回到了 len = 3 也就是'c' 那么c对应位置是不是就是e 怎么得到e呢？同样代入上面那个式子 总长度：7+1-len = 5 我们可以数下发现e的位置就是5 那么依次往上退就可以将所有对应的位置进行一个交换 最终字符串完成了逆序操作。
下面给出完整代码实现，我用的是vs编译器
// ConsoleApplication15.cpp : 定义控制台应用程序的入口点。
//
#include "stdafx.h"
#include "stdlib.h"
#define MaxSize 10
#define ElemType char
typedef struct String
{
ElemType * data;
int length;
}String,*PString; //创建字符串的结构体
int len = 1;
void Init_String(PString S)
{
S->data = (ElemType *)malloc(sizeof(ElemType)*MaxSize); //创建一个内存为10的int型数组空间
S->length=0;
}
void swap(char *x,char *y)
{
char temp = *x;
*x = *y;
*y = temp;
}
void Reverse_Str(PString S)
{
//判断字符串的长度
int flag = (S->length)/2;
int r = (S->length)%2;
if(len<flag+r) //如果没有到达一半的位置
{
len++;
Reverse_Str(S);
}
//swap
swap(&S->data[len],&S->data[S->length+1-len]);
len--;
}
void Create_Stirng(PString S)
{
printf("input the element of your string : \n");
char str;
scanf_s("%c",&str);
char temp = getchar();
while (str !='/')//end flag
{
S->length++;
S->data[S->length] = str;
scanf_s("%c",&str);
temp = getchar();
}
}
void Traverse(PString S)
{
for (int i = 1; i <=S->length; i++)
{
printf("%c ",S->data[i]);
}
}
int _tmain(int argc, _TCHAR* argv[])
{
String S;
Init_String(&S);
Create_Stirng(&S);
Traverse(&S);
printf("\n");
Reverse_Str(&S);
Traverse(&S);
return 0;
}
要是有哪些不懂的地方可以评论区留言哈，或者加我v: Scavenger_self。