数组与串与广义表实用教案

《数组与串与广义表实用教案》由会员分享，可在线阅读，更多相关《数组与串与广义表实用教案（115页珍藏版）》请在装配图网上搜索。

1、1第四章第四章 数组、串与广义数组、串与广义(gungy)(gungy)表表第1页/共115页第一页，共115页。2一维数组一维数组的下标直接存取数组元素的值。的下标直接存取数组元素的值。35 27 49 18 60 54 77 83 41 020 1 2 3 4 5 6 7 8 9第2页/共115页第二页，共115页。3一维数组的定义一维数组的定义(dngy)和初始化和初始化#include main ( ) int a3 = 3, 5, 7 , *elem, i; /静态静态(jngti)数组数组 for (i = 0; i 3; i+) cout ai endl; elem = new

2、int3; /动态数组动态数组 for (i = 0; i elemi; for (i = 0; i 3; i+) cout *elem 0 a, i = 0 35 27 49 18 60 54 77 83 41 020 1 2 3 4 5 6 7 8 9l l l l l l l l l l a+i*la第6页/共115页第六页，共115页。7二维数组二维数组一维数组常被称为向量（一维数组常被称为向量（Vector）。）。二维数组二维数组 Amn 可看成是由可看成是由 m 个行向量个行向量组成的向量，也可看成是由组成的向量，也可看成是由 n 个列向量组个列向量组成的向量。成的向量。一个二维数

3、组类型可以定义为其分量一个二维数组类型可以定义为其分量(fn ling)类型为一维数组类型的一维数组类类型为一维数组类型的一维数组类型型: typedef T array2mn; /T为元为元素类型素类型 等价于：等价于： typedef T array1n; /行向行向量类型量类型 typedef array1 array2m; /二维二维数组类型数组类型第7页/共115页第七页，共115页。8同理，一个三维数组类型同理，一个三维数组类型(lixng)可以定义可以定义为其数据元素为二维数组类型为其数据元素为二维数组类型(lixng)的一的一维数组类型维数组类型(lixng)。静态定义的数组，

4、其维数和维界不再改变，静态定义的数组，其维数和维界不再改变，在编译时静态分配存储空间。一旦数组空间在编译时静态分配存储空间。一旦数组空间用完则不能扩充。用完则不能扩充。动态定义的数组，其维界不在说明语句中显动态定义的数组，其维界不在说明语句中显式定义，而是在程序运行中创建数组对象时式定义，而是在程序运行中创建数组对象时通过通过 new 动态分配和初始化，在对象销毁动态分配和初始化，在对象销毁时通过时通过 delete 动态释放。动态释放。用一维内存来表示多维数组，就必须按某种用一维内存来表示多维数组，就必须按某种次序将数组元素排列到一个序列中。次序将数组元素排列到一个序列中。第8页/共115页

5、第八页，共115页。9二维数组的动态二维数组的动态(dngti)定义和初定义和初始化始化#include int *A;int row = 3, col = 3; int i, j; A = new int *row;for (i = 0; i row; i+) Ai = new int col;for (i = 0; i row; i+) for (j = 0; j Aij; 第9页/共115页第九页，共115页。10111101121202111101101000mnananamaaamaaamaaaan行优先存放：n 设数组开始存放位置(wi zhi) LOC(0, 0) = a, 每个

6、元素占用 l 个存储单元n LOC ( j, k ) = a + ( j * m + k ) * l第10页/共115页第十页，共115页。11111101121202111101101000mnananamaaamaaamaaaa列优先存放(cnfng)： 设数组开始存放(cnfng)位置 LOC(0, 0) = a, 每个元素占用 l 个存储单元 LOC ( j, k ) = a + ( k * n + j ) * l第11页/共115页第十一页，共115页。12三维数组三维数组各维元素个数为各维元素个数为 m1, m2, m3下标为下标为 i1, i2, i3的数组元素的存储地址的数组元

7、素的存储地址(dzh)：（按页行列存放）（按页行列存放）LOC ( i1, i2, i3 ) = a + ( i1* m2 * m3 + i2* m3 + i3 ) * l 前i1页总元素(yun s)个数第i1页前i2行总元素(yun s)个数第 i2 行前 i3 列元素个数第12页/共115页第十二页，共115页。13n n 维数组维数组各维元素个数为各维元素个数为 m1, m2, m3, , mn下标为下标为 i1, i2, i3, , in 的数组元素的存储的数组元素的存储(cn ch)地址：地址： LOC ( i1, i2, , in ) = a + ( i1*m2*m3*mn +

8、i2*m3*m4*mn+ + + in-1*mn + in ) * l limianjnjknkj*111第13页/共115页第十三页，共115页。14特殊特殊(tsh)矩阵矩阵特殊矩阵是指非零元素或零元素的分布有一特殊矩阵是指非零元素或零元素的分布有一定规律的矩阵。定规律的矩阵。特殊矩阵的压缩存储主要是针对特殊矩阵的压缩存储主要是针对(zhndu)阶数很高的特殊矩阵。为节省存储空间，对阶数很高的特殊矩阵。为节省存储空间，对可以不存储的元素，如零元素或对称元素，可以不存储的元素，如零元素或对称元素，不再存储。不再存储。对称矩阵对称矩阵三对角矩阵三对角矩阵第14页/共115页第十四页，共115页

9、。15对称矩阵对称矩阵(j zhn)的压缩存储的压缩存储设有一个设有一个 nn 的对称的对称(duchn)矩阵矩阵 A。11121110122221201112111010020100Annnnnnnnaaaaaaaaaaaaaaaan对称矩阵中的元素(yun s)关于主对角线对称，aij = aji， 0i, jn-1第15页/共115页第十五页，共115页。1611121110122221201112111010020100nnnnnnnnaaaaaaaaaaaaaaaa为节约存储为节约存储(cn ch)，只存对角线及对角，只存对角线及对角线以上的元素，或者只存对角线或对角线线以上的元素，

10、或者只存对角线或对角线以下的元素。前者称为上三角矩阵，后者以下的元素。前者称为上三角矩阵，后者称为下三角矩阵。称为下三角矩阵。下三角(snjio)矩阵第16页/共115页第十六页，共115页。1711121110122221201112111010020100nnnnnnnnaaaaaaaaaaaaaaaa上三角(snjio)矩阵把它们按行存放于一个一维数组把它们按行存放于一个一维数组 B 中，称之中，称之为对称矩阵为对称矩阵(j zhn) A 的压缩存储方式。的压缩存储方式。数组数组 B 共有共有 n + ( n - 1 ) + + 1 = n*(n+1)2 个元素。个元素。第17页/共11

11、5页第十七页，共115页。1811121110122221201112111010020100nnnnnnnnaaaaaaaaaaaaaaaa下三角(snjio)矩阵若 i j, 数组元素(yun s)Aij在数组B中的存放位置为 1 + 2 + + i + j = (i + 1)* i / 2 + jB a00 a10 a11 a20 a21 a22 a30 a31 a32 an-1n-1 0 1 2 3 4 5 6 7 8 n(n+1)/2-1前i行元素(yun s)总数 第i行第j个元素(yun s)前元素(yun s)个数第18页/共115页第十八页，共115页。19n若 i j，数组

12、元素 Aij 在矩阵的上三角(snjio)部分, 在数组 B 中没有存放，可以找它的对称元素Aji：= j *(j +1) / 2 + i n若已知某矩阵元素位于数组 B 的第 k个位置（k0），可寻找满足n i (i + 1) / 2 k (i + 1)*(i + 2) / 2n的 i, 此即为该元素的行号。n j = k - i * (i + 1) / 2n 此即为该元素的列号。n例，当 k = 8, 3*4 / 2 = 6 k j，数组元素(yun s)Aij在矩阵的下三角部分，在数组 B 中没有存放。因此，找它的对称元素(yun s)Aji。Aji在数组 B 的第 (2*n-j-1)

13、* j / 2 + i 的位置中找到。第21页/共115页第二十一页，共115页。22NoImage1121122232232221121110010000000000000000000AnnnnnnnnnnaaaaaaaaaaaaaB a00 a01 a10 a11 a12 a21 a22 a23 an-1n-2 an-1n-1 0 1 2 3 4 5 6 7 8 9 10第22页/共115页第二十二页，共115页。23三对角矩阵中除主对角线及在主对角线上三对角矩阵中除主对角线及在主对角线上 下下最临近的两条对角线上的元素外，所有其它最临近的两条对角线上的元素外，所有其它元素均为元素均为0。

14、总共。总共(znggng)有有3n-2个非零个非零元素。元素。将三对角矩阵将三对角矩阵A中三条对角线上的元素按行中三条对角线上的元素按行存放在一维数组存放在一维数组 B 中，且中，且a00存放于存放于B0。在三条对角线上的元素在三条对角线上的元素aij 满足满足 0 i n-1, i-1 j i+1在一维数组在一维数组 B 中中 Aij 在第在第 i 行，它前面行，它前面有有 3*i-1 个非零元素个非零元素, 在本行中第在本行中第 j 列前面列前面有有 j-i+1 个，所以元素个，所以元素 Aij 在在 B 中位置中位置为为 k = 2*i + j。第23页/共115页第二十三页，共115页

15、。24若已知三对角矩阵中某元素若已知三对角矩阵中某元素 Aij 在数组在数组 B 存放于第存放于第 k 个位置个位置(wi zhi)，则有，则有 i = (k + 1) / 3 j = k - 2 * i例如，当例如，当 k = 8 时，时， i = (8+1) / 3 = 3, j = 8 - 2*3 = 2 当当 k = 10 时，时， i = (10+1) / 3 = 3, j = 10 - 2*3 = 4第24页/共115页第二十四页，共115页。25 0000280000000091039000000006000017000110150022000A76稀疏稀疏(xsh)(xsh)矩

16、阵矩阵 (Sparse Matrix) (Sparse Matrix)n设矩阵 A 中有 s 个非零元素，若 s 远远小于矩阵元素的总数(zngsh)（即s mn），则称 A 为稀疏矩阵。第25页/共115页第二十五页，共115页。26设矩阵设矩阵 A 中有中有 s 个非零元素个非零元素(yun s)。令。令 e = s/(m*n),称称 e 为矩阵的稀疏因子。为矩阵的稀疏因子。有人认为有人认为 e0.05 时称之为稀疏矩阵。时称之为稀疏矩阵。在存储稀疏矩阵时，为节省存储空间，应在存储稀疏矩阵时，为节省存储空间，应只存储非零元素只存储非零元素(yun s)。但由于非零元。但由于非零元素素(yu

17、n s)的分布一般没有规律，故在存的分布一般没有规律，故在存储非零元素储非零元素(yun s)时，必须记下它所在时，必须记下它所在的行和列的位置的行和列的位置 ( i, j )。每一个三元组每一个三元组 (i, j, aij) 唯一确定了矩阵唯一确定了矩阵A的一个非零元素的一个非零元素(yun s)。因此，稀疏矩。因此，稀疏矩阵可由表示非零元的一系列三元组及其行阵可由表示非零元的一系列三元组及其行列数唯一确定。列数唯一确定。第26页/共115页第二十六页，共115页。27稀疏矩阵稀疏矩阵(j zhn)的定义的定义const int drows = 6, dcols = 7, dterms =

18、9;templatestruct Triple /三元组三元组 int row, col; /非零元素非零元素(yun s)行号行号/列号列号 E value; /非零元素非零元素(yun s)的的值值 void operator = (Triple& R) /赋值赋值 row = R.row; col = R.col; value = R.value; ;template class SparseMatrix 第27页/共115页第二十七页，共115页。28public: SparseMatrix (int Rw = drows, int Cl = dcols, int Tm = dterm

19、s); /构造函数 void Transpose(SparseMatrix& b); /转置(zhun zh) void Add (SparseMatrix& a, SparseMatrix& b); /a = a+b void Multiply (SparseMatrix& a, SparseMatrix& b); /a = a*bpvivate: int Rows, Cols, Terms; /行列非零元素数 Triple *smArray; /三元组表; 第28页/共115页第二十八页，共115页。29稀疏稀疏(xsh)矩阵的构造函数矩阵的构造函数template SparseMatri

20、x:SparseMatrix (int Rw, int Cl, int Tm) Rows = Rw; Cols = Cl; Terms = Tm; smArray = new TripleTerms; /三元组三元组表表 if (smArray = NULL) cerr “存储存储(cn ch)分配失败！分配失败！” endl; exit(1); ; 第29页/共115页第二十九页，共115页。30稀疏矩阵(j zhn)的转置n一个(y ) mn 的矩阵 A，它的转置矩阵 B 是一个(y ) nm 的矩阵，且 Aij = Bji。即n矩阵 A 的行成为矩阵 B 的列n矩阵 A 的列成为矩阵 B

21、 的行。n在稀疏矩阵的三元组表中，非零矩阵元素按行存放。当行号相同时，按列号递增的顺序存放。n稀疏矩阵的转置运算要转化为对应三元组表的转置。第30页/共115页第三十页，共115页。31 0000280000000091039000000006000017000110150022000稀疏(xsh)矩阵 行行行行( (r ro ow w) ) 列列列列( (c co ol l) ) 值值值值( (v va al lu ue e) ) 0 0 0 3 3 2 22 2 1 0 0 6 6 1 15 5 2 1 1 1 1 1 11 1 3 1 1 5 5 1 17 7 4 2 2 3 3 - -

22、 - -6 6 5 3 3 5 5 3 39 9 6 4 4 0 0 9 91 1 7 5 5 2 2 2 28 8第31页/共115页第三十一页，共115页。320000015003901700000000006022280000000001100910000 行行行行( (r ro ow w) ) 列列列列( (c co ol l) ) 值值值值( (v va al lu ue e) ) 0 0 0 4 4 9 91 1 1 1 1 1 1 1 11 1 2 2 2 5 5 2 28 8 3 3 3 0 0 2 22 2 4 3 3 2 2 - - - -6 6 5 5 5 1 1 1 1

23、7 7 6 5 5 3 3 3 39 9 7 6 6 0 0 1 16 6第32页/共115页第三十二页，共115页。33用三元组表表示的稀疏用三元组表表示的稀疏(xsh)矩阵及矩阵及其转置其转置原矩阵(j zhn)三元组表 转置矩阵(j zhn)三元组表第33页/共115页第三十三页，共115页。34稀疏稀疏(xsh)矩阵转置矩阵转置算法思想算法思想设矩阵列数为设矩阵列数为 Cols，对矩阵三元组表扫描，对矩阵三元组表扫描Cols 次。第次。第 k 次检测列号为次检测列号为 k 的项。的项。第第 k 次扫描找寻次扫描找寻(zhoxn)所有列号为所有列号为 k 的项，的项，将其行号变列号、列号

24、变行号，顺次存于转将其行号变列号、列号变行号，顺次存于转置矩阵三元组表。置矩阵三元组表。第34页/共115页第三十四页，共115页。35稀疏矩阵稀疏矩阵(j zhn)的转置的转置template void SparseMatrix :Transpose (SparseMatrix& B) /转置转置(zhun zh)this矩阵，转置矩阵，转置(zhun zh)结果结果由由B返回返回 B.Rows = Cols; B.Cols = Rows; B.Terms = Terms; /转置转置(zhun zh)矩阵的列数矩阵的列数,行数和非零元行数和非零元素个数素个数 if (Terms 0) in

25、t CurrentB = 0; /转置转置(zhun zh)三元三元组表存放指针组表存放指针 int i, k;第35页/共115页第三十五页，共115页。36 for (k = 0; k Cols; k+) /处理(chl)所有列号 for (i = 0; i Terms; i+) if (smArrayi.col = k) B.smArrayCurrentB.row = k; B.smArrayCurrentB.col = smArrayi.row; B.smArrayCurrentB.value= smArrayi.value; CurrentB+; ; 第36页/共115页第三十六页，

26、共115页。37设矩阵三元组表总共有设矩阵三元组表总共有 t 项，上述算法的时间项，上述算法的时间(shjin)代价为代价为 O ( n* t )。当非零元素的个。当非零元素的个数数 t 和和 m*n 同数量级时，算法同数量级时，算法transmatrix的的时间时间(shjin)复杂度为复杂度为O(m*n2)。若矩阵有若矩阵有 200 行，行，200 列，列，10,000 个非零元个非零元素，总共有素，总共有 2,000,000 次处理。次处理。快速转置算法的思想为：对快速转置算法的思想为：对 原矩阵原矩阵A 扫描一扫描一遍，按遍，按 A 中每一元素的列号，立即确定在转中每一元素的列号，立即

27、确定在转置矩阵置矩阵 B 三元组表中的位置，并装入它。三元组表中的位置，并装入它。第37页/共115页第三十七页，共115页。38n为加速转置速度，建立辅助数组 rowSize 和 rowStart：nrowSize记录矩阵转置前各列，即转置矩阵各行非零元素个数；nrowStart记录各行非零元素在转置三元组表中开始存放(cnfng)位置。n扫描矩阵三元组表，根据某项列号，确定它转置后的行号, 查 rowStart 表, 按查到的位置直接将该项存入转置三元组表中。第38页/共115页第三十八页，共115页。39A三元组三元组(0)(1)(2)(3)(4)(5)(6)(7)行行row001123

28、45列列col36153502值值value22151117-6399128第39页/共115页第三十九页，共115页。40稀疏矩阵稀疏矩阵(j zhn)的快速转置算法的快速转置算法template void SparseMatrix: FastTranspos (SparseMatrix& B) int *rowSize = new intCols; /列元素列元素(yun s)数数组数数组 int *rowStart = new intCols; /转置位置数转置位置数组组 B.Rows = Cols; B.Cols = Rows; B.Terms = Terms; if (Terms 0

29、) int i, j; for (i = 0; i Cols; i+) rowSizei = 0; 第40页/共115页第四十页，共115页。41 for (i = 0; i Terms; i+) rowSizesmArrayi.col+; rowStart0 = 0; for (i = 1; i Cols; i+) rowStarti = rowStarti-1+rowSizei-1; for (i = 0; i Terms; i+) j = rowStart smArrayi.col; B.smArrayj.row = smArrayi.col; B.smArrayj.col = smAr

30、rayi.row; B.smArrayj.value = smArrayi.value; rowStart smArrayi.col+; 第41页/共115页第四十一页，共115页。42 delete rowSize; delete rowStart;带行指针带行指针(zhzhn)数组的二元组表数组的二元组表稀疏稀疏(xsh)矩阵的三元组表可以用带行指针数矩阵的三元组表可以用带行指针数组的二元组表代替。组的二元组表代替。在行指针数组中元素个数与矩阵行数相等。第在行指针数组中元素个数与矩阵行数相等。第 i 个元素的下标个元素的下标 i 代表矩阵的第代表矩阵的第 i 行，元素的内行，元素的内容即为

31、稀疏容即为稀疏(xsh)矩阵第矩阵第 i 行的第一个非零元行的第一个非零元素在二元组表中的存放位置。素在二元组表中的存放位置。第42页/共115页第四十二页，共115页。43二元组表中每个二元组只记录非零元素的二元组表中每个二元组只记录非零元素的列号和元素值，且各二元组按行号列号和元素值，且各二元组按行号(xn ho)递增的顺序排列。递增的顺序排列。0020090000000000080000300040140000000130011012 行指针数组 row 0 0 1 3 2 4 3 6 4 7 5 7 二元组表 data col value 0 0 12 1 2 11 2 5 13 3

32、6 14 4 1 -4 5 5 3 6 3 8 7 1 -9 8 4 2 第43页/共115页第四十三页，共115页。44字符串字符串 (String)(String)字符串是字符串是 n ( 0 ) 个字符的有限序列，个字符的有限序列， 记作记作 S : “c1c2c3cn” 其中，其中，S 是串名字是串名字 “c1c2c3cn”是串值是串值 ci 是串中字符是串中字符 n 是串的长度，是串的长度，n = 0 称为空串。称为空串。例如例如, S = “Tsinghua University”。注意：空串和空白注意：空串和空白(kngbi)串不同，例如串不同，例如 “ ” 和和 “”“” 分别

33、表示长度为分别表示长度为1的空白的空白(kngbi)串和串和长度为长度为0的空串。的空串。第44页/共115页第四十四页，共115页。45串中任意个连续字符组成的子序列称为该串中任意个连续字符组成的子序列称为该串的子串，包含子串的串相应地称为主串。串的子串，包含子串的串相应地称为主串。通常将子串在主串中首次通常将子串在主串中首次(shu c)出现时，出现时，该子串首字符对应的主串中的序号，定义该子串首字符对应的主串中的序号，定义为子串在主串中的位置。例如，设为子串在主串中的位置。例如，设A和和B分分别为别为 A = “This is a string” B = “is”则则 B 是是 A 的子

34、串，的子串，A 为主串。为主串。B 在在 A 中出现了两次，首次中出现了两次，首次(shu c)出现所对应的出现所对应的主串位置是主串位置是2（从（从0开始）。因此，称开始）。因此，称 B 在在 A 中的位置为中的位置为2。特别地，空串是任意串的子串，任意串是特别地，空串是任意串的子串，任意串是其自身的子串。其自身的子串。第45页/共115页第四十五页，共115页。46通常在程序中使用通常在程序中使用(shyng)的串可分为两的串可分为两种：串变量和串常量。种：串变量和串常量。串常量在程序中只能被引用但不能改变它串常量在程序中只能被引用但不能改变它的值，即只能读不能写。通常串常量是由的值，即只

35、能读不能写。通常串常量是由直接量来表示的，例如语句直接量来表示的，例如语句 Error (“overflow”) 中中“overflow”是直接量。是直接量。但有的语言允许对串常量命名，以使程序但有的语言允许对串常量命名，以使程序易读、易写。如易读、易写。如C+中，可定义中，可定义 const char path = “dir/bin/appl”;这里这里path是一个串常量。串变量和其它类是一个串常量。串变量和其它类型的变量一样，其取值可以改变。型的变量一样，其取值可以改变。第46页/共115页第四十六页，共115页。47字符串的类定义字符串的类定义(dngy)#ifndef ASTRING

36、_H /定义定义(dngy)在文件在文件“Astring.h”中中#define ASTRING_H#define defaultSize = 128; /字符串的最大长度字符串的最大长度class AString /对象对象: 零个或多个字符的一个有限序列。零个或多个字符的一个有限序列。private: char *ch; /串存放数组串存放数组 int curLength; /串的实际长度串的实际长度int maxSize; /存放数组的最大长度存放数组的最大长度public: 第47页/共115页第四十七页，共115页。48 AString(int sz = defaultSize);

37、/构造函数构造函数 AString(const char *init ); /构造函数构造函数 AString(const AString& ob); /复制复制(fzh)构造函数构造函数 AString() delete ch; /析构函数析构函数 int Length() const return curLength; /求求长度长度 Astring& operator() (int pos, int len); /求子求子串串 bool operator = (AString& ob) const return strcmp (ch, ob.ch) = 0; /判串相等判串相等. 若串相

38、等若串相等, 则函数返回则函数返回true bool operator != (AString& ob) const return strcmp (ch, ob.ch) != 0; /判串不等判串不等. 若串不相等若串不相等, 则函数返回则函数返回true 第48页/共115页第四十八页，共115页。49 bool operator ! () const return curLength = 0; /判串空否。若串空判串空否。若串空, 则函数返回则函数返回true AString& operator = (AString& ob); /串串赋值赋值 AString& operator += (

39、AString& ob);/串连串连接接(linji) char& operator (int i);/取第取第 i 个个字符字符 int Find (AString& pat, int k) const; /串匹串匹配配;第49页/共115页第四十九页，共115页。50字符串的构造函数字符串的构造函数AString:AString(int sz) /构造函数：创建(chungjin)一个空串 maxSize = sz; ch = new charmaxSize+1; /创建(chungjin)串数组 if (ch = NULL) cerr defaultSize) ? len : defau

40、ltSize; ch = new charmaxSize+1; /创建串数组 if (ch = NULL) cerr “存储(cn ch)分配错 ! n”; exit(1); curLength = len; /复制串长度 strcpy(ch, init); /复制串值 ；第51页/共115页第五十一页，共115页。52字符串的复制字符串的复制(fzh)构造函数构造函数AString : AString(const AString& ob) /复制构造函数：从已有串ob复制 maxSize = ob.maxSize; /复制串最大长度 ch = new charcurLength+1; /创建

41、(chungjin)串数组 if (ch = NULL) cerr = 0 & pos+len-1 0) /提取子串 if (pos+len-1 = curLength) len = curLength - pos; /调整提取字符数 temp.curLength = len; /子串长度第56页/共115页第五十六页，共115页。57 for (int i = 0, j = pos; i len; i+, j+) temp.chi = chj; /传送串数组传送串数组 temp.chlen = 0; /子串结束子串结束 return temp;例：串例：串 st = “university”

42、, pos = 3, len = 4使用使用(shyng)示例示例 subSt = st(3, 4)提取子串提取子串 subSt = “vers”第57页/共115页第五十七页，共115页。58串重载串重载(zhn zi)(zhn zi)操作操作: : 串赋值串赋值AString& AString:operator = (const AString& ob) if (&ob != this) /若两个串相等(xingdng)为自我赋值 delete ch; ch = new charmaxSize+1;/重新分配 if (ch = NULL) cerr “存储分配失败!n ”; exit(1)

43、; curLength = ob.curLength; strcpy(ch,ob.ch); else cout “字符串自身赋值出错!n”; return this; 第58页/共115页第五十八页，共115页。59串重载串重载(zhn zi)(zhn zi)操作：取串操作：取串的第的第i i个字符个字符char AString:operator (int i) /串重载操作：取当前串串重载操作：取当前串*this的第的第i个字符个字符 if (i = curLength) cout = n) ? maxSize : n; /新空间大小 ch = new charm; if (ch = NUL

44、L) cerr “存储(cn ch)分配错!n ”; exit(1); maxSize = m; curLength = n; strcpy(ch, temp); /拷贝原串数组 strcat(ch, ob.ch); /连接ob串数组 第60页/共115页第六十页，共115页。61 delete temp; return this;例：串 st1 = “beijing ”, st2 = “university”, 使用示例 st1 += st2;连接(linji)结果 st1 = “beijing university” st2 = “university”第61页/共115页第六十一页，共1

45、15页。62串的模式匹配串的模式匹配定义定义 在主串中寻找子串（第一个字符）在主串中寻找子串（第一个字符）在串中的位置在串中的位置词汇词汇 在模式在模式(msh)匹配中，子串称为模匹配中，子串称为模式式(msh)，主串称为目标。，主串称为目标。示例示例 目标目标 T : “Beijing” 模式模式(msh) P : “jin” 匹配结果匹配结果 = 3 第62页/共115页第六十二页，共115页。63朴素朴素(p s)的模式匹配（的模式匹配（B-F算算法）法） 第第1趟趟 T a b b a b a P a b a 第第2趟趟 T a b b a b a P a b ai=2j=2i=1j=

46、0第3趟 T a b b a b a P a b a 第4趟 T a b b a b a P a b ai=2j=0i=6j=3第63页/共115页第六十三页，共115页。64朴素朴素(p s)的模式匹配算法的模式匹配算法int AString:Find(AString& pat, int k) const /在当前串中从第在当前串中从第 k 个字符开始寻找模式个字符开始寻找模式 pat 在当在当/前串中匹配的位置。若匹配成功前串中匹配的位置。若匹配成功, 则函数返回首则函数返回首/次匹配的位置次匹配的位置, 否则否则(fuz)返回返回-1。 int i, j, n = curLength,

47、m = pat.curLength; for (i = k; i = n-m; i+) for (j = 0; j 0，那么在下一趟比较时模式串，那么在下一趟比较时模式串 P的的起始比较位置是起始比较位置是 pnext(j)，目标串，目标串 T 的指针的指针不回溯不回溯(hu s)，仍指向上一趟失配的字符；，仍指向上一趟失配的字符；如果如果 j = 0，则目标串指针，则目标串指针 T 进一，模式串指进一，模式串指针针 P 回到回到 p0，继续进行下一趟匹配比较。，继续进行下一趟匹配比较。 第72页/共115页第七十二页，共115页。73 运用KMP算法的匹配过程第1趟 目标(mbio) a c

48、 a b a a b a a b c a c a a b c 模式 a b a a b c a c j=1 next(1) = 0，下次p0第2趟 目标(mbio) a c a b a a b a a b c a c a a b c 模式 a b a a b c a c j=0 下次p0, 目标(mbio)指针进 1 第3趟 目标(mbio) a c a b a a b a a b c a c a a b c 模式 a b a a b c a c j=5 next(5) = 2, 下次p2第4趟 目标(mbio) a c a b a a b a a b c a c a a b c 模式 (a

49、b) a a b c a c 第73页/共115页第七十三页，共115页。74用用KMPKMP算法实现算法实现(shxin)(shxin)的快速的快速匹配算法匹配算法int AString:fastFind(AString& pat, int k, int next) const /从从 k 开始寻找开始寻找 pat 在在 this 串中匹配的位置。若找串中匹配的位置。若找/到，函数返回到，函数返回 pat 在在 this 串中开始位置，否则函串中开始位置，否则函/数返回数返回-1。数组。数组next 存放存放 pat 的的nextj 值。值。 int posP = 0, posT = k;

50、/两个串的扫描指针两个串的扫描指针 int lengthP = pat.curLength; /模式串长度模式串长度(chngd) int lengthT = curLength; /目标串长度目标串长度(chngd) while (posP lengthP & posT lengthT) if (posP = -1 | pat.chposP = chposT) posP+; posT+; /对应字符匹对应字符匹配配第74页/共115页第七十四页，共115页。75else posP = nextposP; /求pat下趟比较位置 if (posP 0 时时 nj-1 = k:当当 k = -1

51、或或 j 0且且 pj-1 = pk，则，则 nj = k+1。当当 pj-1 pk 且且 k -1，令，令 k = nk，并让，并让循环循环(xnhun)直到条件不满足。直到条件不满足。当当 pj-1 pk 且且 k = -1，则，则 nj = 0。 第76页/共115页第七十六页，共115页。77以前面的例子以前面的例子(l zi)说明：说明：j01234567Pabaabcacnext j-10011201j=4k=1p3p1k=nk=0p3=p0n4= =k+1 =1j=3k=0n3= =k+1 =1j=2k=0p1p0k=nk= =-1n2= =k+1 =0j=1k=-1n1=k+1

52、=0j=0n0=-1j=5k=1p4=p1n5= =k+1 =2j=6k=2p5p2k=nk=0p5p0k=nk=-1n5=k+1=0j=7k=0p6=p0n7=k+1 =1第77页/共115页第七十七页，共115页。78对当前串计算对当前串计算(j sun)next(j sun)next特征向量特征向量的算法的算法void AString:getNext(int next) int j = 0, k = -1, lengthP = curLength; next0 = -1; while (j 0时，表的第一个表元素称为广义表时，表的第一个表元素称为广义表 的的表头（表头（head），除此之

53、外，其它表元素组），除此之外，其它表元素组成的表称为广义表的表尾（成的表称为广义表的表尾（tail）。）。第79页/共115页第七十九页，共115页。80广义广义(gungy)表的特性表的特性有次序有次序(cx)性性有长度有长度n有深度(shnd)n可共享n可递归A( ) A长度为0，深度为1B( 6, 2 ) B长度为2，深度为1C( a, ( 5, 3, x ) ) C长度为2，深度为2D( B, C, A ) D长度为3，深度为3E( B, D ) E长度为？ 深度为？F( 4, F ) F长度为？ 深度为？第80页/共115页第八十页，共115页。81广义广义(gungy)表的表头与表

54、尾表的表头与表尾广义表的第一个表元素广义表的第一个表元素(yun s)即为该表的即为该表的表头，除表头元素表头，除表头元素(yun s)外其他表元素外其他表元素(yun s)组成的表即为该表的表尾。组成的表即为该表的表尾。A( ) head(A) 和 tail(A) 不存在(cnzi)B( 6, 2 ) head(B) = 6, tail(B) = (2)C( a, ( 5, 3, x ) ) head(C) =aD( B, C, A ) tail(C) = (5,3,x)E( B, D ) head( (5,3,x) ) = (5,3,x)F( 4, F ) tail( (5,3,x) )

55、= ( ) 第81页/共115页第八十一页，共115页。82u vax y zu vax y zu vax y zd第82页/共115页第八十二页，共115页。83广义(gungy)表的表示list1 = (a, b, c, d, e)list2 = (a, (b, c, (d, e, f), (), g), h, (r, s, t)ahbcgsrtfedlist2alist1bdec第83页/共115页第八十三页，共115页。84广义广义(gungy)表结点定义表结点定义结点类型结点类型 utype：= 0, 表头；表头；= 1, 原子数据原子数据(shj)； = 2, 子表子表信息信息in

56、fo：utype = 0时时, 存放引用计数存放引用计数(ref)；utype = 1时时, 存放数据存放数据(shj)值值(value)；utype = 2时时, 存放指向子表表头的指针存放指向子表表头的指针(hlink)尾指针尾指针tlink：utype = 0时时, 指向该表第一个指向该表第一个结点；结点；utype 0时时, 指向同一层下一个结点指向同一层下一个结点 utype info tlink 第84页/共115页第八十四页，共115页。85广义(gungy)表的存储表示B0 11 h20 022D0 11 d1 e1 f0 11 c20 12220 21 aBCA1 b 0 1

57、第85页/共115页第八十五页，共115页。86广义(gungy)表的类定义#include #include template struct Items /返回值的类结构定义 int utype;/结点(ji din)类型0/1/2 union /联合int ref;/utype=0,存放引用计数T value;/utype=1,存放数值GenListNode *hlink; /utype=2,存放指向子表的指针 info;第86页/共115页第八十六页，共115页。87 Items() : utype(0), info.ref(0) /构造函数 Items(Items& R) /复制构造函

58、数 utype = R.utype; info = R.info; ;template struct GenListNode /广义表结点类定义 int utype;/0 / 1 / 2 GenListNode *tlink;/同层下一结点指针 union /等价变量 int ref; /存放(cnfng)引用计数T value;/存放(cnfng)数值GenListNode *hlink; /存放(cnfng)子表指针第87页/共115页第八十七页，共115页。88 info; GenListNode() /构造函数 : utype(0), tlink(NULL), info.ref(0)

59、GenListNode(GenListNode& R) /复制(fzh)构造函数 utype = R.utype; tlink = R.tlink; info = R.info; ;template class GenList /广义表类定义public:第88页/共115页第八十八页，共115页。89 Genlist(); /构造函数 GenList();/析构函数 bool Head (Items& x); /x 返回表头元素 bool Tail (GenList& lt); /lt 返回表尾 GenListNode *First(); /返回第一个元素 GenListNode *Next

60、 (GenListNode *elem);/返回表元素elem的直接后继元素 void Copy ( const GenList& R);/广义表的复制(fzh) int Length(); /计算广义表长度 int depth();/计算非递归表深度 第89页/共115页第八十九页，共115页。90private: GenListNode *first;/广义表头指针(zhzhn) GenListNode *Copy (GenListNode *ls); /复制一个ls指示的无共享非递归表 int Length (GenListNode *ls); /求由ls指示的广义表的长度 int de

61、pth (GenListNode *ls); /计算由ls指示的非递归表的深度 bool equal (GenListNode *s, GenListNode *t); /判以s和t为表头的两个表是否相等 void Remove (GenListNode *ls); /释放以ls为附加头结点的广义表第90页/共115页第九十页，共115页。91 void Createlist (istream& in, GenListNode *&ls); /从输入流对象输入广义表的字符串描述, /建立一个带头(di tu)结点的广义表结构friend istream& operator (istream&

62、in, GenList& L); ;第91页/共115页第九十一页，共115页。92广义表类的构造和访问广义表类的构造和访问(fngwn)成员成员函数函数template Genlist:GenList() /构造函数构造函数 GenListNode *first = new GenListNode; if (first = NULL) cerr “存储分配失败！存储分配失败！n”; exit(1); ;template bool GenList:Head (Items& x) /若广义表非空，则通过若广义表非空，则通过x返回其第一个元素的值返回其第一个元素的值/否则函数没有否则函数没有(mi

63、 yu)定义定义第92页/共115页第九十二页，共115页。93 if (first-tlink = NULL) return false;/空表空表 else /非空表非空表 x.utype = first-tlink-utype;x.info = first-tlink-info;return true; /x返回表返回表头的值头的值 ;template bool GenList:Tail(GenList& lt) /若广义表非空，则通过若广义表非空，则通过lt返回广义表除表头元素返回广义表除表头元素/以外其他以外其他(qt)元素组成的表，否则函数没有定元素组成的表，否则函数没有定义义 i

64、f (first-tlink = NULL) return false; /空表空表第93页/共115页第九十三页，共115页。94 else /非空表非空表 lt.first-utype = 0;/设置设置(shzh)头头结点结点 lt.first-info.ref = 0; lt.first-tlink = Copy(first-tlink-tlink); return true; ;template GenListNode *GenList:First() /返回广义表的第一个元素（若表空，则返回一个返回广义表的第一个元素（若表空，则返回一个/特定的空值特定的空值NULL） if (fi

65、rst-tlink = NULL) return NULL; /空表空表第94页/共115页第九十四页，共115页。95 else return first-tlink; /非非空表空表;template GenListNode *GenList:Next(GenListNode *elem) /返回表元素返回表元素(yun s)elem的直接后的直接后继元素继元素(yun s) if (elem-tlink = NULL) return NULL; else return elem-tlink;第95页/共115页第九十五页，共115页。96广义广义(gungy)表的递归算法表的递归算法一个

66、递归算法有两种：一个是递归函数的外一个递归算法有两种：一个是递归函数的外部调用；另一个是递归函数的内部调用。部调用；另一个是递归函数的内部调用。通常通常(tngchng)，把外部调用设置为共有函，把外部调用设置为共有函数，把内部调用设置为私有函数。数，把内部调用设置为私有函数。 广义表的复制(fzh)算法template /公有函数void GenList:Copy(const GenList& R) first = Copy(R.first); /调用私有函数;第96页/共115页第九十六页，共115页。97template /私有函数私有函数GenListNode* GenList:Copy(GenListNode *ls) /复制复制(fzh)一个一个 ls 指示的无共享子表的非递归表指示的无共享子表的非递归表 GenListNode *q = NULL; if (ls != NULL) q = new GenListNode; /处理当前的结点处理当前的结点q q-utype = ls-utype; /复制复制(fzh)结点类型结点类型 switch (ls-utype) /根