标题:关于数据结构中找词游戏的问题
只看楼主
玉垒浮云
Rank: 1
等 级:新手上路
帖 子:28
专家分:0
注 册:2012-11-22
结帖率:75%
 问题点数:0 回复次数:3 
关于数据结构中找词游戏的问题
在美国流行一种找词游戏,要求游戏者从一张填满字符的正方形表中,找出所有的英文单词,这些词可以横着读、竖着读、或者斜着读。为这个游戏设计一个算法。
我用的是矩阵,然后准备结合BF算法,可是有个关键问题不会,举个例子,
矩阵
that
what
herh
teru
我现在找her这个单词,应该用for循环来判断,可是怎么跟矩阵中的her来比较是否一样呢?
就是判断if(“her”==?)?该怎么写呢?
求大神帮助
搜索更多相关主题的帖子: 矩阵 正方形 
2013-05-11 22:58
玉垒浮云
Rank: 1
等 级:新手上路
帖 子:28
专家分:0
注 册:2012-11-22
得分:0 
#include<iostream>
#include<fstream>
#include<cstring>
#include<string>
using namespace std;
const int maxrow=20;
const int maxelem=400;
template<class T>
class Triarray
{
public:
    Triarray(int matsize);//构造函数
   // void SeqString(char S[ ], char K[ ]);
    ~Triarray(){}//析构函数
    void putele( T item,int i,int j);//将矩阵元素item存储到i行j列
    void readmat();//矩阵元素输入
    T getele(int i,int j);//取i行j列的元素
    void out();//输出矩阵元素
    bool getij(int i,int j);//判断是否越界
    void BF(T *s,T *t);//模式匹配
    T arr[maxelem];//一维数组,用于储存矩阵元素
    void print(T ch[]);
private:
    int n;//矩阵阶数
    int k;//
   
};
template<class T>
Triarray<T>::Triarray(int matsize)
{
    n=matsize;
}
template<class T>
bool Triarray<T>::getij(int i,int j)
{
    if((i<1||i>n)||(j<1||j>n))
    {cout<<"数组下标越界"<<endl;exit(1);}
    return true;
}
template<class T>
void Triarray<T>::putele(T item,int i,int j)
{
    if(getij(i,j))
    {
        k=(i-1)*n+j;
        arr[k]=item;
    }
    cout<<"k="<<k<<endl;
   
}
template<class T>
void Triarray<T>::readmat()
{
    T item;
    for(int i=1;i<=n;++i)
        for(int j=1;j<=n;++j)
        {
            cin>>item;
            putele(item,i,j);
        }
        
}
template<class T>
T Triarray<T>::getele(int i,int j)
{
    T item;int k1;
    if(getij(i,j))
    {
        k1=(i-1)*n+j;
    }   
    item=arr[k1];
    return item;
}
template<class T>
void Triarray<T>::out()
{
    for(int i=1;i<=n;++i)
    {
        for(int j=1;j<=n;++j)
            cout<<" "<<getele(i,j);
        cout<<endl;
    }
}
//模式匹配算法
template<class T>
void Triarray<T>::BF(T *arr,T *t)
{  
    int i=0,j=0,n,m;      n=strlen(arr);  m=strlen(t);
    while(i<n && j<m)
    {
        if(arr[i]==t[j])
        {  
            i++;   j++;
        }  
        else { i=i-j+1;  j=0;  }  
    }
    if (j>=m)
    {    print(t);cout<<"是";print(arr);cout<<"的子序列"<<endl;}
    else
    {    print(t);cout<<"不是";print(arr);cout<<"子序列"<<endl;}
}
template<class T>
void Triarray<T>::print(T ch[] )
{  
    int n=strlen(ch);
    for (int j=0;j<n;j++)
        cout<<ch[j];
}
void main()
{
    char* s1="this";
    char* s2="two";
    char* s3="fat";
    char* s4="that";
    int n;
    cout<<"输入矩阵阶数"<<endl;
    cin>>n;
    Triarray<char>a(n);
    a.readmat();
    cout<<"输出矩阵"<<endl;
    a.out();
    a.BF(a,s1);

这是我能想到的,但是出错了,而且功能不完善
vc提示的错误是cannot convert parameter 1 from 'class Triarray<char>' to 'char *'
        No user-defined-conversion operator available that can perform this conversion, or the operator cannot be called
执行 cl.exe 时出错.
求大神帮助,其实我的算法也是不对的,要逐行比较才能得到正确结果,可是我却把矩阵转换成一维数组来进行比较,不符合要求的,我真的无力了,求帮助
2013-05-11 23:56
玉垒浮云
Rank: 1
等 级:新手上路
帖 子:28
专家分:0
注 册:2012-11-22
得分:0 
刚才那个稍微修改了一下,错误还是一样的额
#include<iostream>
#include<fstream>
#include<cstring>
#include<string>
using namespace std;
const int maxrow=20;
const int maxelem=400;
template<class T>
class Triarray
{
public:
    Triarray(int matsize);//构造函数
   // void SeqString(char S[ ], char K[ ]);
    ~Triarray(){}//析构函数
    void putele( T item,int i,int j);//将矩阵元素item存储到i行j列
    void readmat();//矩阵元素输入
    T getele(int i,int j);//取i行j列的元素
    void out();//输出矩阵元素
    bool getij(int i,int j);//判断是否越界
    void BF(T s[],T t[]);//模式匹配
    T arr[maxelem];//一维数组,用于储存矩阵元素
    void print(T ch[]);
private:
    int n;//矩阵阶数
    int k;//
   
};
template<class T>
Triarray<T>::Triarray(int matsize)
{
    n=matsize;
}
template<class T>
bool Triarray<T>::getij(int i,int j)
{
    if((i<1||i>n)||(j<1||j>n))
    {cout<<"数组下标越界"<<endl;exit(1);}
    return true;
}
template<class T>
void Triarray<T>::putele(T item,int i,int j)
{
    if(getij(i,j))
    {
        k=(i-1)*n+j;
        arr[k]=item;
    }
    cout<<"k="<<k<<endl;
   
}
template<class T>
void Triarray<T>::readmat()
{
    T item;
    for(int i=1;i<=n;++i)
        for(int j=1;j<=n;++j)
        {
            cin>>item;
            putele(item,i,j);
        }
        
}
template<class T>
T Triarray<T>::getele(int i,int j)
{
    T item;int k1;
    if(getij(i,j))
    {
        k1=(i-1)*n+j;
    }   
    item=arr[k1];
    return item;
}
template<class T>
void Triarray<T>::out()
{
    for(int i=1;i<=n;++i)
    {
        for(int j=1;j<=n;++j)
            cout<<" "<<getele(i,j);
        cout<<endl;
    }
}
//模式匹配算法
template<class T>
void Triarray<T>::BF(T arr[],T t[])
{  
    int i=0,j=0,n,m;      n=strlen(arr);  m=strlen(t);
    while(i<n && j<m)
    {
        if(arr[i]==t[j])
        {  
            i++;   j++;
        }  
        else { i=i-j+1;  j=0;  }  
    }
    if (j>=m)
    {    print(t);cout<<"是";print(arr);cout<<"的子序列"<<endl;}
    else
    {    print(t);cout<<"不是";print(arr);cout<<"子序列"<<endl;}
}
template<class T>
void Triarray<T>::print(T ch[] )
{  
    int n=strlen(ch);
    for (int j=0;j<n;j++)
        cout<<ch[j];
}
void main()
{
    char s1[]="this";
    char s2[]="two";
    char s3[]="fat";
    char s4[]="that";
    int n;
    cout<<"输入矩阵阶数"<<endl;
    cin>>n;
    Triarray<char>a(n);
    a.readmat();
    cout<<"输出矩阵"<<endl;
    a.out();
    a.BF(a,s1);





/*    for(int k=0;k!=n;++k)
    {
        cout<<"输入矩阵元素"<<endl;
        string t;
        getline(cin,t);
        cout<<"line="<<t<<endl;
        if(t=="faus")
                cout<<"找到单词"<<endl;
            else
                cout<<"没有找到单词"<<endl;
        
    }
     string filename;
    cout<<"请输入文件名"<<endl;
    cin>>filename;
    ofstream fout(filename.c_str());
    fout<<"that"<<endl;
    fout<<"whtg"<<endl;
    fout<<"oais"<<endl;
    fout<<"fshu"<<endl;*/
   
    //    fstream fin(filename.c_str());
   
/*    int i,j;
    for(i=1;i<=n;++i)//矩阵输出
    {    for(j=1;j<=n;++j)
    {
        cout<<" "<<a.getele(i,j);
    }
    cout<<endl;
    }
   
    string t;
    char line,h1;
    cout<<"找正对角单词"<<endl;
    cin>>h1;
    for( i=1;i<=n;++i)//正对角元素输出
        for( j=1;j<=n;++j)
        {
            if(j==i)
            {
                cout<<" "<<a.getele(i,j);
                line=a.getele(i,j);
                cout<<"line="<<line<<endl;
               
            }
            cout<<h1<<endl;
            cout<<endl;
        }
        
        
        
        cout<<"找偏对角元素"<<endl;
            string  h2;
        cin>>h2;
        for( i=n;i>=1;--i)//偏对角元素输出
            for( j=1;j<=n;++j)
            {
                if(i==n+1-j)
                    cout<<" "<<a.getele(i,j);
            }
            cout<<endl;*/
            
}
2013-05-11 23:59
玉垒浮云
Rank: 1
等 级:新手上路
帖 子:28
专家分:0
注 册:2012-11-22
得分:0 
三楼下面那段在/*  */里面的不用看了,是我的实验
2013-05-12 00:00



参与讨论请移步原网站贴子:https://bbs.bccn.net/thread-406853-1-1.html




关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.054254 second(s), 8 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved