第三章 数组和字符串(数据结构word版课件).doc
《第三章 数组和字符串(数据结构word版课件).doc》由会员分享,可在线阅读,更多相关《第三章 数组和字符串(数据结构word版课件).doc(21页珍藏版)》请在三一文库上搜索。
1、第三章 数组和字符串3.1 数 组3.1.1 数组的存储和寻址 一个一维数组就是若干元素的一个有限序列,而其每个元素都通过一个下标来指定,且元素本身就是一个数据结构(或是整型、逻辑型、字符型等简单数据类型,或是数组、记录等复杂数据类型)。对一维数组唯一的限制是所有的元素都具有相同的类型,并占据相同大小的存储空间。因数组元素要通过数组名及紧跟其后的方括号中的下标来确定,故一个一维数组就对应一个下标函数。下面我们讨论数组在计算机存储器中的存储方式。因为通常不进行数组的插入或者删除操作,所以在内存储器中我们选择顺序存储方式实现数组的存储。在内存中以“线性式”的方式组织数组很方便。设一维数组An存放在
2、n个连续的存储单元中,每个数组元素占一个存储单元(不妨设为C个连续字节)。如果数组元素A0的首地址是L,则A1的首地址是L+C,A2的首地址是L+2C, ,依次类推,对于有:Loc (Ai)=Loc (A0)+iC对于高维数组(多维的数据结构)之存储,可将其转化为一维来实现。因此必须对高维数组元素的存放次序进行约定。高维数组通常有两种存放次序约定按行优先顺序和按列优先顺序.首先介绍按行优先顺序。所谓按行优先顺序,就是将高维数组元素按行向量的顺序存储,第个行向量存储在第个行向量之后。换句话说,就是用一维数组的存储结构来解决高维数组的存储问题。设A为n维数组,其每个元素占C个字节,且第一个元素的地
3、址为,若要算出该数组的任一个元素的地址,可将n维数组可考虑为如下一维数组( , )设该数组的每个元素占C1个字节。显然,包含的数组元素实际与一个n-1维数组(包含个的数组元素)相同,于是我们有: .又可将()看作如下一维数组(, , ,)设它的每个元素占C2个字节,显然C2 = m3m4 mnC ;如此类推,设一维数组(, )设它的每个元素占个字节,则Cn-1=mn C . 故的存储地址为: 所谓按列优先顺序,就是将数组元素按列向量的顺序存储,第i+1个列向量存储在第i个列向量之后。换句话说,就是将数组转化为一维数组来考虑。请读者计算以按列优先顺序存储的多维数组中任一个元素的存储地址。3.2
4、矩 阵3.2.1 矩阵类矩阵的乘法运算略为复杂,对于矩阵Amp和Bpn的乘积Cmn ,其第i行第j列元素cij的计算公式为,显然乘法运算的算法可描述如下:算法Multi-1(A, B, C, m, p, n) / 求矩阵与的乘积FOR i=1 TO m DO FOR j=1 TO n DO ( . FOR k=1 TO p DO . ) 前面提到过,可直接以按行优先次序用一维数组存放矩阵元素,下面给出的算法Multi-2是对用一维数组所存放矩阵的乘法运算实现。该算法中用一维数组s存放Amp,用一维数组t存放Bpn,求存放A与B的乘积Cmn 的一维数组w.由矩阵乘法公式知,其中aik是矩阵A中第
5、i行第k列的元素,bkj是矩阵B中第k行第j列的元素,因为矩阵A和B分别按行优先存放在一维数组s和t中,所以ai(k+1)在s中的下标比aik在s中的下标多1,b(k+1)j在t中的下标比bkj在t中的下标多n .这说明,随着一个矩阵元素行号或列号的变换,其在对应的一维数组的下标要进行相应变换。算法Multi-2(s, t, w, m, p, n)/ Amp用一维数组s存放,Bpn用一维数组t存放,求A与B的乘积Cmn并用一维数组w存放M1. 初始化cw0 . / 初始时cw是c11在一维数组w中的下标M2. 循环FOR i=1 TO m DO / 第一层循环cs(i-1)p. / 令cs为a
6、i1在一维数组s中的下标ct0. / 令ct为b11在一维数组t中的下标FOR j=1 TO n DO / 第二层循环( ctj-1. / 令ct为b1j在t中的下标 wcw0 . FOR k=1 TO p DO / 第三层循环,叠加aikbkj 并存于wcw中 ( wcwwcw+scstct. cscs+1. / cs为A中本行下一列元素在s中的下标 ctct+n. ) / ct为B中本列下一行元素在t中的下标 cwcw+1. ) ) 3.2.2 特殊矩阵前一小节所介绍的矩阵类,是以按行优先次序将所有矩阵元素存放在一个一维数组中。但是对于特殊矩阵,如对称矩阵、三角矩阵、对角矩阵和稀疏矩阵等,
7、 如果用矩阵类Matrix来实现,那么大量的存储空间中存放的是重复信息或者是零元素,这样造成很大的空间浪费。为节约存储空间和算法(程序)运行时间,通常会采用压缩存储的方法。对角矩阵的压缩存储nn维方阵M是对角矩阵,则对 i j (1 i , j n),都有M(i, j)=0,即非对角线上的元素均为0 . 对于一个nn维对角矩阵,至多只有n个非零元素,因此只需存储其n个对角元素的信息。很容易想到,采用一维数组dn来压缩存储对角矩阵,其中di存储Mi,i的值。三角矩阵的压缩存储三角矩阵分为上三角矩阵和下三角矩阵。方阵M是上三角矩阵,当且仅当i j时有M(i, j)=0 . 方阵M是下三角矩阵,当且
8、仅当i 0 THEN ( FOR k=0 TO n-1 DO FOR i=0 TO count-1 DO IF (col( ai )=k THEN ( row( bj )k. col( bj )row( ai ). value( bj )value( ai ). jj+1. ) / 考察三元组表b中的下一个结点 对于用三元组表存储的稀疏矩阵,若矩阵非零元素个数为t,求其转置矩阵的时间复杂性是多少?观察Transpose算法不难发现,函数中包含两重循环,第一重循环是对转置矩阵按行优先依次确认非零元素,故循环次数为A的行数n;第二重循环是扫描原矩阵的三元组表,执行次数是矩阵A的非零元素个数t,显然
9、,求转置矩阵的时间复杂性为O(nt) .用三元组表存储稀疏矩阵,无论是添加或删除矩阵非零元素,还是对矩阵实施某些操作(例如AA+B),都可能引起矩阵中非零元素的个数和位置的变化,这些变化将引起与矩阵对应的三元组表中大量结点的移动,效率较低。用链接存储方式实现稀疏矩阵则会避免这些问题。下面介绍稀疏矩阵的一种链接存储方式十字链表。3.2.4 十字链表在稀疏矩阵的十字链表中,矩阵的每一行都设置为由一个表头结点引导的循环链表(简称为行链表),矩阵的每一列也都设置为由一个表头结点引导的循环链表(简称为列链表)。矩阵的元素结构如下:LEFTUPROWCOLVAL其中LEFT和UP是指针变量,分别存放该元素
10、的左邻非零元素和上邻非零元素的地址信息,ROW和COL存放该元素在矩阵中的行号和列号,VAL存放元素值。下图给出一个稀疏矩阵和它的十字链表: (3-3)图 3.2 十字链表-1-1-1-1-1-1-1136214448-1329347这里,每一行和每一列都有一个表头结点:BASEROWi,i=1,2,m(m行)BASECOLj, j=1,2,n(n列)且-1 = COL(Loc(BASEROWi) 0-1 = ROW(Loc(BASECOLj) 0因为行或列都是一个循环链表,所以行表头BASEROWi中的LEFT指针循环地链接到该行最右边的非零元素,列表头BASECOLj中的UP指针循环地链接
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第三章 数组和字符串数据结构word版课件 第三 数组 字符串 数据结构 word 课件
链接地址:https://www.31doc.com/p-4660937.html