Chapter 数组矩阵和串PPT学习教案

1、会计学1Chapter 数组矩阵和串数组矩阵和串第1页/共93页第2页/共93页第3页/共93页第4页/共93页第5页/共93页v多维数组是一维数组的推广。多维数组是一维数组的推广。v多维数组的特点是每一个数据元素可以有多个直多维数组的特点是每一个数据元素可以有多个直接前驱和多个直接后继。接前驱和多个直接后继。v数组元素的下标一般具有固定的下界和上界，因数组元素的下标一般具有固定的下界和上界，因此它比其他复杂的非线性结构简单。此它比其他复杂的非线性结构简单。v例如二维数组的数组元素有两个直接前驱，两个例如二维数组的数组元素有两个直接前驱，两个直接后继，必须有两个下标（行、列）以标识该直接后继，

2、必须有两个下标（行、列）以标识该元素的位置。元素的位置。第6页/共93页第7页/共93页 第8页/共93页第9页/共93页第10页/共93页第11页/共93页01in-1第12页/共93页第13页/共93页第14页/共93页第15页/共93页第16页/共93页行优先存放：行优先存放： 设数组开始存放位置设数组开始存放位置 LOC(0, 0) = a, 每个每个元素占用元素占用 l 个存储单元个存储单元LOC ( j, k ) = a + ( j * m + k ) * l列优先存放：列优先存放： 设数组开始存放位置设数组开始存放位置 LOC(0, 0) = a, 每个每个元素占用元素占用 l

3、个存储单元个存储单元 LOC ( j, k ) = a + ( k * n + j ) * l第17页/共93页前前i1页页总元总元素素个数个数第第i1页页前前i2行行总元素总元素个数个数第第 i2 行行前前 i3 列列元素个元素个数数第18页/共93页第19页/共93页limianjnjknkj*111第20页/共93页nn1jkk1n1jjn21i)mi (),.,i,imap(i11jnkk2njjn21i)mi (),.,i,imap(i第21页/共93页第22页/共93页w02w03w04w05w12w13w14w15w22w23w24w25w32w33w34w35w42w43w44

4、w45w52w53w54w55w62w63w64w65w72w73w74w75w82w83w84w85W=第23页/共93页第24页/共93页第25页/共93页第26页/共93页11121110122221201112111010020100Annnnnnnnaaaaaaaaaaaaaaaan对称矩阵中的元素关于主对角线对称对称矩阵中的元素关于主对角线对称，aij = aji， 0i, jn-1第27页/共93页11121110122221201112111010020100nnnnnnnnaaaaaaaaaaaaaaaa下三角矩阵第28页/共93页1112111012222120111211

5、1010020100nnnnnnnnaaaaaaaaaaaaaaaa第29页/共93页11121110122221201112111010020100nnnnnnnnaaaaaaaaaaaaaaaa若若 i j, 数组元素数组元素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行元素总数 第i行第j个元素前元素个数第30页/共93页n若若 i j，数组元素，数组元素 Ai

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

7、部在矩阵的下三角部分，在数组分，在数组 B 中没有存放。因此，找它的中没有存放。因此，找它的对称元素对称元素Aji。Aji在数组在数组 B 的第的第 (2*n- -j- -1) * j / 2 + i 的位置中找到。的位置中找到。第33页/共93页1121122232232221121110010000000000000000000AnnnnnnnnnnaaaaaaaaaaaaaB 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第34页/共93页第35页/共93页第36页/共93页第37页/共93页

8、0000280000000091039000000006000017000110150022000A76n设矩阵设矩阵 A 中有中有 s 个非零元素，若个非零元素，若 s 远远小远远小于矩阵元素的总数（即于矩阵元素的总数（即smn），则称），则称 A 为稀疏矩阵。为稀疏矩阵。第38页/共93页第39页/共93页第40页/共93页public: SparseMatrix (int Rw = drows, int Cl = dcols, int Tm = dterms); /构造函数 void Transpose(SparseMatrix& b); /转置 void Add (SparseMatr

9、ix& a, SparseMatrix& b); /a = a+b void Multiply (SparseMatrix& a, SparseMatrix& b); /a = a*bpvivate: int Rows, Cols, Terms; /行列非零元素数 Triple *smArray; /三元组表; 第41页/共93页第42页/共93页v一个一个 m n 的矩阵的矩阵 A，它的转置矩阵，它的转置矩阵 B 是一个是一个 n m 的的矩阵，且矩阵，且 Aij = Bji。即。即u矩阵矩阵 A 的行成为矩阵的行成为矩阵 B 的列的列u矩阵矩阵 A 的列成为矩阵的列成为矩阵 B 的行。的行

10、。v稀疏矩阵的转置运算要转化为对应三元组表的转置，稀疏矩阵的转置运算要转化为对应三元组表的转置，新生成的三元组也应以行、列次序排列。新生成的三元组也应以行、列次序排列。第43页/共93页 0000280000000091039000000006000017000110150022000稀疏矩阵稀疏矩阵 行行行行( (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 - -

11、- -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第44页/共93页0000015003901700000000006022280000000001100910000 行行行行( (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 17 7 6 5 5 3 3 3

12、39 9 7 6 6 0 0 1 16 6第45页/共93页原矩阵三元组表原矩阵三元组表 转置矩阵三元组表转置矩阵三元组表第46页/共93页第47页/共93页第48页/共93页 for (k = 0; k Cols; k+) /处理所有列号 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+; ; 第49页/共93页第50页

13、/共93页v为加速转置速度，建立辅助数组为加速转置速度，建立辅助数组 rowSize 和和 rowStart：urowSize记录矩阵转置前各列，即转置记录矩阵转置前各列，即转置矩阵各行非零元素个数；矩阵各行非零元素个数；urowStart记录各行非零元素在转置三元记录各行非零元素在转置三元组表中开始存放位置。组表中开始存放位置。v扫描矩阵三元组表，根据某项列号，确定它转置扫描矩阵三元组表，根据某项列号，确定它转置后的行号后的行号, 查查 rowStart 表表, 按查按查到的位置直接到的位置直接将该项存入转置三元组表中将该项存入转置三元组表中第51页/共93页A三元组三元组(0)(1)(2)

14、(3)(4)(5)(6)(7)行行row00112345列列col36153502值值value22151117-6399128第52页/共93页第53页/共93页 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 = smArrayi.row; B.smArrayj.value = smArrayi.value; rowStart

15、 smArrayi.col+; delete rowSize; delete rowStart; 第54页/共93页第55页/共93页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 6 14 4 1 - -4 5 5 3 6 3 8 7 1 - -9 8 4 2 第56页/共93页第57页/共93页第58页/共93页第59页/共93页第60页/共93页第61页/共93页第62页/

16、共93页第63页/共93页第64页/共93页第65页/共93页第66页/共93页第67页/共93页序序号号重载操作重载操作操作操作使用示例使用示例 (设使用操作的当前串设使用操作的当前串为为S：tsinghua) 1( ) (int pos, int len)取子串取子串S1 = S(3, 2), /S1结果为结果为 ng 2= (const AString& ob)判两串判两串相等相等S = S1 , /若若S与与S1相等相等, 结果为结果为true，否则为，否则为false 3!= (const AString& ob)判两串判两串不等不等S != S1 , /若若S与与S1不等，不等，

17、结果为结果为true，否则为，否则为false 4! ()判串空判串空否否!S , /若串若串S为空，结果为为空，结果为 true，否则为，否则为false第68页/共93页序序号号重载操作重载操作操作操作使用示例使用示例 (设使用操作的当前设使用操作的当前串为串为S：tsinghua) 5= (const AString& ob)串赋值串赋值S1 = S, /S1结果为结果为tsinghua 6+= (const AString& ob)串连接串连接若设若设S1为为 university, 执行执行S += S1, /S结果为结果为tsinghua university 7 (int i)取

18、第取第 i个字符个字符S5, /取出字符为取出字符为h第69页/共93页pos+len- -1 pos+len - -1 curLen- -1 curLen可以全部提取可以全部提取 只能从只能从pos取到串尾取到串尾i n f i n i t yi n f i n i t ypos = 2, len = 3pos = 5, len = 4f i ni t y第70页/共93页例：串例：串 st = “university”, pos = 3, len = 4使用示例使用示例 subSt = st(3, 4)提取子串提取子串 subSt = “vers”第71页/共93页第72页/共93页第73

19、页/共93页例：串例：串 st1 = “beijing ”, st2 = “university”, 使用示例使用示例 st1 += st2;连接结果连接结果 st1 = “beijing university” st2 = “university”第74页/共93页第75页/共93页i=2j=2i=1j=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第76页/共93页第77页/共93页第78页/共93页第79页/共93页 目标目标 Tt0 t1 t2 tm-1 tn-1 模式模式 patp0 p1 p2

20、 pm-1 目标目标 T t0 t1 t2 tm-1 tm tn-1 模式模式 pat p0 p1 pm-2 pm-1 目标目标 T t0 t1 ti ti+1 ti+m-2 ti+m-1 tn-1 模式模式 pat p0 p1 pm-2 pm-1第80页/共93页 T t0 t1 ts-1 ts ts+1 ts+2 ts+j 1 ts+j ts+j+1 tn-1 P p0 p1 p2 pj 1 pj 则有则有 ts ts+1 ts+2 ts+j-1 = p0 p1 p2 pj-1 (1)为使模式为使模式 P 与目标与目标 T 匹配，必须满足匹配，必须满足 p0 p1 p2 pj-1 pm-1

21、 = ts+1 ts+2 ts+3 ts+j ts+m如果如果 p0 p1 pj-2 p1 p2 pj-1 (2)则立刻可以断定则立刻可以断定 p0 p1 pj-2 ts+1 ts+2 ts+j-1下一趟必不匹配下一趟必不匹配p0 p1 pj-2第81页/共93页同样，若同样，若p0 p1 pj-3 p2 p3 pj-1则再下一趟也不匹配，因为有则再下一趟也不匹配，因为有p0 p1 pj-3 ts+2 ts+3 ts+j-1直到对于某一个直到对于某一个“k”值，使得值，使得 p0 p1 pk+1 pj-k-2 pj-k-1 pj-1 且且 p0 p1 pk = pj-k-1 pj-k pj-1则则 p0 p1 pk = ts+j-k-1 ts+j-k ts+j-1 pj-k-1 pj-k pj-1下一趟可以直接用下一趟可以直接用 pk+1 与与 ts+j 继续比较。继续比较。第82页/共93页第83页/共93页其其他他情情况况的的最最大大整整数数且且使使得得0,.ppp .ppp1