数据结构_数组和广义表解读.pptx

CH5 数组和广义表 5.1 数组的定义 5.2 数组的顺序表示和实现 5.3 矩阵的压缩存储 5.3.1 特殊矩阵 5.3.2 稀疏矩阵 5.4 广义表的定义 5.5 广义表的存储结构 教学内容 本章先介绍数组的定义及基本运算，然后介绍数组的存储结构及特殊矩阵的压缩存储，之后讨论稀疏矩阵的三种存储方法，最后介绍广义表的概念、基本运算和存储结构。 教学目标 （1）? 了解数组的逻辑结构和存储表示；掌握数组在以行/列为主的存储结构中的地址计算方法； （2）? 掌握特殊矩阵的压缩存储方式及下标变换公式； （3）? 了解稀疏矩阵压缩存储方法的特点和适用范围，理解以三元组表示的稀疏矩阵进行矩阵运算采用的处理方法； （4）? 掌握广义表的结构特点极其存储表示方法，以及对非空广义表进行分解的两种分析方法。 5.1 数组的定义 一、数组的基本概念 数组的定义 即数组是由n个具有相同数据类型的数据元素a1， a2 ，…，an组成的有限序列，且该有限序列必须存储在一块地址连续的存储单元中。 数组的下标：数组元素的位置。 一维数组 二维数组 多维数组 注意： (1)C语言的数组定义下标从0开始。 (2) 数组的处理相比其它复杂的结构要简单。 ① 数组中各元素具有统一的类型； ② 数组元素的下标一般具有固定的上界和下界，即数组一旦被定义，它的维数和维界就不再改变。 ③数组的基本操作比较简单。 问题：数组与线性表的区别与联系？ 相同之处： 它们都是若干个相同数据类型的数据元素a0,a1,a2,…，an-1构成的有限序列。 不同之处： (1)数组要求其元素占用一块地址连续的内存单元空间，而线性表无此要求； (2)线性表的元素是逻辑意义上不可再分的元素，而数组中的每个元素还可以是一个数组； (3)数组的操作主要是向某个下标的数组元素中存放数据和取某个下标的数组元素，这与线性表的插入和删除操作不同。 5.1 数组的定义 二维数组 在此: 可以将二维数组A看成是由m个行向量[X0,X1, …,Xm-1]T组成，其中，Xi＝( ai0, ai1, ….,ain-1)， 0≤i≤m－1； 可以将二维数组A看成是由n个列向量[y0, y1, ……,yn-1]组成，其中， Yj＝(a0j, a1j, …..,am-1j)， 0≤j≤n－1。 由此可知: 二维数组中的每一个元素 最多可有二个直接前驱和两个直接后继（边界除外），故是一种典型的非线性结构。 5.1 数组的定义 二维数组的抽象数据类型定义 ADT Array2{ 数据对象 :D＝{aij|aij∈ElemSet,0≤i≤m－1,0≤j≤n－1} 数据关系:S＝{R1,R2} R1＝{ ai,j ,ai,j+1| 0≤i≤m－1, 0≤j＜n－1} R2＝{ ai,j ,ai+1,j| 0≤i＜m－1, 0≤j≤n－1} 基本操作: InitArray(A,2,m,n) DestroyArray(A) value(A,e,i,j) Assign(A,e,i,j) } ADT Array2 5.1 数组的定义 三维数组 三维数组最多可有三个直接前驱和三个直接后继，三维以上数组可以作类似分析。 因此，可以把三维以上的数组称为多维数组，多维数组可有多个直接前驱和多个直接后继，故多维数组是一种非线性结构。 5.1 数组的定义 n维数组的抽象数据类型定义 ADT Arrayn{ 数据对象: D={aj1j2…jn| aj1j2…jn ∈ElemSet,其中 ji =0,1,… , bi-1, i =1,…,n} 数据关系: S={R1 ,R2 ,…… ,Rn} Ri={aj1…ji…jn,aj1…ji+1…jn| 0≤jk≤bk-1,1≤k≤n 且k≠i, 0≤ji≤bi-2 , aj1…ji…jn,aj1…ji+1…jn∈D} 基本操作: InitArray(A,n,bound1,…，boundn) DestroyArray(A) value(A,e,index1,…,indexn) Assign(A,e,index1,…,indexn) } ADT Arrayn 5.2 数组的顺序表示和实现 存储结构的选择: 由于对数组一般不做插入和删除操作，也就是说，数组一旦建立，结构中的元素个数和元素间的关系就不再发生变化。因此，一般都是采用顺序存储的方