教黎 串、数组和广义表 程序设计—数据结构 基本概念及应用 4.2串的表示与实现 4.2.1定长顺序存储表示 1、类型定义 #define MAXSTRLEN 255 typedef unsigned char SString[MAXSTRLEN+l,/体0号单元存放串的长度*/ 串长表示： 1)利用下标为0的分量存放串长 局限性：对于MAXSTRLEN超过255的串，此存储结构不适合，需要修改。 2)串值后加入一个不计入串长的结束标记字符，如C语言中的0 不足：串长是隐含的，需要遍历整个串才能得出。 2、串联接Concat(&TS1,S2) ,是定长存储，联接后T的串长为S1和S2串长之和，该长度可能会超出MAXSTRLEN ∴分情况处理，超出部分要“截断” S1[0]>=MAXSTRLEN: T[1..MAXSTRLEN]=S1[1..MAXSTRLEN]; T[O]=MAXSTRLEN; S2全被截去 S1[O]<MAXSTRLEN &&S1[0]+S2[0]>MAXSTRLEN: T[1.S1[0]=s1[1.S1[0 TIS1[0]+1..MAXSTRLEN]=S2[1..MAXSTRLEN-S1[0]]; TIO]=MAXSTRLEN: /S2部分截断 S1[0]+S2[0]<=MAXSTRLEN: T[1.S1[0]=s1[1.S1[01 TS1[0]+1.S1[0]+S2[01=S2[1.S2[0]l T[0]=S1[0]+S2[0: 本做法基于复制，可进一步考虑利用原S1空间时的处理方法。 3、求子串SubString(&Sub,S,pos,len) 1)合法的pos和len:pos>0&&len>=O&&pos<=StrLength(S)-len+1 2)串的复制：Sub[l.len]=S[pos.-pos+len-l;Subf0=len; 4、评价 ·串长超出最大长度，约定采用截尾法 ·串长过小，则串空间浪费较大 4.2.2堆分配存储表示 1、类型定义 typedef struct{ char *ch; 体约定空串时，ch为NULL*/ int length; }HString: 串本身利用动态分配函数分配一块连续的串值存储空间。 借助堆结构的两个域可以在串名和串值之间建立对应关系一一串名的存储映像。 2、实现说明 ·基于复制： 利用malloc(O分配一块足够的空间，再按要求完成复制任务：如StrAssign(&T,chars)), 文档编号 完成时间 完成人张昱 修改时间 第4页程序设计——数据结构 串、数组和广义表 基本概念及应用 文档编号 文 档 编号 完 成 人 完 成 人 张 昱 张 昱 完成时间 完 成 时间 修改时间 修 改 时间 第 4 页 第 4 页 4.2 串的表示与实现 4.2.1 定长顺序存储表示 1、类型定义 #define MAXSTRLEN 255 typedef unsigned char SString[MAXSTRLEN+1]; /* 0 号单元存放串的长度 */ 串长表示： 1） 利用下标为 0 的分量存放串长 局限性：对于 MAXSTRLEN 超过 255 的串，此存储结构不适合，需要修改。 2） 串值后加入一个不计入串长的结束标记字符，如 C 语言中的’\0’ 不足：串长是隐含的，需要遍历整个串才能得出。 2、串联接 Concat(&T, S1, S2) ∵是定长存储，联接后 T 的串长为 S1 和 S2 串长之和，该长度可能会超出 MAXSTRLEN ∴分情况处理，超出部分要“截断” S1[0]>=MAXSTRLEN： T[1..MAXSTRLEN]=S1[1..MAXSTRLEN]; T[0] = MAXSTRLEN; //S2 全被截去 S1[0]<MAXSTRLEN && S1[0]+S2[0] > MAXSTRLEN： T[1..S1[0]]=S1[1..S1[0]]; T[S1[0]+1.. MAXSTRLEN]=S2[1..MAXSTRLEN-S1[0]]; T[0]=MAXSTRLEN; //S2 部分截断 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]; 本做法基于复制，可进一步考虑利用原 S1 空间时的处理方法。 3、求子串 SubString(&Sub, S, pos, len) 1） 合法的 pos 和 len：pos>0 && len>=0 && pos<=StrLength(S)-len+1 2） 串的复制：Sub[1..len]=S[pos..pos+len-1]; Sub[0]=len; 4、评价 ·串长超出最大长度，约定采用截尾法 ·串长过小，则串空间浪费较大 4.2.2 堆分配存储表示 1、类型定义 typedef struct { char *ch; /* 约定空串时，ch 为 NULL */ int length; }HString; 串本身利用动态分配函数分配一块连续的串值存储空间。 借助堆结构的两个域可以在串名和串值之间建立对应关系——串名的存储映像。 2、实现说明 ·基于复制： 利用 malloc()分配一块足够的空间，再按要求完成复制任务；如 StrAssign(&T,chars)