栈和队列多维数组Word格式文档下载.docx
《栈和队列多维数组Word格式文档下载.docx》由会员分享，可在线阅读，更多相关《栈和队列多维数组Word格式文档下载.docx（9页珍藏版）》请在冰点文库上搜索。
二维数组中每个元素aij均属于两个向量：
第i行的行向量和第j列的列向量。
因此，除边界外，每个元素aij都恰好有两个直接前趋和直接后继：
行向量上的直接前趋aij-1和直接后继aij+1，列向量上的直接前趋ai-1j和直接后继ai+1j。
并且有且仅有一个开始结点a11，它没有直接前趋；
有且仅有一个终端结点amn，它没有直接后继。
另外，边界上的结点（开始结点和终端结点除外）只有一个直接前趋或者只有一个直接后继。
即除开始结点a11外，第一行和第一列上的结点：
a1j（j=2,...,n）,ai1（i=2,...,m）都只有一个直接前趋；
除终端结点amn外，第m行和第n列上的结点amj（j=1,...,n-1）,ain（i=1,...,m-1）都只有一个直接后继。
同样，三维数组Amnp中的每个元素aijk都属于三个向量，每个元素最多可以有三个直接前趋除和三个直接后继。
依次类推，m维数组An1n2...nm每个元素ai1i2...im都属于m个向量，最多可以有m个直接前趋除和m个直接后继。
数组通常只有两种基本运算——读和写。
①读：
给定一组下标，读取相应的数据元素。
②写：
给定一组下标，修改相应的数据元素。
值得注意的是，多维数组的数据元素的类型elementype可根据实际需要而定义。
相应地，读、写运算可以读取或修改一个数据元素的一部分而不必一定是整个元素。
二、多维数组的存储结构
计算机的内存结构是一维的。
因此，用一维内存来表示多维数组就必须按某种次序将数组元素排成一个线性的序列，然后的将这个线性序列顺序存放在存储器中。
多维数组的类型定义可以直接用高级程序设计语言中的数组类型给出,也就是说多维数组在语言级的存储表示是数组类型。
相应地，读写运算在高级语言里的实现手段是下标变量和赋值操作。
因为几乎所有高级语言都有数组类型，人们常说多维数组是一种“已经在高级语言中实现了”的数据结构。
以下着重讨论多维数组的机器级实现。
通常采用顺序存储结构来存放数组。
对二维数组可有两种存储方式：
一种是以列序为主序的存储方式，另一种是以行为主序的存储方式，如图3-14所示。
a11
a21
┇
am1
a12
a22
am2
a1n
a2n
amn
┇
（a）以列为主序
（b）以行为主序
图3-14
在有的高级语言象pascal语言的编译器中,数组用的是以行序为主序的存储方法，有的高级语言象FORTRAN语言,用的是以列序为主序的存储方法。
对于数组，一旦定义了它的维数和各维的上、下界，便可为它分配存储空间，给出一组下标即可求得相应数组元素的存储位置，下面以行序为主序的存储结构为例说明位置和下标关系。
假定数组A:
array[c1..d1,c2..d2]ofdatatype每个数据元素占k个存储单元,二维数组中任一元素的存储位置可由下式确定：
loc[i,j]=loc[c1,c2]+[（d2-c2+1）（i-c1）+（j-c2）]*k
loc[c1,c2]是a[c1,c2]的存储位置，它是该二维数组的起始地址，也称基地址。
loc[i,j]是aij的存储位置,这个式确定了数组元素和下标关系。
由上式可知，数组元素的存储位置是下标的线性函数，计算存储位置所需的时间仅取决于乘法的时间。
因此，存取任一元素的时间相等。
通常将具有这一特点的存储结构称为“随机存储结构”。
三、矩阵的压缩存储
在实际问题中经常会碰到阶数很高的矩阵，而且矩阵中有许多值相同的元素或零元素。
为了节省存储空间，对这类矩阵可以进行压缩存储。
压缩存储的基本思想是：
值相同的多个元素只分配一个存储空间，零元素不分配空间。
我们把需要压缩存储的矩阵分为两种：
特殊矩阵和稀疏矩阵。
值相同的元素或者零元素在矩阵中分布有一定规律的矩阵叫特殊矩阵。
矩阵中零元素远远多于非零元素、并且非零元素的分布没有规律的矩阵称为稀疏矩阵。
下面分别讨论。
1.特殊矩阵
这里主要讨论对称矩阵和三角矩阵。
（1）对称矩阵
若一个n阶方阵A中的元素满足下述性质
aij=aji1≤i,j≤n
则A称为对称矩阵。
例如下图便是一个4阶的对称矩阵
┌2156┐
│1401│
│5053│
└6135┘
对称矩阵中有的元素关于主对角线对称，我们为每一对对称元素只分配一个存储空间，则可将n2个元素压缩存储到n（n+1）/2个元素的存储空间中。
我们可以存储矩阵中主对角线上的元素，也可以存储矩阵中主对角线以下的元素。
不失一般性，现以行序为主序存储其下三角（包括对角线）中的元素，参见图3-15。
1 a11
2 a21a22
3 a31a32a33
……… aji（j>
=i） 存入 aij 中
i-1 ai-11ai-12…ai-1i-1
i ai1ai2…aij…aii K=1+2+3+...+（i-1）+j=i（i-1）/2+j
……… （i>
=j）
n an1an2an3…… ……ann
图3-15对称矩阵的下三角部分
假设以一维数组M（1:
n（n+1）/2）作为对称矩阵A的存储结构,存储情况如图3-16所示。
a11
a31
...
an1
ann
K=
1
2
3
4
n（n-1）
+1
...
n（n+1）
数组M和矩阵A间下标存在着如下对应关系：
k=
┌
│
└
i（i-1）
j（j-1）
+j
+i
当i>
=j
当i<
J<
FONT>
即任给矩阵A中的一个元素aij，根据它的下标（i,j），就能由上述公式确定其在数组M中的位置k。
而aij在内存的存储地址可用下列公式求出（假设每个数据元素占用L个存储单元）：
LOC（aij）=LOC（M[k]）=LOC（M[1]）+（k-1）*L
（2）三角矩阵
以上对角线划分,三角矩阵有上三角和下三角两种,所谓上（下）三角矩阵是指矩阵的下（上）三角（不包括对角线）中元素均为常数C或零的n阶矩阵.如图3-17所示。
三角矩阵中重复元素C可共享一个存储空间,其余元素和对称矩阵一样正好有n*（n+1）/2个，因此，三角矩阵可压缩存储到数组M[1..n*（n+1）/2+1]中，其中c若非0，则存放到数组的最后一个下标变量中。
┌a11a12...a1n┐ ┌a11ac1...ac1┐
│cc1a22...a2n│ │a21a22...ac1│
│c2...22...a2n│ │a2...22...ac1│
└cc1cc2...ann┘ └an1an2...ann┘
（a）上三角矩阵 （b）下三角矩阵
图3-17三角矩阵
上三角矩阵中，主对角线上的第t行（1≤t≤n）有n-t+1个元素，按行优先顺序存放上三角阵中的元素aij时，aij之前的前i-1行共有
i-1
∑
t=1
（n-t+1）＝
（2n-i+2）
个元素，在i第行上，aij是该行的第j-i+1个元素，M[k]和aij的对应关系是：
（i-1）
（2n-i+2）+j-i+1
+1
j
当i＞j时，aij=c，c存放在M[n（n-1）/2+1]中。
下三角矩阵的存储和对称矩阵类似，M[k]和aij的对应关系是：
+1
2.稀疏矩阵
一般地，设矩阵Amn中有S个非零元素，若S远远小于矩阵元素的个数（s＜＜m×
n），并且非零元素的分布没有规律，则称A为稀疏矩阵。
稀疏矩阵的压缩存储方法是只存储非零元素。
对每个非零元素aij，可以用一个三元组（i,j,aij）唯一确定，其中aij表示该非零元素的值，i,j为该元素在原矩阵中的行号和列号。
然后将所有非零元素的三元组按一定次序排列在一起构成三元组表。
例如图3-18中的稀疏矩阵中A可表示成如下的三元组表。
（（1,2,3）,（1,6,1）,（3,1,5）,（3,2,-1）,（4,5,4）,（5,1,-3））
┌ 0 3 0 0 0 1┐
│ 0 0 0 0 0 0│
A=│ 5-1 0 0 0 0│
│ 0 0 0 0 4 0│
└-3 0 0 0 0 0┘
图3-18稀疏矩阵A
我们以二维数组表示三元组表.显然,要唯一确定一个稀疏矩阵,还必须存储该矩阵的行数和列数。
为了运算方面我们还将非零元素的个数，与三元组表存储在一起，三元组表的类型说明如下：
constmax_num={大于非0个数的某个常量};
max_mn=max{m,n};
typenode=record
i,j:
integer;
v:
datatype;
end;
spmatrix=record
mu,nu,tu:
//行数、列数，非零元素个数//
data:
array[1..max_num]ofnode;
end;
三元组的结点为：
i
v
其中，v为非零元素，i为v所在矩阵的行数，j为v秘在矩阵的列数。
下面讨论在这种压缩存储结构上如何实现矩阵的转置。
图3-18稀疏矩阵A的三元组表如下：
5
6
-1
-3
A的转置矩阵A＇的三元组表为：
A＇=
┌0 0 5 0-3┐
│3 0-1 0 0│
│0 0 0 0 0│
│0 0 0 4 0│
└1 0 0 0 0┘
转置的方法：
按照A的列序来进行转置，即在A的三元组中按照列号从小到大的次序建立起A＇的三元组。
为了找到A中的每一列中所有的非零元素，需要对A的三元组表从第一行起扫描各个三元组，具体算法如下：
proceduretrans_sparmat（varb:
spmatrix;
a:
spmatrix）;
//a是稀疏矩阵A的三元组，b表示稀疏矩阵A`的三元组//
begin
b.mu:
=a.nu;
b.nu:
=a.mu;
b.tu:
=a.tu;
//mu，nu，tu分别表示稀疏矩阵的行值列值和非零元个数//
ifb.tu≠0then
[q:
=1;
forcol:
=1toa.nudo
forp:
=1toa.tudo
ifa.data[p].j=col
then[b.data[q].i:
=a.data[p].j;
b.data[q].j:
=a.data[p].i;
b.data[q].v:
=a.data[p].v;
q:
=q+1;
]
]
end;
当非零元个数tu和m×
n同数量组，该矩阵不是稀疏矩阵，上面算法对于tu<
<
MU×
NU才有实际意义。
小 结
本章介绍了栈、队列和多维数组三种常见的数据结构。
着重介绍了它们的逻辑结构和存储结构以及基本运算在同存储存构上的实现算法。
栈的逻辑结构同线性表的逻辑结构相同，但具有先进后出的特点，栈可视为一种运算受限的线性表，插入和删除运算只能在表的一端进行，这端称为栈顶。
栈通常有两种存储结构；
顺序栈和链栈，顺序栈受到数组大小的限制，而数组大小只能预先估计，因此，顺序栈容易产生“溢出“。
相反，链栈不存在这种问题。
队列的逻辑结构与线性表逻辑结构相同，因此也可视为一种运算受限的线性表，队列的修改具有先进先出的特点。
队列的两端分别称为队头和队尾，入队列运算只能在队尾进行，出队列运算只能在队头进行。
队列有两种存储结构：
顺序队和链队。
顺序队容易产生“假溢出“（“假队满“）现象，因此往往以循环队作为队列的顺序存储结构。
采用“牺牲“一个存储结点的办法，可以简单地表达循环队的队满、队空条件。
链队由于不存在“假溢出“问题，使用比较方便。
但指针域占用了额外的存储量。
多维数组结构可以看成线性结构的一种推广；
同时，它的运算又可视为线性表的限制。
对矩阵进行压缩存储主要是为了节省存储空间，因此只对那些特殊矩阵才有必要。
压缩存储的关键是要处理好元素在矩阵中的位置与它们的压缩存储结构中的位置之间的关系，以便有关运算的实现。
升级会员 