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

ID:33423141

大小:405.00 KB

页数:12页

时间:2019-02-25

数据结构域算法设计-数组和广义表 教案_第1页
数据结构域算法设计-数组和广义表 教案_第2页
数据结构域算法设计-数组和广义表 教案_第3页
数据结构域算法设计-数组和广义表 教案_第4页
数据结构域算法设计-数组和广义表 教案_第5页
资源描述:

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

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

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
正文描述:

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

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

显示全部收起
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。
关闭