数据结构数组和广义表学习教案.pptx

会计学上面二维数组的例子，介绍(jièshào)了数组的结构特性，实际上数组是一组有固定个数的元素的集合。由于这个性质，使得对数组的操作不象对线性表的操作那样，可以在表中任意一个合法的位置插入或删除一个元素。数组的抽象数据类型定义(dìngyì)（ADTArray）基本操作：5.2数组的顺序存储和实现(shíxiàn)对于二维数组Amxn
以行为主的存储(cúnchǔ)序列为：a11,a12,…a1n,a21,a22,…,a2n,……,am1,am2,…,amn
以列为主存储(cúnchǔ)序列为：a11,a21,…am1,a12,a22,…,am2,……,a1n,a2n,…,amn以二维数组Amn为例，假设每个元素只占一个存储单元，“以行为主”存放数组，下标从1开始(kāishǐ)，首元素a11的地址为Loc[1,1]求任意元素aij的地址，可由如下计算公式得到：
Loc[i,j]=Loc[1,1]+n×(i-1)+(j-1)三维数组A（1..r,1..m,1..n）可以看成(kànchénɡ)是r个m×n的二维数组，如下图所示：假定每个元素占一个存储单元(cúnchǔdānyuán)，采用以行为主序的方法存放，首元素a111的地址为Loc[1,1,1]，ai11的地址为Loc[i,1,1]=Loc[1,1,1]+(i-1)*m*n，那么求任意元素aijk的地址计算公式为：如果将三维数组推广到一般情况，即：用j1，j2，j3代替数组下标i，j，k；并且j1，j2，j3的下限为c1，c2，c3，上限分别为d1，d2，d3，每个元素占一个存储单元(cúnchǔdānyuán)。则三维数组中任意元素a(j1，j2，j3)的地址为：
Loc[j1，j2，j3]=Loc[c1,c2,c3]+1*(d2-c2+1)*(d3-c3+1)*(j1-c1)
+1*(d3-c3+1)*(j2-c2)+1*(j3-c3)
其中l为每个元素所占存储单元(cúnchǔdānyuán)数。令α1=1*(d2-c2+1)*(d3-c3+1),α2=1*(d3-c3+1),α3=1，则：5.3特殊矩阵(jǔzhèn)的压缩存储对于下三角矩阵，按“行序为主序”进行存储，得到的序列为：a11,a21,a22,a31,a32,a33…an1,an2…ann。由于下三角矩阵的元素(yuánsù)个数为n(n+1)/2，所以可压缩存储到一个大小为n(n+1)/2的一维数组中。下三角矩阵中元素(yuánsù)aij(i>j)，在一维数组A中的位置为：
LOC[i,j]=LOC[1,1]+i(i-1)/2+j-1同样，对于上三角矩阵，也可以将其压缩存储到一个大小为n(n+1)/2的一维数组C中。其中(qízhōng)元素aij(i<j)在数组C中的存储位置为：
Loc[i,j]=Loc[1,1]+j(j-1)/2+i-15.3.2带状矩阵(jǔzhèn)三对角带状矩阵的压缩存储(cúnchǔ)，以行序为主序进行存储(cúnchǔ)，并且只存储(cúnchǔ)非零元素。其方法为：5.3.3稀疏(xīshū)矩阵1.稀疏(xīshū)矩阵的三元组表表示法三元组表的类型(lèixíng)说明：1）用三元组表实现(shíxiàn)稀疏矩阵的转置运算实现(shíxiàn)转置的简单方法：算法(suànfǎ)一、算法(suànfǎ)二、用三元组表实现稀疏(xīshū)矩阵的乘法运算根据数学上矩阵相乘的原理，我们(wǒmen)可以得到矩阵相乘的经典算法：经典算法中，不论M[i][k]，N[k][j]是否为零，都要进行一次乘法运算，而实际上，这是没有不必要的。采用三元组表的方法来实现时，因为三元组只对矩阵的非零元素(yuánsù)做存储，所以可以采用固定三元组a中元素(yuánsù)（i，k，Mik）（1≤i≤m1，1≤k≤n1），在三元组b中找所有行号为k的的对应元素(yuánsù)（k，j，Nkj）（1≤k≤m2，1≤j≤n2）进行相乘、累加从而得到Q[i][j]。即：以三元组a中的元素(yuánsù)为基准，依次求出其与三元组b的有效乘积。注意：两个稀疏矩阵相乘的结果不一定(yīdìng)是稀疏矩阵。反之，相乘的每个分量M[i，k]×N[k，j]不为零，但累加的结果Q[i，j]可能是零。例如：#defineMAXSIZE1000/*非零元素的个数最多为1000*/
#defineMAXROW1000/*矩阵(jǔzhèn)最大行数为1000*/
typedefstruct
{introw,col;/*该非零元素的行下标和列下标*/
ElementTypee；/*该非零元素的值*/
}Triple;
typedefstruct
{Tripledata[MAXSIZE+1];