管理网站模板下载免费,泰安哪里做网站,dw做网站导航条,网站规划与建设课设报告4.1串类型的定义
1.串#xff1a;#xff08;或字符串#xff09;
串是由多个字符组成的有限序列#xff0c;记作#xff1a;S‘c1c2c3…cn’ (n0)
其中S是串的名字#xff0c;‘c1c2c3…cn’ 是串值 ci是串中字符 n是串的长度#xff0c;表示字符的数目
空串或字符串
串是由多个字符组成的有限序列记作S‘c1c2c3…cn’ (n0)
其中S是串的名字‘c1c2c3…cn’ 是串值 ci是串中字符 n是串的长度表示字符的数目
空串零个字符的串称为空串记作“”空
2.子串
子串串中任意连续字符组成的子序列 主串包含子串的串
注意空串是任意串的子串任意串是他自身的子串。除它本身外一个串的其他子串都是它的真子串
*字符在串中的位置字符在序列中的序号 *子串在串中的位置子串的第一个字符在子串中的位置
3.串相等
两个串长度相等且各个对应位置的字符串都相等时才相等
4.空格串
由一个或多个空格组成的串长度不为0
【串和线性表的区别 1数据对象串的约束对象为字符集 2 串的操作线性表大多以“单个元素”为操作对象串通常以“串的整体”作为操作对象
4.2.1串的表示和实现
【1.定长顺序存储表示 *静态分配为每个串预先分配一个固定长度的存储区域
*用定长数组描述 #define MAXSTRLEN 255 //最大串长 typedef unsigned char SString[MAXSTRLEN1] // 1个单元为 0号单元存放串的长度
【图】
【串的连接
status Concat(SStingT,SString S!,SString S2)
{//用T返回由S1和S2连接而成的新串。若未截断则返回TURE否则返回FALSEif(S1[0]S2[0]MAXSTRLEN)\
{//未截断T[1,...,S1[10]]S1[1,....S1[0]]; //S1[0]表示S1的0号单元里面是串的长度 T[S1[0]1,...,S2[0]S2[0]];T[0]S1[0]S2[0]; //长度之和uncutTURE; //未截断
}else if(S1[0]MAXSTRSIZE)
{//截断T[1,...,S1[10]]S1[1,....S1[0]]; T[S1[0]1,...,MAXSTRLEN]S2[1,...,MAXSTRLEN-S1[0] ]; //装不下只截取了S2的一部分T[0]MAXSTRLEN; uncutFALSE;
}return uncat;
} //Concat
}【求子串
status SubString(SString Sub,SString S,int pos,int len)
{//用sub返回串的第pos个字符起长度为len的子串//其中1posStrLength(S) 且0lenStrLength(S)-pos1if (pos1||posS[0]||len0||lenS[0]-pos1)return ERROR; //不合法Sub[1..len]S[pos..poslen-1]; //从S的第pos位置开始取长度为len的子串
Sub[0]len; //子串的长度
return OK;}【总结 操作特点 1.实现串操作特点的原操作为“字符序列的复制” 2.在操作中当出现串的长度超过MAXSTRLEN时约定用截断法处理
4.2.2串的表示和实现
2.堆分配存储表示
动态分配
仍以一组地址连续的存储单元存放串值字符序列但存储空间是在程序执行过程中动态分配而得的也称为【动态存储分配的顺序表】。用malloc和free来分配和释放
堆分配的存储表示
typedef struct
{char *ch; //地址指向存储空间 按需分配//若是非空串则按串实用长度分配存储区否则ch为NULLint lentgh; //串长度} HString;
串插入
status strInsert(HString S,int pos,HString T)
//在串S的第pos个位置前插入串T
{ int i;if(pos1||posS.length1) //判断合法范围return ERROR;if(T.length) //判断是否为0{if(!(S.ch(char*)realloc(S.ch,(S.lengthT.length)*sizeof(char)))) //S和T的长度之和exit(OVERFLOW); //分配失败溢出for(iS.length-1;ipos-1;--1) //length-1是节点序数因为长度有一个0节点{ S.ch[iT.length]S.ch[i];}for(i0;iT.length-1;i)S.ch[pos-1i]T.ch[i];S.lengthT.length;}return OK;
}
求串长 int StrLength(HString S)
//求串长
{return S.length
}
串比较 int StrCompare(HString S,HString T)
//比较两个串若相等返回0
{int i;for (i0;iS.length iT.length; i)if (S.ch[i]!T.ch[i])return S.ch[i]-T.ch[i];return S.length-T.length;
}串清空
status ClearString(HString S)
//将S清空为空串
{if(S.ch){free(S.ch);S.chNULL;}S.length0;return OK;
}
串连接
status Concat(HString S,HString S1,HString S2){
int j;
if(!(S.ch(char*)malloc((S1.lengthS2.length)*sizeof(char))))exit(OVERFLOW);
for (j0;jS1.length-1;j){S.lengthS1.lengthS2.length;}
for(j0;jS2.length-1;j){ S.ch[S1.lengthj]S2.ch[j];}
return OK;
}
求子串
status StubString(HString Sub,HString S,int pos,int len)
// 用Sub返回串S的dipos个字符开始长度为len的子串
{if(pos1||posS.length||len0||lenS.length-pos1)return ERROR;if(!len) {Sub.cnNULL;Sub.length0;}else{sub.ch(char*)malloc(len*sizeof(char));for(int j0;jlen-1;j){Sub.ch[j]S.ch[pos-1j];}
Sub.lengthlen;
}
return OK;4.3串的模式匹配算法
4.3.1 BF算法
模式匹配 算法
int Index(SString S,SString T,int pos)
{
ipos;j1;
while(iS[0]jT[0]) //判断合法范围{if(S[i]T[j]) {i;j;}else{ii-j2; j1;}}
if(jT[0]) return i-T[0];
else return 0;
}时间复杂度
最好情况 最坏情况
