第四章 数组、串与广义表

  • 数组部分

主要讲了普通数组的存储和特殊矩阵的压缩存储。

多维数组:二维数组可以用以一维数组为元素的一维数组表示,三维数组可以用二维数组和一维数组表示(一般是以行优先表示的)。 对称矩阵:a(i,j)等于a(j,i),所以只需要存储大约一半的数据。 稀疏矩阵:因为矩阵内部大部分元素为0,所以只需要存储非零项就OK了,这样可以节省大量的空间,使用一个三元组结构体的数组存放非0项。

template <class T>
struct Trituple{
    int row, col;   //存放元素在矩阵中的位置
    T value;
}

关于稀疏矩阵的转置,也有很巧妙的解决办法。转置操作需要对元素进行重新排列:使用普通的循环即可完成排序工作, 【一种优化方法:扫描所有的元素,使用两个辅助数组记录每行的元素数目和起始元素的列号。然后按照转置的定义重新排列元素】

  • 串部分 主要是字符串

  • 广义表 广义表简称表,是线性表的推广,广义表中的元素可以是数据元素(原子)和子表。 广义表的定义是递归的,因为在表的描述中又用到了表,允许表中有表。 LS=(a0, a1, a2, ... ) 表的表示方法,依然用到了结点的概念。用结点表示一个元素,这个结点分为3个部分:

标志域utype 信息域info 尾指针域tlink
0 引用数ref 指向同层下一个结点
1 元素值value
2 子表的链接

utype=0时,该结点是附加头结点,ref记录了本表被引用——作为表元素的次数。 每一个子表都有一个附加头,这样做在删除一个表的第一个结点的时候会很方便。因为不用修改指向该表的指针,此时该表的地址用附加头的地址表示,删除任何一个结点都不会改变该表的地址。

最后更新: 4/30/2019, 12:18:56 AM