第5章数组和稀疏矩阵5.1.1数组的基本概念数组是n(n>1)个相同类型数据元素al,a2,""an构成的有限序列,且该有限序列存储在一块地址连续的内存单元中。由此可见，数组的定义类似于采用顺序存储结构的线性表。5.1.2数组的存储结构在一维数组中，一旦al的存储地址LOC(al)确定,并假设每个数据元素占用k个存储单元,则任一数据元素ai的存储地址LOCai)就可由以下公式求出：LOC(ai)=LOC(al)+(i-1)*k(0≤i≤n)对于一个m行n列的二维数组AmXn,有：将Am*n简记为A,A是这样的一维数组：A-(al,a2,..,ai...,am)其中,ai=(ai,1,ai,2,,ai,n)(1≤j≤m)。以行序为主序的存储方式：即先存储第1行，然后紧接着存储第2行，最后存储第m行。此时，二维数组的线性排列次序为：al,l,al,2,...,al,n,a2,1,a2,2,..a2,n,..,am,1,am,2,..am,n对一个已知以行序为主序的计算机系统中,当二维数组第一个数据元素al,1的存储地址LOC(al,1)和每个数据元素所占用的存储单元k确定后,则该二维数组中任一数据元素aiji的存储地址可由下式确定：LOC(ai,j)=LOC(al,1)+[(i-1)*n+(j-1))*k其中n为列数。同理可推出在以列序为主序的计算机系统中有：LOC(ai,j)=LOC(al,1)+[(j-1)*m+(i-1))*k其中m为行数。5.1.3特殊矩阵的压缩存储特殊矩阵是指非零元素或零元素的分布有一定规律的矩阵为了节省存储空间，特别是在高阶矩阵的情况下可以利用特殊矩阵的规律，对它们进行压缩存储，也就是说，使多个相同的非零元素共享同一个存储单元，对零元素不分配存储空间。特殊矩阵的主要形式有对称矩阵、对角矩阵等，它们都是方阵，即行数和列数相同。1.对称矩阵的压缩存储若一个n阶方阵A[n][n]中的元素满足ai,Faj,i(0≤ij≤n-1),则称其为n阶对称矩阵。由于对称矩阵中的元素关于主对角线对称因此在存储时可只存储对称矩阵中上三角或下三角中的元素使得对称的元素共享一个存储空间。这样就可以将n2个元素压缩存储到个元素的空间中。不失一般性，我们以行序为主序存储其下三角（包括对角线）的元素。2.对角矩阵的压缩存储若一个n阶方阵A满足其所有非零元素都集中在以主对角线为中心的带状区域中,则称其为n阶对角矩阵。其主对角线上下方各有b条次对角线，称b为矩阵半带宽，(2b+1)为矩阵的带宽。对于半带宽为b(0≤b≤(n-1)/2)的对角矩阵,其i-j≤b的元素aij不为零,其余元素为零5.2稀疏矩阵二个阶数较大的矩阵中的非零元素个数s相对于矩阵元素的总个数t十分小时,即s<<t时，称该矩阵为稀疏矩阵。例如一个100×100的矩阵，若其中只有100个非零元素，就可称其为稀疏矩阵。5.2.1稀疏矩阵的三元组表示37
37 第 5 章 数组和稀疏矩阵 5.1.1 数组的基本概念 数组是 n(n＞1)个相同类型数据元素 a1,a2,.,an 构成的有限序列,且该有限序列存储 在一块地址连续的内存单元中。 由此可见,数组的定义类似于采用顺序存储结构的线性表。 5.1.2 数组的存储结构 在一维数组中,一旦 a1 的存储地址 LOC(a1)确定,并假设每个数据元素占用 k 个存储单 元,则任一数据元素 ai 的存储地址 LOC(ai)就可由以下公式求出： LOC(ai)=LOC(a1)+(i-1)*k (0≤i≤n) 对于一个 m 行 n 列的二维数组 Am×n,有： 将 Am*n 简记为 A,A 是这样的一维数组： A=(a1,a2,.,ai.,am) 其中,ai=(ai,1,ai,2,.,ai,n) (1≤j≤m)。 以行序为主序的存储方式：即先存储第 1 行,然后紧接着存储第 2 行,最后存储第 m 行。 此时,二维数组的线性排列次序为： a1,1,a1,2,.,a1,n,a2,1,a2,2,.,a2,n,.,am,1,am,2,.am,n 对一个已知以行序为主序的计算机系统中,当二维数组第一个数据元素 a1,1 的存储地址 LOC(a1,1)和每个数据元素所占用的存储单元 k 确定后,则该二维数组中任一数据元素 ai,j 的 存储地址可由下式确定： LOC(ai,j)=LOC(a1,1)+[(i-1)*n+(j-1)]*k 其中 n 为列数。 同理可推出在以列序为主序的计算机系统中有： LOC(ai,j)=LOC(a1,1)+[(j-1)*m+(i-1)]*k 其中 m 为行数。 5.1.3 特殊矩阵的压缩存储 特殊矩阵是指非零元素或零元素的分布有一定规律的矩阵,为了节省存储空间,特别 是在高阶矩阵的情况下,可以利用特殊矩阵的规律,对它们进行压缩存储,也就是说,使多个相 同的非零元素共享同一个存储单元,对零元素不分配存储空间。 特殊矩阵的主要形式有对称矩阵、对角矩阵等,它们都是方阵,即行数和列数相同。 1. 对称矩阵的压缩存储 若一个 n 阶方阵 A[n][n]中的元素满足 ai,j=aj,i(0≤i,j≤n-1),则称其为 n 阶对称矩阵。 由于对称矩阵中的元素关于主对角线对称,因此在存储时可只存储对称矩阵中上三角 或下三角中的元素,使得对称的元素共享一个存储空间。这样,就可以将 n2 个元素压缩存储到 个元素的空间中。不失一般性,我们以行序为主序存储其下三角(包括对角线)的元素。 2. 对角矩阵的压缩存储 若一个 n 阶方阵 A 满足其所有非零元素都集中在以主对角线为中心的带状区域中,则 称其为 n 阶对角矩阵。其主对角线上下方各有 b 条次对角线,称 b 为矩阵半带宽,(2b+1)为矩 阵的带宽。对于半带宽为 b(0≤b≤(n-1)/2)的对角矩阵,其|i-j|≤b 的元素 ai,j 不为零,其余元素 为零 5.2 稀疏矩阵 一个阶数较大的矩阵中的非零元素个数 s 相对于矩阵元素的总个数 t 十分小时,即 s<<t 时,称该矩阵为稀疏矩阵。例如一个 100×100 的矩阵,若其中只有 100 个非零元素,就可称其 为稀疏矩阵。 5.2.1 稀疏矩阵的三元组表示
稀疏矩阵的压缩存储方法是只存储非零元素。若把稀疏矩阵的三元组线性表按顺序存储结构存储则称为稀疏矩阵的三元组顺序表。则三元组顺序表的数据结构可定义如下：#defineMaxSize100/*矩阵中非零元素最多个数*/typedef struct/*行号*/1intr,intc,/*列号*//*元素值*/ElemType d;}TupNode;/*三元组定义*/typedef struct/*行数值*/int rows;1int cols,/*列数值*/int nums,/*非零元素个数*TupNode data[MaxSize];} TSMatrix;/*三元组顺序表定义*/其中，data域中表示的非零元素通常以行序为主序顺序排列，它是一种下标按行有序的存储结构。这种有序存储结构可简化大多数矩阵运算算法。下面的讨论假设data域按行有序存储。（1）从一个二维矩阵创建其三元组表示(2）三元组元素赋值先在三元组t中找到适当的位置k,将kt.nums个元素后移一位,将指定元素x插入到t.data[k]处。(3）将指定位置的元素值赋给变量先在三元组t中找到指定的位置，将该处的元素值赋给x。（4）输出三元组从头到尾扫描三元组t依次输出元素值。(5）矩阵转置对于一个mXn的矩阵AmXn其转置矩阵是一个n×m的矩阵。设为BnXm满足ai,j=bji,其中1≤i≤m,1≤j≤n。以上算法的时间复杂度为O(t.cols*t.nums).而将二维数组存储在一个m行n列矩阵中时.其转置算法的时间复杂度为O(m*n)。最坏情况是当稀疏矩阵中的非零元素个数tnums和m*n同数量级时，上述转置算法的时间复杂度就为O(m*n2)。对其他儿种矩阵运算也是如此。可见常规的非稀疏矩阵应采用二维数组存储，只有当矩阵中非零元素个数s满足s<<m*n时方可采用三元组顺序表存储结构。这个结论也同样适用于下面要讨论的于字链表。本章小结本章基本学习要点如下：(1）理解数组和一般线性表之间的差异。（2）重点掌握数组的顺序存储结构和元素地址计算方法。（3）掌握各种特殊矩阵如对称矩阵、上、下三角矩阵和对角矩阵的压缩存储方法。(4)掌握稀疏矩阵的各种存储结构以及基本运算实现算法。(5)灵活运用数组这种数据结构解决一些综合应用问题。练习题教材中p113习题3、5和6。38
38 稀疏矩阵的压缩存储方法是只存储非零元素。 若把稀疏矩阵的三元组线性表按顺序存储结构存储,则称为稀疏矩阵的三元组顺序表。则三 元组顺序表的数据结构可定义如下： #define MaxSize 100 /*矩阵中非零元素最多个数*/ typedef struct { int r; /*行号*/ int c; /*列号*/ ElemType d; /*元素值*/ } TupNode; /*三元组定义*/ typedef struct { int rows; /*行数值*/ int cols; /*列数值*/ int nums; /*非零元素个数*/ TupNode data[MaxSize]; } TSMatrix; /*三元组顺序表定义*/ 其中,data 域中表示的非零元素通常以行序为主序顺序排列,它是一种下标按行有序的存储结 构。这种有序存储结构可简化大多数矩阵运算算法。下面的讨论假设 data 域按行有序存储。 (1) 从一个二维矩阵创建其三元组表示 (2) 三元组元素赋值 先在三元组 t 中找到适当的位置 k,将 k～t.nums 个元素后移一位,将指定元素 x 插入到 t.data[k]处。 (3) 将指定位置的元素值赋给变量 先在三元组 t 中找到指定的位置,将该处的元素值赋给 x。 (4) 输出三元组 从头到尾扫描三元组 t,依次输出元素值。 (5) 矩阵转置 对于一个m×n的矩阵Am×n,其转置矩阵是一个n×m的矩阵。设为Bn×m,满足ai,j=bj,i, 其中 1≤i≤m,1≤j≤n。 以上算法的时间复杂度为 O(t.cols*t.nums),而将二维数组存储在一个 m 行n 列矩阵中时,其转 置算法的时间复杂度为 O(m*n)。最坏情况是当稀疏矩阵中的非零元素个数 t.nums 和 m*n 同 数量级时,上述转置算法的时间复杂度就为 O(m*n2)。 对其他几种矩阵运算也是如此。可见,常规的非稀疏矩阵应采用二维数组存储,只有当 矩阵中非零元素个数 s 满足 s<<m*n 时,方可采用三元组顺序表存储结构。这个结论也同样适 用于下面要讨论的十字链表。 本章小结 本章基本学习要点如下： (1) 理解数组和一般线性表之间的差异。 (2) 重点掌握数组的顺序存储结构和元素地址计算方法。 (3) 掌握各种特殊矩阵如对称矩阵、上、下三角矩阵和对角矩阵的压缩存储方法。 (4) 掌握稀疏矩阵的各种存储结构以及基本运算实现算法。 (5) 灵活运用数组这种数据结构解决一些综合应用问题。 练习题 教材中 p113 习题 3、5 和 6
8.1广义表的定义广义表简称表,它是线性表的推广。一个广义表是n(n≥0)个元素的一个序列,若n=0时则称为空表。设ai为广义表的第i个元素,则广义表GL的一般表示与线性表相同：GL-(al,a2,.,ai...,an)其中n表示广义表的长度即广义表中所含元素的个数,n≥0。如果ai是单个数据元素,则ai是广义表GL的原子；如果ai是一个广义表,则ai是广义表GL的子表。广义表具有如下重要的特性：(1)广义表中的数据元素有相对次序；(2)广义表的长度定义为最外层包含元素个数：(3)广义表的深度定义为所含括弧的重数。其中，原子的深度为0,空表的深度为1（4)广义表可以共享；一个广义表可以为其他广义表共享：这种共享广义表称为再入表：（5)广义表可以是一个递归的表。一个广义表可以是自已的子表。这种广义表称为递归表。递归表的深度是无穷值，长度是有限值(6)任何一个非空广义表GL均可分解为表头head(GL)=al和表尾tail(GL)=（a2,",an)两部分。8.2广义表的存储结构广义表是一种递归的数据结构，因此很难为每个广义表分配固定大小的存储空间，所以其存储结构只好采用动态链式结构。8.3广义表的运算1.求广义表的长度在广义表中，同一层次的每个结点是通过link域链接起来的.所以可把它看做是由link域链接起来的单链表。这样，求广义表的长度就是求单链表的长度，可以采用以前介绍过的求单链表长度的方法求其长度。求广义表长度的非递归算法如下：intGLLength(GLNode*g）/*g为一个广义表头结点的指针*/1int n=0;g=g->val.sublist；/*g指向广义表的第一个元素*/while (g!-NULL)1n++;g=g->link;3return n;12.求广义表的深度对于带头结点的广义表g，广义表深度的递归定义是它等于所有子表中表的最大深度加1。若g为原子,其深度为0。3.建立广义表的链式存储结构假定广义表中的元素类型ElemType为char类型,每个原子的值被限定为英文字母。并假定广义表是一个表达式，其格式为：元素之间用一个逗号分隔，表元素的起止符号分别为左、右圆括号,空表在其圆括号内不包含任何字符。例如“(a,(b,c,d))”就是一个符合上述规定的广义表格式。生成广义表链式存储结构的算法如下：39
39 8.1 广义表的定义 广义表简称表,它是线性表的推广。一个广义表是 n(n≥0)个元素的一个序列,若 n=0 时则称为空表。设 ai 为广义表的第 i 个元素,则广义表 GL 的一般表示与线性表相同： GL=(a1,a2,.,ai,.,an) 其中 n 表示广义表的长度,即广义表中所含元素的个数,n≥0。如果 ai 是单个数据元 素,则 ai 是广义表 GL 的原子；如果 ai 是一个广义表,则 ai 是广义表 GL 的子表。 广义表具有如下重要的特性： (1)广义表中的数据元素有相对次序； (2)广义表的长度定义为最外层包含元素个数； (3)广义表的深度定义为所含括弧的重数。其中,原子的深度为 0,空表的深度为 1； (4)广义表可以共享；一个广义表可以为其他广义表共享；这种共享广义表称为再入表； (5)广义表可以是一个递归的表。一个广义表可以是自已的子表。这种广义表称为递归 表。递归表的深度是无穷值,长度是有限值； (6)任何一个非空广义表 GL 均可分解为表头 head(GL) = a1 和表尾 tail(GL) = ( a2,.,an) 两部分。 8.2 广义表的存储结构 广义表是一种递归的数据结构,因此很难为每个广义表分配固定大小的存储空间,所以 其存储结构只好采用动态链式结构。 8.3 广义表的运算 1. 求广义表的长度 在广义表中,同一层次的每个结点是通过 link 域链接起来的,所以可把它看做是由 link 域 链接起来的单链表。这样,求广义表的长度就是求单链表的长度,可以采用以前介绍过的求单 链表长度的方法求其长度。 求广义表长度的非递归算法如下： int GLLength(GLNode *g) /*g 为一个广义表头结点的指针*/ { int n=0; g=g->val.sublist; /*g 指向广义表的第一个元素*/ while (g!=NULL) { n++; g=g->link; } return n; } 2. 求广义表的深度 对于带头结点的广义表 g,广义表深度的递归定义是它等于所有子表中表的最大深度加 1。若 g 为原子,其深度为 0。 3. 建立广义表的链式存储结构 假定广义表中的元素类型 ElemType 为 char 类型,每个原子的值被限定为英文字母。 并假定广义表是一个表达式,其格式为：元素之间用一个逗号分隔,表元素的起止符号分 别为左、右圆括号,空表在其圆括号内不包含任何字符。例如“(a,(b,c,d))”就是一个符合上 述规定的广义表格式。 生成广义表链式存储结构的算法如下：
GLNode *CreatGL(char *&s)GLNode*h:charch=*s++：/*取一个扫描字符*/:if (ch!=10)/*串未结束判断*/h=(GLNode*)malloc(sizeof(GLNode));/*创建新结点*/1if (ch-=()/*当前字符为左括号时*1h->tag=1；/*新结点作为表头结点*/h->val.sublist=CreatGL(s),/*递归构造子表并链到表头结点*else if (ch==))h=NULL;/*遇到)字符，子表为空*/else1h->tag=0;/*新结点作为原子结点*/h->val.data=ch,31elseh=NULL:/*串结束，子表为空*/*取下一个扫描字符*/ch=*s++;if (h!=NULL)/*串未结束判断*if(ch==,)/*当前字符为*/h->link=CreatGL(s);/*递归构造后续子表*//*串结束*/elseh->link-NULL,/*处理表的最后一个元素*//*返回广义表指针*/returnh,14.输出广义表以h作为带表头附加结点的广义表的表头指针,打印输出该广义表时，需要对子表进行递归调用。输出一个广义表的算法如下：voidDispGL(GLNode*g）/*g为一个广义表的头结点指针*/if(g!=NULL)/*表不为空判断*/1/*为表结点时*/if(g->tag--1)1/*输出(*/printf("("),if(g->val.sublist=--NULL)printf("");/*输出空子表*/elseDispGL(g->val.sublist);/*递归输出子表*/1elseprintf("%c",g->val.data);/*为原子时输出元素值*//*为表结点时输出*if(g->tag==1) printf(")"),if (g->link!=NULL)printf(","),1DispGL(g->link);/*递归输出后续表的内容*/1140
40 GLNode *CreatGL(char *&s) { GLNode *h;char ch=*s++; /*取一个扫描字符*/ if (ch!='\0') /*串未结束判断*/ { h=(GLNode *)malloc(sizeof(GLNode));/*创建新结点*/ if (ch=='(') /*当前字符为左括号时*/ { h->tag=1; /*新结点作为表头结点*/ h->val.sublist=CreatGL(s); /*递归构造子表并链到表头结点*/ } else if (ch==')') h=NULL; /*遇到')'字符,子表为空*/ else { h->tag=0; /*新结点作为原子结点*/ h->val.data=ch; } } else h=NULL; /*串结束,子表为空*/ ch=*s++; /*取下一个扫描字符*/ if (h!=NULL) /*串未结束判断*/ if (ch==',') /*当前字符为','*/ h->link=CreatGL(s); /*递归构造后续子表*/ else /*串结束*/ h->link=NULL; /*处理表的最后一个元素*/ return h; /*返回广义表指针*/ } 4. 输出广义表 以 h 作为带表头附加结点的广义表的表头指针,打印输出该广义表时,需要对子表进行 递归调用。输出一个广义表的算法如下： void DispGL(GLNode *g) /*g 为一个广义表的头结点指针*/ { if (g!=NULL) /*表不为空判断*/ { if (g->tag==1) /*为表结点时*/ { printf("("); /*输出'('*/ if (g->val.sublist==NULL) printf(""); /*输出空子表*/ else DispGL(g->val.sublist); /*递归输出子表*/ } else printf("%c", g->val.data); /*为原子时输出元素值*/ if (g->tag==1) printf(")"); /*为表结点时输出')'*/ if (g->link!=NULL) { printf(","); DispGL(g->link); /*递归输出后续表的内容*/ } } }