注册 登录
编程论坛 C++教室

我想问一下,这个程序应该怎么改才可以得到正确的答案?弄不明白,请各位高手看一看。

棉雨 发布于 2011-04-29 09:09, 1137 次点击
#include"iostream"
#define Max 256
using namespace std;
typedef struct
{
    char ch[Max];
    int lenght;
}
SeqString;
void InitString(SeqString *s)
{
    char ch;
    int i=0;
    while((ch=getchar())!='\n'&&i<Max)
        s->ch[i++]=ch;
    s->lenght=i;
}
int Strlen(SeqString *s)
{
    return (s->lenght);
}
SeqString *substr(SeqString *s,int pos,int len,SeqString *sub)
{
    int i;
    if(pos<1||pos>s->lenght||len<1||len>s->lenght)
    {
        cout<<"error!!"<<endl;
    return NULL;
    }
    for(i=0;i<len;i++)
        sub->ch[i]=s->ch[pos+i-1];
    sub->lenght=len;
    return (sub);
}
int strcmp(SeqString *s,SeqString *t)
{
    int i,j;
    for(i=1,j=1;i<s->lenght,j<t->lenght;)
        {
            if(s->ch[i]==t->ch[j])
            {
                i++;
                j++;
            }
            else
            {
                i=i-j+2;
                j=1;
            }
        }
        if(j>t->lenght)
            return (i-t->lenght+1);   
        else
            return 0;
   
}
void main()
{
    int i,k;
    SeqString *s,*t,*r;
    cout<<"构造一个串s!!"<<endl;
    InitString(s);
    cout<<"构造一个串t!!"<<endl;
    InitString(t);
    cout<<"请输入子串在主串中位置:";
    cin>>i;
    k=strcmp(substr(s,i,Strlen(t),r),t);
    cout<<k;
}
编译时出现这样的警告:
C:\VC++6.0简体中文版 编程工具\cv++6.0\MSDev98\MyProjects\program46\2011.4.29.cpp(62) : warning C4700: local variable 's' used without having been initialized
C:\VC++6.0简体中文版 编程工具\cv++6.0\MSDev98\MyProjects\program46\2011.4.29.cpp(64) : warning C4700: local variable 't' used without having been initialized
C:\VC++6.0简体中文版 编程工具\cv++6.0\MSDev98\MyProjects\program46\2011.4.29.cpp(67) : warning C4700: local variable 'r' used without having been initialized

2011.4.29.obj - 0 error(s), 3 warning(s)
帮忙看一下,谢谢啦。
26 回复
#2
配角2011-04-29 09:30
是不是没有初始化 s,t,r
#3
pangding2011-04-29 09:42
main 函数里改成
SeqString s, t, r;
然后调用的时候用
InitString(&s)
看看行不行。
#4
棉雨2011-04-29 11:49
回复 2楼 配角
嗯,换了就可以了。但还是得不到正确的答案,检查函数,也没觉得哪里错,可是结果总是得到个0,不懂为什么
#5
棉雨2011-04-29 11:50
回复 2楼 配角
嗯,换了就可以了。但还是得不到正确的答案,检查函数,也没觉得哪里错,可是结果总是得到个0,不懂为什么
#6
pangding2011-04-29 12:15
你那个 strcmp 是干什么的?用的算法这么奇怪,i j 又加又减的。
#7
棉雨2011-04-29 12:42
回复 6楼 pangding
就是比较两个字符串的大小。
    for(i=1,j=1;i<=s->lenght,j<=t->lenght;)
        {
            if(s->ch[i-1]==t->ch[j-1])
            {
                i++;
                j++;
            }
            else
            {
                i=i-j+2;
                j=1;
            }
        }
串S和串T的字符一个一个比较,要是对应位置上的字符相同,指针i和指针j就向后移动,继续比较下一个字符。要是不相等,i就要回溯,需要从子串的第一个字符重新比较。
#8
棉雨2011-04-29 12:57
以下是引用棉雨在2011-4-29 12:42:49的发言:

就是比较两个字符串的大小。
    for(i=1,j=1;i<=s->lenght,j<=t->lenght;)
        {
            if(s->ch==t->ch[j-1])
            {
                i++;
                j++;
            }
            else
            {
                i=i-j+2;
                j=1;
            }
        }
串S和串T的字符一个一个比较,要是对应位置上的字符相同,指针i和指针j就向后移动,继续比较下一个字符。要是不相等,i就要回溯,然后子串像右移动一个字符
,再从字串的第一个字符跟主串相比较。
#9
pangding2011-04-29 17:15
就是说只要 t 和 s 的一个子串一样就认为是一样的?

我感觉错的地方挺多的呀。
比如 for 里的终止条件是不是应该是 i<=s->lenght && j<=t->lenght
你应该也知道逗号表达式只有最后一个有意义吧。

还有就是那个 < <= 的问题,不过好像自己经注意到了。

还有就是感觉你这个函数接口设计的不好,你最后返回的值,(如果有子串相等的话)是那个子串的起始位置吧?这个是从0开始计的吗?
而且本来库函数里有 strcmp,你重载到是没事,不过故意让它们做的是不相近的事情,这是一种很差的名字函数的习惯。这其实才是我 6楼 问你的意思。

#10
pangding2011-04-29 17:17
这种东西自己跟踪一会就能发现。调试起来难度不是很大的,自己动手丰衣足食嘛~
#11
棉雨2011-04-29 22:10
回复 9楼 pangding
我们这个学期刚刚开的数据结构课程,有很多东西都不懂,这个程序弄了很久都没有找到错在哪里。
谢谢你的指点。上课的时候再问问老师。
#12
辰星睿2011-04-29 22:16
首先 我不知道你这个代码是想实现什么功能 但是我觉得你的错在这strcmp里的
       if(j>t->lenght)
            return (i-t->lenght+1);   
        else
            return 0;
你这里它始终执行的是else下面的 所以一直出现0 你说说你想输出什么 我在看看
#13
玩出来的代码2011-04-29 22:21
这个与数据结构的关系不大,主要是一些细节与知识点的问题、另外LZ写的程序很难让人明白你要干什么,还非得仔细琢磨下。
你也不写下说明的、
#14
棉雨2011-04-30 10:24
回复 11楼 棉雨
用串的strlen(SeqString *s)(求串长)、strcmp(SeqString *s,SeqString *t)(串的比较)、SubStr(SeqString *s,int pos,int len,SeqString *sub)(求子串)这三个串的基本操作来构造子串定位运算index(SeqString *s,SeqString *t).就是说,用那三个基本操作来实现子串定位操作的算法。
#15
棉雨2011-04-30 10:29
回复 13楼 玩出来的代码
我本来发表之前说要写说明要干什么的,忘记了,发表了才发现没写说明。呵呵,下次一定想好了再发表。
#16
棉雨2011-04-30 10:37
回复 12楼 辰星睿
不好意思,我又回复错了……我是想用串的strlen(SeqString *s)(求串长)、strcmp(SeqString *s,SeqString *t)(串的比较)、SubStr(SeqString *s,int pos,int len,SeqString *sub)(求子串)这三个串的基本操作来构造子串定位运算index(SeqString *s,SeqString *t).就是说,用那三个基本操作来实现子串定位操作的算法。最后输出的是模式串(也就是t串)在主串(串s)第一次出现时的首字符对应串s的位置。
#17
pangding2011-04-30 12:39
返回的位置是从下标0开始计的还是1?就是说如果第一个字符就匹配上了,是返回 0 还是返回 1?
#18
棉雨2011-04-30 18:29
回复 17楼 pangding
如果模式串只有一个字符,而且跟主串的第一个祖父相匹配,我想应该是返回1.
我这里for(i=1,j=1;i<s->lenght,j<t->lenght;)写错了,应该是i<=s->lenght&&j<=t->lenght才对。
#19
辰星睿2011-05-03 00:24
回复 16楼 棉雨
不好意思 很久没上了 我给你改了下 你先自己想想 还不清楚的话再说吧
#include"iostream"
#define Max 256
using namespace std;
typedef struct
{
    char ch[Max];
    int lenght;
}
SeqString;
void InitString(SeqString *s)
{
    char ch;
    int i=0;
    while((ch=getchar())!='\n'&&i<Max)
        s->ch[i++]=ch;
    s->lenght=i;
}
int Strlen(SeqString *s)
{
    return (s->lenght);
}
SeqString *substr(SeqString *s,int pos,int len,SeqString *sub)
{
    int i;
    if(pos<1||pos>s->lenght||len<1||len>s->lenght)
    {
        cout<<"error!!"<<endl;
    return NULL;
    }
    for(i=0;i<len;i++)
        sub->ch[i]=s->ch[pos+i-1];
    sub->lenght=len;
    return (sub);
}
int strcmp(SeqString *s,SeqString *t)
{
    int i,j;
    for(i=0,j=0;i<s->lenght,j<t->lenght;)
        {
            if(s->ch[i]==t->ch[j])
            {
                i++;
                j++;
            }
            else
            {
               
                i++;
            }
        }
    return (i-t->lenght+1);
   
}
void main()
{
    int i,k;
    SeqString s,t,r;
    cout<<"构造一个串s!!"<<endl;
    InitString(&s);
    cout<<"构造一个串t!!"<<endl;
    InitString(&t);
    cout<<"请输入子串在主串中位置:";
    cin>>i;
    if(s.ch[i-1]!=t.ch[0])
    {    cout<<endl<<"位置错误! 输出的是错误数据!!"<<endl;}
    k=strcmp(&s,substr(&s,i,Strlen(&t),&r));
    cout<<k<<endl;
}
#20
辰星睿2011-05-03 00:25
不好意思 很久没上了 我给你改了下 你先自己想想 还不清楚的话再说吧
#include"iostream"
#define Max 256
using namespace std;
typedef struct
{
    char ch[Max];
    int lenght;
}
SeqString;
void InitString(SeqString *s)
{
    char ch;
    int i=0;
    while((ch=getchar())!='\n'&&i<Max)
        s->ch[i++]=ch;
    s->lenght=i;
}
int Strlen(SeqString *s)
{
    return (s->lenght);
}
SeqString *substr(SeqString *s,int pos,int len,SeqString *sub)
{
    int i;
    if(pos<1||pos>s->lenght||len<1||len>s->lenght)
    {
        cout<<"error!!"<<endl;
    return NULL;
    }
    for(i=0;i<len;i++)
        sub->ch[i]=s->ch[pos+i-1];
    sub->lenght=len;
    return (sub);
}
int strcmp(SeqString *s,SeqString *t)
{
    int i,j;
    for(i=0,j=0;i<s->lenght,j<t->lenght;)
        {
            if(s->ch[i]==t->ch[j])
            {
                i++;
                j++;
            }
            else
            {
               
                i++;
            }
        }
    return (i-t->lenght+1);
   
}
void main()
{
    int i,k;
    SeqString s,t,r;
    cout<<"构造一个串s!!"<<endl;
    InitString(&s);
    cout<<"构造一个串t!!"<<endl;
    InitString(&t);
    cout<<"请输入子串在主串中位置:";
    cin>>i;
    if(s.ch[i-1]!=t.ch[0])
    {    cout<<endl<<"位置错误! 输出的是错误数据!!"<<endl;}
    k=strcmp(&s,substr(&s,i,Strlen(&t),&r));
    cout<<k<<endl;
}
#21
棉雨2011-05-03 13:01
回复 20楼 辰星睿
else
  {      
     i++;
   }
我不理解这一句,如果主串跟子串的对应位置上的字符不相等,为什么只是i的值变。可不可以跟我说说为什么这么做,先谢谢了。
#22
辰星睿2011-05-03 17:48
回复 21楼 棉雨
你看啊 加入母串是asdfghjkl  子串是ghjk  i控制母串 j控制子串 现在开始比较 首先比较第一个 a和g不相等 i应该+1,j不变 因为你子串还是该从第一个字母开始比较 除非子串和母串对应上了 就该i j都++ 否则你母串都要和子串的第一个开始比较  其实还可以这样 else{i++;j=0;}因为for()里面开始就j=0了 所以就不必再计较了  你看看是不是这么回事??
#23
辰星睿2011-05-03 17:48
回复 21楼 棉雨
你看啊 加入母串是asdfghjkl  子串是ghjk  i控制母串 j控制子串 现在开始比较 首先比较第一个 a和g不相等 i应该+1,j不变 因为你子串还是该从第一个字母开始比较 除非子串和母串对应上了 就该i j都++ 否则你母串都要和子串的第一个开始比较  其实还可以这样 else{i++;j=0;}因为for()里面开始就j=0了 所以就不必再计较了  你看看是不是这么回事??
#24
棉雨2011-05-03 18:02
回复 23楼 辰星睿
受教了,这个有点像KMP算法。谢谢你~
不好意思哦,这个帖我已经结了,不能给你专家分,下次一定给你。
#25
辰星睿2011-05-03 23:08
回复 24楼 棉雨
不客气 要的是技术 不是分数
#26
棉雨2011-05-03 23:10
回复 23楼 辰星睿
今晚去上选修课的时候,想了一下你写的这个程序。感觉有点不对劲,回来我加了一行:
for(i=0,j=0;i<s->lenght&&j<t->lenght;)
    {
        cout<<"i="<<i<<" "<<"j="<<j<<endl;
            
if(s->ch[i]==t->ch[j])
假设我构造的主串是asdhgsjkdghjsdgh,然后再构造模式串dfgd。就是说,我构造的模式串不跟主串中的任何一个跟模式串长度相同的子串相等,在运行的时候,i的值一次次的增加,但j的值并不是一直为0。
再看看这一行:k=strcmp(&s,substr(&s,i,Strlen(&t),&r));它的意思是,从主串中取跟模式串的长度相同的子串,然后跟主串相比较,strcmp函数中return (i-t->lenght+1);返回子串在主串中第一次出现时的首字母对应主串的位置(这样返回来的值总是正确的)。综合起来看,好像跟模式串的关系不大。因为我编这个程序的目的是求出模式串在主串中第一次出现时,模式串首字符在主串中的位置,而这个程序并没有体现出来。

是我自己在写程序的时候没有弄清楚逻辑,导致你在改的时候虽然算法正确了,但还没有达到目的。还是谢谢你。
#27
辰星睿2011-05-04 08:08
回复 26楼 棉雨
我是这么想你的代码的 可以这么说 你这里只有一个母串 你的子串是通过提取子串的那个函数提出来的 所以不存在在母串中找不到子串的情况 这也是我觉得你那个程序冗余的地方 提取子串了 还有个用户输入子串 基于这种情况 所以我改动的那个代码 这种情况就没考虑 如果非要考虑的话 就在循环那里再加上一些条件代码 就可以了 应该不难  你自己想想吧
1