一、串 （一）、定义个性签名：整个建筑最重要的是地基，地基不稳，地动山摇。而学技术更要扎稳基础，关注我，带你稳扎每一板块邻域的基础。
博客主页：啊四战斗霸的博客
专栏：数据结构（C语言版）
创作不易，走过路过别忘了三连击了哟！！！
关注作者，不仅幸运爆棚，未来更可期！！！
有代码，就有注释！！！
Triple attack(三连击):Comment,Like and Collect—>Attention
串，即字符串（string）是由零个或多个字符组成的有限序列。引号括起来的字符序列是串的值；可以是字母、数字、中文或其他字符；串中字符的个数n称为串的长度。n=0时的串称为空串。
子串：串中任意个连续的字符组成的子序列
主串：包含子串的串
字符在主串中的位置：字符在串中的序号
子串在主串中的位置：子串的第一个字符在主串中的位置
注意：位序从1开始而不是从0开始
空串：M=‘’，是不包含任何字符的串，其长度n为0
空串是任意串的子串；任意串s都是s本身的子串，除s本身外，s的其他子串称为s的真子串。
空格串：N=’ '，由一个或多个空格组成的串，其长度n为空格字符个数；
串是一种特殊的线性表，数据元素之间呈线性关系；通常以“子串”为增删改查的 *** 作对象。
两个串相等当且仅当者两个串的长度相等并且每个对应位置上的字符都相同。
串赋值，将字符串常量cstr赋给串s，即生成其值等于cstr的串s
2、DestroyStr(&s)：销毁串，释放为串s分配的存储空间（回收存储空间）
3、StrCopy(&s,t)：串复制，将串t赋给串s
4、StrEqual(s,t)：判断串是否相等，若两个串相等则返回真；否则返回假
5、StrLen(s)：求串长，返回串s中字符的个数
6、Strcat(s,t)：串连接，返回由两个串s和t连接在一起形成的新串
7、SubStr(s,i,j)：求子串，返回串s中从第i个字符开始的连续j个字符组成的子串
8、InsertStr(s1,i,s2)：子串插入，将串s2插入到串s1的第i个位置，并返回产生的新串
9、DelStr(s,i,j)：子串删除，从串s中删去从第i个字符开始的长度为j的子串，并返回产生的新串
10、RepStr(s,i,j,t)：子串替换，在串s中将第i个字符开始的j个字符构成的子串用串t替换，并返回产生的新串
11、DispStr(s)：串输出，输出串s的所有字符值
12、StrCmp(s,t)：比较 *** 作，若串s>串t，则返回值>0；若串s=串t，则返回值=0；若串s<串t，则返回值<0；
13、IndexStr(s,t)：定位 *** 作（模式匹配），若主串s中存在域串t值相同的子串，则返回它在主串中第一次出现的位置，否则函数值为0
二、串的存储结构 （一）、串的顺序存储1、定长顺序存储表示：用一组地址连续的存储单元存储串值得字符序列，属静态存储方式
#define MaxSize 255 //预定义最大串长为255
//静态数组实现（定长顺序存储）
typedef struct
{
char data[MaxSize]; //每个分量存储一个字符
int length; //串的实际长度
}SqString;
2、堆分配存储表示：用一组地址连续的存储单元存储串值得字符序列，但存储空间是在程序执行过程中动态分配而得。
//动态数组实现（堆分配存储）
typedef struct
{
char *data; //按串长分配存储区，ch指向串的基地址
int length //串的长度
}SdqString;
SdqString s;
s.data=(char *)malloc(MaxSize*sizeof(char));
s.length=0;
什么是引用型参数？可参考专栏：数构（C语言）——第二章、线性表
引用型参数是一个重点！！！一定要会
//将一个字符串常量c（以‘void’字符标识结尾）赋给顺序串，即生成一个其值等于cstr的串s
StrAssign (&SqString ,schar[ cstr])//s为引用型参数 int
{
; ifor
(=i0;[cstr]i!=';'++)i.[
s]data=i[]cstr;i.=
s;length//设置串s的长度i} //串复制，将串t赋给串s
void
由于顺序串是之间采用顺序串本身来表示的，而不是顺序串指针，它的存储空间由 *** 作系统管理，即由 *** 作系统分配其存储空间，并在超出作用域时释放其存储空间。此处不包含销毁串的任何 *** 作。
3、StrCopy(&s,t)：StrCopy
( &,SqString )s//s为引用型参数SqString tint ;
{
for i(
=0i;<.i;t++length)i//复制t的所有字符. [
s]data=i.[t]data;i.=
s.length;t//设置串s的长度length} //判断串是否相等，若两个串相等则返回真；否则返回假
StrEqual
(
bool ,)SqString s=SqString t;
{
bool sameinttrue;
if i(
.!=s.length)t//长度不等时则返回length= ;
sameelsefalsefor
(
=0i;<.i;s++length)iif(
.[s]data!=i.[t]data)i//有一个对应字符不相同时返回= ;
{
samebreakfalse;
}return
;
} sameStrLen(s)
//求串长，返回串s中字符的个数
StrLen
( )returnSqString s.
{
; s}lengthStrcat(s,t)
//串连接，返回由两个串s和t连接在一起形成的新串
(
SqString ,)SqString s;SqString t//定义结果串str
{
SqString strint ;
. i=
str.length+s.length;tforlength(
=0i;<.i;s++length)i//将s.data[0..s.length-1]复制到str. [
str]data=i.[s]data;ifor(
=0i;<.i;t++length)i//将t.data[0..t.length-1]复制到str. [
str.data+s]length=i.[t]data;ireturn;
} str//求子串，返回串s中从第i个字符开始的连续j个字符组成的子串。当参数不正确时返回一个空串
SubStr
(
SqString ,intSqString s,int i)int j;
{
; k//定义结果串
SqString str. =
str0length;if( 设置str为空串
<=0i||.||i>s<length0j||+-i1j.)>sreturnlength;
//参数不正确时返回空串 strfor (
=-k1i;<+k-i1j;++)k//将s.data[0..s.length-1]复制到str. [
str-data+k1i]=.[s]data;k.=
str;lengthreturnj;
} str//子串插入，将串s2插入到串s1的第i个位置，并返回产生的新串。当参数不正确时返回一个空串
InsertStr
(
SqString ,intSqString s1,) iintSqString s2;
{
; j//定义结果串
SqString str. =
str0length;//设置str为空串if (
<=0i||.+i>s11length)//参数不正确时返回空串return ;
for str(
=0j;<-j1i;++)j//将s1.data[0..i-2]复制到str. [
str]data=j.[s1]data;jfor(
=0j;<.j;s2++length)j//将s2.data[0..s2.length-1]复制到str. [
str]data=j.[s2]data;jfor(
=-j1i;<.j;s1++length)j//将s1.data[i-1..s1.length-1]复制到str. [
str.data+s2]length=j.[s1]data;j.=
str.length+s1.length;s2returnlength;
} str//子串删除，从串s中删去从第i个字符开始的长度为j的子串，并返回产生的新串。当参数不正确时返回一个空串
DelStr
(
SqString ,intSqString s,int i)int j;
{
; k//定义结果串
SqString s. =
str0length;//设置str为空串if (
<=0i||.||i>s+length.i+j>s1length)return;
//参数不正确时返回空串 strfor (
=0k;<-k1i;++)k//将s.data[0..i-2]复制到str. [
str]data=k.[s]data;kfor(
=+k-i1j;<.k;s++length)k//将s.data[i+j-1..s.length-1]复制到str. [
str-data]k=j.[s]data;k.=
str.length-s;lengthreturnj;
} str//子串替换，在串s中将第i个字符开始的j个字符构成的子串用串t替换，并返回产生的新串。当参数不正确时返回一个空串
RepStr
(
SqString ,intSqString s,int i,) jintSqString t;
{
; k//定义结果串
SqString str. =
str0length;//设置str为空串if (
<=0i||.||i>s+length-i1j.)>sreturnlength;
//参数不正确时返回空串 strfor (
=0k;<-k1i;++)k//将s.data[0..i-2]复制到str. [
str]data=k.[s]data;kfor(
=0k;<.k;t++length)k//将t.data[0..t.length-1]复制到str. [
str+data-i1k]=.[t]data;kfor(
=+k-i1j;<.k;s++length)k//将s,data[i+j-1..s.length-1]复制到str. [
str.data+t-length]k=j.[s]data;k.=
str.length-s+length.j;treturnlength;
} str//串输出，输出串s的所有字符值
void
DispStr
( )intSqString s;
{
if i(
.0s)length>if(
{
=0i;<.i;s++length)iprintf(
"%c",.[s]data)i;printf(
"\n");}}
StrCmp(s,t)
int
//比较 *** 作，若串s>串t，则返回值>0；若串s=串t，则返回值=0；若串s<串t，则返回值<0；
( ,)SqString sintSqString t;
{
fro i(
=0i;<.i&&s<length.i;t++length)iif(
.[s]data!=i.[t]data)ireturn.
[ s]data-i.[t]data;i//扫描过的所有字符都相同，则长度长的串更大return
.
- s.length;t}lengthIndexStr(s,t)
//定位 *** 作（模式匹配），若主串s中存在域串t值相同的子串，则返回它在主串中第一次出现的位置，否则函数值为0
IndexStr
( ,)SqString sintSqString t=
{
1 i,=StrLenn(),s=StrLenm();t;//定义结果串
SqString strwhile (
<=-i+n1m)SubStr(
{
,,str,s)i;mif(
StrCmp(,)str!=t0)++;
ielse//返回子串在主串中的位置
return ;
} ireturn
0
; //s中不存在与t相等的子串} 串的块链存储表示
typedef
struct：链式方式存储
StrNode char ;
{
//每个节点存一个字符，存储密度低 datastruct StrNode
* ; }next;
typedefLinkStrNodestruct
StrNode char [
{
4 data];//每个节点存多个字符，提高存储密度struct StrNode
* ; }next;
//将一个字符串常量c（以‘void’字符标识结尾）赋给顺序串，即生成一个其值等于cstr的串sLinkStrNodeStrAssign
(
* &,LinkStrNode char[s]) cstrint;*
{
, i*
LinkStrNode ;r=(p*
s)mallocLinkStrNode (sizeof());LinkStrNode=;//r始终指向尾结点
rfors( =
0;i[]!=cstr';'i++)=(i*)
{
pmalloc(LinkStrNode sizeof());=LinkStrNode[];
p->data=cstr;i=;
r->next}p=
rNULLp;
//尾结点的next域置为空
r->next}//销毁串，释放为串s分配的存储空间（回收存储空间）。与销毁头结点单链表运算相同void DestoryStr
(
*
& )*LinkStrNode =,s*
{
LinkStrNode =pre;s//pre指向结点p的前驱节点whilep(s->next!= NULL
)//扫描链串spfree() ;
{
//释放pre节点=pre;//pre、p同步后移一个节点 =
pre;p} free
p(pre->next)
;
//循环结束时p为NULL，pre指向尾结点，释放它}pre//串复制，将串t赋给串svoid StrCopy
(
*
& ,*LinkStrNode )*s=LinkStrNode ,t*
{
LinkStrNode ,p*t->next;=q(*r)
smalloc(LinkStrNode sizeof());=LinkStrNode;//r始终指向尾结点while
r(s!= NULL
)//扫描链串t的所有结点p=(* )
{
qmalloc(LinkStrNode sizeof());=LinkStrNode;//将p节点复制到q节点=
q->data;p->data//将q节点链接到链串s的末尾 =
r->next;q= ;
r}q=
pNULLp->next;
//尾结点的next域置为空
r->next}//若两个串的长度相等且对应位置的字符均相同，则返回真；否则返回假StrEqual (
*
,
bool *)LinkStrNode *s=LinkStrNode ,t*
{
LinkStrNode =p;s->next//p、q分别扫描链串s和t的数据节点whileq(t->next!= NULL
&&!=pNULL&&==q)=;p->data=q->data;
{
p}p->nextif
q(q->next==
NULL
&&==pNULL)//s和t的长度相等且对应位置的字符均相同qreturn;else return
; true}
StrLen(s)
//求串长，返回串s中字符的个数 falseint
StrLen
*
) int=LinkStrNode 0s;
{
//i用于累计数据节点的个数 i*=; //p指向链串s的首结点
LinkStrNode whilep(s->next!= NULL
)//扫描所有数据节点p++;= ;
{
i}return
p;p->next}
Strcat(s,t)
//串连接，返回由两个串s和t连接在一起形成的新串 i*
Strcat
*
LinkStrNode ,*)LinkStrNode *s,LinkStrNode *t=
{
LinkStrNode ;str*,p*s->next;=q(*r)
strmalloc(LinkStrNode sizeof());=LinkStrNode;//r指向结果串的尾结点while
r(str!= NULL
)//用p扫描s的所有数据节点p=(* )
{
qmalloc(LinkStrNode sizeof());=LinkStrNode;//将p结点复制到q结点=
q->data;p->data//将q结点链接到str的末尾 =
r->next;q= ;
r}q=
p;p->nextwhile
(
p!=t->nextNULL
)//用p扫描t的所有数据节点p=(* )
{
qmalloc(LinkStrNode sizeof());=LinkStrNode;//将p结点复制到q结点=
q->data;p->data//将q结点链接到str的末尾 =
r->next;q= ;
r}q=
pNULLp->next;
//尾结点的next域置为空
r->nextreturn;} //求子串，返回串s中从第i个字符开始的连续j个字符组成的子串
* strDelStr
(
*
LinkStrNode ,int,LinkStrNode ints)int i;* j,
{
* k=
LinkStrNode ,str*,p*s->next;=q(*r)
strmalloc(LinkStrNode sizeof());=LinkStrNodeNULL;//设置结果串str为空串
str->next=;//r指向结果串的尾结点 if
r(str<= 0
||StrLengthi()||i><0s||+j-1StrLengthi(j))>return;s//参数不正确时返回空串for
( str= 0
;<k-1;k++i)//将s的co第i个节点开始的j个节点复制到str=k(* )
{
qmalloc(LinkStrNode sizeof());=LinkStrNode;=;
q->data=p->data;
r->next=q;
r}qfor
p(p->next=
0
;<k;++)k//让p指向链串s的第i个数据节点j=k;= NULL
p;p->next//尾结点的next域置为空
r->nextreturn;} //子串插入，将串s2插入到串s1的第i个位置，并返回产生的新串
* strRepStr
(
*
LinkStrNode ,int,LinkStrNode ints,* i)int j;LinkStrNode *t,
{
* k=
LinkStrNode ,str=,p*s->next,p1*t->next;=q(*r)
strmalloc(LinkStrNode sizeof());=LinkStrNodeNULL;//设置结果串str为空串
str->next=;//r指向结果串的尾结点 if
r(str<= 0
||StrLengthi()||i><0s||+j-1StrLengthi(j))>return;s//参数不正确时返回空串for
( str= 0
;<k-1;k++i)//将s的前i-1个数据节点复制到str=k(* )
{
qmalloc(LinkStrNode sizeof());=LinkStrNode;=;
q->data=p->data;
r->next=q;
r}qwhile
p(p->next!=
NULL
)//将t的所有数据节点复制到strp1=(* )
{
qmalloc(LinkStrNode sizeof());=LinkStrNode;=;
q->data=p1->data;
r->next=q;
r}qwhile
p1(p1->next!=
NULL
)=p(*) 将p节点及其后的节点复制到str
{
qmalloc(LinkStrNode sizeof());=LinkStrNode;=;
q->data=p->data;
r->next=q;
r}q=
pNULLp->next;
//尾结点的next域置为空
r->nextreturn;} //子串删除，从串s中删去从第i个字符开始的长度为j的子串，并返回产生的新串
* strDelStr
(
*
LinkStrNode ,int,LinkStrNode ints)int i;* j,
{
* k=
LinkStrNode ,str*,p*s->next;=q(*r)
strmalloc(LinkStrNode sizeof());=LinkStrNodeNULL;//设置结果串str为空串
str->next=;//r指向结果串的尾结点 if
r(str<= 0
||StrLengthi()||i><0s||+j-1StrLengthi(j))>return;s//参数不正确时返回空串for
( str= 0
;<k-1;k++i)//将s的前i-1个数据节点复制到str=k(* )
{
qmalloc(LinkStrNode sizeof());=LinkStrNode;=;
q->data=p->data;
r->next=q;
r}qfor
p(p->next=
0
;<k;++)k//让p沿next跳j个节点j=k;while (
p!=p->nextNULL
)=p(*) 将p节点及其后的节点复制到str
{
qmalloc(LinkStrNode sizeof());=LinkStrNode;=;
q->data=p->data;
r->next=q;
r}q=
pNULLp->next;
//尾结点的next域置为空
r->nextreturn;} //子串替换，在串s中将第i个字符开始的j个字符构成的子串用串t替换，并返回产生的新串
* strRepStr
(
*
LinkStrNode ,int,LinkStrNode ints,* i)int j;LinkStrNode *t,
{
* k=
LinkStrNode ,str=,p*s->next,p1*t->next;=q(*r)
strmalloc(LinkStrNode sizeof());=LinkStrNodeNULL;//设置结果串str为空串
str->next=;//r指向结果串的尾结点 if
r(str<= 0
||StrLengthi()||i><0s||+j-1StrLengthi(j))>return;s//参数不正确时返回空串for
( str= 0
;<k-1;k++i)//将s的前i-1个数据节点复制到str=k(* )
{
qmalloc(LinkStrNode sizeof());=LinkStrNode;=NULL
q->data;p->data=
q->next;=;
r->next=q;
r}qfor
p(p->next=
0
;<k;++)k//让p沿next跳j个节点j=k;while (
p!=p->nextNULL
)//将t的所有数据节点复制到strp1=(* )
{
qmalloc(LinkStrNode sizeof());=LinkStrNode;=NULL
q->data;p1->data=
q->next;=;
r->next=q;
r}qwhile
p1(p1->next!=
NULL
)=p(*) 将p所指节点及其后的节点复制到str
{
qmalloc(LinkStrNode sizeof());=LinkStrNode;=NULL
q->data;p->data=
q->next;=;
r->next=q;
r}q=
pNULLp->next;
//尾结点的next域置为空
r->nextreturn;} //串输出，输出串s的所有字符值
void strDispStr
(
*
) *=LinkStrNode ;s//p指向链串s的首结点
{
LinkStrNode whilep(s->next!= NULL
)//扫描s的所有数据节点pprintf("%c" ,
{
);//输出p结点值=p->data;} printf
p(p->next"\n"
)
;}IndexStr(s,t)intBF
(
模式匹配即子串定位运算：在主串中找到与模式串相同的子串，并返回其所在位置
,：定位 *** 作（模式匹配），若主串s中存在域串t值相同的子串，则返回它在主串中第一次出现的位置，否则函数值为0。
（一）、简单匹配算法（BF算法）使用k来记录当前检查的子串起始位置，只要有一个字符不同，就可以停止检查当前子串；所有对应位置的字符都相同，则匹配成功，返回k
) int=SqString s1SqString t;
{
int k=,=
1 i;kwhilej(<.
&&<i.s)length//两个串都没有扫描完时循环jift(length. [
{
]==s.data[i])t//当前比较的两个字符相同data++j;++ ;
{
i//继续比较后续字符}
jelse//当前比较的两个字符不相同 ++
;
//检查下一个子串 =
{
k;//扫描目的串的i回退 =
i1k; //子串从头开始匹配
j}}if (
.
)
//j超界，表示串t是串s的子串returnj>=t;length//返回t在s中的位置 else
//模式匹配失败 kreturn 0
; }
//教材版代码 intBF
(
,
) int=SqString s0SqString t,
{
= i0;whilej(<.
&&<i.s)length//两个串都没有扫描完时循环jift(length. [
{
]==s.data[i])t//当前比较的两个字符相同data++j;++ ;
{
i//继续比较后续字符}
jelse//当前比较的两个字符不相同 =
-
+ 1
{
i=i0j;//子串从头开始匹配
j}}if (
.
)
//j超界，表示串t是串s的子串returnj>=t(length- .
) ;i//返回t在s中的位置telselength//模式匹配失败return (
- 1
) ;}next数组计算方法next[j]=s的最长相等前后缀长度+1
next[1]=0
若主串长度为n，模式串长度为m，则
1、比较好的情况：每个子串的第1个字符都和模式串不匹配，
匹配成功的最好时间复杂度：O(m)，
匹配失败的最好时间复杂度：O(n-m+1)=O(n-m)=O(n)
2、最坏情况：每个子串的前n-1个字符都和模式串匹配，只有第m个字符不匹配，直到匹配成功/匹配失败最多需要（n-m+1）*m次比较，最坏时间复杂度：O(nm)
//求模式串t的next数组：当模式串的第j个字符匹配失败时，令模式串跳到next[j]再继续匹配
串的前缀：包含第一个字符，且不包含最后一个字符的子串
串的后缀：包含最后一个字符，且不包含第一个字符的子串
int：当第j个字符匹配失败，由前1~j-1个字符组成的串记为s，
则：GetNext，特别的，(
,
int []SqString t)int next=0,
{
= i-1;j//i记录t，j记录t[i]之前与t开头相同的字符个数[0] =
next-1;//设置next[1]的值while(< .
)//循环条件或为jiift(length= -
{
1||j.[]==t.data[i])t//j=-1或比较的字符相等时data++j;//i，j依次移到下一个字符 ++
{
i;//若pi=pj，则next[j+1]=next[j]+1 [
j]=
;
next}ielse//否则令j=next[j]，循环继续j=
[
] ;
j//k回退next}j}int KMP
(
,
) int=SqString s0SqString t,
{
= i0;whilej(<.
&&<i.s)length//两个串都没有扫描完时循环jift(length= -
{
1||j.[]==s.data[i])t//当前比较的两个字符相同data++j;++ ;
{
i//继续比较后续字符}
jelse= [
]
;
j//i不变，j后退next}jif( .
)
//匹配成功returnj>=t(length- .
) ;i//返回t在s中的位置telselength//模式匹配失败return (
- 1
) ;}intGetNext(
,
KMP算法：当子串和模式串不匹配时，主串指针i不回溯，模式串指针j=next[j]算法平均时间复杂度：O(n+m)
3、改进的KMP算法int []SqString t)int nextval=0,
{
= i-1;j[0]=
nextval-1;while(<.
)ifj(t=length-
{
1||j.[]==t.data[i])t++data;j++;
{
iif(
j.[
]!=t.data[i])t[data]j=;
nextvalelsei[]j=
[
nextval]i;}nextvalelsej=[
]
;
j}nextval}jintKMP
(
,
) int[SqString s]SqString t,
{
= nextval0MaxSize,=i0;GetNextj(,)
;whilet(nextval<.
&&<i.s)lengthifj(t=length-
{
1||j.[]==s.data[i])t++data;j++;
{
i}else
j=[
]
;
j}nextvalifj(.
)
return(j>=t-length.
) ;ielsetreturnlength(-
1
) ;}
两万字最详细总结（含代码）数构（C语言）——第二章、线性表
一万五千字全面总结（含代码）数构（C语言）——第三章、栈和队列
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）