第五章 串和数组 5.1 串的定义和操作 5.2 串的表示和实现 5.3 字符串应用 5.4 字符串匹配算法 5.5 数组

Presentation on theme: "第五章 串和数组 5.1 串的定义和操作 5.2 串的表示和实现 5.3 字符串应用 5.4 字符串匹配算法 5.5 数组"— Presentation transcript:

1 第五章 串和数组 5.1 串的定义和操作 5.2 串的表示和实现 5.3 字符串应用 5.4 字符串匹配算法 5.5 数组
5.6 数组的压缩

2 5.1串的定义和操作 串定义 字符串，由零个或多个字符组成的有限序列。S＝“a0a1.....an-1” 串的长度：n
空串：n=0，Null String 子串与主串，子串的位置（从0开始） 串的比较：最大相等前缀子序列

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

4 5.2串的表示和实现 存储不同，实现不同！ 5.2.1定长顺序存储表示 两种表示方法 下标为0的数组存放长度 (pascal)
typedef unsigned char SString[MAXSTLEN+1] ; 在串值后面加‘\0’结束 (C语言) char str[10]; 算法5.1 void Concat_Sq1(char T[],char S1[], char S2[]) 【注意】 T[]必须足够长度，否则会溢出 算法5.2 void Concat_Sq2(SString T[],SString S1[], SString S2[]) 存储不同，实现不同！

5 串变量的存储空间是在程序执行过程中动态分配的，程序中出现的所有串变量可用的存储空间是一个共享空间，称为“堆”。
5.2.2堆分配存储表示 串变量的存储空间是在程序执行过程中动态分配的，程序中出现的所有串变量可用的存储空间是一个共享空间，称为“堆”。 算法5.3 求字符串长度 void StrLength(char *S) 算法5.4字符串比较 void StrCompare (char *S, char *T) 算法5.5求字符串字串 void SubString (char *Sub, char *S,int pos,int len) 用Sub返回S中pos位置开始长度为len的子串

6 5.2.3块链存储表示 用链表来存储串。存在节点大小问题 Const CHUNKSIZE =80;
typedef struct Chunk{ char ch[CHUNKSIZE]; struct Chunk * next; }Chunk; typedef struct { Chunk *head, *tail; int curlen; }Lstring;

7 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-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

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

9 5.4正文匹配模式 算法5.6 int find_BF (char *S,char *P,int start) {
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中的出现概率有关

10 当i=6失配时，可以推论：只需i=6和j=3继续比较
a b c a b c a b c d a b c a b c a b c d a b c a b c d a b c a b c d j=0 j=0 j=6 S[1]=P[1]!=P[0] P[3..5]=P[0..2] S[0..5]=P[0..5] (b) (a) i=6 i=3 a b c a b c a b c d a b c a b c a b c d a b c a b c d a b c a b c d j=3 j=0 S[3..5]=P[3..5] =P[0..2] 当i=6失配时，可以推论：只需i=6和j=3继续比较 (d) (c)

11 P0P1…Pk-1=Pj-kPj-k+1…Pj-1
假设p[j]失配后只需要和p[k]继续比较 S i 匹配 Pj-kPj-k+1…Pj-1= Si-k Si-k+1… Si-1 j P 失配S[i]!=P[j] k 匹配 P0P1…Pk-1= Si-k Si-k+1… Si-1 P0P1…Pk-1=Pj-kPj-k+1…Pj-1 next[j]=k

12 匹配模式的改进算法(KMP算法) -1 j=0 j 1 2 3 4 5 6 模式串 a b c d next[j] -1
next[j]= max{k|0<=k<j 且 ‘p0…pk-1’=‘pj-k…pj-1’} next[j]表示当模式中第j个字符与主串失配时，在模式 中需要重新和主串该字符进行比较的字符位置 j 1 2 3 4 5 6 模式串 a b c d next[j] -1

13 算法5.7 int find_KMP(char *S,char *P,int start){ i=start; j=0;
while(i<strlen(S) && j<(int)strlen(P)){ if(j==-1 || S[i]==P[j]){++i;++j} else j=next[j]; } if(j=strlen(P)) return (i-j); else return -1;

14 Next数组如何获取 P j Next[j]=k P0P1…Pk-1= k P Pj-k Pj-k+1… Pj-1 P[j]==P[k]
k’=next[k] P k’ P[j]!=P[k’] P[j]==P[k’’] ? k’’=next[k’] … … P[j]==P[k’] Next[j+1]=k’+1

15 Next数组如何获取 根据定义 next[0]=-1;next[1]=0; 假设next[j]=k; 考虑next[j+1]
由next[j]=k，P0 P1 …Pk-1= Pj-k Pj-k+1 …Pj-1 下面考虑Pk和Pj，若Pk=Pj,则 P0 P1 …Pk-1 Pk = Pj-k Pj-k+1 …Pj-1 Pj 即next[j+1]=k+1; 若Pk!=Pj,希望找到k’<k 使得 P0 P1 …Pk’-1 Pk’ = Pj-k’ Pj-k’+1 …Pj-1 Pj 则有next[j+1]=k’+1, k’即为next[k].

16 获得next数组的算法5.8 void get_next(char* P,int next[]){
j=0; k=-1;next[0]=-1; while(j<strlen(P)-1){ if(k==-1|| P[j]==P[k]){j++; k++;next[j]=k;} else k=next[k]; } j 1 2 3 4 模式串 a b next[j] -1 next[j]修正

17 改进后获得next数组算法5.9 void get_next1(char* P,int next1[]){
j=0; k=-1;next1[0]=-1; while(j<strlen(P)-1){ if(k==-1|| P[j]==P[k]){ j++; k++; if(P[j]!=P[k])next1[j]=k; else next1[j]=next1[k]; } else k=next[k];

18 5.5数组 5.5.1数组的定义和操作 二维数组定义 N维数组定义 数组的基本操作 其数据元素是一维数组的线形表
initarray(&A,n,bound1,bound2...boundn) Destroyarray(&A) value(A,&e,index1,index indexn) assign(&A,e,index1,index indexn)

19 5.5.2数组的顺序表示和实现 数组元素的两种存储方式 数组中元素在内存映象中的关系: 行主序存储 列主序存储 二维数组A[m][n]
LOC[i,j]=LOC[0,0]+(i*n+j)*L 三维数组B[p][m][n] LOC[i,j,k]=LOC[0,0,0]+(i*m*n+j*n+k)*L

20 5.5.3数组应用 例5.1寻找两个串最长的公共子串 通常的匹配算法复杂度O(mn2) 利用二维数组构造串之间的关系来求解
Void diagscan(int mat[][],int m,int n,int i,int j,int &manlen, int &jpos) Void diagmax(int mat[][], int m,int n,int &manlen,int &jpos) int getmaxsamesubstr(char *string1,char *string2,char *&sub)

21 s g a b c d f t 特征值 i-j=0 特征值 i-j=-(n-1) i-j 为固定值 特征值 i-j=m-1 Mat[0,0]
Mat[m-1,n-1]

22 5.6数组的压缩 5.6.1特殊形状矩阵的存储表示 对称矩阵：A[n][n]存储到B[n(n+1)/2]
A[i,j]->B[k] k=(i+1)i/2+j i>=j k=(j+1)j/2+i i<j 三角矩阵：A[n][n]存储到B[n(n+1)/2] A[i,j]->B[k] k=(i+1)i/2+j i>=j i<j 带状矩阵A[n][n]存储到B[3n-2] A[i,j]->B[k] k=3i-1+(j-i+2)-1=2i+j |i-j|<=1 |i-j|>1 随机稀疏矩阵 非零元比零元少的多且分布无规律的矩阵。

23

24 5.6.2随机稀疏矩阵的存储表示 三元组顺序表 const MAXSIZE=1000 typedef struct{ int i,j;
ElementType e; }Triple; Triple data[MAXSIZE] int mu,nu,tu; }TSMatrix;

25 rpos[col]=pos[col-1]+num[col-1]
i j e 1 12 2 9 -3 5 14 3 24 4 18 15 -7 i j e 2 -3 5 15 1 12 4 18 9 3 24 -7 14 (b) T.data (a) M.data rpos[0]=0 rpos[col]=pos[col-1]+num[col-1] j 1 2 3 4 5 6 num[j] rpos[j] 7 8

26 矩阵转置 void transpose(ElemType M[][],T[][],int m,int n) 时间复杂度O(n×m) “按需点菜”的思想 复杂度O(M.nu×M.tu) “按位就座”的思想 建立辅助数组 num[n] rpos[n] void createpos(TSMatrix M) 快速转置 status Transpose TS(TSMatrix M, TSMatrix &T) 时间复杂度 O(M.nu+M.tu)

27 逻辑链接的顺序表 为了能随机存取三元组表示数组的任意一行非零元素，在建立三元组顺序表存储结构同时建立rpos[n]辅助数组,这种带行链接信息的三元组表称为“逻辑连接的顺序表” typedef struct{ Triple data[MAXSIZE]; int rpos[MAXMN]; int mu,nu,tu; }RLSMatrix;

28 十字链表 矩阵运算增加或减少非零元时，使用链表结构来表示三元组序列。 typedef struct OLNode{ int i,j;
ElementType e; struct OLNode *rnext,*cnext; }OLNode,*Olink; typedef struct { Olink *rhead,*chead; int mu,nu,tu; }CrossList;

29 在十字链表中查找元素 void CrossSearch(CrossList M,ElemType x) {
i=0;p=*(M.rhead+i); while(i<M.m){ if(!p){i++;p=*(M.rhead+i);} else{ if(p->e==x) cout<<‘(‘<<p->i<<‘,’<<p->j<<‘)’<<endl; p=p->next; } }//while

30 谢 谢

31 算法5.1 void Concat_sq1(char T[],char S1[],char S2[]) i=j=0;
{//用T返回以’\0’为结束符的串S1、S2连接成的新串 i=j=0; while(S1[i]!=’\0’)T[j++]=S1[i++]; // 复制串S1 i=0; while(S2[i]!=’\0’)T[j++]=S2[i++]; // 复制串S2 T[j]=’\0’; //置T串的结束符 }// end Concat_sq1

32 算法5.2 void Concat_sq2(SString T,SString S1,SString S2)
for(i=1;i<=S1[0];i++)T[i]=S1[i]; // 复制串S1 for(i=1;i<=S2[0];i++)T[i+S1[0]]=S2[i]; // 复制串S2 T[0]=S1[0]+S2[0]; //置T串的长度 }// end Concat_sq2

33 算法5.3 int StrLength_sq(char *S) {//求串S的长度 i=0; while(S[i]!=’\0’)i++;
return i; }// end StrLength_sq

34 算法5.4 int StrCompare_sq(char *S, char *T)
{//比较字符串S、T的大小，S>T返回正数，相等返回0，S<T返回负数。 for(i=0;S[i]!=’\0’&&T[i]!=’\0’;i++) if(S[i]！=T[i])return (S[i]-T[i]); return (S[i]-T[i]); //先结束的字符串当前字符为’\0’,值为0. }// end StrCompare_sq

35 算法5.5 void Substring_sq(char *Sub, char *S,int pos,int len)
{//用Sub返回串S中位置是pos、长度为len的子串 slen=StrLength_sq(S); if(pos<0||pos>slen-1||len<0||len>slen-pos) {ErrorMsg(“非法输入！”)；return;} for(i=0;i<len;i++)Sub[i]=S[pos+i]; Sub[len]=’\0’; //置Sub串的结束符 }// end Substring_sq

36 算法5.10 void diagscan(int mat[][],int m,int n,int i,int j,int &maxlen,int &jpos) {//从[i,j]开始沿对角线方向扫描最长的连续1 eq=0;len=0; // 初始化状态标志eq和当前连续1长度len while(i<m && j<n){ if(mat[i][j]==1){ len++; if(!eq){eq=1;sj=j; } //第一个出现的1, 改变状态 }else if(eq){ //上一个连续1结束 if(len>maxlen){maxlen=len;jpos=sj;} eq=0;len=0; //重新开始下一个连续1的扫描 }//else if i++;j++; }//while }// end diagscan

37 算法5.11 void diagmax(int mat[][],int m,int n,int &maxlen,int &jpos)
{//求矩阵mat中对角线方向上连续1的最长长度maxlen和起点 maxlen=0;jpos=-1; istart=0; //右上的第一条对角线起始行坐标 for(k=-(n-1);k<=m-1;k++){ //当前处理特征量k的对角线 i=istart;j=i-k; //特征量k=i-j diagscan(mat,m,n,i,j,maxlen,jpos); //扫描特征量为k的对角线连续1的最长段 istart+=(k>=0)?1:0; //k>=0时，istart开始增加 }//for }// end diagmax

38 算法5.12 void getmaxsamestr(char *string1,char *string2,char *&sub)
{//求string1和string2的最大共同字串返回到sub p1=string1;m=strlen(string1); p2=string2;n=strlen(string2); for(i=0;i<m;i++) for(j=0;j<n;j++) mat[i][j]=(string1[i]==string2[j])?1:0; diagmax(mat,m,n,maxlen,jpos) //求矩阵mat中对角线方向最长1 if(maxlen==0)sub[0]=’\0’; else strncpy(sub,&string2[jpos],maxlen); //复制string2中jpos开始的maxlen个字符的子串 sub[maxlen]=’\0’; }// end getmaxsamestr

39 算法5.13 for(i=0;i<m;i++) for(j=0;j<n;j++) T[j][i]=M[i][j];
void transpose(Elemtype M[][],Elemtype T[][], int m, int n) {//求二维数组存储的矩阵Mm×n的转置矩阵T for(i=0;i<m;i++) for(j=0;j<n;j++) T[j][i]=M[i][j]; }// end transpose

40 算法5.14 #define MAXM 100 //矩阵最大的列数目+1 void createrpos(TSMatrix M)
{//求矩阵Mm×n的rpos数组 for(col=0;col<M.nu;col++)num[col]=0; for(t=0;t<M.tu;t++)++num[M.data[t].j];//统计各列非零元 rpos[0]=0; for(col=1;col<M.nu;col++) rpos[col]=rpos[col-1]+num[col-1]; //累计num数组获得rpos }// end createrpos

41 算法5.15 void TRansposeTS(TSMatrix M,TSMatrix &T)
T.mu=M.nu;T.nu=M.mu;T.tu=M.tu; //置T相关属性 if(!M.tu)return; //没有非零元，不作处理 createrpos(M); for(p=0;p<M.tu;p++){ col=M.data[p].j; //当前元素在M中的列,即T中的行 q=rpos[col]; //当前元素在T.data中位置 T.data[q].i=M.data[p].j; T.data[q].j=M.data[p].i; //交换i、j坐标 T.data[q].e=M.data[p].e; //赋元素值 ++rpos[col]; //rpos指向T中下一个col行的非零元素位置 }//for }// end TRansposeTS