当前位置：文档之家 › 7第四章 数组,集合和矩阵

7第四章 数组,集合和矩阵

  • 格式：ppt
  • 大小：611.50 KB
  • 文档页数：39

下载文档原格式

  / 39

合集下载

第四章数组、矩阵、广义表

第四章数组、矩阵、广义表

数组、矩阵、广义表数组的概念和逻辑结构模糊定义：它就是数据类型相同的元素按一定顺序排列的集合，可以看作是广义表的推广数组具有的三个特征：1.数据元素类型必须一致2.数组在内存中占用一段连续的存储空间，数组元素的逻辑顺序和物理顺序一致3.数组中的元素本身可以是具有某种结构的数据，如整型，字符型，自定义结构体类型多维数组可以被看做是一维数组，n维数组(n>=2)可以看做是一维数组，它的每个数组元素都是一个n-1维的数组二维数组中每一个数组元素最多可以有两个直接前驱和两个直接后继(边界元素除外)——>在n维数组中，每个数组元素最多可以有n个直接前驱和n个直接后继，所以多维数组是一种非线性结构清晰定义：数组是一个具有固定格式和数量的数据有序集，每个数据元素由唯一的数组下标标识，因此，在数组上不适合做插入、删除数据元素的操作数组中两个主要操作：取值操作：给定数组下标，读取其对应的数据元素；赋值操作：给定数组下标，存储或修改与其对应的数据元素；数组的基本操作(书上P75面)数组的物理结构(是数组在计算机中的存储表示):实质是讨论数组在内存中的映像。

通常，数组在内存中被映像为向量，即用向量作为数组的一种存储结构。

因为内存的地址空间是一维的，用一维的连续存储空间存放多维数组，就必须通过某种次序将数组中的元素排成一个线性序列，然后将这个线性序列顺序存放在计算机中。

当数组的行列固定后，通过一个映像函数，则可根据数组元素下表得到它的存储地址:1.对于一维数组按下标顺序分配地址即可ai=a0+(n-1)d2.对于二维数组分配地址时，需要把它的元素映像存储在一维存储器中，如(BASIC,Pascal,C等)采用以行为主(先行后列)的方式顺序存放，即一行分配结束之后，再分配下一行，物理地址:aij=a00+(i*n+j)d3.“以行为主序”的分配规律：最右边的下标先从小到大变化，循环一遍后，右边第二个下标再变，……，按照此规律从右往左，最后变化的是数组元素最左边的下标特殊矩阵需要原因:二维数组很适合来表示矩阵结构，可是某些特殊矩阵中含有许多重复或无效的数据，如三角矩阵，对称矩阵，对角矩阵，稀疏矩阵。

数据结构复习

数据结构复习

地址计算 以三对角矩阵为例
三对角矩阵中所有非零元素为3*n-2,可用一维数组s[3*n-2]存储.aij与s[k]
LOC(i,j)=LOC(0,0)+[3*i-1+(j-i+1)]*d
=LOC(0,0)+(2i+j)*d
4.3.2 稀疏矩阵
5、设长度为n的链队列用单循环链表表示，若只设头指针，则怎样进行入队和出队操作；若只设尾指针呢？
6、假设循环队列只设rear和quelen来分别指示队尾元素的位置和队中元素的个数，试给出判断此循环队列的队满条件，并写出相应的入队和出队算法，要求出队时需返回队头指针。
第四章 数组
4.1 数组的定义
（2）能否得到出栈序列423和432？并说明为什么不能得到或如何得到。
（3）请分析1、2、3、4的24种排列中，哪些序列可以通过相应的入出栈得到。
2、表达式求值
3、两个栈共享存储空间r[m]，写出向第i个栈插入x,删除第i个栈的栈顶元素算法。
4、循环队列的优点是什么？如何判断它的空和满？循环队列的操作算法？
（2）二叉链表法
5．3 遍历二叉树
在二叉树的一些应用中，常常要求在树中查找具有某
种特征的结点，或者对树中全部结点逐一进行某种处
理。这就引入了遍历二叉树的问题，即如何按某条搜
索路径巡访树中的每一个结点，使得每一个结点均被
访问一次，而且仅被访问一次。
DLR——先（根）序遍历，
LDR——中（根）序遍历，
习题：6.2,6.3,6.5,6.6,6.7,6.12,6.13,6.14,6.19,6.21,6.26,6.42,6.43,6.47,
第六章 图

计算机数据结构习题1附答案

计算机数据结构习题1附答案

文档来源为:从网络收集整理.word 版本可编辑.欢迎下载支持.第1章 绪论1.1 简述下列术语：数据，数据元素、数据对象、数据结构、存储结构、数据类型和抽象数据类型。

解：数据是对客观事物的符号表示。

在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。

数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。

数据对象是性质相同的数据元素的集合，是数据的一个子集。

数据结构是相互之间存在一种或多种特定关系的数据元素的集合。

存储结构是数据结构在计算机中的表示。

数据类型是一个值的集合和定义在这个值集上的一组操作的总称。

抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。

是对一般数据类型的扩展。

1.2 填空题：1.常见的数据结构有__结构，_____结构，____结构等三种。

2.常见的存储结构有_________结构，______结构等两种。

3.数据的基本单位是____，它在计算机中是作为一个整体来处理的。

4.数据结构中的结构是指数据间的逻辑关系，常见的结构可分为两大类，______和_____。

5.《数据结构》课程讨论的主要内容是数据的逻辑结构、存储结构和________。

1.2设有数据结构(D,R)，其中{}4,3,2,1d d d d D =，{}r R =，()()(){}4,3,3,2,2,1d d d d d d r =试按图论中图的画法惯例画出其逻辑结构图。

解：1.3设有以下三个函数：()10002124++=n n n f ，()3450015n n n g+=，()n n n n h log 5005.3+=请判断以下断言正确与否：(1) f(n)是O(g(n)) (2) h(n)是O(f(n)) (3) g(n)是O(h(n)) (4) h(n)是O(n 3.5) (5) h(n)是O(nlogn)解：(1)对 (2)错 (3)错 (4)对 (5)错第二章序列2.1 描述以下三个概念的区别：头指针，头结点，首元结点（第一个元素结点）。

7.4单元刚度矩阵组装及整体分析报告材料

7.4单元刚度矩阵组装及整体分析报告材料

7.4 单元刚度矩阵组装及整体分析7.4.1 单刚组装形成总刚根据全结构的平衡方程可知，总体刚度矩阵是由单元刚度矩阵集合而成的.如果一个结构的计算模型分成个单元，那么总体刚度矩阵可由各个单元的刚度矩阵组装而成，即[K]是由每个单元的刚度矩阵的每个系数按其脚标编号“对号入座”叠加而成的.这种叠加要求在同一总体坐标系下进行.如果各单元的刚度矩阵是在单元局部坐标下建立的，就必须要把它们转换到统一的结构（总体）坐标系.将总体坐标轴分别用表示，对某单元有式中，和分别是局部坐标系和总体坐标系下的单元结点位移向量;［T］为坐标转换阵，仅与两个坐标系的夹角有关，这样就有是该单元在总体坐标系下的单元刚度矩阵.以后如不特别强调，总体坐标系下的各种物理参数均不加顶上的横杠.下面就通过简单的例子来说明如何形成总体刚度矩阵.设有一个简单的平面结构，选取6个结点，划分为4个单元.单元及结点编号如图3-27所示.每个结点有两个自由度.总体刚度矩阵的组装过程可分为下面几步：图7-27（1）按单元局部编号顺序形成单元刚度矩阵.图7-27中所示的单元③，结点的局部编号顺序为.形成的单元刚度矩阵以子矩阵的形式给出是（2）将单元结点的局部编号换成总体编号，相应的把单元刚度矩阵中的子矩阵的下标也换成总体编号.对下图3-27所示单元③的刚度矩阵转换成总体编号后为（3）将转换后的单元刚度矩阵的各子矩阵，投放到总体刚度矩阵的对应位置上.单元③的各子矩阵投放后情况如下：（4）将所有的单元都执行上述的1，2，3步，便可得到总体刚度矩阵，如式（3-9）.其中右上角的上标表示第单元所累加上的子矩阵.（3-9）（5）从式（3-9）可看出，总体刚度矩阵中的子矩阵AB是单元刚度矩阵的子矩阵转换成总体编号后具有相同的下标，的那些子矩阵的累加.总体刚度矩阵第行的非零子矩阵是由与结点相联系的那些单元的子矩阵向这行投放所构成的.7.4.2 结点平衡方程我们首先用结构力学方法建立结点平衡方程.连续介质用有限元法离散以后，取出其中任意一个结点，从环绕点各单元移置而来的结点载荷为式中表示对环绕结点的所有单元求和，环绕结点的各单元施加于结点的结点力为.因此，结点的平衡方程可表示为（3-10）以[K]代入平衡方程，得到以结点位移表示的结点的平衡方程，对于每个结点，都可列出平衡方程，于是得到整个结构的平衡方程组如下：式中，[K]为整体刚度矩阵，为全部结点位移组成的向量，为全部结点载荷组成的向量.当然，如果各点的载荷向量也是在单元局部坐标下建立的，在合成以前，也应把它们转换到统一的结构（总体）坐标系下，即式中，是总体坐标系下的结点载荷向量，为坐标转换阵.7.4.3 位移边界条件在有限元法对结构进行整体分析时，建立了整体刚度矩阵[K]，也得到了结构的刚度平衡方程，即.结构刚度方程的求解相当于总刚[K]求逆的过程.但是，从数学上看，未经处理的总刚是对称、半正定的奇异矩阵，它的行列式值为零，不能立即求逆.从物理意义看，在进行整体分析时，结构是处于自由状态，在结点载荷的作用下，结构可以产生任意的刚体位移.所以，在已知结点载荷的条件下，仍不能通过平衡方程惟一地解出结点位移.为了使问题可解，必须对结构加以足够的位移约束，也就是应用位移边界条件.首先要通过施加适当的约束，消除结构的钢体位移，再根据问题要求设定其他已知位移.所以，处理位移边界条件在有限元分析步骤中十分重要.约束的种类包括使某些自由度上位移为零，，或给定其位移值，还有给定支承刚度等，本书涉及前两种.处理约束的方法，常用的有删行删列法、分块法、置大数法和置“1”法等，下面分别予以介绍.1、删行删列法若结构的某些结点位移值为零时（即与刚性支座连接点的位移），则可将总体刚度矩阵中相应的行列、删行删列划掉，然后将矩阵压缩即可求解.这种方法的优点是道理简单.如果删去的行列很多，则总体刚度矩阵的阶数可大大缩小.通常用人工计算时常采用该方法.若用计算机算题，在程序编制上必带来麻烦，因为刚度矩阵压缩以后，刚度矩阵中各元素的下标必全改变.因而一般计算机算题不太采用.2．分块法为了理解这个方法，我们把方程分块如下：（3-11）其中，假设是给定的结点位移；是无约束的（自由）结点位移.因而是已知的结点力；是未知的结点力.方程（3-11）可以写为即（3-12）和（3-13）其中，不是奇异的，因而可以解方程（3-12）得出（3-14）一旦知道了，就可以由方程（3-13）求得未知结点力.在全部给定的结点自由度都等于零的特殊情况下，我们可以删除对应于的各行和各列（即删行删列法），故可把方程简写为（3-15）3．置“1”法由于全部给定的结点位移通常都不能在位移向量的开始或终了，故分块法的编号方法是很麻烦的.因此，为了引入给定的边界条件，可以采用下述等价的方法.可以把方程（3-12）和（3-13）合在一起写为（3-16）在实际计算中，方程（3-16）所示的过程可以在不重新排列所述方程的情况下用下述分块的方法为进行.步骤（1）如果把给定为，则载荷向量P可以修改为为结点自由度总数.步骤（2）除对角线元素以外，使[K]中对应于的行和列为零，而对角线元素为1，即步骤（3）在载荷向量中引入规定的值，即对全部规定的结点位移均应反复运用上述过程（步骤（1）到（3））.应当指出，由于这个过程保持了方程的对称性，因此，[K]可以按带状存储，而且几乎不会增加编制程序的工作量.4．置大数法置大数法的思路是：在总体刚度矩阵中，把指定位移所对应的行和列的对角元素乘上一个很大的数，如，此行其他元素保持不变，同时把该行对应的载荷项也相应地用来代替，这里为指定位移，于是原平衡方程组变为除第行外，其他各行仍保持原来的平衡特性，而第个方程式展开为由于上式中的比其他项的系数大得多，求和后可略去其小量，则上式变为即.这样就用近似方程组代替原方程组，得到近似满足边界条件的解.当指定位移为零时，只要将对角元素乘上一个大数，而相应的载荷项经证明可以不置零.删行删列法适用于指定零位移点，而置大数法适用于给定位移（包括零位移）.5．斜支座的处理对于简单的约束情况（如限定某些结点位移为零或取得给定数值），可以用前述置大数法处理.有的结构在直角坐标系内建立了位移方程组，但在某个斜边上受有法向约束.如图3-28所示正方形固支板，受均布横向载荷，对此，可利用对称性而只计算其1/8，如图中ABC部分，其中AC为固支边，按对称性，AB边上有，但在BC边上应限定绕BC的转用等于零.为处理此类斜边上的约束，须对斜边上的结点做坐标变换.若结构的总体坐标系为为斜支座的局部坐标系（见图3-29）.对于边界结点，须限定方向位移，为此，将边界结点的位移及载荷都变换到局部坐标轴系.设轴与斜支座的轴夹角为，逆时针为正，图7-28 图7-29 则依据第二单中坐标转换关系有其中，.或写成（3-17）与位移关系相同有（3-18）将上两式带入结构刚度方程有（3-19）这样把位移到列阵中凡是斜支座的结点位移矢量都用局部坐标表示了.将式（3-19）中第行左右两边前乘以（3-20）由上式可见：凡是边界点的斜支座，在刚度方程中对应于斜支座的位移和载荷向量均可直接斜支座的局部坐标值，总刚度距阵中的相应行列需作相应的变换.上式的系数矩阵仍然是对称的，而且此方程中结点位沿轴表示，这样，限定方向的位移就很方便了.实际计算中，并不需要建立结构总的位移方程组后再进坐标变换.而可以在形成单元刚度矩阵和结点载荷之后，就对斜支座点进行坐标变换，把变换后的单元刚度矩阵和结点载荷叠加入总刚度矩阵和总载荷的相应位置，最后叠加形成的也就是方程组（3-20），即需要处理的结点，应该在单元计算中完成坐标变换后再叠加，当结构有不同的斜边约束时，都可以这样处理，只不过对不同边上的结点，应按不同的方向余弦矩阵变换就是了.7.4.4 总刚度平衡方程的求解应用有限元法，最终都是归结为解总体刚度平衡方程，它实际上是以总体刚度矩阵为系数矩阵的大型线性代数方程组.通过对结构施加位移边界条件，消除了结构的刚体位移，从而消除总体刚度矩阵的奇异性，解这个线性代数方程组可求出结位移.我们已知，总体刚度矩阵具有大型、对称、稀疏、带状分布、正定、主元占优势的特点，稀疏表示将对称消元法进一步改造，使之适合总刚的等带宽二维存储.（4）因子化法（三角分解）又称Cholesky分解，适合一维变带宽存储总刚.这上方法储效率高，计算速度快，应用较为普遍.此外，还有一种方法，叫做波前法.波前法实际上也是一种改进的高斯消去法.它建立一个称为“波前”的空间，各单元刚度系数依次进入波前.一旦与某自由度有关的所有单元的刚度系数全部装入，便可将相应的变量消去.经过消元的方程的系数随即退出波前，存放在计算机的外存中.这样就可腾出空间装入新的刚度系数.所以，波前法不需要生成完整的总刚，而是边组装边消元，“成熟”一个消去一个.消元完成后，全部系数都已存储在计算机的外存或缓冲区中.回代时将各方程的系数按“先出后入”的顺序调入内存求解.由此可见，这种方法是利用计算机充裕的外存资源，以多耗取机时来缓解内存不足的矛盾，以便适应较大规模的问题.随着计算机技术的发展，内存资源不断扩大，对具有稀疏、带状性质的有限元刚度方程，这种以时间换取空间的办法得不偿失.另一方面，波前法的阐述和程序设计比较复杂，且对多种单元并存的结构使用不便.所以，本书不拟介绍波前法.本书第九章将详细讨论适合整体存储总刚的高斯消去法和适合一维变带宽存储的因子化法以及有关的程序设计问题，以下仅列出这两种方法的梗概.1、高斯消去法高斯循序消去法的一般公式：对于n阶线性代数方程，需进行次消元.采用循序消去时，第m次消元以m-1次消元后的m行元素作为主元行，为主元，对第行元素（）的消元公式为（3-21）式中等的上角码（m），表示该元素是经过第m次消元后得到的结果.同样，可以把经过m次消元后的系数矩阵和载荷阵分别记为及.式表时第m 次消元是在经m-1次消元的基础上进行的.消元过程中，主元及被消元素的位置可见图3-30（a）.图中阴影部分已完成消元过程的元素，主元行以下的矩阵为待消部分.在进行第m次时，1-m行元素的消元过程已经完成，其中的元素就是消元最后得到的上三角阵中的元素. m行发下的元素消元过程尚未结束，连同m行元素在内构成一个待消的方阵.消元共需进行n-1次.消元完成后，即可回代求解.我们把消元最后结果记为，为上三角阵，回代公式可写作（3-22）回代过程自后向前进行.当回代求解时，已经解得.回代示意图见图3-30（b），阴影部分为已求得解答的部分.图7-30 高斯消去法2．三角分解法总体刚度平衡方程中，[K]是对称、正定矩阵，因而可做如下分解（3-23）其中，则是单位上三角矩阵，.代入整本结构平衡方程记，则.即由向下回代.由其中第一个方程解得，再由第二个方程解得，……，依此类推可求得{Y}.又由向上回代，可得，由得依此类推可求得.由上述过程可见，三角分解法求解线性代数方程组的关键是对系数矩阵进行三角分解.7.4.5 求解内力由平衡方程组解出位移后，从中分离出各单元的结点位移，再通过方程（3-3）、（3-4）和（3-6）等计算各单元的应变、应力和结点力等内力。

数据结构第四章资料

数据结构第四章资料

设数组开始存放位置 LOC( 0, 0 ) = a LOC ( j, k ) = a + j * m + k
三维数组
按页/行/列存放，页优先的顺序存储
u1
①
u3
l1 l2 l3
u2
② ③
三维数组
a[m1][m2] [m3] 各维元素个数为
m1, m 2, m3
下标为 i1, i2, i3的数组元素的存储位置：
KMP（Knuth Morris Pratt）算法（一般理解）
《计算机程序设计艺术 第1卷 基本算法》 《计算机程序设计艺术 第2卷 半数值算法》 《计算机程序设计艺术 第3卷 排序与查找》
/~knuth/
KMP算法设计思想
利用已经部分匹配的结果而加快模式串的滑动速度？ 且主串S的指针i不必回溯！可提速到O(n+m)！
基本操作:
(1) InitArray (&A,n,bound1, boundn) //构造数组A (2) DestroyArray (&A) // 销毁数组A (3) Value(A,&e,index1,…,indexn) //取数组元素值 (4) Assign (A,&e,index1,…,indexn) //给数组元素赋值
FORTRAN
二维数组的行序优先表示
a[n][m]
a[0][1] a[0][0] a[1][1] a[1][0] a a[2][0] a[2][1] a[n 1][0] a[n 1][1] a[0][m 1] a[1][m 1] a[2][m 1] a[n 1][m 1]
第4章 串、数组和广义表

c语言(8)

c语言(8)
再如：float s[3][50];该语句表示s是一个单精度型二维数组,数组s有3行50列，共有150个元素,每个元素都是单精度型数据，系统要为数组s分配4*150=600个字节的存储单元。
二、二维数组元素的引用
1. 格式: 数组名[下标1][下标2]
2. 说明:
(1) 一次只能引用一个数组元素,所引用的数组元素与其他同类变量同等使用；
§7.2 二维数组
一、二维数组的定义
1. 格式: 类型说明符 数组名[常量表达式1][常量表达式2];
2. 说明:
(1) 常量表达式1和常量表达式2和值分别确定了二维数组第一维和第二维和大小.如: int a[3][4] 定义a为一个二维数组,第一维的大小是3,第二维的大小是4,即可以将二维数组中的所有数据看成是一个3行4列的矩阵,数组中的元素个数是各维的大小的乘积即12。
引用的数组元素可以这样使用:
a[0]=12; /* 将常量12赋给数组元素a[0]*/
a[1]=78; /*将常量78赋给数组元素a[1]*/
a[2]=a[1]+a[2];/* 将数组元素a[1]与a[2]的值之和再赋给数组元素a[2]*/
一、一维数组的初始化(即在定义数组时对数组元素赋以初值)
二、一维数组元素的引用
1. 格式: 数组名[下标]
2. 说明:
(1) 一次只能引用一个数组元素,所引用的数组元素与其他同类变量同等使用；
(2) 下标可以是整型常量、整型变量、整型表达式；
(3) 注意数组定义和数组引用的格式相同,但意义不同；
例如,对于前面所定义的数组a,a[0]表示数组a中的首元素,a[9]表示数组a中的最后一个元素,数组元素的最大下标只能为9而不能为10；

数据结构考试题库含答案

数据结构考试题库含答案数据结构习题集含答案目录目录1选择题2第一章绪论2第二章线性表4第三章栈和队列5第四章串6第五章数组和广义表7第六章树和二叉树7第七章图9第八章查找11第九章排序12简答题15第一章绪论15第二章线性表20第三章栈和队列22第四章串24第五章数组和广义表24第六章树和二叉树26第七章图31第八章查找33第九章排序34编程题36第一章绪论36第二章线性表36第三章栈和队列46第四章串46第五章数组和广义表46第六章树和二叉树46第七章图46第八章查找46第九章排序51选择题第一章绪论1.数据结构这门学科是针对什么问题而产生的？（A）A、针对非数值计算的程序设计问题B、针对数值计算的程序设计问题C、数值计算与非数值计算的问题都针对D、两者都不针对2.数据结构这门学科的研究内容下面选项最准确的是（D）A、研究数据对象和数据之间的关系B、研究数据对象C、研究数据对象和数据的操作D、研究数据对象、数据之间的关系和操作3.某班级的学生成绩表中查得张三同学的各科成绩记录，其中数据结构考了90分，那么下面关于数据对象、数据元素、数据项描述正确的是（C）A、某班级的学生成绩表是数据元素，90分是数据项B、某班级的学生成绩表是数据对象，90分是数据元素C、某班级的学生成绩表是数据对象，90分是数据项D、某班级的学生成绩表是数据元素，90分是数据元素4.某数据结构是指（A）。

A、数据元素的组织形式B、数据类型C、数据存储结构D、数据定义5.数据在计算机存储器内表示时，物理地址与逻辑地址不相同，称之为（C）。

A、存储结构B、逻辑结构C、链式存储结构D、顺序存储结构6.算法分析的目的是（C）A、找出数据的合理性B、研究算法中的输入和输出关系C、分析算法效率以求改进D、分析算法的易懂性和文档型性7.算法分析的主要方法（A）。

A、空间复杂度和时间复杂度B、正确性和简明性C、可读性和文档性D、数据复杂性和程序复杂性8.计算机内部处理的基本单元是（B）A、数据B、数据元素C、数据项D、数据库9.数据在计算机内有链式和顺序两种存储方式，在存储空间使用的灵活性上，链式存储比顺序存储要（B）。

c语言第四章 数组和结构.ppt


C语言程序设计
10
任务4.2 筛法依据
方法的依据：
1到200这些自然数可以分为3类： （1）单位数，即1 （2）素数，大于1，且只能被1和它自身整除 （3）合数，除了1和自身，还有其他正因子 筛法实际上是筛去合数，留下素数 为了提高筛法效率，注意到： 如n为合数（这里是200），c为n的大于1的最
赋过初值后的ice变量如下图所示
C语言程序设计
22
4.2.3 二维数组中的元素存放顺序
在内存中二维数组中的元素是按行存放的。 如上例中的二维数组 ice，其元素的存放顺序 如下图所示。
•二维数组一经定义， 系统就为其分配了连 成一片的存储区域， 这个区域有个首地址， 即ice[0][0]的地址， C/C++规定数组名就是 这个首地址的符号地 址
（5）第二遍扫描后， a[4]位置已定，以 后也不需再与a[4] 交换
以此类推每遍扫描 后都有一个元素的 位置已定，以后不 需再与之进行比较
C语言程序设计
15
冒泡排序算法设计
为了表述方便，定义以下3个变量
–（1）待排序的数的个数n（此处为6） –（2）扫描遍数j（j=1,2,3,…n-1） –（3）每遍扫描时待比较元素的下标i（i=1,2,3,…n-j）
定义格式：
–类型标识符 数组名[一维数组个数][一维数组中元素 的个数]
用于描述冰山高度的二维数组的定义为：
–int ice[5][7]；
–上面语句定义了名为ice的数组，它包含5个一维数组， ice[0],ice[1]…ice[4]，每个一维数组含7个整型元
素。
二维数组是带两个下标的变量，第一个下标规定
h[4]=‘4’;

数组和矩阵的运算需要掌握运算法则


本节要求
1.掌握数组和矩阵的数值计算，尤其是数 组的“点运算” 2.掌握数组的关系和逻辑运算 3.掌握指令find的使用 4.了解notebook文档的编辑
本课件由飞华健康网/pifu/cc/编辑
>>A=[1 2 3; 4 5 6],B=[4,5,6;1,2,3]; >>C=zeros(2); %生成2阶全0方阵 >>c1=A+B ％加法运算 >>c2=A-C ％减法相乘 >>c3=A-2 %与标量之间的加减运算
结果如下：
c1 = 5 7
7 7
9 7
c3 = -1 2
0 3
1 4
??? Error using ==> minus Matrix dimensions must agree.
A =
>> A(～B)=0
13 8 12 1
A= 0 2 5 11 0 7 0 0 1 0 0 0 3 13 0 0 0 0 0 0
16 5 9 4
2 11 7 14
3 10 6 15
>> B=isprime(A)
B = 0 1 0 0 1 1 1 0 1 0 0 0
注：isprime是用来检测数值是否为质数。
log10 log2 exp pow2
例1：分析语句a=2+2==4的执行结果。
分析：单个等号表示赋值，后面的双等号表示关系 运算，所以a的值为1.
例2：分析语句a=‘fate’;b=‘cake’;result=a==b 的执行结果。
分析：应用关系运算应该逐个比较字符是否相等。 执行结果如下： result = 0 1 0 1
结果如下：

第四章_数组

22
4.2
多维数组
下列程序段实现对数组 int s[3][5]的动态赋值： 4.2.3 二维数组元素的引用 for(i=0; i<=2; i++) /* 行标i从0开始变化到2*/ 二维数组的元素也称为双下标变量，其表示的形式为： for(j=0; j<=4; j++) /* 列标j从0开始变化到4*/ 数组名 ][ 列下标 ] scanf( “%d”[ , 行下标 &s[i][j]) ； /*二维数组元素如同普通 其中下标应为整型常量或整型表达式，其取值范围从 整型变量操作*/ 0开始，分别到行数 -1和列数-1。 例如： a[3][4] 通过前面的学习，对数组也可以这样理解：单个变量描述 了空间中‚点‛的概念，一维数组是对单个变量的扩展，它描 表示a数组中行标为3,列标为4的元素。 述了空间中‚线‛的概念，而二维数组又对一维数组做了扩展， 如果要引用数组中的全部元素，只要利用循环语句即 描述了空间中‚平面‛的概念。人们可以模仿二维数组的使用 可实现，这是对数组中元素进行操作的基本算法。对于一 方法来实现多维数组等各种数据容器。例如，可用如下方法定 维数组，只需用单重循环就可完成；而对于二维数组则需 义三维数组: int a[2][3][4]； 要使用两重循环来完成，外循环控制行标变化，内循环控 多维数组元素在内存中的排列顺序为：第一维的下标变化 制列标变化。 最慢，最右边的下标变化最快。
20
s[0][3]
s[1][1] s[1][2]
……
4.2
多维数组
4.2.2 二维数组的初始化 二维数组初始化也是在类型说明时给各下标变量赋以初值。 二维数组可按行分段赋值，也可按行连续赋值。 例如对数组int s[3][5]： (1)按行分段赋值可写为: int s[3][5]={{80,75,92,61,65},{71,59,63,70,85},{87,90,76, 77,85}}； (2)按行连续赋值可写为: int s[3][5]={ 80,75,92,61,65,71,59,63,70,85,87,90,76,77, 85}； 这两种赋初值的结果是完全相同的。
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

（或空） 或空） 当i<j j 此时一维数组sa的数据元素个数为(n(n+1)/2)+1 sa的数据元素个数为(n(n+1)/2)+1个 注：此时一维数组sa的数据元素个数为(n(n+1)/2)+1个，其中数组 sa的最后一个位置存储 中数值不为0的那个常数。 的最后一个位置存储A sa的最后一个位置存储A中数值不为0的那个常数。
a０0的内存单元地址
每个元素所需的字节个数
a0,0 a0,1 … a0,n-1 a1,0 a1,1 … a1,n-1 Amn= … … … … am-1,0 am-1,1 … am-1,n-1
一个m× 的二维数组可以 一个 ×n的二维数组可以 看成是m行的一维数组 行的一维数组， 看成是 行的一维数组，或 列的一维数组。 者n列的一维数组。 列的一维数组
特殊矩阵压缩存储方式有两种: 特殊矩阵压缩存储方式有两种 1.只存储相同矩阵元素的一个副本； 只存储相同矩阵元素的一个副本； 只存储相同矩阵元素的一个副本 2.采用不等长的二维数组。 采用不等长的二维数组。 采用不等长的二维数组
（1）n阶对称矩阵 在一个n阶方阵A 在一个n阶方阵A中，若元素满足下述性质： 若元素满足下述性质： aij=aji 1 5 1 3 7 5 0 8 0 0 1 8 9 2 6 3 0 2 5 1 7 0 6 1 3 （1≦i,j≦n） 1≦i,j≦n） 则称A 则称A为n阶对称矩阵。下图是一个5阶对称矩阵。 阶对称矩阵。下图是一个5阶对称矩阵。 a11 a21 a 22 a31 a32 a33 ……………….. an1 an2 an3 …a nn
第4章 数组、集合和矩阵 章 数组、
4.1 数组 4.2 特殊矩阵 4.3 稀疏矩阵 4.4 集合
4.1 数组
4.1.1 数组的定义 数组是 （ 数组是n（n≥1）个相同数据类型的数据元素 ） a0,a1,a2,...,an-1构成的占用一块地址连续的内存单元的 构成的占用一块地址连续的内存单元 构成的占用一块地址连续的内存单元的 有限集合。 有限集合。
问题： 问题：数组与线性表的区别与联系
相同之处： 相同之处： 它们都是若干个相同数据类型的数据元素a 它们都是若干个相同数据类型的数据元素a0,a1,a2,…，an-1 相同数据类型的数据元素 ， 构成的有限序列。 构成的有限序列。 不同之处： 不同之处： (1)数组要求其元素占用一块地址连续的内存单元空间，而 (1)数组要求其元素占用一块地址连续的内存单元空间， 数组要求其元素占用一块地址连续的内存单元空间 线性表无此要求； 线性表无此要求； (2)线性表的元素是逻辑意义上不可再分的元素， (2)线性表的元素是逻辑意义上不可再分的元素，而数组中 线性表的元素是逻辑意义上不可再分的元素 元素还可以是一个数组； 的每个元素还可以是一个数组 的每个元素还可以是一个数组； (3)数组的操作主要是向某个下标的数组元素中存放数据和 (3)数组的操作主要是向某个下标的数组元素中存放数据和 数组的操作 取某个下标的数组元素，这与线性表的插入和删除操作不同。 取某个下标的数组元素，这与线性表的插入和删除操作不同。 不同
k=
i(i-1)/2+j-1 i(i-1)/2+jn(n+1)/2
当 i ≧j
2 采用不等长的二维数组 C#语言支持不等长的二维数组，对于n阶对称矩阵， 语言支持不等长的二维数组，对于 阶对称矩阵 阶对称矩阵， 语言支持不等长的二维数组 也可以通过只申请存储下三角（或上三角） 也可以通过只申请存储下三角（或上三角）矩阵元素 所需的二维数组，来达到压缩存储的目的。 所需的二维数组，来达到压缩存储的目的。 不等长的二维数组结构 int[][] a=new int[4][]; a[0]=new int[1]; a[1]=new int[2]; a[2]=new int[3]; a[3]=new int[4];
下标 0 1 1 4 7 2 5 8 3 6 9 1 2 3 4 5 6 7 8 9 第3行 第2行 第1行
下标 0 1 1 4 7 2 5 8 3 6 9 第3列 第2列 第1列
2
3 4 5 6 7 8
2
3 4 5 6 7 8
(a) 二维数组的逻辑结构
(b) 行优先顺序存储结构
(c) 列优先顺序存储结构
4.2 特殊矩阵
特殊矩阵是指这样一类矩阵， 特殊矩阵是指这样一类矩阵，其中有许多值相同 是指这样一类矩阵 的元素或有许多零元素， 的元素或有许多零元素，且值相同的元素或零元素的 分布有一定规律。 分布有一定规律。 一般采用二维数组来存储矩阵元素。但是，对于 一般采用二维数组来存储矩阵元素。但是， 特殊矩阵， 特殊矩阵，可以通过找出矩阵中所有值相同元素的数 学映射公式，只存储相同元素的一个副本， 学映射公式，只存储相同元素的一个副本，从而达到 压缩存储数据量的目的。 压缩存储数据量的目的。
二维数组的顺序存储结构
注：只要知道以下三要素便可随时求出任一元素的地址（意义： 只要知道以下三要素便可随时求出任一元素的地址（意义： 数组中的任一元素可随机存取） 数组中的任一元素可随机存取） 开始结点的存放地址（即基地址）； ①开始结点的存放地址（即基地址）； 维数和每维的上、下界； ②维数和每维的上、下界； ③每个数组元素所占用的单元数
i(i-1)/2+ji(i-1)/2+j-1 k=
（2）n阶三角矩阵
当 i ≧j 当i<j j
j(j-1)/2+ij(j-1)/2+i-1
以主对角线划分， 阶三角矩阵有n阶上三角矩阵和n 以主对角线划分， n阶三角矩阵有n阶上三角矩阵和n阶下三角矩阵 两种。 两种。 n阶上三角矩阵图(a)所示，它的下三角（不包括主对角线）中的元 阶上三角矩阵图(a)所示，它的下三角（不包括主对角线） (a)所示 素均为0 或常数）。 阶下三角矩阵正好相反， ）。n 素均为0（或常数）。n阶下三角矩阵正好相反，它的主对角线上方均为 或常数），如图(b)所示。 ），如图(b)所示 0（或常数），如图(b)所示。 注：在大多数情况下， n阶三角矩阵常数为零。 在大多数情况下， 阶三角矩阵常数为零。
n阶对称矩阵中的元素关于主对角线对称，故只要存储矩阵中上三 阶对称矩阵中的元素关于主对角线对称， 角或下三角中的元素，让每两个对称的元素共享一个存储空间，这样， 角或下三角中的元素，让每两个对称的元素共享一个存储空间，这样， 能节约近一半的存储空间。不失一般性，我们按“行优先顺序 顺序” 能节约近一半的存储空间。不失一般性，我们按“行优先顺序”存储主 对角线（包括对角线）以下的元素。 对角线（包括对角线）以下的元素。
数组的数据集合可以表示为a0, a1, a2, ..., an-1， 数据集合 数组的数据集合可以表示为 ， 且限定数组元素必须存储在地址连续的内存单元中。 限定数组元素必须存储在地址连续的内存单元中。 操作集合： 操作集合： （1）分配内存空间 ）分配内存空间acclocate()：为数组分配用户所需的内存 ： 空间。 空间。 （2）取数组长度 ）取数组长度getLength()：取数组的长度。 ：取数组的长度。 存入下标为i的数组中 （3）存数组元素 ）存数组元素set(i, x)：把数据元素 存入下标为 的数组中。 ：把数据元素x存入下标为 的数组中。 其约束条件为： 其约束条件为：0≤i≤getLength()-1。 。 的数据元素。 （4）取数组元素 ）取数组元素get(i)：取出数组中下标为 的数据元素。其 ：取出数组中下标为i的数据元素 约束条件为： 约束条件为：0≤i≤getLength()-1。 。
4.1.2 数组的实现机制
１、一维数组（n个元素）中任一元素ai的内存单元地址 一维数组（ 个元素）中任一元素a 一维数组 LOC(ai)=LOC(a０)+i*k (0≤i <n)
a０的内存单元地址
每个元素所需的字节个数
２、一个m行n列的二维数组 一个 行 列的二维数组 LOC(aij)=LOC(a00)+(i*n+j)*k (0≤i<m， 0≤j<n) ，
a11 a12 … a 1n c a22 … a 2n
a11 a21………………. c c … a nn
(a)上三角矩阵 (a)上三角矩阵
……………… an1 an2 … an n
(b)下三角矩阵 (b)下三角矩阵
假设以一维数组sa作为n阶下三角矩阵A的压缩存储单元， 假设以一维数组sa作为n阶下三角矩阵A的压缩存储单元，k为一维数 sa作为 va的下标序号 的下标序号， 阶下三角矩阵A 列的数据元素( 组va的下标序号，aij为n阶下三角矩阵A中i行j列的数据元素(其中 ），其数学映射关系为 其数学映射关系为： 1≦i,j≦n ），其数学映射关系为：
4.3 稀疏矩阵
对一个m× 的矩阵 的矩阵， 为矩阵元素个数的总和 为矩阵元素个数的总和， 对一个 ×n的矩阵，设s为矩阵元素个数的总和， 为矩阵中非零元素个数的总和， 有s=m*n，设t为矩阵中非零元素个数的总和，满足 ＜ ， 为矩阵中非零元素个数的总和 满足t＜ 的矩阵称作稀疏矩阵 ＜s的矩阵称作稀疏矩阵。符号“＜＜”读作小于小于。 的矩阵称作稀疏矩阵。符号“＜＜”读作小于小于。 简单说， 简单说，稀疏矩阵就是非零元素个数远远小于元素个 数的矩阵。相对于稀疏矩阵来说， 数的矩阵。相对于稀疏矩阵来说，一个不稀疏的矩阵 也称作稠密矩阵 稠密矩阵。 也称作稠密矩阵。
4.3.1 稀疏矩阵的压缩存储
稀疏矩阵的压缩存储方法， 稀疏矩阵的压缩存储方法，是只存储矩阵中的 方法 非零元素。 非零元素。 稀疏矩阵中每个非零元素及其对应的行下标和 列下标构成一个三元组，稀疏矩阵中所有这样的三 列下标构成一个三元组， 三元组 元组构成一个以三元组为数据元素的线性表。 元组构成一个以三元组为数据元素的线性表。
例１：一个二维数组A，行下标的范围是1到6，列下标的范围是0到7，每个数 一个二维数组A 行下标的范围是1 列下标的范围是0 组元素用相邻的6个字节存储，存储器按字节编址。那么， 组元素用相邻的6个字节存储，存储器按字节编址。那么，这个数组的体积 是