数据结构课件CH4串li幻灯片.ppt

一、串的定长顺序存储表示 二、串的堆分配存储表示 三、串的块链存储表示 #define MAXSTRLEN 255 // 用户可在255以内定义最大串长 typedef unsigned char SString [MAXSTRLEN + 1]; // 0号单元存放串的长度 一、串的定长顺序存储表示 用一组地址连续的存储单元存储串值的字符序列。 按这种串的表示方法实现的串的运算时，其基本操作为 “字符序列的复制”。 串的实际长度可在这个予定义长度的范围内随意设定，超过予定义长度的串值则被舍去，称之为“截断” 。 特点: Status Concat(SString S1, SString S2, SString T) { // 用T返回由S1和S2联接而成的新串。若未截断, 则返回TRUE，否则FALSE。 return uncut; } // Concat 算法4.2 例1.串的联接算法中需分三种情况处理： 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; } if (S1[0]+S2[0] = MAXSTRLEN) {// 未截断 else if (S1[0] MAXSTRLEN) { // s2截断,s1未截断 else { // s1截断(仅取S1) T[1..S1[0]] = S1[1..S1[0]]; T[S1[0]+1..MAXSTRLEN] = S2[1..MAXSTRLEN－S1[0]]; T[0] = MAXSTRLEN; uncut = FALSE; } T[1..MAXSTRLEN] = S1[1..MAXSTRLEN]; T[0] = MAXSTRLEN uncut = FALSE; } 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串返回 Sub[0]=len；//0号单元存放的串长为len return OK； }//SubString 算法4.3 例2. 求子串 SubString(Sub, S, pos,len) ： 即将串S中从第pos个字符开始长度为len的字符序列复制到串Sub中。 typedef struct { char *ch; // 指针，若是非空串，则按串实际长度分配 //存储区，否则 ch 为NULL int length; // 串长度 } HString; 二、串的堆分配存储表示 （动态分配） 以一组地址连续的存储单元存放串值字符序列，但它们的存储空间是在程序执行过程中动态分配而得。通常，C语言中提供的串类型就是以这种存储方式实现的。系统利用函数malloc( ) 和 free( ) 进行串值空间的动态管理，为每一个新产生的串分配一个存储区，称串值共享的存储空间为“堆”。 C语言中的串以一个空字符为结束符，串长是一个隐含值。 这类串操作实现的算法为: 先为新生成的串分配一个存储空间，然后 进行串值的复制。 Status Concat(HString T, HString S1, HString S2) { // 用T返回由S1和S2联接而成的新串 if (T.ch) free(T.ch); // 释放旧空间 if (!(T.ch =new char[S1.length+S2.length])) exit (OVERFLO