第 4章 串和数组（二） 本讲主要内容： 数组的定义及其顺序表示和实现。 矩阵的压缩存储。 广义表的定义。
1.1 数组的定义和特点 数组可以看成是一种特殊的线性表，即线性表中数据元素本身也是一个线性表 定义:数组是有序数据的集合。 数组特点 数组结构固定 数据元素同构 数组运算 给定一组下标，存取相应的数据元素 给定一组下标，修改数据元素的值 ( ) ( )
1.2 数组的顺序存储结构 次序约定 a11 a12 …….. a1n a11 a12 …….. a1n a21 a22 …….. a2n 以行序为主序 以列序为主序 a11 a12 …….. a1n a21 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 a11 a12 …….. a1n a21 a22 …….. a2n am1 am2 …….. amn …………………. Loc(aij)=Loc(a11)+[(j-1)m+(i-1)]*l
2矩阵的压缩存储 矩阵可以用二维数组来表示。压缩存储的基本思想是：值相同的多个元素只分配一个存储空间，零元素不分配空间。 特殊矩阵：值相同的元素和零元素在矩阵中的分布有一定规律。 对称矩阵 三角矩阵 对角矩阵 稀疏矩阵
2 矩阵的压缩存储 2.1对称矩阵 a11 a12 …. … ….. a1n a21 a22 …….. ……. a2n …………………. an1 an2 …….. ann …………………. a11 a21 a22 a31 a32 an1 ann …... k=0 1 2 3 4 n(n-1)/2 n(n+1)/2-1 按行序为主序：
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)下三角矩阵
a11 C C …….. C a21 a22 C …….. C …………………. C an1 an2 an3…….. ann 2.3下三角矩阵 按行序为主序： a11 a21 a22 a31 a32 an1 ann c …... …... k=0 1 2 3 4 n(n-1)/2 n(n+1)/2
2.4上三角矩阵 a11 a12 … a 1n c a21 … a 2 n ………………….. c c … a n n 按行序为主序： a11 a12 a13 a14 a15 a1n ann c …... …... k=0 1 2 3 4 (n-1) n(n+1)/2
2.5对角矩阵 对角矩阵中，所有的非零元素集中在以主对角线为了中心的带状区域中，即除了主对角线和主对角线相邻两侧的若干条对角线上的元素之外，其余元素皆为零。 a11 a12 0 …………… . 0 a21 a22 a23 0 …………… 0 0 0 … an-1,n-2 an-1,n-1 an-1,n 0 0 … …an,n-1 ann. 0 a32 a33 a34 0 ……… 0 ……………………………
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）唯一确定
稀疏矩阵的压缩存储方法 顺序存储结构 三元组表 #define M 20 typedef struct node { int i,j; int v; }JD; JD ma[M]; 行列下标 非零元值 ma i j v 0 1 2 3 4 5 6 7 8 6 7 8 1 2 12 ma[0].i,ma[0].j,ma[0].v分别存放 矩阵行列维数和非零元个数 1 3 9 3 1 -3 3 6 14 4 3 24 三元组表所需存储单元个数为3(t+1) 其中t为非零元个数 5 2 18 6 1 15 6 4 -7
带辅助行向量的二元组表 增加一个辅助数组NRA[m+1],其物理意义是第i行第一个非零元 在二元组表中的起始地址（m为行数） 显然有： NRA[i]=NRA[i-1]+第i-1行非零元个数(i2) 7 8 2 12 3 9 1 -3 6 14 3 24 2 18 1 15 4 -7 ma j v 0 1 2 3 4 5 6 7 8 矩阵列数和 非零元个数 列下标和 非零元值 0 1 2 3 4 5 6 NRA NRA[0]不用或 存矩阵行数 6 1 3 3 5 6 7 二元组表需存储单元个数为2(t+1)+m+1
伪地址表示法 伪地址：本元素在矩阵中（包括零元素在内） 按行优先顺序的相对位置 伪地址 非零元值 addr v 6 7 2 12 3 9 15 -3 20 14 24 24 30 18 36 15 39 -7 ma addr v 伪地址 非零元值 矩阵行列维数 0 1 2 3 4 5 6 7 8 伪地址表示法需存储单元个数 为2(t+1)
设置一个行指针数组，指向本行第一个非零元结点；若本行无非零元，则指针为空 表头结点与单链表结点类型定义 链式存储结构 带行指针向量的单链表表示 每行的非零元用一个单链表存放 设置一个行指针数组，指向本行第一个非零元结点；若本行无非零元，则指针为空 表头结点与单链表结点类型定义 typedef struct node { int col; int val; struct node *link; }JD; typedef struct node *TD; ^ 1 3 5 7 3 -1 1 -1 2 -2 4 2 需存储单元个数为3t+m
设行指针数组和列指针数组，分别指向每行、列第一个非零元 结点定义 十字链表 设行指针数组和列指针数组，分别指向每行、列第一个非零元 结点定义 row col val down right tpedef struct node { int row,col,val; struct node *down, *right; }JD; 1 3 4 8 2 5 ^ ^ ^ ^ ^ ^ ^
3.广义表的定义 广义表是线性表的推广 广义表一般记作： LS=(a1，a2，…，an) 其中：LS为广义表的名称；n为其长度；ai可以是单个元 素，也可以是广义表分别对应LS的原子和子表。 注：① 习惯上，大写字母表示广义表的名称，小写字母表示原子 ② LS非空时，称第一个元素a1为LS的表头（Head），其余元素组成的表(a2，a3，…，an)为LS的表尾（Tail） 16/
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/
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/
作业 实现普通矩阵的转置操作以及三元组表示的矩阵的转置操作。 20/