字符串代码总结

╰+攻爆jí腚メ 2023-05-29 06:50 2阅读 0赞

### 文章目录 ###

*   *   *   *  1. 串的存储结构
             *  2. 串的基本操作
             *  3. 简单模式匹配算法
             *  4. KMP算法

#### 1. 串的存储结构 ####

1.  定长存储结构

typedef struct{ 
    	char str[maxSize+1];
    	int length;
    }Str;

1.  变长存储结构

typedef struct{ 
    	char *ch;    //指向动态分配存储区的首地址的字符指针
    	int length;
    }Str;

#### 2. 串的基本操作 ####

1.  赋值操作

int strcopy(Str& str,char *ch){ 
    	if(str.ch)
    		free(str.ch);     //释放原来串空间
    	int len=0;
    	char *c=ch;
    	while(*c){             //求ch串的长度
     		++len;
     		++c;
    	}
    	if(len==0){            //如果ch为空串，则直接返回空串
    		str.ch=0;
    		str.length=0;
    		return 1;
    	}
    	else{ 	
    		str.ch=(char*)malloc(sizeof(char)*(len+1));  //为‘\0’多分配一个空间
    		if(str.ch==NULL)
    			return 0;
    		else
    			c=ch;
    			for(int i=0;i<=len;i++)   //将ch最后的‘\0’赋值到新串中作为结束标记
    				str.ch[i]=*c;
    			str.length=len;
    			return 1;
    	}
    }

1.  串比较操作

int strcompare(Str s1,Str s2){ 
    	for(int i=0;i<s1.length&&i<s2.length;++i)
    		if(s1.ch[i]!=s2.ch[i])
    			return s1.ch[i]-s2.ch[i];
    	return s1.length-s2.length;
    }

1.  串连接操作

int concat(Str& str,Str& s1,Str& s2){ 
    	if(str.ch){ 
    		free(str.ch)
    		str.ch=NULL;
    	}
    	str.ch=(char*)malloc(sizeof(char)*(s1.length+s2.length+1));
    	if(str.ch==NULL)
    		return 0;
    	int i=0;
    	while(i<s1.length){ 
    		str.ch[i]=s1.ch[i];
    		++i;
    	}
    	int j=0;
    	while(j<=s2.length){    //将s2.ch最后的‘\0’一起复制
    		str.ch[i+j]=s2.ch[j];
    		++j;
    	}
    	str.length=s1.length+s2.length;
    	return 1;
    }

1.  求子串

int subStr(Str& substr,Str str,int pos,int len){ 
    	//求str串中从pos位置开始，长度为len的子串，由substr返回
    	if(pos<0||pos>=str.length||len<0||len>str.length)
    		return 0;
    	if(substr.ch){ 
    		free(substr.ch);
    		substr.ch=NULL;
    	}
    	if(len==0){ 
    		substr.ch=NULL;
    		substr.length=0;
    		return 1;
    	}
    	else{ 
    		substr.ch=(char*)malloc(sizeof(char)*(len+1));
    		int i=pos;
    		int j=0;
    		while(i<pos+len)
    			substr.ch[j++]=str.ch[i++];
    		substr.ch[j]='\0';
    		substr.length=len;
    		return 1;
    	}
    }

1.  串清空

int clearStr(Str& str){ 
    	if(str.ch){ 
    		free(str.ch);
    		str.ch=NULL;
    	}
    	str.length=0;
    	return 1;
    }

#### 3. 简单模式匹配算法 ####

int index(Str str,Str substr){ 
    	int i=1,j=1,k=i;
    	while(i<=str.length&&j<=substr.length){ 
    		if(str.ch[i]==substr[j]){ 
    			++i;
    			++j;
    		}
    		else{ 
    			j=1;
    			i=++k;  //匹配失败，i从主串的下一个位置开始，k记录了上一次起始位置
    		}
    	}//while
    	if(j>substr.length)
    		return k;
    	else 
    		return 0;
    }

#### 4. KMP算法 ####

void getNext(Str substr,int next[]){ 
    	int i=1,j=0;
    	next[1]=0;
    	while(i<substr.length){ 
    		if(j==0||substr.ch[i]==substr.ch[j]){ 
    			++i;
    			++j;
    			next[i]=j;
    		}
    		else
    			j=next[j];
    	}//while
    }
    
    int KMP(Str str,Str substr,int next[]){ 
    	int i=1,j=1;
    	while(i<=str.length&&j<substr.length){ 
    		if(j==0||str.ch[i]==substr.ch[j]){ 
    			++i;
    			++j;
    		}
    		else 
    			j=next[j];
    	}//while
    	if(j>substr.length)
    		return i-substr.length;
    	else	
    		return 0;
    }