第四章 串和数组 4.1 串的定义* 4.2 串的表示和实现* 4.3 数组 4.4 数组的压缩.

Presentation on theme: "第四章 串和数组 4.1 串的定义* 4.2 串的表示和实现* 4.3 数组 4.4 数组的压缩."— Presentation transcript:

1 第四章 串和数组 4.1 串的定义* 4.2 串的表示和实现* 4.3 数组 4.4 数组的压缩

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>|ai-1 , aiD,i=2,…n} 基本操作:

3 最小操作子集 StrAssign、StrCompare、StrLength、Concat，Substring
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) <=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 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’; …

5 4.2.2堆分配存储表示 串变量的存储空间是在程序执行过程中动态分配的，程序中出现的所有串变量可用的存储空间是一个共享空间，称为“堆”。 typedef struct{ char *ch; int length; }Hstring; 算法 void StrInsert(HString &S,int pos, HString T)

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

7 匹配模式的改进算法*(KMP算法) 0 j=1时 模式匹配算法 主串指针不回溯。
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; 主串指针不回溯。

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

9 4.3数组 数组的定义 ADT Array{ 数据对象：D={aj1aj2…ajn| aj1aj2…ajn∈Elemset,
ji=0,1,…bi-1,bi是数组第i维的长度，n是位数} 数据关系：R={R1,R2…Rn} Ri={< aj1…aji…ajn , aj1…aji+1…ajn >| 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 }

10 基本操作 : 二维数组定义 N维数组定义 initArray(&A,n,bound1,bound2...boundn)
DestroyArray(&A) Value(A,&e,index1,index indexn) Assign(&A,e,index1,index indexn) }ADT Array 二维数组定义 其数据元素是一维数组的线形表 N维数组定义 其数据元素是N－1维数组的线形表

11 数组的顺序表示和实现 数组元素的两种存储方式 数组中元素在内存映象中的关系: 行主序存储 列主序存储 二维数组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 多维： LOC(j1,j2…jn)=LOC(0,0…0)+(b2*…*bn*j1+ b3*…*bn*j2 +…+bn*jn-1+jn )*L=LOC(0,0…0)+∑ciji cn=L,ci-1=bi*ci,1<i<=n

12 数组应用 例寻找两个串最长的公共子串 通常的匹配算法复杂度O(m*n2) 利用二维数组构造串之间的关系来求解
S1=“sgabacbadfgbacst” S2=“gabadfgab” 最大公共子串“badfg”。 算法时间复杂度 O(m*n)

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

14 4.4 数组的压缩 特殊形状矩阵的存储表示(下标从0开始) 对称矩阵：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 随机稀疏矩阵 非零元比零元少的多且分布无规律的矩阵。

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

16 三元组顺序表示例 (下标从1开始) (b) T.data (a) M.data i j e 1 2 12 3 9 -3 6 14 4 24
5 18 15 -7 i j e 1 3 -3 6 15 2 12 5 18 9 4 24 -7 14 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 (b) T.data (a) M.data cpot[1]=1 cpot[col]=cpot[col-1]+num[col-1] 2<=col<=nu col 1 2 3 4 5 6 7 num[col] cpot[col] 8 9

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

18 逻辑链接的顺序表 为了能随机存取三元组表示数组的任意一行非零元素，在建立三元组顺序表存储结构同时建立rpos[n]辅助数组,这种带行链接信息的三元组表称为“逻辑连接的顺序表” typedef struct{ Triple data[MAXSIZE+1]; int rpos[MAXMN+1]; 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 谢 谢

21 Status Concat(SString &T, SString S1, SString S2) {
if (S1[0]+S2[0] <= MAXSTRLEN) { // 未截断 for (i=1; i<=S1[0]; i++) T[i] = S1[i]; for (i=1; i<=S2[0]; i++) T[i+S1[0]] = S2[i]; T[0] = S1[0]+S2[0]; uncut = TRUE; } else if (S1[0] < MAXSTRLEN) { // 截断 for (i=S1[0]+1; i<=MAXSTRLEN; i++) T[i] = S2[i-S1[0]]; T[0] = MAXSTRLEN; uncut = FALSE; } else { // 截断(仅取S1) for (i=0; i<=MAXSTRLEN; i++) T[i] = S1[i]; uncut = FALSE; } return uncut; } // Concat

22 Status StrInsert(HString &S, int pos, HString T) {
// 1≤pos≤StrLength(S)＋1。在串S的第pos个字符之前插入串T。 if (pos < 1 || pos > S.length+1) return ERROR; if (T.length) { // T非空,则重新分配空间,插入T if (!(S.ch = (char *)realloc(S.ch,(S.length+T.length) *sizeof(char)))) return ERROR; for (i=S.length-1; i>=pos-1; --i) // 为插入T而腾出位置 S.ch[i+T.length] = S.ch[i]; for (i=0; i<T.length; i++) // 插入T S.ch[pos-1+i] = T.ch[i]; S.length += T.length; } return OK; } // StrInsert

23 int Index(SString S, SString T, int pos) {
// 返回子串T在主串S中第pos个字符之后的位置。若不存在，则函数值为0。 int i = pos, j = 1; while (i <= S[0] && j <= T[0]) { if (S[i] == T[j]) { // 继续比较后继字符 ++i; ++j; } else { // 指针后退重新开始匹配 i = i-j+2; j = 1; } if (j > T[0]) return i-T[0]; //i-j+1 j=T[0]+1 else return 0; } // Index

24 对称阵

25 条带阵

26 三元组存储数组的快速转置 Status FastTransposeSMatrix(TSMatrix M, TSMatrix &T) { // 算法5.2 // 采用三元组顺序表存储表示，求稀疏矩阵M的转置矩阵T T.mu = M.nu; T.nu = M.mu; T.tu = M.tu; if (! T.tu) return FAIL; for (col=1; col<=M.nu; ++col) num[col] = 0; for (t=1; t<=M.tu; ++t) // 求 M 中每一列所含非零元的个数 ++num[M.data[t].j]; cpot[1] = 1; // 求 M 中每一列的第一个非零元在 b.data 中的序号 for (col=2; col<=M.nu; ++col) cpot[col] = cpot[col-1]+num[col-1]; for (p=1; p<=M.tu; ++p) { col = M.data[p].j; q = cpot[col]; T.data[q].i =M.data[p].j; T.data[q].j =M.data[p].i; T.data[q].e =M.data[p].e; ++cpot[col]; } // for } // FastTransposeSMatrix