#include "stdio.h"

void swap(char *c1, char *c2)
{
    *c1 ^= *c2;
    *c2 ^= *c1;
    *c1 ^= *c2;
}

void fun(char array[][3], int len, char *ans)
{
    char c[128]={0};
    int i, j, k=1;
    for (i=0; i<len; i++)
        for (j=0; j<3; j++)
            if (c[array[i][j]] == 0)
                c[array[i][j]] = k++;
    ans[k] = 0;
    k = 0;
    while (1)
    {
        for (i=k; i<len; i++)
        {
            if (c[array[i][0]] > c[array[i][1]])
                swap(&c[array[i][0]], &c[array[i][1]]);
            if (c[array[i][1]] > c[array[i][2]])
                swap(&c[array[i][1]], &c[array[i][2]]);
        }
        for (i=0; i<len; i++)
            if ((c[array[i][0]] > c[array[i][1]]) || (c[array[i][1]] > c[array[i][2]]))
            {
                k = i;
                break;
            }
        if (i == len)
            break;
    }
    for (i=97; i<123; i++) //只考虑 a -- z
        if (c[i] > 0)
            ans[c[i]-1] = i;
}

main()
{
    char str[128]={0};
    char array[][3]={{'t', 's', 'f'}, {'a', 's', 'u'}, {'m', 'a', 'f'}, {'a', 'i', 'n'}, {'s', 'u', 'n'},
                     {'m', 'f', 'u'}, {'a', 't', 'h'}, {'t', 'h', 'i'}, {'h', 'i', 'f'}, {'m', 'h', 'f'},
                     {'a', 'u', 'n'}, {'m', 'a', 't'}, {'f', 'u', 'n'}, {'h', 's', 'n'}, {'a', 'i', 's'},
                     {'m', 's', 'n'}, {'m', 's', 'u'}};
    fun(array, sizeof(array)/sizeof(array[0]), str);
    puts(str);            
   
}

[此贴子已经被作者于2016-12-13 21:36编辑过]

收到的鲜花

• azzbcc 于 2016-12-14 09:27 送鲜花  10朵   附言：all tests runs 0.23ms

增加规则控制，以防挂死。


#include "stdio.h"

void swap(char *c1, char *c2)
{
    *c1 ^= *c2;
    *c2 ^= *c1;
    *c1 ^= *c2;
}

void fun(char array[][3], int len, char *ans)
{
    char c[128]={0};
    int i, j, k=1, m;
    for (i=0; i<len; i++)
        for (j=0; j<3; j++)
            if (c[array[i][j]] == 0)
                c[array[i][j]] = k++;
    ans[k] = 0;
    k = 0;
    for (m=0; m<len; m++)
    {
        for (i=k; i<len; i++)
        {
            if (c[array[i][0]] > c[array[i][1]])
                swap(&c[array[i][0]], &c[array[i][1]]);
            if (c[array[i][1]] > c[array[i][2]])
                swap(&c[array[i][1]], &c[array[i][2]]);
        }
        for (i=0; i<len; i++)
            if ((c[array[i][0]] > c[array[i][1]]) || (c[array[i][1]] > c[array[i][2]]))
            {
                k = i;
                break;
            }
        if (i == len)
            break;
    }
    if (m == len)
    {
        puts("规则自相矛盾，此题无解。");
        return;
    }
    for (i=97; i<123; i++) //只考虑 a -- z
        if (c[i] > 0)
            ans[c[i]-1] = i;
}

main()
{
    char str[128]={0};
    char array[][3]={{'t', 's', 'f'}, {'a', 's', 'u'}, {'m', 'a', 'f'}, {'a', 'i', 'n'}, {'s', 'u', 'n'},
                     {'m', 'f', 'u'}, {'a', 't', 'h'}, {'t', 'h', 'i'}, {'h', 'i', 'f'}, {'m', 'h', 'f'},
                     {'a', 'u', 'n'}, {'m', 'a', 't'}, {'f', 'u', 'n'}, {'h', 's', 'n'}, {'a', 'i', 's'},
                     {'m', 's', 'n'}, {'m', 's', 'u'}};
    fun(array, sizeof(array)/sizeof(array[0]), str);
    puts(str);            
   
}

对这道题的一些体会，不知有无理解错。
题意：
1、假设给定一个字符串"afhimnstu"，并给出这个字符串的字符排队规则（二维数组array）。
2、按排队规则重新排列字符串"afhimnstu"，使得重新排列后的字符串"mathisfun"符合排队规则的要求。
3、输出重新排列后的字符串"mathisfun"。
解题过程：
1、从排队规则数组中获取某一组各字符。
2、按排队规则比较字符串（afhimnstu）中相应的字符是否符合排队规则。
3、如果不符合排队规则，相应的字符就互换位置。
4、重复1--3步骤，直到全部字符符合排队规则为止。
关键技巧：
在按排队规则比较字符时，尽可能优化搜寻字符的效率。
这道题讲到底也是字符搜寻的问题。

[此贴子已经被作者于2016-12-14 09:43编辑过]

可以看一下第20楼的change函数，不止交换两个字符，当然交换并没有错。

[此贴子已经被作者于2016-12-14 09:32编辑过]

加了一组测试数据

[此贴子已经被作者于2016-12-14 10:31编辑过]

只是用交换队列位置方法来处理前后关系，当然也不只是交换两个字符。
不管用什么方法比对，都是按排队规则相关的两个字符的前后关系比对，直到所有的相关字符位置符合其排队规则。
比对效率关键在于搜寻字串的字符，我的代码采用字串数组，不用扫描搜寻字符，点到即得到。

试了一下，是规则控制的问题。
看看最少的控制次数是多少。

修改规则控制，以防挂死。
每组两对，应该用 len*2。

#include "stdio.h"

void swap(char *c1, char *c2)
{
    *c1 ^= *c2;
    *c2 ^= *c1;
    *c1 ^= *c2;
}

void fun(char array[][3], int len, char *ans)
{
    char c[128]={0};
    int i, j, k=1, m;
    for (i=0; i<len; i++)
        for (j=0; j<3; j++)
            if (c[array[i][j]] == 0)
                c[array[i][j]] = k++;
    ans[k] = 0;
    k = 0;
    for (m=0; m<len*2; m++)
    {
        for (i=k; i<len; i++)
        {
            if (c[array[i][0]] > c[array[i][1]])
                swap(&c[array[i][0]], &c[array[i][1]]);
            if (c[array[i][1]] > c[array[i][2]])
                swap(&c[array[i][1]], &c[array[i][2]]);
        }
        for (i=0; i<len; i++)
            if ((c[array[i][0]] > c[array[i][1]]) || (c[array[i][1]] > c[array[i][2]]))
            {
                k = i;
                break;
            }
        if (i == len)
            break;
    }
    if (m == len*2)
    {
        puts("规则自相矛盾，此题无解。");
        return;
    }
    for (i=97; i<123; i++) //只考虑 a -- z
        if (c[i] > 0)
            ans[c[i]-1] = i;
}

main()
{
    char str[128]={0};
    char array[][3]={{'t', 's', 'f'}, {'a', 's', 'u'}, {'m', 'a', 'f'}, {'a', 'i', 'n'}, {'s', 'u', 'n'},
                     {'m', 'f', 'u'}, {'a', 't', 'h'}, {'t', 'h', 'i'}, {'h', 'i', 'f'}, {'m', 'h', 'f'},
                     {'a', 'u', 'n'}, {'m', 'a', 't'}, {'f', 'u', 'n'}, {'h', 's', 'n'}, {'a', 'i', 's'},
                     {'m', 's', 'n'}, {'m', 's', 'u'}};
    fun(array, sizeof(array)/sizeof(array[0]), str);
    puts(str);            
   
}

是len+1次，因为交换最多影响前面len-1组规则，所以第len次交换，必然不会影响

正确性毋庸置疑，我也测试了len+1,吹水佬版主觉得呢

[此贴子已经被作者于2016-12-14 10:46编辑过]