中国科学技术大学：《数据结构与数据库》课程教学资源（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-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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)

4.3串的模式匹配算法 BF算法 int Index BF char S []char T[],int pos){ i=pos-1;j=0; while (S[i+j]!=0'&&T[j]!=10') if(S[itj订=T[])j+; else {i++;j=0;) if T[j]=0')return i+1; else return -1;} -例：S="ababcabcacbabi”T-“abcac”返▣值=6 、 算法复杂度：O(m×n)与首字母在$中的出现概率有关 采用SString实现 ypb@ustc.edu.cn 6 中国科学技术大学

ypb@ustc.edu.cn 6 中国科学技术大学 4.3串的模式匹配算法 • BF算法 int Index_BF ( char S [ ], char T [ ], int pos ) { i = pos-1; j = 0; while ( S[i+j] != '\0' && T[j] != '\0' ) { if ( S[i+j] == T[j] ) j ++; else { i ++; j = 0; }} if ( T[j] == '\0' ) return i+1; else return -1;} – 例：S＝ “ababcabcacbab” T=“abcac” 返回值＝6 – 算法复杂度：O(m×n) 与首字母在S中的出现概率有关 – 采用SString实现

匹配模式的改进算法*(KMP算法 0 j1时 next[j]= max{k1模式匹配算法 int Index KMP(SString S,SString T,int pos){ i-pos;j=1; while(iT[O])return i-T[O];else return 0; 一主串指针不回溯。 ypb@ustc.edu.cn 中国科学技术大学

ypb@ustc.edu.cn 7 中国科学技术大学 0 j=1时 next[j]= max{k|1T[0]) return i-T[0]; else return 0; } – 主串指针不回溯。 匹配模式的改进算法*(KMP算法)

>获得next数组的算法 void get next(Sstring T,int &next[]){ i=1;next[1]=0;j=0; while(i改进后获得next数组(nextval)算法 (红色部分改写如下) if(T[i]!=T[j])nextval[i]=j; else nextval[i]=nextval[j]; ypb@ustc.edu.cn 8 中国科学技术大学

ypb@ustc.edu.cn 8 中国科学技术大学 ➢获得next数组的算法 void get_next(Sstring T,int &next[]){ i=1; next[1]=0; j=0; while(i<T[0]){ if(j==0 || T[i]==T[j]){++i; ++j;next[i]=j;} else j=next[j]; } } ➢改进后获得next数组(nextval)算法 （红色部分改写如下) if(T[i]!=T[j])nextval[i]=j; else nextval[i]=nextval[j];

4.3数组 数组的定义 ADT Array{ 数据对象：D={aa2.na2.an∈El emset,. j=0,1,b:-1bi是数组第i维的长度，n是位数} 数据关系：R={R,R2Rn} Riaji...aji.ain,aj...jiin aj1…aji…an,aj1.aitl.an∈D,i=2,3n 0<=jk<=bk-1,1<=k<=n,k!=l 0<=j=b-1} ypb@ustc.edu.cn 9 中国科学技术大学

ypb@ustc.edu.cn 9 中国科学技术大学 4.3数组 数组的定义 ADT Array{ 数据对象：D={aj1 aj2…ajn| aj1 aj2…ajn∈Elemset, ji=0,1,…bi-1,bi是数组第i维的长度，n是位数} 数据关系：R={R1 ,R2…Rn} Ri={| aj1…aji…ajn , aj1…aji+1…ajn ∈D,i=2,3…n 0<=jk<=bk-1,1<=k<=n,k!=I 0<=ji<=bi-1 }

基本操作： initArray(&A,n,bound1,bound2...boundn) DestroyArray(&A) Value(A &e,index1,index2......indexn) Assign(&A,e,index1,index2......indexn) ADT Array ·二维数组定义 一其数据元素是一维数组的线形表 ·N维数组定义 -其数据元素是-1维数组的线形表 ypb@ustc.edu.cn 10 中国科学技术大学

ypb@ustc.edu.cn 10 中国科学技术大学 基本操作 : initArray(&A,n,bound1,bound2...boundn) DestroyArray(&A) Value(A,&e,index1,index2......indexn) Assign(&A,e,index1,index2......indexn) }ADT Array • 二维数组定义 – 其数据元素是一维数组的线形表 • N维数组定义 – 其数据元素是N－1维数组的线形表