数据结构(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特殊矩阵的压缩存储特殊矩阵的压缩存储1.对称矩阵及其压缩存储对称矩阵中的元素关于主对角线对称，若将对称矩阵中的所有数据元素都进行存储，则所需的存储空间将会随着矩阵阶数n的增大而急剧上升。因此，对于顺序存储而言，最好的做法是为每一对对称元素分配一个存储空间，即只存放主对角线和下三角(或上三角)区的元素。012345678910573122017423144.1特殊矩阵的压缩存储特殊矩阵的压缩存储1.对称矩阵及其压缩存储为讨论方便，假定为每一对对称元素只分配一个存储空间，且按行优先的次序顺序存储主对角线和下三角区的元素，那么对于n阶对称矩阵来说，只需要存放第0行的一个元素a00，第1行的两个元素a10、a11，第2行的3个元素a20，a21，a22，……第n-1行的n个元素an-1,0，an-1,1，an-1,n-1。4.1特殊矩阵的压缩存储特殊矩阵的压缩存储1.对称矩阵及其压缩存储现在，矩阵中每行要存储的元素个数，恰好形成一个等差数列，该数列的首项是1，末项是n，项数是n，公差是1。因此，对称矩阵要存储的元素个数为：n(n+1)/2。这样，原先存储整个矩阵需要给n2个元素分配存储区，现在由于矩阵的对称性只需要给n(n+1)/2个元素分配存储区，所需存储区几乎节省了一半，这就是对对称矩阵进行压缩存储的意义所在。对对称矩阵进行压缩存储后，访问该矩阵元素的位置计算公式如式(4.2)：4.1特殊矩阵的压缩存储特殊矩阵的压缩存储1.对称矩阵及其压缩存储k=0，1，2，…，n(n+1)/2-1，是对称矩阵位于(i，j)位置的元素在一维数组中的存储序号。4.1特殊矩阵的压缩存储特殊矩阵的压缩存储1.对称矩阵及其压缩存储以下C语言函数的功能是将一维数组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.三角矩阵及其压缩存储三角矩阵分为上三角矩阵和下三角矩阵，下三角矩阵的特点是以主对角线为界的上半部分是一个固定的值，下半部分的元素值没有任何规律；上三角矩阵的特点是以主对角线为界的下半部分是一个固定的值，上半部分的元素值没有任何规律。其中，C表示某个常数，当然也可以为0。(a)下三角矩阵(b)上三角矩阵4.1特殊矩阵的压缩存储特殊矩阵的压缩存储2.三角矩阵及其压缩存储三角矩阵的存储除了只存储其上(下)三角中的元素之外，再加一个存储常数C的存储空间即可，即一个n阶方阵中只需要为n(n+1)/2+1个元素分配存储空间。例如，下三角矩阵图4.7(a)的压缩存储可将上三角部分的常量值存储在第0个单元，下三角和主对角上的元素从第1个存储单元开始存放，则以行优先的方式存储。对下三角矩阵进行压缩存储后，访问该矩阵元素的位置计算公式如式k=012345678910C296128103013269204.1特殊矩阵的压缩存储特殊矩阵的压缩存储2.三角矩阵及其压缩存储k=0，1，2，…，n(n+1)/2，是下三角矩阵位于(i，j)位置的元素在一维数组中的存储序号。同理，上三角矩阵的压缩存储可将下三角部分的常量值存储在第0个单元，上三角和主对角上的元素从第1个存储单元开始存放，则以行优先的方式存储。4.1特殊矩阵的压缩存储特殊矩阵的压缩存储2.三角矩阵及其压缩存储对上三角矩阵进行压缩存储后，访问该矩阵元素的位置计算公式如式k=k=0，1，2，…，(n+1)/2，是上三角矩阵位于(i，j)位置的元素在一维数组中的存储序号。012345678910C296813121026309204.1特殊矩阵的压缩存储稀疏矩阵及其压缩存储在特殊矩阵中如果非零元素的分布有明显的规律，就可以将其压缩存储到一维数组中，并找到每个非零元素在一维数组中的对应关系。然而，在实际应用中我们还会经常遇到另一类矩阵，其非零元素较零元素少，且分布没有一定的规律，我们称之为稀疏矩阵。对稀疏矩阵人们无法给出确切的定义，它只是一个凭人们的直觉了解的概念。若一个m×n的矩阵含有t个非零元素，且t远远小于m×n，则我们将这个矩阵称为稀疏矩阵。令δ=t/(m*n)，则称δ为矩阵的稀疏因子。如图4.10所示为一个5阶方阵，共25个元素，其中非零元素6个，零元素19个，零元素占整个元素个数的76%。可以说它是一个稀疏矩阵。4.1特殊矩阵的压缩存储稀疏矩阵及其压缩存储由于稀疏矩阵的零元素很多，非零元素很少，因此完全可以对其进行压缩存储。通常采用三元组表示法来对稀疏矩阵进行压缩存储：即矩阵中的每个元素都由行序号和列序号唯一确定，需要用三项内容表示稀疏矩阵中的每个非零元素，形式为：(i，j，value)。其中，i表示行序号，j表示列序号，value表示非零元素的值。将稀疏矩阵中的所有非零元素用这种三元组的形式表示，并将它们按以行为主的顺序存放在一维数组中，形成一个三元组表。4.1特殊矩阵的压缩存储稀疏矩阵及其压缩存储

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

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

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

for(i=0;i<row*col;i++)

if(a[i]!=0)

{

M->data[k].i=i/col;

M->data[k].j=i%col;

M->data[k].e=a[i];

++k;

}

4.1特殊矩阵的压缩存储稀疏矩阵及其压缩存储1.三元组表的顺序存储及实现(1)创建稀疏矩阵M

if(k)

{M->tu=k;

M->mu=row;

M->nu=col;

return1;

}

else

return0;}4.1特殊矩阵的压缩存储稀疏矩阵及其压缩存储1.三元组表的顺序存储及实现(2)求稀疏矩阵M的转置矩阵T算法4.7求稀疏矩阵的转置intTransposeSMatrix(TSMatrixM,TSMatrix*T){intp,q,col;

T->mu=M.nu;

T->nu=M.mu;

T->tu=M.tu;

if(T->tu)

{q=0;

for(col=0;col<M.nu;++col) 4.1特殊矩阵的压缩存储稀疏矩阵及其压缩存储1.三元组表的顺序存储及实现(2)求稀疏矩阵M的转置矩阵T /*先将列转换成行*/

for(p=0;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].i;

T->data[q].e=M.data[p].e;

++q;

}

}

return1;}4.1特殊矩阵的压缩存储稀疏矩阵及其压缩存储1.三元组表的顺序存储及实现(2)求稀疏矩阵M的转置矩阵TM为m×n的矩阵，首先创建一个n×m的T矩阵，然后逐个将M矩阵的非零元素的行值赋给T矩阵的非零元素的列值，同时相应地将非零元素值赋给T矩阵。4.1特殊矩阵的压缩存储稀疏矩阵及其压缩存储2.三元组表的链式存储带行指针的单链表存储法该方法是把稀疏矩阵每行非零元素的三元组连接成一个单链表，并为每行的三元组链表设置一个表头指针。为此，要在每一个非零元素的三元组中增添一个指针域，指向本行下一个非零元素的三元组。由于相同的行的三元组节点中，都包含有相同的行号域，因此也可以把三元组里的行号域提取出来含在表头节点里，这时的单链表存储法如图4.8(b)所示。4.1特殊矩阵的压缩存储稀疏矩阵及其压缩存储2.三元组表的链式存储(1)带行指针的单链表存储法

图4.8带行指针的单链表存储法(a)带行指针的单链表存储法(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.2广义表广义表的定义广义表有以下特性（4）广义表是一种多层次的数据结构。广义表的元素可以是单元素，也可以是子表，而子表的元素还可以是子表。（5）广义表中元素可共享。列表可以为其它列表所共享。（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广义表广义表的存储结构及实现1.广义表的表示(1)广义表常用表示④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广义表广义表的存储结构及实现1.广义表的表示(2)广义表的深度一个表的“深度”是指表展开后所含括号的层数。表L、A、B、C的深度为分别为1、2、3、4，表D的深度为∞。4.2广义表广义表的存储结构及实现1.广义表的表示(3)带名称的广义表表示如果规定任何表都是有名称的，为了既表明每个表的名称，又说明它的组成，则可以在每个表的前面冠以该表的名称，于是上例中的各表又可以写成：①E()②L(a,b)③A(x,L(a,b))