多维数组和广义表.ppt

?3. 广义表取尾算法 若广义表GL=（a1,a2,……,an）,则tail（GL）=（a2,……,an） 。取表尾运算的结果是取出除表头以外的所有元素。 例如,tail（（a1,a2）,（a3,a4,a5）,a6）=（（a3,a4,a5）,a6）。 Tail(linknode *GL) { if GL-tag==1 p=GL-tp; return p; } * 2021/9/12 4. 求广义表深度算法 int Depth(linknode *GL) { int max=0; while (GL!=NULL) { if (GL-tag==0) // 有子表 { int dep=Depth(GL-sublit) if (depmax) max=dep; } GL=GL-link; } return max+1; // 非空表的深度是各元素的深度的最大值加1 } 求广义表深度算法的时间复杂度为O(n)。 * 2021/9/12 （1） 数组是一个具有固定格式和数量的数据有序集,每一个数据元素有唯一的一组下标来标识,在数组上不太适宜做插入、删除数据元素的操作。 （2）二维数组中aij的地址为: LOC(aij) = LOC(a00) + ( i×n + j ) × d （0下标起始的语言） （3）三维数组中aijk的地址为: LOC(aijk)=LOC(a000)+( (i×n×p+ j×p +k) ×d （0下标起始的语言） （4）对称矩阵是一种特殊矩阵,n阶方阵的元素满足性质: aij=aji （0≤i , j≤n-1）。对称矩阵是关于主对角线的对称,因此只需存储上三角或下三角部分的数据即可。 小 结 * 2021/9/12 （5）三角矩阵的特殊性是以主对角线划分矩阵。主对角线任意一侧（不包括主对角线中）的元素均为常数（C）。下三角矩阵,主对角线以上均为同一个常数;上三角矩阵,主对角线以下均为同一个常数,均可以采用压缩存储。 （6）在m*n的矩阵中有t个非零元素,且t远小于m*n,这样的矩阵称稀疏矩阵。稀疏矩阵常用的有:三元组表存储、带行指针的链表存储、十字链表存储等存储方法。 （7） 广义表是n（n≥0）个数据元素的有序序列,广义表的元素可以是单元素,也可以是一个广义表。 （8） 由于广义表的元素有两种形式,所以其结点的存储形式也有两种:表结点由标志域、表头指针域、表尾指针域组成;而原子结点由标志域和值域组成。 * 2021/9/12 1．实验目的 （1） 掌握稀疏矩阵三元组表的存储方法。 （2）掌握稀疏矩阵三元组表创建、显示、转置和查找等算法。 （3）掌握广义表的存储方法。 （4）掌握广义表的新建、显示和查找等算法。 （5）掌握稀疏矩阵三元组表和广义表的算法分析方法。 2．实验内容 （1）编写稀疏矩阵三元组表的存储程序; （2）编写疏矩阵三元组表创建、显示、转置和查找程序; （3）编写建立广义表的程序; （4）编写广义表的显示和查找程序; （5）设计选择式菜单,其一级菜单形式如下: 验证性实验6: 稀疏矩阵和广义表子系统系统 * 2021/9/12 　　　　　稀疏矩阵和广义表子系统 ******************************************* * 1-----稀 疏 矩 阵 * * 2-----广 义 表 * * 0-----退 出 * ******************************************* 请输入菜单号（0-2）: 稀疏矩阵二级菜单形式如下: 稀疏矩阵的三元组存储 ****************************************** * 1-----新 建 * * 2-----转 置 * * 3-----查 找 * * 4-----显 示 * * 0-----返 回 * ****************************************** 请输入菜单号（0-4）