中国科学技术大学：《数据结构与数据库》课程教学资源（PPT课件讲稿）第四章 串和数组

第四章串和数组 4.1串的定义* 4.2串的表示和实现* 4.3数组 4.4数组的压缩 ypb@ustc.edu.cn 中国科学技术大学

ypb@ustc.edu.cn 1 中国科学技术大学 第四章 串和数组 4.1 串的定义* 4.2 串的表示和实现* 4.3 数组 4.4 数组的压缩

4.1串的定义 串定义 - 字符串，由零个或多个字符组成的有限序列。 S="aoal..an- -串的长度：n -空串：n=O,Null String 子串与主串，子串的位置 一串的比较：最大相等前缀子序列 ADT String{ 数据对象：D={ala∈CharacterSet,.i=l,2,n,n≥0} 数据关系：R={<a-l,a>a-1,a∈D,i=2,.n 基本操作 ypb@ustc.edu.cn 中国科学技术大学

ypb@ustc.edu.cn 2 中国科学技术大学 4.1串的定义 • 串定义 – 字符串，由零个或多个字符组成的有限序列。 S＝ “ a0a1 .....an-1 ” – 串的长度：n – 空串：n=0，Null String – 子串与主串，子串的位置 – 串的比较：最大相等前缀子序列 ADT String{ 数据对象:D={ai |aiCharacterSet,i=1,2,…n,n≥0} 数据关系:R={<ai-1 ,ai>|ai-1 , aiD,i=2,…n} 基本操作:

S StrAssign(&T,chars) strcpy StrCopy(&T,S) strepy StrEmpty(S) strlen(S)==0 StrCompare(S,T) strcmp StrLength(S) strlen ClearString(&S) Concat(&T,S1,S2) strcat Substring(&Sub,S,Pos,len) 0<=pos<=Strlength(S)-1 Index (S,T,pos) 0<=pos<=Strlength(S)-1 strstr Replace(&S,T,V) StrInsert(&S,pos,T) 0<=pos<=Strlength(S) StrDelete(&S,pos,len) 0<=pos<=StrLength(S)-len DestroyString(&S) }ADT String 最小操作子集StrAssign、StrCompare、StrLength、Concat,,Substring ypb@ustc.edu.cn 中国科学技术大学

ypb@ustc.edu.cn 3 中国科学技术大学 StrAssign(&T,chars) strcpy StrCopy(&T,S) strcpy StrEmpty(S) strlen(S)==0 StrCompare(S,T) strcmp StrLength(S) strlen ClearString(&S) Concat(&T,S1,S2) strcat Substring(&Sub,S,Pos,len) 0<=pos<=Strlength(S)-1 Index（S，T，pos） 0<=pos<=Strlength(S)-1 strstr Replace(&S,T,V) StrInsert(&S,pos,T) 0<=pos<=Strlength(S) StrDelete(&S,pos,len) 0<=pos<=StrLength(S)-len DestroyString(&S) } ADT String 最小操作子集StrAssign、StrCompare、StrLength、Concat，Substring

4.2串的表示和实现 4.2.1定长顺序存储表示 两种表示方法 -下标为0的数组单元存放长度(pascal) typedef unsigned char SString[MAXSTLEN+1]; -在串值后面加0'结束(C语言) char str[10]; Status Concat(Sstring &T,Sstring S1,Sstring S2) 【注意】T]是否足够长度，溢出处理 void Substring(char Sub[],char S[],int pos,int len) ...Strncpy(Sub,&S[pos],len);Sub[len]=0';... ypb@ustc.edu.cn 中国科学技术大学

ypb@ustc.edu.cn 4 中国科学技术大学 4.2串的表示和实现 4.2.1定长顺序存储表示 • 两种表示方法 – 下标为0的数组单元存放长度 (pascal) typedef unsigned char SString[MAXSTLEN+1] ; – 在串值后面加‘\0’结束 (C语言) char str[10]; 算法 Status Concat(Sstring &T,Sstring S1, Sstring S2) 【注意】 T[]是否足够长度，溢出处理 算法 void Substring(char Sub[],char S[], int pos, int len) …Strncpy(Sub,&S[pos],len);Sub[len]=‘\0’; …

4.2.2堆分配存储表示 。 串变量的存储空间是在程序执行过程中动态分配的， 程序中出现的所有串变量可用的存储空间是一个共享 空间，称为“堆”。 typedef struct{ char *ch; int length; Hstring; void StrInsert(HString &S,int pos,HString T) ypb@ustc.edu.cn 5 中国科学技术大学

ypb@ustc.edu.cn 5 中国科学技术大学 4.2.2堆分配存储表示 • 串变量的存储空间是在程序执行过程中动态分配的， 程序中出现的所有串变量可用的存储空间是一个共享 空间，称为“堆” 。 typedef struct{ char *ch; int length; }Hstring; 算法 void StrInsert(HString &S,int pos, HString T)