数据结构第九讲精.ppt

《数据结构第九讲精.ppt》由会员分享，可在线阅读，更多相关《数据结构第九讲精.ppt（44页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构第九讲数据结构第九讲第1页，本讲稿共44页数组数组1 数组的定义和基本运算数组的定义和基本运算 数组的特点是每个数据元素可以又是一个线性表结数组的特点是每个数据元素可以又是一个线性表结构。因此，数组结构可以简单地定义为：若线性表中的构。因此，数组结构可以简单地定义为：若线性表中的数据元素为非结构的简单元素，则称为一维数组，即为数据元素为非结构的简单元素，则称为一维数组，即为向量向量；若一维数组中的数据元素又是一维数组结构，则；若一维数组中的数据元素又是一维数组结构，则称为二维数组；依次类推，若二维数组中的元素又是一称为二维数组；依次类推，若二维数组中的元素又是一个一维数组结构，则称作三

2、维数组。个一维数组结构，则称作三维数组。结论：线性表结构是数组结构的一个特例，而数组结论：线性表结构是数组结构的一个特例，而数组结构又是线性表结构的扩展。举例：结构又是线性表结构的扩展。举例：第2页，本讲稿共44页第3页，本讲稿共44页 其中，其中，A是数组结构的名称，整个数组元素可以看是数组结构的名称，整个数组元素可以看成是由成是由m个行向量和个行向量和n个列向量组成，其元素总数为个列向量组成，其元素总数为mn。在。在C语言中，二维数组中的数据元素可以表示成语言中，二维数组中的数据元素可以表示成a表达式表达式1表达式表达式2，表达式，表达式1和表达式和表达式2被称为下标被称为下标表达式，比如

3、，表达式，比如，aij。数组结构在创建时就确定了组成该结构的行向量数组结构在创建时就确定了组成该结构的行向量数目和列向量数目，因此，在数组结构中不存在插入、数目和列向量数目，因此，在数组结构中不存在插入、删除元素的操作。删除元素的操作。二维数组结构的基本操作：二维数组结构的基本操作：（1）给定一组下标，修改该位置元素的内容给定一组下标，修改该位置元素的内容 Assign(A,item,index1,index2)（2）给定一组下标，返回该位置的元素内容）给定一组下标，返回该位置的元素内容 Value(A,item,index1,index2)第4页，本讲稿共44页2 数组的存储结构数组的存储结

4、构 从理论上讲，数组结构也可以使用两种存储结构，从理论上讲，数组结构也可以使用两种存储结构，即顺序存储结构和链式存储结构。然而，由于数组结即顺序存储结构和链式存储结构。然而，由于数组结构没有插入、删除元素的操作，所以使用顺序存储结构没有插入、删除元素的操作，所以使用顺序存储结构更为适宜。换句话说，一般的数组结构不使用链式构更为适宜。换句话说，一般的数组结构不使用链式存储结构。存储结构。组成数组结构的元素可以是多维的，但存储数据组成数组结构的元素可以是多维的，但存储数据元素的内存单元地址是一维的，因此，在存储数组结元素的内存单元地址是一维的，因此，在存储数组结构之前，需要解决将多维关系映射到一维

5、关系的问题。构之前，需要解决将多维关系映射到一维关系的问题。举例：举例：第5页，本讲稿共44页假设每个元素占L个存储单元，下面求地址公式第6页，本讲稿共44页 第0行 第1行 第m-1行 第0列 第1列 第m-1列LOC(i,j)=LOC(0,0)+(n*i+j)*LLOC(i,j)=LOC(0,0)+(m*j+i)*L第7页，本讲稿共44页 3 3矩阵的压缩存储矩阵的压缩存储 矩阵是在很多科学与工程计算中遇到的数学模型。在矩阵是在很多科学与工程计算中遇到的数学模型。在数学上，矩阵是这样定义的：它是一个由数学上，矩阵是这样定义的：它是一个由mn个元素排成个元素排成的的m行（横向）行（横向）n列

6、（纵向）的表。下面就是一个矩阵：列（纵向）的表。下面就是一个矩阵：第8页，本讲稿共44页mmn n的矩阵的矩阵的矩阵的矩阵第9页，本讲稿共44页4 4 特殊矩阵特殊矩阵 所谓所谓特殊矩特殊矩阵就是元素值的排列具有一定规律的矩阵就是元素值的排列具有一定规律的矩阵。常见的这类矩阵有：对称矩阵、下（上）三角矩阵、阵。常见的这类矩阵有：对称矩阵、下（上）三角矩阵、对角线矩阵等等。对角线矩阵等等。对称矩阵的特点是对称矩阵的特点是aij=aji，比如，下面就是一个对称，比如，下面就是一个对称矩阵：矩阵：第10页，本讲稿共44页第11页，本讲稿共44页 下（上）三角矩阵的特点是以主对角线为界的上下（上）三角

7、矩阵的特点是以主对角线为界的上（下）半部分是一个固定的值，下（上）半部分的元（下）半部分是一个固定的值，下（上）半部分的元素值没有任何规律。比如，下面是一个下三角矩阵：素值没有任何规律。比如，下面是一个下三角矩阵：第12页，本讲稿共44页 对角矩阵的特点是所有的非零元素都集中在以主对角矩阵的特点是所有的非零元素都集中在以主对角线为中心的带状区域中。比如，下面就是一个对角线为中心的带状区域中。比如，下面就是一个3阶阶对角矩阵：对角矩阵：第13页，本讲稿共44页压缩：为多个值相同的元只分配一个存储空间，对零元不分配空间.对于这些特殊矩阵，应该充分利用元素值的分布规律，将其进行压缩存储。选择压缩存储

8、的方法应遵循两条原则：一是尽可能地压缩数据量，二是压缩后仍然可以比较容易地进行各项基本操作。三种特殊矩阵的压缩方法：（1）对称矩阵 对称矩阵的特点是aij=aji。一个nn的方阵，共有n2个元素，而实际上在对称矩阵中有n(n-1)/2个元素可以通过其他元素获得。第14页，本讲稿共44页压缩的方法是首先将二维关系映射成一维关系，并只存储其中必要的n(n+1)/2个（主对角线和下三角）元素内容，这些元素的存储顺序以行行为主序。举例：假设定义一个数组型变量：int A10;第15页，本讲稿共44页设 k是对称矩阵位于（i，j）位置的元素在一维数组中的存放位置。注意第一元素放在a0。Ai,j,前i-1

9、行元素的个数为i(i-1)/2,在第i行为第j个的次序为j，而A1,1放在a0,所以k=i(i-1)/2+j-1,(i=j),Ai,j,当ij时，由于对称性，Ai,j=Aj,i,即看Aj,i放在什么位置，所以有上面的知识得到：k=j(j-1)/2+i-1,(ij),第16页，本讲稿共44页(2)下（上）三角矩阵 下三角矩阵的压缩存储与上面讲述的对称矩阵的压缩存储一样，只是将上三角部分的常量值存储在0单元，下三角和主对角上的元素从1号单元开始存放。举例：第17页，本讲稿共44页设设 k是对称矩阵位于（是对称矩阵位于（i，j）位置的元素在一维数组中的存放位置。）位置的元素在一维数组中的存放位置。对

10、于任意的（对于任意的（i，j），在一维数组中的存放位置可利用下列公式求得：），在一维数组中的存放位置可利用下列公式求得：第18页，本讲稿共44页（3）对角矩阵我们以三阶对角矩阵为例讨论一下它的压缩存储方法。对于对角矩阵，压缩存储的主要思路是只存储非零元素。这些非零元素按以行为主序的顺序，从下标为1 的位置开始依次存放在一维数组中，而0位置存放数值0。第19页，本讲稿共44页 下面我们讨论一下对于任意给定的（i，j），求得在一维数组中存储位置k的方法。注：该矩阵除第一行和最后一行外，每行有3个元素。前i-1行元素的个数：3*(i-1)-1;第i行，第j个位置在第i行的次序为：j-i+2故：k=3

11、*(i-1)-1+j-i+2=3*(i-1)+j-i+1,当 i-1=j=i+1第20页，本讲稿共44页 2.2.稀疏矩阵的压缩存储稀疏矩阵的压缩存储 若一个若一个mn的矩阵含有的矩阵含有t个非零元素，且个非零元素，且t远远小于远远小于m*n，则我们将这个矩阵称为，则我们将这个矩阵称为稀疏矩阵稀疏矩阵。举例：。举例：注：通常：注：通常：t/(m*n)=0.05时称为稀疏矩阵时称为稀疏矩阵第21页，本讲稿共44页 稀疏矩阵的压缩存储方法稀疏矩阵的压缩存储方法三元组表示法。三元组表示法。矩阵中的每个元素都是由行序号和列序号唯一确定的。矩阵中的每个元素都是由行序号和列序号唯一确定的。因此，我们需要用

12、三项内容表示稀疏矩阵中的每个非零元素因此，我们需要用三项内容表示稀疏矩阵中的每个非零元素，即形式为：，即形式为：(i,j,value)其中，其中，i表示行序号，表示行序号，j表示列序号，表示列序号，value表示非零元素表示非零元素的值，通常将它称为三元。我们将稀疏矩阵中的所有非零元的值，通常将它称为三元。我们将稀疏矩阵中的所有非零元素用这种三元的形式表示，并将它们按以行为主的顺序存放素用这种三元的形式表示，并将它们按以行为主的顺序存放在一个一维数组中，就形成了我们所说的三元组表示法。在一个一维数组中，就形成了我们所说的三元组表示法。第22页，本讲稿共44页注：稀疏矩阵可由表示非零元的三元组及

13、其行列数唯一确定。稀疏矩阵可由表示非零元的三元组及其行列数唯一确定。例如（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的另一种描述第23页，本讲稿共44页/-稀疏矩阵的三元组顺序表存储表示#define MAXSIZE 125000/最大的非零元素个数typedef struct int i,j;/行序号、列序号 ElemType e;/非零元素值Triple;typedef struct Triple dataMAXSIZE+1;/非

14、零元素的三元组表，data0未用 int mu,nu,tu;/稀疏矩阵的行数、列数及非零元素个数TSMatrix;第24页，本讲稿共44页那么求矩阵的转置？假设a和b是TSMatrix型的变量，分别表示矩阵M和T,如何a得到b?前两步很容易实现，关键是第三步，我们需要做如下三步：（1）矩阵的行列值互换；（2）将每个三元组中的i和j相互调换；（3）重排三元组之间的次序实现矩阵的转置；有两种处理办法：（1）按照b.data中三元组的次序依次在a.data中找到相应的三元组进行转置，即，按照矩阵M的列序来进行转置。其算法如下：第25页，本讲稿共44页Status TransposeSMatrix(T

15、SMatrix M,TSMatrix&T)/算法5.1 /采用三元组顺序表存储表示，求稀疏矩阵M的转置矩阵T int p,q,col;T.mu=M.nu;T.nu=M.mu;T.tu=M.tu;/第1，2步if(T.tu)q=1;for(col=1;col=M.nu;+col)/第3步 for(p=1;p=M.tu;+p)if(M.datap.j=col)T.dataq.i=M.datap.j;T.dataq.j=M.datap.i;T.dataq.e=M.datap.e;+q;第26页，本讲稿共44页 return OK;/TransposeSMatrix注：该算法仅适用于注：该算法仅适用于

16、tumu*nu的情况的情况（2）按照a.data中的三元组的次序进行转置，并将转置后的三元组置入b中恰当的位置。提示：如果能预先确定矩阵M的每一列（T的每一行）的第一个非零元在b.data中的应有位置，则在对a.data中的三元组依次作转置时，便可直接放到b.data中的恰当位置，因此在转置前，映先求得M的每一列中非零元的个数，进而求得每一列的第一个非零元在b.data中的应有位置。第27页，本讲稿共44页设num和cpot两个向量，numcol表示矩阵M中第col列的非零元的个数，cpotcol指示M中第col列的第一个非零元在b.data中的恰当位置，显然有：cpot1=1;cpotcol

17、=cpotcol-1+numcol-1;2=col=a.nu;第28页，本讲稿共44页前面矩阵M，num和cpot的值如下所示：第29页，本讲稿共44页Status FastTransposeSMatrix(TSMatrix M,TSMatrix&T)/采用三元组顺序表存储表示，求稀疏矩阵M的转置矩阵T int col,t,p,q;int num20,cpot20;T.mu=M.nu;T.nu=M.mu;T.tu=M.tu;if(T.tu)for(col=1;col=M.nu;+col)numcol=0;for(t=1;t=M.tu;+t)/求 M 中每一列所含非零元的个数 +numM.dat

18、at.j;cpot1=1;/求 M 中每一列的第一个非零元在 b.data 中的序号 for(col=2;col=M.nu;+col)cpotcol=cpotcol-1+numcol-1;for(p=1;p=M.tu;+p)col=M.datap.j;q=cpotcol;T.dataq.i=M.datap.j;T.dataq.j=M.datap.i;T.dataq.e=M.datap.e;+cpotcol;/for /if return OK;/FastTransposeSMatrix该转置方法称为快速转置，详细算法见课本P100第30页，本讲稿共44页注：三元顺序表又称为有序的双下表法，其特

19、点是：非零元在表中按行序有序存储，因此便于进行依行顺序处理的矩阵运算。对于稀疏矩阵的表示还有：行逻辑链接的顺序表行逻辑链接的顺序表和十十字链表字链表第31页，本讲稿共44页一、选择题1.设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（）。A.13 B.33 C.18 D.403.设有数组Ai,j，数组的每个元素长度为3字节，i的值为1 到8，j的值为1 到10，数组从内存首地址BA开始顺序存放，当用以列为主存放时，元素A5，8的存储首地址为()。A.BA+141 B.BA+180 C.BA+222 D.B

20、A+2254.假设以行序为主序存储二维数组A=array1.100，1.100，设每个数据元素占2个存储单元，基地址为10，则LOC5，5=（）。A.808 B.818 C.1010 D.1020答案：1 B,3 B,4B第32页，本讲稿共44页2.有一个二维数组A1:6，0:7 每个数组元素用相邻的6个字节存储，存储器按字节编址，那么这个数组的体积是（）个字节。假设存储数组元素A1，0的第一个字节的地址是0，则存储数组A的最后一个元素的第一个字节的地址是（）。若按行存储，则A2，4的第一个字节的地址是（）。若按列存储，则A5，7的第一个字节的地址是（）。就一般情况而言，当（）时，按行存储的A

21、I，J地址与按列存储的AJ，I地址相等。供选择的答案：-：A12 B.66 C.72 D.96 E.114 F.120 G.156 H.234 I.276 J.282 K.283 L.288：A行与列的上界相同 B.行与列的下界相同 C.行与列的上、下界都相同 D.行的元素个数与列的元素个数相同 答案：2.1L，2.2J，2.3C，2.4I，2.5C第33页，本讲稿共44页5.数组A0.5,0.6的每个元素占五个字节，将其按列优先次序存储在起始地址为1000的内存单元中，则元素A5，5的地址是()。A.1175 B.1180 C.1205 D.12106.有一个二维数组A0:8,1:5,每个数

22、组元素用相邻的4个字节存储，存储器按字节编址，假设存储数组元素A0,1的第一个字节的地址是0，存储数组A的最后一个元素的第一个字节的地址是（）。若按行存储，则A3,5和 A5,3的第一个字节的地址是（）和（）。若按列存储，则A7,1和A2,4的第一个字节的地址是（）和（）。-:A.28 B.44 C.76 D.92 E.108 F.116 G.132 H.176 I.184 J.188答案：5.A，6.1H，6.2C，6.3E，6.4A，6.5F第34页，本讲稿共44页7.将一个A1.100，1.100的三对角矩阵，按行优先存入一维数组B1298中，A中元素A6665（即该元素下标i=66，j

23、=65），在B数组中的位置K为（）。供选择的答案：A.198 B.195 C.1979.二维数组A的每个元素是由6个字符组成的串，其行下标i=0,1,8,列下标j=1,2,10。若A按行先存储，元素A8,5的起始地址与当A按列先存储时的元素（）的起始地址相同。设每个字符占一个字节。A.A8,5 B.A3,10 C.A5,8 D.A0,910.若对n阶对称矩阵A以行序为主序方式将其下三角形的元素(包括主对角线上所有元素)依次存放于一维数组B1.(n(n+1)/2中，则在B中确定aij（inext D.j=rj-next17.对稀疏矩阵进行压缩存储目的是（）。A便于进行矩阵运算 B便于输入和输出

24、C节省存储空间 D降低运算的时间复杂度答案：14.B，15.B，16.A，17.C第38页，本讲稿共44页二、填空题1.数组的存储结构采用_存储方式。2.设二维数组A-20.30,-30.20,每个元素占有4 个存储单元,存储起始地址为200.如按行优先顺序存储,则元素 A25,18的存储地址为_；如按列优先顺序存储,则元素A-18,-25的存储地址为_。3.设数组a1.50,1.80的基地址为2000，每个元素占2个存储单元，若以行序为主序顺序存储，则元素a45,68的存储地址为_;若以列序为主序顺序存储，则元素a45,68的存储地址为_。4.将整型数组A1.8，1.8按行优先次序存储在起始

25、地址为1000的连续的内存单元中，则元素A7，3的地址是：_。5.二维数组a456（下标从0开始计，a有4*5*6个元素），每个元素的长度是2，则a234的地址是_。(设a000的地址是1000,数据以行为主方式存储)第39页，本讲稿共44页6.设有二维数组A0.9,0.19,其每个元素占两个字节，第一个元素的存储地址为100，若按列优先顺序存储，则元素A6,6存储地址为_。7.已知数组A0.9,0.9的每个元素占5个存储单元，将其按行优先次序存储在起始地址为1000的连续的内存单元中，则元素A6，8的地址为_。8.已知二维数组A1.10，0.9中每个元素占4个单元，在按行优先方式将其存储到起

26、始地址为1000的连续存储区域时，A5，9的地址是：_。9.用一维数组B与列优先存放带状矩阵A中的非零元素Ai,j(1in,i-2ji+2),B中的第8个元素是A 中的第_（1）_行，第_（2）_列的元素。11设n行n列的下三角矩阵A已压缩到一维数组B1.n*（n+1）/2中，若按行为主序存储，则Ai,j对应的B中存储位置为_。第40页，本讲稿共44页10.设数组A0.8,1.10,数组中任一元素Ai,j均占内存48个二进制位，从首地址2000开始连续存放在主内存里，主内存字长为16位，那么（l）存放该数组至少需要的单元数是_;（2）存放数组的第8列的所有元素至少需要的单元数是_;（3）数组按

27、列存储时，元素A5,8的起始地址是_。12.n阶对称矩阵a满足aij=aji,i,j=1.n,，用一维数组t存储时，t的长度为_(1)_，当i=j，aij=t(2),ij,aij=t(3),ij,aij=t(4)。13己知三对角矩阵A1.9,1.9的每个元素占2个单元，现将其三条对角线上的元素逐行存储在起始地址为1000的连续的内存单元中，则元素A7,8的地址为_。第41页，本讲稿共44页14.设有一个10阶对称矩阵A采用压缩存储方式（以行为主序存储：a1,1=1），则a8,5 的地址为_。15.所谓稀疏矩阵指的是_。16.对矩阵压缩是为了_。17.上三角矩阵压缩的下标对应关系为：_。18.假

28、设一个15阶的上三角矩阵A按行优先顺序压缩存储在一维数组B中，则非零元素A9,9在B中的存储位置k=_。（注：矩阵元素下标从1开始）第42页，本讲稿共44页参考答案：1.顺序存储结构 2.（1）9572（2）1228 3.（1）9174（2）8788 4.11005.1164 公 式：LOC(aijk)=LOC(a000)+v2*v3*(i-c1)+v3*(j-c2)+(k-c3)*l(l为每个元素所占单元数)6.232 7.1340 8.1196 9.第1行第3列10.(1)270(2)27(3)2204 11.i(i-1)/2+j(1=i,j=n)12.(1)n(n+1)/2(2)i(i+1)/2(或j(j+1)/2)(3)i(i-1)/2+j(4)j(j-1)/2+i(1=i,j=n)13.1038 三对角矩阵按行存储：k=2(i-1)+j(1=i,j=n)14.33(k=i(i-1)/2+j)(1=i,j=n)15.非零元很少(tm*n)且分布没有规律 16.节省存储空间。第43页，本讲稿共44页17.上三角矩阵中，主对角线上第r(1rn)行有n-r+1个元素，aij所在行的元素数是j-i+1。所以，元素在一维数组的下标k和二维数组下标关系:k=(i-1)*(2n-i+2)/2+(j-i+1)=(i-1)(2n-i)/2+j (ij)18.93第44页，本讲稿共44页