发布网友
发布时间：2022-12-29 04:52
共1个回答
热心网友
时间：2023-10-25 12:21
整体思路就是利用回溯的思想，也可认为是深度优先搜索
从字符串第一位idx=0开始，每次递归都从s[idx]之后选择一个字符与s[idx]交换
因为可能有重复字符，可使用哈希数组标记当前循环每个字符是否被选择
因为字符范围不超过ASCII码，所以使用128空间的数组足够用来标记了
选择好当前字符s[i]并与s[idx]交换之后，递归调用继续排列下一位s[idx+1]
注意这里要进行回溯，即不选s[i]而选择之后的某个字符交换到s[idx]
所以要将之前的s[i]与s[idx]交换过来，恢复原状，才能循环判断下一个选择
具体代码截图如下：
运行结果如下：
结果正确，望采纳~
附源码：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXN 1000000 // 排列总数可能很多
int num = 0; // 记录排列总数
char *res[MAXN] = {NULL}; // 指针数组保存排列结果
void swap(char *x, char *y) { // 交换两个字符变量的内容
char ch = *x;
*x = *y;
*y = ch;
}
void perm(char *s, int n, int idx) { // 回溯产生字符串全排列
if (idx == n) { // 已排列到字符串结尾
res[num] = (char *)malloc(sizeof(char) * (n + 1));
//printf("%s\n", s); // 输出当前排列
strcpy(res[num], s); // 保存当前排列
num++; // 排列总数加1
return;
}
int i, hash[128] = {0}; // 哈希数组，标记每个字符是否被选择
for (i = idx; i < n; i++) {
if (hash[s[i]] == 1)
continue; // 跳过已被标记过的重复字符
hash[s[i]] = 1; // 选过的话在数组中标记为1
swap(&s[idx], &s[i]); // 选择s[i]交换到s[idx]
perm(s, n, idx + 1); // 递归，继续s[idx+1]的选择
swap(&s[idx], &s[i]); // 回溯，当前不选择s[i]，而选择其他字符
}
}
int main() {
int n, i;
scanf("%d", &n);
char *s = (char *)malloc(sizeof(char) * (n + 1));
scanf("%s", s);
perm(s, n, 0);
printf("一共有%d种排列:\n", num); // 输出排列总数
for (i = 0; i < num; i++) { // 输出所有排列
printf("%s\n", res[i]);
free(res[i]); // 释放内存空间
}
free(s);
return 0;
}
Copyright © 2019-2022 51dongshi.com 版权所有
违法及侵权请联系：TEL:177 7030 7066 E-MAIL:11247931@qq.com 本站由北京市万商天勤律师事务所王兴未律师提供法律服务
