首页 严蔚敏数据结构视频配套讲义（数组）

严蔚敏数据结构视频配套讲义（数组）

严蔚敏数据结构视频配套讲义（数组）来自 www.freekaoyan.com 转载请注明严蔚敏数据结构教学笔记第 1 页第五章数组 5.1 数组的类型定义 ADT Array { 数据对象：D＝{aj ,j ,...,j ,...j | ji =0,...,bi -1, i=1,2,..,n, n(>0)称为数组的维数，bi 是数组第i维的长度，ji是数组元素的第i维下标，aj ,...,j ∈ElemSet } 数据关系：R＝{R1, R2, ..., Rn} ...

来自 www.freekaoyan.com 转载请注明严蔚敏数据结构教学笔记第 1 页第五章数组 5.1 数组的类型定义 ADT Array { 数据对象：D＝{aj ,j ,...,j ,...j | ji =0,...,bi -1, i=1,2,..,n, n(>0)称为数组的维数，bi 是数组第i维的长度，ji是数组元素的第i维下标，aj ,...,j ∈ElemSet } 数据关系：R＝{R1, R2, ..., Rn} Ri＝{ | 0 ? jk ? bk -1, 1 ? k ? n 且k ? i, 0 ? ji ? bi -2, aj ,...,j ,...,j , aj ,...j +1,...,j∈D, i=2,...,n } 基本操作： InitArray(&A, n, bound1, ..., boundn) 操作结果：若维数 n和各维长度合法，则构造相应的数组 A，并返回 OK。 DestroyArray(&A) 操作结果：销毁数组 A。 Value(A, &e, index1, ..., indexn) 初始条件：A是 n维数组，e为元素变量，随后是 n个下标值。来自 www.freekaoyan.com 转载请注明严蔚敏数据结构教学笔记第 2 页操作结果：若各下标不超界，则 e赋值为所指定的 A的元素值，并返回 OK。 Assign(&A, e, index1, ..., indexn) 初始条件：A是 n维数组，e为元素变量，随后是 n个下标值。操作结果：若下标不超界，则将 e的值赋给所指定的 A的元素，并返回 OK。 } ADT Array 数组是 (一组下标，值) 的集合。 5.2 数组的顺序表示和实现类型特点: 1) 只有引用型操作，没有加工型操作; 2) 数组是多维的结构，而存储空间是一个一维的结构。有两种顺序映象的方式: 1. 以行序为主序(低下标优先); A(0, 0, 0), A(0, 0, 1), A(0, 1, 0), A(0, 1, 1), A(1, 0, 0), A(1, 0, 1), ⋯, A(2, 1, 1) 2. 以列序为主序(高下标优先); A(0, 0, 0), A(1, 0, 0), A(2, 0, 0) A(0, 1, 0), A(1, 1, 0), A(2, 1, 0) A(0, 0, 1), ⋯, A(2, 1, 1) 来自 www.freekaoyan.com 转载请注明严蔚敏数据结构教学笔记下面以“行序为主序”为例进行讨论: 假设每个数据元素占L个存储单元，则二维数组A中任一元素ai,j 的存储位置可由下式确定 LOC[i,j] = LOC[0,0] + (b2×i＋j)L (5-1) 式中，LOC[i,j]是ai,j 的存储位置；LOC[0,0]是a0,0 的存储位置，即二维数组A 的起始存储位置，亦称为基地址或基址。将式(5－1)推广到一般情况，可得到 n维数组的数据元素存储位置的计算公式： LOC[j1 , j2 , ..., jn ] = LOC[0,0,...,0] + (b2×...×bn×j1 ＋b3×...×bn× j2＋...＋bn×jn-1 + jn )L= LOC[0,0,...,0] + (∑ji∏bk + jn )L 可缩写成 LOC[j1, j2, ..., jn ] = LOC[0,0,...,0] + ∑ ci ji (5-2) 其中 cn = L，ci-1 = bi ×ci , 1 < i ≤ n。式(5-2)称为n维数组的映象函数。容易看出，数组元素的存储位置是其下标的线性函数，一旦确定了数组的各维的长度，ci 就是常数。由于计算各个元素存储位置的时间相等，所以存取数组中任一元素的时间也相等。我们称具有这一特点的存储结构为随机存储结构。 5.3 稀疏矩阵的压缩存储假设 m行 n列的矩阵含 t个非零元素，则称为稀疏因子通常认为 δ ≤ 0.05 的矩阵为稀疏矩阵以常规方法，即以二维数组表示高阶的稀疏矩阵时产生的问题: 1) 零值元素占的空间很大; 2) 计算中进行了很多和零值的运算; 解决问题的原则: 1) 尽可能少存或不存零值元素; 第 3 页来自 www.freekaoyan.com 转载请注明严蔚敏数据结构教学笔记第 4 页 2) 尽可能减少没有实际意义的运算; 3) 运算方便; 即: 能尽可能快地找到与下标值(i,j)对应的非零值元; 能尽可能快地找到同一行或同一列的非零值元; 通常，以非零元素在矩阵中的分布情况，可将稀疏矩阵分为两类: 1) 特殊矩阵的压缩存储例如: 三角矩阵对角矩阵 2) 随机稀疏矩阵的压缩存储随机矩阵中的非零元分布不规则下面讨论(随机)稀疏矩阵的几种表示方法一、三元组顺序表 #define MAXSIZE 12500 // 假设非零元个数的最大值为 12500 typedef struct { int i, j; // 该非零元的行下标和列下标 ElemType e; } Triple; // 三元组类型 typedef union { Triple data[MAXSIZE + 1]; // 非零元三元组表，data[0]未用 int mu, nu, tu; // 矩阵的行数、列数和非零元个数 } TSMatrix; // 稀疏矩阵类型求转置矩阵的操作: 用常规的二维数组表示时的算法 for (col=1; col<=nu; ++col) 来自 www.freekaoyan.com 转载请注明严蔚敏数据结构教学笔记第 5 页 for (row=1; row<=mu; ++row) T[col][row] = M[row][col]; 其时间复杂度为: O(mu×nu) Status FastTransposeSMatrix(TSMatrix M, TSMatrix &T) { // 采用三元组顺序表存储表示，求稀疏矩阵 M的转置矩阵 T T.mu = M.nu; T.nu = M.mu; T.tu = M.tu; if (T.tu) { for (col=1; col<=M.nu; ++col) num[col] = 0; for (t=1; t<=M.tu; ++t) ++num[M.data[t].j]; // 求 M 中每一列所含非零元的个数 cpot[1] = 1; for (col=2; col<=M.nu; ++col) cpot[col] = cpot[col-1] + num[col-1]; // 求 M 中每一列的第一个非零元在 b.data 中的序号 for (p=1; p<=M.tu; ++p) { // 转置矩阵元素 col = M.data[p].j; q = cpot[col]; T.data[q].i =M.data[p].j; T.data[q].j =M.data[p].i; T.data[q].e =M.data[p].e; ++cpot[col]; } // for } // if return OK; } // FastTransposeSMatrix 其时间复杂度为: O(mu +nu) 来自 www.freekaoyan.com 转载请注明严蔚敏数据结构教学笔记三元组顺序表又称有序的双下标法，它的特点是，非零元在表中按行序有序存储，因此便于进行依行顺序处理的矩阵运算。然而，若需按行号存取某一行的非零元，则需从头开始进行查找。二、行逻辑联接的顺序表修改前述的稀疏矩阵的类定义，增加一个数据成员 rpos, 其值在稀疏矩阵的构造函数中确定。 #define MAXMN 500 // 假设矩阵行数和列数的最大值为 500 typedef struct { Triple data[MAXSIZE + 1]; // 非零元三元组表，data[0]未用 int rpos[MAXMN + 1]; // 指示各行第一个非零元的位置 int mu, nu, tu; // 矩阵的行数、列数和非零元个数 } RLSMatrix; // 行逻辑链接顺序表类型在下面讨论的两个稀疏矩阵相乘的例子中，容易看出这种表示方法的优越性。矩阵乘法的精典算法: for (i=1; i<=m1; ++i) for (j=1; j<=n2; ++j) { Q[i][j] = 0; for (k=1; k<=n1; ++k) Q[i][j] += M[i][k] * N[k][j]; } 其时间复杂度为：O(m1 n1 n2) 两个稀疏矩阵相乘（Q= M N）的过程可大致描述如下： Q初始化; if Q是非零矩阵 { // 逐行求积第 6 页来自 www.freekaoyan.com 转载请注明严蔚敏数据结构教学笔记第 7 页 for (arow=1; arow<=M.mu; ++arow) { // 处理 M的每一行 ctemp[] = 0; // 累加器清零计算 Q中第 arow行的积并存入 ctemp[] 中；将 ctemp[] 中非零元压缩存储到 Q.data； } // for arow } // if Status MultSMatrix(RLSMatrix M, RLSMatrix N, RLSMatrix &Q) { //求矩阵乘积 Q=M× N，采用行逻辑链接存储表示。 if (M.nu != N.mu) return ERROR; Q.mu = M.mu; Q.nu = N.nu; Q.tu = 0; // Q初始化 if (M.tu*N.tu != 0) { // Q是非零矩阵 for (arow=1; arow<=M.mu; ++arow) { // 处理 M的每一行 ctemp[] = 0; // 当前行各元素累加器清零 Q.rpos[arow] = Q.tu+1; for (p=M.rpos[arow]; p MAXSIZE) return ERROR; Q.data[Q.tu] = {arow, ccol, ctemp[ccol]}; } // if } // for arow } // if return OK; } // MultSMatrix 分析上述算法的时间复杂度有如下结果：累加器 ctemp初始化的时间复杂度为Ο (M.mu N.mu)，求 Q的所有非零元的时间复杂度为Ο (M.tu N.tu/N.mu)，进行压缩存储的时间复杂度为Ο (M.mu N.nu)，总的时间复杂度就是Ο (M.mu N.nu+M.tu N.tu/N.mu)。若 M是 m行 n列的稀疏矩阵，N是 n行 p列的稀疏矩阵，则M中非零元的个数 M.tu = δ M m n， N中非零元的个数 N.tu = δ N n p，相乘算法的时间复杂度就是 Ο (m p (1+nδ Mδ N)) ，当δ M<0.05 和δ N<0.05及 n <1000时，相乘算法的时间复杂度就相当于 Ο (m p)。显然，这是一个相当理想的结果。如果事先能估算出所求乘积矩阵 Q不再是稀疏矩阵，则以二维数组表示 Q，相乘的算法也就更简单了。三、十字链表第 8 页来自 www.freekaoyan.com 转载请注明严蔚敏数据结构教学笔记当矩阵的非零元个数和位置在操作过程中变化较大时，就不宜采用顺序存储结构来表示三元组的线性表。例如，在作“将矩阵 B加到矩阵 A上”的操作时，由于非零元的插入或删除将会引起 A.data中元素的移动。为此，对这种类型的矩阵，采用链式存储结构表示三元组的线性表更为恰当。在链表中，每个非零元可用一个含五个域的结点表示，其中 i, j 和 e 三个域分别表示该非零元所在的行、列和非零元的值，向右域 right 用以链接同一行中下一个非零元，向下域 down 用以链接同一列中下一个非零元。同一行的非零元通过 right 域链接成一个线性链表，同一列的非零元通过 down 域链接成一个线性链表，每个非零元既是某个行链表中的一个结点，又是某个列链表中的一个结点，整个矩阵构成了一个十字交叉的链表，故称这样的存储结构为十字链表，可用两个分别存储行链表的头指针和列链表的头指针的一维数组表示之。例如：矩阵 M的十字链表如下图所示。假设非空指针 pa和 pb分别指向矩阵 A和 B中行值相同的两个结点，pa == NULL 表明矩阵 A在该行中没有非零元，则上述四种情况的处理过程为： (1) 若pa==NULL或pa->j 〉pb->j，则需要在A矩阵的链表中插入一个值为bi,j的结点。此时，需改变同一行中前一结点的right域值，以及同一列中前一结点的 down域值。 (2) 若 pa->j〈 pb->j，则只要将 pa指针往右推进一步。 (3) 若pa->j == pb->j且pa->e＋pb->e !=0，则只要将ai,j＋bi,j 的值送到pa所指结点的e域即可，其它所有域的值都不变。第 9 页来自 www.freekaoyan.com 转载请注明严蔚敏数据结构教学笔记第 10 页 (4) 若 pa->j == pb->j且 pa->e＋pb->e == 0，则需要在 A矩阵的链表中删除 pa所指的结点。此时，需改变同一行中前一结点的 right域值，以及同一列中前一结点的 down域值。为了便于插入和删除结点，还需要设立一些辅助指针。其一是，在 A的行链表上设 pre指针，指示 pa所指结点的前驱结点；其二是，在 A的每一列的链表上设一个指针 hl[j]，它的初值和列链表的头指针相同，即 hl[j]＝chead[j]。算法: (1) 初始，令 pa和 pb分别指向 A和 B的第一行的第一个非零元素的结点，即 pa＝A.rhead[1]; pb＝B.rhead[1]; pre = NULL; 且令 hl初始化 for (j=1; j<=A.nu; ++j) hl[j]＝A.chead[j]; (2) 重复本步骤，依次处理本行结点，直到 B的本行中无非零元素的结点，即 pb==NULL为止： ① 若 pa==NULL或 pa->j〉pb->j（即 A的这一行中非零元素已处理完），则需在 A中插入一个 pb所指结点的复制结点。假设新结点的地址为 p，则 A的行表中的指针作如下变化： if pre == NULL rhead[p->i]=p; else { pre->right＝p; } p->right＝pa; pre = p; A的列链表中的指针也要作相应的改变。首先需从 hl[p->j]开始找到新结点在同一列中的前驱结点，并让 hl[p->j]指向它，然后在列链表中插入新结点： if chead[p->j] == NULL { chead[p->j] = p; p->down = NULL; } else { p->down＝hl[p->j]->down; hl[p->j]->down＝p; } hl[p->j] = p; ② 若 pa->j〈pb->j且 pa->j!=0，则令 pa指向本行下一个非零元结点，即 pre ＝pa; pa＝pa->right; 来自 www.freekaoyan.com 转载请注明严蔚敏数据结构教学笔记第 11 页 ③ 若 pa->j == pb->j，则将 B中当前结点的值加到 A中当前结点上，即 pa->e＋＝pb->e; 此时若 pa->e!=0，则指针不变，否则删除 A中该结点，即行表中指针变为 if pre == NULL rhead[pa->i] = pa->right; else { pre->right＝pa->right; } p=pa; pa=pa->right; 同时，为了改变列表中的指针，需要先找到同一列中的前驱结点，且让 hl[pa->j] 指向该结点，然后如下修改相应指针： if chead[p->j] == p chead[p->j] = hl[p->j] = p->down; else { hl[p->j]->down＝p->down; } free (p); (3) 若本行不是最后一行，则令pa和pb指向下一行的第一个非零元结点，转(2)；否则结束。 5.4 广义表的类型定义 ADT Glist { 数据对象：D＝{ei | i=1,2,..,n; n≥0; ei∈AtomSet 或 ei∈GList,AtomSet为某个数据对象 } 数据关系：LR＝{| ei-1 ,ei ∈D, 2≤i≤n } 广义表是递归定义的线性结构，来自 www.freekaoyan.com 转载请注明严蔚敏数据结构教学笔记第 12 页一般情况下，广义表写成LS = ( α 1,α 2, ... , α n )其中：α i 或为原子或为广义表广义表是一个多层次的线性结构。例如： D = (E, F) E = (a, (b, c)) F = (d, (e)) 其它如： A = ( ) B = (a, B) = (a, (a, (a, ... , ) ) ) C = (A, D, F) 广义表LS = (a1,a 2, ⋯,an )的结构特点: 1) 广义表中的数据元素有相对次序; 2) 广义表的长度定义为最外层包含的元素个数; 3) 广义表的深度定义为所含括弧的重数; 注意: “原子”的深度为“0”;“空表”的深度为 1 4) 广义表可以共享; 来自 www.freekaoyan.com 转载请注明严蔚敏数据结构教学笔记第 13 页 5) 广义表可以是一个递归的表; 递归表的深度是无穷值，长度是有限值。 6) 任何一个非空广义表 LS = ( α 1, α 2, ⋯, α n)均可分解为表头 Head(LS) = α 1 和表尾 Tail(LS) = ( α 2, ⋯, α n)两部分例如：LS = ( A, D ) = (( ), ( E, F )) = (( ), ((a, (b, c)，F ) Head(LS) = A Tail(LS) = ( D ) Head( D ) = E Tail( D ) = ( F ) Head( E ) = a Tail( E ) = ( ( b, c) ) Head( (( b, c)) ) = ( b, c) Tail( (( b, c)) ) = ( ) Head( ( b, c) ) = b Tail( ( b, c) ) = ( c ) Head( ( c ) ) = c Tail( ( c ) ) = ( ) 基本操作：结构的创建和销毁 InitGList(&L); DestroyGList(&L); CreateGList(&L, S); CopyGList(&T, L); 来自 www.freekaoyan.com 转载请注明严蔚敏数据结构教学笔记状态函数 GListLength(L); GListDepth(L); GListEmpty(L); GetHead(L); GetTail(L); 插入和删除操作 InsertFirst_GL(&L, e); DeleteFirst_GL(&L, &e); 遍历 Traverse_GL(L, Visit()); } ADT GList 5.5 广义表的表示方法头、尾指针的链表结构构造存储结构的两种分析方法: 第 14 页来自 www.freekaoyan.com 转载请注明严蔚敏数据结构教学笔记 5.6 广义表操作的递归函数递归函数一个含直接或间接调用本函数语句的函数被称之为递归函数，它必须满足以下两个条件: 1) 在每一次调用自己时，必须是(在某种意义上)更接近于解; 2) 必须有一个终止处理或计算的准则。例如: 梵塔的递归函数 void hanoi (int n, char x, char y, char z) { if (n==1) move(x, 1, z); else { hanoi(n-1, x, z, y); move(x, n, z); hanoi(n-1, y, x, z); } 第 15 页来自 www.freekaoyan.com 转载请注明严蔚敏数据结构教学笔记第 16 页 } 二叉树的遍历 void PreOrderTraverse( BiTree T, void (Visit)(BiTree P) ) { if (T) { Visit(T->data); (PreOrderTraverse(T->lchild, Visit); (PreOrderTraverse(T->rchild, Visit); } } // PreOrderTraverse 这一类问题可以借助算法设计的一种方法¾ 分治法(分割求解) (Divide and Conquer)来求解分治法的设计思想为: 对于一个输入规模为 n的函数或问题，用某种方法把输入分割成 k(1

                    本文档为【严蔚敏数据结构视频配套讲义（数组）】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
                    图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。 
 该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。

                    [版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。

                    本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。

                    网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
                

下载需要：免费已有0 人下载

立即下载

严蔚敏数据结构视频配套讲义（数组）

你可能还喜欢