数组与广义表数据结构课件：压缩存储上三角形矩阵

"本资源是关于数据结构课程的课件，重点关注数组和广义表，特别是对上三角形矩阵的讲解。课件中涉及到数组的类型定义、顺序表示与实现，以及稀疏矩阵的压缩存储。同时，还涵盖了广义表的类型定义和表示方法。" 在数据结构中，数组是一种基本的数据组织形式，它可以被看作是在内存中连续存储的同类型元素的集合。数组的类型定义通常包含数据对象D，即数组中的元素，以及数据关系R，描述了元素之间的关系。例如，二维数组D={aij|0≤i≤b1-1,0≤j≤b2-1}，其中n表示维数，bi表示第i维的长度。基本操作包括初始化、销毁、获取元素值和赋值。 数组的顺序表示和实现中，数组虽然逻辑上是多维的，但在内存中通常被一维化存储。例如，行序为主序的存储方式下，二维数组元素ai,j的存储位置可通过公式LOC(i,j)=LOC(0,0)+(b2×i+j)×a计算得出，其中LOC(0,0)是数组的基地址，b2是第二维的长度，a是每个元素的大小。 课件中提到了对上三角形矩阵，这是矩阵的一种特殊形式，其中主对角线以下的元素为0。对于上三角形矩阵，当i≤j时，aij之前的元素有i行，因此有i*(i+1)/2个元素。在第(i+1)行上，aij之前有i个元素。对于压缩存储上三角形矩阵的作业，目标是找出一种节省空间的方法来存储非零元素，这通常通过使用三元组（行号，列号，值）来实现，只存储非零元素，从而节省大量空间。 此外，课件也提及了广义表的概念，这是一种能表示多种复杂数据结构的数据类型，可以包含子表，类似于树结构。广义表的类型定义和表示方法涉及其元素的定义、子表的嵌套以及访问和修改元素的操作。 稀疏矩阵是指非零元素较少的矩阵，对于这类矩阵，常规的存储方式会浪费大量空间。因此，通常采用压缩存储，如链表或三元组方式，只存储非零元素，以提高存储效率。 这份课件提供了数组、广义表和稀疏矩阵的基础知识和具体实现，是学习数据结构的重要参考资料。通过学习，学生可以理解这些基本数据结构的原理，掌握它们的存储和操作方法，为进一步学习更复杂的算法和数据结构奠定基础。