数据结构与【C语言】--串 .ppt

数组的定义和运算 数组i是一个具有固定格式和数量的数据集合，在数组上一般不能做插入和删除元素的操作。因此除了初始化和销毁操作之外，数组通常只有两种操作： 1、存取（读）：给定一组下标，读取相应的数组元素 2、修改（写）：给定一组下标，存储或修改相应的数组元素 它们本质上只对应一种操作——寻址，即根据一组下标定位相应的元素。 行优先存储 列优先存储 5.3、矩阵的压缩存储 矩阵中非零元素呈某种规律分布或者矩阵中出现大量的零元素的情况下，为了节省存储空间，我们可以对这类矩阵进行压缩存储，即： 为多个相同的非零元素只分配一个存储空间； 对零元素不分配空间。 5.3.1 特殊矩阵的压缩存储 对称矩阵的压缩存储 对称矩阵的压缩存储 n阶对称矩阵中，显然只需存储对称矩阵的上（或下）三角元素。这样，n阶对称矩阵的n2个元素就压缩到n(n+1)/2个存储单元中。 设用一维数组S[n(n+1)/2 ]存储n阶对称对称矩阵A的下三角（包括主对角线元素）的元素。不失一般性，我们以行序为主序方式存储对称矩阵下三角元素。 三角矩阵的压缩存储 三角矩阵的压缩存储 三角矩阵的压缩存储 三对角矩阵的压缩存储 在三对角矩阵里除满足条件i=0，j=0、1，或i=n-1j=n-2、n-1或1in-1,j=i-1、i、i+1的元素aij外，其余元素都是零。 对这种矩阵，我们也可按行优序为主序来存储。除第0行和第n-1行是2个元素外，每行的非零元素都要是3个，因此，需存储的元素个数为3n-2。 数组sa中的元素sa[k]与三对角带状矩阵中的元素aij存在一一对应关系，在aij之前有i行,共有3*i-1个非零元素，在第i行，有j-i+1个非零元素，这样，非零元素aij的地址为： LOC(i,j)=LOC(0,0)+[3*i-1+(j-i+1)]*d =LOC(0,0)+(2i+j)*d 上例中，a34对应着sa[10]。 k=2*i+j=2*3+4=10 a21对应着sa[5] k=2*2+1=5 由此，我们称sa[0..3*n-3]是阶三对角带状矩阵A的压缩存储表示。 5.3.1 特殊矩阵的压缩存储 随机稀疏矩阵的压缩存储 随机稀疏矩阵的压缩存储 三元组顺序表上的转置 三元组顺序表上的转置 时间复杂度分析 算法的基本操作为将M.data中的三元组赋值到T.data，是在两个循环中完成的，故算法的时间复杂度为 O(nu?tu) 当非零元的个数tu和矩阵元素个数mu?nu 同数量级时，转置运算算法5.1的时间复杂度为 O（ mu?nu ? nu）。 由此可见：在这种情况下，用三元组顺序表存储矩阵，虽然可能节省了存储空间，但时间复杂度提高了，因此算法仅适于tu mu?nu的情况。 该算法效率不高的原因是：对为实现M到T的转置，该算法对M.data进行了多次扫描。能否在对M.data一次扫描的过程中，完成M到T 的转置？ 十字链表：三元组的双链表，结点不但包含三元组，而且还包含两个指针，一个称为行链指针，指向下一个同行的非零元素；另一个称为列链指针，指向下一个同列的非零元素。同一个结点，同时链到行链和列链上。 十字链表的数据类型定义： 作业 转置 i j v 1 2 12 1 3 9 3 1 -3 3 6 14 4 3 24 5 2 18 6 1 15 6 4 -7 2 3 4 5 6 7 8 1 i j v 2 3 4 5 6 7 8 1 cpot 1 3 5 7 8 8 9 1 2 3 4 5 6 7 2 1 12 3 转置 i j v 1 2 12 1 3 9 3 1 -3 3 6 14 4 3 24 5 2 18 6 1 15 6 4 -7 2 3 4 5 6 7 8 1 i j v 2 3 4 5 6 7 8 1 cpot 1 4 5 7 8 8 9 1 2 3 4 5 6 7 2 1 12 转置 i j v 1 2 12 1 3 9 3 1 -3 3 6 14 4 3 24 5 2 18 6 1 15 6 4 -7 2 3 4 5 6 7 8 1 i j v 2 3 4 5 6 7 8 1 cpot