算法3：给一个字符数组（a-z）,如何打印该数组成员构成集合的全部子集合

2019-11-06 08:17:33

字体：大中小

来源：转载

供稿：网友

给一个字符数组（a-z）,如何打印该数组成员构成集合的全部子集合

样例

字符数组ahia,输出如下： a h i ah ai hi ahi

解题思路如下：

1、首先算出字符数据中所包含的字符，使用二进制数据来表示，比如abca的二进制数据表示为{1,1,1,0…0}，输出二进制位为1的全部子集合。 2、打印二进制位为1的字符子集合，每个子集合与二进制关系对应如下： a 1 b 10 c 100 ab 11 ac 101 bc 110 abc 111

算法

设字符数组包含n个字符，s是从第一位到第n位均为1的二进制，i=0~2^n-1与s进行&操作，打印出值为1在n个字符数据中的字符，时间复杂度为O(2^n).

数据结构设置如下：

strBuffer[100]为字符数组； character[26]代表26个字母是否存在，0不存在，1存在 exsitChar[26]表示实际存在的字母集合 length为exsitChar[26]的长度 exsitcharBin表示从第一位到第n位均为1的二进制

c++代码

#include "iostream"#include "string.h"#include "math.h"using namespace std;#define CHAR_LEN 26//获取字符数组中包含的所有字符void GetExistChar(char* srcBuffer,char exsitChar[], int& length){ char character[CHAR_LEN] = {0}; length = 0; for(int i = 0; i < strlen(srcBuffer);i++) { character[srcBuffer[i]-'a'] = 1; } for(int i = 0; i < CHAR_LEN;i++) { if(character[i] == 1) { exsitChar[length++] = i+'a'; } }}//输出全部子集合void PRintAllSubChar(char exsitChar[], int count){ int exsitCharBin = pow(2,(double)count)-1; int index = 0; cout<<"begin to output sub buffer"<<endl; for(int i = 1; i <= exsitCharBin; i++) { index = exsitCharBin & i; int m = 0; while(index > 0) { if(index%2 > 0) { cout<<exsitChar[m]; } index = index>>1; m++; } cout<<endl; }}

测试代码：

char srcBuffer[100] = {0};cout<<"please print character buffer"<<endl;cin>>srcBuffer;char existChar[CHAR_LEN] = {0};int length = 0;GetExistChar(srcBuffer,existChar,length);PrintAllSubChar(existChar,length);

上一篇：歌星大奖赛

下一篇：c语言中关于函数参数中（包含...），占位符。

学习交流

索泰发布一款GTX 1070 Mini迷你版本:小机

索泰发布一款GTX 1070 Mini迷你版本:小机箱大爱...

热门图片

猜你喜欢的新闻

猜你喜欢的关注