第 4章 串和数组（二） 本讲主要内容： 数组的定义及其顺序表示和实现。 矩阵的压缩存储。 广义表的定义。

Presentation on theme: "第 4章 串和数组（二） 本讲主要内容： 数组的定义及其顺序表示和实现。 矩阵的压缩存储。 广义表的定义。"— Presentation transcript:

1 第 4章 串和数组（二） 本讲主要内容： 数组的定义及其顺序表示和实现。 矩阵的压缩存储。 广义表的定义。

2 1.1 数组的定义和特点 数组可以看成是一种特殊的线性表，即线性表中数据元素本身也是一个线性表 定义:数组是有序数据的集合。 数组特点
数组结构固定 数据元素同构 数组运算 给定一组下标，存取相应的数据元素 给定一组下标，修改数据元素的值 ( ) ( )

3 1.2 数组的顺序存储结构 次序约定 a11 a12 …….. a1n a11 a12 …….. a1n a21 a22 …….. a2n
以行序为主序 以列序为主序 a a12 …….. a1n a a22 …….. a2n am1 am2 …….. amn …………………. Loc( aij)=Loc(a11)+[(i-1)n+(j-1)]*l   按行序为主序存放 amn …….. am2 am1 ………. a2n a22 a21 a1n ……. a12 a11 1 n-1 m*n-1 n   按列序为主序存放 1 m-1 m*n-1 m amn …….. a2n a1n ………. am2 a22 a12 am1 ……. a21 a11 a a12 …….. a1n a a22 …….. a2n am1 am2 …….. amn …………………. Loc(aij)=Loc(a11)+[(j-1)m+(i-1)]*l

4 2矩阵的压缩存储 矩阵可以用二维数组来表示。压缩存储的基本思想是：值相同的多个元素只分配一个存储空间，零元素不分配空间。
特殊矩阵：值相同的元素和零元素在矩阵中的分布有一定规律。 对称矩阵 三角矩阵 对角矩阵 稀疏矩阵

5 2 矩阵的压缩存储 2.1对称矩阵 a11 a12 …. … ….. a1n a21 a22 …….. ……. a2n ………………….
an1 an2 …… ann …………………. a11 a21 a22 a31 a an ann …... k= n(n-1)/ n(n+1)/2-1 按行序为主序：

6 2.2三角矩阵 以主对角线划分，三角矩阵有上三角和下三角两种。 上三角矩阵如图所示，它的下三角（不包括主对角线） 中的元素均为常数。下三角矩阵正好相反，它的主对 角线上方均为常数，如图所示。在大多数情况下， 三角矩阵常数为零。 a11 a12 … a 1n a11 c … c c a21 … a 2 n a21 a22 … c ………………… …………….. c c … a n n an1 an2 … ann (a)上三角矩阵 (b)下三角矩阵

7 a11 C C …….. C a21 a22 C …….. C …………………. C an1 an2 an3…….. ann
2.3下三角矩阵 按行序为主序： a11 a21 a22 a31 a an ann c …... …... k= n(n-1)/ n(n+1)/2

8 2.4上三角矩阵 a11 a12 … a 1n c a21 … a 2 n ………………….. c c … a n n 按行序为主序：
a11 a12 a13 a14 a a1n ann c …... …... k= (n-1) n(n+1)/2

9 2.5对角矩阵 对角矩阵中，所有的非零元素集中在以主对角线为了中心的带状区域中，即除了主对角线和主对角线相邻两侧的若干条对角线上的元素之外，其余元素皆为零。 a a …………… a a a …………… 0 … an-1,n an-1,n-1 an-1,n … …an,n ann. a a33 a ……… 0 ……………………………

10 2.6稀疏矩阵 定义：非零元较零元少，且分布没有一定规律的矩阵 压缩存储原则：只存矩阵的行列维数和每个非零元的行列下标及其值
M由{(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）唯一确定

11 稀疏矩阵的压缩存储方法 顺序存储结构 三元组表 #define M 20 typedef struct node { int i,j;
int v; }JD; JD ma[M]; 行列下标 非零元值 ma i j v ma[0].i,ma[0].j,ma[0].v分别存放 矩阵行列维数和非零元个数 三元组表所需存储单元个数为3(t+1) 其中t为非零元个数

12 带辅助行向量的二元组表 增加一个辅助数组NRA[m+1],其物理意义是第i行第一个非零元 在二元组表中的起始地址（m为行数） 显然有：
NRA[i]=NRA[i-1]+第i-1行非零元个数(i2) ma j v 矩阵列数和 非零元个数 列下标和 非零元值 NRA NRA[0]不用或 存矩阵行数 6 1 3 3 5 6 7 二元组表需存储单元个数为2(t+1)+m+1

13 伪地址表示法 伪地址：本元素在矩阵中（包括零元素在内） 按行优先顺序的相对位置 伪地址 非零元值 addr v
ma addr v 伪地址 非零元值 矩阵行列维数 伪地址表示法需存储单元个数 为2(t+1)

14 设置一个行指针数组，指向本行第一个非零元结点；若本行无非零元，则指针为空 表头结点与单链表结点类型定义
链式存储结构 带行指针向量的单链表表示 每行的非零元用一个单链表存放 设置一个行指针数组，指向本行第一个非零元结点；若本行无非零元，则指针为空 表头结点与单链表结点类型定义 typedef struct node { int col; int val; struct node *link; }JD; typedef struct node *TD; ^ 需存储单元个数为3t+m

15 设行指针数组和列指针数组，分别指向每行、列第一个非零元 结点定义
十字链表 设行指针数组和列指针数组，分别指向每行、列第一个非零元 结点定义 row col val down right tpedef struct node { int row,col,val; struct node *down, *right; }JD; 1 3 4 8 2 5 ^ ^ ^ ^ ^ ^ ^

16 3.广义表的定义 广义表是线性表的推广 广义表一般记作： LS=(a1，a2，…，an)
其中：LS为广义表的名称；n为其长度；ai可以是单个元 素，也可以是广义表分别对应LS的原子和子表。 注：① 习惯上，大写字母表示广义表的名称，小写字母表示原子 ② LS非空时，称第一个元素a1为LS的表头（Head），其余元素组成的表(a2，a3，…，an)为LS的表尾（Tail） 16/

17 3.广义表的定义 结论： 例如： A =( ) 空表，长度为0 B =(e) 表只有一个原子e，长度为1
C =(a,(b,c,d)) 表包含一个原子a和子表(b,c,d)，长度为2 D =(A,B,C) 长度为3，3个元素都是列表 E =(a,E) E为递归表，长度为2 结论： 列表的元素可以是子表，子表的元素还可以是子表……； 列表可以为其他列表所共享，如D中的A、B、C； 列表可以是递归的表，即列表可以是其本身的一个子表。 17/

18 3.广义表的定义 说明： 任何一个非空列表的表头可能是原子，也可能是列表，而其表尾必定为列表 求表头和表尾：
GetHead (B) =e GetTail(B) =( ) GetHead (D) =(A) GetTail(D) =(B,C) GetHead((B,C)) =B GetTail((B,C))=(C) 注：列表( )和(( ))是不同的，前者为空表，长度为0；后者长度为1，其表头、表尾均为空表。 18/

19 小结 矩阵的压缩存储 广义表的定义 19/

20 作业 实现普通矩阵的转置操作以及三元组表示的矩阵的转置操作。 20/