幻灯片课件--第4章串.ppt

第 4 章 串 ;4.1 串的逻辑结构;*; 零个字符的串称为空串 (null string)，它的长度为零。为了清楚起见，以后我们用 “?” 来表示空串。;*; 如果在程序设计语言中，串只是作为输入或者输出的常量出现，则只需要存储此串的串值，即字符序列即可。但是在多数非数值处理的程序中，串也以变量的形式出现。串有 3 种机内表示方法。; 串的定长顺序存储表示类似于线性表的顺序存储结构，用一组地址连续的存储单元存储串值的字符序列。在串的定长顺序存储结构中，按照予定义的大小，为每个定长的串变量分配一个固定长度的存储区，则可以用定长数组描述。; 1. 定长顺序存储表示; (1) 串联接 StrCat(SString *s,SString t);s.len+t.len≤MAXSTRLEN 得到的 串是正确的结果。;strCat( SString *s, SString t) /* 用 s返回由 s和 t联接而成的新串。如果没有截断，则返回1，否则返回 0。*/; else if (s-len MAXLEN ) { // 截断t for (i-s-len; iMAXLEN; i++) s-ch[i]= t.ch [i-s-len]; s-len=MAXLEN; flag=0; }; (2) 求子串 SubString ( Sub, S, pos, len );SubString ( SString *Sub, SString S, int pos, int len) //用 Sub 返回串 S 的下标 pos 起长度为 len 的子串。;StrIndex (SString S, int pos, SString t) /* 求从主串s的下标pos起,串t第一次出现的位置, 成功返回位置序号,不成功返回-1*/; 堆分配存储表示的特点是，仍然以一组地址连续的存储单元存储串值的字符序列，但是它们的存储空间是在程序执行过程中动态分配而得的。;1. 堆分配存储表示;StrAssign ( HString *s , char *tral ) // 串常量 tral的值赋给堆串s */ { int len, i=0; if (s-ch!=NULL ) free (s-ch); //释放 s原有空间 While (tral [i]!=‘\0’) i++; //求 tral的长度 i len=i; if ( ! len) {s-ch = NULL; s- len = 0; } // 串 tral为空串 else { s-ch = ( char * ) malloc (len) ; if ( s-ch=NULL) return(0); for(i=0; ilen; i++) s-ch[i]=tral[i]; } return (1); } /* StrAssign*/ ;(2) 求串长;(3) 串比较;(4) 清空串;StrInsert ( HString *s, int pos, HString *t) /*在串 s的第 pos 个字符之前插入串 t。*/ { if ( pos 0|| pos s-len) return ERROR; if (t-len ) { // 如果 T 非空，则重新分配空间，插入t if ( ! (s-ch = ( char * ) realloc (s-ch, (s-len +t-.len )) return (FALSE); //存储分配失败 for ( i = s-len-1; i = pos-1; i-- ) /*为插入 T 而腾出位置*/ s-ch[ i+t-len ] = s-ch[ i ]; for(i=pos-1;ipos+t-len-1;i++) s-ch[i]=t-ch[i-pos+1] // 插入 T s-len + =t-len; //更新串