四、串 | 數據結構

一、串數據類型的定義

1、串的定義

串是由零個或者多個字元組成的有限序列。由串中任意個連續字元組成的序列叫做該串的子串，包含子串的串稱為主串。由一個或者多個空格組成的串叫做空格串。

2、串的存儲結構

1）定長順序表示

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

2）變長分配存儲表示

typedef struct { char ch*; int length;}Str;

3、串的基本操作

1）賦值操作

int strassign(Str& str,char*ch){ if(str.ch) free(str.ch); int len=0; char *c=ch; while(c){ len++; c++; } if(0==len){ str.length=0; str.ch=NULL; return 1; }else{ str.ch=(char*)malloc(sizeof(char)*(len+1)); if(str.ch==NULL) return 0;//如果無法正常分配內存（比如len很大的情況下）返回0 else{ int i; for(i=0;i<=len;i++){//末尾的『』也要複製過去 str.ch[i]=ch[i]; } str.length=len; return 1; } }}

2）取串長度操作

int strLength(Str str){ return str.length;}

3）串比較操作

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

4）連接兩個字元串

int concat(Str& s,Str s1,Str s2){ if(s.ch){ free(s.ch); s.ch=NULL; } s.ch=(char*)malloc(sizeof(char)*(s1.length+s2.length+1)); if(NULL==s.ch){//分配內存失敗時 s.length=0; return 0; } int i; for(i=0;i<s1.length;i++){ s.ch[i]=s2.ch[i]; } int j=0; while(j<=s2.length){//將s2的『』一併複製過來 s.ch[i+j]=s2.ch[j]; j++; } s.length=s1.length+s2.length; return 1;}

5）取子串

int substring(Str &substr,Str str,int pos,int len){ if(pos<0||pos>str.length||len<0||pos+len>str.length) return 0; substr.ch=(char*)malloc(sizeof(char)*(len+1)); int i=0; for(;i<len;i++){ substr.ch[i]=str.ch[pos+i]; } substr.ch[i]=; substr.length=len; return 1;}

6）串清空

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

二、串的模式匹配演算法

1、簡單模式匹配

2、KMP演算法

參考：完全理解KMP以及實戰練習

PS：

廣告時間啦~

理工狗不想被人文素養拖後腿？不妨關注微信公眾號：