数据结构域算法设计-数组和广义表 教案

《数据结构域算法设计-数组和广义表 教案》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第五章数组和广义表继续增加线性表结构的内涵。数组结构每个子结构是由基本元素组成的大小均等的线性表。广义表结构每个子结构或是基本元素，或是由基本元素组成的大小不等的线性表结构。本章学习要点：掌握数组的相关概念掌握特殊矩阵的压缩存储方式掌握稀疏矩阵的存储方法掌握广义表的相关运算掌握广义表的存储结构掌握广义表的基本运算的实现第一节数组的逻辑结构1_Array=(D,S,P)　定长线性表D={ai

2、ai∈ElemSet,i=0,1,2,…,n-1}S={

3、ai-1,ai∈D,i=1,2,…,n-1}2_Arra

4、y=(D,S,P)定长线性表，每个元素又是定长线性表。D={ai,j

5、ai,j∈ElemSet,i=0,1,…,n1-1;j=0,1,…,n2-1}S={ROW,COL}ROW={

6、i=0,1,…,n1-1;j=1,…,n2-1}COL={

7、i=1,…,n1-1;j=0,1,…,n2-1}3_Array=(D,S,P)增加层的关系基本操作：取值、赋值。第二节数组结构的顺序存储结构数组结构是多维的，内存地址是一维的。存储方式：行主序，列主序以行主序为例：5-12一维：LO

8、C(ai)=base+i二维(MxN)：LOC(ai,j)=base+i*N+j三维(MxNxP)：LOC(ai,j,k)=base+i*N*P+j*P+k四维(MxNxPxQ)：LOC(ai,j,k,l)=base+i*N*P*Q+j*P*Q+k*Q+lTypedefstruct{ElemType*base;intdim;　　　　维数int*bounds;　各维元素个数int*constants;各维包含的基本元素个数}Array;例：数组A[3,4,5,6]的存储结构A.dim=4A.bounds[]={3,4,5,

9、6}A.constants[]={120,30,6,1}A[i,j,k,l]的地址:A.base+(i*120+j*30+k*6+l)1、初始化数组结构voidArray_Init(Array&A,intdim,intbounds[])5-12{A.dim=dim;A.bounds=(int*)malloc(dim*sizeof(int));A.constants=(int*)malloc(dim*sizeof(int));if(!A.bounds

10、

11、!A.constants){printf(“overflow!”);r

12、eturn;}for(i=0;i=0;i--)A.constants[i]=A.bounds[i+1]*A.constants[i+1];//开辟数组空间elemtotal=A.bounds[0]*A.constants[0];A.base=(ElemType*)malloc(elemtotal*sizeof(ElemType));if(!A.base){printf(“overflow!”

13、);return;}printf(“OK!”);}2、取值ElemTypeArray_GetValue(ArrayA,intdim_i[])//dim[]存放要求元素的下表{intoffset;for(offset=0,i=0;i

14、标的范围是0到7，每个数组元素用相邻的6个字节存储，存储器按字节编址。那么，这个数组的体积是个字节。第三节矩阵的压缩存储矩阵的用途：大型方程组求解、高次方程求解真正有用的计算是矩阵的计算。从空间/时间复杂度出发：一、特殊矩阵利用矩阵的特征，尽量减少数据的存储量。1、对称矩阵aij=ajiNxN矩阵的存储结构：S[N(N+1)/2]。以行主序的方式存储下三角元素：若i>=j:k=i*(i+1)/2+j若i

15、下三角，则元素A[3][5]的存储位置是？2、上/下三角矩阵类似对称矩阵，只是某三角区域所有元素为0，或为某固定值3、对角矩阵非0元素的分布：以主对角线为中心的带状区域。半带宽为d，带宽为2d+1。非0元素个数：(2d+1)n-(1+d)d存储方案：S[(2d+1)n]，扩展了上下二个三角区域。aij=>S[k],k