C++实现字母重排算法

《C++实现字母重排算法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、字母重排分析 （这个题目来自刘汝佳算法竞赛入门经典）输入一个字典（用******结尾），然后再输入若干单词w，你都需要在字典中找出所有的w的字母重排后得到的单词，并按照字典序冲销到大的顺序在一行中输出（如果不存在，输出:(）。输入单词之间用空格或则空行隔开，且所有的输入单词都由不草果6个字母组成，注意字典的单词不一定按照字典的书序排列样例输入tarpgivenscorerefundonlytrapworkcarnworkearncoursepepperpart******resconfudrea

2、ptrsettoresuc样例输出scorerefundparttarptrap:(course    看到上面的题目，首先不要害怕，也不要说你的语言功底不好，我告诉你的是不管你现在怎么样，你都要冷静下来，去思考这个问题，你的目的是去解决问不是表示在这个难题面前你有多么的胆怯，知道？你语言不熟悉，你可以google你别的方法不会，你就挖出本体要解决所需要的真正的可信思想。这就ok了，我一之认为，解决一个问题靠的是自己的思维而不是纯正的语言，语言知识工具，而思维方式则是独一无二的。 下面听我分析这

3、道题目1.就题目中要求的输入你的字典而言你需要存储他们。2.你需要对字符串进行比较但是不考虑字母顺序，只要字母相同的就可为在字典中查到但是要按照字符串的大小顺序输出。所以必须要有排序。而且不能用冒泡排序，考虑到速度问题我们采取快速排序，而考虑到实践有限，采用stdlib.h库中的函数qsort来解决，如果这些不会的话就去网上查找资料，谁都是从不会到会的所以这些东西不要担心和着急。3.我想到首先给个提前处理，这样的处理使我们的问题更加简单化，这就是对字典中的字符串进行排序，和对要输入比较的字符串也

4、排序，这样的话他们就位于同一个比较平台，同时它们就具有了可比性。 这是刘汝佳的想法下面来听听我的想法，你先想我们可以发每个字符串中的字符单词换成具体的数字？然后把我们输入的单词也进行换成数字的数字的操作，同时属于同一个单词的数字相加，例如我们可以按照他们本来的ascall中的序列就ok了，eg score s=115c=99o=111r=114e=101所以score数字化之后为540所以我们只需要在单词库中查找所有的单词数字化后是否为540即可。 这样的话就省去排序这么麻烦的函数了。 面对一个

5、问题，不是错乱不堪而是思路万千，这就是任何人之间的差别，也是你能力的体现。  #include#include#include#include#includeintn;charword[2000][10],sorted[2000][10];intcmp_char(constvoid*_a,constvoid*_b){   char*a=(char*)_a;   char*b=(char*)_b;   return*a-*b;}intcmp_string(constvoid*_a,constvoi

6、d*_b){ char*a=(char*)_a; char*b=(char*)_b; returnstrcmp(a,b);}intmain(){   n=0;   for(;;)   {       scanf("%s",word[n]);       if(word[n][0]=='*')break;       n++;   }   qsort(word,n,sizeof(word[0]),cmp_string);   for(inti=0;i

7、(sorted[i],word[i]);       qsort(sorted[i],strlen(sorted[i]),sizeof(char),cmp_char);   }

8、rted[i],s)==0)       {           found=1;           printf("%s",word[i]);       }       if(!found)printf(":(");       printf("");   }