数组和广义表介绍.pptxVIP

数组和广义表教学内容： 数组的定义、顺序表示稀疏矩阵的压缩存储广义表的定义、存储结构和递归算法教学要求：掌握数组的两种顺序存储表示方法，掌握数组元素存储地址的计算方法；掌握稀疏矩阵的三元组表压缩存储方法和其上的矩阵转置运算的算法；掌握广义表的结构特点、存储表示方法和递归算法知识结构图1 数组的定义本章之前讨论的线性结构的数据元素都是非结构的原子类型，元素值不可再分。本章讨论的两种数据结构——数组和广义表。作为线性表的扩展，表中的数据元素本身也是一种数据结构。抽象数据类型数组的定义数组的顺序表示n维数组的存储方式n维数组的数据元素存储位置的计算公式 a00a01 … a0,n-1 a10 a11 … a1,n-1 … … … …am-1,0 am-1,1 … am-1,n-1Am*n= a00a01 … a0,n-1 a10 a11 … a1,n-1 … … … …am-1,0 am-1,1 … am-1,n-1二维数组Am*n=Am*n=((a00a01…a0,n-1),(a10a11…a1,n-1) , …, (am-1,0am-1,1…am-1,n-1))列向量的一维数组行向量的一维数组1 数组的定义n维数组是线性表的推广 当n=1，n维数组退化成顺序表当n1，n维数组可看成表中数据元素仍是线性表的线性表A=(α0,α1,…αp) p=m-1或n-1 a[0]a[1]a[2]1 数组的定义在C语言中，一个二维数组类型可以定义为其分量类型为一维数组类型的一维数组类型， typedef Elemtype Array2[m][n];= typedef Elemtype Array1[n]; typedef Array1 Array2[m];二维数组的二种理解方式： 视作多个一维数组 视作一个一维数组a[3][4]a[0] a[1] a[2] a[3]a00 a01 a02 a03a10 a11 a12 a13a20 a21 a22 a23a[3][4]1 数组的定义ADT Array { 数据对象:ji=0,…,bi – 1, i = 1,2,…,n, // bi是数组第i维上的长度 D={ | ∈ElemSet } 数据关系:R = {R1,R2,…,Rn} Ri={ |0≤jk≤bk–1, 1≤k≤n, k!=i,0≤ji≤bi–2, ∈D, i=2,3,…,n} 基本操作： InitArray(A,n,bound1,…,boundn) DestroyArray(A) Value(A,e,index1,…,indexn) Assign(A,e,index1,…,indexn)}ADT Array n维数组的特点nn维数组中含有?bi个数据元素;每个数据元素都受着n个关系的约束；在每个关系中，元素aj1j2…jn(0=ji=bi-2)都有一个直接后继;数据元素都必须属于同一数据类型;n=1时，退化为定长的线性表；n维数组可以看成是线性表的推广。数组一旦被定义，则维数已定，对于数组的操作只有存取元素和修改元素。(一旦建立了数组，数组中的元素个数和元素之间的关系就不再发生变动)数组是多维的结构，而存储空间是一个一维的结构。（存储时需要一个次序约定）i=12 数组的顺序表示特点：用一组地址连续的存储单元按照某种规则存放数组中的数据元素。存储方式的两种约定（顺序存储方式）：以行序为主（低下标优先）—将数组元素按行排列，第i+1个行向量紧接在第i个行向量后。如：PASCAL、C。以列序为主（高下标优先）—将数组元素按列排列，第j+1个列向量紧接在第j个列向量后。如：FORTRAN。例：A[2][3][2]以行序为主存储，写出其元素存放的先后顺序。a00a00a10a01… …… …am-1,0 a0,n-1 a00a01 … a0,n-1 a10 a11 … a1,n-1 … … … …am-1,0 am-1,1 … am-1,n-1a01a10 Am*n= a11 a11… … … … 按行序为主序按列序为主序a1,n-1 am-1,1 二维数组… …… …am-1,0 a0,n-1 a1,n-1am-1,1 … … … … am-1,n-1am-1,n-12 数组的顺序表示和实现 a00a01 … a0,n-1 a10 a11 … a1,n-1 … …aij …am-1,0 am-1,1 …am-1,n-1Am*n=2 数组的顺序表示计算数组任