算法竞赛入门经典 第五章（2）排序与检索

5.3.1 6174问题

#include<stdio.h>

int get_next(int x){
    int a,b,n;
    char s[10];
    sprintf(s,"%d",x);
    n=strlen(s);
    // bubbling 得到了从大到小的排序
    for(int i=0; i<n; i++){
        for(int j=i+1; j<n; j++){
            if(s[j]>s[i]){//把大数冒泡放前头
                char t=s[i];
                s[i]=s[j];
                s[j]=t;
            }
        }
    }
    // b > a
    sscanf(s,"%d",&b); // 把字符串打印到b里面（字符串转int）
    // reverse
    for(int i=0; i<n/2; i++){
        char t=s[i];
        s[i]=s[n-1-i];
        s[n-1-i]=t;
    }
    sscanf(s,"%d",&a);
    return b-a;
}

int main(void) {
    int num[2000], count; // num是用来存储所有从input的数演变出来的所有数
    scanf("%d",&num[0]);
    printf("%d",num[0]);
    count = 1; // 计数当前是去到num里面的第几个数
    for(;;){
        num[count]=get_next(num[count-1]); // 当前的演变数是从前一个演变数经过get_next计算得来的
        printf("->%d",num[count]); // 先输出来，再检查是否found，如果found，停止循环和输出
        // 在数组中从头到尾寻找新生成的数，如果已经存在，那么可以停止寻找了
        int found = 0;
        for(int i=0; i<count; i++){
            if(num[i]==num[count]) {found=1;break;}
        }
        if(found) break;
        count++;
    }
    return 0;
}

主要使用了冒泡排序和反转字符串的两个循环技巧，以及采用数组存储每一次出现的数字方便检索是否已经存在。

5.3.2 字母重排

自己写出来的第一种方法如下，判定两个单词之间是否可以重排得到，使用的是将两者按qsort从小到大排序比较是否相等;

#include<stdio.h>
// 字符比较函数
int cmp_char(const void* _a, const void* _b){
    char* a = (char*) _a; // 强制转换类型
    char* b = (char*) _b;
    return *a-*b; // char类型的相减，等于0就是相等，否则不相等
}

char word[2000][15], ans[2000][100];
int main(void) {
    int n=0;
    while(scanf("%s",word[n])!=EOF){
        if(word[n][0]=='*') break;
        n++;
    }
    char temp[15], s[15];
    int i=0;
    while(scanf("%s",s)!=EOF){
        int found=0;
        qsort(s,strlen(s),sizeof(char),cmp_char); // 先对输入进来的字符串快排（方便比较所有字符）
        int first=1; // 处理输出的空格，第一个匹配到字典的前面不用加空格
        for(int j=0;j<n;j++){
            strcpy(temp,word[j]); // 用temp存储word中每个循环的字符串
            qsort(temp,strlen(temp),sizeof(char),cmp_char); // 对temp快排
            if(strcmp(s,temp)==0) { // 比较temp和s
                found = 1;
                if(first) { // 只是为了消除输出首空格
                    first=0;
                } else{
                    strcat(ans[i]," "); 
                }
                strcat(ans[i],word[j]);// 将和s匹配的所有temp放到第i个答案中
            }
        }
        if(!found) strcpy(ans[i],":(");
        i++;
    }
    // 打印结果，直接把ans里面所有的内容输出即可，ans有内容的个数和要求比较的s的个数一样（i个）
    for(int j=0; j<i; j++){
        printf("%sn",ans[j]);
    }
    return 0;
}

采取分析中的第二种方法的代码如下，word本身（单词排序），并且使用了sorted（单词排序+字符排序）：

#include<stdio.h>
// word存储原始输入字符串，每个字符串最大为15个字符，只按单词进行排序
// sorted比word更进一步，对word中所有的单词里的字符也进行排序
char word[1000][15], sorted[1000][15];
// 字符比较函数
int cmp_char(const void* _a, const void* _b){
    char* a = (char*) _a; // 强制转换类型
    char* b = (char*) _b;
    return *a-*b; // char类型的相减，等于0就是相等，否则不相等
}

// 字符串比较函数
int cmp_string(const void* _a, const void* _b){
    char* a = (char*) _a; // 强制类型转换为char*指针，标记字符串的首字符指针(char*) x[0]位置
    char* b = (char*) _b;
    return strcmp(a,b); // 因为可以通过首字符指针(char) x[0]访问整个字符串，所以比较时传入两个指针就行了
}

int main(void) {
    int n=0;
    while(scanf("%s", word[n])!=EOF){
        if(word[n][0]=='*') break;
        n++;
    };
    // 给原本的所有单词用字符串排序
    // 快排，qsort(要排序的数组名（指针）,要排序的数量,每个排序单元的尺寸,比较函数)
    qsort(word,n,sizeof(word[0]),cmp_string);
    
    for(int i=0; i<n; i++){
        strcpy(sorted[i],word[i]);
        // 给所有排序后的字符串里面所有字符从小到大排序
        qsort(sorted[i],strlen(sorted[i]),sizeof(char),cmp_char);
    }
    
    // 接受测试的字符串
    char s[10];
    while(scanf("%s",s)==1){
        // 把输进来的字符串排一遍序
        qsort(s,strlen(s),sizeof(char),cmp_char);
        int found=0;
        for(int i=0; i<n; i++){
            if(strcmp(sorted[i],s)==0){
                found=1;
                printf("%s ",word[i]); //这里不是直接打印s（因为它已经被排序了），而是打印原来的word里面排第i个的word[i]
            }
        }
        if(!found) printf(":(");
        printf("n");
    }
    
    // 为了理解，可以在这里很直观地看到word和sorted分别是如何排序的（可删掉）
    for(int i=0; i<n; i++){
        printf("word[%d]:%st",i,word[i]);
        printf("sorted[%d]:%s",i,sorted[i]);
        printf("n");
    }

    return 0;

输出是这个样子的：

* 最下面stdin是输入