数据结构课件第5章数组和广义表.ppt

《数据结构课件第5章数组和广义表.ppt》由会员分享，可在线阅读，更多相关《数据结构课件第5章数组和广义表.ppt（64页珍藏版）》请在三一办公上搜索。

1、1,第,5,章,数,组,和,广,义,表,5.1 数组的逻辑结构,5.2 数组的顺序存储结构5.3 矩阵的压缩存储5.4 广义表,数组(array)是最常用的数据结构之一。几乎所有的程序设计语言都把数组类型设定为固有类型。,数组的定义,线性结构中的数据都是非结构的原子类型，元素的值是不再分解的。而数组可以看成是线性表在下述含义上的扩展：,2,数组的基本操作,表中的数据元素本身也是一种数据结构。,数组是由下标和值组成的序对集合。在数组中，一旦给定下标，都存在一个与其相对应的值，这个值就称为数组元素。,也可以说，数组中的每个数据元素都对应于一组下标（j1,j2,jn），每个下标取值范围是 1jibi

2、，bi 称为第 i 维的长度（i=1,2,n）。显然，当 n=1 时，n 维数组就退化为定长的线性表。反之，n 维数组也可以看成是线性表的推广。,3,5.1.1 数组的定义,可以把二维数组看成是这样一个定长线性表：它的每个数据元素也是一个定长线性表。,Amn=,4,例如，下面是一个二维数组，且以 m 行 n 列的矩阵形式表示。,每个数据元素 j是一个列向量形式的线性表,Amn=,二维数组 A 还可以看成是一个线性表：,A=(1,2,n),j=(a1j,a2j,am,j)1 j n,每个数据元素是一个行向量形式的线性表 B=(123,m),Amn=(a11 a12 a1,n),(am,1am,2

3、 am,n),(a21 a22 a2,n),i=(ai 1,ai 2,ai,n)1 i m,5,6,5.1.2 数组的抽象类型定义,ADT Array D=aj1j2j3.jn|n0,称为数组的维数,ji是数组的第i维下标,1 ji bi,bi为数组第i维的长度，aj1j2j3.jnElementSet数据关系：=R1,R2,.Rn Ri=|1jk bk,1kn 且 ki,1ji bi-1,aj1j2.jn,aj1ji+1jnD,i=1,n,8,5.1.2 数组的抽象类型定义,由于内存储器的结构是一维的。一维数组可直接采用顺序存储。用一维的内存存储表示多维数组时，需按某种次序将数组中元素排成一

4、线性序列，再将这个线性序列存放在一维的内存中，即数组的顺序存储结构表示。,顺序存储的定位公式,9,数组的顺序存储表示,基本操作的算法描述,用顺序存储结构来存储数组中的元素，一定要按照某种次序将元素排成一个线性序列。有两种存储方式：,(1)以列为主序(column major order)的存储方式，即按列优先，逐列顺序存储。,(2)以行为主序(row major order)的存储方式，即按行优先，逐行顺序存储。,10,5.2.1 顺序存储的定位公式,11,列主次序存放,12,行主次序存放,13,（）一维数组的地址计算：设一维数组为：=(a1,a2,ai,an),数组中每个元素占size个存储

5、单元，则元素ai的存储地址为：Loc(Ai)=Loc(A1)+(i-1)*size。,数组的地址计算,14,二维数组的地址计算 假设每个数据元素占 1 个存储单元，且以行序为主序的进行存储，则二维数组 A 中任一元素 aij 的存储位置可以由下面定位公式确定LOC(Ai,j)=LOC(A1,1)+n*(i-1)+(j-1),其中：,LOC(Ai,j)是 aij 的存储位置；,LOC(A1,1)是 a11 的存储位置，即二维数组 A 的起始存储位置，也称为基地址或基址；,n是数组第二维的长度。,15,假设每个数据元素占size个存储单元，则二维数组 A 中任一元素 aij 的存储位置可以由下面定

6、位公式确定LOC(Ai,j)=LOC(A1,1)+(n*(i-1)+(j-1)*size,三维数组的地址计算 三维数组A(1:r,1:m,1:n)。假设每个数据元素占size个存储单元，且以行序为主序的进行存储，首元素a111的地址为Loc(A111),求任意元素aijk的地址。显然，ai11地址为 oc(Ai11)=Loc(A111)+(i-1)*m*n,因为在该元素之前有i-1个m*n的二维数组。,16,不难得到三维数组任意元素aijk的地址：Loc(Aijk)=Loc(A111)+(i-1)*m*n+(j-1)*n+(k-1)*size,其中：ir,jm,kn。,矩阵(matrix)是很

7、多科学与工程计算问题中研究的数学对象。在数据结构中，我们感兴趣的不是矩阵本身，而是如何存储矩阵的元素而使矩阵的各种运算能够有效地进行。,特殊矩阵包括两个部份：元素分布有特殊规律的矩阵,找到规律对应的公式，实现压缩存储。非零元素很少的稀疏矩阵，可采用只存非零元素的方法实现压缩存储。,17,特殊矩阵的压缩存储,所谓压缩存储是指：为多个值相同的元素只分配一个存储空间；对零元不分配空间。,18,稀疏矩阵的逻辑结构,稀疏矩阵的存储结构,假若相同的元素或者零元素在矩阵中的分布有一定规律，则称特殊矩阵。特殊矩阵主要有 3 种：对称矩阵、三角矩阵、带状矩阵。,在所有这些统称为“特殊矩阵”的矩阵中，非零元的分布

8、都有一个明显的规律，从而都可以将其压缩存储到一维数组中，并且找到每个非零元在一维数组中的对应关系。,19,5.3.1 特殊矩阵的压缩存储,若一个 n 阶矩阵 M 中的元素满足下述性质,1.对称矩阵,aij=aji1 i，j n,则称为 n 阶对称矩阵。,20,对于对称矩阵，可以为每一对对称元只分配一个存储空间，这样就可以将 n2 个元压缩存储到 n(n+1)/2 个元的空间中。,假设以行序为主序存储对称矩阵的下三角（包括对角线）中的元。以一维数组 Bn(n+1)/2 作为 n 阶对称矩阵 M 的存储结构，,21,B,Loc(Aij=1,2,3,4,Loc(Aij)=Loc(A11)+i*(i-

9、1)/2+j-1(ij),三角矩阵分为下三角矩阵和上三角矩阵。所谓下(上)三角矩阵是指矩阵的上(下)三角(不包括对角线)中的元均为常数 c 或为零的 n 阶矩阵。,2.三角矩阵,22,三角矩阵除了和对称矩阵一样，只存储矩阵的下(上)三角中的元之外，再加上一个存储常数 c 的存储空间即可。,一个 n 阶方阵，若它的全部非零元素落在一个以对角线为中心的带状区域中，则称该矩阵为带状矩阵，或对角矩阵。这个带状区域若包含主对角线上下各 b 条对角线道上元素，那么，b 称为该带状矩阵的半带宽，或称该带状矩阵的带宽为(2b+1)。,3.带状矩阵,b 条,b 条,23,在带状矩阵中，当|i-j|b 时，aij

10、=0。该方阵共有(2b+1)n-(b+1)b 个非零元素。,D 矩阵是一个 5 阶、半带宽为 2 的带状矩阵，在其主对角线 a11、a22、a33、a44、a55 上下各有 2 条对角线，共有(2b+1)n-(b+1)b=19 个非零元素。,24,例如：,带状矩阵中最常见的是三对角带状矩阵。,25,特点：当 i=1 j=1,2 1in,j=i-1,i,i+1 i=n,j=n-1,n aij非零，其它元素均为零,1.确定存储该矩阵所需的一维向量空间的大小除第一行和最后一行只有两个元素外，其余各行均有3个非零元素，由此得到一维向量所需的空间大小为：n-2,2.确定非零元素在一维数组空间中的位置oc

11、(aij)=Loc(a11)+2(i-1)+j-1,26,三对角带状矩阵的压缩存储，以行序为主序进行存储，且只存储非零元素。其方法为,27,一般来说，当矩阵中非零元素的个数远远小于矩阵元素的总数时，称之为稀疏矩阵。假设在 mn 的矩阵中，若有 t 个元素不为零，令=t/(mn)，则称 为矩阵的稀疏因子。通常认为 25%-30%时称为稀疏矩阵。,5.3.2 稀疏矩阵的逻辑结构,1.稀疏矩阵的定义,按照压缩存储的概念，只存储稀疏矩阵的非零元素。因此，除了存储非零元素的值 aij 之外，还必须同时记下非零元素所在矩阵的行 i 号和列 j号。反之，一个三元组(i,j,aij)唯一确定了矩阵的一个非零元

12、素。因此，稀疏矩阵可以由表示非零元的三元组及其矩阵的总的行列数唯一确定。,假设以顺序存储结构表示三元组表，则可以得到稀疏矩阵的一种压缩存储方式，这种方式称之为三元组顺序表。,28,5.3.3 稀疏矩阵的存储结构,1.三元组顺序表,M=,矩阵 M 可以由三元组表,(1,3,-3)，(1,6,15)，(2,1,12)，(2,5,18)，(3,1,9)，(3,4,24)，(4,6,-7)，(6,3,14)再加上（7,6）这一对总的行列值来描述。,29,#define MAXSIZE1000/假设非零元个数的最大值为 1000,typedef struct/三元组顺序表的元素结构定义 int row,

13、;col/该非零元的行下标和列下标 ElementType e;/该非零元的值 Triple;,typedef struct/三元组顺序表存储结构定义 Triple data MAXSIZE+1;/非零元三元组表，data0 未用 int m,n,len;/矩阵的行数、列数和非零个数 TSMatrix;/三元组顺序表的类型名,30,(1)三元组顺序存储表示,M=,(a)稀疏矩阵,(b)三元组顺序表,31,(2)利用三元组顺序表实现矩阵的转置运算,将矩阵的行列值相互交互；,在这 3 点中，最关键的是第 3 条，即如何使 B.data 中的三元组以 的行（的列）为主序依次排列。,32,显然，一个稀

14、疏矩阵的转置矩阵仍是稀疏矩阵。假设 A 和 B 是 TSMatrix（三元组顺序表）类型变量，分别表示矩阵 和其转置矩阵。那么，只要做到下面 3 点就可以由 A 得到 B，实现矩阵的转置。,将每三元组中的 row 和 col 相互调换；,重排三元组之间的次序。,33,原始的三元组表,原矩阵,转置矩阵,转置的三元组表,使 b.data 中的三元组以 T 的行（M 的列）为主序依次排列的方法有如下两种：,34,方法一：按照 B.data 中三元组的次序，依次在 a.data 中找到相应的三元组进行转置。,方法二：按照 A.data 中三元组的次序进行转置，并将转置后的三元组置入 B.data 中恰

15、当的位置。,算法思想,在 A中按三元组的列域值(col)开始扫描，依序将三元组 A.data 的列域值(col)与行域值(row)进行对换，并且存入 B中。由于A是以M的行序为主序来存放每个非零元的，由此得到转置后矩阵的三元组表B恰是 以“行序为主序”。,35,按照方法一，即按照“被转置矩阵”M的三元组表A 的“列序”递增顺序进行转置。为了找到矩阵 M 的每一列中所有的非零元素，需要对其三元组 A.data 从第一行起进行扫描，方法如下：,转置的三元组表,B-data,原始的三元组表,A.data,1,2,12,1,3,9,3,1,-3,3,6,14,4,3,24,5,2,18,6,1,15,

16、6,4,-7,36,利用三元组顺序表存储实现矩阵的转置,void TransposeTSMatrix(TSMatrix A,TSMatrix*B)/采用三元组表结构，求稀疏矩阵 A 的转置矩阵 B。在程序中，int i,j,k;/j 指示 B-data 中三元组的序号，/i 指示 A.data 中三元组的序号，/k指示A 的列号（即B 的行号）,B-m=A.n;/将稀疏矩阵 A 的列数值作为其转置矩阵 B 的行数值 B-n=A.m;/将稀疏矩阵 A 的行数值作为其转置矩阵 B 的列数值 B-len=A.len;/转置矩阵 B与稀疏矩阵A的非零元个数相等,算法编(稀疏矩阵“列序”递增转置算法),

17、if(B-len0)j=1;,37,for(k=1;k=A.n;k+)for(i=1;i=A.len;i+)if(A.datai.col=k)/进行转置,return OK;/TransposeSMatrix,B-dataj.row=A.datai.col;/稀疏矩阵A的列域值成为其转置矩阵 B 的行域值,B-dataj.col=A.datai.row;/稀疏矩阵 A 的行域值成为其转置矩阵 M 的列域值,B-dataj.e=A.datai.e;/将稀疏矩阵 M 的非零元值赋给其转置矩阵 T,j+;/B-data 中三元组的序号加 1,/if(A.data)结束/if(B-len0)结束,38

18、,算法分析,一般矩阵的转置算法（经典算法）为：,39,for(col=0;col n;+col)for(row=0;row m;+row)destcolrow=sourcerowcol;时间复杂度为 O(mn)。,前面给出的求转置矩阵算法的主要工作是在 i 和 k 的两重循环中完成的，所以此算法的时间复杂度为 O(A.nA.len)即和矩阵 A 的列数和非零元的个数的乘积成正比。,40,当矩阵非零元素的位置或个数经常变动时，就不易采用顺序存储结构表示三元组的线性表。例如，在进行“将矩阵 B 加到矩阵 A 上”的操作时，由于非零元素的插入或删除将会引起 A.data 中元素的大量移动。为此，对这

19、种类型的矩阵，采用链式存储结构表示三元组的线性表更为恰当。,41,2.十字链表,(1)稀疏矩阵的十字链表存储表示,矩阵中非零元的行号 row；矩阵中非零元的列号 col；矩阵中非零元的值 e；向右域 right，用以链接同一行中下一个非零元；向下域 down，用以链接同一列中下一个非零元。,42,非零元行号,非零元列号,非零元的值,向下域,向右域,在链表中，矩阵的非零元素可用如下结点表示：,typedef struct OLNode/结点定义 int row,col;/该非零元的行和列下标 ElementType value;/该非零元的值 struct OLNode*right,*down;

20、/该非零元所在的行表和列表的后继链域 OLNode;*Olink;,typedef struct/十字链表定义 int m,n,len;/稀疏矩阵行数、列数和非零元个数 Olink*row_head,*col_head;/行和列链表头指针向量，由 CreateSMatrix 分配 CrossList;/十字链表存储结构的类型名,43,M.col_head,M.row_head,44,CreateSMatrix_OL(CrossList*M)/创建稀疏矩阵 M。采用十字链表存储表示。,(2)利用十字链表实现创建稀疏矩阵的运算,if(!(M-row_head=(Olink*)malloc(m+1)

21、*sizeof(Olink)exit(OVERFLOW);,if(!(M-col_head=(Olink*)malloc(n+1)*sizeof(Olink)exit(OVERFLOW);,if(M)free(M);scanf(,45,算法编写,for(scanf(,p-row=i;/生成新结点的行号域 p-col=j;/生成新结点的列号域 p-value=e;/生成新结点的值域,46,M-row_head=NULL;/初始化行头指针向量；令各行链表为空链表 M-col_head=NULL;/初始化列头指针向量；令各列链表为空链表,if(M-row_headi=NULL)M-row_headi

22、=p;p-right=NULL;,else for(q=M-row_headi;(q-right)/完成行插入,else if(M-row_headi-col j)/寻找在行表中的插入位置 p-right=M-row_headi;M-row_headi=p;,47,if(M-col_headj=NULL)M_col_headj=p;p-down=NULL;,else for(q=M-col_headj;(q-down)/完成列插入,else if(M-col_headj-row i)/寻找在列表中的插入位置 p-down=M-row_headj;M-col_headj=p;,/for 结束 r

23、eturn OK;/CreateSMatrix_OL,48,M-col_head,M-row_head,(1)输入(1,1,3),1,1,3,p,(2)输入(1,3,5),p,1,3,5,q,(3)输入(1,4,9),1,4,9,p,q,(4)输入(3,1,2),3,1,2,p,q,49,(5)输入(2,3,4),2,3,4,q,(6)输入(2,2,8),q,创建稀疏矩阵 M 的十字链表,if(M.rheadi=NULL)M.rheadi=p;p-right=NULL;,for(q=M-col_headi;(q-down),if(M-row_headi-j j)p-right=M-row_he

24、adi;M-row_headi=p;,if(M-col_headj=NULL)M-col_headj=p;p-down=NULL;,p,q,p,2,2,8,if(M-col_headj=NULL)M-col_headj=p;p-down=NULL;,for(q=M-row_headi;(q-right),if(M-col_headj=NULL)M-col_headj=p;p-down=NULL;,for(q=M-row_headi;(q-right),if(M-col_headj=NULL)M-col_headj=p;p-down=NULL;,if(M-row_headi=NULL)M-row

25、_headi=p;p-right=NULL;,for(q=M-col_headi;(q-down),if(M-row_headi=NULL)M-row_headi=p;p-right=NULL;,对于一个 m 行 n 列，并且有 t 个非零元的稀疏矩阵，CreateSMatrix_OL 算法执行时间为 O(ts)，其中 s=maxm,n。,这是因为：每建立一个非零元的结点时都需要寻查它在行表和列表中的插入位置，此算法对非零元输入的先后次序没有任何要求。,反之，若按以行序为主序的次序依次输入三元组，即可以将建立十字链表表示的算法改写成 O(t)数量级的（t 为非零元个数）的算法。,算法分析,50

26、,广义表(generalized list)是线性表的推广，有时也称为列表（lists，用复数形式以示与统称的表 list 的区别）。广泛地应用于人工智能等领域的 LISP（表处理语言），把广义表作为基本的数据结构，就连程序也表示为一系列的广义表。,51,广义表的逻辑结构,和数组一样，广义表也可以看成是线性表在下述含义上的扩展：表中的数据元素本身也是一种数据结构。,52,广义表的存储结构,53,5.4.1 广义表的逻辑结构,广义表一般记作：GL=(a1,a2,an),其中：,n 是广义表 GL 的长度；,ai 可以是单个元素，也可以是广义表，分别称为广义表 GL 的原子和子表，习惯上用大写字母

27、表示广义表的名称，用小写字母表示原子的名称。,GL是广义表(a1,a2,an)的名称；,1.广义表的定义,54,例5-1 A=()，A 是一个空表，它的长度为零。,例5-2 B=(e)，B 只有一个原子 e，它的长度为 1。,例5-3 C=(a,(b,c,d)，C 的长度为 2，两个元素分别为原子 a 和子表(b,c,d)。,例5-4 D=(A,B,C)，D 的长度为 3，三个元素分别为 A、B 和 C，都是广义表。显然，将上面所述三个子表的值代入以后，则有 D=(),(e),(a,(b,c,d)。,例5-5 E=(a,E)，这是一个递归表，它的长度为 2，E 相当于一个无限的广义表 E=(a

28、,(a,(a,)。,55,2.广义表的三个重要结论,从上述定义和例子推出如下广义表的三个重要结论,(1)广义表的元素可以是子表，而子表的元素还可以是子表，。由此，广义表是一个多层次结构。,(2)广义表可以为其他广义表所共享。例如在上述例子中，广义表 A、B 和 C 为 D 的子表，则在 D 中可以不必列出广义表的值，而是通过子表的名称引用。,(3)广义表可以是一个递归表，即广义表也可以是其本身的一个子表。例如广义表 E 就是一个递归的表。,56,表示广义表,表示原子,57,和线性表相类似，可以对广义表进行的操作有查找、插入、删除和取表元素等。由于广义表在结构上较线性表复杂的多，因此，广义表操作

29、的实现也不如线性表简单。在这些操作中，最重要的两个基本操作是：,(1)取广义表表头 GetHead：表中的第一个元素为此表的表头。(2)取广义表表尾 GetTail：表中除第一个元素外的其余元素组成的表为此表的表尾。,58,3.广义表的两个基本操作,(1)A=()(2)B=(e)(3)C=(a,(b,c,d)(4)D=(A,B,C)(5)E=(a,E),GetHead(B)=eGetTail(B)=()GetHead(C)=aGetTail(C)=(b,c,d)GetHead(D)=AGetTail(D)=(B,C)由于(B,C)为非空广义表，令F=(B,C)，则可以继续分解得到：GetHea

30、d(F)=BGetTail(F)=(C),任何一个非空广义表的表头可能是原子，也可能是广义表；而其表尾必定是广义表。例如，广义表如下：,对定义表 B，C，D 取表头和取表尾的操作结果：,59,60,由于广义表（a1,a2,an）中的数据元素可以具有不同的结构（或是原子，或是广义表），因此很难用顺序结构表示，通常采用链式存储结构。在这种结构中，需要两种结构的结点。,61,5.4.2 广义表的存储结构,标志域,头指针域,指向下一个结点,(1)表结点：用以表示广义表。由 3 个域组成：标志域、指示表头的指针域和指示下一个元素结点的指针域。,(2)原子结点：用以表示原子。由 3 个域组成：标志域、值域

31、及指示下一个元素结点的指针域。,指向下一个结点,标志域,值域,62,广义表的扩展线性链表存储结构,typedef enum ATOM,LIST ElemTag;/ATOM=0:原子；LIST=1:子表,typedef struct GLNode ElemTag tag;/公共部分，用于区分原子结点和表结点,union/原子结点和表结点的联合部分 AtomType atom;/原子结点的值域 struct GLNode*hp;/表结点的表头指针;,struct GLNode*tp;/相当于线性链表的 next，指向下一个元素结点,GLNode,*GList;/广义表扩展线性链表类型名,63,(1)A=(),例：,A,B,C,D,E,(2)B=(e),(3)C=(a,(b,c,d),(4)D=(A,B,C),(5)E=(a,E),64,