数据结构之--字符串的处理

左手的ㄟ右手 2022-12-25 06:54 138阅读 0赞

## 题目描述 ##

1、定义字符串S1和S2。  
2、输入字符串S1和S2。  
3、判断S2是否是S1的字串。  
4、打印S2在S1中的起始位置。  
5、从S1中删除S2，打印S1。  
6、用"VER"替换S1（原始输入的S1）中的S2，打印S1。

## 范例 ##

Please input S1 = Foshan University
    Please input S2 = ver
    S2 is a sub-string of S1!
    The position is at 10!
    After delete S2, S1 = Foshan Unisity
    After replace S2, S1 = Foshan UniVERsity

# 考察的知识点：字符串匹配，以及通过覆盖去达到删除字符串，以及插入字符实现替换字符串 #

## 字符串匹配 ##

这个我们就不陌生了，数据结构的书本上就介绍了朴素匹配算法以及朴素算法的改进版本KMP算法  
kmp算法

int strStr(char * haystack, char * needle)
    {
        
        int hl,nl;
        hl=strlen(haystack);
        nl=strlen(needle);
        if(nl==0)
            return 0;
        int next[nl];
        get_next(needle,next);
        for(int i=0,k=0;i<hl;i++){
        
            while(k>0 && haystack[i]!=needle[k])
                k=next[k-1];
            if(haystack[i]==needle[k])
                k++;
            if(k==nl)
                return i-nl+1;
        }
        return -1;
    }
    void get_next(char *needle, int *next)
    {
        
        int l=strlen(needle);
        next[0]=0;
        for(int i=1,k=0;i<l;i++){
        
            while(k>0 && needle[i]!=needle[k])
                k=next[k-1];
            if(needle[i]==needle[k])
                k++;
            next[i]=k;
        }
    }

朴素匹配

int strStr(char * haystack, char * needle){
        
        int len1=strlen(haystack);
        int len2=strlen(needle);
        int flag=0;
        if(len1==0&&len2==0){
        
            return 0;
        }
        int i,j;
        for(i=0;i<len1;i++){
        
            flag=0;
            for(j=0;j<len2;j++){
        
                if(haystack[i+j]!=needle[j]){
        
                    flag=1;
                    break;
                }
            }
            if(flag==0){
        
                return i;
            }
        }
        return -1;
    }

对于还没学过数据结构的小伙伴来说，朴素匹配算法比较容易理解和记忆，虽然kmp的性能更好，但是我还是比较优先选择朴素匹配

## 完整代码 ##

#include "string.h"
    #include "stdio.h"
    #include "stdlib.h"
     
    int strStr(char * haystack, char * needle){
        
        int len1=strlen(haystack);
        int len2=strlen(needle);
        int flag=0;
        if(len1==0&&len2==0){
        
            return 0;
        }
        int i,j;
        for(i=0;i<len1;i++){
        
            flag=0;
            for(j=0;j<len2;j++){
        
                if(haystack[i+j]!=needle[j]){
        
                    flag=1;
                    break;
                }
            }
            if(flag==0){
        
                return i;
            }
        }
        return -1;
    }
    //删除函数
    char * delete(char a[],char b[]){
        
        int i,j,k;
        for(i=0;a[i]!='\0';i++)//遍历a数组
        {
        
            for(j=0;b[j]!='\0';j++)//遍历b数组
            {
        
                if(a[i]==b[j])//如果含有指定字符则开始替换后面字符
                {
        
                    for(k=i;a[k]!='\0';k++)//定义新的变量开始循环赋值
                        a[k]=a[k+1];
                    i--;//下一轮循环会到新赋值的字符位置，继续比较
                }
            }
        }
    //    printf("After delete S2, S1 =%s\n",a);
          return a;
    }
     
    char *insert(char *s1, char *s2, int n) {
        //n是匹配到的下标位置
        int len1 = 0, len2 = 0, j = 0, len3, k = 0;
        char s4[30];
        char *s3 = s4;
        if (s1 == NULL)
            return NULL;
        if (s2 == NULL)
            return s1;
        len1 = strlen(s1);
        len2 = strlen(s2);
     
        if (n > len1)
            return NULL;
        for (int i = 0; i < n; i++) {
        
            j++;
        }
        for (int i = 0; i < len1; i++) {
        
            s4[k++] = s1[i];//实现删除功能后的字符串S1的复制
        }
        for (int i = 0; i < len2; i++)
            s1[j++] = s2[i];//这里是将s1中的s2被需要替换的字符串所覆盖
        for (int i = n; i < len1; i++)
            s1[j++] = s4[i];//这里是将剩余的字符串进行处理
        s1[j] = '\0';
        return s1;
    }
    int main(){
        
        char string1[300];
        char string2[300];
        char _str[3]="VER";
        char string4[90];
        char *new_str=string4;
        printf("Please input S1 = ");
        gets(string1);
        printf("Please input S2 = ");
        gets(string2);
        int n1=strlen(string1);
        int n2=strlen(string2);
        int result=strStr(string1,string2);
        if(result==-1){
        
            printf("not correct");
            exit(0);
        }
        else{
        
            printf("S2 is a sub-string of S1!\nThe position is at %d!\n",result);
        }
     
        * delete(string1,string2);
        printf("After delete S2, S1 = %s\n",string1);
        new_str=insert(string1,"VER",result);
        printf("After replace S2, S1 = %s",new_str);
    }

## 关于替换算法的解释 ##

比如题目中的Foshan University中的ver要替换成VER，不能直接赋值替换，容易忽略细节导致错误，C语言不像面向对象的语言可以用replace函数直接实现字符串的替换，因此本题的思路是将已经实现删除功能的字符串S1进行插入操作便可以直接实现替换功能，相关的说明在注释中已经提及。