第8章 数组(汪同庆)

A、j(j-1)/2+i-1 B、j(j-1)/2+i C、j(j+1)/2+i-1 D、 j(j+1)/2+i
数据结构（Java版）》叶核亚
5.2.2 稀疏矩阵的压缩存储
表示稀疏矩阵的三元组
0 0 11 0 17 0
0
20
0
0
0
0
行号 row
列号 column
元素值 value
A56
0 19
设矩阵A是一个对称矩阵，为了节省空间，将其下三角部分 按行优先存放在一维数组B中。对下三角矩阵中任一元素 aij(i>=j,j>=1)，在一维数组B中下标K的值是：
A、i(i-1)/2+j-1 B、i(i-1)/2+j C、i(i+1)/2+j-1 D、 i(i+1)/2+j
设矩阵A是一个对称矩阵，为了节省空间，将其上三角部分 按列优先存放在一维数组B中。对上三角矩阵中任一元素 aij(i<=j,i>=1)，在一维数组B中下标K的值是：
1．多维数组的逻辑结构
数据结构（Java版）》叶核亚
5.1.2 多维数组
2．多维数组的遍历
（1）行优先次序
a1,1 a1,2 a1,n
Amn
a2,1
am,1
a2,2 am,2
a2,n
am,n
a1,1，a1,2，…，a1,n，a2,1，a2,2，…， a2,n，…，am,1，am,2，…，am,n
常见的广义表为：
L＝(a，b)
//线性表，长度为2 ，深度为1
T＝(c，L)＝(c，(a，b)) //L为T的子表，T的长度为2 ， 深度为2

• 如果已有多个元素拍序，则自右向左逐个与已排序元素进行比较，然后将已 排序元素向后移动，直到已排序元素小于下一个元素，将下一个元素插入到
第3步 小于它的后面。
• 再取下一个元素，重复上述步骤，直到所有元素都排序完毕。
第4步
5.2 一维数组
• 5.2.3 一维数组的常见操作
5、一维数组的排序—插入排序
例5-5所示。
将n个数存入数组中
i<n-1 真
数组[i]>数组[i+1]
假 假
结束
真 交换两个元素
i++
5.2 一维数组
• 5.2.3 一维数组的常见操作
5、一维数组的排序——插入排序
− 所谓插入排序法，就是每一步将一个待排序元素插入到已经排序的元素中 的适当位置，直到全部插入完毕。
9
8
3
5
2
i=1 8
• 对部分数组元素赋初值 • int b[3][4] = {{1},{4,3},{2,1,2}};
• 对全部数组元素置初值，则第一个下标可省略 • int a[ ][3] = {1,2,3,4,5,6};
5.3 二维数组
• 5.3.2 二维数组的引用
− 二维数组的引用方式同一维数组的引用方式一样，也是通过数组名和下 标的方式来引用数组元素，其语法格式如下：
5.5 进阶案例（一）
• 斐波那契数列
− 在第四章，曾用递归实现了斐波那契数列，其实用数组也可以实现。其递 归的规律为当前项是前两项的和，则可以考虑用一维数组来实现。如例512所示，用数组来计算斐波那契数列的前20项。
5.6 进阶案例（二）
• 杨辉三角
−为了大家更好的掌握数组在实际开发中的应用，接下来通过一个打印杨辉三角

5.2.3
一“实”多“名”带来的困惑
数组变量最容易给我们带来的困惑有两个：一是容易 让人错误的觉得赋值时创建了一个数组；二是数组变量的赋 值容易让人误认为是数组元素的赋值。
数组
0 1 2 3 4
数组 数组的名字： students
0 1 2 3
55 66 77 88 99
55 66 77 88 99
数组变量 classOne 数组
0 1 2 3
0 0 0 0 0
数组 数组变量 gradeStudents[0]
0
4
数组变量 gradeStudents 数组变量 gradeStudents[1]
0 1 2 3 4
数组 0 0 0 0 0
1
5.3.2
多维数组的实质
图5-12 给classOne[0]赋值88后的状态
5.1.5
创建数组的简洁语法
本小节中我们来学习一下创建数组的另一种语法。首先我们看下面的例程。 public class CreateArrayII { public static void main(String[] args) { int[] students = { 55, 66, 77, 88, 99 }; // 创建数组，并完成了数组元素的 赋值 System.out.println("第1位学生的分数是：" + students[0]); System.out.println("第3位学生的分数是：" + students[2]); System.out.println("第5位学生的分数是：" + students[4]); } } 上面例程中的第一行向我们展示了另一种创建数组的方式。代码“{ 55, 66, 77, 88, 99 }”完成了创建数组和给数组元素赋值两个过程。当我们明确的知道数组中 的值时，就可以使用这种语法。这种语法的规则就是“{”+“数组中的元素值，中间 用逗号隔开”+“}”。

教学重点：1、 数组的概念及顺序存储结构。

2、 稀疏矩阵的转置矩阵。

教学难点：稀疏矩阵的转置矩阵 授课内容2.6 数组2.6.1 数组的基本概念数组是一种常用对数据结构，几乎所有的程序设计语言都把数组类型设定为固有类型。

计算机系统的内存是连续的空间，为了方便的存取处理大量的相关性数据，我们定义一种“连续的存储区域”，并使用一个名称指向此区域的起点，通过名称及偏移的方式，可以很容易的存取到该区域内的数据，此即为数组。

数组 是由下标（index ）和值（value ）组成的序对（indexvalue pairs ）集合。

简单地讲，数组就是按一定格式排列起来的一列同一属性的项目,是相同类型的数据元素的集合。

我们经常使用数组来存放一连串数据类型相同的数据。

因此，数组具有两个特性是：1. 数组中的元素间的地址是连续的。

2. 数组中所有元素的数据类型是相同的。

数组的类型有一维数组A[10]、二维数组A[5][6]、三维数组A[3][5][5]、多维数组等。

数组元素 在数组中，对于每组有定义的下标，都存在一个与其相对应的值，这个值通常称为数组元素。

二维数组：每一行都是一个线性表，每一个数据元素既在一个行表中，又在一个列表中。

在c 语言中，其被定义为：ELEMTP arrayname[row][col]；在二维数组中，每个元素都受到行关系和列关系的约束，例如有一个而外数组A[m][n]，对于第i 行第j 列的元素A[i][j]，A[i][j+1]是该元素在行关系中的直接后继元素；而A[i]+1[j]是该元素在列关系中的直接后继元素。

所以，可以把二维数组看成是一个一维数组，它有row 个元素，每个数据元素又是一个col 个数据元素的一维数组。

对数组一般讨论下面两种运算：第七讲 数组给定一组有定义的下标，存取相应的数据元素；给定一组有定义的下标，修改相应数据元素（或其中的某个数据项）的值。

2.6.2 数组的顺序存储结构数组是一顺序存储方式在计算机中的，而随机存取是顺序存储结构的主要特征。