哈工大数据结构4讲解.ppt

Status Concat(SString S1, SString S2, SString T) { // 用T返回由S1和S2联接而成的新串。若未截断, 则返回TRUE，否则FALSE。 if ( S1[0]+S2[0] = MAXSTRLEN ) { // 未截断 T[1..S1[0]] = S1[1..S1[0]]; T[S1[0]+1..S1[0]+S2[0]] = S2[1..S2[0]]; T[0] = S1[0]+S2[0]; uncut = TRUE; } //如图(a) else if ( S1[0] MAXSTRLEN ) // S1[0] MAXSTRLEN 而S1[0]+S2[0] MAXSTRLEN { // 截断：将串S2 的一部分截断，得到的串T除S1外，只包含串S2的一个子串。 T[1..S1[0]] = S1[1..S1[0]]; T[S1[0]+1..MAXSTRLEN] =S2[1..MAXSTRLEN－S1[0]]; T[0] = MAXSTRLEN; uncut = FALSE; } //如图(b) else // S1[0] ==MAXSTRLEN { // 截断(仅取S1)：得到的串T并非联结结果，而和串S1相等。 T[0..MAXSTRLEN] = S1[0..MAXSTRLEN]; // T[0] == S1[0] == MAXSTRLEN uncut = FALSE; } //如图(c) return uncut; } 例：求子串 SubString ( Sub,S,pos,len ) 求子串的过程即为复制字符序列的过程，将串S中从第pos 个字符开始长度为len的字符序列复制到串Sub中。 Status SubString(SString Sub,SString S,int pos, int len) { //用Sub返回串S的第 pos 个字符起长度为len的子串。 // 其中，1=pos=Strlength(S) 且 0=len= Strlength(S) –pos+1 if( pos1 || posS[0] || len0 || lenS[0]-pos+1) return ERROR; Sub[1..len]=S[pos..pos+len-1]; Sub[0]=len; return OK; } 综上两个操作： 在顺序存储结构中， 实现串操作的基本操作为字符序列的复制，操作的时间复杂度基于复制的字符序列的长度。 如果在操作中出现串值序列的长度超过上界MAXSTRLEN 时，约定用截尾法处理。 克服这个弊病惟有不限定串长的最大长度，即动态分配串 值的存储空间。 2.堆分配存储表示 特点： 仍以一组地址连续的存储单元存放串值字符序列， 但它们的存储空间是在程序执行过程中动态分配而得。 在C语言中，存在一个称为“堆”的自由存储区，由动态分配函数malloc( )和free( )来管理。用malloc( )为每个新串分配一块实际串长所需的存储空间，若分配成功，则返回一个指向起始地址的指针，作为串的基址，同时，为处理方便，约定串长也作为存 储结构的一部分。 这种存储结构表示的串操作仍是基于“字符序列的复制”。 typedef struct { char *ch ; // 若是非空串，则按串长分配存储区，否则 ch 为NULL int length ; // 串长度 } HString ; Status Concat(HString T, HString S1, HString S2) { // 用T返回由S1和S2联接而成的新串 if (T.ch) free(T.ch); // 释放串T的旧空间 if (!(T.ch = (char *) malloc((S1.length+S2.length)*sizeof(ch