XY

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

删除字符串中的子串

Posted on 2008-06-04 14:09 路缘 阅读(6544) 评论(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是什么类型？

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理