变位词解题报告

题目描述:

给定一本英语单词词典,请找出所有的变位词集。
所谓的变位词是指,组成各个单词的字母完全相同,只是字母排列的顺序不同。

处理方法

编码

首先应该对每个单词进行编码,使互为变位词的单词获得相同编码。所以将单词内部进行排序,排序出来完全相同的单词自然便互为变位词。当然还需要保留原有的单词,所以用一个结构体来保存编码前和编码后的两个字符串。

1
2
3
4
typedef struct {
char str[WORD_MAX];
char sign[WORD_MAX];
}signed_str;

排序

为了使互为变位词的单词可以被输出,最好的办法就是将他们聚拢在一起,然后到时输出时只需要在编码相同的情况下平移一段距离便可。所以将这些结构体按照上述编码后的字符串进行排序,最后得到的序列中,互为变位词的单词会被聚拢在一起。

输出

最后只需要遍历一次编码、排序后的结构体,在有重复编码时将原始字符串输出,没有便略过。

完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
/* 变位词求解 */
#include "stdio.h"
#include "stdlib.h"
#include "string.h"
#define WORD_MAX 30
typedef struct {
char str[WORD_MAX];
char sign[WORD_MAX];
}signed_str;
signed_str sstrs[20000];
/*
* 编码
* 将单词内字母排序,让所有变位词都成为同一编码
*/
int sign_compare(const void *x, const void *y){
return *(char *)x - *(char *)y;
}
void sign(signed_str *sstr){
qsort(sstr->sign,strlen(sstr->sign),sizeof(char),sign_compare);
printf("sign %s => %s\n",sstr->str,sstr->sign);
}
/*
* 排序
* 将所有签名进行排序,以便下一步汇总
*/
int _sort_compare(const void *x,const void *y){
return strcmp((*(signed_str *)x).sign,(*(signed_str *)y).sign);
}
void _sort(signed_str *sstr,int len){
qsort(sstr,len,sizeof(signed_str),_sort_compare);
printf("@@@Sort Result@@@\n");
int i;
for(i=0;i<len;i++){
printf("[%d] %s\n",i,sstr[i].sign);
}
printf("@@@@@@@@@@@@@@@@@\n");
}
/*
* 读取字典
* 将字典中的单词读取出来
*/
int read_from_file(char *filename){
FILE *fp = fopen(filename,"rt");
int cnt = 0;
int tmp;
char str[WORD_MAX];
while(!feof(fp)){
fgets(str,WORD_MAX,fp);
str[strlen(str)-2] = 0;
strcpy(sstrs[cnt].str,str);
strcpy(sstrs[cnt].sign,str);
sign(&sstrs[cnt]);
cnt++;
}
/*
while(fscanf(fp,"%s",&str)!=EOF){
strcpy(sstrs[cnt].str,str);
strcpy(sstrs[cnt].sign,str);
sign(&sstrs[cnt]);
cnt++;
}
*/
cnt--;
printf("load finish\n");
fclose(fp);
return cnt;
}
/*
* 打印结果
* 将结果打印出来
*/
int print(signed_str *sstr,int len){
int i;
for(i = 0;i < len - 1;i++){
if(strcmp(sstr[i].sign,sstr[i+1].sign)) continue;
printf("%s => %s",sstr[i].str,sstr[i+1].str);
i = i + 1;
while(!strcmp(sstr[i].sign,sstr[i+1].sign) && i<len-1){
printf(", %s",sstr[i+1].str);
i = i + 1;
}
printf("\n");
}
}
int main(){
int cnt = read_from_file("dictionary.txt");
_sort(sstrs,cnt);
print(sstrs,cnt);
}