第五章 串和数组 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+j] != '\0' && P[j] != '\0' ) { if ( S[i+j] == P[j] ) j ++; else { i ++; j = 0; }} if ( P[j] == '\0' ) return i; else return -1; } 例：S＝“ababcabcacbab” T=“abcac” 返回值＝5 算法复杂度：O(m×n) 与首字母在S中的出现概率有关

10 匹配模式的改进算法(KMP算法) -1 j=0 模式匹配算法
next[j]= max{k|0<=k<j 且 ‘p0…pk-1’=‘pj-k…pj-1’} next[j]表示当模式中第j个字符与主串失配时，在模式 中需要重新和主串该字符进行比较的字符位置 模式匹配算法 int find_KMP(char *S,char *P,int start){ i=start; j=0; while(i<strlen(S) && j<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;

11 获得next数组的算法 void get_next(char* P,int next[]){ i=0; j=-1;next[0]=-1; while(i<strlen(P)-1){ if(j==-1|| P[i]==P[j]){++i; ++j;next[i]=j;} else j=next[j]; } 改进后获得next数组算法 （红色部分改写如下) if(j==-1 || P[i]==P[j]){ ++i; ++j; if(P[i]!=P[j])nextval[i]=j; else nextval[i]=nextval[j];

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

13 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

14 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) 算法5.7 int getmaxsamesubstr(char *string1,char *string2,char *&sub) 【更正】sub[maxlen]=0;

15 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 随机稀疏矩阵 非零元比零元少的多且分布无规律的矩阵。

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

17 矩阵转置 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)

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

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

20 在十字链表中查找元素 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