第5章数组与广义表.docx
《第5章数组与广义表.docx》由会员分享，可在线阅读，更多相关《第5章数组与广义表.docx（44页珍藏版）》请在冰点文库上搜索。
第5章数组与广义表
第5章数组与广义表
5.1数组的基本概念
1.数组的定义2.数组与线性表3.数组的抽象数据类型
1.数组的定义
数组是由类型相同的数据元素构成的有序集合，每个数据元素称为一个数组元素（简称元素），每个元素受n（n≥1）个线性关系的约束，每个元素在n个线性关系中的序号j1，j2，…，jn，称为该元素的下标，并称该数组为n维数组。
理解数组的定义要把握以下要点：
⑴元素推广性：
元素本身可以具有某种结构，而不限定是单个的数据元素。
⑵元素同一性：
元素具有相同的数据类型。
⑶关系确定性：
每个元素均受n（n≥1）个线性关系的约束，元素个数和元素之间的关系一般不发生变动。
2.数组与线性表
⑴线性表的顺序存储结构常借助一维数组来描述。
⑵数组是线性表的推广。
⑶数组的操作只能是存取和修改，而线性表除此之外还可以做插入与删除等操作。
数组是线性表的推广
将线性表中数据元素的类型扩充为线性表，例如，对于一个m行n列的二维数组Am×n可以看成是长度为m的线性表（每一行为线性表中的一个元素，它本身又是一个长度为n的线性表），或者是长度为n的线性表（每一列为线性表中的一个元素，它本身又是一个长度为m的线性表）。
即此时的线性表中的元素本身也是一个线性表，如图5.1所示。
图5.1
3.数组的抽象数据类型
ADTArray{
Data：
数据元素具有相同类型。
每个元素均受n（n≥1）个线性关系的约束并由一组下标唯一标识。
Operation：
InitArray（&A，dim，bound1，…，boundn）
操作结果：
若维数dim和各维长度合法，则构造相应的数组A。
DestroyArray（&A）
初始条件：
A是n维数组。
操作结果：
撤销数组A。
Value（A，&e，index1，…，indexn）
初始条件：
A是n维数组，e为元素变量，随后是n个下标值。
操作结果：
若各下标不超界，则e赋值为所指定的A的元素值。
Assign（A，e，index1，…，indexn）
初始条件：
A是n维数组，e为元素变量，随后是n个下标值。
操作结果：
若下标不超界，则将e的值赋给所指定的A的元素。
Locate（A,va_listap,int&off）
初始条件：
A是n维数组，ap指示一组下标。
操作结果：
若ap指示的各下标值合法，则求出该元素在A中的相对地址off
}ADTArray
5.2数组的存储结构
1.一维数组的存储2.二维数组的存储3.n维数组的存储
1.一维数组的存储
对于一维数组，因为元素之间的关系是线性的，所以一维数组就顺序地存放在一段连续的存储单元中。
如图5.2，设数组a[n]的每个元素占有L个存储单元，其第一个元素的存储首址表示为Loc（a0），则数组a中第i个元素（0≤i≤n-1）的存储首址为：
Loc（ai）=loc（a0）+i×L
图5.2
2.二维数组的存储
用一组连续的存储单元存放二维数组的数据元素，一般有两种存储方式：
一种以行序为主序的存储方式，一种是以列序为主序的存储方式。
行序为主序
对一个如图5.1所示的m行n列的二维数组Am×n，以行序为主序存储时，二维数组的线性排列次序为：
其中,二维数组中任一数据元素的存储首址为（其中n为列数）：
Loc（aij）=Loc（a00）+（i×n+j）×L
列序为主序
以列序为主序存储时，二维数组的线性排列次序为：
其中,二维数组中任一数据元素的存储首址为（其中m为行数）：
Loc（aij）=Loc（a00）+（j×m+i）×L
3.n维数组的存储
n维数组的数据元素的存储原理类同于二维数组，一般也采用以行序为主序和以列序为主序两种存储方法。
若以行序为主序，设bi为n维数组第i维的长度（i=1,2,…,n）,则下标为j1,j2,…,jn（0≤ji≤bi-1）的元素的存储首地址可由下式计算：
Loc（aj1,j2,…,jn）
=Loc（a0,0,…，o）+（b2×…×bn×j1+b3×…×bn×j2+…+bn×jn-1+jn）×L
可缩写成：
其中，cn=L,ci-1=bi×ci，1上式称为n维数组的映象函数。
容易看出，数组元素的存储位置是其下标的线性函数。
一旦确定了数组各维的长度、数组元素的类型，则ci、bi和L均为常数，计算各个元素存储位置的时间相等，所以，存取数组中任一元素的时间也相等，所以数组是随机存储结构。
5.3数组的顺序存储及其操作
5.3.1数组的顺序存储表示5.3.2数组的基本操作5.3.3数组的应用举例
5.3.1数组的顺序存储表示
按存储空间分配的不同，数组的顺序存储可分为：
静态存储分配的数组和动态存储分配的数组。
一般在高级程序设计语言中的数组（如矩阵）均采用静态存储分配方式，其相关操作的实现较为简单。
动态存储分配的数组其数组的维数、空间大小可根据实际需要确定，因而较灵活，但相关操作的实现较复杂。
下面是动态存储分配的数组的存储表示。
#defineMAX_ARRAY_DIM8//假设数组维数的最大值为8
typedefstruct{
ElemType*base;//数组元素基址，由InitArray分配
intdim;//数组维数
int*b;//数组维界基址，由InitArray分配
int*c;//数组映象函数常量基址，由InitArray分配
}Array;
5.3.2数组的基本操作
1.初始化2.元素的定位3.取元素4.存元素5.撤销数组6.总结
1.初始化
数组的初始化就是构造一个空的数组A，也就是说数组A有一定的相邻空间，但目前无数据元素。
具体操作包括：
确定数组的维数以及每一维的长度、计算数组元素总数、计算数组映象函数常量ci、并为n维数组分配存储空间（下列算法中函数va_start（）、va_arg（）、va_end（）和类型va_list在文件stdarg.h中）。
其算法描述见算法5.1。
算法5.1
boolInitArray（Array&A,intdim,...）
{intelemtotal=1,i;
va_listap;
f（dim<1||dim>MAX_ARRAY_DIM）returnfalse;
A.dim=dim;//数组维数
A.b=（int*）malloc（dim*sizeof（int））;//动态分配数组维界基址
if（!
A.b）exit
（1）;
va_start（ap,dim）;//变长参数“...”从形参dim之后开始
for（i=0;i{A.b[i]=va_arg（ap,int）;//逐一将变长参数（各维长度）赋给A.b[i]
if（A.b[i]<0）returnfalse;//长度不合法
elemtotal*=A.b[i];//求出A的元素总数
}
va_end（ap）;//结束提取变长参数
A.base=（ElemType*）malloc（elemtotal*sizeof（ElemType））;
if（!
A.base）exit
（1）;
A.c=（int*）malloc（dim*sizeof（int））;//动态分配数组偏移量基址
if（!
A.c）exit
（1）;
A.c[dim-1]=1;//最后一维的偏移量为1
//L=1,指针的增减以元素的大小为单位
for（i=dim-2;i>=0;--i）
A.c[i]=A.b[i+1]*A.c[i+1];//每一维的偏移量
returntrue;
}//InitArray
2.元素的定位
boolLocate（ArrayA,va_listap,int&off）
{//给定一组下标，求该元素在数组A中的相对地址off
inti,ind;
off=0;
for（i=0;i{ind=va_arg（ap,int）;//逐一读取各维的下标值
if（ind<0||ind>=A.b[i]）returnfalse;
off+=A.c[i]*ind;
}
returntrue;
}//Locate
3.取元素
boolValue（ElemType&e,ArrayA,...）
{
va_listap;
intoff;
va_start（ap,A）;
if（!
Locate（A,ap,off））returnfalse;
e=*（A.base+off）;
returntrue;
}//Value
4.存元素
boolAssign（ArrayA,ElemTypee,...）
{
va_listap;
intoff;
va_start（ap,e）;
if（!
Locate（A,ap,off））
returnfalse;
*（A.base+off）=e;
returntrue;
}//Assign
5.撤销数组
voidDestroyArray（Array&A）
{
if（A.base）free（A.base）;
if（A.b）free（A.b）;
if（A.c）free（A.c）;
A.base=A.b=A.c=NULL;
A.dim=0;
}//DestroyArray
6.总结
⑴在对数组的相关操作中，随着所构造的数组的维数不同，参数的个数也不同，用变长参数“…”就能很好地解决这一问题。
即“…”可用若干个参数取代。
如果是二维数组，参数中则要包含两维的长度，即两个整型量；而如果是三维数组，则参数中要包含三个整型参数。
其实，C语言中的printf（）就是含有变长参数表的库函数，它的第1个参数是字符串常量或字符串指针，第2个形参则是变长参数表。
因此，我们可以在1个printf（）函数中输出任意个表达式的值。
⑵在上述算法中创建的数组占用一段连续的内存空间，访问数组元素是先通过一组下标计算相对地址，然后加上数组基址，找到真正的数组元素，这一过程叫寻址。
5.3.3数组的应用举例
1.问题描述
2.算法思想
3.算法描述
1.问题描述
例5.1寻找两个字符串中的最长公共子串。
假设string1="sgabacbadfgbacst，string2="gabadfgab"则最长公共子串为"badfg"。
2.算法思想
利用二维数组存储两个串中对应字符的分布特点，其算法思想为：
⑴利用二维数组mat[n][m]建立两个串之间的“对应矩阵”（对应矩阵是存储两个串中对应字符的分布特点）：
若string2[i]=stringl[j]，则mat[i][j]=1；否则mat[i][j]=0，显然，和矩阵对角上连续出现的l相对应的是两个串的共同子串。
如图5.3是本例所设两个串的对应矩阵。
⑵检查矩阵中所有对角线，找出在对角线上连续出现1的最长段。
扫描对角线时，首先必须解决沿主对角线平行方向扫描时的下标控制问题。
同一条对角线上的元素都受一个特征量的制约，与主对角线平行的各条对角线的特征量由其上元素行列坐标之差给出，例如主对角线上元素的行列坐标之差为零，特征量也是零。
若二维数组为mat[n][m]，则最右上对角线和最左下对角线都只有一个元素，特征量分别为-（m-1）和n-1。
图5.3
3.算法描述
假设以len记当前被扫描对角线上连续出现的1的长度，maxlen记已经得到的最长公共子串的长度，设eq为当前状态的标志，其值为1时表明当前处在“进行子串匹配”的状态中，换句话说就是，当前的状态为：
前一对字符比较相等（即当前对角线上前一元素的值为1），现在继续比较下一对字符。
本例的算法描述由下列模块构成：
求对角线上各段连续出现1的最长长度、求所有对角线上连续出现1的最长长度、求最长公共子串。
求对角线上各段连续出现1的最长长度
voiddiagscan（Arraymat,int&maxlen,int&jpos,inti,intj）
{//求该对角线上各段连续1的最长长度maxlen和起始位置jpos
inteq=0,len=0,sj;
ElemTypee;
while（i{Value（e,mat,i,j）;//将mat[i][j]的值赋给e
if（e==1）
{len++;
if（!
eq）{sj=j;eq=1;}//出现的第一个1,记下起始位置,改变状态
}
elseif（eq）//求得一个公共子串
{if（len>maxlen）//是到目前为止求得的最长公共子串
{maxlen=len;jpos=sj;}
eq=0;len=0;//重新开始求新的一段连续出现的1
}
i++;j++;//继续考察该对角线上当前的下一元素
}
}//diagscan
求所有对角线上连续出现1的最长长度
voiddiagmax1（Arraymat,int&maxlen,int&jpos）
{
inti,j,k,istart;
ElemTypee;
istart=0;
for（k=-（len1-1）;k<=len2-1;k++）
{i=istart;
j=i-k;
diagscan（mat,maxlen,jpos,i,j）;
if（k>=0）istart++;
}
DestroyArray（mat）;
}//diagmax1
⑶求最长公共子串
intmaxsamesubstring（char*string1,char*string2,char*sub）
{
ElemTypee;
char*p1,*p2;;
inti,j,maxlen,jpos;
Arraymat;
len1=strlen（string1）;len2=strlen（string2）;
InitArray（mat,2,len2,len1）;
p1=string2;p2=string1;
for（i=0;ifor（j=0;jif（*（p1+i）==*（p2+j））Assign（mat,1,i,j）;
elseAssign（mat,0,i,j）;
diagmax1（mat,maxlen,jpos）;
if（maxlen==0）*sub='\0';
elseSubString（sub,string1,jpos,maxlen）;
returnmaxlen;
}//maxsamesubstring
5.4矩阵的压缩存储
5.4.1压缩存储的思想5.4.2特殊矩阵的压缩存储5.4.3稀疏矩阵的压缩存储
5.4.1压缩存储的思想
压缩存储一般是针对矩阵中包含了大量的值相同的元素或零元素的矩阵，其基本思想是：
⑴为多个值相同的元素只分配一个存储空间；
⑵对零元素不分配存储空间。
如果矩阵中有许多值相同的元素或零元素且它们的分布有一定规律，则称它为特殊矩阵；如果矩阵中有许多零元素并且零元素的分布没有规律，则称它们为稀疏矩阵。
这两类矩阵适合进行压缩存储。
5.4.2特殊矩阵的压缩存储
1.对称矩阵的压缩存储2.三角矩阵的压缩存储3.对角矩阵的压缩存储4.总结
1.对称矩阵的压缩存储
⑴对称矩阵的定义⑵对称矩阵的压缩存储原理
⑴对称矩阵的定义
一个n阶方阵A中的元素满足aij=aji（0≤i,j≤n-1），则称其为n阶对称矩阵，如图5.4所示。
图5.4
⑵对称矩阵的压缩存储原理
对称矩阵是关于主对角线对称的，因此只需要存储下三角（或上三角）部分，即为每对对称元素仅分配一个存储空间，这样n2个元素被压缩到n（n+1）/2个元素的空间中。
假设以行为主序来存储n阶对称矩阵A的下三角（包括对角线）中的元素，并以一维数组Va[n（n+1）/2]作为矩阵A的存储结构，其中Va[k]存放元素aij，则Va[k]和矩阵元素aij之间存在着如下对应关系：
由上式可知，对于任意给定的一组下标（i,j）均可在数组Va中找到矩阵元素aij；反之，对所有的k（k=0,1,2,…,n（n+1）/2-1）都能确定Va[k]中的矩阵元素在矩阵中的位置（i,j）。
由此称一维数组Va[n（n+1）/2]为n阶对称矩阵A的压缩存储。
压缩存储后n阶对称矩阵A的数据元素在一维数组Va中对应的位置关系如图5.5所示。
图5.5
2.三角矩阵的压缩存储
⑴三角矩阵的定义⑵三角矩阵的压缩存储原理
⑴三角矩阵的定义
三角矩阵有上、下三角之分，其特征是矩阵的下（上）三角（不包括对角线）中的元素均为常数（或零）的n阶矩阵，如图5.6所示。
图5.6
⑵三角矩阵的压缩存储原理
三角矩阵的压缩存储与对称矩阵类似，不同之处仅在于除了存储下（上）三角的元素以外，还要存储对角线上（下）方的常数。
因为是同一个常数，所以只存一个即可。
这样，一共需要n（n+1）/2+1个元素的存储空间。
假设以数组Va[n（n+1）/2+1]作为n阶下三角矩阵A的存储结构，其中数组Va中的最后一元素存储常数或零。
则A中任一元素aij和Va[k]之间存在着如下对应关系：
其中Va[n（n+1）/2]中存放常数c（c也可为0）。
3.对角矩阵的压缩存储
⑴对角矩阵的定义⑵对角矩阵的压缩存储原理
⑴对角矩阵的定义
在对角矩阵中，所有的非零元素都集中在以主对角线为中心的带状区域中，除了主对角线上和它的上下方的若干条对角线的元素之外，所有其它的元素皆为零。
占有非零元素的对角线的个数称为带宽，因此，对角矩阵也称带状矩阵。
图5.7所示为对角矩阵，其带宽为2b+1（b称为矩阵半带宽）。
对于半带宽为b（0≤b≤（n-1）/2）的对角矩阵，其|i-j|≤b的元素aij不为零，其余元素都为零。
此时，也可以按照某个原则（或以行为主，或以主对角线的顺序）将其压缩到一维数组上。
图5.7
⑵对角矩阵的压缩存储原理
以行序为主序，对如图5.8所示三对角矩阵（b=1）进行压缩存储。
对于n阶三对角矩阵A，其非零元素总数为：
3n-2，因而可将其非零元素存储到一维数组Va[3n-2]中，其中aij存储存储到Va[k]中。
则A中任一元素aij和Va[k]之间存在如下的对应关系：
①|i-j|>1：
元素aij位于三条对角线以外，是零元素不需要存储；
②|i-j|≤1：
元素aij位于三条对角线上，则k=2i+j。
图5.8
4.总结
对特殊矩阵如对称矩阵、三角矩阵、对角矩阵等的压缩存储方法是：
找出这些特殊矩阵中特殊元素的分布规律，把那些有一定分布规律的、值相同的元素（包括零）压缩存储到一个存储空间中。
这样的压缩存储只需在算法中按公式作一映射即可实现矩阵元素的随机存取。
5.4.3稀疏矩阵的压缩存储
1.三元组线性表2.稀疏矩阵的存储结构表示3.稀疏矩阵的基本操作
1.三元组线性表
稀疏矩阵的压缩存储方法是只存储非零元素。
由于在稀疏矩阵中非零元素的分布没有规律，为了反映出稀疏矩阵中数据元素之间的相互关系，所以仅存储非零元素的值是不够的，还必须同时存储该非零元素在矩阵中的行下标和列下标。
这样稀疏矩阵中的每一个非零元素需由一个三元组（行下标，列下标，非零元素值）唯一确定，稀疏矩阵中所有非零元素构成三元组线性表。
如图5.9所示
。
三元组线性表中一个元素是用来描述一个非零元素的信息，其结构描述如下：
typedefstruct{
inti;//行下标
intj;//列下标
ElemTypee;//非零元素值
}Triple;
图5.9
2.稀疏矩阵的存储结构表示
⑴顺序存储⑵链式存储
⑴顺序存储
◆三元组顺序表
◆三元组顺序表的结构描述
三元组顺序表
稀疏矩阵的顺序存储就是用一段连续的存储单元依次存储其对应的三元组线性表，并称这种存储结构的三元组线性表为三元组顺序表。
图5.9所示的稀疏矩阵的三元组顺序表如图5.10所示。
说明：
⑴稀疏矩阵进行压缩存储后，矩阵的行数和列数不能显式的反映出来，这样，如果压缩存储时仅仅存储稀疏矩阵中非零元素，就有可能出现不同的稀疏矩阵对应同一个三元组线性表，因此，要唯一地表示一个稀疏矩阵，还必须在存储三元组线性表的同时存储整个矩阵的行数和列数以及非零元素的个数。
⑵虽然稀疏矩阵中没有插入和删除操作，但是，稀疏矩阵在进行相关运算如两个矩阵相加、矩阵的修改等操作都有可能使得稀疏矩阵的非零元素的个数发生改变，因此，描述三元组顺序表的存储结构时需要为稀疏矩阵的相关操作预留存储空间。
三元组顺序表的结构描述
设稀疏矩阵非零元素的最大个数为MAX_SIZE，则三元组顺序表的结构描述如下：
#defineMAX_SIZE100
typedefstruct{
intm,n,t;
Tripledata[MAX_SIZE];
}TSMatrix;
其中，data域中表示的非零元素的三元组是以行序为主序顺序排列，它是一种下标按行有序的存储结构。
图5.10
⑵链式存储
①三元组单链表②行指针数组链表③十字链表
①三元组单链表
用指针依次把稀疏矩阵中非零元素的三元组链接起来，就构成了稀疏矩阵的三元组单链表。
在三元组单链表中，每个结点的数据域由稀疏矩阵中非零元素的行下标、列下标和元素值组成，单链表的头结点中存放稀疏矩阵的行数和列数。
其结点的结构描述如下：
typedefstructTripleNode{
inti;
intj;
ElemTypee;
structTripleNode*next;
}TLink;
利用Tlink类型的对象存储图5.9所示的稀疏矩阵，则链式存储结构如图5.11所示。
这种存储结构的缺点是实现矩阵相关操作算法时间复杂度高。
因为当要访问某行某列中的一个元素时，必须从头指针进入后逐个结点查找，这是链式存储结构的非随机存取特性限定的。
图5.11
②行指针数组链表
将稀疏矩阵中每一行的非零元素的三元组按列号从小到大的顺序链接成一个单链表，并为每一行设计一个头指针，所有头指针构成一个指针数组，指针数组中的每一行的头指针指向该行三元组单链表的第一个数据元素结点。
换句话说，每一行的单链表是仅由该行三元组元素结点构成的单链表，该单链表由指针数组中对应该行的头指针域指示。
称这种结构的三元组链表为行指针数组链表。
其如下：
#defineMAX_SIZE100
typedefstruct{
intm,n,t;
Tlink*data[MAX_SIZE];
}TSMatrix;
利用TSMatrix类型的对象存储图5.9所示的稀疏矩阵，则链式存储结构如图5.12所示。
这种存储结构的特点是：
对于
升级会员 