中国科学技术大学：《数据结构》课程教学课件（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串的基本概念·串定义一字符串，由零个或多个字符组成的有限序列。S2= "aoa..an-l一串的长度：n 空串：n=O，Null String一子串与主串，子串的位置（从开始）【例】主串：“BeiJing”子串"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描述串的基本操作ADT String {1)StrAssign(&T,chars)strcpyD-{a;a;eElemSet,i-1,2..n)2) StrCopy(&T,S)strcpyR={la;1,a,eD,i-2,3..n)3) StrEmpty(S)strlen(S)-=0基本操作：4) StrCompare(S,T)strcmpstrlen5) StrLength(S)strcat6) Concat(&T,S1,S2)7) Substring(&Sub,S,Pos,len) 0<=pos<=Strlength(S)-10<=len<=Strlength(S)-pos strncpy8)Index ( S , T, pos ) 0<=pos<=Strlength(S)-1 strstr9) Replace(&S,T,V)10) StrInsert(&S,pos,T) 0<=pos<=Strlength(S)11) StrDelete(&S,pos,len) 0<=pos<=StrLength(S)-len12) DestroyString(&S)最小操作子集StrAssign、StrCompare、StrLength、Concat , Substring3ypb@ustc.edu.cn中国科学技术大学

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|ai-1 ,aiD,i=2,3.n} 基本操作： ｝ 串的ADT描述

4.2串的表示和实现>顺序存储表示1．静态顺序存储-下标为o的数组存放长度（pascal)typedef unsigned char SString[MAXSTLEN+1] ;-在串值后面加“0'结束（C语言）char str[10];算法4.1 void Concat Sq1(char T[l,char S1[], char S2[])【注意】T[]必须足够长度，否则会溢出算法4.2 void Concat _Sq2(SString T[],SString S1[], 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[]) 存储不同，实现不同！

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的子串5中国科学技术大学ypb@ustc.edu.cn

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的子串

》串的链式存储方式 (块链）存在节点大小问题Const CHUNKSIZE =80:typedef struct Chunk?char ch[CHUNKSIZE];struct Chunk * next;↑Chunk;typedef struct {Chunk *head, *tail;int curlen;}Lstring,6中国科学技术大学ypb@ustc.edu.cn

ypb@ustc.edu.cn 6 中国科学技术大学 ➢ 串的链式存储方式（块链） 存在节点大小问题 Const CHUNKSIZE =80; typedef struct Chunk{ char ch[CHUNKSIZE]; struct Chunk * next; }Chunk; typedef struct { Chunk *head, *tail; int curlen; }Lstring;

Relplacestring实现char *replacestring(char *s,char *oldstr, char* newstr)char *p1=s,*p2,tmpfield[MAX _LEN];int nlen=0,ilen;while(p2=strstr(p1,oldstr)!=NULL)ilen=p2-pl;memcpy(tmpfield+nlen,p1,ilen);memcpy(tmpfield+nlen+ilen,newstr,strlen(newstr);nlen+=ilen+strlen(newstr);p1=p2+strlen(oldstr); //whileif(pll=s) (memcpy(tmpfield+nlen,p1,strlen(p1)nlen+=strlen(p1);memmove(s,tmpfield,nlen);s[nlen]="10′; //if// replacestringypb@ustc.edu.cn中国科学技术大学

ypb@ustc.edu.cn 7 中国科学技术大学 char *replacestring(char *s,char *oldstr, char* newstr){ char *p1=s,*p2,tmpfield[MAX_LEN]; int nlen=0,ilen; while((p2=strstr(p1,oldstr))!=NULL){ ilen=p2-p1; memcpy(tmpfield+nlen,p1,ilen); memcpy(tmpfield+nlen+ilen,newstr,strlen(newstr)); nlen+=ilen+strlen(newstr); p1=p2+strlen(oldstr); } //while if(p1!=s) { memcpy(tmpfield+nlen,p1,strlen(p1)); nlen+=strlen(p1); memmove(s,tmpfield,nlen); s[nlen]=‘\0’; } //if } // replacestring Relplacestring实现*

4.3串的应用正文编辑正文编辑通过页表和行表来维护正文串。页表中每一项给出页号和该页的起始行号行表中每一项给出行号、起始地址和该行子串的长度当插入和删除字符时需要修改行表中该行的长度，若超出预先分配的存储空间，还需要重新分配当插入和删除一行时对行表也进行插入和删除；若删除的是一页的首行，则要求修改页表中相应的起始行号当删除一页时仅仅需要修改页表8中国科学技术大学ypb@ustc.edu.cn

ypb@ustc.edu.cn 8 中国科学技术大学 4.3串的应用—— 正文编辑 • 正文编辑通过页表和行表来维护正文串。 • 页表中每一项给出页号和该页的起始行号 • 行表中每一项给出行号、起始地址和该行子串的 长度 • 当插入和删除字符时需要修改行表中该行的长度， 若超出预先分配的存储空间，还需要重新分配 • 当插入和删除一行时对行表也进行插入和删除； 若删除的是一页的首行，则要求修改页表中相应 的起始行号 • 当删除一页时仅仅需要修改页表

4.4模式匹配>BF算法int find BF (char *S,char *P,int start)算法4.61i= start; j = O;while （S[i] !="o' && P[il !="1o')if (S[i] == P[i] ) (i++;j ++;)else (i=i-j+l; j= 0; }if(P[i] == "o') return (i-i);else return -l;人-例：S="ababcabcacbab”T=“abcac”返回值=5一算法复杂度：O(m×n)与首字母在S中的出现概率有关9ypb@ustc.edu.cn中国科学技术大学

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

ei=1i=6i=0cabcabcdbalbcdabcabc?abcabcdaabcabcdj=0j=0 j=6S[1]=P[1]!=P[0]P[3..5]-P[0..2](b)(a)S[0..5]=P[0..5]i=6i=3→abcabcabcdabcacabcdbａｂｃａｂｃdbcabcda4j=3j=0当i=6失配时，可以S[3..5]-P[3.5]-(d)(c)=P[0..2]推论：只需i=6和j=3继续比较10ypb@ustc.edu.cn中国科学技术大学

ypb@ustc.edu.cn 10 中国科学技术大学 a b c a b c a b c d a b c a b c d i=6 j=6 (a) a b c a b c a b c d a b c a b c d i=1 j=0 (b) a b c a b c a b c d a b c a b c d i=3 j=0 (c) a b c a b c a b c d a b c a b c d i=6 j=3 (d) S[1]=P[1]!=P[0] P[3.5]=P[0.2] S[0.5]=P[0.5] S[3.5]=P[3.5] =P[0.2] 当i=6失配时，可以 推论：只需i=6和j=3 继续比较 i=0 j=0