C语言实现：输入字符串的全部组合

116 阅读 0 评论 77 点赞

我是靠谱客的博主柔弱战斗机，这篇文章主要介绍C语言实现：输入字符串的全部组合，现在分享给大家，希望可以做个参考。

来自剑指offer上相关题目拓展，居然磨了我两天的功夫，我可能学的是假的编程。

代码是用纯C写的，题目要求是将输入字符串的所有组合全部输出，例如输入a,b,c三个字符，则它们的组合有a, b, c, ab, ac, bc, abc.

当交换两个字符时，虽然排列顺序变动，但还是算作一个组合，即ab和ba算作同一个，如何不重复的输出这些组合呢？

复制代码

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MAX 25

void combination_op(char* pstr, char* output, int m);
void combination(char* pstr);

int main(){
//	char* pstr = "";
	char pstr[MAX] = "";
//	FILE *fp = fopen("input.txt", "r");

printf("输入待处理的字符串:n");
	while(gets(pstr) != NULL);

combination(pstr);

/*	if(fp != NULL){
		while(fgets(pstr, sizeof(pstr), fp) != NULL);
		combination(pstr);
	}
*/
	return EXIT_SUCCESS;
}

void combination(char* pstr){
	int cap;

if(pstr == NULL){
		printf("空串！n");
		return;
	}
	for(cap = 1; cap <= (int)strlen(pstr); cap++){
		char output[MAX] = "";
		combination_op(pstr, output, cap);
	}
}
void combination_op(char* pstr, char* output, int m){
	/*
	**当剩下的字符恰好够组合时，直接全部复制到输出字串中。
	*/
	if((int)strlen(pstr) == m){
		strcat(output, pstr);
		printf("%sn",output);
		*(output + (int)strlen(output) - m - 1) = '';//回溯
		return;
	}
	/*
	**输出串已满时
	*/
	if(m <= 0){
		printf("%sn", output);	
		*(output + (int)strlen(output) - 1) = '';//回溯
	}else{
		//添加当前字符
		strncat(output, pstr,1);
		combination_op(pstr+1, output, m-1);
		//不添加当前字符
		combination_op(pstr+1, output, m);
	}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MAX 25

void combination_op(char* pstr, char* output, int m);
void combination(char* pstr);


int main(){
//	char* pstr = "";
	char pstr[MAX] = "";
//	FILE *fp = fopen("input.txt", "r");

	printf("输入待处理的字符串:n");
	while(gets(pstr) != NULL);

	combination(pstr);

/*	if(fp != NULL){
		while(fgets(pstr, sizeof(pstr), fp) != NULL);
		combination(pstr);
	}
*/
	return EXIT_SUCCESS;
}

void combination(char* pstr){
	int cap;

	if(pstr == NULL){
		printf("空串！n");
		return;
	}
	for(cap = 1; cap <= (int)strlen(pstr); cap++){
		char output[MAX] = "";
		combination_op(pstr, output, cap);
	}
}
void combination_op(char* pstr, char* output, int m){
	/*
	**当剩下的字符恰好够组合时，直接全部复制到输出字串中。
	*/
	if((int)strlen(pstr) == m){
		strcat(output, pstr);
		printf("%sn",output);
		*(output + (int)strlen(output) - m - 1) = '';//回溯
		return;
	}
	/*
	**输出串已满时
	*/
	if(m <= 0){
		printf("%sn", output);	
		*(output + (int)strlen(output) - 1) = '';//回溯
	}else{
		//添加当前字符
		strncat(output, pstr,1);
		combination_op(pstr+1, output, m-1);
		//不添加当前字符
		combination_op(pstr+1, output, m);
	}
}