第四章 数组、串与广义表

数组部分

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

• 多维数组：二维数组可以用以一维数组为元素的一维数组表示，三维数组可以用二维数组和一维数组表示（一般是以行优先表示的）。
• 对称矩阵：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记录了本表被引用——作为表元素的次数。 每一个子表都有一个附加头，这样做在删除一个表的第一个结点的时候会很方便。因为不用修改指向该表的指针，此时该表的地址用附加头的地址表示，删除任何一个结点都不会改变该表的地址。