西交《数据结构》faq（四）
西交《数据结构》FAQ（四）第四章 串
1、串的ADT定义及基本操作
ADT String{
数据对象D={ai I ai∈字符集，i=1,2,...,n,n≥0)
数据关系R={<ai．1,ai>I ai．1,ai∈D，i=2,...,n)
基本操作13个P71
} ADT String
基本操作13个
串赋值StrAssign(＆T,chars)
串复制StrCopy(＆T,S)
判空串StrEmpty(S)
串比较StrCompare(S,T)
求串长StrLength(S)
串清空ClearString(＆S)
串联结Concat(＆T,S1,S2)
取子串StrString
串匹配Index(S,T,pos)
串置换Replace (＆S,pos,T)
串插入StrInsert(＆S,pos,T)
删子串StrDelete(＆S,pos,len)
串销毁DesroySring(＆S)
2、定位函数 Index(S, T, pos )的基本思想及实现。
算法思想逐字符逐位比较S串和T串，不相等时向后移位继续比较，直至匹配，输出i，或到s尾终止。
intIndex (String S,String T,int pos ) {
if ( pos>0 ) {
n=StrLength(S) ; m=StrLength(T) ; i = pos;
while (i<=n-m+1) {
SubString(sub,S,i,m) ;
if (StrCompare(sub,T)!=0) ++i ;
elsereturn i ;
}∥while
}∥if
return 0 ;
} ∥index
3、串的定长顺序存储表示
用定长数组。长出截断!(例，文件／人名8位)
定义ADT存储表示maxstrlen=256 char0位放串长
#define MAXSTRLEN 255
typedefunsigned char SString;
4、串的连接 Concat( &T, S1, S2 )
几种连接情况的讨论 s1 + s2 ( T
① s1.len + s2.len≤maxstrlen
s1, s2全部拼入T
② s1.len< maxstrlen s1.len + s2.len > maxstrlen
s1全部, s2 部分拼入T
③ s1.len= maxstrlen T=S1
算法思想：分情况拼接串。 超长截断
算法 4.2P73
5、求取子串 SubString( &Sub, S, pos, len )
*pos、len的合理性
status SubString (SString &sub,SString S,int pos,int len) {
if ( pos<1‖pos>S ‖len<0‖len>S-pos+1)
return ERROR ;
sub=S ;
sub=len ; return OK ;
}∥SubString
6、串的堆分配存储表示
用一组连续的存储单元存放。
typedefstruct {
char*ch ;
int length ;
}Hstring
通常，C语言中提供的串类型就是以这种存储方式实现的。系统利用函数malloc( )和free( )进行串值空间的动态管理，为每一个新产生的串分配一个存储区，称串值共享的存储空间为“堆”。C语言中的串以一个空字符为结束符，串长是一个隐含值。
这类串操作的实现算法为:先为新生成的串分配一个存储空间，然后进行串值的复制。
7、串插入 StrInsert( HString &S, int pos, Hstring T )算法
status StrInsert (HString &S, int pos,HString T) {
if ( pos<1‖pos>S.length) return ERROR ;
if (T.length) {
if(!(S.ch=(char*)realloc(S.ch,(S.length+T.length)*sizeof(char))))
exit (OVERFLOW) ;
for ( i =S.length-1; i >=pos-1 ; --i )
S.ch[ i +T.length]=S.ch[ i ] ;
S.ch=T.ch;
S.length+=T.length ;
}
return OK ;
}∥StrInsert
8、堆上的其它6个操作
串复制 StrAssign ( HString&T,char*chars )；原T如存在，释放，另存另分。
求串长 Strength ( HStringS )
串比较 StrCompare ( HStringS,HStringT )
串清空 ClearString ( HString&S )
串联接 Concat ( HString&T,HStringS1,HStringS2 )原T如存在，释放，另分，拼S1, S2存入T的store区
取子串 SubString ( HStringS,intpos,intlen )
例：汉字：字码 字模 字库 字号 字体……激光打印一字一K
五笔/全拼16×1632字节
9、串赋值 StrAssingn( HString &T, char*chars )
status StrAssingn( HString &T,char*chars ) {
if( T.ch) free ( T.ch ) ;
for ( i =0, c=chars ; c ; ++ i , ++c ) ; //求长度
if( ! i ){ T.ch=NULL ; T.length=0 ;}
else{
if( ! (T.ch=(char*)malloc( i *sizeof(char))))
exit (OVERFLOW) ;
T.ch[ 0.. i -1]=chars ;
}
T.length= i ;
return OK ;
}∥StrInsert本内容由易百网整理发布
网址 www.openhelp100.com
QQ 515224986
页:
[1]