资源描述：
《数据结构第五章数组和广义表》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第五章数组和广义表教学目的通过本章的学习，要求学生了解数组及广义表的定义，掌握数组的存储结构5.1数组的定义5.2数组的顺序表示和实现5.3矩阵的压缩存储5.3.1特殊矩阵5.3.2稀疏矩阵重点：数组的两种存储表示方式及元素存储地址的计算公式；特殊矩阵和稀疏矩阵的压缩存储方法；难点：特殊矩阵和稀疏矩阵的压缩存储方法及运算的实现。数组可看成是一种特殊的线性表，其特殊在于，表中的数据元素本身也是一种线性表。5.1数组的定义数组是我们最熟悉的数据类型，在早期的高级语言中，数组是唯一可供使用的数据类型。由于数组中
2、各元素具有统一的类型，并且数组元素的下标一般具有固定的上界和下界，因此，数组的处理比其它复杂的结构更为简单。多维数组是向量的推广。例如，二维数组：a00a01…a0,n-1a10a11…a1,n-1…………am-1,1am-1,2…am-1,n-1在C语言中，一个二维数组类型可以定义为其分量类型为一维数组类型的一维数组类型.也就是说，typedefelemtypearray2[m][n];等价于：typedefelemtypearray1[n];typedefarray1array2[m];数组一旦被定义
3、，它的维数和维界就不再改变。因此，除了结构的初始化和销毁之外，数组只有存取元素和修改元素值的操作。同理，三维数组类型可以定义为其数据元素为二维数组类型的一维数组类型。数组的抽象数据类型定义ADTArray{数据对象：ji=0,…,bi-1i=1,2,…,nD={aj1j2…jn
4、n称为数组的维数,bi称为第i维的长度}数据关系：R={R1,R2,…,Rn}Ri={
5、0≤jk≤bk-1,1≤k≤n,且k≠i,0≤ji≤bi-2,i=2,…,n}基本操作：}二维数
6、组的抽象数据类型定义ADTTArray{D={ai,j
7、ai,j∈ElemType，}R=R1,R2R1=Row={}R2=Col={}}0≤i≤b1-10≤j≤b2-10≤i≤b1-10＜j≤b2-10＜i≤b1-10≤j≤b2-1a00,……,a0,b2-1.…….…….…….……ab1-1,0,……,ab1-1,b2-1（下标，元素）（i，ai）（(i,j),ai,j）（(j1…jn)，aj1…jn）基本操作InitArray(&A,n,bound
8、1,…,boundn)DestoryArray(&A)Value(A,&e,index1,…,indexn)//取得根据下标(index1,…,indexn)确定的元素的值，并将之赋于变量eAssign(&A,e,index1,…,indexn)//找到根据下标(index1,…,indexn)确定的元素，并将变量e的值赋于它数组的性质：(1)数组中的数据元素数目固定。一旦定义了一个数组，其数据元素数目不再有增减变化。它属于静态分配存储空间的数据结构。(2)数组中的数据元素必须具有相同的数据类型。(3)数
9、组中的每个数据元素都有一组唯一的下标值。(4)数组是一种随机存取结构。可随机存取数组中的任意数据元素。5.2数组的顺序表示和实现又由于计算机的内存结构是一维的，因此用一维内存来表示多维数组，就必须按某种次序将数组元素排成一列序列，然后将这个线性序列存放在存储器中。由于对数组一般不做插入和删除操作，也就是说，数组一旦建立，结构中的元素个数和元素间的关系就不再发生变化。因此，一般都是采用顺序存储的方法来表示数组。通常有两种顺序存储方式：⑴行优先顺序(低下标优先)——将数组元素按行排列，第i+1个行向量紧接在第
10、i个行向量后面。⑵列优先顺序(高下标优先)——将数组元素按列向量排列，第j+1个列向量紧接在第j个列向量之后三维数组A(2,3,2)第一个下标:0,1第二个下标:0,1,2第三个下标:0,1行优先：列优先：(0,0,0)(0,0,1)(0,1,0)(0,1,1)(0,2,0)(0,2,1)(1,0,0)(1,0,1)(1,1,0)(1,1,1)(1,2,0)(1,2,1)(0,0,0)(1,0,0)(0,1,0)(1,1,0)(0,2,0)(1,2,0)(0,0,1)(1,0,1)(0,1,1)(1,1,
11、1)(0,2,1)(1,2,1)对一个以行序为主序的计算机系统，当二维数组第一个数据元素a0,0的存储地址LOC(a0,0)以及每个数据元素所占用的存储单元k确定后，该二维数组中任一数据元素ai,j的存储地址可由下式确定:LOC(ai,j)=LOC(a0,0)+(i×b2+j)k其中b2为列数。推广到一般情况，可得到n维数组数据元素存储位置：LOC[j1j2…jn]=LOC[00…0]+(b2×…×bn×j1+b3×…×bn×
