第5章数组和广义表课件-2.ppt
- 【下载声明】
1. 本站全部试题类文档,若标题没写含答案,则无答案;标题注明含答案的文档,主观题也可能无答案。请谨慎下单,一旦售出,不予退换。
2. 本站全部PPT文档均不含视频和音频,PPT中出现的音频或视频标识(或文字)仅表示流程,实际无音频或视频文件。请谨慎下单,一旦售出,不予退换。
3. 本页资料《第5章数组和广义表课件-2.ppt》由用户(晟晟文业)主动上传,其收益全归该用户。163文库仅提供信息存储空间,仅对该用户上传内容的表现方式做保护处理,对上传内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(点击联系客服),我们立即给予删除!
4. 请根据预览情况,自愿下载本文。本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
5. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007及以上版本和PDF阅读器,压缩文件请下载最新的WinRAR软件解压。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数组 广义 课件 _2
- 资源描述:
-
1、第第5章章 数组和广义表数组和广义表 元素的值并非原子类型,可以再分解,表中元素的值并非原子类型,可以再分解,表中 元素也是一个线性表(即线性表的推广)。元素也是一个线性表(即线性表的推广)。数组和广义表的特点:数组和广义表的特点:特殊的线性表特殊的线性表5.1 数组的定义数组的定义5.2 数组的顺序表示和实现数组的顺序表示和实现5.3 矩阵的压缩存储矩阵的压缩存储5.4 广义表的定义广义表的定义5.5 广义表的存储结构广义表的存储结构第第5章章 数组和广义表数组和广义表5.1 数组的定义 数组:数组:由一组名字相同、下标不同的同类型的元素由一组名字相同、下标不同的同类型的元素 组成组成 数组
2、特点数组特点 数组结构固定,下标一般具有下标一般具有固定的上界和下界固定的上界和下界 数据元素具有具有统一的类型统一的类型 数组运算数组运算 给定一组下标,取取相应的数据元素.给定一组下标,修修改数据元素的值.数组的处理比其它复杂的结构要简单数组的处理比其它复杂的结构要简单与高级语言中数组的区别:与高级语言中数组的区别:1、本章所讨论的数组是一种、本章所讨论的数组是一种数据结构数据结构,而高级语,而高级语言言 中数组是一种中数组是一种数据类型数据类型。2、高级语言高级语言中的数组是中的数组是顺序结构顺序结构;而本章的数组;而本章的数组 既可以是既可以是顺序的,顺序的,也可以是也可以是链式结构链
3、式结构,用户可,用户可根根 据需要选择。据需要选择。1m10mnAAAA二维数组的特点:二维数组的特点:一维数组的特点:一维数组的特点:1个下标,个下标,ai是是ai+1的直接前驱的直接前驱2 2个下标,个下标,每个元素每个元素aij受到两个关系受到两个关系(行关系和列关系)的约束:(行关系和列关系)的约束:一个一个m mn n的二维数组可以的二维数组可以看成是由看成是由m m行的一维数组组行的一维数组组成或由成或由n n列的一维数组组成。列的一维数组组成。A0A1.Am-1Ai=(ai0,ai1,ai,n-1)i=0,1,2,m-11n1,m1,1m1,0m1n1,11101n0,0100m
4、naaaaaaaaaA)aa(a)aa(a)aa(aA1n1,m1,1m1,0m1n1,11101n0,0100mn5.1 数组的定义 1n1,m1n1,1n0,1,1m11011,0m1000mnaaaaaaaaaA B0 B1 Bn-11n10mnBBBA二维数组是一个数据元素为线性表的线性表二维数组是一个数据元素为线性表的线性表j1,m1j0jjaaaBj=0,1,n-1qaij(1i m-2,1 j n-2)有有两个前驱两个前驱结点结点ai,j-1和和ai-1,j 两个后继两个后继结点结点ai,j+1和和 ai+1,jqa00没有前驱结点没有前驱结点,称之为开始结点称之为开始结点.qa
5、m-1,n-1没有后继结点没有后继结点,称之为终端结点称之为终端结点.q第第0行的元素行的元素a0j(j=1,n-1)q第第0列的元素列的元素ai0(i=1,m-1)只有一个前驱只有一个前驱只有一个后继只有一个后继我们可以把二维数组中的元素我们可以把二维数组中的元素aij看成是属于两个线性表看成是属于两个线性表:即即第第i行的线性表行的线性表Ai和和第第j列的线性表列的线性表Bjq第第m-1行的元素行的元素am-1,j(j=1,n-2)q第第n-1列的元素列的元素ai,n-1(i=1,m-2)同理,三维数组同理,三维数组Amn l中每个元素属于三个线性表,每个元素中每个元素属于三个线性表,每个
6、元素最多有三个前驱和三个后继。最多有三个前驱和三个后继。ai1,i2,i3 前驱:前驱:ai1-1,i2,i3,ai1,i2-1,i3,ai1,i2,i3-1 后继:后继:ai1+1,i2,i3,ai1,i2+1,i3,ai1,i2,i3+1推而广之推而广之,一个一个n n维数组可以看成是维数组可以看成是由若干个由若干个n1维数组组成的线维数组组成的线性表性表,在,在n维数组维数组Ab1 b2 bn中中,每个元素每个元素ai1,i2,in(0 ij bi-1,j=1,2,n)属于属于n个线性表个线性表,每个元素每个元素最多有最多有n个前驱和个前驱和n个后继。个后继。ai1,i2,in 前驱:前
7、驱:ai1-1,i2,in,ai1,i2-1,in,,,ai1,i2,in-1 后继:后继:ai1+1,i2,in,ai1,i2+1,in,ai1,i2,in+1数据对象数据对象:D=aij|aij ElemSet,0ib1-1,0 jb2-1数据关系数据关系:R=ROW,COL ROW=|0ib1-1,0jb2-2 COL=|0ib1-2,0jb2-1二维数组的二维数组的 定义定义:2b1bA InitArray(&A,n,bound1,.,boundn)操作结果:操作结果:若维数若维数 n 和各维长度合法,则构造相应和各维长度合法,则构造相应 的数组的数组A,并返回并返回OK。基本操作:基
8、本操作:DestroyArray(&A)操作结果:操作结果:销毁数组销毁数组A。Value(A,&e,index1,.,indexn)/取数组元素取数组元素 初始条件:初始条件:A是是n维数组,维数组,e为元素变量,随后是为元素变量,随后是n 个下标值。个下标值。操作结果:操作结果:若各下标不超界,则若各下标不超界,则e赋值为所指定的赋值为所指定的 A 的元素值,并返回的元素值,并返回OK。基本操作:基本操作:Assign(&A,e,index1,.,indexn)/修改数组元素修改数组元素 初始条件:初始条件:A是是n维数组,维数组,e为元素变量,随后是为元素变量,随后是 n 个下标值。个下
9、标值。操作结果:操作结果:若下标不超界,则将若下标不超界,则将e的值赋给所指的值赋给所指 定的定的A的元素,并返回的元素,并返回OK。5.2 数组的顺序存储表示和实现问题:问题:计算机的存储结构一般是一维的,而计算机的存储结构一般是一维的,而n n维数组维数组(n n22)一般是多维的,怎样存放?一般是多维的,怎样存放?解决办法:解决办法:事先约定按某种次序将数组元素排成一序事先约定按某种次序将数组元素排成一序 列,然后将这个线性序列存入存储器中。列,然后将这个线性序列存入存储器中。例如:例如:在二维数组中,我们既可以规定按在二维数组中,我们既可以规定按行行存储,也存储,也可以规定按可以规定按
10、列列存储存储。若规定好了次序,则数组中任意一个元素的存放地址便有若规定好了次序,则数组中任意一个元素的存放地址便有规律可寻,可形成地址计算公式;规律可寻,可形成地址计算公式;约定的次序不同,则计算元素地址的公式也有所不同;约定的次序不同,则计算元素地址的公式也有所不同;C C和和PASCALPASCAL中一般采用行优先顺序;中一般采用行优先顺序;FORTRANFORTRAN采用列优先。采用列优先。按行序为主序存放按行序为主序存放 am-1,n-1 .am-1,1 am-1,0 .a1n-1 .a11 a10 a0,n-1 .a01 a00 a00 a01 .a0,n-1 a10 a11 .a1
11、,n-1 am-1,0 am-1,1 am-1,n-1 .01n-1m*n-1n am-1,n-1 .a1,n-1 a0,n-1 .am-1,1 .a11 a01 am-1,0 .a10 a00 a00 a01 .a0n-1 a10 a11 .a1n-1 am-10 am-11 .am-1n-1 .按列序为主序存放按列序为主序存放01m*n-1m-1m计算二维数组元素地址的通式计算二维数组元素地址的通式二维数组二维数组列优先列优先存储的通式为:存储的通式为:LOC(aij)=LOC(a00)+(b1*j+i)*L则则行优先行优先存储时的地址公式为:存储时的地址公式为:LOC(aij)=LOC(
12、a00)+(b2*i+j)*L设一般的二维数组是设一般的二维数组是A0.bA0.b1 1-1,0.b-1,0.b2 2-1-11b21,b11,0b11b2i,iji01b20,00mna.a.a.a.a.a.aA计算三维数组元素地址的通式计算三维数组元素地址的通式设一般的设一般的三维数组是维数组是A0.bA0.b1 1-1,0.b-1,0.b2 2-1-1,0.b0.b3 3-1-1按按“行优先顺序行优先顺序”存储,其任一元素存储,其任一元素A Aijkijk地地址计算函数为:址计算函数为:LOC(aLOC(aijkijk)=LOC(a)=LOC(a000000)+()+(i i*b b2
13、2*b b3 3+j j*b b3 3+k)+k)*L L若是若是N N维数组,其中任一元素的地址该如何计算?维数组,其中任一元素的地址该如何计算?LjbjaLOCLjjbjbbbjbbbaLOCaLOCniniknkinnnnnnjjj1110.0012431320.00,.,21)()().()()(开始结点的存放地址(即基地址)开始结点的存放地址(即基地址)维数和每维的上、下界;维数和每维的上、下界;每个数组元素所占用的单元数每个数组元素所占用的单元数其中其中Cn=L,Ci-1=biCi,1in(递归)递归)Loc(jLoc(j1 1,j,j2 2,j jn n)=LOC(0,0,)=L
14、OC(0,0,0)0)niii1jC5.3 矩阵的压缩存储矩阵的压缩存储 在科学与工程计算问题中,矩阵是一种常用在科学与工程计算问题中,矩阵是一种常用的数学对象,在高级语言编制程序时,将一个矩的数学对象,在高级语言编制程序时,将一个矩阵描述为一个二维数组。矩阵在这种存储表示之阵描述为一个二维数组。矩阵在这种存储表示之下,可以对其元素进行随机存取,各种矩阵运算下,可以对其元素进行随机存取,各种矩阵运算也非常简单。也非常简单。但是在矩阵但是在矩阵中非零元素呈某种规律分布中非零元素呈某种规律分布或者或者矩阵中出现大量的零元素矩阵中出现大量的零元素的情况下,占用了许多的情况下,占用了许多单元去存储重复
15、的非零元素或零元素,这对高阶单元去存储重复的非零元素或零元素,这对高阶矩阵会造成极大的浪费,为了节省存储空间,矩阵会造成极大的浪费,为了节省存储空间,我们可以对这类矩阵进行我们可以对这类矩阵进行压缩存储压缩存储:即为多个相即为多个相同的非零元素只分配一个存储空间;对零元素不同的非零元素只分配一个存储空间;对零元素不分配空间分配空间。并非所有的矩阵都可以压缩并非所有的矩阵都可以压缩对称矩阵对称矩阵三角矩阵三角矩阵稀疏矩阵稀疏矩阵5.3.1 5.3.1 特殊矩阵特殊矩阵在一个在一个n n阶方阵阶方阵A A中,若元素满足下述性质:中,若元素满足下述性质:a aijij=a=ajiji 0 0i,ji
16、,jn-1n-1 1 5 1 3 7 a00 5 0 8 0 0 a10 a 11 1 8 9 2 6 a20 a21 a22 3 0 2 5 1 .7 0 6 1 3 an-1 0 an-1 1 an-1 2 an-1 n-1 对称矩阵对称矩阵1 1、对称矩阵、对称矩阵sak按行序为主序按行序为主序:a00a10a11a20a21a22an-1,0an-1,n-1012345n(n-1)n(n+1)/2-11)对称矩阵的存储方式)对称矩阵的存储方式在对称矩阵中,第在对称矩阵中,第i i行恰有行恰有i+1i+1个元素,元素总数为:个元素,元素总数为:可以将这些元素存放在一个向量可以将这些元素存
17、放在一个向量 中中1 1、对称矩阵、对称矩阵1n0i21)n(n1)(i 12/)1(.0nnsa2)为了便于访问对称矩阵为了便于访问对称矩阵A A中的元素,我们必须在中的元素,我们必须在a aijij和和saksak之间找一个对应关系之间找一个对应关系。v若若i ij j,则则a aijij在下三角形中。在下三角形中。a aijij之前的之前的i i行(从第行(从第0 0行行到第到第i-1i-1行)一共有行)一共有1+2+1+2+i=ii=i*(i+1)/2(i+1)/2个元素,在第个元素,在第i i行上,行上,a aijij之前恰有之前恰有j j个元素(即个元素(即a ai0i0,a,ai
18、1i1,a,ai2i2,a,aij-1ij-1),),因此有:因此有:k=ik=i*(i+1)/2+j(i+1)/2+j 0kn(n+1)/2-10kn(n+1)/2-1 v若若ijij,则则a aijij是在上三角矩阵中。因为是在上三角矩阵中。因为a aijij=a=ajiji,所以只所以只要交换上述对应关系式中的要交换上述对应关系式中的i i和和j j即可得到:即可得到:k=jk=j*(j+1)/2+i(j+1)/2+i 0kn(n+1)/2-10kn(n+1)/2-1 1 1、对称矩阵、对称矩阵 2、三角矩阵、三角矩阵以主对角线划分,三角矩阵有以主对角线划分,三角矩阵有上三角上三角和和下
19、三角下三角两种。两种。上三角矩阵中主对角线以下的元素均为常数上三角矩阵中主对角线以下的元素均为常数(a)。下三角矩阵正好相反,主对角线以上的元素均为常数下三角矩阵正好相反,主对角线以上的元素均为常数(b)。a00 a01 .a0,n-1 c a11 .a1,n-1 c c c am-1,n-1 (a)上三角矩阵上三角矩阵 a00 c .c a10 a11 c.c am-10 am-11 am-1,n-1 (b)下三角矩阵下三角矩阵可以用向量可以用向量sa0.n(n+1)/2sa0.n(n+1)/2存储,将常量存入存储,将常量存入第一或最后一个单元第一或最后一个单元 5.3.2 5.3.2 稀疏
20、矩阵稀疏矩阵1 1、什么是稀疏矩阵?、什么是稀疏矩阵?设矩阵设矩阵A A中有中有s s个非零元素,若个非零元素,若s s远远小于矩远远小于矩阵元素的总数(即阵元素的总数(即smsmn),n),则称则称A A为稀疏矩为稀疏矩阵。阵。有有s s个非零元素。令个非零元素。令e=s/(me=s/(mn)n),称称e e为矩阵为矩阵的的稀疏因子稀疏因子。通常认为。通常认为e e0.050.05时为稀疏矩时为稀疏矩阵。阵。稀疏矩阵的压缩存储方法稀疏矩阵的压缩存储方法一、三元组顺序表一、三元组顺序表二、行逻辑联接的顺序表二、行逻辑联接的顺序表三、三、十字链表十字链表存储稀疏矩阵时,为了节省存储单元,使用存储
21、稀疏矩阵时,为了节省存储单元,使用压缩压缩 存储方法。存储方法。非零元素的分布一般是没有规律的,因此在存储非零元素的分布一般是没有规律的,因此在存储 非零元素的同时,还必须同时记下它所在的非零元素的同时,还必须同时记下它所在的行和行和 列的位置(列的位置(i,j)i,j)。一个一个三元组三元组(i,j,ai,j,aijij)唯一确定了矩阵唯一确定了矩阵A A的一个非零的一个非零 元。因此,稀疏矩阵可由元。因此,稀疏矩阵可由表示非零元的三元组表示非零元的三元组及及 其其行列数行列数唯一确定。唯一确定。一、三元组顺序表一、三元组顺序表例如,下列稀疏矩阵例如,下列稀疏矩阵 5.3.2 5.3.2 稀
22、疏矩阵稀疏矩阵可由三元组表可由三元组表(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)唯一确定)唯一确定 7600070015000001800000240001400003000000000009120M=123456 1 2 3 4 5 6 7 一、三元组顺序表一、三元组顺序表#define MAXSIZE 12500 typedef struct int i,j;/该非零元的行下标和列下标该非零元的行下标和列下标 ElemType e;/该非零元的值该非零元的值 T
23、riple;/三元组类型三元组类型typedef struct Triple dataMAXSIZE+1;int mu,nu,tu;(mu行数行数,nu列数列数,tu非零元个数非零元个数)TSMatrix;/稀疏矩阵类型稀疏矩阵类型三元组表表示法:三元组表表示法:121213931-3351443245218611564-7注意:注意:三元组表中的三元组表中的元素按行(或列)排元素按行(或列)排列。列。668ije稀疏矩阵压缩存储的稀疏矩阵压缩存储的缺点:将失去随机存取功能缺点:将失去随机存取功能0 12 9 0 0 00 0 0 0 0 0 -3 0 0 0 14 00 0 24 0 0 0
24、0 18 0 0 0 015 0 0 -7 0 0求转置矩阵算法求转置矩阵算法028003600070500140M005280000007143600T用常规的二维数组表示时的算法用常规的二维数组表示时的算法 其时间复杂度为其时间复杂度为:O(munu)for(c=1;c=nu;+c)for(r=1;r=mu;+r)Tcr=Mrc;三元组表示的转置(1,2,12)(1,3,9)(3,1,-3)(3,5,14)(4,3,24)(5,2,18)(6,1,15)(6,4,-7)(1,3,-3)(1,6,15)(2,1,12)(2,5,18)(3,1,9)(3,4,24)(4,6,-7)(5,3,1
25、4)三三元元组组表表M.data三三元元组组表表T.data转置后转置后0 12 9 0 0 00 0 0 0 0 0-3 0 0 0 14 00 0 24 0 0 00 18 0 0 0 015 0 0 -7 0 0M=0 0 3 0 0 1512 0 0 0 18 0 9 0 0 24 0 00 0 0 0 0 -70 0 14 0 0 00 0 0 0 0 0T=?不正确!不正确!(1 1)每个元素的行下标和列下标互换(即三元组中的)每个元素的行下标和列下标互换(即三元组中的i i和和j j 互换互换););(2 2)T T的总行数的总行数mumu和总列数和总列数nunu与与M M值不同
展开阅读全文