数据结构（C语言版）（第三版）（微课版）第4章 特殊矩阵和广义表

第4章

特殊矩阵和广义表教学要求相关知识点稀疏矩阵广义表的表头、表尾学习重点稀疏矩阵的存储与操作广义表的操作目录特殊矩阵的压缩存储1广义表2本章小结34.1特殊矩阵的

压缩存储4.1特殊矩阵的压缩存储规律分布特殊矩阵的压缩存储两种规律分布特殊矩阵：对称矩阵和三角矩阵。充分利用元素值的分布规律，将特殊矩阵进行压缩存储。两条原则：一是尽可能地压缩数据量，二是压缩后仍然可以比较容易地进行各项基本操作。1.对称矩阵及其压缩存储在一个n阶方阵A中，若元素满足下述性质：aij=aji 0≤i，j≤n-1则称A为n阶对称矩阵。如图4.5(a)为4阶对称矩。4.1特殊矩阵的压缩存储对称矩阵中的元素关于主对角线对称，因此，顺序存储时为每一对对称元素分配一个存储空间，即只存放主对角线和下三角(或上三角)区的元素。对称矩阵下标i,j0,01,01,12,02,12,23,03,13,23,3一维数组下标k0123456789a[i][j]a[j][i]b[k]1057312201742314元素存储位置：4.1特殊矩阵的压缩存储为每一对对称元素只分配一个存储空间，且按行优先的次序顺序存储主对角线和下三角区的元素，那么对于n阶对称矩阵来说，只需要存放第0行的一个元素a00，第1行的两个元素a10、a11，第n-1行的n个元素an-1,0，an-1,1，an-1,n-1。4.1特殊矩阵的压缩存储矩阵每行存储的元素个数形成一个等差数列，该数列的首项是1，末项是n，项数是n，公差是1。因此，对称矩阵要存储的元素个数为：n(n+1)/2。非压缩存储矩阵需分配n2个存储区，由于对称矩阵的对称性，压缩存储后只需分配n(n+1)/2个存储区，几乎节省一半。对称矩阵进行压缩存储后，访问该矩阵元素的位置计算公式如式：

其中k(0≤k≤n(n+1)/2)对称矩阵位于(i，j)位置的元素在一维数组中的存储序号。4.1特殊矩阵的压缩存储将一维数组a中压缩存储的下三角4×4阶对称矩阵按矩阵格式输出。print(inta[]){inti,j;for(i=0;i<4;i++){for(j=0;j<4;j++)if(i>=j)printf("%4d",a[i*(i+1)/2+j]);elseprintf("%4d",a[j*(j+1)/2+i]);printf(“\n”);}}4.1特殊矩阵的压缩存储2.三角矩阵及其压缩存储三角矩阵分为上三角矩阵和下三角矩阵。下三角矩阵以主对角线为界的上半部分是一个固定值，下半部分的元素值没有规律；上三角矩阵以主对角线为界的下半部分是一个固定值，上半部分的元素值没有规律。(a)下三角矩阵(b)上三角矩阵4.1特殊矩阵的压缩存储三角矩阵的存储除了存储其上(下)三角中的元素之外，再加一个存储常数C的存储空间，即一个n阶方阵只需为n(n+1)/2+1个元素分配存储空间。4.1特殊矩阵的压缩存储下三角矩阵图4.7(a)的压缩存储可将上三角部分的常量值存储在第0个单元，下三角和主对角上的元素从第1个存储单元开始存放，则以行优先的方式存储如下：012345678910C29612810301326920对下三角矩阵进行压缩存储后，访问该矩阵元素的位置计算公式如式k=k(0≤k≤n(n+1)/2)是下三角矩阵位于(i，j)位置的元素在一维数组中的存储序号。4.1特殊矩阵的压缩存储上三角矩阵的压缩存储可将下三角部分的常量值存储在第0个单元，上三角和主对角上的元素从第1个存储单元开始存放，则以行优先的方式存储如下：012345678910C29681312102630920对上三角矩阵进行压缩存储后，访问该矩阵元素的位置计算公式如式k=k(0≤k≤n(n+1)/2)是上三角矩阵位于(i，j)位置的元素在一维数组中的存储序号。4.1特殊矩阵的压缩存储稀疏矩阵及其压缩存储称非零元素较零元素少，且分布没有规律的矩阵为稀疏矩阵。若m×n的矩阵含有t个非零元素，且t远远小于m×n，则将这个矩阵称为稀疏矩阵。令δ=t/(m*n)，称δ为矩阵的稀疏因子。一个5阶方阵，共25个元素，其中非零元素6个，零元素19个，零元素占整个元素个数的76%，它是一个稀疏矩阵。4.1特殊矩阵的压缩存储稀疏矩阵及其压缩存储用三元组法对稀疏矩阵进行压缩存储：用三项内容表示稀疏矩阵中的每个非零元素，形式为：(i，j，value)。其中，i表示行序号，j表示列序号，value表示非零元素的值。将稀疏矩阵中的所有非零元素用这种三元组的形式表示，并将它们按以行为主的顺序存放在一维数组中，形成一个三元组表。4.1特殊矩阵的压缩存储

三元组ijvalue00031047212-1320-1421-254324.1特殊矩阵的压缩存储1.稀疏矩阵的三元组表的顺序存储及实现(1)稀疏矩阵的三元组表的顺序存储稀疏矩阵的三元组表的顺序存储结构定义如下：typedefintElemType; #defineMAXSIZE100//非零元素个数的最大值typedefstruct{inti,j; /*行下标，列下标*/

ElemTypee; /*非零元素值*/}Triple;4.1特殊矩阵的压缩存储typedefstruct{Tripledata[MAXSIZE+1]; /*非零元素三元组表，data[0]未用*/

intmu,nu,tu; /*矩阵的行数、列数和非零元素的个数*/}TSMatrix;用一个m×n的二维数组来存放稀疏矩阵A；用变量tu记录非零元素的个数；变量mu记录稀疏矩阵的行数；变量nu记录非零元素的列数；用Triple结构体来存放稀疏矩阵A的非零元素的三元组，其中的i表示行下标，j表示列下标；用data来存放非零三元组表。4.1特殊矩阵的压缩存储(2)创建稀疏矩阵M根据一维数组a及要创建的顺序存储三元组表实现的稀疏矩阵M所要求的行数、列数创建稀疏矩阵M。intCreateM(TSMatrix*M,inta[],introw,intcol){intt,k=0;

for(t=0;t<row*col;t++) if(a[t]!=0)//对数组中的非零元素创建三元组

{(*M).data[k].i=t/col;//三元组行号

(*M).data[k].j=t%col;//三元组列号

(*M).data[k].e=a[t];//三元组的非零元素值

++k;

}

4.1特殊矩阵的压缩存储

if(k)//如果三元组表中有元素，则创建三元组成功

{ (*M).tu=k;//矩阵的非零元素个数

(*M).mu=row;//矩阵的行数

(*M).nu=col;//矩阵的列数return1;

}

elsereturn0;}4.1特殊矩阵的压缩存储2.三元组表的链式存储(1)带行指针的单链表存储法稀疏矩阵每行非零元素的三元组连成一个单链表，每行三元组链表设置一个表头指针。每个非零元素的三元组中增添一个指针域，指向本行下个非零元素的三元组。4.1特殊矩阵的压缩存储由于相同的行的三元组节点中，都包含有相同的行号域，因此可以把三元组里的行号域提取出来放在表头节点里，这时的单链表存储法如图4.8(b)所示。4.2广义表4.2广义表广义表的定义广义表是n（n≥0）个数据元素的有限序列，一般记作：LS＝(a0，a1，……，an-1)。LS是广义表的名称，ai（0≤i≤n-1）是LS的成员（也称直接元素），它可以是单个的数据元素(也称原子)，也可以是一个广义表，分别称为LS的单元素和子表。习惯上，用大写字母表示广义表的名称，用小写字母表示原子。当广义表LS为非空时，称第一个元素a0为LS的表头（Head），称其余元素组成的表（a1，……，an-1）为LS的表尾（Tail）。n是广义表的长度，即广义表最外层包含元素个数。广义表的深度定义为所含括弧的重数，注意：“原子”的深度为

0，“空表”的深度为

1。

4.2广义表广义表的特性（1）广义表中元素是有次序性的。表中的元素位置不可以随意调换，调换后表示的是一个不同的广义表。（2）广义表有长度。广义表最外层包含元素个数是它的长度，不管这个元素是原子，还是子表。空表长度为0。（3）广义表有深度。为所含括弧的层数，如果表中元素是子表，要把子表用原子表示出来，再计算广义表的深度。（4）广义表是一种多层次的数据结构。广义表的元素可以是单元素，也可以是子表，而子表的元素还可以是子表。（5）广义表中元素可共享。子表可以为其它子表所共享。4.2广义表（6）广义表中元素可递归。即广义表中的子表可以是其本身的一个子表。这时，广义表的深度是个无限值，长度是个有限值。（7）任何一个非空广义表LS＝(a0，a1，……，an-1)均可分解为：表头Head(LS)=a0和表尾Tail(LS)=(a1，a2，……，an-1)两部分。4.2广义表广义表的常用表示及基本运算1.广义表的表示(1)广义表存储数据的常用表示形式①E=()E是一个空表，其长度为0。②L=(a,b)L是长度为2的广义表，它的两个元素都是原子，因此它是一个线性表。③A=(x,L)=(x,(a,b))A是长度为2的广义表，第一个元素是原子x，第二个元素是子表L。4.2广义表④B=(A,y)=((x,(a,b)),y)B是长度为2的广义表，第一个元素是子表A，第二个元素是原子y。⑤C=(A,B)=((x,(a,b)),((x,(a,b)),y))C的长度为2，两个元素都是子表。⑥D=(a,D)=(a,(a,(a,(…))))D的长度为2，第一个元素是原子，第二个元素是D自身，展开是一个无限的广义表。4.2广义表(2)广义表的深度一个表的“深度”是指表展开后所含括号的层数。表L、A、B、C的深度为分别为1、2、3、4，表D的深度为∞。4.2广义表(3)带名称的广义表表示如果规定任何表都是有名称的，为了既表明每个表的名称，又说明它的组成，则可以在每个表的前面冠以该表的名称，于是上例中的各表又可以写成：①E()②L(a,b)③A(x,L(a,b))④B(A(x,L(a,b)),y)⑤C(A(x,l(a,b)),B(A(x,L(a,b)),y))⑥D(a,D(a,D(…)))4.2广义表2.广义表的基本运算由于广义表是对线性表和树的推广，并且具有共享和递归特性的广义表可以和有向图建立对应，因此广义表的大部分运算与这些数据结构上的运算类似。只讨论广义表的两种特殊的基本运算：取表头head(Ls)和取表尾tail(Ls)。任何一个非空广义表的表头是表中的第一个元素，它可以是原子，也可以是子表，而其表尾必定是子表。广义表的存储结构及实现【例4.1】取广义表的表头及表尾假设广义表L=(a,(b)),B=(A,(y))，则有：head(L)=a，tail(L)=((b))head(B