判定确定能否将一组单词排列在一个列表中，使得任何单词首字母与前面单词尾字母相同：函数canArrangeWords的输入应该包含一个整数num(1<=num<=100)和一个单词阵列arr，阵列元素是由所有小写字母组成的单词。单词长度为2-100之间,可取到2和100。能排列成功，返回1，返回不成功返回-1；

int canArrangeWords(int num,char** arr)
{
    //code.....
    //return the result
}

样例输入： 4 abd def fgg gpjd
输出：1
样例输入： 4 abd fgg def gpjd
输出：1
样例输入： 4 abc cba def gpjd
输出：-1
ACM上的题吧，中兴拿来当模拟测试题了，可是我还不会编呀

[此贴子已经被作者于2016-6-11 17:03编辑过]

补充说明一下，对排好的列表，首尾可以是任何小写字母

我自己的想法是统计N个单词中，除去第i个单词，其他N-1个单词中首字母与第i个单词尾字母相同的单词的个数，如此以来得到一个N个元素的数组，如果能接龙成功，则数组中的0元素个数必须小于等于1，但这只是必要不充分条件....求大家指导一下思路，给出个方法，代码我更希望能自己写，感觉个人的执行力还是不行，看代码能看懂，自己写代码就各种问题，效率差......

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

假如可以排成一行，对于任一个单词而言，其前面或其后面必然可以接另一个单词。
递归算法就是
int canArrangeWords(int num,char** arr)
{
    if( num == 1 )
        return +1;

    for( i=1; i!=num; ++i )
    {
        if( arr[i]可以排在arr[0]前面 )
        {
            int r = canArrangeWords( num-1, arr[i]组合在arr[0]前并剔除掉arr[i] );
            if( r == +1 )
                return 1;
        }
        if( arr[i]可以排在arr[0]后面 )
        {
            int r = canArrangeWords( num-1, arr[i]组合在arr[0]后并剔除掉arr[i] );
            if( r == +1 )
                return 1;
        }
    }
    return -1;
}
当然，用递归效率太差，主要浪费于需要重新制作一个arr数列，可以改为非递归形式，但算法思想一样。

顺便吐槽一下，这些题，都是些Javar儿们搞的，函数原型就很别扭
int canArrangeWords(int num,char** arr)
按C++的风格应该是 bool can_arrange_words( size_t num, const char* arr[] )

下班了，抛砖引玉

#include <vector>
#include <cstring>

bool CanArrangeWords( size_t num, const char* arr[] )
{
    std::vector<size_t> s; // 其中的size_t为下标的两倍，以区分从前面插入还是从后面插入
    char head = arr[0][0];
    char tail = arr[0][strlen(arr[0])-1];
    size_t next = 2; // 为下标的两倍，以区分从前面插入还是从后面插入
    std::vector<bool> used_mark( num );

    while( s.size() < num-1 )
    {
        // 增长
        size_t t = s.size();
        for( size_t i=next; i!=num*2; ++i )
        {
            if( used_mark[i/2] )
                continue;

            if( i%2==0 && arr[i/2][strlen(arr[i/2])-1]==head )
            {
                s.push_back( i );
                head = arr[i/2][0];
                next = 2;
                used_mark[i/2] = true;
                break;
            }

            if( i%2==1 && arr[i/2][0]==tail )
            {
                s.push_back( i );
                tail = arr[i/2][strlen(arr[i/2])-1];
                next = 2;
                used_mark[i/2] = true;
                break;
            }
        }

        // 若无法增长则减短
        if( t == s.size() )
        {
            if( s.empty() )
                return false;

            size_t i = s.back();
            s.pop_back();
            if( i%2 == 0 )
                head = arr[i/2][strlen(arr[i/2])-1];
            else
                tail = arr[i/2][0];
            next = i + 1;
            used_mark[i/2] = false;
        }
    }

    return true;
}

#include <iostream>
using namespace std;

int main( void )
{
    //const char* s[] = { "fgg", "def", "abd", "gpjd" };
    const char* s[] = { "abc", "cba", "def", "gpjd" };

    cout << CanArrangeWords(_countof(s),s) << endl;

    return 0;
}

这题原来在c里做过，我是用递归做的，再次贴出略加修改，供楼主参考（https://bbs.bccn.net/viewthread.php?tid=444997&extra=&page=3）：

#include <stdio.h>
/*
使用方法：首先输入测试数据组数，再输入第一组数据测试字符串个数，再输入第一组相应个数字符串，接下来输入第二组测试字符串个数，再输入第二组相应个数字符串，如：
3
4 abd def fgg gpjd
4 abd fgg def gpjd
4 abc cba def gpjd
*/
#include <stdlib.h>
struct node
{
    int next;
    char *p;
};
int find(node *p,int dp,int l)
{
    int i,j;
    char a;
    for(i=0,j=0;i<l;i++)if(p[i].next >=0)j++;;
    if(j==l-1)return 1;  //如果连成串则返回
    for(i=0;p[dp].p[i];i++);
    a=p[dp].p[i-1];          //找到字符串尾部字符
    for(i=0;i<l;i++)
    {
        if(i!=dp&&p[i].next <0&&p[i].p[0]==a)
        {
            p[dp].next =i;
            if (find(p,i,l))return 1;
            else p[dp].next =-1;
        }
    }
    return 0;
}
void main()
{
    int i,j,n,t;
    char a[1000],*pp;
    node *p;
    for(t=0,scanf("%d",&t);t>0;t--)
    {
        if(scanf("%d",&n))
        {
            if(n>0)
            {
                p=(node*)malloc(sizeof(node)*(n+1));  //申请指针空间
                for(i=0;i<n;i++)
                {
                    scanf("%s",a);
                    for(j=0;a[j];j++);
                    p[i].p=(char*)malloc(j+1);  //申请字符串空间
                    for(;j>=0;j--)p[i].p[j]=a[j];  //拷贝字符串到堆中
                    p[i].next =-1;
                }
                for(i=0;i<n;i++)if(find(p,i,n))break;;
                if(i==n)
                    printf("-1\n");
                else
                    printf("1\n");
                for(i=0;i<n;i++)free(p[i].p);  //释放字符串堆空间
                free(p);    //释放指针空间
            }
        }
    }
}

[此贴子已经被作者于2016-6-13 17:39编辑过]

感谢两们大神