数据结构教程第5单元-数组和广义表

1、数据结构教程6 数组和广义表授课老师：彭伟国计算机学院 第六章 数组和广义表一、教学内容：数组的定义和顺序存储方式； 特殊矩阵及稀疏矩阵的压缩存储；第六章 数组和广义表二、教学要求：掌握一维数组以及多维数组的存储和表示方法，能计算二维数组任一元素的存贮地址；掌握对特殊矩阵进行压缩存储时的下标变换公式，掌握稀疏矩阵的三元组表示方法及矩阵转置算法思想。第六章 数组和广义表教学重点： 数组的定义 , 数组的顺序表示方法，矩阵的压缩存储。 教学难点： 矩阵的压缩存储。 第六章 数组和广义表6.1 数组的定义6.2 数组的顺序表示和实现（重点和难点）6.3 矩阵的压缩存储 （重点和难点） 6.3.1 特

2、殊矩阵 6.3.2 稀疏矩阵6.4 广义表的定义及存储结构（重点和难点）6.1 数组 数组可看成是一种特殊的线性表，其特殊在于，表中的数据元素本身也是一种线性表。一维数组：A1=（a0，a1，a2，an-1）二维数组： a00 a01 a0n-1 A2= am-10 am-11 am-1n-1又可表示为： A2=（ a0，a1，a2，an-1 ）其中 ai=（a0i，a1i，am-1i）为列向量。6.1 数组N维数组：b1b2b3bn 也可以表示为一个线性表 （ a0，a1，a2，abn -1 ）表中的每个元素均为一个N-1维的数组。数组的抽象数据类型（了解） 数组一旦被定义，它的维数和维界就

3、不再改变。因此，除了结构的初始化和销毁之外，数组只有存取元素和修改元素值的操作。数组具有以下性质： (1) 数组中的数据元素数目固定。一旦定义了一个数组,其数据元素数目不再有增减变化。 (2) 数组中的数据元素具有相同的数据类型。 (3) 数组中的每个数据元素都和一组惟一的下标值对应。 (4) 数组是一种随机存储结构。可随机存取数组中的任意数据元素。 第六章 数组和广义表6.1 数组的定义6.2 数组的顺序表示和实现6.3 矩阵的压缩存储 6.3.1 特殊矩阵 6.3.2 稀疏矩阵6.4 广义表的定义及存储结构（重点和难点）6.2 数组的顺序表示和实现类型特点: 1) 数组是多维的结构，而存储

4、空间是 一个一维的结构。 有两种顺序映象的方式: 1)以行序为主序; 2)以列序为主序;数组的顺序存储方式行优先顺序将数组元素按行排列，第i+1个行向量紧接在第i个行向量后面。以二维数组为例，按行优先顺序存储的线性序列为： a11,a12,a1n,a21,a22,a2n,am1,am2,amn 在PASCAL、C语言中，数组就是按行优先顺序存储的。列优先顺序将数组元素按列向量排列，第j+1个列向量紧接在第j个列向量之后，A的m*n个元素按列优先顺序存储的线性序列为：a11,a21,am1,a12,a22,am2,an1,an2,anm在FORTRAN语言中，数组就是按列优先顺序存储的。例如：

5、数组A b1b2 称为基地址或基址。数组元素地址计算二维数组A中任一元素ai,j 的存储位置 LOC(i,j) = LOC(0,0) + (ib2j)a0,1 a0,0 a0,2 a1,0 a1,1 a1,2 a0,1 a0,0 a0,2 a1,0 a1,1 a1,2 L L 数组元素地址计算结论: 只要知道开始元素的存放地址（即基地址），维数和每维的上、下界，以及每个数组元素所占用的单元数，就可以将数组元素的存放地址表示为其下标的线性函数。因此，数组中的任一元素可以在相同的时间内存取，即顺序存储的数组是一个随机存取结构。例2：已知二维数组Am,n按行存储的元素地址公式是： Loc(aij)=

6、 Loc(a11)+(i-1)*n+(j-1)*K , 按列存储的公式是？ Loc(aij)=Loc(a11)+(j-1)*m+(i-1)*K 例1、一个二维数组A，行下标的范围是1到6，列下标的范围是0到7，每个数组元素用相邻的6个字节存储，存储器按字节编址。那么，这个数组的体积是 个字节。 288例3、设数组a160, 170的基地址为2048，每个元素占2个存储单元，若以列序为主序顺序存储，则元素a32,58的存储地址为 。8950LOC(aij)=LOC(ac1，c2)+(j-c2)*b1+i-c1)*L答：请注意审题！利用列优先通式： 例6.1 对二维数组float a54计算： (

7、1) 数组a中的数组元素数目； (2) 若数组a的起始地址为2000,且每个数组元素长度为32位(即4个字节),数组元素a32的内存地址。 解：由于C语言中数组的行、列下界均为0,该数组行上界为5-1=4,列上界为4-l=3,所以该数组的元素数目共有(4-0+1)*(3-0+1)=5*4=20个。 又由于C语言采用行序为主序的存储方式,则有： LOC(a3,2)=LOC(a0,0)+(i*n+j)*k =2000+(3*4+2)*4=2056 第六章 数组和广义表6.1 数组的定义6.2 数组的顺序表示和实现6.3 矩阵的压缩存储 6.3.1 特殊矩阵 6.3.2 稀疏矩阵6.4 广义表的定义

8、及存储结构（重点和难点）6.3 矩阵的压缩存储 矩阵的一般存贮表示?元素的访问? 矩阵类似二维数组，存储方式同二维数组。 1 5 1 3 7 0 0 3 0 0 5 0 8 0 0 4 0 0 0 5A= 1 8 9 2 6 B= 0 0 0 0 7 3 0 2 5 1 6 0 0 0 3 7 0 6 1 3但以二维数组表示的特殊矩阵有重复元素值反复存储的缺点，及高阶的稀疏矩阵时产生的问题:1) 零值元素占了很大空间; 2) 计算中进行了很多和零值的运算，遇除法，还需判别除数是否为零。 特殊矩阵是指非零元素或零元素的分布有一定规律的矩阵,为了节省存储空间,特别是在高阶矩阵的情况下,可以利用特殊

9、矩阵的规律,对它们进行压缩存储,也就是说,使多个相同的非零元素共享同一个存储单元,对零元素不分配存储空间。 特殊矩阵的主要形式有对称矩阵、对角矩阵等,它们都是方阵,即行数和列数相同。6.3.1 特殊矩阵6.3.1 特殊矩阵1、对称矩阵 在一个n阶方阵A中，若元素满足下述性质： aij=aji 1i,jn 则称A为对称矩阵。如下图便是一个5阶对称矩阵。 1 5 1 3 7 a11 5 0 8 0 0 a21 a 22 1 8 9 2 6 a31 a32 a33 3 0 2 5 1 . 7 0 6 1 3 an1 a n2 a n3 a nn 对称矩阵A 由于对称矩阵中的元素关于主对角线对称,因此

10、在存储时可只存储对称矩阵中上三角或下三角中的元素,使得对称的元素共享一个存储空间。这样,就可以将n2个元素压缩存储到n(n+1)/2个元素的空间中。不失一般性,我们以行序为主序存储其下三角(包括对角线)的元素。 n2个元素 n(n+1)/2个元素 A0.n-1,0.n-1 B0.n(n+1)/2-1 aij bkk=+ j ij+ i ij 为了便于访问对称矩阵A中的元素，我们必须在aij和sak之间找一个对应关系。 若ij，则ai j在下三角形中。 ai j之前的i行（从第0行到第i-1行）一共有1+2+i-1+(i)=i(i+1)/2个元素，在第i行上， a i j之前恰有j个元素（即ai

11、1,ai2,ai3,aij-1），因此有： k=i*(i+1)/2+j ij 若ij，则aij是在上三角矩阵中。因为aij=aji，所以只要交换上述对应关系式中的i和j即可得到： k=j*(j+1)/2+i ij2、三角矩阵以主对角线划分，三角矩阵有上三角和下三角两种。上三角矩阵如图所示，它的下三角（不包括主对角线）中的元素均为常数。下三角矩阵正好相反，它的主对角线上方均为常数，如图所示。在大多数情况下，三角矩阵常数为零。 a11 a12 a 1 n a11 c c c a22 a 2 n a21 a22 c . . c c a n n a n 1 a n 2 a n n (a)上三角矩阵 (

12、b)下三角矩阵三角矩阵三角矩阵存储a1,1a1,2a1,na2,2a2,3a 2, n an,n 对上三角阵只需存上三角部分，一维数组B中从0号位置开始存放，并按行优先存储，如下图所示：0 1 n-1 n n+1 2n-2 n(n+1)/2-1 则对矩阵A的任意矩阵元素aij（ij），在按行优先存储的情况下，它在一维数组B中对应的存储位置为： LOC(i,j)=n+(n-1)+(n-2)+(n-(i-1)+1)+(j-i) =(2n-i+2)(i-1)/2+j-i6.3.2 稀疏矩阵 什么是稀疏矩阵？简单说，矩阵非零元素远远小于矩阵元素的总数，则称为稀疏矩阵. 在存储稀疏矩阵时，为了节省存储单

13、元，只存储非零元素。故用一个三元组(i,j,aij)来存储矩阵的一个非零元。 一个三元组(i,j,aij)唯一确定了矩阵的一个非零元。因此，稀疏矩阵可由表示非零元的三元组及其行列数唯一确定。 例如，下列三元组表(1,2,12)(1,3,9),(3,1,- 3),(3,6,14),(4,3,24), (5,2,18),(6,1,15),(6,4,-7)加上(6,7)这一对行、列值便可作为下列矩阵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 稀疏矩阵

14、M 一、三元组顺序表（以行为主的顺序）ijv121415-522-731363428三元组顺序表特点 非零元在表中按行序有序存储，因此便于进行依行顺序处理的 矩阵运算；然而，若需按行号存取某一行的非零元，则需从头开始进行查找。另当矩阵的非零元个数和位置在操作过程中变化较大时，就不适宜了。解决方法：三元组采用其他表示方法 行逻辑链接的顺序表和十字链表 假设有一个67阶稀疏矩阵A(为图示方便,我们所取的行列数都很小),A中元素如下图所示。则对应的三元组线性表为： (0,2,1),(1,1,2),(2,0,3),(3,3,5), (4,4,6),(5,5,7),(5,6,4)一个稀疏矩阵A 若把稀疏

15、矩阵的三元组线性表按顺序存储结构存储,则称为稀疏矩阵的三元组顺序表。则三元组顺序表的数据结构可定义如下： #define MaxSize 100 /*矩阵中非零元素最多个数*/ typedef struct int r; /*行号*/ int c; /*列号*/ ElemType d; /*元素值*/ TupNode; /*三元组定义*/ typedef struct int rows; /*行数值*/ int cols; /*列数值*/ int nums; /*非零元素个数*/ TupNode dataMaxSize; TSMatrix; /*三元组顺序表定义*/ 其中,data域中表示的非

16、零元素通常以行序为主序顺序排列,它是一种下标按行有序的存储结构。这种有序存储结构可简化大多数矩阵运算算法。下面的讨论假设data域按行有序存储。 (1) 从一个二维矩阵创建其三元组表示 以行序方式扫描二维矩阵A,将其非零的元素插入到三元组t的后面。算法如下： void CreatMat(TSMatrix &t,ElemType AMN) int i,j; t.rows=M;t.cols=N;t.nums=0; for (i=0;iM;i+) for (j=0;j=t.rows | cs=t.cols) return 0; while (kt.datak.r) k+;/*查找行*/ while

17、(kt.datak.c) k+;/*查找列*/ if (t.datak.r=rs & t.datak.c=cs) t.datak.d=x; /*存在这样的元素 else /*不存在这样的元素时插入一个元素*/ for (i=t.nums-1;ik;i-) /*元素后移*/ t.datai+1.r=t.datai.r; t.datai+1.c=t.datai.c; t.datai+1.d=t.datai.d; t.datak.r=rs;t.datak.c=cs;t.datak.d=x; t.nums+; return 1; (3) 将指定位置的元素值赋给变量 先在三元组t中找到指定的位置,将该处

18、的元素值赋给x。算法如下： int Assign(TSMatrix t,ElemType &x,int rs,int cs) int k=0; if (rs=t.rows | cs=t.cols) return 0; while (kt.datak.r) k+; while (kt.datak.c) k+; if (t.datak.r=rs & t.datak.c=cs) x=t.datak.d; return 1; else return 0; (4) 输出三元组 从头到尾扫描三元组t,依次输出元素值。算法如下： void DispMat(TSMatrix t) int i; if (t.n

19、ums=0) return;printf(“t%dt%dt%dn,t.rows,t.cols,t.nums); printf( -n); for (i=0;it.nums;i+)printf(t%dt%dt%dn,t.datai.r,t.datai.c, t.datai.d); (5) 矩阵转置 对于一个mn的矩阵Amn,其转置矩阵是一个nm的矩阵。设为Bnm,满足ai,j=bj,i,其中1im,1jn。其完整的转置算法如下： void TranTat(TSMatrix t,TSMatrix &tb) int p,q=0,v; /*q为tb.data的下标*/ tb.rows=t.cols;t

20、b.cols=t.rows;tb.nums=t.nums; if (t.nums!=0) for (v=0;vt.cols;v+) for (p=0;pt.nums;p+) /*p为t.data的下标*/ if (t.datap.c=v) tb.dataq.r=t.datap.c; tb.dataq.c=t.datap.r; tb.dataq.d=t.datap.d; q+; 单选题例1 在一个二维数组A中，假设每个数组元素的长度为3个存储单元，行下标i从0到8，列下标j从0到9，从首地址SA开始按行连续存放。在这种情况下，元素A85的起始地址为_. A.SA+141 B.SA+144 C.S

21、A+222 D.SA+255【解答】D。按照二维数组计算地址（按行优先顺序）的公式LOC(i,j)=LOC(0,0)+(i*m+j)*L其中，LOC(0,0)=SA，是数组存放首地址，L=3是每个数组元素的长度，m=9-0+1=10是数组的列数。因此有LOC(8,5)=SA+(8*10+5)*3=SA+255单选题例2 设有一个10阶的对称矩阵A1010,采用压缩存储方式按行将矩阵中下三角部分的元素存入一堆数组B中，A00存入B0中，则A85在B中的位置是_. A.32 B.33 C.41 D.65【解答】C。如果将对称矩阵的下三角部分（要求0=i=9,0=j=j)前面总共有1+2+i-1+j

22、=i(i+1)/2+j个元素。这样可得LOC(8,5)=8(8+1)/2+5=413. 数组A05,06的每个元素占5个单元，将其按列优先次序存储在起始地址为1000的连续内存单元中，则元素a55的地址为（ ） A.1175 B.1180 C.1205 D.12104. 5行8列的二维数组A（行列下标均从0开始）按行存储在存储器中，每个元素占4个存储单元，首地址为100，则存储地址为184的元素是（ ）。A. A25 B. A26 C. A35 D. A365.设二维数组A54（行列下标从1开始编号）的每个元素占4个单元，将其按行优先顺序存放在起始地址为680的连续内存单元中，则元素a42的地

23、址为（ ）A728 B732 C736 D740AAB 第六章 数组和广义表6.1 数组的定义6.2 数组的顺序表示和实现6.3 矩阵的压缩存储 6.3.1 特殊矩阵 6.3.2 稀疏矩阵6.4 广义表的定义及存储结构（重点和难点）6.4 广义表1、定义：广义表（Lists，又称列表）是线性表的推广。广义表是递归定义的线性结构， LS = ( 1, 2, , n ) 其中：i 或为原子 或为广义表 广义表是n(n=0)个元素a1,a2,a3,an的有限序列，其中ai或者是原子项，或者是一个广义表。通常记作LS=（a1,a2,a3,an)。LS是广义表的名字，n为它的长度。若ai是广义表，则称它

24、为LS的子表。线性表的成分都是结构上不可分的单元素广义表的成分可以是单元素，也可以是有结构的表线性表是一种特殊的广义表广义表不一定是线性表，也不一定是线性结构广义表与线性表的区别？2、广义表的特点列表是一个多层次的结构；列表可为其他列表所共享；列表可以是一个递归的表递归表的深度是无穷值，长度是有限值。有次序性有长度有深度可递归可共享一个直接前驱和一个直接后继表中元素个数表中括号的重数自己可以作为自己的子表可以为其他广义表所共享E=(a,E)=(a,(a,E)= (a,(a,(a,.)，E为递归表1）A =( )2）B = ( e ) 3）C =( a ,( b , c , d ) ) 4）D=( A , B ,C )5）E=(a, E)n=0，因为A是空表n=1，表中元素e是原子n=2，a 为原子，(b,c,d)为子表n=3，3个元素都