第五章 串和数组 5.1 串的定义和操作 5.2 串的表示和实现 5.3 正文匹配模式 5.4 正文编辑 5.5 数组 5.6 数组的压缩

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

串的基本操作 最小操作子集 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

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

串变量的存储空间是在程序执行过程中动态分配的，程序中出现的所有串变量可用的存储空间是一个共享空间，称为“堆”。 5.2.2堆分配存储表示 串变量的存储空间是在程序执行过程中动态分配的，程序中出现的所有串变量可用的存储空间是一个共享空间，称为“堆”。 算法5.4 void Strinsert_HSq(char *S,int pos,char *T) 【更正】：缺少delete [] S。S其实不可重新分配地址，因其在函数内不可改变地址值(即S指针)。 算法5.5 void Strinsert (char *S,int pos,char *T) 利用C语言固有函数 【更正】：S1=strdup(S) 改为S1=S，无需分配空间。S同上

5.2.3块链存储表示 用链表来存储串。存在节点大小问题 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-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

5.3正文匹配模式 算法5.6 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中的出现概率有关

匹配模式的改进算法(KMP算法) 模式匹配算法 next[j]= max{k|1<k<j 且’p1…pk-1’=’pj-k+1…pj-1’} 1 其他情况 next[j]表示当模式中第j个字符与主串失配时，在模式 中需要重新和主串该字符进行比较的字符位置 模式匹配算法 int Index_KMP(Sstring S,Sstring T,int pos){ i=pos; j=1; while(i<=S[0] && j<=T[0]){ if(j==0 || S[i]==T[j]){++i;++j} else j=next[j]; } if(j>T[0]) return i-T[0]; else return 0;

获得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数组算法 （红色部分改写如下) if(j==0 || T[i]==T[j]){ ++i; ++j; if(T[i]!=T[j])nextval[i]=j; else nextval[i]=nextval[j];

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

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

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

5.5.3数组应用 例5.1寻找两个串最长的公共子串 通常的匹配算法复杂度O(mn2) 利用二维数组构造串之间的关系来求解 Void diagmaxl(int mat[][],int &manlen,int &jpos) Void diagscan(int i,int j) 算法5.7 int maxsamesubstring(char *string1,char *string2,char *&sub) void substring(char * &sub,char *s,int s,int len) 【更正】p=str+s-1 应为p=str+s s从0开始

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

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

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

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

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