Programming Pearls Second Edition
Page 11

Problem C : Given a dictionary of english words,find all sets of anagrams,For instance, “posts”,”stop”and ”tops” are all anagrams of one another because each can be formed by permuting the letters of the others.

按照书上给出的解法,先对每一个单词生成相应的“签名”(“signature”),即把单词中的字母按照字母表的顺序重新排列,例如stop 重新排列成opst , 然后把有相同signature的单词归为一组输出。基本过程如下:

其中sign()函数用于生成每一个单词的”签名“,如何生成呢?由于每个单词的长度一般都很短(不超过10个字母)于是可选择用直接插入排序法。其他的数据结构和函数很简单,直接看代码吧!

001 /* Programming Pearls Second Edition
002  * Page 11, Problem C
003  * Wang Runzhen 2011-1-26
004  */
005 
006 #include<stdio.h>
007 #include<string.h>
008 
009 #define MAX_WORD  100 /* the max length of a word */
010 #define MAX_NUM   100 /* the max number of words in a dictionary */
011 struct Word{
012     char ch[MAX_WORD];/*a word*/
013     char sig[MAX_WORD];/*signature*/
014     int flag;/*has been print or not*/
015 };
016 struct Word dic[MAX_NUM];
017 
018 /*put in*/
019 int  putin();
020 void putout(int count);
021 /*generate a word’s signature */
022 void sign(int count);
023 void insertSort(char * arr,int left,int right);
024 
025 /* main() */
026 int main(void)
027 {
028     int count;
029     int i;
030     count=putin();
031     sign(count);
032     putout(count);
033     return 0;
034 }
035 
036 int putin()
037 {
038     int c=0;
039     while(scanf(“%s”,dic[c].ch)!=EOF)
040     {
041         strcpy(dic[c].sig,dic[c].ch);
042         dic[c].flag=0;
043         c++;
044     }
045     return c;
046 }
047 
048 void sign(int count)
049 {
050     int cnt,i,len;
051     for(cnt=0;cnt<count;cnt++)
052     {
053         len=strlen(dic[cnt].ch);
054         insertSort(dic[cnt].sig,0,len);
055         dic[cnt].sig[len]=‘\0’;
056     }
057 }
058 
059 void insertSort (char * arr,int left,int right)
060 {
061     int i,j;
062     char temp;
063     for(i=left+1;i<right;i++)
064     {
065         if(arr[i1]>arr[i])
066         {
067             temp=arr[i];
068             j=i1;
069             do
070             {
071                 arr[j+1]=arr[j];
072                 j;
073             }while(j>=left && arr[j]<temp);
074             arr[j+1]=temp;
075         }
076     }
077 }/* insertSort */
078 
079 void putout(int cnt)
080 {
081     int i,j;
082 
083     for(i=0;i<cnt;i++)
084     {
085         if(dic[i].flag==0)
086         {
087             printf(“———-%s———-\n,dic[i].sig);
088             printf(“%s\n,dic[i].ch);
089             dic[i].flag=1;
090 
091             for(j=0;j<cnt;j++)
092             {
093                 if(strcmp(dic[i].sig,dic[j].sig)==0&&dic[j].flag==0)
094                 {
095                     dic[j].flag=1;
096                     printf(“%s\n,dic[j].ch);
097                 }
098             }
099         }
100     }
101 
102 }
Tags: . 6,426 views
Home

6 Comments so far

Trackbacks/Pingbacks

Leave a comment

Name(required)
Mail (required),(will not be published)
Website(recommended)

Fields in bold are required. Email addresses are never published or distributed.

Some HTML code is allowed:
<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>
URLs must be fully qualified (eg: http://blog.nlogn.cn),and all tags must be properly closed.

Line breaks and paragraphs are automatically converted.

Please keep comments relevant. Off-topic, offensive or inappropriate comments may be edited or removed.