第10讲 数组和矩阵.ppt

Chapter5数组和广义表§5.1数组的ADT定义当n＝1时，n维数组就退化为定长的线性表

反之，n维数组可以看作线性表的推广
例如，二维数组可以看作元素是线性表的线性表

§5.2数组的顺序表示和实现例子：§5.3矩阵的压缩存储5.3.1特殊矩阵的压缩存储对称矩阵的压缩存储
为每一对对称元素分配一个存储空间。ADTSparseMatrix{
数据对象：D={aij|i=1,..,m,j=1,…,n;aij∈ElemSet}
数据关系：R={Row,Col}

基本操作：

}ADTSparseMatrix如何实现稀疏矩阵的压缩存储？1）三元组顺序表（顺序存储结构）转置运算

三元组顺序表求转置
StatusTransposeSMatrix(TSMatrixM,TSMatrix&T){
T.mu=M.nu;T.nu=M.mu;T.tu=M.tu;
if(T.tu){
q=1;
for(row=1;row<=T.mu;row++)
for(p=1;p<=M.tu;p++)
if(M.data[p].j==row){
T.data[q].i=M.data[p].j;
T.data[q].j=M.data[p].i;
T.data[q].e=M.data[p].e;
q++;}
}retrurnOK;
}作业1作业2（上机检验）2）十字链表（三元组表的链式结构）作业3：§5.4广义表的定义抽象数据类型广义表的定义如下：广义表的例子:分析表长，表头，表尾练习：§5.5广义表的存储结构广义表的头尾链表存储表示：
typedefenum{ATOM,LIST}ElemTag;
typedefstructGLNode{
ElemTagtag;
union{
AtomTypeatom;//atom是原子结点的值域
struct{
structGLNode*hp;
structGLNode*tp;}ptr;//ptr是表结点的指针域，
//ptr.hp和ptr.tp分别指向表头和表尾
};
}*GList;作业4：Chapter5小结十字链表的创建