数据结构第五章数组和广义表.ppt

第五章数组和广义表 n教学目的 n通过本章的学习，要求学生了解数组及广义 表的定义，掌握数组的存储结构 n5.1 数组的定义 n5.2 数组的顺序表示和实现 n5.3 矩阵的压缩存储 5.3.1 特殊矩阵 5.3.2 稀疏矩阵 n重点：数组的两种存储表示方式及元素存储 地址的计算公式；特殊矩阵和稀疏矩阵的压 缩存储方法； n难点：特殊矩阵和稀疏矩阵的压缩存储方法 及运算的实现。 n数组可看成是一种特殊的线性表，其特殊在于，表中的 数据元素本身也是一种线性表。 5.1 数组的定义 数组是我们最熟悉的数据类型，在早期的高级语言 中，数组是唯一可供使用的数据类型。由于数组中各元 素具有统一的类型，并且数组元素的下标一般具有固定 的上界和下界，因此，数组的处理比其它复杂的结构更 为简单。多维数组是向量的推广。 例如，二维数组： a00 a01 a0,n-1 a10 a11 a1,n-1 am-1,1 am-1,2 am-1,n-1 在C语言中，一个二维数组类型可以定义 为其分量类型为一维数组类型的一维数组类 型. 也就是说， typedef elemtype array2mn; 等价于： typedef elemtype array1n; typedef array1 array2m; 数组一旦被定义，它的维数和维界就不再改变。 因此，除了结构的初始化和销毁之外，数组只有 存取元素和修改元素值的操作。 同理，三维数组类型可以定义为其数据元素为二 维数组类型的一维数组类型。 数组的抽象数据类型定义 ADT Array 数据对象： ji=0,bi-1 i=1,2,n D=aj1j2jn|n称为数组的维数, bi称为第i维的长度 数据关系： R=R1,R2,Rn Ri=| 0 jkbk-1, 1 k n,且ki, 0 jibi-2, i=2,n 基本操作： 二维数组的抽象数据类型定义 ADT TArray D=ai,j|ai,jElemType， R=R1,R2 R1=Row= R2=Col= 0ib1-1 0jb2-1 0ib1-1 0 jb2-1 0 ib1-1 0jb2-1 a00, ,a0,b2-1 . . . . ab1-1,0,ab1-1,b2-1 （下标 ， 元素） （i ， ai ） （(i,j) , ai,j ） （(j1jn)， aj1jn ） 基本操作 nInitArray( for(int j = 0;jscore.GetLength(1);j+) /score.GetLength(1)方法可以获得第二维的长度 sum = sum + scorei,j; return sum; static void Main() int, score = new int10,3; for (int i = 0; i 10; i+) for (int j = 0; j 3; j+) scorei,j = (i + 1) * (j + 1);/为第i个学生的第j门课赋 值 Console.Write(scorei,j.ToString()+“ “); Console.WriteLine(); for (int i = 0; i 10; i+) int sum = Student_Sum(score, i); Console.WriteLine(“第0位同学的总分是 1“,i+1,sum); Console.ReadLine(); 求第j门课程总分数的算法为： static public int Course_Sum(int, score, int j) int sum = 0; for (int i = 0; i score.GetLength(0); i+) sum += scorei, j; return sum; 5.3 矩阵的压缩存储 n矩阵是数值计算程序设计中经常用到的数学模型， 它是由 m 行和 n 列的数值构成（当m=n 时称为方 阵）。 n在高级程序设计语言中，通常用二维数组表示矩阵 。 n然而在数值分析过程中经常遇到一些比较特殊的矩 阵，它们的阶数很高，矩阵中元素数量很大，而且 有很多元素的值相同或零值元素，如对称矩阵、三 角矩阵、带状矩阵和稀疏矩阵等。 n为了节省存储空间并且加快处理速度，需要对这类 矩阵进行压缩存储，压缩存储的原则是：不重复存不重复存 储相同元素；不存储零值元素储相同元素；不存储零值元素。 特殊矩阵的压缩存储方法 n n 特殊矩阵是指非零元素或零元素的分布有一特殊矩阵是指非零元素或零元素的分布有一 定规律的矩阵。主要形式有对称矩阵、三角定规律的矩阵。主要形式有对称矩阵、三角 矩阵、对角矩阵等矩阵、对角矩阵等。 1 1、对称矩阵的压缩存储、对称矩阵的压缩存储 对称矩阵是一个n阶方阵。若一个n阶矩阵A中的元素满足 : ai,j=aj,i (0i，jn-1)，则称A为n阶对称矩阵。 1 5 1 3 7 a00 5 0 8 0 0 a10 a 11 1 8 9 2 6 a20 a21 a23 3 0 2 5 1 7 0 6 1 3 an-1 0 a n-1 1 a n-1 2 a n-1 n-1 1 5 1 3 7 a00 5 0 8 0 0 a10 a 11 1 8 9 2 6 a20 a21 a23 3 0 2 5 1 7 0 6 1 3 an-1 0 a n-1 1 a n-1 2 a n-1 n-1 a00a10a11a20a21a23 an-1n-1 an-1n-3an-1n-2Sa数组 只需存储 n(n+1)/2 个元素 共n(n+1)/2个元素 012345n(n+1)/2-1 由于对称矩阵中的元素关于主对角线对称，因此可以为 每一对对称的矩阵元素分配 1 个存储空间，n阶矩阵中 的nn个元素就可以被压缩到 n(n+1)/2 个元素的存储空 间中去。 称一维数组San(n+1)/2 为n 阶对称矩阵A的压缩存储 矩阵中的元素Aij和Sak的关系？ k i(i+1)/2+j 当ij j(j+1)/2+i 当ij 当Aij为下三角中的元素时（即ij ）： 此元素前共有i行按照下三角存储的元素， Aij所处列之 前共有j个元素 当Aij为上三角中的与元素时（即ij ）： 和此元素对应相等的元素为Aji，此时Aji为下三角元素 稀疏矩阵的压缩存储 n如果一个矩阵中有很多元素的值为零，即零元素的 个数远远大于非零元素的个数时，称该矩阵为稀疏 矩阵 稀疏因子 若m行n列的矩阵中含有t个非零元素 则称： 为稀疏因子 问题？ 通常认为稀疏因子0.05的矩阵为稀疏矩阵 零值元素占用空间很大 计算中进行了很多零值运算 t mn 解决问题的原则 n尽可能少存或者不存零值元素 n尽可能减少没有实际意义的运算 n运算方便，即： n能尽可能快的找到与下标值(i,j)对应的元素 n能尽可能快地找到同一行或同一列的非零值元 使用A67的数组存储？ 行列值 (0,2,1) (1,1,2) (2,0,3) (3,3,5) (4,4,6) (5,5,7) (5,6,4) 三元组表示法 n三元组表示法就是在存储非零元的同时，存储该元 素所对应的行下标和列下标。稀疏矩阵中的每一个 非零元素由一个三元组(i，j，aij)唯一确定。矩阵中 所有非零元素存放在由三元组组成的数组中。 三元组表中的第一行分别表示稀疏矩 阵A的行数、列数和非零元的个数。 显然，非零元素的三元组是按行号递 增的顺序、相同行号的三元组按列号 递增的顺序排列的。 n三元组顺序表 假设以行序为主序，且以一维数组作为三元组表 的存储结构，可以得到稀疏矩阵的一种压缩存储 方法，称为三元组顺序表。三元组顺序表的数据 结构定义如下： public class MatrixNode /三元组结点类 private int row; /行号 private int col; /列号 private int item; /元素值 public class TsMatrix /三元组类 public int Rows; /矩阵总行数 public int Cols; /矩阵总列数 private int nums; /三元组个数 public MatrixNode Data; /三元组表 1稀疏矩阵的转置运算 n转置是矩阵中最简单的一种运算。 0 1 0 0 4 0 2 0 0 0 0 0 0 0 0 5 0 2 0 0 0 0 6 1 A46= 0 2 0 0 1 0 0 0 0 0 0 0 0 0 5 0 4 0 0 6 0 0 2 1 B64= 转置后 对于一个mn的矩阵其转置矩阵是一个nm的矩 阵，设为Bnm 且满足aij=bji 即：aij=bji，其中：0im-1，0jn-1 即A的行是B的列，A的列是B的行。 0 1 0 0 4 0 2 0 0 0 0 0 0 0 0 5 0 2 0 0 0 0 6 1 A46= 0 2 0 0 1 0 0 0 0 0 0 0 0 0 5 0 4 0 0 6 0 0 2 1 B64= 行列值 (0,1,1) (0,4,4) (1,0,2) (2,3,5) (2,5,2) (3,4,6) (3,5,1) (1,0,1) (4,0,4) (0,1,2) (3,2,5) (5,2,2) (4,3,6) (5,3,1) 行下标列下标互换 (0,1,2) (1,0,1) (3,2,5) (4,0,4) (4,3,6) (5,2,2) (5,3,1) 以行下标为主序 n矩阵A是按行序为主序存储的，若按列序为主序进 行转置就可以得到A阵的转置矩阵B。 n算法思想1：在存储三元组的数组Ma中按三元组的 列域cols的值开始扫描每一个三元组，从第0列至第 n-1列，依序将三元组列域与行域之值对换，并顺次 存人数组Mb中。 public void TransPose(TsMatrix mb) /初始化转置三元组，使得长度相等，行数变为列数，列数变为行数 mb.nums = this.nums; mb.Cols = this.Rows; mb.Rows = this.Cols; int index = 0;/三元组下标 if (mb.nums != 0) /若mb.nums为没有转置的必要 for (int i = 0; i this.Cols; i+) /从矩阵A的列值开始 for (int j = 0; j this.nums; j+) /比较每一个三元组，看是否是第i列的(即矩阵B的第i行) if (this.Dataj.Col = i) /如果此三元组属于第i列，开始置换 mb.Dataindex.Row = this.Dataj.Col; mb.Dataindex.Col = this.Dataj.Row; mb.Dataindex.Item = this.Dataj.Item; index+; n此算法的时间复杂度为O(cols*nums) n三元组顺序表虽然节省了存储空间，但时间 复杂度比一般矩阵转置的算法还要复杂，同 时还有可能增加算法的难度。因此，此算法 仅适用于t m*n的情况。 n算法思想2：对A扫描一次，按A提供的列号 一次确定位置装入B的一个三元组。具体实 施如下：一遍扫描先确定三元组的位置关系 ，二次扫描由位置关系装入三元组。可见， 位置关系是此种算法的关键 行列值 (0,1,1) (0,4,4) (1,0,2) (2,3,5) (2,5,2) (3,4,6) (3,5,1) 列 个数 0列 1 1列 1 2列 0 3列 1 4列 2 5列 2 (1,0,1) (4,0,4) (0,1,2) (3,2,5) (5,2,2) (4,3,6) (5,3,1) 列 起始位 0列 0 1列 1 2列 2 3列 2 4列 3 5列 5 n为此，需要设置两个一维数组num0n和rpos0n： nnum0n：统计M中每列非零元素的个数。 nrpos0n：M中的每列第一个非零元素在T中的位置。 n算法通过rpos数组建立位置对应关系： rpos0=0 ； rposcol=rposcol-1+numcol-1 0colM.rows； 列 个数 0列 1 1列 1 2列 0 3列 1 4列 2 5列 2 列 起始位 0列 0 1列 1 2列 2 3列 2 4列 3 5列 5 列 num rpos 110 10 2 2 12 345 1 012235 public void ExTransPose(TsMatrix mb) /初始化转置三元组，使得长度相等，行数变为列数，列数变为行数 mb.nums = this.nums; mb.Cols = this.Rows; mb.Rows = this.Cols; int num = new intthis.nums;/列个数数组 int rpos = new intthis.nums;/各列位置数组 if (mb.nums != 0) /将num数组先赋为0，然后计算三元组中各列的个数，存入num数组 中 for (int i = 0; i this.nums; i+) numi = 0; for(int i =0;ithis.nums;i+) numthis.Datai.Col+; /第0列的起始位置为0；其余列等于前一列的起始位置+前一列总个数 rpos0 = 0; for (int i = 1; i this.Cols; i+) rposi = rposi - 1 + numi - 1; for (int i = 0; i this.nums; i+) int pos = rposthis.Datai.Col; mb.Datapos.Col = this.Datai.Row; mb.Datapos.Row = this.Datai.Col; mb.Datapos.Item = this.Datai.Item; rposthis.Datai.Col+; 2、矩阵相乘 0 1 2 1 1 0 0 1 2 0 1 0 = a00*b00+a01*b10+a02*b20 a00*b01+a01*b11+a02*b21 a10*b00+a11*b10+a12*b20 a10*b01+a11*b11+a12*b21 矩阵A 矩阵B = 4 0 2 1 = C00 C01 C10 C11 总结： 1、矩阵A的行号和矩阵B的列号决定矩阵C的行列号 2、矩阵A的列号和矩阵B的行号相同者进行乘法操作 0 1 2 1 1 0 0 1 2 0 1 0 (0,2,2) (1,1,1) (0,1,1) (1,0,1) (2,0,1) (0,1,1) 0 0 0+2 (1,0,2) +2 0 1 0 1 1+1 0 1 0 0 +2 (1,1,1) (0,0,4) (1,0,2) = 4 0 2 1 0 2 0 0 3 0 -1 5 0 0 4 0 0 7 6 0 0 -3 0 0 0 3 2 4 1 0 0 0 0 -2 行逻辑链接的顺序表行逻辑链接的顺序表 n有时为了方便某些矩阵运算，在按行优先存 储的三元组中，加入一个行表来记录稀疏矩 阵中每行的非零元素在三元组表中的起始位 置。当将行表作为三元组表的一个新增属性 加以描述时，就得到了稀疏矩阵的另一种顺 序存储结构：带行表的三元组表。 n称这种“带行链接信息”的三元组表为行逻辑 链接的顺序表。 n矩阵的非零元个数和位置在操作过程中变化较大 n再使用三元组表示法不合适了，此时，采用链表 作为存储结构更为恰当 + 0 1 0 0 4 0 2 0 0 0 0 0 0 0 0 5 0 2 0 0 0 0 6 1 1 -1 0 2 0 0 0 3 0 0 0 0 0 1 0 1 0 0 0 0 4 0 0 0 = 1 0 0 2 4 0 2 3 0 0 0 0 0 1 0 6 0 2 0 0 4 0 6 1 3、矩阵相加 十字链表 n在该方法中，每一个非零元用一个结点表示 ，结点中除了表示非零元所在的行、列和值 的三元组（i,j,v）外，还需增加两个链域： n行指针域（rptr），用来指向本行中下一个 非零元素； n列指针域（cptr），用来指向本列中下一个 非零元素。 n稀疏矩阵中同一行的非零元通过向右的rptr 指针链接成一个带表头结点的循环链表。 n同一列的非零元也通过cptr指针链接成一个 带表头结点的循环链表。 结点 jivalue rightdown 0 1 0 1 2 0 011 112 10