完善如下函数：

// 根据二维数组求出字符串，通过ans指针返回数据
void fun(char array[][3], int len, char *ans) {}

example:

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);   // mathisfun

给个算法就行，当然有代码最好，要求时间限制，我试过全排列runtime error

补充一下：字符串不含重复字母，数据保证有唯一解

项目：

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

先取第一个t，有大于t的吗，a大于t，有大于a的吗，……，最后就得到第一个字母，依此类推
效率不高，但代码简单

遍历一次，大于a的存数组，大于b的存数组，…
没有大于的就是第一个字母，然后在各数组中去掉第一个字母，……

void fun(char array[][3], int len, char *ans)
{
    ans[0]=array[0][0];
    ans[1]=array[0][1];
    ans[2]=array[0][2];        //将前三个元素先按顺序放进数组
    for(int i=1;i<len;i++)      //嵌套循环的作用是取出新的元素与已经放入的元素比较，有相同的就做flag标记，
    {                           //再处理，没有相同的就把该字母放在相邻位置上，其余各各字母依次移位，对于同一组的字母排列由flag来判断，判断是否要交换
        for(int j=0;j<3;j++)
        {
            ...
        {
    }
}

这题有点挑战性！大凡在算法上有点打哽的题目我就想到了递归。我也考虑过权值，但实际上权值还是要统计一遍要统计字符的前面的字符个数，还要一个临时字符数组存储统计字符的前面所有不重复的字符，不符合题主给出的函数原型，因此我就Pass掉了这个思路，用递归解决的代码如下（未做极端测试，可能有漏洞，感觉代码还能优化）：

#include<stdio.h>
int findchar(char *s,char c)
{//查找字符是否出现过，出现过则返回出现位置+1，否则返回0
    int i;
    for(i=0;s[i]&&s[i]!=c;i++);
    if(!s[i])i=0;
    else i++;
    return i;
}

void fun(char a[][3], char* s,int len)
{
    int i,j,l,p;
    for(l=0;s[l];l++);
    l--;   //定位到字符串里最后一个字符
    for(i=0;i<len;i++)
    {
        for(j=1;j<3;j++)
        {
            if(s[l]==a[i][j])
            {
                p=findchar(s,a[i][j-1]);
                if(!p)
                {
                    s[l]=a[i][j-1];
                    fun(a,s,len);  //递归查找该字符前面的一个不在字符串中的字符
                }
            }
        }
    }

}

int main()
{
    char str[128];
    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'}};
    int len,i,j,l;
    len=sizeof(array)/3;
    str[0]=0;
    for(i=0;i<len;i++)
    {
        for(j=0;j<3;j++)
        {
            if(!findchar(str,array[i][j]))  
            { //遍历字符数组，如果相应位置的字符在字符串中不存在则调用递归找到这个字符对应其最前面的一个不在字符串中的字符
                for(l=0;str[l];l++);
                str[l]=array[i][j];
                str[l+1]=0;
                fun(array,str,len);
                if(str[l]!=array[i][j])j--;  //2016-12-16修正此bug
            }
        }
    }
    printf("%s\n",str);
    return 0;
}

[此贴子已经被作者于2016-12-16 08:38编辑过]

今天又想到了另一个算法，感觉这个算法好理解多了，提出来和各位大神分享：这个算法的原理很简单，排在第一位的字母不可能出现在第二位，如字母'm'，永远只会出现在字符数组的array[n][0]的位置，如果我不断地消除array[n][0]位置的字母，并将后面字母前移，那么最终我一定会得到该字符串的所有顺序，就这么简单。
实现该算法的代码如下，也是递归实现的，已通过验证：

#include<stdio.h>
void fun(char a[][3], char* s,int len)
{
    int i,j,k,l;
    for(i=0;i<len&&!a[i][0];i++);
    if (i==len)return;
    for(;i<len;i++)
    {
        for(j=i+1;j<len&&a[i][0]!=a[j][1]&&a[i][0]!=a[j][2];j++);
        if(j==len)
        {
            for(l=0;s[l];l++);
            s[l]=a[i][0];
            s[l+1]=0;
            for(j=i;j<len;j++)
            {
                if(s[l]==a[j][0])
                {
                    a[j][0]=a[j][1];
                    a[j][1]=a[j][2];
                    a[j][2]=0;
                }
            }
            fun(a,s,len);
        }
    }
}

int main()
{
    char str[128];
    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'}};
    int len,i,j,l;
    len=sizeof(array)/3;
    str[0]=0;
    fun(array,str,len);
    printf("%s\n",str);
    return 0;
}

发现7楼代码一个小瑕疵，尽管这个bug永远不会造成危害，仍觉得需要完善。main函数找到最前面的一个未出现的字符后，如果该字符不是当前字符数组的字符，需要j--下，重新对这个字符找下它最前面的未出现的字符，如第一次array[0][0]='t'，执行递归后找到第一个字符'm'，原代码会循环过去，找array[0][1]='s'的最前面的字符，虽然会找到正确的字符'a'，但实际上't'前面的字符还没有找完，如果字符数组后面不再出现't'的话，可能造成错误（尽管不可能不再出现），所以为安全起见，在main函数语句fun(array,str,len);后面加一句if(str[l]!=array[i][j])j--;确保穷尽某单个字符前面的所有字符再循环后面的。

[此贴子已经被作者于2016-12-11 16:30编辑过]

收到的鲜花

• azzbcc 于 2016-12-12 10:55 送鲜花  10朵   附言：all tests runs 0.63ms
• azzbcc 于 2016-12-12 11:49 送鲜花  -5朵   附言：鉴于楼下的错误，加了一组测试数据，结果这 ...
• azzbcc 于 2016-12-12 13:28 送鲜花  5朵   附言：数据的问题，重新测试可以运行
• azzbcc 于 2016-12-14 09:56 送鲜花  -5朵   附言：又加数据了。。。

#include <stdio.h>
#include <string.h>
#define LEN sizeof(array)
void swap(char *sr,char ch,int a,int b);

int main()
{
    char sr[128],as[26],temh,teme,temh1,teme1;
    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'}};
     //char array[][3]={{'d','e','f'},{'a','b','c'},{'b','d','e'},{'c','d','f'}};
     //char array[][3]={{'c','d','e'},{'a','b','c'}};
     int m,j=1,i;
     char *p=&array[0][0];
     memset(as,0,26);
     sr[0]=array[0][0];
     sr[1]=0;
     /*将array里重复出现的字符去掉*/
     while(j<LEN)        
     {
         temh=p[j];
        int fla=1;
        i=0;
        while(sr[i])
        {
            if(sr[i++]==temh)
            {
                fla=0;
                break;
            }
        }
        if(fla)
        {
            sr[i++]=temh;
            sr[i]=0;
        }
        ++j;
     }
     i=0;
     j=strlen(sr)-1;
     /*得到的数组sr通过array进行排序*/
     while(i<j)
     {
         temh1=temh=sr[i];
         teme1=teme=sr[j];
         m=LEN/3;
         while(m--)
         {
             for(int k=0;k<LEN;k+=3)
             {
                 if(!(as[p[k]-'a']))
                 {
                     if(temh==p[k+1]||temh==p[k+2]) temh=p[k];
                 }
                else if(!(as[p[k+1]-'a']))
                {
                    if(temh==p[k+2]) temh=p[k+1];
                }
               
                 if(!(as[p[k+2]-'a']))   
                 {
                         if(teme==p[k]||teme==p[k+1])  teme=p[k+2];     
                 }
                else if(!(as[p[k+1]-'a']))
                {
                        if(teme==p[k]) teme=p[k+1];
                }   
             }
             if(temh==temh1&&teme==teme1)  break;
             temh1=temh;
             teme1=teme;
         }
         
         int k=i,e=j;         
         while(temh!=sr[k]) ++k;
         swap(sr,temh,k,i);         
         while(teme!=sr[e]) --e;
         swap(sr,teme,e,j);
         
         as[temh-'a']=1;        //标记
         as[teme-'a']=1;        
         ++i;
         --j;
     }
     puts(sr);
    return 0;
}

void swap(char *sr,char ch,int a,int b)
{
    sr[a]=sr[b];
    sr[b]=ch;
}

[此贴子已经被作者于2016-12-16 12:41编辑过]

怎么总是多了个字母y？我跟踪了，在去掉重复出现的字符的循环后出现，应该把while(j<=n)的等于号去掉。

忙了一个通宵，终于弄出了这个东东，看看运行效率如何~~~~没时间慢慢写注释了，慢慢看，看看能不能看得懂~

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define LEN sizeof(Node)

typedef struct Node
{
    char str[27]; 
    int num;
    struct Node *next;
}Node;
static Node *head=NULL;

void check(char a[][3],int n)
{
    Node *p=(Node*)malloc(LEN);
    char *ps=a[0];
    int AS[26]={0};

    p->str[0]=*ps;
    p->str[1]='\0';
    p->num=1;
    AS[*ps-'a']++;
    ++ps;

    for (head=p;ps-a[0]<n;++ps)
    {
        if(++AS[*ps-'a']==1)
        {
            p=p->next=malloc(LEN);
            p->str[0]=*ps;
            p->str[1]='\0';
            p->num=1;

        }
    }

    p->next=head;    //这里用了环链表
}
void input()
{
    Node *p=head;

    do
    {
        printf("%s %d\n",p->str,p->num);
        p=p->next;
    }while (p!=head);
}

void change(char array[][3],Node *p,int sizarray)
{
    char *ps=array[0];
    int AS[26]={0};
    int i=1;
    int n=0;

    AS[p->str[0]-'a']=1;

    do
    {
        ps=memchr(ps,p->str[0],sizarray-(ps-array[0]));

        if (ps==NULL)
            break;

        n=(ps-array[0])%3;

        while (n)
        {
            if (AS[*(ps-n)-'a']!=0)
            {
                n--;
                continue;
            }

            p->str[i]=*(ps-n);
            p->str[++i]='\0';
            p->num++;

            ++AS[*(ps-n)-'a'];

            n--;
        }

        ++ps;
    }while (sizarray-(ps-array[0])>0);

    if (p->next!=head)
        change(array,p->next,sizarray);
}

void fun(char ABC[])
{
    Node *p1=head;
    Node *p2=NULL;
    char *ps=ABC;

    while (p1->next!=p1)  //类约瑟夫环框架
    {
        if (p1->num==1)
        {
            *ps=p1->str[0];
            p2=p1;

            do
            {
                if (strchr(p1->next->str,p2->str[0]))
                    p1->next->num--;

                p1=p1->next;

            }while (p1->next!=p2);

            p1->next=p2->next;

            free(p2);

            ++ps;
        }

        p1=p1->next;
    }

    *ps=p1->str[0];  //读入最后一个字符

    *(ps+1)='\0';  //虽然初始化时已经清零，但习惯还是写一下

    free(p1);
}

int main()
{
     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'}};

     char ABC[27]={0};

     Node *p=NULL;

     check(array,sizeof(array));

     p=head;

     change(array,p,sizeof(array));

     input();    //这是个输出说明

     fun(ABC);

     printf("\n%s\n\n",ABC);

     return 0;
}

原贴change函数在memchr处用了strchr，可能会导致ps指向地址超出二维数组，现已更正~在这里可以看出用strchr和memchr的区别,在这里用memchr更可靠

[此贴子已经被作者于2016-12-16 12:44编辑过]

收到的鲜花

• azzbcc 于 2016-12-12 14:03 送鲜花  10朵   附言：all tests runs 0.30ms
• azzbcc 于 2016-12-14 10:00 送鲜花  -5朵   附言：加了一组测试数据

7
t u p
w h i
t s u
a t s
h a p
t i s
w h s
whatisup

这组数据没过

201612121331改
数据出错，此层作废


原内容如下
====

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