|
/************************************************************************/ /* 面试题：请编写一个函数，把字符串中的所有字符子串的各种组合形式全部都显示出来。 字符子串的长度范围是从一个字符到字符串的长度。 不管排列顺序如何，只要两种组合中的字符完全一样，它们就是同一种组合。 比如：给定字符串"hart"，则"ha"和"har"是不同的组合，而"ha"和"ah"是相同的组合。 排列方式：不以字符串多少为排列区分，而是以是否确定某一字符来确定字符子串 以hart作为字符串，则如下： h ha har
hart hat hr hrt ht a
ar art at r rt t 可以看出：第一行全有h，第二行没有h，全是art，第三行没有ha，全是rt，第四行没有har，就只有t 且 如果第一行去掉 h，恰好是 第二行 第三行 第四行 的全部，正好是 后3个字符art的组合， 再黏上一个 h ，就成了新的组合。 根据这样的特点：我们设计一个递归算法 （1）从首字符到尾字符的各个字符，循环 （2）输出被循环到的字符 （3）如果循环的字符 后面还有字符，递归；以后面的字符为起点，重复步骤（2）和步骤（3） （4）如果被循环到的字符后面没有字符，跳出循环。 画图的话，看成如下：以行为单位输出，1表示此字符输出 h a r t h a r t h 1 . . . h 1 . . . a 1 1 . . --》 a 1 1 . . r 1 1 1 . r 1 1 . 1 //下一行返回后，本行往下一列进行，后面的依次类推 t 1 1 1 1(return） t 1 1 1 1
*/ /************************************************************************/ #include <stdlib.h> #include <stdio.h> #include <iostream> using namespace std; int length; char *out; char str[]="hart"; //此法当有重复字母时，结果是错误的 int sum=0; void DoCombine(char in[],char out[],int length,int rec,int start)//rec看成行， { int i; for( i = start; i < length; i++)//i看成列 { out[rec] = in[i]; out[rec+1] =0; printf("%s\n",out); if(i< length-1) DoCombine(in,out,length,rec+1,i+1); } } int main(int argc, char* argv[]) { length = strlen(str); out = (char *)malloc(length +1); DoCombine(str,out,length,0,0); getchar(); return 0; } |
|
|
