第4章 串、数组和广义表 丽水学院工学院

第2章 线性表 第3章 栈和队列 第4章 串、数组和广义表 线性结构 可表示为：（a1 , a2 , ……, an） 2018年11月15日

调用标准库函数 #include<string.h> 串比较，strcmp(char s1,char s2) 串复制，strcpy(char to,char from) 串连接，strcat(char to,char from) 求串长，strlen(char s) …… 2018年11月15日

第4章　串、数组和广义表 教学内容 4.1 串 4.2 数组 4.3 广义表 2018年11月15日

教学目标 1. 了解串的存储方法，理解串的两种模式匹配算法，重点掌握BF算法。 2. 明确数组和广义表这两种数据结构的特点，掌握数组地址计算方法，了解几种特殊矩阵的压缩存储方法。 3.掌握广义表的定义、性质及其GetHead和GetTail的操作。 1. 掌握串的存储方法，理解串的两种模式匹配算法； 2. 明确数组和广义表这两种数据结构的特点，掌握数组存储时地址计算方法，了解几种特殊矩阵的压缩存储方法。 2018年11月15日

4.1 串的定义 串(String)----零个或多个字符组成的有限序列 串名 串值 n n=0 串长 空串 2018年11月15日

a=‘BEI’, b=‘JING’ c=‘BEIJING’ d=‘BEI JING’ 子串 主串 字符位置 子串位置 串相等 空格串 2018年11月15日

4.2 案例引入 案例4.1 ：病毒感染检测 研究者将人的DNA和病毒DNA均表示成由一些字母组成的字符串序列。 例如，假设病毒的DNA序列为baa，患者1的DNA序列为aaabbba，则感染，患者2的DNA序列为babbba，则未感染。 （注意，人的DNA序列是线性的，而病毒的DNA序列是环状的)

4.3 串的类型定义、存储结构及运算 ADT String { 数据对象: 数据关系: 基本操作: (1) StrAssign (&T,chars) //串赋值 (2) StrCompare (S,T) //串比较 (3) StrLength (S) //求串长 (4) Concat(&T,S1,S2) //串联

(5) SubString(&Sub,S,pos,len) //求子串 (6) StrCopy(&T,S) //串拷贝 (7) StrEmpty(S) //串判空 (8) ClearString (&S) //清空串 (9) Index(S,T,pos) //子串的位置 (11) Replace(&S,T,V) //串替换 (12) StrInsert(&S,pos,T) //子串插入 (12) StrDelete(&S,pos,len) //子串删除 (13) DestroyString(&S) //串销毁 }ADT String 2018年11月15日

串的存储结构 顺序存储 链式存储 2018年11月15日

顺序存储表示 typedef struct{ char *ch; //若串非空,则按串长分配存储区, //否则ch为NULL int length; //串长度 }HString;

链式存储表示

链式存储表示 #define CHUNKSIZE 80 //可由用户定义的块大小 typedef struct Chunk{ char ch[CHUNKSIZE]; struct Chunk *next; }Chunk; typedef struct{ Chunk *head,*tail; //串的头指针和尾指针 int curlen; //串的当前长度 }LString; 2018年11月15日

可将多个字符存放在一个结点中，以克服其缺点 链式存储表示 优点：操作方便 缺点：存储密度较低 实际分配的存储位 串值所占的存储位 存储密度 = 可将多个字符存放在一个结点中，以克服其缺点 2018年11月15日

串的模式匹配算法 算法目的： 算法种类： 确定主串中所含子串第一次出现的位置（定位） 即如何实现教材P72 Index(S,T,pos)函数 BF算法（又称古典的、经典的、朴素的、穷举的） KMP算法（特点：速度快） 算法种类： 2018年11月15日

BF算法设计思想 i S : a b a b c a b c a c b a b T : a b c j 北京林业大学信息学院

BF算法设计思想 Index(S,T,pos) 将主串的第pos个字符和模式的第一个字符比较， 若相等，继续逐个比较后续字符； 若不等，从主串的下一字符起，重新与模式的第一个字符比较。 直到主串的一个连续子串字符序列与模式相等 。返回值为S中与T匹配的子序列第一个字符的序号，即匹配成功。 否则，匹配失败，返回值 0

BF算法描述（算法4.1） int Index(Sstring S,Sstring T,int pos){ 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]; else return 0; }

总次数为：(n-m)*m+m＝(n-m+1)*m 若m<<n，则算法复杂度O(n*m) BF算法时间复杂度 例： S=‘0000000001’，T=‘0001’，pos=1 若n为主串长度，m为子串长度，最坏情况是 主串前面n-m个位置都部分匹配到子串的最后一位，即这n-m位各比较了m次 最后m位也各比较了1次 总次数为：(n-m)*m+m＝(n-m+1)*m 若m<<n，则算法复杂度O(n*m)

KMP（Knuth Morris Pratt）算法 《计算机程序设计艺术 第1卷 基本算法》   《计算机程序设计艺术 第2卷 半数值算法》 《计算机程序设计艺术 第3卷 排序与查找》 http://www-cs-faculty.stanford.edu/~knuth/ 2018年11月15日

KMP算法设计思想 利用已经部分匹配的结果而加快模式串的滑动速度？ 且主串S的指针i不必回溯！可提速到O(n+m)！ S=‘a b a b c a b c a c b a b’ a b a S=‘a b a b c a b c a c b a b’ T=‘a b c a c’ a b c T=‘a b c a c’ i i i k k S=‘a b a b c a b c a c b a b’ T=‘a b c a c’ k

因p1≠p2,s2=p2,必有s2≠p1,又因p1=p3,s3=p3,所以必有s3=p1。因此,第二次匹配可直接从i=4, j=2开始。

改进：每趟匹配过程中出现字符比较不等时，不回溯主指针i，利用已得到的“部分匹配”结果将模式向右滑动尽可能远的一段距离，继续进行比较。

s1 s2 s3…si-j+1 si-j+2…si-2 si-1 si si+1 ‖ ‖ ‖ ‖ ≠ p1 p2 … pj-2 pj-1 pj pj+1 ‖ ‖ p1 … pk-1 pk pk+1 ① “p1p2…pk-1” = “si-k+1si-k+2…si-1” ②“pj-k+1pj-k+2…pj-1” = “si-k+1si-k+2…si-1”（部分匹配） ③ “p1p2…pk-1” = “pj-k+1pj-k+2…pj-1” (真子串）

为此,定义next[j]函数，表明当模式中第j个字符与主串中相应字符“失配”时，在模式中需重新和主串中该字符进行比较的字符的位置。 max{ k|1<k<j,且“p1…pk-1”=“pj-k+1…pj-1” } 当此集合非空时 0 当j=1时 1 其他情况 next[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]; /*i不变,j后退*/ } if (j>T[0]) return i-T[0]; /*匹配成功*/ else return 0; /*返回不匹配标志*/

如何求next函数值 1. next[1] = 0;表明主串从下一字符si+1起和模式串重新开始匹配。i = i+1; j = 1; 2. 设next[j] = k，则next[j+1] = ? ①若pk=pj，则有“p1…pk-1pk”=“pj-k+1…pj-1pj” ，如果在 j+1发生不匹配，说明next[j+1] = k+1 = next[j]+1。 ②若pk≠pj，可把求next值问题看成是一个模式匹配问 题，整个模式串既是主串，又是子串。

p1 p2…pj-k+1…pj-1 pj pj+1 next[j]=k ‖ ‖ ≠ p1 … pk-1 pk pk+1 next[k]=k’ p1…… pk’ pk’+1 next[k’]=k” p1… pk’’ pk’’+1 next[k’’’]=k’’’ 若pk’=pj，则有“p1…pk’”=“pj-k’+1…pj”， next[j+1]=k’+1=next[k]+1=next[next[j]]+1. 若pk”=pj ，则有“p1…pk””=“pj-k”+1…pj”， next[j+1]=k”+1=next[k’]+1=next[next[k]]+1. next[j+1]=1.

模式串 a b c a a b b c a b c a a b d a b j 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 模式串 a b c a a b b c a b c a a b d a b next[j] 1 1 1 2 2 3 1 1 2 3 4 5 6 7 1 2

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

KMP算法的时间复杂度 设主串s的长度为n,模式串t长度为m,在KMP算法中求next数组的时间复杂度为O(m),在后面的匹配中因主串s的下标不减即不回溯,比较次数可记为n,所以KMP算法总的时间复杂度为O(n+m)。

next[j] = k，而pj=pk，则 主串中si和pj不等时，不需再和pk进行比较，而直接和pnext[k]进行比较。 模式 a a a a b next[j] 0 1 2 3 4 nextval[j] 0 0 0 0 4 next函数的改进 i=4 a a a b a a a a b a a a a ① a a a ② a a ③ a a a a a b i = 5; j = 1 j=4 j=3 next[j] = k，而pj=pk，则 主串中si和pj不等时，不需再和pk进行比较，而直接和pnext[k]进行比较。 j=2 j=1

模式串 a b c a a b b c a b c a a b d a b j 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 模式串 a b c a a b b c a b c a a b d a b next[j] 0 1 1 1 2 2 3 1 1 2 3 4 5 6 7 1 2 nextval[j] 1 1 2 1 3 1 1 1 2 1 7 1

void get_nextval(SString T, int &nextval[]) { i= 1; nextval[1] = 0; j = 0; while( i<T[0]){ if(j==0 || T[i] == T[j]){ ++i; ++j; if(T[i] != T[j]) nextval[i] = j; else nextval[i] = nextval[j]; } else j = nextval[j]; next[i] = j;

4.4 数组 本节所讨论的数组与高级语言中的数组区别： 高级语言中的数组是顺序结构； 　高级语言中的数组是顺序结构； 　而本章的数组既可以是顺序的，也可以是链式结构，用户可根据需要选择。

数组的抽象数据类型 ADT Array { 数据对象: 数据关系:

基本操作: }ADT Array (1) InitArray (&A,n,bound1, boundn) //构造数组A (2) DestroyArray (&A) // 销毁数组A (3) Value(A,&e,index1,…,indexn) //取数组元素值 (4) Assign (A,&e,index1,…,indexn) //给数组元素赋值 }ADT Array 2018年11月15日

LOC(i-1)+l = a+i*l, i > 0 一维数组 a, i = 0 LOC(i) = LOC(i-1)+l = a+i*l, i > 0 0 1 2 3 4 5 6 7 8 9 a 35 27 49 18 60 54 77 83 41 02 l l l l l l l l l l a+i*l LOC(i) = LOC(i-1)+l = a+i*l

二维数组

数组的顺序存储 以行序为主序 C, PASCAL

以列序为主序 FORTRAN

a[n][m] 二维数组的行序优先表示 设数组开始存放位置 LOC( 0, 0 ) = a LOC ( j, k ) = a + j * m + k

三维数组 按页/行/列存放，页优先的顺序存储 ① ② ③

LOC ( i1, i2, i3 ) = a + i1* m2 * m3 + i2* m3 + i3 前i1页总 第i1页的 三维数组 a[m1][m2] [m3] 各维元素个数为 m1, m2, m3 下标为 i1, i2, i3的数组元素的存储位置： LOC ( i1, i2, i3 ) = a + 　i1* m2 * m3 + i2* m3 + i3 前i1页总 元素个数 第i1页的 前i2行总元素个数 第 i2 行前 i3 列元素个数

n维数组 各维元素个数为 m1, m2, m3, …, mn 下标为 i1, i2, i3, …, in 的数组元素的存储位置：

n维数组

练习 设有一个二维数组A[m][n]按行优先顺序存储，假设A[0][0]存放位置在644(10)，A[2][2]存放位置在676(10)，每个元素占一个空间，问A[3][3](10)存放在什么位置？脚注(10)表示用10进制表示。 设数组元素A[i][j]存放在起始地址为Loc ( i, j ) 的存储单元中 ∵ Loc ( 2, 2 ) = Loc ( 0, 0 ) + 2 * n + 2 = 644 + 2 * n + 2 = 676. ∴ n = ( 676 - 2 - 644 ) / 2 = 15 ∴ Loc ( 3, 3 ) = Loc ( 0, 0 ) + 3 * 15 + 3 = 644 + 45 + 3 = 692.

练习 设有二维数组A[10,20]，其每个元素占两个字节， A[0][0]存储地址为100，若按行优先顺序存储，则元素A[6,6]的存储地址为 ，按列优先顺序存储，元素A[6,6]的存储地址为 。 352 232 (6*20+6)*2+100=352 (6*10+6)*2+100=232

数组下标(i,j) 确定 存储地址 1. 对称矩阵 k= i(i-1)/2+j 当ij j(j-1)/2+i 当i<j aji 1. 对称矩阵 [特点] 在nn的矩阵a中，满足如下性质： aij=aji (1  i, j  n) [存储方法] 只存储下(或者上)三角(包括主对角线)的数据元素。共占用n(n+1)/2个元素空间。 k= i(i-1)/2+j 当ij j(j-1)/2+i 当i<j sa a11 a21 a22 a31 aij(aji) ann k 1 2 3 4 n(n+1)/2 aji aij

C C 2. 三角矩阵 k= (i-1)(2n-i+2)/2+j-i+1 ij k= i(i-1)/2+j ij 2. 三角矩阵 [特点] 对角线以下(或者以上)的数据元素(不包括对角线)全部为常数c。 [存储方法] 重复元素c共享一个元素存储空间，共占用n(n+1)/2+1个元素空间: sa[1.. n(n+1)/2+1] 上三角矩阵 下三角矩阵 k= (i-1)(2n-i+2)/2+j-i+1 ij k= i(i-1)/2+j ij n(n+1)/2+1 i>j n(n+1)/2+1 i<j C C 上三角矩阵 下三角矩阵

3. 对角矩阵（带状矩阵） [特点] 在nn的方阵中，非零元素集中在主对角线及其两侧共L(奇数)条对角线的带状区域内 — L对角矩阵。 [存储方法] 以对角线的顺序存储 8 2 3 0 0 0 4 2 0 3 0 0 5 7 7 6 8 0 0 9 6 9 1 5 0 0 6 1 4 2 0 0 0 2 8 3 1 2 3 4 5 6 -2 -1 1 2 3 3 8 5 2 0 6 1 2 8 2 7 9 4 3 4 7 6 1 8 5 9 6 2 i1=i-j j1=j |i-j|(L-1)/2 sa s[-2..2; 1..6] k 1 n*L 五对角矩阵 k=(i1+2)*n+j1=(i-j+2)*n+j |i-j|(L-1)/2

只存储带状区内的元素 除首行和末行，按每行 L个元素，共(n-2)L+(L+1)个元素。sa[1..(n-1)L+1] k=(i-1)L+1+(j-i) |i-j|(L-1)/2 8 2 3 0 0 0 4 2 0 3 0 0 5 7 7 6 8 0 0 9 6 9 1 5 0 0 6 1 4 2 0 0 0 2 8 3 sa 8 2 3 4 2 0 3 5 7 k 1 2 3 4 5 6 7 8 9 10 7 6 8 9 6 9 1 5 6 1 11 12 13 14 15 16 17 18 19 20 4 2 2 8 3 21 22 23 24 25 26

稀疏矩阵 [特点] 大多数元素为零。 [常用存储方法] 只记录每一非零元素(i,j,aij ) 节省空间，但丧失随机存取功能 顺序存储：三元组表 链式存储：十字(正交)链表 15 0 0 22 0 -15 0 11 3 0 0 0 0 0 0 -6 0 0 0 0 0 0 0 0 91 0 0 0 0 0 0 0 28 0 0 0 66

4.6 案例分析与实现 案例4.1 ：病毒感染检测 【案例分析】 因为患者的DNA和病毒DNA均是由一些字母组成的字符串序列，要检测某种病毒DNA序列是否在患者的DNA序列中出现过，实际上就是字符串的模式匹配问题。 可以利用BF算法，也可以利用更高效的KMP算法。 但与一般的模式匹配问题不同的是，此案例中病毒的DNA序列是环状的。 这样需要对传统的BF算法或KMP算法进行改进。

【案例实现】 对于每一个待检测的任务，假设病毒DNA序列的长度是m，因为病毒DNA序列是环状的，为了线性取到每个可行的长度为m的模式串，可将存储病毒DNA序列的字符串长度扩大为2m，将病毒DNA序列连续存储两次。 然后循环m次，依次取得每个长度为m的环状字符串，将此字符串作为模式串，将人的DNA序列作为主串，调用BF算法进行模式匹配。 只要匹配成功，即可中止循环，表明该人感染了对应的病毒；否则，循环m次结束循环时，可通过BF算法的返回值判断该人是否感染了对应的病毒。

【算法步骤】 ① 从文件中读取待检测的任务数num。 ② 根据num个数依次检测每对病毒DNA和人的DNA是否匹配，循环num次，执行以下操作： 从文件中分别读取一对病毒DNA序列和人的DNA序列； 设置标志性变量flag，用来标识是否匹配成功，初始为0，表示未匹配； 病毒DNA序列的长度是m，将存储病毒DNA序列的字符串长度扩大为2m，将病毒DNA序列连续存储两次； 循环m次，重复执行以下操作： 依次取得每个长度为m的病毒DNA环状字符串； 将此字符串作为模式串，将人的DNA序列作为主串，调用BF算法进行模式匹配，将匹配结果返回赋值给flag； 若flag非0，表示匹配成功，中止循环，表明该人感染了对应的病毒。 退出循环时，判断flag的值，若flag非0，输出“YES”，否则，输出“NO”。

小结 1. 了解串的存储方法，理解串的两种模式匹配算法，重点掌握BF算法。 2. 明确数组和广义表这两种数据结构的特点，掌握数组地址计算方法。