这篇文章是 读厚《编程珠玑》系列博客 的第 2 篇，主要的内容是《编程珠玑》第二章最后提出的变位词程序的实现。

问题简述

问题来源于《编程珠玑》第二章中最后提出的变位词程序的实现。其中的变位词的概念，在第二章开篇的 C 问题中得到了阐释。

C. 给定一个英语词典，找出其中所有变位词的集合。例如，『pots』，『stop』，『tops』互为变位词，因为每一个单词都可以通过改变其他单词中字母的顺序来得到。

我们所实现的变位词程序需要做的就是：将字典读入，然后找出所有的变位词集合。

实现思路

本文中的思路就按照文章中介绍的进行实现：

将程序分为三个部分：

• sign：读入字典，对单词进行『sign』（计算标识符）。计算标识符的过程就是对单词中的字母进行排序。例如：上述三个单词『pots』，『stop』，『tops』的标识符是相同的，都是『opst』
• sort：将所有具有相同标识符的单词放到一起（这里我们直接使用系统的 sort 程序）
• squash：将具有相同标识符的单词放到一行打印出来

最后，通过管道将三个程序连接起来：

sign < words.txt | sort | squash > gramlist.txt
  

 

  
1
 

最终gramlist.txt中就是我们需要的结果。

代码实现

sign 程序

//
//  sign.c
//  somecode
//
//  Created by 罗远航 on 16/12/2016.
//  Copyright © 2016 罗远航. All rights reserved.
//

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define WORDMAX 100

int charcomp(const void *x, const void *y){ return *(char *)x - *(char *)y;
}

int main(){ char word[WORDMAX], sig[WORDMAX]; while(scanf("%s",word) != EOF){ strcpy(sig, word); qsort(sig, strlen(sig), sizeof(char), charcomp); printf("%s %s\n",sig, word); }
}
  

 

  
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
 

squash 程序

//
//  squash.c
//  somecode
//
//  Created by 罗远航 on 16/12/2016.
//  Copyright © 2016 罗远航. All rights reserved.
//

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define WORDMAX 100

int main()
{ char word[WORDMAX], sig[WORDMAX], oldsig[WORDMAX]; int linenum = 0; strcpy(oldsig, ""); while (scanf("%s %s", sig, word) != EOF) { if (strcmp(oldsig, sig) != 0 && linenum > 0) printf("\n"); strcpy(oldsig, sig); linenum++; printf("%s ", word); } printf("\n"); return 0;
}
  

 

  
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
 

运行结果

运行程序之后，我找到了几个比较长的变位词：

algorithm's logarithm's 
anatomicopathological pathologicoanatomical 
paradisaically paradisiacally 
……
  

 

  
1
  
2
  
3
  
4
 

注：单词表我是在这里下载到的，大概有35万英文单词。

本文的版权归作者 罗远航 所有，采用 Attribution-NonCommercial 3.0 License。任何人可以进行转载、分享，但不可在未经允许的情况下用于商业用途；转载请注明出处。感谢配合！

文章来源: blog.csdn.net，作者：冰水比水冰，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/luoyhang003/article/details/53693340