数据结构数组广义表.pptx

会计学第5章数组和广义表
5.1.1数组的定义Page55.1.1数组的定义数组顺序存储的特点：
数组中的数据元素数目固定，一旦定义，其数据元素的数目不再有增减变化；
数组中的数据元素具有相同的数据类型。
数组中的每个数据元素都和一组唯一的下标值对应；以行序为主序5.1.2数组的顺序表示与实现二维数组——以列序为主序存储三维数组n维数组课前任务检查Page171.什么是压缩存储？
若多个数据元素的值都相同，则只分配一个元素值的存储空间，且零元素不占存储空间。
2.什么样的矩阵能够压缩？
一些特殊矩阵，如：对称矩阵，对角矩阵，三角矩阵，稀疏矩阵等。
3.什么叫稀疏矩阵？
矩阵中非零元素的个数较少（一般小于5%）5.1.3矩阵的压缩存储5.1.3矩阵的压缩存储Page21Page22Page23Page243、对角矩阵3、对角矩阵3、对角矩阵3、对角矩阵课堂练习
特点：1.存在大量的零元素
2.零元素出现无规律1.稀疏矩阵定义：非零元较零元少，且分布没有一定规律的矩阵。A=5.1.4稀疏矩阵5.1.4稀疏矩阵稀疏矩阵Page38Page39Page40Page41求转置矩阵
对于一个m×n的矩阵M,它的转置矩阵T应该是n×m
的矩阵,同时满足T[i,j]=M[j,i],并且1<=i<=n,1<=j<=m求转置矩阵
分析：
⑴将矩阵的行列值相互交换
⑵将每个三元组中的i和j相互调换
⑶重排三元组之间的次序（将T.data按行序排序法）3）稀疏矩阵的基本操作Page46转置运算算法二：
按照M.data中三元组的次序进行转置，将转置后三元组放到T.data中恰当位置。
若能预先确定矩阵M中每一列第一个非0元素在T.data中位置，那么在对M.data中的依次转置时,便可直接放到T.data的恰当位置
算法二思想：
实现：设两个辅助数组num[col]、cpot[col]
数组num[col]：表示矩阵M中第col列中非零元个数；
cpot[col]：指示M中第col列第一个非零元在转置矩阵中的位置，显然有：
cpot[0]=0;
cpot[col]=cpot[col-1]+num[col-1];
cpot[0]=0;
cpot[col]=cpot[col-1]+num[col-1];(1colma[0].j)Page53数据元素结点定义：补充：十字链表具体实现第5章数组和广义表
Page57广义表的示例（2）广义表的深度（3）广义表的表头、表尾设HAED[p]为求广义表p的表头函数，TAIL[p]为求广义表p的表尾函数，其中[]是函数的符号，给出下列广义表的运算结果：
HEAD[（a，b，c）]的结果是___。
TAIL[（a,b,c）]的结果是__。
HEAD[((a),(b))]的结果是___。
TAIL[((a),(b))]的结果是___。
HEAD[TAIL[(a,b,c)]的结果是___
TAIL[HEAD((a,b),(c,d)]的结果是___。
HEAD[HEAD[(a,b),(c,d)]]的结果是___。
TAIL[TAIL[(a,(c,d))]]的结果是___。由于广义表(a1,a2,a3,…an)中的数据元素可以具有不同的结构，（或是原子，或是广义表），因此，难以用顺序存储结构表示，通常采用链式存储结构，每个数据元素可用一个结点表示。
由于广义表中有两种数据元素，原子或广义表，因此，需要两种结构的结点：
一种是表结点
一种是原子结点存储结构1：
表结点由三个域组成：标志域、指示表头的指针域和指示表尾的指针域；
原子结点只需两个域：标志域和值域。
表结点原子结点存储结构1的结点类型定义如下：
#defineatomtypeint
typedefenum{ATOM,LIST}elemtag;
typedegstructglnode{
elemtagtag;
union{
atomtypeatom;
struct{structglnode*hp,*tp;}ptr;
};
}*glist;1存储结构2：表结点由三个域组成：标志域、指示表头的指针域和指示表尾的指针域；原子结点的三个域为：标志域、值域和指示表尾的指针域。
存储结构2的结点类型定义如下：
typedefintatomtype;
typedefenum{atom,list}elemtag;
typedefstructglnode{
elemtagtag;
union{//联合体，成员共享内存
atomtypeatom;//原子数据
structglnode*hp;
};
structglnode*tp;//指向同一层的下一个节点
}GLNode;1