面接訓練文字列の組合せ

2622 ワード

タイトル:文字列を入力し、その文字列のすべての組合せを出力します.例えば、abcが入力されると、その組み合わせはa、b、c、ab、ac、bc、abcである.
最初は私の考えは再帰だったが、具体的にどうするかは考えられなかった.
后ろで涛兄日志の中の1人のネットユーザーの返事を见て、文字列を01と见て数字の列を构成して、1はアルファベットがあって、このように1から2^nの数字の中でどの位が1で、文字列に対応します
コードが簡単:
#include "stdio.h"
#include "math.h"
#include "string.h"

int main()
{
	int len ;
	int i,j;
	int number;
	char str[1024];
	scanf("%s",&str);
	len = strlen(str);
	number = pow(2,len);
	for(i=1;i<number;i++)
	{
		for(j=0;j<len;j++)
		{
			if((i>>j)&1)
			{
				printf("%c",str[j]);
			}
		}
		printf(" ");
	}
	return 0;
}

参考海濤の再帰解法
大波のブログを見て目の前が明るくなってよかったです.考えはこうだ
長さnの文字列からm文字を取り出します.どうやって取りますか.1最初の文字を取り、残りのn-1文字の列にm-1文字を取ります.
2最初の文字を取らず、残りのn文字列からm文字を削除
もちろん再帰的な戻りには条件が必要であり,文字列が終了したり,長さnが取得されたりしたときに終了する.
コードは次のとおりです.
#include "stdio.h"
#include "stdlib.h"
#include "math.h"
#include "string.h"
#define MAX 1024
typedef struct node{
	char data;
	struct node *next;
}MyNode;
typedef struct queue{
	
	 MyNode *tail;
	 MyNode *top;
	 int size;
}lineQueue;
void push( lineQueue *q,char data)
{
	 MyNode *p = ( MyNode *)malloc(sizeof( MyNode));
	p->data = data;
	p->next = NULL;
	if(q->tail != NULL)
	{
		(q->tail)->next = p;
	}
	q->tail = p;
	if(q->top == NULL)
	{
		q->top = p;
	}
	q->size +=1;
	
}
void pop( lineQueue *q,char *data)
{
	MyNode *p;
	if(q->top == NULL)
		return;
	p = q->top;
	if(q->top == q->tail)           /*            ,                      ,        */
	{
		q->tail = NULL;
	}
	*data = q->top->data;
	q->top = q->top->next;
	
	free(p);
	q->size-=1;
}
void initQueue(lineQueue **q)
{
	if(*q == NULL)
	{
		*q = (lineQueue *)malloc(sizeof(lineQueue));
	}
	(*q)->top = NULL;
	(*q)->tail = NULL;
	(*q)->size = 0;
}
void traverse(lineQueue *q)
{
	MyNode  *p = NULL;
	p = q->top;
	while(p!=NULL)
	{
		printf("%c",p->data);
		p= p->next;
	}
}
void combineLine(char *str,int num,lineQueue *q)
{
	int i =0;
	char data;
	if(num == 0)
	{
	
		traverse(q);
		printf(" ");
		return;
	}
	if(*str == '\0')
	{
		return;
	}
	push(q,*str);
	combineLine(str+1,num-1,q);
	pop(q,&data);
	combineLine(str+1,num,q);
}
void combine(char *str,lineQueue *q)
{
	int i = 0;
	int len = strlen(str);
	for(i=1;i<=len;i++)
	{
		combineLine(str,i,q);
	}
}
int main()
{
    lineQueue *q=NULL;
	int num=5;
	int i;
	char str[1024];
	initQueue(&q);

	scanf("%s",str);
	combine(str,q);

	return 0;
}