数组和广义表-副本.ppt

数据结构 Data Structures 长江大学计算机科学学院 第五章 数组和广义表 F本章内容 5.1 数组的定义 5.2 数组的顺序表示 5.3 矩阵的压缩存储 5.3.1 特殊矩阵 5.3.2 稀疏矩阵 5.4 广义表的定义 5.5 广义表的存储结构 数据结构 Data Structures 长江大学计算机科学学院 5.1数组的定义 v数组是我们很熟悉的一种数据结构，它可以看 作线性表的推广。数组作为一种数据结构其特 点是结构中的元素本身可以是具有某种结构的 数据，但属于同一数据类型，比如：一维数组 可以看作一个线性表，二维数组可以看作“数 据元素是一维数组”的一维数组，三维数组可 以看作“数据元素是二维数组”的一维数组， 依此类推。 v由于数组中各元素具有统一的类型，并且数组 元素的下标一般具有固定的上界和下界，因此 ，数组的处理比其它复杂的结构更为简单。多 维数组是一维数组的推广。 2 数据结构 Data Structures 长江大学计算机科学学院 v例如，二维数组A： 5.1数组的定义(续) Amn= a11 a12 a1n a21 a22 a2n am1 am2 amn v二维数组A可以看成是由m个行向量组成的向量 ，也可以看成是n个列向量组成的向量。 v数组一旦被定义，它的维数和维界就不再改变 。因此，除了结构的初始化和销毁之外，数组 只有存取元素和修改元素值的操作。 3 数据结构 Data Structures 长江大学计算机科学学院 v由于计算机的内存结构是一维的，因此用一维 内存来表示多维数组，就必须按某种次序将数 组元素排成一列序列，然后将这个线性序列存 放在存储器中。 v数组一旦建立，结构中的元素个数和元素间的 关系就不再发生变化。因此，一般采用顺序存 储的方法来表示数组。 5.2 数组的顺序表示 4 数据结构 Data Structures 长江大学计算机科学学院 v行优先顺序或以行为主序存储方式：将数组元素 按行排列，第i+1个行向量紧接在第i个行向量后 面。以二维数组为例，按行优先顺序存储的线性 序列为： a11,a12,a1n,a21,a22,a2n,am1,am2,amn v在PASCAL、C等语言中，数组就是按行优先顺序存 储的。 5.2 数组的顺序表示(续) Amn= a11 a12 a1n a21 a22 a2n am1 am2 amn vLOC(aij)=LOC(a11)+(i-1)*n+j-1*d 5 数据结构 Data Structures 长江大学计算机科学学院 v列优先顺序或以列为主序存储方式：将数组元素按 列向量排列，第j+1个列向量紧接在第j个列向量之 后，A的m*n个元素按列优先顺序存储的线性序列为 ： a11,a21,am1,a12,a22,am2,an1,an2,anm v在FORTRAN语言中，数组按列优先顺序存储。 5.2 数组的顺序表示(续) Amn= a11 a12 a1n a21 a22 a2n am1 am2 amn vLOC(aij)=LOC(a11)+(j-1)*m+i-1*d 6 数据结构 Data Structures 长江大学计算机科学学院 v行优先顺序先排最右的下标，从右到左 ，最后排最左下标。 v列优先顺序先排最左下标，从右向左， 最后排最右下标。 v例如：三维数组Am*n*p 5.2 数组的顺序表示(续) 7 数据结构 Data Structures 长江大学计算机科学学院 v只要知道开始结点的存放地址（即基地址）、维 数和每维的上、下界，以及每个数组元素所占用 的单元数，就可以将数组元素的存放地址表示为 其下标的线性函数。因此，数组中的任一元素可 以在相同的时间内存取，即顺序存储的数组是一 个随机存取结构。 数组存储的特点 8 数据结构 Data Structures 长江大学计算机科学学院 v压缩存储：为多个值相同的非零元素只分配 一个存储空间；对零元素不分配空间。 5.3 矩阵的压缩存储 9 数据结构 Data Structures 长江大学计算机科学学院 v特殊矩阵：非零元素按照一定的规律分布。 5.3.1特殊矩阵的压缩存储 a1,1 a1,2 a1,n a2,1 a2,2 a2,n ai,j an,1 an,2 an,n aij=aji 1 2 3 4 2 1 3 4 3 3 1 4 4 4 4 1 对称矩阵 v常见的特殊矩阵有对称矩阵、三角矩阵、对 角矩阵等。 对称矩阵：元素的值按照主对角线对称 10 数据结构 Data Structures 长江大学计算机科学学院 5.3.1(续)对称矩阵的压缩存储 对称矩阵 1 2 3 4 2 1 3 4 3 3 1 4 4 4 4 1 1 2 3 4 2 1 3 4 3 3 1 4 4 4 4 1 1213314441数组B 12345678910下标k v例如：一个4*4的对称矩阵。 11 数据结构 Data Structures 长江大学计算机科学学院 5.3.1(续)对称矩阵的压缩存储 对称矩阵 数组Bai,jan,na1,1a2,1a2,2a3,1 1234km下标 a1,1 a1,2 a1,n a2,1 a2,2 a2,n ai,j an,1 an,2 an,n a1,1 a2,1 a2,2 ai,j an,1 an,2 an,n k = ? m = ? v推广至一般情况，n*n的对称矩阵 12 数据结构 Data Structures 长江大学计算机科学学院 5.3.1(续)三角矩阵的压缩存储 1 0 0 0 2 1 0 0 3 3 1 0 4 4 4 1 1 2 3 4 0 1 3 4 0 0 1 4 0 0 0 1 (a) 下三角矩阵(a) 上三角矩阵 v三角矩阵：上(下)三角矩阵是指矩阵的下（上） 三角（不包括对角线）中的元素均为常数或零的n 阶矩阵，即非零元素的分布在矩阵中呈现为三角 形。 v例如：一个4*4的三角矩阵。 13 数据结构 Data Structures 长江大学计算机科学学院 5.3.1(续)三角矩阵的压缩存储 1 8 8 8 2 1 8 8 3 3 1 8 4 4 4 1 1 2 3 4 9 1 3 4 9 9 1 4 9 9 9 1 (c) 下三角矩阵(d) 上三角矩阵 v例如：一个4*4的三角矩阵。 14 数据结构 Data Structures 长江大学计算机科学学院 5.3.1(续)三角矩阵的压缩存储 a0,0 a0,1 a0,2 a0,n-2 a0, n-1 a1,1 a1,2 a1,n-2 a1, n-1 ai,i ai,j ai, n-1 an-1, n-1 0 a0,0 a0,1 a0,2 a0,3 ai,j an-1, n-1 b1 b2 b3 b4 bk bm k = ? m = ? v推广至一般情况，n*n的三角矩阵以行为主 序压缩存储 15 数据结构 Data Structures 长江大学计算机科学学院 5.3.1(续)三角矩阵的压缩存储 a0,0 a0,1 a0,2 a0,n-2 a0, n-1 a1,1 a1,2 a1,n-2 a1, n-1 ai,i ai,j ai, n-1 an-1, n-1 0 a0,0 a0,1 a1,1 a0,2 ai,j an-1, n-1 b1 b2 b3 b4 bk bm k = ? m = ? a1,2b5 a2,2b6 v推广至一般情况，n*n的三角矩阵以列为主 序压缩存储 16 数据结构 Data Structures 长江大学计算机科学学院 5.3.1(续)三对角矩阵的压缩存储 a0,0 a0,1 a1,0 a1,1 a1,2 a2,1 a2,2 a2,3 . ai,j . an-2,n-3 an-2,n-2 an-2,n-1 an-1,n-2 an-1, n-1 a0,0a0,1a1,0ai,j数组B 12k k+1m下标0 k = ? m = ? v对角矩阵是指所有的非零元素都集中在以主 对角线为中心的带状区域中。 17 数据结构 Data Structures 长江大学计算机科学学院 v上述各种特殊矩阵，其非零元素的分布都是 有规律的，因此总能找到一种方法将它们压 缩存储到一维数组中，并且一般都能找到矩 阵中的元素与该一维数组元素的对应关系， 通过这个关系，仍能对矩阵的元素进行随机 存取。 5.3.1(续)特殊矩阵的压缩存储 Example 18 数据结构 Data Structures 长江大学计算机科学学院 v什么是稀疏矩阵？简单说，设矩阵A中有s个 非零元素，若s远远小于矩阵元素的总数（ 即smn），则称A为稀疏矩阵。 v设在矩阵A中，有s个非零元素。令 e=s/(m*n)，称e为矩阵的稀疏因子。通常认 为e0.05时称之为稀疏矩阵。 5.3.2稀疏矩阵 19 数据结构 Data Structures 长江大学计算机科学学院 5.3.2稀疏矩阵的压缩存储 v在存储稀疏矩阵时，由于非零元素的分布一般 是没有规律的，因此在存储非零元素的同时，还 必须同时记下它所在的行和列的位置（i,j)。反 之，一个三元组(i,j,aij)惟一确定了矩阵A的一 个非零元。因此，稀疏矩阵可由表示非零元的三 元组及其行列数唯一确定。 20 数据结构 Data Structures 长江大学计算机科学学院 ( (1,2,12), (1,3,9), (3,1,-3), (3,6,14), (4,3,24), (5,2,18), (6,1,15), (6,4,-7) ) 5.3.2稀疏矩阵的压缩存储 M= 0 12 9 0 0 0 0 0 0 0 0 0 0 0 -3 0 0 0 0 14 0 0 0 24 0 0 0 0 0 18 0 0 0 0 0 15 0 0 7 0 0 0 v例如，一个6*7的稀疏矩阵 v稀疏矩阵中的非零元素 21 数据结构 Data Structures 长江大学计算机科学学院 假设以顺序存储结构来表示三元组表，则可得到 稀疏矩阵的一种压缩存储方法三元组顺序表 。 #define maxsize 10000 typedef int datatype; typedef struct int i,j; datatype v; triple; /* 三元组*/ 5.3.2(续)稀疏矩阵的压缩存储 22 数据结构 Data Structures 长江大学计算机科学学院 typedef struct triple datamaxsize; int m,n,t; tripletable; 5.3.2(续)三元组顺序表 M= 0 12 9 0 0 0 0 0 0 0 0 0 0 0 -3 0 0 0 0 14 0 0 0 24 0 0 0 0 0 18 0 0 0 0 0 15 0 0 7 0 0 0 i j v 1 2 12 1 3 9 3 1 -3 3 6 14 4 3 24 5 2 18 6 1 15 6 4 -7 1 2 3 4 5 6 7 8 23 转置 MT= 0 0 -3 0 0 15 12 0 0 0 18 0 9 0 0 24 0 0 0 0 0 0 0 -7 0 0 0 0 0 0 0 0 14 0 0 0 0 0 0 0 0 0 M= 0 12 9 0 0 0 0 0 0 0 0 0 0 0 -3 0 0 0 0 14 0 0 0 24 0 0 0 0 0 18 0 0 0 0 0 15 0 0 7 0 0 0 24 数据结构 Data Structures 长江大学计算机科学学院 5.3.2(续)三元组顺序表上的转置 i j v 1 2 12 1 3 9 3 1 -3 3 6 14 4 3 24 5 2 18 6 1 15 6 4 -7 1 2 3 4 5 6 7 0 转 置 i j v 2 1 12 3 1 9 1 3 -3 6 3 14 3 4 24 2 5 18 1 6 15 4 6 -7 1 2 3 4 5 6 7 0 排 序 i j v 1 3 -3 1 6 15 2 1 12 2 5 18 3 1 9 3 4 24 4 6 -7 6 3 14 1 2 3 4 5 6 7 0 25 数据结构 Data Structures 长江大学计算机科学学院 typedef struct triple datamaxsize; int m,n,t; tripletable; Void transmatrix(tripletable A, tripletable AT.n=A.m; AT.t=A.t; if (AT.t=0) return; for(p=0;pA.t;+p) AT.datap.i = AT.datap.j; AT.datap.j = AT.datap.i; AT.datap.v = AT.datap.v; /按照AT.datap.i进行非递减排序 5.3.2(续)三元组顺序表 26 数据结构 Data Structures 长江大学计算机科学学院 5.3.2(续)三元组顺序表上的转置(二 ) 转置 i j v 1 2 12 1 3 9 3 1 -3 3 6 14 4 3 24 5 2 18 6 1 15 6 4 -7 1 2 3 4 5 6 7 0 i j v 1 3 -3 1 6 15 2 1 12 2 5 18 3 1 9 3 4 24 4 6 -7 6 3 14 1 2 3 4 5 6 7 0 27 数据结构 Data Structures 长江大学计算机科学学院 v设置向量num,numcol表示矩阵A中第col 列中非零元的个数。(A的列数：A.n) 5.3.2(续)三元组顺序表上的转置(二) for(col=1;col=A.n;+col) numcol = 0; for(p=1;p=A.t;+p) /计算A中每列非零元的个数 numA.datap.j+; 列号 28 数据结构 Data Structures 长江大学计算机科学学院 v设置向量cpot,cpotcol指示A中第col列 的第一个非零元在转置矩阵AT.data中的恰 当位置。 5.3.2(续)三元组顺序表上的转置(二) cpot1=1 cpotcol=cpotcol-1+numcol-1 2colA.n cpot1=1; for(col = 2; col=A.n; +col) cpotcol=cpotcol-1+numcol-1; 29 数据结构 Data Structures 长江大学计算机科学学院 5.3.2(续)三元组顺序表上的转置(二) cpot 1357889 1 2 3 4 5 6 7 num 2221010 M= 0 12 9 0 0 0 0 0 0 0 0 0 0 0 -3 0 0 0 0 14 0 0 0 24 0 0 0 0 0 18 0 0 0 0 0 15 0 0 7 0 0 0 30 数据结构 Data Structures 长江大学计算机科学学院 转置 i j v 1 2 12 1 3 9 3 1 -3 3 6 14 4 3 24 5 2 18 6 1 15 6 4 -7 2 3 4 5 6 7 8 1 i j v 2 3 4 5 6 7 8 1 cpot 1357889 1 2 3 4 5 6 7 2 1 12 三元组顺序表上的转置(二续) 31 数据结构 Data Structures 长江大学计算机科学学院 转置 i j v 1 2 12 1 3 9 3 1 -3 3 6 14 4 3 24 5 2 18 6 1 15 6 4 -7 2 3 4 5 6 7 8 1 i j v 2 3 4 5 6 7 8 1 cpot 1457889 1 2 3 4 5 6 7 2 1 12 三元组顺序表上的转置(二续) 32 数据结构 Data Structures 长江大学计算机科学学院 转置 i j v 1 2 12 1 3 9 3 1 -3 3 6 14 4 3 24 5 2 18 6 1 15 6 4 -7 2 3 4 5 6 7 8 1 i j v 2 3 4 5 6 7 8 1 cpot 1457889 1 2 3 4 5 6 7 2 1 12 3 1 9 三元组顺序表上的转置(二续) 33 数据结构 Data Structures 长江大学计算机科学学院 转置 i j v 1 2 12 1 3 9 3 1 -3 3 6 14 4 3 24 5 2 18 6 1 15 6 4 -7 2 3 4 5 6 7 8 1 i j v 2 3 4 5 6 7 8 1 cpot 1467889 1 2 3 4 5 6 7 2 1 12 3 1 9 三元组顺序表上的转置(二续) 34 数据结构 Data Structures 长江大学计算机科学学院 转置 i j v 1 2 12 1 3 9 3 1 -3 3 6 14 4 3 24 5 2 18 6 1 15 6 4 -7 2 3 4 5 6 7 8 1 i j v 2 3 4 5 6 7 8 1 cpot 1467889 1 2 3 4 5 6 7 2 1 12 3 1 9 1 3 -3 三元组顺序表上的转置(二续) 35 数据结构 Data Structures 长江大学计算机科学学院 转置 i j v 1 2 12 1 3 9 3 1 -3 3 6 14 4 3 24 5 2 18 6 1 15 6 4 -7 2 3 4 5 6 7 8 1 i j v 2 3 4 5 6 7 8 1 cpot 2467889 1 2 3 4 5 6 7 2 1 12 3 1 9 6 3 14 1 3 -3 三元组顺序表上的转置(二续) 36 数据结构 Data Structures 长江大学计算机科学学院 转置 i j v 1 2 12 1 3 9 3 1 -3 3 6 14 4 3 24 5 2 18 6 1 15 6 4 -7 2 3 4 5 6 7 8 1 i j v 2 3 4 5 6 7 8 1 cpot 2467899 1 2 3 4 5 6 7 2 1 12 3 1 9 3 4 24 1 3 -3 6 3 14 三元组顺序表上的转置(二续) 37 数据结构 Data Structures 长江大学计算机科学学院 转置 i j v 1 2 12 1 3 9 3 1 -3 3 6 14 4 3 24 5 2 18 6 1 15 6 4 -7 2 3 4 5 6 7 8 1 i j v 2 3 4 5 6 7 8 1 cpot 2477899 1 2 3 4 5 6 7 2 1 12 3 1 9 2 5 18 1 3 -3 6 3 14 3 4 24 三元组顺序表上的转置(二续) 38 数据结构 Data Structures 长江大学计算机科学学院 转置 i j v 1 2 12 1 3 9 3 1 -3 3 6 14 4 3 24 5 2 18 6 1 15 6 4 -7 2 3 4 5 6 7 8 1 i j v 2 3 4 5 6 7 8 1 cpot 2577899 1 2 3 4 5 6 7 2 1 12 3 1 9 1 6 15 1 3 -3 6 3 14 3 4 24 2 5 18 三元组顺序表上的转置(二续) 39 数据结构 Data Structures 长江大学计算机科学学院 转置 i j v 1 2 12 1 3 9 3 1 -3 3 6 14 4 3 24 5 2 18 6 1 15 6 4 -7 2 3 4 5 6 7 8 1 i j v 2 3 4 5 6 7 8 1 cpot 3577899 1 2 3 4 5 6 7 2 1 12 3 1 9 4 6 -7 1 3 -3 6 3 14 3 4 24 2 5 18 1 6 15 三元组顺序表上的转置(二续) 40 数据结构 Data Structures 长江大学计算机科学学院 for(col=1;col=A.n;+col) numcol = 0; for(p=1;p=A.t;+p) /计算A中每列非零元的个数 numA.datap.j+; 5.3.2(续)三元组顺序表上的转置(二) cpot1=1; for(col = 2; col=A.n; +col) /计算元素位置 cpotcol=cpotcol-1+numcol-1; 41 for(col=1;col=A.n;+col) numcol = 0; for(p=1;p=A.t;+p) /计算A中每列非零元的个数 numA.datap.j+; cpot1=1; for(col = 2; col=A.n; +col) /计算元素位置 cpotcol=cpotcol-1+numcol-1; for(p = 1; p=A.t; +p) /转置 col = A.datap.j; q = cpotcol; AT.dataq.i = A.datap.j; AT.dataq.j = A.datap.i; AT.dataq.v = A.datap.v; cpotcol+; 42 十字链表 1 2 121 3 9 3 1 -33 6 14 4 3 24 5 2 18 6 1 156 4 -7 43 数据结构 Data Structures 长江大学计算机科学学院 5.3广义表的定义 F广义表是线性表的推广。 L=(a1,a2,.,an ),n0,ai可以是单元素，也可以是一个表。 例如： A = ( )：A是一个空表。 B = (e)：B只有一个原子。 C = (a, (b,c,d) )：C有一个原子和一个子表。 D = (A, B, C)：D有3个子表。 E = (a, E) = (a, (a, (a, , ) )：E是一个递归的表。 44 数据结构 Data Structures 长江大学计算机科学学院 5.3广义表的定义 F广义表 LS = ( 1, 2, , n )的结构特点: 广义表中的数据元素有相对次序; 广义表的长度定义为表中的元素个数; 广义表的深度定义为表的嵌套层数; 注意:“原子”的深度为 0 ; “空表”的深度为 1 。 广义表可以共享; 广义表可以是一个递归的表; 递归表的深度是无穷值，长度是有限值。 45 数据结构 Data Structures 长江大学计算机科学学院 5.4 广义表的定义 广义表是一个多层次的线性结构 例: D=(E, F) 其中: E=(a, (b, c) F=(d, (e) D EF a( )d( ) bce 46 数据结构 Data Structures 长江大学计算机科学学院 5.4 广义表的定义 例： A = ( )：长度为0，深度为1。 B = (e)：长度为1，深度为1 。 C = (a, (b,c,d) )：长度为2，深度为2 。 D = (A, B, C)：长度为3，深度为3 。 E = (a, E) = (a, (a, (a, , ) )：长度为2，深度为 。 47 数据结构 Data Structures 长江大学计算机科学学院 5.4 广义表的定义 F任何一个非空广义表 LS = ( 1, 2, , n) 均可分解表头和 表尾两部分: 表头(Head)：第一个元素 Head(LS) = 1 表尾(Tail)：除第一个元素外其余元素构成的表 Tail(LS) = ( 2, , n) F例如: D = ( E, F ) = (a, (b, c), F ) 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 ) Tail( Head(Head(a, (b, c), F ) = ? 48 数据结构 Data Structures 长江大学计算机科学学院 5.4 广义表的定义 F基本操作 结构的创建和销毁 InitGList( DestroyGList( CreateGList( CopyGList( 状态函数 GListLength(L); GListDepth(L); GListEmpty(L); GetHead(L); GetTail(L); 插入和删除操作 InsertFirst_GL( DeleteFirst_GL( 遍历 Traverse_GL(L, Visit() 49 数据结构 Data Structures 长江大学计算机科学学院 广义表的存储结构(一) 链表存储 C = (a,(b,c,d) D = (A,B,C) E = (a,E) 链表结点结构 tag=1hptp 表结点 tag=0 atom 原子结点 50 数据结构 Data Structures 长江大学计算机科学学院 广义表的存储结构(一) C = (a,(b,c,d) C 1 0a Head(C) = a Tail(C)=(b,c,d) 1 51 数据结构 Data Structures 长江大学计算机科学学院 广义表的存储结构(一) C = (a,(b,c,d) C 1 0a 1 Head(C) = a Tail(C)=(b,c,d) 1 (b,c,d ) 52 数据结构 Data Structures 长江大学计算机科学学院 广义表的存储结构(一) C = (a,(b,c,d) C 1 0a 1 1 0b 1 0c 1 0d Head(C) = a Tail(C)=(b,c,d) (b,c,d ) (c,d)(d) 53 数据结构 Data Structures 长江大学计算机科学学院 广义表的存储结构(一) C = (a,(b,c,d) C 1 0a 1 1 0b 1 0c 1 0d 54 B= (e) C 1 0a 1 1 0b 1 0c 1 0d 1 0e B 55 数据结构 Data Structures 长江大学计算机科学学院 A= () C 1 0a 1 1 0b 1 0c 1 0d 1 0e B A 56 D= (A,B,C) C 1