大学数据结构课件--第5章 数组和广义表

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

数 组
• 4．寻址公式的计算 • 下面考虑如何根据一组给定下标求出对应数组元素地址的 问题，这是数组最重要的基本操作，一般用在高级语言的 实现当中。这里只考虑n维数组按行存储的寻址公式的计算。 用秦九韶法变换按行存储公式中的主要部分： • j1d2d3…dn + j2d3…dn +…+jn–1dn + jn • =(j1d2+ j2)d3…dn + j3d4…dn +…+jn–1dn + jn • =((j1d2+ j2)d3+ j3)d4…dn + j4d5…dn +…+jn–1dn + jn • =… • =(…(j1d2+ j2)d3+ j3)d4+j4)d5+…+jn–1)dn+ jn • =(…((0×d1+j1)d2+ j2)d3+ j3) d4+j4)d5+…+jn–1)dn+ jn
数 组
• 1. 一维数组 • 一维数组的每个元素只含一个下标，其实质上是一个线性 表，存储方法与普通线性表的顺序存储方法完全相同，即 将数组元素按它们的逻辑次序存储在一片连续区域内。设 一维数组为A =(a0, a1,…, an–1)，则它的元素ai的相对地址为 Loc(ai) = i×c。这里，c表示每个元素占用的存储单元数目。
矩阵的压缩存储
• 矩阵是很多科学与工程计算问题研究的数学对象。在高级 语言程序设计中，常用二维数组来存储矩阵元素，有些程 序语言还提供了各种方便用户使用的矩阵运算。然而，对 于在数值分析中经常出现的一些阶数很高，且矩阵中有许 多值相同的元素或者是零元素的特殊矩阵，不适合用二维 数组来存放，因为这将造成大量存储空间的浪费。为了节 省存储空间，可对这类矩阵进行压缩存储，即为多个值相 同的元素只分配一个存储空间，对零元素不分配空间。

sa[k]与矩阵元素 aij之间的关系
7
i(i 1) / 2 j 1，i j k j ( j 1) / 2 i 1, i j
三角矩阵 a11 0 0 …….. 0
a21 a22
0 ……..
0
0
………………….
an1 an2 an3……..
按行序为主序：
0 0 0 0 0 14 0 0 0 0 0 0 0 0 0 0 67 0 0
3
4 5
data[0].i,data[0].j,data[0].e分别存放 矩阵行列维数和非零元个数
6
7 8
三元组表所需存储单元个数为3(t+1) 其中t为非零元个数
6
4 data
-7
16
如何求转置矩阵？
2
或ai是一个行向量形式的线性 ai =(ai1, ai2, ……, ain ) , 0 i m
(
( ( (
(
am2
... ... a1n ) ... ... a 2 n ) ... ... ... ) ... ... a mn )
) ) )
)
数组特点
数组结构固定 数据元素同构
#define MAXSIZE 12500 typedef struct { int i, j; //该非零元的行下标和列下标 ElemType e; // 该非零元的值 } Triple; // 三元组类型
typedef union { Triple data[MAXSIZE + 1]; //非零三元数组 int mu, nu, tu; //矩阵的行数、列数和非零单元个数 } TSMatrix; // 稀疏矩阵类型

a11 a12 ... a1n c a22 ... a2n ... ... ... ... c c c ann
a11 c ... c a21 a22 ... c ... ... ... ... an1 an2 ... ann
（a）上三角矩阵 （b）下三角矩阵 显然对三角矩阵的压缩存储可采用和对称矩阵 一样的方法。
由此，我们称sa[n(n+1)/2] 为n阶对称矩阵A 的压缩存储。
13
5.3.1 特殊矩阵
2．三角矩阵
a. 上三角矩阵 即矩阵上三角部分元素是随机的，而下三
角部分元素全部相同（为某常数C）或全为0， 具体形式见下图a。 b.下三角矩阵
与上三角矩阵相反，见下图b。
14
5.3.1 特殊矩阵
1 . 一维数组 一维数组可以看成是一个线性表，它在计算机
内是存放在一块连续的存储单元中，适合于随 机查找。
2
5.1 数组的定义
2．二维数组 如下图中，A是一个m行n列的二维数组. 二维数组也可以看成是一个定长的线性表.
a
00
a
01
…
a
10
a
11
…
a
0,n-1
aቤተ መጻሕፍቲ ባይዱ
1,n-1
A= … … …
aa
m-1,0 m-1,1
…
… a
m-1,n-1
3
5.1 数组的定义
则A可以表示为这样一个线性表： A=(a0,a1,…,an-1)
其中每个数据元素aj可以是一个列向量形式的 线性表:
aj= ( a0j, a1j, …, am-1,j)
(0≤j≤n-1）
4
5.1 数组的定义