《算法競賽入門經典》5.32排序與檢索-字母重排，檢索排序
輸入一個字典（用******結尾），然後再輸入若干單詞。每輸入一個單詞w，你都需要在字典中找出所有可以用w的字母重排後得到的單詞，並按照字典序從小到大的順序在一行中輸出（如果不存在，輸出:(）。輸入單詞之間用空格或空行隔開，且所有輸入單詞都由不超過6個小寫字母組成。注意，字典中的單詞不一定按字典序排列。
![]()
1 #include <stdio.h>
2 #include <stdlib.h>
3 #include <string.h>
4 int n;
5 char word[2000][10], sorted[2000][10];
6 //字符比較函數
7 int cmp_char(const void* _a, const void* _b)
8 {
9 char*a = (char*) _a;
10 char*b = (char*) _b;
11 return *a - *b;
12 }
13
14 //字符串比較函數
15 int cmp_string(const void* _a, const void* _b)
16 {
17 char*a = (char*) _a;
18 char*b = (char*) _b;
19 return strcmp(a, b);
20 }
21
22 int main()
23 {
24 n = 0;
25 for(; ;)
26 {
27 scanf("%s", word[n]);
28 if(word[n][0] == '*') break; //遇到結束標志就終止循環
29 n++;
30 }
31 qsort(word, n, sizeof(word[0]), cmp_string); //給所有單詞排序
32 for(int i = 0; i < n; i++)
33 {
34 strcpy(sorted[i], word[i]);
35 qsort(sorted[i], strlen(sorted[i]), sizeof(char), cmp_char);//給每個單詞排序
36 }
37 char s[10];
38 while(scanf("%s", s) == 1) //持續讀到文件結尾
39 {
40 qsort(s, strlen(s), sizeof(char), cmp_char);//給輸入單詞排序
41 int found = 0;
42 for(int i = 0; i < n; i++)
43 if(strcmp(sorted[i], s) == 0)
44 {
45 found = 1;
46 printf("%s", word[i]); //輸出原始單詞，而不是排序後的
47 }
48 if(!found) printf(":(");
49 printf("\n");
50 }
51 return 0;
52 }
View Code
分析：
1.步驟：
第一步：首先在讀入字典後把所有單詞排序（確保字典中單詞按字典序排列），結果保存在sorted數組；
第二步：然後把字典中每個單詞排序（避免每次重排）；
第三步：每讀入一個單詞，把該單詞各個字母排序後就和字典中所有的單詞直接比較，判斷兩個單詞是否可以通過重排得到；
第四步：每遇到一個滿足條件的單詞，則立刻輸出其在字典中的原始單詞。
2.程序使用了<stdlib.h>中的sqort排序函數，雖然用庫函數排序的代碼量並不比冒泡排序法小，但速度快得多。
