数组和广义表.pptVIP

由于广义表的元素类型不同，难以用顺序结构表示，常用链接存储方法存储广义表，并称之为广义链表。 * 数组的处理比其它复杂的结构要简单： ①数组中各元素具有统一的类型； ②数组元素的下标一般具有固定的上界和下界，即数组一旦被定义，它的维数和维界就不再改变。 ③数组的基本操作比较简单，除了结构的初始化和销毁之外，只有存取元素和修改元素值的操作。P90页，基本操作只有4种 * 一维数组可以看成是一个线性表或一个向量 * * 一个m×n的二维数组可以看成是m行的一维数组，或者n列的一维数组。 二维数组，又称矩阵(matrix)。二维数组中的每一个元素又是一个定长的线性表（一维数组），都要受到两个关系即行关系和列关系的约束，也就是每个元素都同属于两个线性表。 (1) 数组中的数据元素数目固定。一旦定义了一个数组，其数据元素数目不再有增减变化。它属于静态分配存储空间的数据结构。 (2) 数组中的数据元素必须具有相同的数据类型。 (3) 数组中的每个数据元素都有一组唯一的下标值。 (4) 数组是一种随机存储结构。可随机存取数组中的任意数据元素。 * 数组一般不做插入或者删除操作，一旦建立数组，结构中的数据元素个数和元素之间的关系就不再发生变动。因此采用顺序存储结构。 * 数组由行向量组成 N为列数 * 数组由列向量组成 m为行数 * 在一个n阶方阵A中，若元素满足下述性质：aij=aji 0≤i,j≤n-1.则称A为对称矩阵。 对称矩阵中的元素关于主对角线对称，故只要存储矩阵中上三角或下三角中的元素，让每两个对称的元素共享一个存储空间，这样，能节约近一半的存储空间。不失一般性，我们按“行优先顺序”存储主对角线（包括对角线）以下的元素 则ai j在下三角形中。 ai j之前的i行（从第0行到第i-1行）一共有 1+2+…+i=i(i+1)/2 个元素， 对于任意给定一组下标(i，j)，均可在sa[k]中找到矩阵元素aij，反之，对所有的k=0,1,2,…，n(n-1)/2-1，都能确定sa[k]中的元素在矩阵中的位置(i,j)。 问：a23和a32存储在哪个位置？ K=3(3-1)/2+2-1=4 * * 其中，s[n(n+1)/2]中存放常数c或0。 * 对角矩阵中，所有的非零元素集中在以主对角线为了中心的带状区域中，即除了主对角线和主对角线相邻两侧的若干条对角线上的元素之外，其余元素皆为零。 结论：对特殊矩阵的压缩存储实质上就是将二维矩阵中的部分元素按照某种方案排列到一维数组中，不同的排列方案也就对应不同的存储方案。 0相加，0相乘，0相除的运算会很麻烦 * 1.既然0值浪费空间，那么就少存或不存0元 2.尽量减少和0相加，和0相乘的运算 3.在减少了很多元素（0元）的情况下还要运算方便 * * 三元组表示法如何表示？ * * 对比稀疏多项式：只存储系数不为0的项。如2+〖3??〗^354?〖5??〗^567，表示方法（（2,0）,(3,354),(-5,567)） 用一个数组来存储所有的非零元 用三元组存储法避免了零元的存储，但是否能满足我们解决问题的第二第三个原则呢：2. 尽量减少没有意义的运算；3. 运算要方便。 原来的矩阵为M，转置矩阵为T 即A的行是B的列，A的列是B的行。 矩阵个数不变，元素值不变，位置发生了变化 原来某一行的元素变成了新矩阵某一列的元素 时间复杂度为：O(muXnu) 时间浪费在0元素的转置上（列序转换法） * 第一步:将矩阵行、列维数互换：4行5列变成5行4列，非零元个数仍为7 第二步：将每个三元组中的i和j相互调换 问：若采用三元组压缩技术存储稀疏矩阵，只要把每个元素的行下标和列下标互换，就完成了对该矩阵的转置运算，这种说法正确吗？ （传统转置法） 第三步：按行排序：关键问题在于如何把三元组的顺序表得到对应的三元组顺序表 原矩阵非零元的排序是以行序为主序，每一行以列排序（1,2）（1,5），因此得到的转置矩阵也应为行序为主序排列。 传统方法：从头到尾依次处理 先处理第一个元素，第二个元素与第一个比较，行数比第一个大，因此排在下面 第三个元素就麻烦了，它的行值比第二个小，和第一个一样，因此第二个元素下移，然后插入第三个元素 同理 原来矩阵是个线性结构（线性表），转置操作也是线性，但因为要移动元素，时间复杂度变为非零元个数的平方（n*(n+1)/2），显然是不能令人满意 问：有没有一种可能性在线性的复杂度完成操作？ 转置后一次到位不用移动 * （快速转置法） 假如每个元素转置后一次到位不用移动，那么转置操作是在线性的数量级上完成的 关键是要找到每个元素对应的存储位置，我们能否事先估计出来呢？ (1,2,3)变成（2,1,3）即第二行第一个非零元，它出现的位置取决于它前面第一行有几个非