当前位置:首页 » 数据结构精品文章 » 正文

关于串,你知道哪些?

1588 人参与  2018年09月03日 22:37  分类 : 数据结构精品文章  评论

1、串的ADT定义及基本操作

ADT String{

数据对象D={ai I ai∈字符集,i=1,2,...,n,n≥0)

数据关系R={<ai1,ai>I ai1,aiDi=2,...,n)

基本操作13P71

} 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尾终止。

int  Index (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 ;
         else  return i ;
       }∥while
    }∥if
   return 0 ;
} ∥index

3、串的定长顺序存储表示  

用定长数组。长出截断!(例,文件/人名8)

定义ADT存储表示  maxstrlen=256   char[0.255]  0位放串长

#define MAXSTRLEN   255
typedef  unsigned char SString[MAXSTRLEN +1 ];

4、串的连接 Concat( &T, S1, S2 )

几种连接情况的讨论    s1 + s2 à T

 s1.len + s2.lenmaxstrlen

     s1, s2全部拼入T

 s1.len< maxstrlen    s1.len + s2.len > maxstrlen

     s1全部, s2 部分拼入T

 s1.len= maxstrlen     T=S1

算法思想:分情况拼接串。 超长截断 

算法 4.2  P73

5、求取子串 SubString( &Sub, S, pos, len )

*pos、len的合理性
status SubString (SString &sub,SString S,int pos,int len) {
   if ( pos<1‖pos>S[0] ‖len<0‖len>S[0]-pos+1) 
        return ERROR ;
   sub[1..len]=S[pos..pos+len-1] ;
   sub[0]=len ;   return OK ;
 }∥SubString

6、串的堆分配存储表示  

用一组连续的存储单元存放。

typedef  struct {
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[pos-1..pos+T.length-2]=T.ch[0..T.length-1];
       S.length+=T.length ;
      }
    return OK ;
  }∥StrInsert

8、堆上的其它6个操作

串复制 StrAssign ( HString  &T,  char  *chars );原T如存在,释放,另存另分。

求串长 Strength ( HString  S )

串比较 StrCompare ( HString  S,  HString  T )

串清空 ClearString ( HString  &S )

串联接 Concat ( HString  &T,  HString  S1,  HString  S2 )T如存在,释放,另分,拼S1, S2存入Tstore

取子串 SubString ( HString  S,  int  pos,  int  len )

例:汉字:字码 字模 字库 字号 字体……激光打印一字一K

五笔/全拼  16×16  32字节

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[0..i -1] ;
   }
   T.length= i ;
   return OK ;
 }∥StrInsert

来源:我是码农,转载请保留出处和链接!

本文链接:http://www.54manong.com/?id=197

微信号:qq444848023    QQ号:444848023

加入【我是码农】QQ群:864689844(加群验证:我是码农)

<< 上一篇 下一篇 >>

网站分类

标签列表

最近发表

全站首页 | 数据结构 | 区块链| 大数据 | 机器学习 | 物联网和云计算 | 面试笔试

本站资源大部分来自互联网,版权归原作者所有!