重庆移通学院：《数据结构》课程教学资源（PPT课件讲稿）第5章 串

字符串

字符串

串 ◆字符串是非数值处理的基本对象 ◆应用领域 信息检索系统 文字编辑程序 语言翻译系统 ◆问题 如何有效地组织和存储字符串,并提供必要的操作

串  字符串是非数值处理的基本对象  应用领域 – 信息检索系统 – 文字编辑程序 – 语言翻译系统 – … …  问题 – 如何有效地组织和存储字符串，并提供必要的操作

C语言中的字符串函数 ◆头文件 # include‘ string. h ◆函数包括 char s strcat(char *strl, char *str2) char s strchr( char *str, int ch) 找出串st中第一次出现字符ch的位置 int strcmp(char str1, char *str 2) char *strcpy(char *str l, char *str2); unsigned int strlen(char *str) Char * strstr(char*strl, char * str2) 找出串st2在串str1中第一次出现的位置

C语言中的字符串函数  头文件 – #include “string.h”  函数包括 – char * strcat(char *str1, char *str2); – char * strchr(char *str, int ch); //找出串str中第一次出现字符ch的位置 – int strcmp(char *str1, char *str2); – char *strcpy(char *str1, char *str2); – unsigned int strlen(char *str); – Char * strstr(char *str1, char *str2); //找出串str2在串str1中第一次出现的位置

Q串的抽象类型定义 D=ail ae CharacterSet, 1=1, 2,.n g R={a12a1>|a12a1∈D,i=2,n} trAssign(&T, chars)∥/串赋值, chars为一字符串常量 StrCopy(&T,S)∥串拷贝 teMpts(S)∥是否空串 StrCompare(S,T)/串比较,分ST情形、S-T情形和S<情形 StrEngth(S)∥取串长 ClearString(&S)∥将串清空 Concat(&T,S1,S2)∥两串联接 SubString(&Sub,S,pos,len)∥从串S中取出从pos个位置起长为len的子 Index(S,T,pos)/若串S中存在和T相同的字串,返回起始位置 Replace(&S,T,V)∥/串替换,用Ⅴ替换S中出现的所有字串T Strlnsert(&s,pos,T)∥/在串S的第pos个字符前插入串T StrDelete(&S,pos3len)∥从串S中删除第pos个字符起长度为en的子串 DestroyString(&S)∥销毁串S JADT String

串的抽象类型定义 ADT String { D = {ai | ai CharacterSet, i = 1,2,…n } R = { | ai-1 , ai D, i = 2,…n} P: StrAssign(&T, chars) //串赋值, chars为一字符串常量 StrCopy(&T, S) //串拷贝 StrEmpty(S) //是否空串 StrCompare(S, T) //串比较，分S>T情形、S=T情形和S<T情形 StrLength(S) //取串长 ClearString(&S) //将串清空 Concat(&T, S1, S2) //两串联接 SubString(&Sub, S, pos, len) //从串S中取出从pos个位置起长为len的子串 Index(S, T, pos) //若串S中存在和T相同的字串，返回起始位置 Replace(&S, T, V) //串替换，用V替换S中出现的所有字串T StrInsert(&S, pos, T) //在串S的第pos个字符前插入串T StrDelete(&S, pos, len) //从串S中删除第pos个字符起长度为len的子串 DestroyString(&S) //销毁串S }ADT String  

Q串的表示和实现 ◆选用不同的存储结构,串操作的实现也 各不相同,可选用的串的存储结构包括: 串的定长顺序存储表示 串的堆分配存储表示 串的块链存储表示

串的表示和实现  选用不同的存储结构，串操作的实现也 各不相同，可选用的串的存储结构包括： – 串的定长顺序存储表示 – 串的堆分配存储表示 – 串的块链存储表示

Q串的表示和实现 ◆串的定长顺序存储表示 按照预定义大小,为每个定义的串变量分配一个固定 长度的存储区(可用定长数组来描述) 当串的实际长度超过预定义长度时,字符串将被截断 串操作均基于“字符序列的复制” typedefstruct i char dataMAXSIZEI Int curlen Seqstring 定义一个串变量: Seqstrings; BSUIN 0123 MAXSIZE

串的表示和实现  串的定长顺序存储表示 – 按照预定义大小，为每个定义的串变量分配一个固定 长度的存储区(可用定长数组来描述) – 当串的实际长度超过预定义长度时，字符串将被截断 – 串操作均基于“字符序列的复制” typedef struct { char data[MAXSIZE]; int curlen; } SeqString; 定义一个串变量：SeqString s; S 0 1 2 3 MAXSIZE 3 S U N

串联接:把两个串s1和s2首尾连接成一个新串s,即 1+s2。 /*设串结束用“\0’来标识。*/ int StrConcatl(SeqString sl, SeqString S2, SeqString S) char sl,s2口],s[]; i int i=0, j, len1, len2 len1= StrEngth(s1); len2-StrLength(s2) if(enl+len2> MAXSIZE-l) return0;/*s长度不够* while(sl[]=10,)(sli=s1[]; i++: j++,) j=0; while(s2[]=10,)(s[i]=s2[]; 1++: j++,) 1=10, return 1 O(n)

1．串联接：把两个串s1和s2首尾连接成一个新串s ，即：sMAXSIZE-1) return 0 ; /* s长度不够*/ j=0; while(s1[j]!=’\0’) { s[i]=s1[j];i++; j++; } j=0; while(s2[j]!=’\0’) { s[i]=s2[j];i++; j++; } s[i]=’\0’; return 1; } O(n)

求子串 int StrSub(char *t, char *S, int i, int len) /*用t返回串s中第个i字符开始的长度为en 的子串1 slen lensslen-i+1) printf("参数不对"); return0;,} for =0; j<len; j ++) O(n) tll=S[i+j-1 j]=)0 return 1; M len pos MAXSIZE MAXSIZE

２．求子串 int StrSub (char *t, char *s, int i, int len) /* 用t返回串s中第个i字符开始的长度为len 的子串1≤i≤串长*/ { int slen; slen=StrLength(s); if ( islen || lenslen-i+1) { printf(＂参数不对＂); return 0; } for (j=0; j<len; j++) t[j]=s[i+j-1]; t[j]=’\0’; return 1;} S 0 len pos MAXSIZE 3 0 len T MAXSIZE O(n)

】串的表示和实现 ◆串的堆分配存储表示 堆:一个自由存储区,C中用 malloc和feO来管理 该方法仍以一组地址连续的存储单元存放串值字符 序列,但它们的存储空间在程序执行过程中动态分 配而得 串操作仍基于“字符序列的复制” 设堆空间为: typedef struct char store SMAX+ll { int length;,/*串长* 自由区指针: int free int strada;*起始地址* 串的存储映象类型如右: 3 HString HString T, S strada SUN length 01

串的表示和实现  串的堆分配存储表示 – 堆：一个自由存储区，C中用malloc()和free()来管理 – 该方法仍以一组地址连续的存储单元存放串值字符 序列，但它们的存储空间在程序执行过程中动态分 配而得 – 串操作仍基于“字符序列的复制” typedef struct { int length; /*串长*/ int stradr; /*起始地址*/ } HString; HString T, S; T 0 1 2 3 stradr S U N length 设堆空间为： char store[SMAX+1]; 自由区指针：int free; 串的存储映象类型如右：

1.串常量赋值 void Str Assign( HString *sl, char *s2) /*将一个字符型数组s2中的字符串送入 堆 store中,fee是自由区的指针* i int 1=0,len len= Length(s2); if (lenSMAX return O else(for(i=0; i<len; 1++) store[ frre+1]=s2(i sl strada=free sIlen.len free=free+len

1. 串常量赋值 void StrAssign(HString *s1,char *s2) /*将一个字符型数组s2中的字符串送入 堆store中,free是自由区的指针*/ { int i=0,len; len=StrLength(s2); if (len<0||free+len-1＞SMAX) return 0; else {for (i=0;i<len;i++) store[frre+i] =s2[i]; s1.stradr=free; s1.len.=len; free=free+len; } }