数据结构课件数组与广义表资料

一、教学内容：一、教学内容：1、数组的定义和顺序存储方式；、数组的定义和顺序存储方式；2、特殊矩阵的压缩存储；、特殊矩阵的压缩存储；3、稀疏矩阵、稀疏矩阵4、广义表的概念、表示及基本操作；广义表存储结构的实现。、广义表的概念、表示及基本操作；广义表存储结构的实现。二、教学要求：二、教学要求：1、了解数组的两种存储表示方法，并掌握数组在以行为主的存储结构中的地址、了解数组的两种存储表示方法，并掌握数组在以行为主的存储结构中的地址计算方法；计算方法；2、掌握对特殊矩阵进行压缩存储时的下标变换公式；、掌握对特殊矩阵进行压缩存储时的下标变换公式；3、了解稀疏矩阵的两种压缩存储方法的特点和适用范围，理解以三元组表示稀、了解稀疏矩阵的两种压缩存储方法的特点和适用范围，理解以三元组表示稀疏矩阵时进行矩阵运算采用的处理方法；疏矩阵时进行矩阵运算采用的处理方法；4、掌握广义表的结构特点及其存储表示方法，会对非空广义表进行分解。、掌握广义表的结构特点及其存储表示方法，会对非空广义表进行分解。第五章第五章 数组和广义表数组和广义表第五章第五章 数组和广义表数组和广义表5.1 数组的定义5.2 数组的顺序表示和实现5.3 矩阵的压缩存储 5.3.1 特殊矩阵 5.3.2 稀疏矩阵 5.4 广义表的定义 5.5 广义表的存储结构 数组和广义表可看成是一种特殊的线性表，其特数组和广义表可看成是一种特殊的线性表，其特殊在于，表中的数据元素本身也是一种线性表。殊在于，表中的数据元素本身也是一种线性表。5.1 5.1 数数组的定的定义由于数组中各元素具有统一的类型，并且数组元素由于数组中各元素具有统一的类型，并且数组元素的下标一般具有固定的上界和下界，因此，数组的下标一般具有固定的上界和下界，因此，数组的处理比其它复杂的结构更为简单。多维数组是的处理比其它复杂的结构更为简单。多维数组是向量的推广。例如，二维数组：向量的推广。例如，二维数组：()()()()()()()()()M个行向量个行向量N个列向量个列向量 在在C C语言中，一个二维数组类型可以定义为其分量语言中，一个二维数组类型可以定义为其分量类型为一维数组类型的一维数组类型，也就是说，类型为一维数组类型的一维数组类型，也就是说，typedeftypedef elemtypeelemtype array2mn;array2mn;等价于：等价于：typedeftypedef elemtypeelemtype array1n;array1n;typedeftypedef array1 array2m;array1 array2m;数组一旦被定义，它的维数和维界就不再改变。数组一旦被定义，它的维数和维界就不再改变。因此，除了结构的初始化和销毁之外，数组只有存因此，除了结构的初始化和销毁之外，数组只有存取元素和修改元素值的操作。取元素和修改元素值的操作。5.2 5.2 数组的顺序表示和实现数组的顺序表示和实现 由于计算机的内存结构是一维的，因此用一由于计算机的内存结构是一维的，因此用一维内存来表示多维数组，就必须按某种次序将维内存来表示多维数组，就必须按某种次序将数组元素排成一列序列，然后将这个线性序列数组元素排成一列序列，然后将这个线性序列存放在存储器中。存放在存储器中。又由于对数组（或矩阵）一般不做插入和又由于对数组（或矩阵）一般不做插入和删除操作，也就是说，数组一旦建立，结构中删除操作，也就是说，数组一旦建立，结构中的元素个数和元素间的关系就不再发生变化。的元素个数和元素间的关系就不再发生变化。因此，一般都是采用顺序存储的方法来表示数因此，一般都是采用顺序存储的方法来表示数组。组。通常有两种顺序存储方式：通常有两种顺序存储方式：以行序为主序以行序为主序以列序为主序以列序为主序a11a12.a1na21a22.a2nam1am2.amn.Loc(aij)=Loc(a11)+(i-1)n+(j-1)*l按行序为主序存放按行序为主序存放 amn .am2 am1 .a2n .a22 a21 a1n .a12 a1101n-1m*n-1n按列序为主序存放按列序为主序存放每个元素占一个单每个元素占一个单元元01m-1m*n-1m amn .a2n a1n.am2 .a22 a12 am1 .a21 a11a11a12.a1na21a22.a2nam1am2.amn.Loc(aij)=Loc(a11)+(j-1)m+(i-1)*l计算二维数组元素地址的通式计算二维数组元素地址的通式设一般的二维数组是设一般的二维数组是AcAc1 1.d.d1 1,c,c2 2.d.d2 2，这里这里c c1 1,c,c2 2不一定是不一定是0 0。无论规定行优先或列优先，只要知道以下三要素便可随时求出任无论规定行优先或列优先，只要知道以下三要素便可随时求出任一元素的地址（这样数组中的任一元素便可以随机存取！）：一元素的地址（这样数组中的任一元素便可以随机存取！）：二维数组二维数组列优先列优先存储的通式为：存储的通式为：LOC(aij)=LOC(ac1，c2)+(j-c2)*(d1-c1+1)+i-c1)*Lac1,c2ac1,d2aijad1,c2ad1,d2Amn=单个元素单个元素长度长度aijaij之前的之前的行数行数数组基址数组基址总列数，即总列数，即第第2 2维长度维长度aijaij本行前面本行前面的元素个数的元素个数开始结点的存放地址（即基地址）开始结点的存放地址（即基地址）维数和每维的上、下界；维数和每维的上、下界；每个数组元素所占用的单元数每个数组元素所占用的单元数则则行优先行优先存储时的地址公式为：存储时的地址公式为：LOC(aij)=LOC(ac1，c2)+(i-c1)*(d2-c2+1)+j-c2)*L例例2：已知二维数组已知二维数组Am,m按行存储的元素地址公式是：按行存储的元素地址公式是：Loc(aij)=Loc(a11)+(i-1)*m+(j-1)*K,按列存储的公式是？按列存储的公式是？Loc(aij)=Loc(a11)+(j-1)*m+(i-1)*K （尽管是方阵，但公式仍不同）尽管是方阵，但公式仍不同）例例1软考题软考题：一个二维数组一个二维数组A，行下标的范围是行下标的范围是1到到6，列下，列下标的范围是标的范围是0到到7，每个数组元素用相邻的，每个数组元素用相邻的6个字节存储，存储器个字节存储，存储器按字节编址。那么，这个数组的体积是按字节编址。那么，这个数组的体积是个字节。个字节。288例例3：00年计算机系考研题年计算机系考研题设数组设数组a160,170的基地址的基地址为为2048，每个元素占，每个元素占2个存储单元，若以列序为主序顺序存储，个存储单元，若以列序为主序顺序存储，则元素则元素a32,58的存储地址为的存储地址为。8950LOC(aij)=LOC(ac1，c2)+(j-c2)*(d1-c1+1)+i-c1)*L得：得：LOC(a32,58)=2048+(58-1)*(60-1+1)+32-1)*28950答：请注意审题！答：请注意审题！利用列优先通式：利用列优先通式：答：Volume=m*n*L=(6-1+1)*(7-0+1)*6=48*6=288 5.3 5.3 矩阵的压缩存储矩阵的压缩存储 在科学与工程计算问题中，矩阵是一种常用的数学在科学与工程计算问题中，矩阵是一种常用的数学对象，在高级语言编制程序时，简单而又自然的方法，对象，在高级语言编制程序时，简单而又自然的方法，就是将一个矩阵描述为一个二维数组。矩阵在这种存就是将一个矩阵描述为一个二维数组。矩阵在这种存储表示之下，可以对其元素进行随机存取，各种矩阵储表示之下，可以对其元素进行随机存取，各种矩阵运算也非常简单，并且存储的密度为运算也非常简单，并且存储的密度为1 1。但是在矩阵中。但是在矩阵中非零元素呈某种规律分布或者矩阵中出现大量的零元非零元素呈某种规律分布或者矩阵中出现大量的零元素的情况下，看起来存储密度仍为素的情况下，看起来存储密度仍为1 1，但实际上占用了，但实际上占用了许多单元去存储重复的非零元素或零元素，这对高阶许多单元去存储重复的非零元素或零元素，这对高阶矩阵会造成极大的浪费，为了节省存储空间，矩阵会造成极大的浪费，为了节省存储空间，我们可我们可以对这类矩阵进行压缩存储：以对这类矩阵进行压缩存储：即为多个相同的非零元即为多个相同的非零元素只分配一个存储空间；对零元素不分配空间。素只分配一个存储空间；对零元素不分配空间。5.3.1 5.3.1 特殊矩阵特殊矩阵 所谓特殊矩阵是指非零元素或零元素的分布有一所谓特殊矩阵是指非零元素或零元素的分布有一定规律的矩阵。定规律的矩阵。1 1、对称矩阵、对称矩阵 在一个在一个n n阶方阵阶方阵A A中，若元素满足下述性质：中，若元素满足下述性质：a aijij=a ajiji 0i,jn-1 0i,jn-1则称则称A A为对称矩阵。为对称矩阵。对称矩阵中的元素关于主对角线对称，故只要对称矩阵中的元素关于主对角线对称，故只要存储矩阵中上三角或下三角中的元素，让每两个存储矩阵中上三角或下三角中的元素，让每两个对称的元素共享一个存储空间，这样，能节约近对称的元素共享一个存储空间，这样，能节约近一半的存储空间。不失一般性，我们按一半的存储空间。不失一般性，我们按“行优先行优先顺序顺序”存储主对角线（包括对角线）以下的元素，其存储形式如存储主对角线（包括对角线）以下的元素，其存储形式如图所示：图所示：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在这个下三角矩阵中，第在这个下三角矩阵中，第i i行恰有行恰有i+1i+1个元素，元素总数为个元素，元素总数为：n(n+1)/2n(n+1)/2 因此，我们可以按从上到下、从左到右将这些元素存放在因此，我们可以按从上到下、从左到右将这些元素存放在一个向量一个向量sa0.n(n+1)/2-1sa0.n(n+1)/2-1中。为了便于访问对称矩阵中。为了便于访问对称矩阵A A中中的元素，我们必须在的元素，我们必须在a aijij和和saksak 之间找一个对应关系。之间找一个对应关系。若若ij，则则aij在下三角形中。在下三角形中。aij之前的之前的i行（从第行（从第0行行到第到第i-1行）一共有行）一共有1+2+i=i(i+1)/2个元素，在第个元素，在第i行行上，上，aij之前恰有之前恰有j个元素（即个元素（即ai0,ai1,ai2,aij-1），），因此因此有：有：k=i*(i+1)/2+j0kn(n+1)/2若若ij，则则aij是在上三角矩阵中。因为是在上三角矩阵中。因为aij=aji，所以只要所以只要交换上述对应关系式中的交换上述对应关系式中的i和和j即可得到：即可得到：k=j*(j+1)/2+i0kn(n+1)/2 特殊矩阵，其非零元素的分布都是有规律的，因此特殊矩阵，其非零元素的分布都是有规律的，因此总能找到一种方法将它们压缩存储到一个向量中，并总能找到一种方法将它们压缩存储到一个向量中，并且一般都能找到矩阵中的元素与该向量的对应关系，且一般都能找到矩阵中的元素与该向量的对应关系，通过这个关系，仍能对矩阵的元素进行随机存取。通过这个关系，仍能对矩阵的元素进行随机存取。2.5.2 2.5.2 稀疏矩阵稀疏矩阵 什么是稀疏矩阵？简单说，设矩阵什么是稀疏矩阵？简单说，设矩阵A A中有中有s s个个非零元素，若非零元素，若s s远远小于矩阵元素的总数（即远远小于矩阵元素的总数（即smnsmn），），则称则称A A为稀疏矩阵为稀疏矩阵。精确地说，设在的矩阵精确地说，设在的矩阵A A中，有中，有s s个非零元素。个非零元素。令令 e=s/(m*n)e=s/(m*n)，称称e e为矩阵的稀疏因子。通常为矩阵的稀疏因子。通常认为认为e0.05e0.05时称之为稀疏矩阵。时称之为稀疏矩阵。在存储稀疏矩阵时，为了节省存储单元，很自然在存储稀疏矩阵时，为了节省存储单元，很自然地想到使用压缩存储方法。但由于非零元素的地想到使用压缩存储方法。但由于非零元素的分布一般是没有规律的，因此在存储非零元素分布一般是没有规律的，因此在存储非零元素的同时，还必须同时记下它所在的行和列的位的同时，还必须同时记下它所在的行和列的位置（置（i,j)i,j)。反之，一个三元组反之，一个三元组(i,j,ai,j,aijij)唯一确唯一确定了矩阵定了矩阵A A的一个非零元。因此，稀疏矩阵可的一个非零元。因此，稀疏矩阵可由表示非零元的三元组及其行列数唯一确定。由表示非零元的三元组及其行列数唯一确定。1、三元组表示法、三元组表示法例如，下列三元组表例如，下列三元组表(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,8)(6,7,8)这一对行、列值便可作为下列矩阵这一对行、列值便可作为下列矩阵M M的另一种的另一种描述。描述。0 12 9 0 0 0 0 0 0-3 0 0 15 0 0 0 0 0 0 0 12 0 0 0 18 0 -3 0 0 0 0 14 0 9 0 0 24 0 0 0 0 24 0 0 0 0 0 0 0 0 0 7 0 18 0 0 0 0 0 0 0 14 0 0 0 15 0 0 7 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 M=T=如果有如果有k个非零元素，需要个非零元素，需要3k个存储单元。可将个存储单元。可将i和和j作为关键作为关键码，查找矩阵元素。码，查找矩阵元素。缺点：缺点：当数据元素值从当数据元素值从0变为非变为非0，要想表，要想表中插入结点，为了保持行优先顺序，插入要移动后面的元素。中插入结点，为了保持行优先顺序，插入要移动后面的元素。三元组顺序表三元组顺序表 假设以顺序存储结构来表示三元组表，则可得假设以顺序存储结构来表示三元组表，则可得到稀疏矩阵的一种压缩存储方法到稀疏矩阵的一种压缩存储方法三元顺序表。三元顺序表。#define define maxsizemaxsize 10000 10000 typedeftypedef intint datatypedatatype;typedeftypedef structstruct intint i,j;i,j;/该非零元的行下标和列下标该非零元的行下标和列下标 datatypedatatype v;v;triplet;triplet;typedeftypedef structstruct triple triple datamaxsizedatamaxsize;intint m,n,t;m,n,t;/矩阵的行数、列数和非零元个数矩阵的行数、列数和非零元个数 tripletabletripletable;带行指针向量的单链表表示带行指针向量的单链表表示Y每行的非零元用一个单链表存放每行的非零元用一个单链表存放 Y设置一个行指针数组，指向本行第一个非零元设置一个行指针数组，指向本行第一个非零元结点；若本行无非零元，则指针为空结点；若本行无非零元，则指针为空2、链式存储结构、链式存储结构typedef struct node int col;int val;struct node *link;JD;typedef struct node *TD;1 35 73 -11 -12 -24 2需存储单元个数为需存储单元个数为3t+mY 表头结点与单链表结点类型定义表头结点与单链表结点类型定义矩阵的一个非零元素用一个结点表示，每个结矩阵的一个非零元素用一个结点表示，每个结点包括五个字段，分别为元素的行下标、列下点包括五个字段，分别为元素的行下标、列下标、值以及指向本行和本列下一个非零元素的标、值以及指向本行和本列下一个非零元素的指针。指针。需要存储空间需要存储空间5k+m+n具有链表的灵活性（插入、删除方便）具有链表的灵活性（插入、删除方便）3、行、行-列表示法（十字链表）列表示法（十字链表）tpedef struct node int row,col,val;struct node *down,*right;JD;rowcolvaldownright113418225234第五章第五章 广义表广义表广义表的基本概念广义表的基本概念广义表的链接存储结构广义表的链接存储结构一、一、基本概念基本概念广义表是第二章提到的线性表的推广。线性表中的元素广义表是第二章提到的线性表的推广。线性表中的元素仅限于原子项仅限于原子项(单个数据元素单个数据元素)，即不可以再分，而广义表，即不可以再分，而广义表中的元素既可以是原子项，也可以是子表中的元素既可以是原子项，也可以是子表(另一个线性表另一个线性表)。(如果如果ai是单个数据元素是单个数据元素,则称则称ai为广义表的原子为广义表的原子)1广义表的定义广义表的定义广广义义表表是是n0个个元元素素a0，a1，an-1的的有有限限序序列列，其其中中每每一一个个ai或或者者是是原原子子，或或者者是是一一个个子子表表。广广义义表表通通常常记记为为GL=(a0,a1,an-1)，其其中中GL为为广广义义表表的的名名字字，n为为广广义义表表的的长长度度，每每一一个个ai为为广广义义表表的的元元素素。但但在在习习惯惯中中，一一般般用用大大写写字母表示广义表，小写字母表示原子。字母表示广义表，小写字母表示原子。称称第第一一个个元元素素a0为为广广义义表表GL的的表表头头,其其余余部部分分(a1,.an-1)为为GL的表尾的表尾,分别记作分别记作head(GL)=a0和和tail(GL)=(a1,.an-1)说明说明:1.广义表是线性表的一种推广。广义表是线性表的一种推广。2.广义表的定义是递归的。因为在描述广义广义表的定义是递归的。因为在描述广义表的时候又用到了广义表的概念表的时候又用到了广义表的概念.3.广义表是多层次结构。广义表是多层次结构。4.一个广义表可以为其它广义表所共享。一个广义表可以为其它广义表所共享。2广义表举例广义表举例(1)A=(),A为空表，长度为为空表，长度为0。(2)B=(a,（b,c),B是是长长度度为为2的的广广义义表表，第第一一项项为为原原子，第二项为子表。子，第二项为子表。(3)C=(x,y,z)C是是长长度度为为3的的广广义义表表，每每一一项项都都是是原原子。子。(4)D=(B,C)，D是是长长度度为为2的的广广义义表表，每每一一项项都都是是上上面面提到的子表。提到的子表。(5)E=(a,E)是是长长度度为为2的的广广义义表表，第第一一项项为为原原子子，第第二二项为它本身。（项为它本身。（递归递归）3广义表的深度广义表的深度一一个个广广义义表表的的深深度度是是指指该该广广义义表表展展开开后后所所含含括括号号的的层数。层数。例例如如，A=(b,c)的的深深度度为为1，B=(A,d)的的深深度度为为2，C=(f,B,h)的深度为的深度为3。4取表头运算取表头运算head若广义表若广义表LS=(a1，a2，an)，则则head(LS)=a1。取表头运算得到的结果可以是原子，也可以是一个子表。取表头运算得到的结果可以是原子，也可以是一个子表。例如，例如，head(a1,a2,a3,a4)=a1，head(a1,a2),(a3,a4),a5)=(a1,a2)。5取表尾运算取表尾运算tail若广义表若广义表LS=(a1，a2，an)，则则tail(LS)=(a2，a3，an)。即即取取表表尾尾运运算算得得到到的的结结果果是是除除表表头头以以外外的的所所有有元元素素，取取表表尾尾运运算得到的结果一定是一个子表。算得到的结果一定是一个子表。值得注意的是广义表值得注意的是广义表()和和()是不同的，前者为空表，长是不同的，前者为空表，长度为度为0，后者的长度为，后者的长度为1，可得到表头、表尾均为空表，即，可得到表头、表尾均为空表，即head()=()，tail()=()。1.GetTail【(b,k,p,h)】;2.GetHead【(a,b),(c,d)】;3.GetTail【(a,b),(c,d)】;4.GetTail【GetHead【(a,b),(c,d)】;例：例：求下列广义表操作的结果（严题集求下列广义表操作的结果（严题集5.10）(k,p,h)（b）(a,b)5.GetTail【（【（e）】）】;6.GetHead【()】.7.GetTail【()】.()(a,b)()()(c,d)二、二、广义表的链接广义表的链接存储结构存储结构由由于于广广义义表表的的元元素素类类型型不不一一定定相相同同，因因此此，难难以以用用顺顺序序结结构构存存储储表表中中元元素素，通通常常采采用用链链接接存存储储方方法法来来存存储储广广义义表表中中元元素素，并称之为广义链表。并称之为广义链表。1、结点结构形式是：、结点结构形式是：tag为标志字段，若为标志字段，若tag=0表示该结点为原子结点，第二个域表示该结点为原子结点，第二个域data存放相应原子元素的信息。存放相应原子元素的信息。若若tag=1为子表结点为子表结点,第二个域为第二个域为sublist存放相应子表第一个存放相应子表第一个元素对应的结点的地址。元素对应的结点的地址。link存放本元素同一层的下一个存放本元素同一层的下一个元素所在链结点的地址。元素所在链结点的地址。用用C语言描述结点的类型如下：语言描述结点的类型如下：typedefstructnodeinttag;unionstructnode*sublist;chardata;dd;structnode*link;NODE;2、结点的链接表示（、结点的链接表示（见书见书109页页5.9）(1)一般的链接方法一般的链接方法广义表的每个元素有一个结点表示，同一层每个结点广义表的每个元素有一个结点表示，同一层每个结点按其在表中的次序用按其在表中的次序用link指针链接起来，每个表结点的指针链接起来，每个表结点的sublist指向子表的第一个元素对应的结点。指向子表的第一个元素对应的结点。(2)带附加表头链接方法带附加表头链接方法在每个广义表的表头结点之前增加一个表结点。在每个广义表的表头结点之前增加一个表结点。相对于一般的链接方法，这种链接方法在进行元素的相对于一般的链接方法，这种链接方法在进行元素的插入、删除和表的共享等处理时会显得更为方便。插入、删除和表的共享等处理时会显得更为方便。0a0b0cBA=NULL0a1C1110a11DE一般的广义表链接存储结构一般的广义表链接存储结构(1)A=()(2)B=(b,c)(3)C=(a,(b,c)(4)D=(C,(),(a)(5)E=(a,E)