XY

没有任何借口
posts - 9, comments - 31, trackbacks - 0, articles - 0
  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

删除字符串中的子串

Posted on 2008-06-04 14:09 路缘 阅读(5516) 评论(14)  编辑 收藏 引用 所属分类: C/C++
题目:
         请编写一个函数,删除一个字符串的一部分。函数原型如下:
               int del_substr(char *str, char const *substr)
         函数首先应判断substr是否出现在str中。如果它并未出现,函数就返回0;如果出现,函数应该把str中位于该子串后面的所有字符复制到该子串的位置,从而删除这个子串,然后函数返回1。如果substr多次出现在str中,函数只删除第1次出现的子串。函数的第2个参数绝不会被修改。
         举个例子,假定str指向ABCDEFG。如果substr指向FGH、CDF或XABC,函数应该返回0,str未作任何修改。但如果substr指向CDE,函数就把str修改为指向ABFG,方法是把F、G和结尾的NUL字节复制到C的位置,然后函数返回1。不论出现什么情况,函数的第2个参数都不应该被修改。
        要求:a.你不应该使用任何用于操纵字符串的库函数(如strcpy, strcmp, 等)。
                    b.函数中的任何地方都不应该使用下标引用。
       一个值得注意的是,空字符串是每个字符串的一个子串,如果字符串中删除一个空字符串不会产生变化。
算法:
#include <stdlib.h>
#include 
<stdio.h>

#define TRUE 1
#define FALSE 0

/*********************************************************
函数声明
*/

int del_substr(char *str, char const *substr);
/*********************************************************
主函数
*/

int main()
{
    
char str1 [] = "aabcdefgh324";
    
char const * str2= "abc";

    printf(
"before delete: %s\n", str1);
    printf(
"will delete che chars: %s\n", str2);
    del_substr(str1, str2);
    printf(
"After delete: %s\n", str1);

    system(
"pause");
    
return 0;
}

/***删除字符串str中包含的子串substr,不进行重复删除*/
int del_substr(char *str, char const *substr)
{
    
char const * subP;
    
char *strP;
    
char *temp;
    
int flag = TRUE;

    strP 
= str;
    
if((!*str) || *substr == '\0')/***如果主串为空或子串为空字符串,则返回*/
        
return FALSE;

    
while(*strP)
    
{        
        temp 
= strP;
        
for(subP=substr; *subP; subP++)
        
{
            
if(*strP == *subP)/***如果当前的主串和子串字符相等*/
            
{
                strP++;/**//***则主串指针向前移一个字符*/
                flag = FALSE;/**//*设置为false,防止后续的主串指针,重复移动*/
                continue;
            }
            
break;
        }

        
        
if(*subP == '\0'/***如果subP指向末尾的'\0'则表示子串匹配成功*/
        
{
            
while(*temp++ = *strP++)/***进行字符复制*/
                ;
/***空语句*/
            
break;
        }

        
if(flag)
            strP
++;
    }

    
return TRUE;
}

说明:
       最先str1的定义为 char *,然而就会出现while(*temp++ = *strP++)语句报错。报错误写入位置 0x00447240 时发生访问冲突,我的理解是因为字符指针temp指向的是字符串常量,不允许进行修改。所以定义为
         char str1 [] 很关键。
       经上网查资料,解释是:
       C++中数据存储区分为五种:
栈、堆(new分配)、自由存储区(malloc分配)、全局/静态变量存储区、常量存储区(不允许修改,除非采用特殊手段)。 字符串这种常量就存在常量区中。全局、静态变量放在静态存储区,而它们是可以被修改的。

Feedback

# re: 删除字符串中的子串[未登录]  回复  更多评论   

2008-06-04 16:11 by raof01
感觉博主对于传参方式(传值)没有理解。
函数原型有错误:无法返回该字符串。感觉下面会好一点:
char* del_substr(char* str, const char * substr);
说不用字符串操作函数,我就hack一把——自己写操纵字符串的库函数,呵呵……:
ssize_t Strlen(const char* str)
{
ssize_t len = 0;
while (*str++) ++len;
return len;
}

int StrCmp(const char* str1, const char* str2, ssize_t len)
{
for (int i = 0; i < len; ++i)
{
if (*(str1 + i) != *(str2 + i))
return (*(str1 + i) - *(str2 + i));
}
return 0;
}

char* del_substr(char* str, const char * substr)
{
char* temp = NULL;
ssize_t len = Strlen(substr);
while (*substr++ && *str++)
{
if (*substr == *str)
{
if (!StrCmp(substr, str, len))
{
temp = str + len;
while (*temp++)
{
*str++ = *temp;
}
break;
}
}
}
return str;
}

# re: 删除字符串中的子串[未登录]  回复  更多评论   

2008-06-04 16:15 by raof01
这几行代码里面有写错误,不知道你看出来了没有?呵呵。希望你能改掉这些错误。

# re: 删除字符串中的子串  回复  更多评论   

2008-06-05 01:41 by passerby
为何不用KMP来比较字符呢

# re: 删除字符串中的子串  回复  更多评论   

2008-06-05 10:13 by 路缘
@raof01
确实有问题,我现把更改的代码贴在下面,但不知为为何说我的方法无法返回字符串,对传参方式没有理解。del_substr(char *str, char const *substr)传递的是主串指针的拷贝,但它和原字符串指针指向的是相同的位置,通过改变所指位置的内容来达到改变原字符串的目的。
 
关于你提供的代码,我修改如下。还是谢谢你的热心回复。让我同时也学了一些东西
char* del_substr(char* str, const char * substr) 

    
char* temp = NULL, *cp = str; 
    ssize_t len 
= Strlen(substr); 
    
while (*str) 
    

        
if (*substr == *str) 
        

            
if (!StrCmp(substr, str, len)) 
            

                temp 
= str + len; 
                
while (*str++ = *temp++
                    ;
                
break
            }
 
        }
 
        str
++;
    }
 
    
return cp; 
}
 
 

# re: 删除字符串中的子串  回复  更多评论   

2008-06-05 13:11 by raof01
@路缘
看来没有唬住你。你的理解是没错的,呵呵。
除了del_substr(),别的还有问题吗?

# re: 删除字符串中的子串  回复  更多评论   

2008-06-05 15:52 by 路缘
看来没有唬住你。你的理解是没错的,呵呵。
除了del_substr(),别的还有问题吗?
--------------------------------------------------------
@raof01,问题我是找不出来了,不过我对比了哈C的库函数,你的代码,
while (*str++) ++len;
不如库函数中的
const char *eos = str;
while( *eos++ )
;
return( eos - str - 1 );
写法效率高。

关于字符串的比较,跟库函数的写法的出入,我还得研究哈一些细节东西,看能不能琢磨出差别的用意。

如果代码中还有其他问题,还望@raof01不吝赐教,谢谢了。

# re: 删除字符串中的子串  回复  更多评论   

2008-06-05 15:54 by 路缘
@passerby
谢谢你,KMP算法大学时学过,谢谢你的提醒,你让我知道事情不是做完那么简单,还得精益求精,我会抽时间,再写一个改进的算法来实现。

# re: 删除字符串中的子串  回复  更多评论   

2008-06-05 17:51 by raof01
@路缘
也没啥问题了——我没有仔细考虑,时间紧,我只拿了5分钟来写这个。

# re: 删除字符串中的子串  回复  更多评论   

2008-07-09 10:20 by chu
效率似乎太低了点

# re: 删除字符串中的子串  回复  更多评论   

2008-12-03 16:33 by 佰锐科技
StrCmp 应该改为StrNCmp

# re: 删除字符串中的子串  回复  更多评论   

2010-01-08 14:30 by ff
if(flag)
strP++;
后少了点吧?没有找到的时候死循环了吧?
加else break;可以解决~

# re: 删除字符串中的子串  回复  更多评论   

2010-01-08 15:03 by ff
char* del_substr(char* str, const char * substr)
{
char* temp = NULL, *cp = str;
ssize_t len = Strlen(substr);
while (*str)
{
if (*substr == *str)
{
if (!StrCmp(substr, str, len))
{
temp = str + len;
while (*str++ = *temp++)
;
break;
}
}
str++;
}
return cp;
} 能删除全部出现的子字符串,但是“如果substr多次出现在str中,函数只删除第1次出现的子串”,这段代码会把重复出现的也删除。。。

# re: 删除字符串中的子串  回复  更多评论   

2010-01-08 15:07 by ff
看错了~~sorry

# re: 删除字符串中的子串  回复  更多评论   

2010-03-13 00:47 by sb
ssize_t是什么类型?

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理