数据结构与算法 课件 第5章 数组和广义表

第5章数组和广义表数组和广义表都是线性表的扩展，其元素本身也是一种线性表。数组是一种常用的结构类型，几乎所有的程序设计语言都有数组类型。广义表是一种非线性的数据结构，是线性表的一种推广。1【本章重点】①数组的存储结构及元素地址的计算；②特殊矩阵、稀疏矩阵的压缩存储。2【本章难点】

稀疏矩阵的压缩存储。3【本章内容】数组特殊矩阵的压缩存储稀疏矩阵的压缩存储习题545.1数组数组的基本概念：数组中各元素具有相同的类型，数组元素具有值和确定元素位置的下标。数组可以是一维数组、二维数组、三维数组等等。一维数组又称为向量，多维数组是向量的扩充。一维数组可表示为An=[a1,a2,…,an]，每个数据元素对应一个数组下标，它具有线性表的结构，即除了第一个元素和最后一个元素，每个元素存在一个直接前驱元素和一个直接后继元素。5

6数组的存储结构一维数组的存储结构：一维数组的存储结构与线性表的顺序存储结构类似。二维数组的存储结构：存放二维数组或多维数组，就必须按照某种顺序将数组中的元素形成一个线性序列，然后将这个线性序列存放在内存中。（1）行优先顺序存储

将数组元素按行向量的顺序存储，即第i+1行的元素存放在第i行的元素之后。元素存储的线性序列为

a11,a12,…,a1n,a21,a22,…,a2n,…,am1,am2,…,amn（2）列优先顺序存储

将数组元素按列向量的顺序存储，即第j+1列的元素存放在第j列的元素之后。元素存储的线性序列为

a11,a21,…,am1,a12,a22,…,am2,…,a1n,a2n,…,amn7已知二维数组存储的起始地址，下标的上、下界，以及每个数组元素所占用的存储单元个数，就可以计算出元素aij的存储地址，从而对数组元素随机存取。二维数组A[c1..d1,c2..d2]按行优先的顺序存储在内存中，假设每个元素占d个存储单元，计算元素aij的地址公式：Loc(aij)=Loc(ac1c2)+[(i-c1)×(d2-c2+1)+j-c2]×d

其中Loc(ac1c2)是数组的起始地址，元素aij前面的i-c1行中共有(i-c1)×(d2-c2+1)个元素，第i行上元素aij前面又有j-c2个元素。二维数组A[c1..d1,c2..d2]按列优先的顺序存储在内存中，元素aij的地址计算公式：Loc(aij)=Loc(ac1c2)+[(j-c2)×(d1-c1+1)+i-c1]×d不难写出一维数组A[c..d]中元素ai的地址计算公式：Loc(ai)=Loc(ac)+(i-c+1)×d8【例5.1】假设二维数组按行优先的顺序存储，分别计算数组A[1..m,1..n]和A[0..m-1,0..n-1]中元素aij的地址。（1）行下标的下界是1，上界是m；列下标的下界是1，上界是n。元素aij的地址是 Loc(aij)=Loc(a11)+[(i-1)×n+j-1]×d（2）行下标的下界是0，上界是m-1；列下标的下界是0，上界是n-1。元素aij的地址是 Loc(aij)=Loc(a00)+(i×n+j)×d95.2

特殊矩阵的压缩存储

特殊矩阵是指n阶方阵中非零元素或零元素的分布具有一定的规律。特殊矩阵的压缩存储就是为多个值相同的元素只分配一个存储空间，零元素不分配存储空间，从而达到节省存储空间的目的。1、三角矩阵

在n阶方阵中，以主对角线划分，如果矩阵的下三角（不包括主对角线）中的元素均为值相同的常数，则称为上三角矩阵，反之称为下三角矩阵。

在多数情况下，三角矩阵的常数为零。10（a）上三角矩阵（b）下三角矩阵用向量A[0..n(n+1)/2]压缩存储三角矩阵，其中A[0]~A[n(n+1)/2-1]存储矩阵的下（上）三角中的元素，向量的最后一个分量A[n(n+1)/2]存储三角矩阵中的常数。如何根据矩阵元素的下标i、j，计算矩阵元素在一维数组中的下标k。（1）下三角矩阵按行优先的顺序存储，A[k]与aij的对应关系为（2）上三角矩阵按列优先的顺序存储，A[k]与aij的对应关系为11

【例】分别采用一维数组存储4阶下三角矩阵和上三角矩阵。12

2、对称矩阵若n阶方阵A中的元素关于主对角线对称，即满足下述性质：则称A为对称矩阵。如果采用一维数组存储矩阵中的上三角或下三角元素，使对称的两个元素共享同一个存储空间，可以节省近一半的存储空间。可以用向量A[0..n(n+1)/2-1]压缩存储对称矩阵。对于下三角部分的元素aij（i>j），可以看作按行优先的顺序存储，A[k]与aij的对应关系为：对于上三角部分的元素aij（i<j），可以看作按列优先的顺序存储，A[k]与aij的对应关系为：13

【例】一个4阶对称方阵，按行优先的顺序存储下三角矩阵，按列优先的顺序存储上三角矩阵。14

3、对角矩阵对角矩阵是指方阵中的所有非零元素集中在以主对角线为中心的带状区域内，带状区域之外的元素值均为零。对角矩阵的带宽可以是3，5，7，...带宽为3的对角矩阵又称为三对角矩阵。当|i-j|>1时，元素aij为0。一般地，对于k对角矩阵（k为奇数），当|i-j|>(k-1)/2时，元素aij为0。15

n阶三对角矩阵有3n-2个非零元素，采用向量A[0..3n-3]按行优先的顺序压缩存储三对角矩阵。每个非零元素与向量下标的对应关系为16

A[2(i-1)+j-1]=aij

1≤i≤n，i-1≤j≤i+1稀疏矩阵的定义：设矩阵Amn中有t个非零元素，若t远远小于矩阵元素的总数（即t<<m×n，），并且非零元素在矩阵中的分布没有规律，则称A为稀疏矩阵。存储系数矩阵中的非零元素，除了存储元素值外，还必须存储该元素的位置信息。通常对稀疏矩阵进行压缩存储可以采用顺序存储结构的三元组表或者链式存储结构的十字链表。175.3稀疏矩阵的压缩存储1、稀疏矩阵的三元组表存储将稀疏矩阵中的非零元素的行号、列号和元素值作为一个三元组（i，j，aij）所有非零元素的三元组按行优先（或列优先）的顺序排列，便得到一个其结点均是三元组的线性表——三元组表。三元组表的结构类型定义描述为#defineMaxSize1000//最大非零元素个数typedefintdatatype;typedefstruct{inti,j;//非零元素的行、列号datatypev;//非零元素的元素值}Node;//三元组结构类型typedefstruct{intm,n,t;//行数,列数,非零元素个数Nodedata[MaxSize];//存放三元组表的向量}spmatrix;//稀疏矩阵的三元组表结构类型18【例】用三元组表存储稀疏矩阵。19矩阵的转置（用三元组表存储矩阵）20算法5.1矩阵的转置（用三元组表存储矩阵）voidTransMat(spmatrix*a,spmayrix*b)//返回稀疏矩阵A的转置，ano和bno分别指示a→data和b→data中结点序号//col指示*a的列号(即*b的行号){intano,bno,col;b->m=a->n;b->n=a->m;//A和B的行列数交换b->t=a->t;//非零元素个数if(b->t>0)//有非零元素，则转置{bno=0；for(col=1;col<=a->n;col++)//按*a的列序转置，对a->data扫描n趟 for(ano=0;ano<a->t;ano++)//扫描一趟三元组表 if(a->data[ano].j==col){//列号为col则进行置换 b->data[bno].i=a->data[ano].j;//a的列号变为b的行号 b->data[bno].j=a->data[ano].i;//a的行号变为b的列号 b->data[bno].v=a->data[ano].v; bno++;//b->data结点序号加1 }}}//TransMat算法的基本思想是：对a->data按列扫描n趟，在第col趟扫描中，找出所