最新【考研计算机专业课】武汉大学数据结构PPT课件 第5章数组(共48张PPT课件).pptx

《最新【考研计算机专业课】武汉大学数据结构PPT课件 第5章数组(共48张PPT课件).pptx》由会员分享，可在线阅读，更多相关《最新【考研计算机专业课】武汉大学数据结构PPT课件 第5章数组(共48张PPT课件).pptx（48页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第第5章章 数组和数组和稀疏稀疏(xsh)矩阵矩阵 5.1 数组数组5.2 稀疏稀疏(xsh)矩阵矩阵数据结构数据结构(sh j ji u)基础第基础第2章章2.5和和2.6节节p5877第一页，共四十八页。5.1.1 数组的基本概念数组的基本概念 从逻辑结构上看，数组从逻辑结构上看，数组A是是n（n1）个相同类型数据元素）个相同类型数据元素a1，a2，an构成的有限序列，其逻辑表示为：构成的有限序列，其逻辑表示为： A=（a1，a2，an） 其中，其中，ai（1in）表示数组）表示数组A的第的第i个元素。个元素。 一个二维数组可以看作是每个数据元素都是相同类型的一维数一个二维数组可以看作是每

2、个数据元素都是相同类型的一维数组的一维数组。以此类推，任何多维数组都可以看作一个线性表，组的一维数组。以此类推，任何多维数组都可以看作一个线性表，这时线性表中的每个数据元素也是一个线性表。多维数组是线性表这时线性表中的每个数据元素也是一个线性表。多维数组是线性表的推广。的推广。 推广到推广到d（d3）维数组，不妨把它看作一个由）维数组，不妨把它看作一个由d-1维数组作维数组作为数据元素的线性表；或者这样理解，它是一种较复杂的线性表为数据元素的线性表；或者这样理解，它是一种较复杂的线性表结构，由简单结构，由简单(jindn)的数据结构即线性表的数据结构即线性表辗转合成而得。辗转合成而得。第二页，

3、共四十八页。5.1.2 数组的存储结构数组的存储结构(jigu) 在一维数组中在一维数组中,一旦一旦a1的存储地址的存储地址LOC(a1)确定确定,并假设每个数据并假设每个数据元素占用元素占用k个存储单元个存储单元,则任一数据元素则任一数据元素ai的存储地址的存储地址LOC(ai)就可由就可由以下公式求出：以下公式求出： LOC(ai)=LOC(a1)+(i-1)*k (0in) 上式说明上式说明,一维数组中任一数据元素的存储地址可直接计算得到一维数组中任一数据元素的存储地址可直接计算得到,即一维数组中任一数据元素可直接存取即一维数组中任一数据元素可直接存取,因此因此,一维数组是一种随机一维数

4、组是一种随机存储结构。同样存储结构。同样,二维及多维数组也满足随机存储特性。二维及多维数组也满足随机存储特性。第三页，共四十八页。nmmmnnnmaaaaaaaaaA,2,1 ,22,21 ,2, 12, 11 , 1.对于对于(duy)一个一个m行行n列的二维数组列的二维数组Amn,有：有： 将将Am*n简记为简记为A,可以可以(ky)看成是这样的一维数组：看成是这样的一维数组： A=(a1,a2,ai,am)其中，其中，ai=(ai,1,ai,2,ai,n) (1im)。第四页，共四十八页。 对于二维数组来说对于二维数组来说,由于计算机的存储结构是线性的由于计算机的存储结构是线性的,如何用

5、线如何用线性的存储结构存放二维数组元素就有一个行列次序排放问题。性的存储结构存放二维数组元素就有一个行列次序排放问题。 以行序为主序的存储方式：即先存储第以行序为主序的存储方式：即先存储第1行行,然后紧接着存然后紧接着存储第储第2行行,最后存储第最后存储第m行。此时行。此时(c sh),二维数组的线性排列次序二维数组的线性排列次序为：为： a1,1,a1,2,a1,n,a2,1,a2,2,a2,n,am,1,am,2,am,n第五页，共四十八页。 对一个已知以行序为主序的计算机系统中对一个已知以行序为主序的计算机系统中,当二维数组第一个数当二维数组第一个数据元素据元素a1,1的存储地址的存储地

6、址(dzh)LOC(a1,1)和每个数据元素所占用的存储单和每个数据元素所占用的存储单元元k确定后确定后,则该二维数组中任一数据元素则该二维数组中任一数据元素ai,j的存储地址可由下式确定：的存储地址可由下式确定： LOC(ai,j)=LOC(a1,1)+(i-1)*n+(j-1)*k 其中其中n为列数。为列数。第六页，共四十八页。 同理可推出在以列序为主序的计算机系统中有：同理可推出在以列序为主序的计算机系统中有： LOC(ai,j)=LOC(a1,1)+(j-1)*m+(i-1)*k 其中其中(qzhng)m为行数。为行数。第七页，共四十八页。 例例5.1 按行优先顺序和按列优先顺序列出四

7、维按行优先顺序和按列优先顺序列出四维(s wi)数组数组A2222所有元素在内存中的存储次序。所有元素在内存中的存储次序。第八页，共四十八页。 解：解： 按行优先按行优先(yuxin)的存储次序的存储次序: A0000, A0001, A0010, A0011, A0100, A0101, A0110, A0111, A1000, A1001, A1010, A1011, A1100, A1101, A1110, A1111第九页，共四十八页。 按列优先按列优先(yuxin)(yuxin)的存储次序的存储次序: : A0000, A1000, A0100, A1100, A0010, A101

8、0, A0110, A1110, A0001, A1001, A0101, A1101, A0011, A1011, A0111, A1111第十页，共四十八页。 例例5.2 对二维数组对二维数组float a54计算：计算： （1）数组）数组a中的数组元素数目；中的数组元素数目； （2）若数组）若数组a的起始地址为的起始地址为2000,且每个数组元素长度且每个数组元素长度(chngd)为为32位位(即即4个字节个字节),数组元素数组元素a32的内存地址。的内存地址。 第十一页，共四十八页。 解：该数组的元素数目共有解：该数组的元素数目共有5*4=20个。个。 又由于又由于(yuy)C语言采用

9、行序为主序的存储方式语言采用行序为主序的存储方式,则有：则有： LOC(a3,2)=LOC(a0,0)+(i*n+j)*k =2000+(3*4+2)*4=2056第十二页，共四十八页。 几种几种(j zhn)特殊矩阵：特殊矩阵：（1）对称矩阵）对称矩阵（2）上三角矩阵下三角矩阵）上三角矩阵下三角矩阵（3）对角矩阵）对角矩阵它们都是方阵它们都是方阵,即行数和列数相同。即行数和列数相同。第十三页，共四十八页。 1. 对称矩阵的压缩存储对称矩阵的压缩存储 若一个若一个n阶方阵阶方阵Ann中的元素满足中的元素满足ai,j=aj,i(0i,jn-1),则称则称其为其为n阶阶对称矩阵对称矩阵。 由于对称

10、矩阵中的元素关于主对角线对称由于对称矩阵中的元素关于主对角线对称,因此因此(ync)在存储时可在存储时可只存储对称矩阵中上三角或下三角中的元素只存储对称矩阵中上三角或下三角中的元素,使得对称的元素共享一使得对称的元素共享一个存储空间。这样个存储空间。这样,就可以将就可以将n2个元素压缩存储到个元素的空间中。个元素压缩存储到个元素的空间中。不失一般性不失一般性,我们以行序为主序存储其下三角我们以行序为主序存储其下三角(包括对角线包括对角线)的元素。的元素。第十四页，共四十八页。 n2个元素个元素(yun s) n(n+1)/2个元素个元素 A0.n-1,0.n-1 B0.n(n+1)/2-1 a

11、ij bk21)i(i k=+ j ij+ i ij21)j(j 第十五页，共四十八页。上三角上三角(snjio)矩阵：矩阵： 2)12(* ini2)1( nnk=+ j i ij时时ij时时第十六页，共四十八页。下三角下三角(snjio)矩阵：矩阵： jii2)1(* 2)1( nnk= ij时时ij时时第十七页，共四十八页。 2. 对角矩阵的压缩存储对角矩阵的压缩存储 若一个若一个n阶方阵阶方阵A满足其所有非零元素都集中在以主对角线为中心满足其所有非零元素都集中在以主对角线为中心的带状区域的带状区域(qy)中中,则称其为则称其为n阶对角矩阵阶对角矩阵。其主对角线上下方各有其主对角线上下方

12、各有b条次对角线条次对角线,称称b为矩阵半带为矩阵半带宽宽,(2b+1)为矩阵的带宽。对于半带宽为为矩阵的带宽。对于半带宽为b(0b(n-1)/2)的对角的对角矩阵矩阵,其其|i-j|b的元素的元素ai,j不为零不为零,其余元素为零。其余元素为零。下图所示是半带宽为下图所示是半带宽为b的对角矩阵示意图。的对角矩阵示意图。第十八页，共四十八页。 . b条条 b条条 0 0 . 半带宽半带宽(di kun)(di kun)为为b b的对角矩阵的对角矩阵 第十九页，共四十八页。当当b1时称为三对角时称为三对角(du jio)矩矩阵。阵。其压缩地址计算公式如下：其压缩地址计算公式如下： k=2i+j

13、A B aij bk第二十页，共四十八页。思考题：思考题：为什么采用压缩存储，需要解决为什么采用压缩存储，需要解决(jiju)什么问题？什么问题？第二十一页，共四十八页。5.2 稀疏矩阵稀疏矩阵 一个一个(y )阶数较大的矩阵中的非零元素个数阶数较大的矩阵中的非零元素个数s相对于矩阵相对于矩阵元素的总个数元素的总个数t十分小时十分小时,即即st时时,称该矩阵为稀疏矩阵。例称该矩阵为稀疏矩阵。例如一个如一个(y )100100的矩阵的矩阵,若其中只有若其中只有100个非零元素个非零元素,就可就可称其为称其为稀疏矩阵稀疏矩阵。第二十二页，共四十八页。5.2.1 稀疏矩阵的三元组表示稀疏矩阵的三元组

14、表示 稀疏矩阵的压缩存储方法是只存储非零元素。稀疏矩阵的压缩存储方法是只存储非零元素。 由于稀疏矩阵中非零元素的分布由于稀疏矩阵中非零元素的分布(fnb)没有任何规律没有任何规律,所以在存储所以在存储非零元素时还必须同时存储该非零元素所对应的行下标和列下标。非零元素时还必须同时存储该非零元素所对应的行下标和列下标。 稀疏矩阵中的每一个非零元素需由一个三元组：稀疏矩阵中的每一个非零元素需由一个三元组：(i, j, ai,j)唯一确定唯一确定,稀疏矩阵中的所有非零元素构成三元组线性表。稀疏矩阵中的所有非零元素构成三元组线性表。第二十三页，共四十八页。 假设有一个假设有一个67阶稀疏矩阵阶稀疏矩阵A

15、(为图示方便为图示方便,所取的行列数都很所取的行列数都很小小),A中元素如下中元素如下(rxi)图所示。则对应的三元组线性表为：图所示。则对应的三元组线性表为： (0,2,1),(1,1,2),(2,0,3),(3,3,5), (4,4,6),(5,5,7),(5,6,4) 47000000060000000500000000030000020000010076A一个一个(y )(y )稀疏矩阵稀疏矩阵A A第二十四页，共四十八页。 若把稀疏矩阵的三元组线性表按顺序存储若把稀疏矩阵的三元组线性表按顺序存储(cn ch)(cn ch)结构存储结构存储(cn ch)(cn ch), ,则称为稀疏矩

16、阵的三元组顺序表。则三元组顺序表的数则称为稀疏矩阵的三元组顺序表。则三元组顺序表的数据结构可定义如下：据结构可定义如下：第二十五页，共四十八页。 #define MaxSize 100 /矩阵中非零元素最多个数矩阵中非零元素最多个数 typedef struct int r; /行号行号(xn ho) int c; /列号列号 ElemType d; /元素值元素值 TupNode; /三元组定义三元组定义 typedef struct int rows; /行数值行数值 int cols; /列数值列数值 int nums; /非零元素个数非零元素个数 TupNode dataMaxSize

17、; TSMatrix; /三元组顺序表定义三元组顺序表定义第二十六页，共四十八页。 其中其中,data域中表示的非零元素通常以行序为主序顺序排域中表示的非零元素通常以行序为主序顺序排列列,它是一种下标按行有序的存储结构它是一种下标按行有序的存储结构(jigu)。 这种有序存储结构可简化大多数矩阵运算算法。这种有序存储结构可简化大多数矩阵运算算法。 下面的讨论假设下面的讨论假设data域按行有序存储。域按行有序存储。第二十七页，共四十八页。 47000000060000000500000000030000020000010076Aijaij021112203335446557564（1） 从一个

18、二维矩阵创建从一个二维矩阵创建(chungjin)其三元组表示其三元组表示 以行序方式扫描二维矩阵以行序方式扫描二维矩阵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 | j=t.cols) return 0; while (kt.datak.r) k+; /查找行查找行 while (kt.datak.c) k+; /查找

19、列查找列执行执行(zhxng)：Aij=x第三十二页，共四十八页。 if (t.datak.r=i & t.datak.c=j) t.datak.d=x; /存在存在(cnzi)这样的元素这样的元素 else /不存在这样的元素时插入一个元素不存在这样的元素时插入一个元素 for (k1=t.nums-1;k1=k;k1-) /元素后移元素后移 t.datak1+1.r=t.datak1.r; t.datak1+1.c=t.datak1.c; t.datak1+1.d=t.datak1.d; t.datak.r=i;t.datak.c=j; t.datak.d=x; t.nums+; retu

20、rn 1; 第三十三页，共四十八页。 （3）将指定位置的元素值赋给变量）将指定位置的元素值赋给变量(binling) 先在三元组先在三元组t中找到指定的位置中找到指定的位置,将该处的元素值赋给将该处的元素值赋给x。算法如下：。算法如下：执行：执行：x=Aij int Assign(TSMatrix t,ElemType &x,int i,int j)int k=0; if (i=t.rows | j=t.cols) return 0; while (kt.datak.r) k+; /查找行查找行 while (kt.datak.c) k+; /查找列查找列 if (t.datak.r=i &

21、t.datak.c=j) x=t.datak.d; return 1; else return 0;第三十四页，共四十八页。 （4）输出三元组）输出三元组 从头到尾扫描从头到尾扫描(somio)三元组三元组t,依次输出元素值。算法如下：依次输出元素值。算法如下： void DispMat(TSMatrix t) int i; if (t.nums=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,

22、 t.datai.d);第三十五页，共四十八页。 （5）矩阵转置）矩阵转置 对于对于(duy)一个一个mn的矩阵的矩阵Amn,其转置矩阵是一个其转置矩阵是一个nm的矩阵。的矩阵。设为设为Bnm,满足满足ai,j=bj,i,其中其中1im,1jn。47000000060000000500000000030000020000010076Aijaij02111220333544655756440000070000006000000500000000100002000030067Bijaij023112201335446557654第三十六页，共四十八页。void TranTat(TSMatrix t

23、,TSMatrix &tb) int p,q=0,v; /q为为tb.data的下标的下标(xi bio) tb.rows=t.cols;tb.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+; 第三十八页，共四十八页。 以上算法的时间复杂度为以上

24、算法的时间复杂度为O(t.cols*t.nums),而将二维数组存储在一而将二维数组存储在一个个m行行n列矩阵中时列矩阵中时,其转置算法的时间复杂度为其转置算法的时间复杂度为O(m*n)。最坏情况是。最坏情况是当稀疏矩阵中的非零元素个数当稀疏矩阵中的非零元素个数t.nums和和m*n同数量级时同数量级时,上述转置算法上述转置算法的时间复杂度就为的时间复杂度就为O(m*n2)。 对其他几种矩阵运算也是如此。可见对其他几种矩阵运算也是如此。可见,常规的非稀疏矩阵应采用二常规的非稀疏矩阵应采用二维数组存储维数组存储,只有当矩阵中非零元素个数只有当矩阵中非零元素个数s满足满足s(N)?(M):(N)

25、/矩阵行列较大者矩阵行列较大者typedef struct mtxn int row; /行号行号 int col;/列号列号 struct mtxn *right,*down; /向右和向下的指针向右和向下的指针 union int value; struct mtxn *link; tag; MatNode;/十字链表类型定义十字链表类型定义第四十五页，共四十八页。思考题：思考题：稀疏矩阵的十字链表表示给我们什么启示？稀疏矩阵的十字链表表示给我们什么启示？例如，要存放若干班的学生信息，每个班的人数不定例如，要存放若干班的学生信息，每个班的人数不定(bdng)，如，如何设计其存储结构？何设计其存储结构？第四十六页，共四十八页。练习题练习题4 1.p66第第1题；题； 2.p68第第3题；题；第四十七页，共四十八页。内容(nirng)总结第5章 数组和稀疏矩阵。，an构成的有限序列，其逻辑表示为：。A=（a1，a2，。推广到d（d3）维数组，不妨把它看作一个由d-1维数组作为数据元素的线性表。对于一个m行n列的二维数组Amn,有：。（1）数组a中的数组元素数目(shm)。稀疏矩阵的压缩存储方法是只存储非零元素。稀疏矩阵中的每一个非零元素需由一个三元组：。它们采用和非零元素结点类似的结点结构,具体如上图(b)所示。其中行头结点和列头结点的i,j域值均为0第四十八页，共四十八页。