第5章 数组与广义表

第5章组数和广义表

本章主要内容数组的定义及使用特殊矩阵广义表的定义及使用小结一、数组的定义及使用1.数组定义:是由n(n＞1)个相同类型数据元素a0，a1，…，an-1组成的有限序列，且该有限序列存储在一块地址连续的内存单元中，是顺序存储结构。一、数组的定义及使用2.数组的特点数组中的数据元素具有相同的数据类型。数组元素的位置：Loc(ai)=Loc(a0)+i*k数组是一种随机存储结构，可以根据给定的一组下标直接访问对应的数组元素二维数组，可将其转化为一维数组来考虑，每个元素是一个一维数组二维数组元素在计算机中的位置有行主序和列主序在行主序中：Loc(aij)=Loc(a00)+(i×n+j)×k(k为每个数据元素占用的存储单元数)返回行序为主序进行存储例：某一个二维数组a[n][n]a0,0a0,1a0,n-1………a1,0a1,1a0,n-1………an-2,0an-2,1…an-2,n-1an-1,0an-1,1…an-1,n-1第1行第2行第3~n-2行第n-1行第n行列序为主序进行存储例：某一个二维数组a[n][n]a0,0a0,1a0,n-1………a1,0a1,1a1,n-1………an-2,0an-2,1…an-2,n-1an-1,0an-1,1…an-1,n-1第1列第2列第3~n-1列第n列二、特殊矩阵的压缩存储一般情况下都是用二维数组来存储矩阵特殊矩阵怎么存储？有许多值相同的元素或有许多零元素，且分布有一定的规律的矩阵－特殊矩阵。1.对称矩阵2.三角矩阵3.稀疏矩阵下页介绍它们的存储方式1、对称矩阵

定义：在一个n阶方阵A中，若所有元素满足下述性质：

aij=aji

0≤i,j≤n-1

存储存储矩阵中上三角或下三角中的元素，存储到n(n+1)/2个元素的空间中，节约近一半假定按“行优先顺序”存储主对角线（包括对角线）以下的元素aij和sa[k]有对应关系：0a0,0a0,1a0,n-1………a1,0a1,1a1,n-1………an-2,0an-2,1…an-2,n-1an-1,0…an-1,n-1下图是一个对称矩阵kSa[k]ksa[k]行优先存储i=0,j=0i=jan-1,1i=0,j=1i<j1……i=0,j=n-1i<jn(n-1)/2i=1,j=0i>j1其他元素存储同理23a2,0，a0,2……n(n+1)/2-12、三角矩阵

定义：下(上)三角矩阵是指矩阵的上(下)三角（不包括主对角线）中的元素均为常数或零的n阶方阵上三角矩阵存储三角矩阵中的重复元素值为c可共享一个存储空间其余的n(n+1)/2元素用一维数组a[n(n+1)/2+1]存储，常量c放在数组最后一个单元aij和sa[k]有对应关系：如下三角矩阵：为何是这样？？请大家思考上三角矩阵的存储3、稀疏矩阵

定义：设矩阵Amn中有s个非零元素，若s远远小于矩阵元素的总数（即s<<m×n），则称A为稀疏矩阵；e=s/(m*n)为矩阵的稀疏因子。

存储

(1)采用压缩的方法来表示稀疏矩阵三元组(i，j，aij)表示任意一个矩阵元素，如aij!=0用一个按行序优先存储的线性顺序表（i，j，v）表示一个稀疏矩阵下页给出稀疏矩阵存储的C语言定义：＃defineMAXSIZE1000typedefstruct{inti,j;/*非零元素的行、列号*/DataTypev;/*非零元素的值*/}triple;typedefstruct{tripledata[maxsize];/*非零元素的三元组表*/intm,n,t;/*稀疏矩阵的行数、列数和非零元素的个数*/}tripletable;稀疏矩阵的转置算法转置：一个m×n的矩阵A，它的转置B是一个n×m的矩阵，且a[i][j]=b[j][i]如：目标：将矩阵稀疏A转置为稀疏B，并且保持存储的行序优先顺序，及B的存储顺序表也是按照B的行序优先两种算法：1.按列col(1≤col≤n)扫描三元表a.data，找出所有列号等于col的那些三元组，将它们的行号和列号互换后依次放入b.data中－跳着找，顺着存

2.先计算出A中每列第一元素在B的三元表中的存储位置（用pot[]数组保存），然后按行扫描A的三元表的元素－顺着找，跳着存

下页给出它们的C语言实现从视觉上看待转置？1)跳着找，顺着存

tripletabletransmatrix(tripletablea){/*将稀疏矩阵a转置，结果通过函数名返回*/tripletableb；intp,q,col;b.m=a.n;b.n=a.m;b.t=a.t;/*初始化*/if(b.t){/*把a中每一个非零元素转换到b中相应位置*/q=0;for(col=1;col<=a.n;col++)/*按列号作扫描，做cols趟*/for(p=0;p<a.t;p++)/*在数据中找列号为col的三元组*/if(a.data[p].j==col){b.data[q].i=col;/*新三元组的行号*/b.data[q].j=a.data[p].i;/*新三元组的列号*/b.data[q].v=a.data[p].v;/*新三元组的值*/q++;}}return(b);}时间代价主要消耗两个循环上，请看下页ijva.dataijvb.data127144211233645colb.m=a.n=5a.m=b.n=4a.t=b.t=5q=01232q=117q=224634q=341q=4531跳着找，顺着存稀疏矩阵转置完成算法一时间代价普通矩阵转置o(m*n)本算法：O(a.n*a.t)其中a.t为稀疏矩阵元素个数，当t≈m*n时间代价为O(m*n2)；本算法适用于T<<m*n使用两个一维数组num和pot，1)num[j]表示矩阵A中的第j列非零元素个数2)pot[j]表示A矩阵中第j列下一个非零元素在B中应存放的位置（初值为该列第一个非零元素在B中应存放的位置）。得出：pot[1]=0pot[j]=pot[j-1]+num[j-1]2≤j≤a.n

j12345num[j]12011pot[j]013342)顺序找，跳着存如图所示：ijva.dataj12345num[j]pot[j]127144211233645pot[1]=0pot[2]=pot[1]+num[1]=1ijvb.data10pot[3]=pot[2]+num[2]=321031pot[4]=pot[3]+num[3]=331pot[5]=pot[4]+num[4]=44pot[1]=0pot[j]=pot[j-1]+num[j-1]2≤j≤a.n12321724641

453

1转置算法二（顺取跳存）

tripletablefasttranstri(tripletablea){tripletableb；intp,q,col,k;intnum[a.n+1],pot[a.n+1];b.m=a.n;b.n=a.m;b.t=a.t;if(b.t){for(col=1;col<=a.n;++col)num[col]=0;

/*对数组num初始化*/for(k=0;k<a.t;++k)/*计算a中每一列含非零元素的个数*/++num[a.data[k].j];pot[1]=0;/*计算a中第col列中第一个非零元素在b中的序号*/for(col=2;col<=a.n;++col)

转置算法二（顺取跳存）

pot[col]=pot[col-1]+num[col-1];for(p=0;p<a.t;++p){/*把a中每一个非零元素插入到b中的相应位置*/col=a.data[p].j;q=pot[col];b.data[q].i=a.data[p].j;b.data[q].j=a.data[p].i;b.data[q].v=a.data[p].v;++pot[col];//修改为下次该列元素该存储的位置

}}return(b);}

效率分析：典型的牺牲空间换取时间的算法（类似于矩阵中寻找马鞍点的算法）时间效率：O(a.n+a.t)用十字链表存储稀疏矩阵稀疏矩阵稀疏矩阵的每个非零元素可用一个含5个域的结点表示，结点结构除了表示非零元素所在的行、列和值的三元组外，还增加了两个链域：指向本行中下一个非零元素行指针域right和指向本列下一个非零元素列指针域down。ijv127144213351426a.data00H100H500H400H300H25400H100H200H5000H400H3721441312624153Headpppppppqqqpqqpqpqqpqq结点结构typedefstructnode{introw,col;structnode*down,*right;union{structnode*next;DataTypevalue;}}crosslist;建立十字链表的算法

crosslist*creatclinkmat(){/*采用十字链表存储结构创建稀疏矩阵*/intm,n,t,k,i,j,v,s;crosslist*p,*q,*head,*cp[100];scanf(“%d,%d,%d”,&m,&n,&t);

/*输入稀疏矩阵的行数、列数和非零元素个数*/s=m>n?m:n;/*确定行、列表头结点个数,取行、列最大数即s=max{m,n}*