内蒙古大学《算法与数据结构》讲义04数组和矩阵
33页1、下载第4章数组和矩阵在实际应用过程中,数据通常以表的形式出现。尽管用数组来描述表数据是最自然的方式,但有时为了减少程序的时间和空间需求,通常会采用自定义的描述方式,比如,当表中大部分数据全为0时。本章首先检查了多维数组的行主描述形式和列主描述形式。通过行主描述和列主描述,可以把多维数组映射成一维数组。尽管C + +支持多维数组,但它无法保证数组下标的合法性。同时, C + +也未能提供数组的输入、输出以及简单的算术运算(如数组赋值和数组相加) 。为了克服这些不足,我们针对一维数组和二维数组分别设计了类A r r a y 1 D和类A r r a y 2 D。矩阵通常被描述成一个二维数组。不过,矩阵的索引通常从 1开始,而不是像数组那样从0开始,并且通常使用 A(i,j)而不是Ai j来引用矩阵中的元素 (i,j)。为此,设计了另一个类Matrix 以便更好地描述矩阵。本章还考察了一些具有特殊结构的矩阵,如对角矩阵、三对角矩阵、三角矩阵和对称矩阵。与采用二维数组描述矩阵相比, 采用公式化的方法来描述这些特殊矩阵所需要的空间将大大减小,同时,公式化的描述方法还可以显著地节省诸如矩阵加和矩阵
2、减操作所需要的运行时间。本章的最后一节给出了稀疏矩阵(即大部分元素为 0的矩阵)的公式化描述和链表描述,这两种描述方法对于0元素都做了特殊处理。4.1 数组4.1.1 抽象数据类型数据对象a rr a y的每个实例都是形如(i n d e x,v a l u e)的数据对集合,其中任意两对数据的i n d e x值都各不相同。有关数组的操作如下: C re a t e创建一个初始为空的数组(即:不含任何数据) S t o re向数组中添加一对(i n d e x,v a l u e)数据,如果数组中已经存在索引值与 i n d e x相同的数据对,则删除该数据对。 R e t r i e v e返回具有给定i n d e x值的数据对的v a l u e值。A D T 4 - 1给出了具有上述三种操作的抽象数据类型A r r a y。ADT 4-1 数组的抽象数据类型描述抽象数据类型A rr a y实例形如 ( i n d e x , v a l u e )的数据对集合,其中任意两对数据的 i n d e x值都各不相同操作C re a t e( ):创建一个空的数组S t o re(
3、index, value):添加数据(index, value),同时删除具有相同i n d e x值的数据对(如果存在)R e t r i e v e(i n d e x):返回索引值为i n d e x的数据对例4-1 上个星期每天的高温(华氏度数)可用如下的数组来表示:h i g h= ( s u n d a y, 82), (monday, 79), (tuesday, 85), (wednesday, 92),(thursday, 88), (friday, 89), ( s a t u r d a y, 91)数组中的每对数据都包含一个索引(星期)和一个值(当天的温度) ,数组的名称为h i g h。通过执行如下操作,可以将m o n d a y的温度改变为8 3。S t o re( m o n d a y, 83)通过执行如下操作,还可以确定f r i d a y的温度:R e t r i e v e( f r i d a y )也可以采用如下的数组来描述每天的温度:h i g h=(0,82), (1,79), (2,85), (3,92), (4,88), (5,89
4、), (6,91)在这个数组中,索引值是一个数值,而不是日期名,数值( 0,1,2,. . .)代替了一周中每天的名称(s u n d a y,m o n d a y,t u e s d a y,. . .) 。4.1.2 C+数组尽管在C + +中数组是一个标准的数据结构,但 C + +数组的索引(也称为下标)必须采用如下形式:i1 i2 i3 . . . ikij为非负整数。如果k为1,则数组为一维数组,如果k 为2,则为二维数组。i1是索引的第一个坐标,i2是第二个,ik是第k个。在C + +中,值为整数类型的k 维数组s c o r e可用如下语句来创建:int scoreu1 u2 u3 . . . uk 其中ui是正的常量或由常量表示的正的表达式。对于这样一个数组描述,索引 ij的取值范围为:0ijuj, 1jk。因此,该数组最多可以容纳n=u1 u2 u3 . uk 个值。由于数组s c o r e中的每个值都是整数,所以需要占用 s i z e o f ( i n t )个字节,因而,整个数组所需要的内存空间为s i z e o f ( s c o r e ) = n
5、* s i z e o f ( i n t )个字节。C + +编译器将为数组预留这么多空间。假如预留空间的始地址为s t a r t,则该空间将延伸至s t a r t + s i z e ( s c o r e ) - 1。4.1.3 行主映射和列主映射为了实现与数组相关的函数S t o r e和R e t r i e v e,必须确定索引值在s t a rt,s t a rt+n* s i z e o f ( s c o r e ) -1 中的相应位置。实际上就是把数组索引i1 i2 i3 . . . ik 映射到0, n- 1 中的某个数m a p(i1 , i2 , i3 ,., ik ),使得该索引所对应的元素值存储在以下位置:s t a rt + m ap(i1 , i2 , i3 , ., ik ) * s i z e of( i n t )当数组维数为1时(即k= 1) ,使用以下函数:m ap(i1 ) = i1 当数组维数为2时,各索引可按图4 - 1所示的表格形式进行排列,第一个坐标相同的索引位于同一行,第二个坐标相同的索引位于同一列。在图4 - 1中从第一行开
《内蒙古大学《算法与数据结构》讲义04数组和矩阵》由会员东***分享,可在线阅读,更多相关《内蒙古大学《算法与数据结构》讲义04数组和矩阵》请在金锄头文库上搜索。
幼儿园大班科学活动《智能留言机》课件
幼儿园大班语言绘本阅读《手电筒看见了什么》PPT
幼儿园小班科学《教宝宝认识动物》课件
幼儿园中班语言《灰狼家的小饭桶们》教案
【国家审计报告】审计报告W-06审计处罚决定书
【企业财务管理办法】会计档案管理办法
【员工主动离职-风险防范】劳动争议判决书
【员工被动离职-后续工作】70-070员工违反有关商业秘密的约定可以索赔吗
【员工被动离职-辞退申请】第六节 员工任免通知书
【员工被动离职-后续工作】70-050因员工的原因使服务期无法完成可以索赔吗
企业岗位管理制度12办公室行为规范
企业岗位管理制度30离职人员薪资发放通知单
幼儿园春游活动美丽的公园教案
呼职院电力机车制动机讲义11高速列车和重载列车制动
武理工《运输管理》教案第1章 运输系统
中海大海洋化学讲义02海洋的形成和海水的组成——兼论地球上水的起源、变迁和循环
武理工船舶柴油机习题库及答案04燃油喷射和燃烧
厦大海洋生态学课件07海洋初级生产力
华北理工水声学课件05声波在目标上的反射和散射-1目标强度及常见声纳目标的目标强度的一般特征
武理工船舶结构与设备课件02船体结构与管系-4专用船特殊船体结构特点
2023-09-25 37页
2023-09-25 10页
2023-09-25 33页
2023-09-25 26页
2023-04-03 8页
2023-04-03 4页
2023-04-03 8页
2023-03-29 10页
2023-03-22 10页
2023-03-20 8页