4-第四章.ppt

1、第4章阵列和字串，阵列可以视为特殊的线性表格。也就是说，定线表格中的资料元素本身也是定线表格4.1阵列的定义和性质定义。阵列特性阵列结构固定数据元素同构阵列操作提供了一组指定的下标。指定相应的数据元素下标集、修改数据元素值、n维数组中包含的数据元素数？4.2数组的顺序存储结构和实现顺序规则是以行顺序为主的顺序，多维一维，4.3矩阵的压缩存储，对称矩阵，三角矩阵，对角矩阵，Loc(aij)=Loc(a11) 2(i-1) (j-1)，M表示(1，2，12)，(1) 4.3矩阵Tripletypedef struct triple data maxsize 1；Int mu、nu、tu；TSMat

2、rixts matrix M；三叉表所需的存储单元数为3(t 1)。其中T为非0牙齿元数，6 7 8，1 2 12，1 3 9，3 1-3 6 14，4 3 24，5 2 18，6 1 15，6 4-7，m。Col=nucol)for(row=1；Row=murow)t colrow=mrow col；T(n)=O(munu)，矩阵，寻找解决方法：矩阵行，只要交换列维数，就徐璐交换每个三元中的I和J，以重新排列三元顺序，T.data中元素t的行(M的列)为主。方法1:按照M的列顺序旋转，要按照T.data的三元顺序在M . M的每一列中查找所有非零牙齿(0)，必须从第一行开始扫描相应的三元表M

3、.data一次。M.data基于m行顺序，因此，T.data中必须存在的顺序就是T. data中的顺序。算法说明：算法分析：T(n)=O(M的列数n 0牙齿以外的元数t) t与Mn相同的数量级状态，则稀疏矩阵树文件为算法，4 6-7，6 3 14，col=1，col=2，状态truscol)for(p=1；P=M.tup)if(m . datap . j=col)t . dataq . I=m . datap . j；t . dataq . j=m . datap . I；t . dataq . e=m . datap . e；q；方法2:稀疏矩阵快速旋转算法思想是以M矩阵的三元组为中心，依次

4、取出M.data的各三元组，交换队伍后直接写入T.data的适当位置。(约翰肯尼迪，美国电视电视剧)，I j e，0 1 2 3 4 5 6 7 8，M.data，I j e，0 1 2 3 4 5 6 7 8，T.data，7 6 8，2 1 12，首先，如果可以获得m每列的第一个0牙齿以外的3元T. data中的位置，则实现：引入两个辅助数组num come3.扫描一次M.data，遇到col列中第一个非零牙齿的三元时，按cpotcol的位置将其放在T.data中。如果再次遇到每列的后续非零牙齿的三元，则只需将它们依次放置在相应列元素之后。、7 6 8、1 3-3、1 6 15、2 1 1

5、2、2 5 18、3 1 9、3 4 24、4 6-7、6 3 14、p)col=m . datap . j；Q=cpotcolt . dataq . I=m . datap . j；t . dataq . j=m . datap . I；t . dataq . e=m . datap . e；Cpotcol，cpot1=1for(col=2；Col=M.nucol)cpot col=cpot col-1 num col-1；if(t . tu)for(col=1；Col=M.nucol)num col=0；for(t=1)；T=M.tut)numm . datat . j；行逻辑链接顺序表有

6、时为了便于特定矩阵运算，将行表添加到行优先级中存储的三元组中，以记录稀疏矩阵中每行的非零牙齿元素三元表的起始位置。通过将行表描述为triple表的新属性，可以获得具有稀疏矩阵另一个顺序存储结构“行链接信息”的triple。类型说明如下：# define maxsize 100 typedef struct triple data maxsize 1；/0非牙齿元组表int rposmaxrc 1；/每行的第一个非零位置表int n，m，t；/矩阵中的行数、列数和非零牙齿元数TSMatrix下面讨论两个稀疏矩阵乘法的例子，很容易看出这种表达的优越性。两个矩阵相乘的经典算法也是众所周知的。如果设置

7、Q=M*N，则M是m1*n1矩阵，N是m2*n2矩阵。一般二维阵列表示时旋转的算法：n1=m2时：for(I=1；I=m1I)for(j=1；J=n2j)qij=0 for(k=1；K=n1k)qij=mik * nkj；牙齿算法复杂性为O(m1*n1*n2)。两个稀疏矩阵相乘，行逻辑链接的顺序表如何从M和N中求Q？1，在乘法矩阵Q中，元素查找矩阵乘法规则已知：Q(i，j)=m (I，1) n (1，j) m (I，2) n (2，j) m (I，2，相乘的基本操作是对于m中的每个元素M.datap，在N中查找满足M.datap.j=N.dataq.i条件的所有元素N.dataq，然后查找M.

8、datap.e和m .即M11等于N乘以行1的非零牙齿元素，M12等于N乘以行2的非零牙齿元素，再乘以同一行0牙齿以外的人民币当然，如果Mik和Nkj(列号等于行号)都不是零牙齿(有三个组)，则只需乘以。N.data中N的第一行row第一个非0牙齿元素，与以前一样，必须同时引入num和rpos向量。Numrow表示矩阵n中row行的非零牙齿元素数。Rposrow表示N.data中行row的第一个非零牙齿的元素位置。因此，牙齿r pos 1=1 RP OSROW=RP OSROW-1 num row-1 2R OWN。例如，矩阵N的NUM和RPOS如下所示：Row 1 2 3 4 numrow

9、1 1 2 0 rposrow 1 2 3 5图5.17矩阵N的num和rpos值，两个稀疏矩阵相乘(Q=M* N)过程可以大致描述如下：q初始化；If (Q是非零牙齿矩阵)/按行的乘积for(arow=1；Arow=M.muArow) /m的每行ctemp=0；/累加器计算Q的arow行积，并将其存储在ctemp中。Ctemp中的非零牙齿元压缩为q . data；中选择所需的构件。/for arow /if，3，根据上述分析，稀疏矩阵乘法的近似步骤是初始化。整理一些单元，准备按行顺序保存产品矩阵。请获取n的num、rpos。创建矩阵乘法。M.data的三元列值乘以非零牙齿元素值(等于N.da

10、ta的三元行值)，元素与下标相同的乘积相加。M和N牙齿稀疏矩阵和元组表存储结构时，假设M和N牙齿分别为：0 0 0 5 0-1 0 2 0，m=，0 2 1 0-2 4 0，n=，Q=M*N， 积累分别是I j e I j e I j e I j e I je 1 3 2 2 2 6 4 5 2 1 1 1-1 2 3 1-2 3 2 3 2 3 2 2 4m . data n . data q . data，Status mults matrix for(ccol=1；Ccol=Q.nuCcol) /压缩在牙齿行中存储0牙齿以外的元if (ctempccol) Q.tu。Q.dataq.tu

11、=(crow，ccol，ctemp ccol)；/if/do while(p=m . tu)；/if return OK；/MultSMatrix乘以算法时间复杂度等于O (mp)。设置每行、列的第一个非零牙齿元节点定义，以及指向typedef struct node int row、col、val的行和列指针数组。Struct node *down，* rightJD；，Else /在行表格中查找插入位置for(q=m . rheadi；(q-right) /CreateSMatrix_OL，算法创意：not null假设指针pa和Pb分别指向矩阵a和b的行值相同的两个节点，主要处理过程为1

12、，pa=NULL或pa-(这是同一行中前一个节点的rii)2，对于pa-jj，只需将pa指针向右推一步。3，如果pa-j=pb-j和pa-e pb-e！=0时，所有其他域的值保持不变，只要AIJ bij值传递到pa指向的节点的E域即可。4，pa-j=pb-j和pa-e pb-e=0时，必须从a矩阵的链表中删除pa指向的节点。此时，必须更改同一行中前一节点的right域值所在列中前一节点的down域值。=，添加两个稀疏矩阵，4.4光义表的概念1光义表光义表()也称为列表，是线性表的扩展，也是数据元素有限序列。记录：LS=(d0，d1，d2，.dn-1)。其中di可以是单个元素或广义表。说明1)广义表的定义是递归定义。因为在描述广义表时又使用了广义表。2)在线性表中，数据元素是单个元素，在广义表中，元素可以是单个元素，单个元素(原子)或广义表，简称广义表。3)n是光义表的长度。4)以下是范围广泛的表的一些茄子示例：A=()零长度