第五章 数组和广义表 ￡5.1 数组 ￡5.2 矩阵的压缩存储 ￡5.3 广义表 ￡5.1.1 数组的定义 ￡5.2.1 特殊矩阵

Presentation on theme: "第五章 数组和广义表 ￡5.1 数组 ￡5.2 矩阵的压缩存储 ￡5.3 广义表 ￡5.1.1 数组的定义 ￡5.2.1 特殊矩阵"— Presentation transcript:

1 第五章 数组和广义表 ￡5.1 数组 ￡5.2 矩阵的压缩存储 ￡5.3 广义表 ￡5.1.1 数组的定义 ￡5.2.1 特殊矩阵
第五章 数组和广义表 ￡5.1 数组 ￡5.2 矩阵的压缩存储 ￡5.1.1 数组的定义 ￡5.2.1 特殊矩阵 ￡5.1.2 数组的顺序存储结构 ￡5.2.2 稀疏矩阵 ￡5.3 广义表 ￡5.3.1 广义表的定义 ￡5.3.2 广义表的存储结构

2 ￡5.1 数组 ￡5.1.1 数组的定义 数组：是线性表的推广。其每一个元素都是由一个（组）值及一组下标
组成。对于每组有定义的下标，都存在一个元素与之对应。当元素具有n个下 标时，该数组称为n维数组。 我们可以把二维数组看成是这样一个定长的线性表：它的每个数据元素 也是一个定长线性表。 例，设有二维数组A(m×n)＝ 以m行n列的矩阵形式表示。 每个元素均由一个（组）值及一组（2个）下标构成。任何有定义的下标 组（i，j），只要1≤i≤m，1≤j≤n，均有一个元素 与之对应。每个数据元 素 都受两个关系（ROW行关系和COL列关系）的约束。在行关系中 是 的直接后继元素。在列关系中 是 的直接后继元素。该数组元素 的个数为m×n个。 这里主要讨论二维数组

3 … 同理，n维数组中含有 个数据元素。每个数据元素都受着n个关系的约束， 。在每个关系中，元素 （1≤ji≤bi－1）都 都对应于一组下标
二维数组A(m×n)可以看成是一个线性表： （p＝m或n）。 其中每个数据元素 1≤j≤n 是一个列向量形式的线性表（如图5.1(a)所示）： 是一个行向量形式的线性表（如图5.1(b)所示）： 1≤i≤m 或者 … A(m×n)＝ (a) 列向量的一维数组

4 A(m×n)＝ (b) 行向量的一维数组 图5.1 二维数组图例 在C语言中，一个二维数组类型可以定义为其分量类型为一维数组类型的一维 数组类型，也就是说，typedef ElemType Array2[m][n]；等价于： typedef ElemType Array1[n]； typedef Array1 Array2[m]; 同理，一个n维数组 类型可以定义为其数据元素为n－1维数组的一维数组类型。 ADT Array { 数据对象：ji = 0, … ,bi－1, i = 1, 2, … ,n D={ ∈ElemSet} 数据关系：R ＝ { R1, R2, … , Rn} Ri = {< >| , 1≤jk≤bk，1≤k≤n 且k≠i， 1≤ji≤bi－1， ∈D,i=2,…,n} | n(>0)称为数组的维数，bi是数组第i维的长度， ji是数组元素的第i维下标，

5 基本操作： Init Array (&A, n, bound1, … , boundn) 操作结果：若维数n和各维长度合法，则构造相应的数组A， 并返回OK。 Destroy Array (&A) 操作结果：销毁数组A。 Value (A, &e, index1, … , indexn) 初始条件：A是n维数组，e为元素变量，随后是n个下标值。 操作结果：若各下标不超界,则e赋值为所指定的A的元素值， Assign (&A, e, index1, … , indexn) 操作结果：若下标不超界，则将e的值赋给所指定的A的元素 值，并返回OK。 }ADT Array

6 ￡5.1.2 数组的顺序存储结构 （1）求址公式 数组一旦建立，其结构中的数据元素个数和元素之间的关系就不再发生变
动，一般不作插入或删除操作。故大多数情况下都用顺序存储结构表示数组。 由于顺序存储结构是一维的结构，而数组是个多维的结构，用一组连续存 储单元存放数组的数据元素就有个次序约定问题。即，以行序为主序 （row major order）的存储方式和以列序为主序（column major order） 的存储方式（如图5.2所示，以二维数组为例）。 ①以行序为主序的存储方式：BASIC, PASCAL, PL/1, COBOL和C语言等。 ②以列序为主序的存储方式：FORTRAN语言等。

7 (a) 以列序为主序 (b) 以行序为主序 图5.2 二维数组的两种存储方式 a10 a01 a11 a11 am-1,1 a1,n-1
LOC(A0(1))＝LOC(a00) a LOC(A0(1))＝LOC(a00) a00 a a01 am-1, a0,n-1 LOC(A1(1))＝LOC(a01) a LOC(A1(1))＝LOC(a10) a10 a a11 am-1, a1,n-1 LOC(An-1(1))=LOC(a0,n-1) a0,n LOC(Am-1(1))=LOC(am-1,0) am-1,0 a1,n am-1,1 am-1,n am-1,n-1 (a) 以列序为主序 (b) 以行序为主序 图5.2 二维数组的两种存储方式

8 假设每个数据元素占L个存储单元，则二维数组A中任一元素aij的存储位置可由
以行序为主序的求址公式： 假设每个数据元素占L个存储单元，则二维数组A中任一元素aij的存储位置可由 下式确定： LOC(i, j) = LOC(0, 0) + (b2×i + j)L 式中，LOC(i, j)是aij的存储位置，LOC(0, 0)是a00的存储位置，即二维数组A的起始 存储位置，也称为基地址或基址。b2是数组第二维的长度，即数组A(m×n)中的列 数n。 可缩写成： 其中cn＝L，ci－1＝bi×ci，1≤i≤n。 将上式推广到一般情况，可得到n维数组的数据元素存储位置的计算公式： 由上易知，数组元素的存储位置是其下标的线性函数，一旦确定了数组的各维 长度，ci就是常数。由此，对于数组，一旦规定了它的维数和各维的长度，便可为 它分配存储空间。只要给出一组下标便可求得相应数组元素的存储位置。由于计算 各个元素存储位置的时间相等，所以存取数组中任一元素的时间也相等。我们称具 有这一特点的存储结构为随机存储结构。

9 （2）数组的顺序存储表示和实现 // 数组的顺序存储表示 #include <stdarg.h> //标准头文件，提供宏va_start、vz_arg和va_end, //用于存取变长参数表 #define MAX_ARRAY_DIM 8 //假设数组最大维数为8 typedef struct { ElemType *base; //数组元素基址，由InitArray分配 int dim; //数组维数 int *bounds; //数组维界基址，由InitArray分配 int *constants; //数组映像函数常量基址，由InitArray分配 } Array; // 基本操作的函数原型说明 Status InitArray (Array &A, int dim, …); //若维数dim和随后的各维长度合法，则构造相应的数组A，并返回OK。 Status DestroyArray (Array &A)； //销毁数组A。 Status Locate (Array A, va_list ap, int &off); //若ap指示的各下标值合法，则求出该元素在A中相对地址off Status Value (Array &A, ElemType &e, …); //A是n维数组，e为元素变量，随后是n个下标值。 //若各下标不超界，则e赋值为所指定的A的元素值，并返回OK。

10 Status Assign (Array &A, ElemType &e, …);
//A是n维数组，e为元素变量，随后是n个下标值。 //若各下标不超界，则将e的值赋给所指定的A的元素，并返回OK。 // 基本操作的算法描述 Status InitArray (Array &A, int dim, …) { //若维数dim和各维长度合法，则构造相应的数组A，并返回OK。 if (dim < 1 | | dim > MAX_ARRAY_DIM) return ERROR; A.dim = dim; A.bounds = (int *) malloc (dim * sizeof(int)); if (!A.bounds) exit (OVERFLOW); //若各维长度合法，则存入A.bounds，并求出A的元素总数elemtotal elemtotal = 1; va_start (ap, dim); //ap为va_list类型，是存放变长参数表信息的数组 for (i = 0; i < dim; ++i) { A.bounds[i] = va_arg(ap, int); if (A.bounds[i] < 0) return UNDERFLOW; elemtotal * = A.bounds[i]; }

11 va_end (ap); A.base = (ElemType *) mallo c(elemtotal * sizeof (ElemType)); if (!A.base) exit (OVERFLOW); //求映像函数的常数c，并存入A.constants[i－1]，i＝1, … , dim A.constants = (int *) mallo c(dim * sizeof (int)); if (!A.constants) A.constants[dim－1] = 1; //L＝1，指针的增减以元素的大小为单位 for (i = dim－2; i >= 0; ――i) A.constants[i] = A.bounds[i+1] *A.constants[i+1]; return OK; } // InitArray

12 Status DestroyArray (Array &A) {
if (!A.base) return ERROR; free (A.base); A.base = NULL; if (!A.bounds) free (A.bounds); A.bounds = NULL; if (!A.constants) free (A.constants); A.constants = NULL; return OK; } // DestroyArray

13 Status Locate (Array A, va_list ap, int &off) {
//若ap指示的各下标值合法，则求出该元素在A中相对地址off off = 0; for (i = 0; i < A.dim; ++i) { ind = va_arg (ap, int); if (ind <0| | ind >= A.bounds[i]) return OVERFLOW; off += A.constants[i] * ind; } return OK; } // Locate Status Value (Array &A, ElemType &e, …); //A是n维数组，e为元素变量，随后是n个下标值。 //若各下标不超界，则e赋值为所指定的A的元素值，并返回OK。 va_start (ap, e); if ((result = Locate (A, ap, off)) <= 0) return result; e = *(A.base + off); return OK; } // Value

14 Status Assign (Array &A, ElemType &e, …);
//A是n维数组，e为元素变量，随后是n个下标值。 //若各下标不超界，则将e的值赋给所指定的A的元素，并返回OK。 va_start (ap, e); if ((result = Locate (A, ap, off)) <= 0) return result; *(A.base + off) = e; return OK; } // Assign

15 ￡5.2 矩阵的压缩存储 ￡5.2.1 特殊矩阵 压缩存储：为多个值相同的元只分配一个存储空间；对零元不分配空间。
特殊矩阵：值相同的元素或者零元素在矩阵中的分布有一定规律的矩阵。 （1）对称矩阵 ①定义 若n阶矩阵A中的元满足下述性质： aij＝aji 1≤i，j≤n 则称为n阶对称矩阵。 例如，4阶对称矩阵A＝ ②压缩存储 为每一对对称元分配一个存储空间，则可将 个元压缩存储到n(n+1)/2 个元的空间中。我们以行序为主序存储其下三角（包括对角线）中的元。

16 假设以一维数组sa[n(n+1)/2]作为n阶对称矩阵A的存储结构，则sa[k]和矩阵 元aij之间存在着一一对应的关系。
a a21 a a an, an,n k = 图5.3 对称矩阵的压缩存储 k ＝ 当i≥j 当i<j 对于任意给定一组下标(i, j)，均可在sa中找到矩阵元aij，反之，对所有的 k = 0, 1, 2, … , n(n+1)/2－1，都能确定sa[k]中的元在矩阵中的位置(i, j)。

17 （2）上（下）三角矩阵 ①定义 上（下）三角矩阵：是指矩阵的上（下）三角（不包括对角线）中的 元均为常数c或零的n阶矩阵。 ②压缩存储 对称矩阵的压缩存储方法也适用于三角矩阵。除了和对称矩阵一样， 只存储其上（下）三角中的元之外，再加一个存储常数c的存储空间即可。 （3）对角矩阵 ①定义 对角矩阵：是指所有的非零元素都集中在以主对角线为中心的带状 区域中的矩阵。即除了主对角线上和直接在对角线上、下方若干条对角 线上的元之外，所有其他的元皆为零。

18 对这种矩阵，我们也可按某个原则（或以行为主，或以对角线的顺序） 将其压缩存储到一维数组上。
a条对角线 n行 n列 a00 a01 a10 a11 a12 an-2,n-1 an-1,n-2 an-1,n-1 (a) 一般情形 (b) 三对角矩阵 图5.4 对角矩阵 ②压缩存储 对这种矩阵，我们也可按某个原则（或以行为主，或以对角线的顺序） 将其压缩存储到一维数组上。 总之，在上述这些特殊矩阵中，非零元的分布 都有一个明显的规律，从而我们都可将其压缩存 储到一维数组中，并找到每个非零元在一维数组 中的对应关系。

19 ￡5.2.2 稀疏矩阵 （1）定义 稀疏矩阵：矩阵的非零元较多，且其分布没有一个明显的规律。这是一 个要凭直觉来了解的概念。 稀疏因子δ：
，其中，t为不为零或常数c的元素的个数； 稀疏因子δ： m×n是矩阵的规模。通常认为δ≤0.05时称为稀疏矩阵。 稀疏矩阵的抽象数据类型定义： ADT SparseMatrix { 数据对象：D={ aij | i=1,2,…,m; j=1,2,…,n; ai,j∈ElemSet, m和n分别称为矩阵的行数和列数} 数据关系：R＝{Row, Col} Row＝{< ai,j, ai,j+1 > | 1≤i≤m, 1≤j≤n－1} Col = {< ai,j, ai+1,j > | 1≤i≤m－1, 1≤j≤n} 基本操作： CreateSMatrix (&M); 操作结果：创建稀疏矩阵M。 DestroySMatrix (&M); 初始条件：稀疏矩阵M已存在。 操作结果：销毁稀疏矩阵M。

20 PrintSMatrix (M); 初始条件：稀疏矩阵M已存在。 操作结果：输出稀疏矩阵M。 CopySMatrix (M, &T); 操作结果：有稀疏矩阵M复制得到T。 AddSMatrix (M, N, &Q); 初始条件：稀疏矩阵M与N的行数和列数对应相等。 操作结果：求稀疏矩阵的和Q=M+N。 SubSMatrix (M, N, &Q); 操作结果：求稀疏矩阵的差Q=M－N。 MultSMatrix (M, N, &Q); 操作结果：求稀疏矩阵的乘积Q=M×N。 TransposeSMatrix (M, &T); 操作结果：求稀疏矩阵M的转置矩阵T。 }ADT SparseMatrix

21 （2）压缩存储 进行压缩存储时，我们只存储稀疏矩阵的非零元，同时记下它所在行 和列的位置(i, j)。一个三元组(i, j, aij )唯一确定了矩阵A的一个非零元。由 此，稀疏矩阵可由表示非零元的三元组及其行列数唯一确定。 例：矩阵M，加上(6, 7)这一对行、列值便可用下列三元组表描述。 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) )

22 三元组顺序表：以顺序存储结构来表示三元组表。又称有序的双下标法。 特点：非零元在表中按行序有序存储，因此便于进行依行顺序处理的矩阵运算。
①三元组顺序表 1．定义 三元组顺序表：以顺序存储结构来表示三元组表。又称有序的双下标法。 特点：非零元在表中按行序有序存储，因此便于进行依行顺序处理的矩阵运算。 例，上述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 i j value

23 在此，data域中表示非零元的三元组是以行序为主序顺序排列的。
2．C语言描述 // 稀疏矩阵的三元组顺序表存储表示 #define MAXSIZE //假设非零元个数的最大值为12500 typedef struct { int i, j; //该非零元的行下标和列下标 ElemType e; } Triple; Triple data[MAXSIZE + 1]; //非零元三元组表，data[0]未用 int mu, nu, tu; //矩阵的行数、列数和非零元个数 } TSMatrix; 在此，data域中表示非零元的三元组是以行序为主序顺序排列的。

24 3．矩阵转置运算 对于一个m×n的矩阵M，它的转置矩阵T是一个n×m矩阵， 且T(i, j) = M(j, i)，1≤i≤n，1≤j≤m。一个稀疏矩阵的转置矩阵 仍然是稀疏矩阵。 例：上述矩阵M ＝ 的转置矩阵为： T ＝

25 假设a和b是TSMatrix型的变量，分别表示矩阵M和T。
由a转置到b只需：i.将矩阵的行列值相互交换； ii.将每个三元组中的i和j相互调换； iii.重排三元组之间的次序便可实现矩阵的转置。 (6×7)6行7列 (7×6)7行6列 (7×6)7行6列 i j value i(j) j(i) value i(j) j(i) value －3 － － －7 i.和ii. iii. － － 图5.5 矩阵a转置到矩阵b的过程

26 实现方法： i. 直接取顺序存 算法思想：按照b.data中三元组的次序依次在a.data中找到相应的三元组进行转置。 算法5.1如下： Status TransposeSMatrix (TSMatrix M, TSMatrix &T) { //采用三元组表存储表示，求稀疏矩阵M的转置矩阵T。 T.mu = M.nu; T.nu = M.mu; T.tu = M.tu; if (T.tu) { q = 1; for (col = 1; col <= M.nu; ++col) for (p = 1; p <= M.tu; ++p) if (M.data[p].j = = col) { T.data[q].i = M.data[p].j; T.data[q].j = M.data[p].j; T.data[q].e = M.data[p].e; ++q; } return OK; } // TransposeSMatrix

27 时间复杂度：O(nu×tu)，即和M的列数及非零元的个数的乘积乘正比。当非零
元的个数tu和mu×nu同数量级时，算法5.1的时间复杂度就为O(mu× )了（例如， 假设在100×500的矩阵中有tu＝10000个非零元），虽然节省了存储空间，但时间复 杂度提高了。因此，该算法仅适于tu<<mu×nu的情况。 ii. 顺序取直接存 算法思想：按照a.data中三元组的次序进行转置，并将转置后的三元组置 入b中适当的位置。 在此，附设了num和cpot两个向量。num[col]表示矩阵M中第col列中非零元的个 数，cpot[col]指示M中第col列的第一个非零元在b.data中的恰当位置。显然有： cpot[1] = 1; cpot[col] = cpot[col－1] + num[col－1] ≤col≤a.nu 例如，对上述矩阵M，num和cpot的值如表5.1所示。 表5.1 矩阵M的向量cpot的值 col num[col] cpot[col]

28 时间复杂度：O(nu＋tu).在M的非零元个数tu和mu×nu等数量级时,其时间复杂度为O(mu×nu) .
Status FastTransposeSMatrix (TSMatrix M, TSMatrix &T) { //采用三元组顺序表存储表示，求稀疏矩阵M的转置矩阵T。 T.mu = M.nu; T.nu = M.mu; T.tu = M.tu; if (T.tu) { for (col = 1; col <= M.nu; ++col) num [col] = 0; for (t =1; t <= M.tu; ++t) ++ num[M.data[t].j]; //求M中每一列含非零元个数 cpot[1] = 1; //求第col列中第一个非零元在b.data中的序号 for (col = 2; col <= M.nu; ++col) cpot[col] = cpot[col－1] + num[col－1]; for (p =1; p <= M.tu; ++p) { col = M.data[p].j; q = cpot[col]; T.data[q].i = M.data[p].j; T.data[q].j = M.data[p].i; T.data[q].e = M.data[p].e; ++cpot[col]; } // for } // if return OK; } // FastTransposeSMatrix 算法5.2 时间复杂度：O(nu＋tu).在M的非零元个数tu和mu×nu等数量级时,其时间复杂度为O(mu×nu) .

29 行逻辑链接的顺序表：带行链接信息的三元组表。
②行逻辑链接的顺序表 1．定义 行逻辑链接的顺序表：带行链接信息的三元组表。 2．C语言描述 typedef struct { Triple data[MAXSIZE+1]; //非零元三元组表 int rpos[MAXRC+1]; //各行第一个非零元的位置表 int mu, nu, tu; //矩阵的行数、列数和非零元个数 } RLSMatrix 3．矩阵相乘运算 i. 经典算法 若设 Q = M×N，其中，M是 矩阵，N是 矩阵。当n1＝m2时有： for (i = 1; i <= m1; ++i) for (j = 1; j <= n2; ++j) { Q[i][j] = 0; for (k = 1; k <= n1; ++k) Q[i][j] + = M[i][k] * N[k][j]; } 时间复杂度是O( )

30 ii. 稀疏矩阵相乘算法 当M和N是稀疏矩阵并用三元组表作存储结构时，不能套用上述算法。 × = 例如， 两个稀疏矩阵相乘所得的乘积矩阵不是稀疏矩阵，故乘积矩阵不应采用 压缩存储，而应以二维数组表示。 算法思想：对于M中每个元素M.data[p] (p=1, 2, … , M.tu)，找到N中所有 满足条件M.data[p].j = N.data[q].i（即M.data中的j值和N.data中的i值相等）的 元素N.data[q]，求得M.data[p].v和N.data[q].v的乘积。乘积矩阵Q中每个元素 的值是个累计和，这个乘积M.data[p].v×N.data[q].v只是Q[i][j]中的一部分。 为便于操作，并对每个元素设一累计和的变量，其初值为零，然后扫描数组 M，求得相应元素的乘积并累加到适当的求累计和的变量上。乘积矩阵Q中的 元素是否为非零元，只有在求得其累加和后才能得知。由于Q中元素的行号和 M中元素的行号一致，又M中元素排列是以M的行序为主序的，由此可对Q中 元素进行逐行处理，先求得累计求和的中间结果（Q的一行），然后再压缩存 储到Q.data中去。

31 两个稀疏矩阵相乘(Q = M×N)的过程可大致描述如下：
if (Q是非零矩阵) { //逐行求积 for (arow = 1; arow <= M.mu; ++ arow) { //处理M的每一行 ctemp[ ] = 0; //累加器清零 计算Q中第arow行的积并存入ctemp[ ]中； 将ctemp[ ]中非零元压缩存储到Q.data； } // for arow } // if 算法5.3如下： Status MlutSMatrix (RLSMatrix M, RLSMatrix N, RLSMatrix &Q) { //求矩阵乘积Q = M×N，采用逻辑链接存储表示。 if (M.nu != N.mu) return ERROR; Q.mu = M.mu; Q.nu = M.nu; Q.tu = 0; //Q初始化 if (M.tu * N.tu !=0) { //Q是非零矩阵 for (arow = 1; arow <= M.mu; ++ arow) { //处理M的每一行 ctemp[ ] = 0; //当前各元素累加器清零 Q.rpos[arow] = Q.tu + 1; if (arow < M.mu) tp = M.rpos[arow + 1]; 算法5.3是上述过程求精的结果。

32 for (p = M.rpos[arow]; p < tp; ++p) { //为当前行中每一个非零元找到对应元在N中的行号
else tp = M.tu + 1; for (p = M.rpos[arow]; p < tp; ++p) { //为当前行中每一个非零元找到对应元在N中的行号 brow = M.data[p].j; if (brow < N.mu) t = N.rpos[brow + 1]; t = N.tu + 1; for (q = N.rpos[brow]; q < t; ++q) { ccol = N.data[q].j; //乘积元素在Q中的列号 ctemp[ccol] + = M.data[p].e * N.data[q].e; } // for q } //求得Q中第crow( = arow)行的非零元 for (ccol = 1; ccol <= Q.nu; ++ccol) //压缩存储该行非零元 if (ctemp[ccol]) { if (++Q.tu > MAXSIZE) return ERROR; Q.data[Q.tu] = (arow, ccol, ctemp[ccol]); } // if } // for arow return OK; } // MlutSMatrix 时间复杂度：O(M.mu×N.nu+M.tu×N.tu/N.mu)。 其中累加器ctemp初始化的时间复杂度为O(M.mu×N.nu)， 求Q的所有非零元的时间复杂度为O(M.tu×N.tu/N.mu)， 进行压缩存储的时间复杂度为O(M.mu×N.nu)。

33 ③十字链表 1．定义 十字链表：在链表中，每个非零元既是某个行链表中的一个结点， 又是某个列链表中的一个结点，这个矩阵构成了一个十字交叉的链表 结构。可用两个分别存储行链表的头指针和列链表的头指针的一维数 组表示之。 2．结点结构 row col val down right 其中，row，col和val分别表示该非零元所在的行、列和非零元的值。 right域，用以链接同一行中下一个非零元。down域，用以链接同一 列中下一个非零元。

34 3．图形表示 例如，矩阵M＝ 的十字链表如图5.6所示。 M.chead M.rhead 图5.6 稀疏矩阵M的十字链表

35 4．C语言描述 // 稀疏矩阵的十字链表存储表示 typedef struct OLNode { int i, j; //该非零元的行和列下标 ElemType e; struct OLNode *right, *down; //该非零元所在行表和列表的后继链域 } OLNode *OLink; typedef struct { OLink *rhead, *chead; //行和列链表头指针向量基址由CreateSMatrix分配 int mu, nu, tu; //稀疏矩阵的行数、列数和非零元个数 } CrossList; 5. 创建稀疏矩阵 算法5.4如下： Status CreateSMatrix_OL (CrossList &M) { //创建稀疏矩阵M。采用十字链表存储表示。 if (M) free (M); scanf (&m, &n, &t); //输入M的行数、列数和非零元个数 M.mu := m; M.nu := n; M.tu := t;

36 if (!(M.rhead = (OLink *) malloc ((m + 1) * sizeof(OLink))))
exit (OVERFLOW); if (!(M.chead = (OLink *) malloc ((n + 1) * sizeof(OLink)))) M.rhead[ ] = M.chead[ ] = NULL; //初始化行列头指针向量；各行列链表为空链表 for (scanf (&i, &j, &e); i != 0; scanf (&i, &j, &e)) { //按任意次序输入非零元 if (!(p = (OLNode *) malloc (sizeof (OLNode)))) p－>i = i; //生成结点 p－>j = j; p－>e = e; if (M.rhead[i] = = NULL | | M.rhead[i] －>j > j) { p－>right = M.rhead[i]; M.rhead[i] = p; } else { //寻查在行表中的插入位置 for (q = M.rhead[i]; (q－>right) && q－>right－>j < j; q = q－>right); p－>right = q－>right; q－>right = p; //完成行插入

37 if (M.chead[j] = = NULL | | M.chead[j] －>i > i) {
p－>down = M.chead[j]; M.chead[j] = p; } else { //寻查在列表中的插入位置 for (q = M.chead[j]; (q－>down) && q－>down－>i < i; q = q－>down); p－>down = q－>down; q－>down = p; //完成列插入 return OK; } // CreateSMatrix_OL 时间复杂度：O(t×s)，其中s = max {m×n}。这是因为每建立一个非零元的 结点时都要寻查它在行表和列表中的插入位置，此算法对非零元输入的先后次 序没任何要求。反之，若按以行序为主序的次序依次输入三元组，则可将建立 十字链表的算法改写成O(t)数量级的。

38 6．矩阵加法 假设将矩阵B加到矩阵A上的结果为A’,则和矩阵A’中的元aij’可能有4种情况： i. aij’＝ bij, (aij＝0 , bij≠0); 在矩阵A的十字链表上插入一个新结点。 ii. aij’＝ aij , (aij≠0 , bij ＝0); 不改变矩阵A的十字链表上对应的结点的val域值。 iii. aij’＝ aij＋bij ≠0 , (aij≠0); 修改矩阵A的十字链表对应结点的val域值。 iv. aij’＝ aij＋bij ＝0 , (aij≠0); 删除矩阵A的十字链表上对应的结点。 假设非空指针pa和pb分别指向矩阵A和B中行值相同的两个结点，pa = = NULL 表明矩阵A在该行中没有非零元，则上述4种情况的处理过程为： i. 若pa = = NULL 或pa－>j > pb－>j，则需要在A矩阵的链表中插入一个值 为bij的结点。此时，需改变同一行中前一结点的right域值，以及同一列 中前一结点的down域值。 ii. 若pa－>j < pb－>j，则只要将pa指针往右推进一步。 iii. 若pa－>j = = pb－>j且pa－>e + pb－>e !=0，则只要将aij＋bij的值送到 pa所值结点的e域即可，其他所有域的值都不变。 iv. 若pa－>j = = pb－>j且pa－>e + pb－>e = =0，则需要在A矩阵的链表中 删除pa所指的结点。此时，需改变同一行中前一结点的right域值，以及 同一列中前一结点的down域值。

39 将矩阵B加到矩阵A上的操作过程的概要描述：
i. 初始，令pa和pb分别指向A和B的第一行的第一个非零元素的结点，即 pa = A.rhead[1]; pb = B.rhead[1]; pre = NULL; 且令h1初始化 for (j = 1; j <= A.nu; ++j) h1[j] = A.chead[j]; ii. 重复本步骤，依次处理本行结点，直到B的本行中无非零元素的结点， 即pb = = NULL为止： a．若pa = = NULL或pa－>j > pb－>j（即A的这一行中非零元素已 处理完），则需在A中插入一个pb所指结点的复制结点。假设新结点的 地址为p，则A的行表中的指针作如下变化： if (pre = = NULL) A.rhead[p－>i] = p; else {pre－>right = p;} p－>right = pa; pre = p; A的列链表中的指针也要作相应的改变。首先需从h1[p－>j] 开始找到新结点在同一列中的前驱结点，并让h1[p－>j]指向它，然后在列链表中插入新结点：

40 if (A.chead[p－>j] = = NULL) {
A.chead[p－>j] = p; p－>down = NULL; } else { p－>down = h1[p－>j]－>down; h1[p－>j]－>down = p; h1[p－>j] = p; b．若pa ! = NULL或pa－>j < pb－>j，则令pa指向本行下一个非零元结点，即 pre = pa; pa = pa－>right; c．pa－>j = = pb－>j，则将B中当前结点的值加到A中当前结点上，即 pa－>e += pb－>e; 此时若pa－>e!= 0，则指针不变，否则删除A中该结点， 即行表中指针变为： if (pre = = NULL) A.rhead[pa－>i] = pa－>right; else {pre－>right = pa－>right;} p = pa; pa = pa－>right;

41 同时，为了改变列表中的指针，需要先找到同一列中的前驱结点，且让
h1[pa－>j]指向该结点，然后如下修改相应指针： if (A.chead[p－>j] = = p) A.chead[p－>j] = h1[p－>j] = p－>down; else { h1[p－>j]－>down = p－>down; } free (p); iii. 若本行不是最后一行，则令pa和pb指向下一行的第一个非零元结 点，转ii；否则结束。 时间复杂度：O(ta + tb)。

42 ￡5.3 广义表 ￡5.3.1 广义表的定义 （1）定义 广义表是线性表的推广。一般记作： 其中，LS是广义表
的名称（用大写字母表示），n是它的长度。 可以是单个元素，也可以是广义表。 原子：广义表LS中 是单个元素，则称 为原子。用小写字母表示。 子表：广义表LS中 是广义表，则称 为子表。 表头（Head）：当广义表LS非空时，其第一个元素 即为表头。 表尾（Tail）：广义表LS中除表头元素外， 其余元素组成的表 。 由表头、表尾的定义易知：任何一个非空列表 其表头可能是原子，也可能是列表，而其表尾必定 是列表。

43 例如： ①A = ( )——A是一个空表，它的长度为零，深度为1。 ②B = (e)——列表B只有一个原子e，B的长度为1，深度也为1。 ③C = (a, (b, c, d))——列表C的长度为2，深度为2，两个元素分 别为原子a和子表(b, c, d)。 ④D = (A, B, C)——列表D的长度为3，深度为1，3个元素都是 列表。将子表的值带入后，则有D = (( ), (e), (a, (b, c, d)))。 ⑤E = (a, E)——这是一个递归的表，它的长度为2，深度为∞。 E相当于一个无限的列表E = (a, (a, (a, …)))。 （2）广义表的抽象数据类型定义 ADT GList { 数据对象：D={ ei| i=1,2,…,n；n≥0；ei∈AtomSet 或 ei∈GList;} 数据关系：R1＝{< ei-1, ei >|ei-1, ei ∈D, 2≤i≤n} 基本操作： InitGList (&L); 操作结果：创建空的广义表L。 CreateGList(&L, S); 初始条件：S是广义表的书写形式串。 操作结果：由S创建广义表L。

44 DestroyGList(&L); 初始条件：广义表L已存在。 操作结果：销毁广义表L。 CopyGList(&T, L); 操作结果：由广义表L复制得到广义表T。 GListLength(L); 操作结果：求广义表L的长度，即元素个数。 GListDepth(L); 操作结果：求广义表L的深度。 GListEmpty(L); 操作结果：判定广义表L是否为空。 GetHead(L); 操作结果：取广义表L的头。 GetTail(L); 操作结果：取广义表L的尾。

45 InsertFirst_GL(&L, e); 初始条件：广义表L已存在。 操作结果：插入元素e作为广义表L的第一个元素。
DeleteFirst_GL (&L, &e); 操作结果：删除广义表L的第一个元素，并用e返回其值。 Traverse_GL(L, visit()); 操作结果：遍历广义表L，用函数visit处理每个元素， }ADT GList D A B C E e a b c d （3）3个重要结论： ①列表的元素可以是子表，而子表的元素还可以 是子表……故，列表是一个多层次的结构。如图5.7所 示的列表D。图中圆圈表示列表，以方块表示原子。 ② 列表可为其他列表所共享。 图5.7 列表的图形表示 ③列表可以是一个递归的表，即列表也可以是其 本身的一个子表。

46 ￡5.3.2 广义表的存储结构 （1）头尾链表存储表示 ①结点结构 tag = 1 hp tp 表结点 原子结点 tag = 0 atom
tag：标志域。tag＝1表示表结点；tag＝0表示原子结点。 hp：指示表头的指针域。 tp：指示表尾的指针域。 atom：值域。 ②C语言描述 typedef enum {ATOM, LIST}ElemTag; //ATOM = = 0:原子，LIST = = 1:子表 typedef struct GLNode { ElemTag tag; //公共部分，用于区分原子结点和表结点 union { //原子结点和表结点的联合部分 AtomType atom; //atom是原子结点的值域，AtomType由用户定义 struct {struct GLNode *hp, *tp;} ptr; //ptr是表结点的指针域，ptr.hp和ptr.tp分别指向表头和表尾 }; } *GList;

47 例1，D = (A, B, C)，其中A = ( )，B = (e)，C = (a, (b, c, d))。如图5.9(a)所示。
③图形表示 例1，D = (A, B, C)，其中A = ( )，B = (e)，C = (a, (b, c, d))。如图5.9(a)所示。 A = NULL 0 b c d D B C 0 e a (a) 例1 例2，E = (a, E) 。如图5.9(b)所示。 E 0 a (b) 例2 图5.8 广义表的存储结构示例

48 ④特点 1．除空表的表头指针为空外，对任何非空表，其表头指针均指向一个表结点。 2．容易分清列表中原子和子表所在层次。 3．最高层的表结点个数即为列表的长度。 （2）扩展性链表存储表示 ①结点结构 tag = hp tp 表结点 tag = 0 atom tp 原子结点 tag：标志域。tag＝1表示表结点；tag＝0表示原子结点。 hp：指示表头的指针域。 tp：指示表尾的指针域。 atom：值域。 ②C语言描述 typedef enum {ATOM, LIST}ElemTag; //ATOM = = 0:原子，LIST = = 1:子表 typedef struct GLNode { ElemTag tag; //公共部分，用于区分原子结点和表结点 union { //原子结点和表结点的联合部分 AtomType atom; //atom是原子结点的值域，AtomType由用户定义 struct GLNode *hp; //表结点的表头指针 }; struct GLNode *tp; //相当于线性链表的next，指向下一个元素结点 } *GList; //广义表类型GList是一种扩展的线性链表

49 ③图形表示 图5.9 广义表的另一种链表表示 A 1 1 1 1 B 1 C 1 0 e 0 a 1 0 b 0 c 0 d E 1
B C 0 e a 0 a E 图5.9 广义表的另一种链表表示