变位词程序的实现

发表于 | 0 comments | 阅读次数

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

问题简述

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

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

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

实现思路

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

将程序分为三个部分：

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

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

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

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

代码实现

sign 程序

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
//
//  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);
    }
}

squash 程序

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
//
//  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
algorithm's logarithm's
anatomicopathological pathologicoanatomical
paradisaically paradisiacally
……

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

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