Chinaunix首页 | 论坛 | 博客
  • 博客访问: 537076
  • 博文数量: 45
  • 博客积分: 931
  • 博客等级: 准尉
  • 技术积分: 590
  • 用 户 组: 普通用户
  • 注册时间: 2005-04-17 13:27
文章分类

全部博文(45)

文章存档

2013年(6)

2012年(15)

2011年(23)

2005年(1)

分类: C/C++

2012-09-18 17:40:04

给定一个字符串S,其中S中的字符互不相同,输出S中字符的所有组合,
如S = "abc", 则输出:空,a, b, c, ab, ac, bc, abc,

下面是实现的程序:

点击(此处)折叠或打开

  1. void fullCombination(char *arr)
  2. {
  3.     int len = strlen(arr);
  4.     int *mask = new int[len];
  5.     int i, j;
  6.     
  7.     for(mask[0]=1, i=1; i<len; i++)
  8.         mask[i] = (mask[i-1]<<1);

  9.     int max = (1 << len);
  10.     int temp;
  11.     for(int count=0; count < max; count++) {
  12.         printf("[");
  13.         temp = count;
  14.         for(j=0; temp!=0; j++) {
  15.             if(temp & mask[j]) {
  16.                 printf("%c", arr[j]);
  17.                 temp ^= mask[j];
  18.             }
  19.         }
  20.         printf("]\n");
  21.     }
  22. }

  23. void testFullCombin()
  24. {
  25.     fullCombination("abcdef");
  26. }
上面是非递归的实现方法。

递归的实现方法:

点击(此处)折叠或打开

  1. void innerCombin(const char *arr, int n, int idx, int count, char *buf)
  2. {
  3.     if(count == n) {
  4.         printf("%s\n", buf);
  5.         return;
  6.     }
  7.     if (arr[idx] == '\0') return;
  8.     buf[count] = arr[idx];
  9.     innerCombin(arr, n, idx+1, count+1, buf);
  10.     innerCombin(arr, n, idx+1, count, buf);
  11. }
  12. void combination(const char *arr, int n)
  13. {
  14.     if (arr==NULL) return;
  15.     if (strlen(arr) < n) return;
  16.     char *buf = new char[n+1];
  17.     buf[n] = '\0';
  18.     innerCombin(arr, n, 0, 0, buf);
  19.     delete [] buf;
  20. }

  21. void testCombin()
  22. {
  23.     char arr[27] = "abcdefghijklmnopqrstuv";
  24.     strcpy(arr, "abcde");
  25.     int len = strlen(arr);
  26.     for(int i=1; i<=len; i++) {
  27.         combination(arr, i);
  28.     }
  29. }
更简单的一种递归办法:

点击(此处)折叠或打开

  1. void innerCombin2(char *arr, int idx, int count, char *buf)
  2. {
  3.     if(arr[idx] == '\0') {
  4.         buf[count] = '\0';
  5.         printf("%s\n", buf);
  6.         return;
  7.     }
  8.     innerCombin2(arr, idx+1, count, buf);
  9.     buf[count] = arr[idx];
  10.     innerCombin2(arr, idx+1, count+1, buf);
  11. }
  12. void combination2(char *arr) {
  13.     if(arr == NULL) return;
  14.     char *buf = new char[strlen(arr) + 1];
  15.     innerCombin2(arr, 0, 0, buf);
  16. }
  17. void testCombin2()
  18. {
  19.     combination2("abcde");
  20. }


阅读(2191) | 评论(2) | 转发(1) |
给主人留下些什么吧!~~

rubik_nslk2012-09-19 09:34:58

用shell完成过,C愣是写不出来

rubik_nslk2012-09-19 09:34:36