第5章 数组和广义表.ppt

********累加器的时间复杂度为O(M.mu*N.nu),求Q所有非零元的时间复杂度为O(M.tu*N.tu/N.mu),进行压缩存储的时间复杂度为O(M.mu*N.nu),******对于m行、n列有t个非零元的稀疏矩阵，算法的执行时间为O(t*s)，s=max(m.n)，因为每建立一个非零元的结点时都要寻查它在行表和列表中的插入位置。**由于广义表本属线性类型的数据结构，它和数组类似，每个数据元素本身又可以是一个数据结构，因此在教材中和“数组”合为一章。但由于广义表比数组更为复杂，它兼有“多层次”的特点，特别是它的存储表示和操作的实现和树的操作极为类似。因此在本章的学习中应善于和第六章的内容相对照，反之通过本章的学习恰好是对实现树操作的递归算法的复习和巩固。希望你通过本章的学习能自己总结出如何利用“分治法”的算法思想设计递归定义的结构的递归算法的规律来广义表是递归的概念，描述广义表时又用到了广义表的概念。和数组不同，二维数组中的每个数据元素是结构相同的一维数组，而广义表中的每个数据元素，其结构不一定相同。****（）和（（））是不同的，前者长度为0，后者长度为1**（）和（（））是不同的，前者长度为0，后者长度为1**因为，广义表的数据元素可以具有不同的结构，采用顺序存储结构表示将非常困难，通常采用链式结构。**结构复杂********二维数组中共有m?n个元素，每个元素同时处于行和列的两个关系中，它既在行关系ROW中是(i0)的后继，又在列关系COL中是(j0)的后继。**数组一旦被定义，其维数(N)和每一维的上、下界均不能再变，数组中元素之间的关系也不再改变。因此数组的基本操作除初始化和结构销毁之外，只有通过给定的一组下标索引取得元素或修改元素的值。**由于数组不作插入和删除的操作，因此,采用顺序存储结构表示数组是自然的事。这是我们只介绍数组的顺序存储表示的原因。由于数组中的数据元素之间是一个多维的关系，而存储地址是一维的，因此数组的顺序存储表示要解决的是一个如何用一维的存储地址来表示多维的关系的问题。

现有的高级语言中的大多数都是按以行为主实现数组类型的。**这个公式可以推广到n维数组**这个公式可以推广到n维数组**例如，我们处理PPT这帧图像？色彩比较单一，一个点（色彩，灰度等）一个点存储是否好？矩阵是很多科学与工程计算问题中研究的对象，在数值分析中，经常出现一些阶数很高的矩阵，同时在矩阵中有许多值相同的元素或者零元素。为了节省存储空间，可以对这类矩阵进行压缩存储********虽然可以压缩存储，但是不能改变随机存储的性质，即任意给定i,,j，应能立即找到其值。****虽然可以压缩存储，但是不能改变随机存储的性质，即任意给定I,j，应能立即找到其值。****公式：请同学们自己写出来，可以到图书馆查找结果****共有三种压缩存储的方法，本节介绍的是顺序存储**共有三种压缩存储的方法，本节介绍的是顺序存储**共有三种压缩存储的方法，本节介绍的是顺序存储**三元组表所需存储单元个数为3(tu+1),其中tu为非零元个数****两种转换方法：一、按data2中的顺序，在data1中找到合适的值进行转置；二、按data1的顺序，在data2中找到合适的位置进行转置。**为找到转置矩阵中每一列所有非零元素，需对其三元组表a.data从第一行起扫描一遍。由于a.data中以矩阵行序为主序,所以由此得到的恰是b.data中应有的顺序**当tu和mu*nu同数量级时，算法的时间复杂度为O(mu*nu2)，例如在100*500的矩阵中有tu=10000个非零元素虽然空间节省了，但时间复杂度提高了。因为不经压缩的矩阵在求转置矩阵的时间复杂度为O(mu*nu)，**求表长、插入、取元素时间复杂度：O(1)For循环次数LB_len，LocateElem(La,e,equal)是O(ListLenth(LA))****num[col]：表示矩阵M中第col列中非零元个数cpot[col]：指示M中第col列第一个非零元在T中row位置cpot[1]=1;cpot[col]=cpot[col-1]+num[col-1];(2?col?ma[0].j)**关于++num[M.data[t].j]，举例人口各年龄段统计，++年龄段[int(年龄/10)]这个算法比前一个算法多用了两个辅助空间。从时间上看，算法中有4个并列的单循环，循环次数分别为nu和tu。比上一个