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

第4章串和数组 4.1串的基本概念 4.2串的表示和实现 4.3字符串应用 4.4字符串匹配算法 4.5数组 4.6矩阵的压缩存储 ypb@ustc.edu.cn 中国科学技术大学

ypb@ustc.edu.cn 1 中国科学技术大学 第4章 串和数组 4.1 串的基本概念 4.2 串的表示和实现 4.3 字符串应用 4.4 字符串匹配算法 4.5 数组 4.6 矩阵的压缩存储

4.1串的基本概念 串定义 -字符串，由零个或多个字符组成的有限序列。S ="aa1anl” -串的长度：n -空串：n=0,Null String -子串与主串，子串的位置（从0开始） 【例】主串："Bei Jing”子串"Jing”位置是4 -串的比较：最大相等前缀子序列 ypb@ustc.edu.cn 中国科学技术大学

ypb@ustc.edu.cn 2 中国科学技术大学 4.1串的基本概念 • 串定义 – 字符串，由零个或多个字符组成的有限序列。S ＝ “ a0a1 .....an-1 ” – 串的长度：n – 空串：n=0，Null String – 子串与主串，子串的位置（从0开始） 【例】主串: “Bei Jing” 子串“Jing” 位置是4 – 串的比较：最大相等前缀子序列

串的ADT描述 ● 串的基本操作 1)StrAssign(&T,chars) strcpy ADT String 2)StrCopy(&T,S) strcpy D={ajajEElemSet,i=1,2..n) 3)StrEmpty(S) strlen(S)-=0 R=(<aaplaiLajeD,i-2,3..n) 基本操作： 4)StrCompare(S,T) strcmp 5)StrLength(S) strlen 6)Concat(&T,S1,S2) strcat 7)Substring(&Sub,S,Pos,len)0<=pos<=Strlength(S)-1 0<=len<=Strlength(S)-pos strncpy 8)Index (S,T,pos)0<=pos<=Strlength(S)-1 strstr 9)Replace(&S,T,V) 10)StrInsert(&S,pos,T)0<=pos<=Strlength(S) 11)StrDelete(&S,pos,len)0<=pos<=StrLength(S)-len 12)DestroyString(&S) 最小操作子集 StrAssign、StrCompare、StrLength、Concat,Substring ypb@ustc.edu.cn 3 中国科学技术大学

ypb@ustc.edu.cn 3 中国科学技术大学 • 串的基本操作 1)StrAssign(&T,chars) strcpy 2) StrCopy(&T,S) strcpy 3) StrEmpty(S) strlen(S)==0 4) StrCompare(S,T) strcmp 5) StrLength(S) strlen 6) Concat(&T,S1,S2) strcat 7) Substring(&Sub,S,Pos,len) 0<=pos<=Strlength(S)-1 0<=len<=Strlength(S)-pos strncpy 8) Index（S，T，pos） 0<=pos<=Strlength(S)-1 strstr 9) Replace(&S,T,V) 10) StrInsert(&S,pos,T) 0<=pos<=Strlength(S) 11) StrDelete(&S,pos,len) 0<=pos<=StrLength(S)-len 12) DestroyString(&S) • 最小操作子集 StrAssign、StrCompare、StrLength、Concat，Substring ADT String｛ D={ai |aiElemSet,i=1,2..n} R={<ai-1 ,ai>|ai-1 ,aiD,i=2,3..n} 基本操作： ｝ 串的ADT描述

4.2串的表示和实现 >顺序存储表示 1.静态顺序存储 -下标为0的数组存放长度(pascal) typedef unsigned char SString[MAXSTLEN+1]; -在串值后面加0'结束(C语言) char str[10]; 4.1 void Concat_Sq1(char T[],char S1[],char S2[]) 【注意】T必须足够长度，否则会溢出 算法4.2 void Concat Sq22(SString T☐，SString S1[l,SString S2[]) 存储不同，实现不同！ ypb@ustc.edu.cn 中国科学技术大学

ypb@ustc.edu.cn 4 中国科学技术大学 4.2串的表示和实现 ➢ 顺序存储表示 1. 静态顺序存储 – 下标为0的数组存放长度 (pascal) typedef unsigned char SString[MAXSTLEN+1] ; – 在串值后面加‘\0’结束 (C语言) char str[10]; 算法4.1 void Concat_Sq1(char T[],char S1[], char S2[]) 【注意】 T[]必须足够长度，否则会溢出 算法4.2 void Concat_Sq2(SString T[],SString S1[], SString S2[]) 存储不同，实现不同！

S 2.动态顺序存储 ·串变量的存储空间是在程序执行过程中动态分配 的，而不是在程序运行的开始分配的。 算法4.3求字符串长度> void StrLength(char *S) 算法4.4字符串比较 void StrCompare (char *S,char *T) 算法4.5求字符串字串 void SubString (char *Sub,char *S,int pos,int len) 用Sub返回S中pos位置开始长度为len的子串 ypb@ustc.edu.cn 5 中国科学技术大学

ypb@ustc.edu.cn 5 中国科学技术大学 2. 动态顺序存储 • 串变量的存储空间是在程序执行过程中动态分配 的，而不是在程序运行的开始分配的。 算法4.3 求字符串长度 void StrLength(char *S) 算法4.4字符串比较 void StrCompare (char *S, char *T) 算法4.5求字符串字串 void SubString (char *Sub, char *S,int pos,int len) 用Sub返回S中pos位置开始长度为len的子串