04数据结构---数组与串

本章主要讲述数组、串与广义表,其中包括多维数组的概念与存储;特殊矩阵:对称矩阵,三对角矩阵;对称矩阵的压缩存储;稀疏矩阵:三元组表示的稀疏矩阵转置的直观方法,包括按列从小到大排序,行列交换;字符串,子串;字符串的一些基本操作:复制,连接,比较,长度等
展开查看详情

1.第四章 数组、串与广义表 东南大学计算机学院 方效林 方效林 本课件借鉴了清华大学殷人昆老师 和哈尔滨工业大学张岩老师的课件

2. 本章主要内容  多维数组的概念与存储  特殊矩阵  稀疏矩阵  字符串 2

3. 多维数组的概念与存储  多维数组是一维数组的扩展 二维数组 三维数组 3

4. 多维数组的概念与存储  多维数组存储在连续的空间中  存储地址计算方法(假设数组首地址为 a ,元素元素 大小为 l )  一维数组: a[m1] Loc(i)= a + i*l  二维数组: a[m1][m2] Loc(i, j)= a + ( i*m2 + j )*l  三维数组: a[m1][m2] [m3] Loc(i, j, k)= a + ( i*m2*m3 + j*m3 + k )*l  n 维数组: a[m1][m2] …[mn] 4

5. 特殊矩阵  二维数组也称为矩阵  特殊矩阵是指非零元素或零元素的分布有一定 规律的矩阵。  对称矩阵  三对角矩阵  利用特殊矩阵的性质,元素节省存储空间 a 00 a 01 0 0 0 0   a 00 a 01 a 02  a 0n  1  a a a  a 0 0 0   10 a 11 a 12  a 1n  1   10 11 12  0 a 21 a 22 a 23 0 0  A   a 20 a 21 a 22  a 2n  1  A                     0 0 0 a n  2n  3 a n  2n  2 a n  2n 1  a n  10 a n  11 a n  12  a n  1n  1    0 0 0 0 a n  1n  2 a n  1n  1  对称矩阵 三对角矩阵 5

6. 特殊矩阵  对称矩阵的压缩存储  设有一个 nn 的矩阵 A 。如果在在矩阵 中,元素 aij = aji ,元素则此矩阵是对称矩阵。  只保存对称矩阵的对角线和对角线以上 ( 或以下 ) 的元素,元素则称此为对称矩阵的压缩存储  压缩存储方式:用一维数组存储  a 00 a 01 a 02  a 0n  1   a a 11 a 12  a 1n  1   10 A   a 20 a 21 a 22  a 2n  1            a n  10 a n  11 a n  12  a n  1n  1  6

7. 特殊矩阵  对称矩阵的压缩存储  下三角阵存储: 用一维数组 B 存储对称矩阵 A 中 对角线及对角线以下的元素  矩阵 A 中元素 a[i][j] 对应一维数组 B 中的下标为 (i+1)*i/2 + j, i≥j  a 00  Loc(i, j) =    a 10 a 11  (j+1)*j/2 + i, i<j A   a 20 a 21 a 22          a a n  11 a n  12  a n  1n  1   n  10 0 1 2 3 4 5 6 7 8 n(n+1)/2-1 B a00 a10 a11 a20 a21 a22 a30 a31 a32 …… an-1n-1 7

8. 特殊矩阵  对称矩阵的压缩存储  上三角阵存储: 用一维数组 B 存储对称矩阵 A 中 对角线及对角线以上的元素  矩阵 A 中元素 a[i][j] 对应一维数组 B 中的下标为 (2n - i + 1)*i/2 + j-i, i≤j a 00 a 01 a 02  a 0n  1  Loc(i, j) =   (2n - j - 1)*j/2 + i, i > j  a 11 a 12  a 1n  1  A  a 22  a 2n  1         a n  1n  1   0 1 2 n-1 n n+1 2n-2 2n-1 n(n+1)/2-1 B a00 a01 a02 … a0n-1 a11 a12 … a1n-1 a22 … an-1n-1 8

9. 稀疏矩阵  设矩阵 A 中有 s 个非零元素,元素若 s 远远 小于矩阵元素的总数(即 s << m×n ),元素则称 A 为稀疏矩阵。  稀疏因子: δ = s/(m×n)  一般 δ ≤ 0.05 可称为稀疏  0 0 2 0 0 0 0    3 0 0  11 0 0 0  0 0 0  6 0 0 0  A 6 7  0 0 0 0 0  17 0    0 9 0 0 19 0 0  0 0 0  8 0 0  52   稀疏矩阵表示 9

10. 稀疏矩阵  用三元组 (i, j, aij) 表示稀疏矩阵一个元素 aij 行 列 值 (row) (col) (value) [0] 0 2 2 0 0 2 0 0 0 0  [1] 1 0 3   [2] 1 3 -11 3 0 0  11 0 0 0  [3] 2 3 -6 0 0 0  6 0 0 0  [4] 3 5 -17 A 6 7  0 0 0 0 0  17 0  [5] 4 1 9   [6] 4 4 19 0 9 0 0 19 0 0  [7] 5 3 -8 0 0 0  8 0 0  52   [8] 5 6 -52 三元组表示 稀疏矩阵表示 10

11. 稀疏矩阵  三元组表示的稀疏矩阵转置的直观方法  按列从小到大排序  行列交换 行 列 值 行 列 值 行 列 值 (row) (col) (value) (row) (col) (value) (row) (col) (value) [0] 0 2 2 [0] 1 0 3 [0] 0 1 3 [1] 1 0 3 [1] 4 1 9 [1] 1 4 9 [2] 1 3 -11 [2] 0 2 2 [2] 2 0 2 [3] 2 3 -6 [3] 1 3 -11 [3] 3 1 -11 [4] 3 5 -17 [4] 2 3 -6 [4] 3 2 -6 [5] 4 1 9 [5] 5 3 -8 [5] 3 5 -8 [6] 4 4 19 [6] 4 4 19 [6] 4 4 19 [7] 5 3 -8 [7] 3 5 -17 [7] 5 3 -17 [8] 5 6 -52 [8] 5 6 -52 [8] 6 5 -52 11

12. 稀疏矩阵  三元组表示的稀疏矩阵转置的扫描方法  假设 A 有 Cols 列,元素则扫描 Cols 趟  第 k 趟扫描在表中找列号为 k 的三元组,元素取出,元素交 换行列号 行 列 值 行 列 值 (row) (col) (value) (row) (col) (value) [0] 0 2 2 扫描列号为 0 的三元组 [0] 0 1 3 [1] 1 0 3 扫描列号为 1 的三元组 [1] 1 4 9 [2] 1 3 -11 扫描列号为 2 的三元组 [2] 2 0 2 [3] 2 3 -6 扫描列号为 3 的三元组 [3] 3 1 -11 [4] 3 5 -17 扫描列号为 4 的三元组 [4] 3 2 -6 [5] 4 1 9 扫描列号为 5 的三元组 [5] 3 5 -8 [6] 4 4 19 扫描列号为 6 的三元组 [6] 4 4 19 [7] 5 3 -8 [7] 5 3 -17 [8] 5 6 -52 [8] 6 5 -52 12

13. 稀疏矩阵  三元组表示的稀疏矩阵转置的快速方法  统计各列非零数 rowSize( 扫描三元组表 )  计算各列在转置三元组中的索引位置 rowStart  扫描三元组表,元素放入相应索引位置,元素相应索引加 1 0 0 2 0 0 0 0  行 列 值 行 列 值   3 0 0  11 0 0 0  (row) (col) (value) (row) (col) (value) 0 0 0  6 0 0 0  [0] 0 2 2 [0] 0 1 3 A 67  [1] 1 0 3 [1] 1 4 9 0 0 0 0 0  17 0    [2] 1 3 -11 [2] 2 0 2 0 9 0 0 19 0 0  [3] 2 3 -6 [3] 3 1 -11 0 0 0  8 0 0  52   [4] 3 5 -17 [4] 3 2 -6 rowSize 1 1 1 3 1 1 1 [5] 4 1 9 [5] 3 5 -8 [6] 4 4 19 [6] 4 4 19 rowStart 0 1 2 3 6 7 8 [7] 5 3 -8 [7] 5 3 -17 1 2 3 4 7 8 9 [8] 5 6 -52 [8] 6 5 -52 5 6

14. 字符串  字符串  n(n≥0) 个字符的一个有限序列,元素简称为串  记为 S = “a0 a1 a2 … an-1”  n 是串的长度,元素 n 等于 0 的串叫空串  子串  串中连续若干个字符组成的串  S=“maintenance” ,元素 P=“ten” 是 S 的子串,元素 P 在 S 中的位置为 4 (从第 0 个字符开始) 14

15. 字符串  字符串的一些基本操作 typedef struct {  复制 strcpy char ch[maxSize]; int length;  连接 strcat } SeqString;  比较 strcmp  长度 strlen 15

16. 字符串  字符串的穷举模式匹配算法  匹配失败时,元素目标串 T 回溯,元素模式串 P 从头开始 T t0 t1 t2 t3 … tm-3 tm-2 tm-1 … tn-1 第1趟 P p0 p1 p2 p3 … pm-3 pm-2 pm-1 第2趟 P p0 p1 p2 p3 … pm-3 pm-2 pm-1 第3趟 P p0 p1 p2 p3 … pm-3 pm-2 pm-1 … … 时间复杂度 O(m*n) 16

17. 字符串  字符串的穷举模式匹配算法  匹配失败时,元素目标串 T 回溯,元素模式串 P 从头开始 T a b b a b a T a b b a b a ≠ ≠ P a b a P a b a 第1趟 第2趟 T a b b a b a T a b b a b a ≠ P a b a P a b a 第3趟 第4趟 17

18. 字符串  字符串的改进模式匹配算法 T … a b c d a b c d x … ≠ P a b c d a b c d e P a b c d a b c d e 例子: P 中重复出现 abcd ,元素但是 e 和 x 不匹配时,元素 可直接向右滑动 4 个字符开始匹配,元素可少匹配 4 趟 18

19. 字符串  字符串的改进模式匹配算法 T … ts ts+1 ts+2 ts+3 … ts+j-3 ts+j-2 ts+j-1 ts+j … ≠ 设 T[s, s+j-1] = P[0, j-1] ,元素 = = = = = = = = 但 T[s, s+j] ≠ P[0, j] P p0 p1 p2 p3 … pj-3 pj-2 pj-1 pj P p0 p1 p2 p3 … pj-3 pj-2 若 P[0, j-2] ≠ P[1, j-1] ,元素可少匹配 1 趟 P p0 p1 p2 p3 … pj-3 若又 P[0, j-3] ≠ P[2, j-1] ,元素可少匹配 2 趟 P p0 p1 p2 … pj-4 若又 P[0, j-4] ≠ P[3, j-1] ,元素可少匹配 3 趟 … … 类推直到前缀 P[0, k+1] ≠ 后缀 P[j-k-2, j-1] 但是前缀 P[0, k] = 后缀 P[j-k-1, j-1] 时,元素 可少匹配 j-k-1 趟,元素 相当于 P 直接向右滑动 j-k-1 个字符19

20. 字符串  字符串的改进模式匹配算法  对模式串 P 进行预处理,元素计算可以滑过多少个字 符 -1 ,元素当 j = 0 next( j ) = k+1 ,元素当 0 ≤ k < j-1, 且使 p0p1…pk=pj-k-1pj-k…pj-1 的最大数 0 ,元素其他情况 next(j) 直观含义: [0, j-1] 中前缀和后缀相等的最大长度 next(j) 直观作用:可滑过 j-next(j) 位不用匹配 下标 j 0 1 2 3 4 5 6 7 8 P a b c d a b c d e next(j) -1 0 0 0 0 1 2 3 4 20

21. 字符串  字符串的改进模式匹配算法  对模式串 P 进行预处理,元素计算可以滑过多少个字 符 -1 ,元素当 j = 0 next( j ) = k+1 ,元素当 0 ≤ k < j-1, 且使 p0p1…pk=pj-k-1pj-k…pj-1 的最大数 0 ,元素其他情况 next(j)=-1 表示匹配失败时,元素 T 的指针加 1 ,元素 P 的指针指向 p[0] next(j)=k+1 表示匹配失败时,元素 P 的指针指向 p[k+1] ,元素 next(j)=0 表示匹配失败时,元素 P 的指针指向 p[0] T … b c … ≠ 此例中模式串 P 的 next[0]=- P a b c d a b c d e 1 ,元素 T 指针加 1 ,元素 P 指向 p[0] ,元素 即 T 中 c 与 P 中 p[0]=a 进行 P a b c d a b c d e 21 比较

22. 字符串  字符串的改进模式匹配算法  对模式串 P 进行预处理,元素计算可以滑过多少个字 符 -1 ,元素当 j = 0 next( j ) = k+1 ,元素当 0 ≤ k < j-1, 且使 p0p1…pk=pj-k-1pj-k…pj-1 的最大数 0 ,元素其他情况 next(j)=-1 表示匹配失败时,元素 T 的指针加 1 ,元素 P 的指针指向 p[0] next(j)=k+1 表示匹配失败时,元素 P 的指针指向 p[k+1] ,元素 next(j)=0 表示匹配失败时,元素 P 的指针指向 p[0] T … a b c d a b c d x … ≠ 此例中模式串 P 的 P a b c d a b c d e next[8]=4 ,元素 T 中 x 直接与 P 中 p[4]=a 比较 P a b c d a b c d e 22

23. 字符串  字符串的改进模式匹配算法  对模式串 P 进行预处理,元素计算可以滑过多少个字 符 -1 ,元素当 j = 0 next( j ) = k+1 ,元素当 0 ≤ k < j-1, 且使 p0p1…pk=pj-k-1pj-k…pj-1 的最大数 0 ,元素其他情况 next(j)=-1 表示匹配失败时,元素 T 的指针加 1 ,元素 P 的指针指向 p[0] next(j)=k+1 表示匹配失败时,元素 P 的指针指向 p[k+1] ,元素 next(j)=0 表示匹配失败时,元素 P 的指针指向 p[0] T … a b c x … ≠ 此例中模式串 P 的 P a b c d a b c d e next[3]=0 ,元素 T 中 x 直接与 P 中 p[0]=a 比较 P a b c d a b c d e 23

24. 字符串  字符串的改进模式匹配算法  对模式串 P 进行预处理,元素计算可以滑过多少个字 符 -1 ,元素当 j = 0 next( j ) = k+1 ,元素当 0 ≤ k < j-1, 且使 p0p1…pk=pj-k-1pj-k…pj-1 的最大数 0 ,元素其他情况 可按定义直接计算 next ,元素下面介绍一种快速的计算 next 的方法 假设已知 next(j)=x ,元素现在计算 next(j+1) 若 px=pj ,元素则 next(j+1) = x+1 = next(j)+1 j=0;k=-1;next[0]=-1; 否则,元素设 next(x)=h ,元素 ( 此时有 p[0,h-1]=p[x-h,x-1]=p[j-h,j-1]) while(j<pLength) { 若 ph=pj ,元素则 next(j+1) = h+1 if(k==-1 || ch[j]==ch[k]) { 否则,元素令 next(h)=t, ( 此时有 p[0,t-1]=p[h-t,h- j++;k++;next[j]=k; 1]=p[j-t,j-1]) } 继续判断是否 pt=pj ,元素直到找到或者到 else k = next[k]; next(0) = -1 24 }

25. 字符串  字符串的改进模式匹配算法  对模式串 P 进行预处理,元素计算可以滑过多少个字 符 -1 ,元素当 j = 0 next( j ) = k+1 ,元素当 0 ≤ k < j-1, 且使 p0p1…pk=pj-k-1pj-k…pj-1 的最大数 0 ,元素其他情况 可按定义直接计算 next ,元素下面介绍一种快速的计算 next 的方法 下标 j 0 1 2 3 4 5 6 7 8 9 10 P a b a b c a b a b a x j=0;k=-1;next[0]=-1; next(j) -1 0 0 1 2 0 1 2 3 4 ? while(j<pLength) { if(k==-1 || ch[j]==ch[k]) { ≠ j++;k++;next[j]=k; = } else k = next[k]; next(10)=2+1=3 25 }

26. 字符串  字符串的改进模式匹配算法  对模式串 P 进行预处理,元素计算可以滑过多少个字 符 -1 ,元素当 j = 0 next( j ) = k+1 ,元素当 0 ≤ k < j-1, 且使 p0p1…pk=pj-k-1pj-k…pj-1 的最大数 0 ,元素其他情况 可按定义直接计算 next ,元素下面介绍一种快速的计算 next 的方法 下标 j 0 1 2 3 4 5 6 7 8 9 10 P a b a b c a b a b e x j=0;k=-1;next[0]=-1; next(j) -1 0 0 1 2 0 1 2 3 4 ? while(j<pLength) { if(k==-1 || ch[j]==ch[k]) { ≠ j++;k++;next[j]=k; ≠ } ≠ ,元素 - else k = next[k]; 1 26 } next(10)=0

27.作业: 计算下列 3 个串的 next 数组的值 aaab abcabaa abcxaabbabcabaacbacba 作业: 目标串 T=ababbaabaa ,元素模式串 P=aab ,元素 求 P 的 next 数组的值,元素并给出快速匹配过程 27