最新北京师范大学数据结构教学资料 第4章——数组、串与广义表PPT课件.ppt
《最新北京师范大学数据结构教学资料 第4章——数组、串与广义表PPT课件.ppt》由会员分享,可在线阅读,更多相关《最新北京师范大学数据结构教学资料 第4章——数组、串与广义表PPT课件.ppt(92页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、2 2一维数组一维数组数组是数组是相同类型的数据元素的集合相同类型的数据元素的集合而一维而一维数组的每个数组元素是一个序对,由数组的每个数组元素是一个序对,由下标下标(index)和值()和值(value)组成。)组成。n一维数组的示例一维数组的示例n在高级语言中,一维数组只能按元素的下标在高级语言中,一维数组只能按元素的下标直接存取数组元素的值。直接存取数组元素的值。35 27 49 18 60 54 77 83 41 020 1 2 3 4 5 6 7 8 99 9二维数组的动态定义和初始化二维数组的动态定义和初始化#include int *A;int row = 3, col = 3;
2、 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; 1010二维数组中数组元素的顺序存放二维数组中数组元素的顺序存放111101121202111101101000mnananamaaamaaamaaaan行优先存放:行优先存放: 设数组开始存放位置设数组开始存放位置 LOC(0, 0) = a, 每个每个元素占用元素占用 l 个存储单元个存储单元LOC ( j, k ) = a + ( j * m + k ) * l11 11
3、111101121202111101101000mnananamaaamaaamaaaa列优先存放:列优先存放: 设数组开始存放位置设数组开始存放位置 LOC(0, 0) = a, 每个每个元素占用元素占用 l 个存储单元个存储单元 LOC ( j, k ) = a + ( k * n + j ) * l1212三维数组三维数组n各维元素个数为各维元素个数为 m1, m2, m3n下标为下标为 i1, i2, i3的数组元素的存储地址:的数组元素的存储地址:(按页行列存放)(按页行列存放)LOC ( i1, i2, i3 ) = a + ( i1* m2 * m3 + i2* m3 + i3
4、) * l前前i1页页总元素总元素个数个数第第i1页页前前i2行行总元素总元素个数个数第第 i2 行行前前 i3 列列元素个元素个数数1313n n 维数组维数组n各维元素个数为各维元素个数为 m1, m2, m3, , mnn下标为下标为 i1, i2, i3, , in 的数组元素的存储地的数组元素的存储地址:址: LOC ( i1, i2, , in ) = a + ( i1*m2*m3*mn + i2*m3*m4*mn+ + + in-1*mn + in ) * llimianjnjknkj*1111414特殊矩阵特殊矩阵n特殊矩阵是指非零元素或零元素的分布有特殊矩阵是指非零元素或零元
5、素的分布有一定规律的矩阵。一定规律的矩阵。n特殊矩阵的压缩存储主要是针对阶数很高特殊矩阵的压缩存储主要是针对阶数很高的特殊矩阵。为节省存储空间,对可以不的特殊矩阵。为节省存储空间,对可以不存储的元素,如零元素或对称元素,不再存储的元素,如零元素或对称元素,不再存储。存储。u对称矩阵对称矩阵u三对角矩阵三对角矩阵1515对称矩阵的压缩存储对称矩阵的压缩存储n设有一个设有一个 n n 的对称矩阵的对称矩阵 A。11121110122221201112111010020100Annnnnnnnaaaaaaaaaaaaaaaan对称矩阵中的元素关于主对角线对称对称矩阵中的元素关于主对角线对称,aij
6、= aji, 0i, jn-1161611121110122221201112111010020100nnnnnnnnaaaaaaaaaaaaaaaan为节约存储,只存对角线及对角线以上的元为节约存储,只存对角线及对角线以上的元素,或者只存对角线或对角线以下的元素。素,或者只存对角线或对角线以下的元素。前者称为前者称为上三角矩阵上三角矩阵,后者称为,后者称为下三角矩阵下三角矩阵。下三角矩阵171711121110122221201112111010020100nnnnnnnnaaaaaaaaaaaaaaaa上三角矩阵n把它们按行存放于一个一维数组把它们按行存放于一个一维数组 B 中,称之中,称
7、之为对称矩阵为对称矩阵 A 的压缩存储方式。的压缩存储方式。n数组数组 B 共有共有 n + ( n - 1 ) + + 1 = n*(n+1)2 个元素。个元素。181811121110122221201112111010020100nnnnnnnnaaaaaaaaaaaaaaaa下三角矩阵若若 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
8、行(0i-1)元素总数 第i行第j个元素前元素个数1919n若若 i j,数组元素,数组元素 Aij 在矩阵的上三角部在矩阵的上三角部分分, 在数组在数组 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
9、例,当例,当 k = 8, 3*4 / 2 = 6 k j,数组元素,数组元素Aij在矩阵的下三角部在矩阵的下三角部分,在数组分,在数组 B 中没有存放。因此,找它的中没有存放。因此,找它的对称元素对称元素Aji。Aji在数组在数组 B 的第的第 (2*n- -j- -1) * j / 2 + i 的位置中找到。的位置中找到。22221121122232232221121110010000000000000000000AnnnnnnnnnnaaaaaaaaaaaaaB a00 a01 a10 a11 a12 a21 a22 a23 an-1n-2 an-1n-1 0 1 2 3 4 5 6 7
10、 8 9 102323n三对角矩阵中除主对角线及在主对角线上三对角矩阵中除主对角线及在主对角线上 下下最临近的两条对角线上的元素外,所有其它最临近的两条对角线上的元素外,所有其它元素均为元素均为0。总共有。总共有3n-2个非零元素。个非零元素。n将三对角矩阵将三对角矩阵A中三条对角线上的元素按行存中三条对角线上的元素按行存放在一维数组放在一维数组 B 中,且中,且a00存放于存放于B0。n在三条对角线上的元素在三条对角线上的元素aij 满足满足 0 i n-1, i-1 j i+1n在一维数组在一维数组 B 中中 Aij 在第在第 i 行,它前面有行,它前面有 3*i-1 个非零元素个非零元素
11、, 在本行中第在本行中第 j 列前面有列前面有 j-i+1 个,所以元素个,所以元素 Aij 在在 B 中位置为中位置为 k = 2*i + j。2424n若已知三对角矩阵中某元素若已知三对角矩阵中某元素 Aij 在数组在数组 B 存放于第存放于第 k 个位置,则有个位置,则有 i = (k + 1) / 3 j = k - 2 * in例如,当例如,当 k = 8 时,时, i = (8+1) / 3 = 3, j = 8 - 2*3 = 2 当当 k = 10 时,时, i = (10+1) / 3 = 3, j = 10 - 2*3 = 42525 0000280000000091039
12、000000006000017000110150022000A76稀疏矩阵稀疏矩阵 (Sparse Matrix)(Sparse Matrix)n设矩阵设矩阵 A 中有中有 s 个非零元素,若个非零元素,若 s 远远小于远远小于矩阵元素的总数(即矩阵元素的总数(即smn),则称),则称 A 为为稀疏矩阵。稀疏矩阵。2626n设矩阵设矩阵 A 中有中有 s 个非零元素。令个非零元素。令 e = s/(m*n),称称 e 为矩阵的稀疏因子。为矩阵的稀疏因子。n有人认为有人认为 e0.05 时称之为稀疏矩阵。时称之为稀疏矩阵。n在存储稀疏矩阵时,为节省存储空间,应只在存储稀疏矩阵时,为节省存储空间,
13、应只存储非零元素。但由于非零元素的分布一般存储非零元素。但由于非零元素的分布一般没有规律,故在存储非零元素时,必须记下没有规律,故在存储非零元素时,必须记下它所在的行和列的位置它所在的行和列的位置 ( i, j )。n每一个三元组每一个三元组 (i, j, aij) 唯一确定了矩阵唯一确定了矩阵A的一的一个非零元素。因此,稀疏矩阵可由表示非零个非零元素。因此,稀疏矩阵可由表示非零元的一系列三元组及其行列数唯一确定。元的一系列三元组及其行列数唯一确定。2727稀疏矩阵的定义稀疏矩阵的定义const int drows = 6, dcols = 7, dterms = 9;templatestru
14、ct Triple /三元组 int row, col; /非零元素行号/列号 E value; /非零元素的值 void operator = (Triple& R) /赋值 row = R.row; col = R.col; value = R.value; ;template class SparseMatrix 2828public: SparseMatrix (int Rw = drows, int Cl = dcols, int Tm = dterms); /构造函数 void Transpose(SparseMatrix& b); /转置 void Add (SparseMatr
15、ix& a, SparseMatrix& b); /a = a+b void Multiply (SparseMatrix& a, SparseMatrix& b); /a = a*bpvivate: int Rows, Cols, Terms; /行列非零元素数 Triple *smArray; /三元组表; 2929稀疏矩阵的构造函数稀疏矩阵的构造函数template SparseMatrix:SparseMatrix (int Rw, int Cl, int Tm) Rows = Rw; Cols = Cl; Terms = Tm; smArray = new TripleTerms;
16、/三元组表 if (smArray = NULL) cerr “存储分配失败!” endl; exit(1); ; 3030稀疏矩阵的转置稀疏矩阵的转置n一个一个 m n 的矩阵的矩阵 A,它的转置矩阵,它的转置矩阵 B 是一是一个个 n m 的矩阵,且的矩阵,且 Aij = Bji。即即u矩阵矩阵 A 的行成为矩阵的行成为矩阵 B 的列的列u矩阵矩阵 A 的列成为矩阵的列成为矩阵 B 的行。的行。n在稀疏矩阵的三元组表中,非零矩阵元素按在稀疏矩阵的三元组表中,非零矩阵元素按行存放。当行号相同时,按列号递增的顺序行存放。当行号相同时,按列号递增的顺序存放。存放。n稀疏矩阵的转置运算要转化为对应
17、三元组表稀疏矩阵的转置运算要转化为对应三元组表的转置。的转置。3131 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 - - - -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 83
18、2320000015003901700000000006022280000000001100910000 行行行行( (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 39 9 7 6 6 0 0 1 16 63333用三元组表表示的稀疏矩阵及其转置用三元组表表示的稀疏矩阵及其转置原矩阵三元组
19、表原矩阵三元组表 转置矩阵三元组表转置矩阵三元组表3434稀疏矩阵转置算法思想稀疏矩阵转置算法思想n设矩阵列数为设矩阵列数为 Cols,对矩阵三元组表扫描,对矩阵三元组表扫描Cols 次。第次。第 k 次检测列号为次检测列号为 k 的项。的项。n第第 k 次扫描找寻所有列号为次扫描找寻所有列号为 k 的项,将其行的项,将其行号变列号、列号变行号,顺次存于转置矩阵号变列号、列号变行号,顺次存于转置矩阵三元组表。三元组表。3535稀疏矩阵的转置稀疏矩阵的转置template void SparseMatrix :Transpose (SparseMatrix& B) /转置this矩阵,转置结果由
20、B返回 B.Rows = Cols; B.Cols = Rows; B.Terms = Terms; /转置矩阵的列数,行数和非零元素个数 if (Terms 0) int CurrentB = 0; /转置三元组表存放指针 int i, k;3636 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= smAr
21、rayi.value; CurrentB+; ; 3737n设矩阵三元组表总共有设矩阵三元组表总共有 t 项,上述算法的时项,上述算法的时间代价为间代价为 O ( n* t )。当非零元素的个数当非零元素的个数 t 和和 m*n 同数量级时,算法同数量级时,算法transmatrix的时间复的时间复杂度为杂度为O(m*n2)。n若矩阵有若矩阵有 200 行,行,200 列,列,10,000 个非零元个非零元素,总共有素,总共有 2,000,000 次处理。次处理。n快速转置算法的思想为:对快速转置算法的思想为:对 原矩阵原矩阵A 扫描一扫描一遍,按遍,按 A 中每一元素的列号,立即确定在转中每
22、一元素的列号,立即确定在转置矩阵置矩阵 B 三元组表中的位置,并装入它。三元组表中的位置,并装入它。3838n为加速转置速度,建立辅助数组为加速转置速度,建立辅助数组 rowSize 和和 rowStart:urowSize记录矩阵转置前各列,即转置矩记录矩阵转置前各列,即转置矩阵各行非零元素个数;阵各行非零元素个数;urowStart记录各行非零元素在转置三元组记录各行非零元素在转置三元组表中开始存放位置。表中开始存放位置。n扫描矩阵三元组表,根据某项列号,确定扫描矩阵三元组表,根据某项列号,确定它转置后的行号它转置后的行号, 查查 rowStart 表表, 按查按查到到的位置直接将该项存入
23、转置三元组表中的位置直接将该项存入转置三元组表中3939A三元组三元组(0)(1)(2)(3)(4)(5)(6)(7)行行row00112345列列col36153502值值value22151117-63991284040稀疏矩阵的快速转置算法稀疏矩阵的快速转置算法template void SparseMatrix: FastTranspos (SparseMatrix& B) int *rowSize = new intCols; /列元素数数组 int *rowStart = new intCols; /转置位置数组 B.Rows = Cols; B.Cols = Rows; B.Te
24、rms = Terms; if (Terms 0) int i, j; for (i = 0; i Cols; i+) rowSizei = 0; 4141 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 =
25、 smArrayi.row; B.smArrayj.value = smArrayi.value; rowStart smArrayi.col+; 4242 delete rowSize; delete rowStart;带行指针数组的二元组表带行指针数组的二元组表n稀疏矩阵的三元组表可以用带行指针数组的稀疏矩阵的三元组表可以用带行指针数组的二元组表代替。二元组表代替。n在行指针数组中元素个数与矩阵行数相等。在行指针数组中元素个数与矩阵行数相等。第第 i 个元素的下标个元素的下标 i 代表矩阵的第代表矩阵的第 i 行,元素行,元素的内容即为稀疏矩阵第的内容即为稀疏矩阵第 i 行的第一个非零元行
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 最新北京师范大学数据结构教学资料 第4章数组、串与广义表PPT课件 最新 北京师范大学 数据结构 教学 资料 数组 广义 PPT 课件
限制150内