资源描述：
《chap5数组与广义表》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第五章数组与广义表四类基本结构：1.线性结构2.树形结构3.图状结构4.集合1）线性表2）栈和队列3）串4）数组与广义表本章主要内容5.2数组的顺序存储和实现5.1数组的定义和运算5.3特殊矩阵的压缩存储5.4广义表5.5总结5.1数组的定义和运算1.基本概念数组可看成是一种特殊的线性表，其特殊在于表中的数据元素本身也是一个线性表。m个行向量个列向量namn…a2na1n…am2am1…………a22a21…a12a11Am*n=2.数组的抽象数据类型定义ADTArray{数据对象：数据关系：基本操作：1.
2、InitArray(&A,n,bound1,…,boundn)2.Assign(&A,e,indx1,…,indexn)3.Destroy(&A)4.Value(A,&e,index1,…,indexn)}ADTArrayR={R1,R2,…,Rn}Ri={
3、0≤jk≤bk-1,1≤k≤n,且k≠i,0≤ji≤bi-2,aj1…ji…jn,aj1…ji+1…jn∈D,i=1,…,n}D={aj1j2…jn
4、n>0,称为数组的维数，ji是数组的第i维下标,0≤j
5、i≤bi-1,bi为数组第i维的长度，aj1j2…jn∈ElementSet}…………了解各种操作的功能即可3.数组的运算类型特点:1.数组是一组有固定个数的元素集合2.不考虑插入和删除操作；3.数组是多维的结构，而存储空间是一个一维的结构一般操作:1.获得特定位置的元素值2.修改特定位置的元素值地址计算:其本质是地址计算问题。因为主要操作是数据元素的定位，即给定元素的下标，得到该元素在计算机中的存放位置。有两种顺序映象的方式:1)以行序为主序；2)以列序为主序。5.2数组的顺序存储和实现存储顺序(C、P
6、ASCAL、BASIC等)：1.行序为主序的存储方式5.2数组的顺序存储和实现第1行元素第2行元素第m行元素amn…a2na1n…am2am1…………a22a21…a12a11Am*n=二维数组Amxn中任一元素ai,j的存储位置LOC(i,j)=LOC(1,1)+(n×(i-1)＋(j-1))×例如：称为基地址或基址a1,2a1,1a1,3a2,1a2,2a2,3a1,2a1,1a1,3a2,1a2,2a2,3LL1.行序为主序的存储方式——举例5.2数组的顺序存储和实现存储顺序(FORTRAN)：2.
7、列序为主序的存储方式5.2数组的顺序存储和实现第1列元素第2列元素第n列元素amn…a2na1n…am2am1…………a22a21…a12a11Am*n=二维数组Amxn中任一元素ai,j的存储位置LOC(i,j)=LOC(1,1)+(m×(j-1)＋(i-1))×例如：称为基地址或基址。a1,2a1,1a1,3a2,1a2,2a2,3a2,1a1,1a1,2a2,2a1,3a2,3LL2.列序为主序的存储方式——举例5.2数组的顺序存储和实现例：设有二维数组A[10][20]，其每个元素占2个字节，第一
8、个元素A1,1的存储地址为100，则按行优先顺序存储时元素A6,6的存储地址为按列优先顺序存储时元素A6,6的存储地址为5.2数组的顺序存储和实现A6,6=100+[(6-1)*20+(6-1)]*2=310A6,6=100+[(6-1)+(6-1)*10]*2=210推广到一般情况，可得到n维数组数据元素存储位置的映象关系：称为n维数组的映象函数。数组元素的存储位置是其下标的线性函数。LOC(j1,j2,...,jn)＝LOC(c1,c2,...,cn)+…….(见P92)其中ci≤ji≤di3.n维数
9、组的存储位置的映象关系5.2数组的顺序存储和实现特殊矩阵：元素分布有特殊规律的矩阵，找 到规律对应的公式5.3特殊矩阵的压缩存储①三角矩阵②带状矩阵①三元组顺序表②十字链表稀疏矩阵：非零元素很少的矩阵，且非零元 在矩阵中随机出现， 可采用只存非零元素的方法5.3.1规律分别的特殊矩阵1.下三角矩阵LOC(i,j)=LOC(1,1)LOC(i,j)=LOC(1,1)(1≤j≤i≤n)……ccan3an2an1………a33a32a31ca22a21ann…ccccca11c+前i-1行非零元素个数+第i行中a
10、ij前非零元素个数+i(i-1)/2+j-15.3.1规律分别的特殊矩阵2.上三角矩阵LOC(i,j)=LOC(1,1)LOC(i,j)=LOC(1,1)(1≤i≤j≤n)…………ccc………a33cca23a22cann…a3na2n…a13a12a11a1n+前i-1行非零元素个数+第i行中aij前非零元素个数+(i-1)(2n-i+2)/2+j-i5.3.1规律分别的特殊矩阵3.带状矩阵LOC(i,j)=LOC(1,1)
