20CN网络安全小组论坛 - 编程破解

论坛: 编程破解标题: 我面试的一道题目

复制本贴地址

作者: ziaichen [ziaichen]

论坛用户

我现在实习所在公司以前给我的一到面试题目：把一个字符串的全排列输出
语言种类不限（最好是c）
请有兴趣的朋友贴出自己的算法，大家交流以下

地主发表时间: 06-03-20 16:45

回复: jhkdiy [jhkdiy]

版主

遭了，什么是全排列。

B1层发表时间: 06-03-20 19:14

回复: ziaichen [ziaichen]

论坛用户

汗，就是一个字符串所有不同的字母排列，比如有n个字母，这样的排列就有n！个

B2层发表时间: 06-03-21 08:39

回复: sniper167 [sniper167]

论坛用户

上网有限制又贴不上来大家去看看这个程序字符串的全排列的
偶还没看懂哪位要是看懂了麻烦解释下谢谢咯 http://community.csdn.net/Expert/topic/4651/4651618.xml?temp=.5014459

B3层发表时间: 06-03-30 19:15

回复: ziaichen [ziaichen]

论坛用户

楼上的程序有个严重的错误：当输入的字符串有相邻的字符是相同的话，会重复输出相同的排列

如：请输入一个不超过20个字符的字符kkm
1:kkm
2:kmk
3:kkm
4:kmk
5:mkk
6:mkk
Press any key to continue

[此贴被一窍不通(ziaichen) 在 04月06日17时37分编辑过]

B4层发表时间: 06-04-06 17:32

回复: ziaichen [ziaichen]

论坛用户

楼上的，最近没什么时间上网看帖子喽，偶要走了，有时间和你q或者邮箱多多探讨问题，qq：153975801 邮箱：ckun0210@163.com

B5层发表时间: 06-04-06 17:36

回复: sniper167 [sniper167]

论坛用户

偶只能邮箱跟你联系咯我这不能上qq的

我正在用另外一种算法写写好了发上来
偶最近也有点忙啊

B6层发表时间: 06-04-07 12:53

回复: sniper167 [sniper167]

论坛用户

TO: 一窍不通
楼上的程序有个严重的错误：当输入的字符串有相邻的字符是相同的话，会重复输出相同的排列

如：请输入一个不超过20个字符的字符kkm
1:kkm
2:kmk
3:kkm
4:kmk
5:mkk
6:mkk
Press any key to continue

写完了，可是偶还没解决这个问题
办法想象中。。。

B7层发表时间: 06-04-08 16:25

回复: sniper167 [sniper167]

论坛用户

日哦
又贴不上来
真服了

B8层发表时间: 06-04-21 08:51

回复: sniper167 [sniper167]

论坛用户

修正了重复字符问题还请各位多指点有没有更好的方法
#include <stdio.h>

#include <stdlib.h>

#include <string.h>

int sum = 0; /* 全排列个数 */

int iLength = 0; /* 字符串才长度 */

struct node

{

char *string;

struct node *next;

};

struct node *head, *pCurNode;

void insert(char *pStr)

{

struct node *ptmp;

int i;

char *pCurStr;

pCurStr = (char *)malloc(strlen(pStr) + 1);

strcpy(pCurStr, pStr);

if(sum == 0)

{

ptmp = (struct node *)malloc(sizeof(struct node));

if(ptmp == NULL)

{

printf("malloc error!\n");

return;

}

ptmp->string = pCurStr;

ptmp->next = NULL;

head = ptmp;

pCurNode = head;

sum++;

}

else

{ /* 检查有无重复字符 */

ptmp = head;

for(i=0; i<sum; i++)

{

if(!strcmp(ptmp->string, pCurStr))

{

printf("Have same string: %s\n", pCurStr);

return;

}

ptmp = ptmp->next;

}

/* 无重复字符，插入存储链表 */

ptmp = (struct node *)malloc(sizeof(struct node));

if(ptmp == NULL)

{

printf("malloc error!\n");

return;

}

ptmp->string = pCurStr;

ptmp->next = NULL;

pCurNode->next = ptmp;

pCurNode = ptmp;

sum++;

}

}

/* 把字母从小到大排序 */

void compositor(char *pStr)

{

char temp;

int i, j;

for(i=0; i<iLength-1; i++)

for(j=i+1; j<iLength; j++)

if(pStr[i] > pStr[j])

{

temp = pStr[i];

pStr[i] = pStr[j];

pStr[j] = temp;

}

printf("Now, the string is %s\n", pStr);

}

void Permute(char in[], char out[], int used[], int recursLev)

{

int i;

if(recursLev == iLength)

{

insert(out);

}

for(i = 0; i < iLength; i++)

{

if(used[i]) /* 如果这个字母已经使用，则跳到下一个字母 */

continue;

out[recursLev] = in[i]; /* 把这个字符填充入out序列 */

used[i] = 1; /* 标记这个字母已经被使用 */

Permute(in, out, used, recursLev+1);

used[i] = 0; /* 取消字母标记 */

}

}

int Init(char *inString)

{

int i, *ipUsedFlag;

char *cpOut;

cpOut = (char *)malloc(iLength + 1);

if(!cpOut)

return 0;

cpOut[iLength] = '\0';

ipUsedFlag = (int *)malloc(sizeof(int) * iLength);

if(!ipUsedFlag)

return 0;

for(i = 0; i < iLength; i++) /* 初始化ipUsedFlag */

{

ipUsedFlag[i] = 0;

}

Permute(inString, cpOut, ipUsedFlag, 0);

free(cpOut);

free(ipUsedFlag);

return 1;

}

void main()

{

char Str;

struct node *p;

int i;

printf("Please input the string:\n");

gets(&Str);

iLength = strlen(&Str);

compositor(&Str); /* 可以不要，只是为了好看 */

Init(&Str);

/* 输出所有排列 */

p = head;

for(i = 1; i <=sum; i++)

{

printf("%d : %s\n", i, p->string);

p = p->next;

}

}

B9层发表时间: 06-04-27 12:33