编程珠玑(五):寻找变位词

1.前言

最近的天气真的好热,跟随着温度的升高人也莫名的变得容易烦躁。在这炎热的夏日里,什么事情都提不起兴趣!

距离上一篇博文,不知觉间一周的时间就快过去了,最近一周工作异常繁忙,不知觉间学习的计划就被打乱。

其实,做什么事情都是一样–一旦放下就很难再提起。

人生就是和另一个我战斗的过程,为了不被另一个我打败,我决定,今天无论如何也得写的什么。

哪怕只是单纯的代码,也可能会给我带来不一样的筹码!

2.问题描述

今天的问题是关于变位词的,首先来看问题的描述:

给定一本英语单词词典,请找出所有的变位词集。

所谓的变位词是指,组成各个单词的字母完全相同,只是字母排列的顺序不同

比如,pots、stop、tops就是变位词。

3.解决思路

  • 思路一
    对组成单词的字母进行组合,针对每一个组合结果在字典中进行匹配。
    不足:组合的结果太多,存在很多无效的组合。
  • 思路二
    针对每个单词和字典中其他的单词进行比较:先比较单词的长度,长度相同后比较组成字母是否相同。
    不足:比较的次数还是太多。
  • 书中的思路
    对每个单词进行签名(以字母顺序进行排序),这样变位词将具有相同的签名。输出签名相同的单词,就得到了要求的变位词。

4.实现思路

将变位词程序组织成三段式的“管道”结构,前一个程序的输出文件将是下一个程序的输入文件。三段程序如下:

  1. sign:读入字典文件,对单词进行“签名”操作
  2. sort:输入签名后的单词文件,对文件进行排序
  3. squash:将同一个变位词类中的各个单词放到同一行中

下面是对具有六个单词的词典进行操作的流程:

pans                                  anps  pans                                  anps  pans
pots                                  opst   pots                                  anps  snap                                 pans  snap
opt           –》 签名  –》     opt    opt             –》 排序  –》   opt    opt              –》挤压 –》        opt
snap                                  anps  snap                                  opst   pots                                 pots  stop   tops
stop                                  opst   stop                                  opst   stop
tops                                  opst   tops                                  opst   tops

5.代码实现

  1. sign程序
    代码如下:
    #include <stdio.h>#include <stdlib.h>#include <string.h>#define WORDMAX 100int 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 %sn", sig, word);    }    return 0;}
  2. sort程序
    排序程序直接使用系统的sort程序。

  3. squash程序
    挤压程序代码如下:

    #include <stdio.h>#include <stdlib.h>#include <string.h>#define WORDMAX 100int 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;}

5.代码运行

将以上程序编译成可执行程序后,放到同一目录下(同时将测试测试字典文件拷贝到该目录)。

命令行下(windows下,运行cmd)执行如下命令运行程序:

sign < dictionary | sort | squash >gramlist.txt

我在网上找了一个一万五千个的单词文件,放在这里供测试:dictionary

6.一体化代码

上面的程序使用了三段通道。如何使用一个完整的程序实现以上的功能?

下面的程序是参照园友的博文写的程序(地址:http://www.cnblogs.com/seebro/archive/2012/03/01/2375644.html)

使用了临时文件作为中转站。个人感觉这种实现也不是很好(好像stl库中提供了很好的数据结构),感兴趣的可以搜一下看看。

好了,下面是代码:

#include <stdio.h>#include <stdlib.h>#include <string.h>#define WORD_MAX_LENGTH 100#define DIC_NUM 20000/* save word before sign */char word[DIC_NUM][WORD_MAX_LENGTH];/* save word after sign */char word_sign[DIC_NUM][WORD_MAX_LENGTH];char old_world_sign[WORD_MAX_LENGTH];int comp(const void *a,const void *b){    return *(char *)a - *(char *)b; } int str_compare(const void *a,const void *b){    return strcmp((char *)a, (char *)b);}int sign_sort(char* dic){    int index = 0;    int i;    FILE* fp_dic;    FILE* fp_tmp;    fp_dic = fopen(dic,"r");     fp_tmp = fopen("tmp.txt","w");    if (fp_dic == NULL || fp_tmp == NULL)    {        printf("File operator error !n");        return -1;    }    while (fscanf(fp_dic,"%s",word[index]) != EOF)    {        strcpy(word_sign[index], word[index]);        /* sign word */        qsort(word_sign[index], strlen(word_sign[index]),sizeof(char),comp);        strcat(word_sign[index], ": ");        strcat(word_sign[index], word[index]);        index++;    }    /* sign string */    qsort(word_sign, index, sizeof(word_sign[index]),str_compare);    for (i = 0; i < index; i++)    {        fprintf(fp_tmp, "%sn", word_sign[i]);    }    fclose(fp_dic);    fclose(fp_tmp);    return 0;}int squash(char * output){    FILE *fp_tmp;    FILE *fp_output;    int index = 0;    int count = 0;    fp_tmp = fopen("tmp.txt", "r");    fp_output = fopen(output, "w");    if (fp_tmp == NULL || fp_output == NULL)    {        printf("File operation error !n");        return -1;    }    while(fscanf(fp_tmp, "%s %s", word_sign[index], word[index]) != EOF)    {        if (strcmp(old_world_sign, word_sign[index]) != 0 && count > 0)        {            fprintf(fp_output, "n");        }        strcpy(old_world_sign, word_sign[index]);        count++;        fprintf(fp_output, "%s ", word[index++]);    }    fclose(fp_output);    fclose(fp_tmp);    return 0;}int main(){    char dic[WORD_MAX_LENGTH];    char output[WORD_MAX_LENGTH];    printf("please input dic name:");    scanf("%s",dic);    printf("Please input output file:");    scanf("%s", output);    sign_sort(dic);    squash(output);    return 0;}

 

 

本文链接



You must enable javascript to see captcha here!

Copyright © All Rights Reserved · Green Hope Theme by Sivan & schiy · Proudly powered by WordPress

无觅相关文章插件,快速提升流量