Chapter05 数组和广义表

《Chapter05 数组和广义表》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、数据结构（C语言版）姓名：薛均晓办公室：302（63887286）Email：xuejx@zzu.edu.cn《数据结构（C语言版）》第1章绪论第2章线性表第3章栈和队列第4章串第5章数组和广义表第6章树和二叉树第7章图第9章查找第10章内部排序2第五章数组和广义表内容：5.1数组的定义5.2数组的顺序表示和实现5.3矩阵的压缩存储5.4广义表的定义5.5广义表的存储结构5.6广义表的递归算法3第五章数组和广义表内容：5.1数组的定义5.2数组的顺序表示和实现5.3矩阵的压缩存储5.4广义表的定义5.5广义表的存储结构5.6广义表的递归算法4数组概述数组是

2、在程序设计中，为了处理方便，把具有相同类型的若干变量按有序的形式组织起来的一种形式。这些按序排列的同类数据元素的集合称为数组。一维数组逻辑结构是线性表。多维数组线性表的推广。5多维数组例：二维数组A=(V1,V2,…,Vn)是一线性表，其中Vj=(a1j,a2j,…amj),1<=j<=n6多维数组说明：下文中多维数组简称数组75.1数组的定义ADTArray{数据对象：D＝{aj1,j2,...,jn

3、ji=0,...,bi-1,i=1,2,..,n}数据关系：R＝{R1,R2,...,Rn}Ri＝{

4、1,...jn>

5、0jkbk-1,1kn且ki,0jibi-2,i=2,...,n}基本操作：......}ADTArray8二维数组的定义数据对象:D={aij

6、0≤i≤b1-1,0≤j≤b2-1}数据关系:R={ROW,COL}ROW={

7、0≤i≤b1-2,0≤j≤b2-1}COL={

8、0≤i≤b1-1,0≤j≤b2-2}基本操作：......9数组的基本操作InitArray(&A,n,bound1,...,boundn)DestroyArray(&A)Value(A,&e,index

9、1,...,indexn)Assign(&A,e,index1,...,indexn)10数组的基本操作InitArray(&A,n,bound1,...,boundn)操作结果：若维数n和各维长度合法，则构造相应的数组A，并返回OK。11数组的基本操作DestroyArray(&A)操作结果：销毁数组A。12数组的基本操作Value(A,&e,index1,...,indexn)初始条件：A是n维数组，e为元素变量，随后是n个下标值。操作结果：若各下标不超界，则e赋值为所指定的A的元素值，并返回OK。13数组的基本操作Assign(&A,e,index1

10、,...,indexn)初始条件：A是n维数组，e为元素变量，随后是n个下标值。操作结果：若下标不超界，则将e的值赋给所指定的A的元素，并返回OK。14数组的基本操作一般来说，数组有两种常用运算：读：给定一组下标，存取相应的数据元素写：给定一组下标，修改数据元素的值15第五章数组和广义表内容：5.1数组的定义5.2数组的顺序表示和实现5.3矩阵的压缩存储5.4广义表的定义5.5广义表的存储结构5.6广义表的递归算法165.2数组的顺序表示和实现类型特点只有引用型操作，没有加工型操作，即：一经定义，则一般不做插入和删除操作；数组中的数据元素数量及元素之间的关

11、系一般不发生变动；因此，采用顺序存储。175.2数组的顺序表示和实现行主序Loc(aij)=Loc(a00)+(i*n+j)*l185.2数组的顺序表示和实现列主序Loc(aij)=Loc(a00)+(j*m+i)*l19第五章数组和广义表内容：5.1数组的定义5.2数组的顺序表示和实现5.3矩阵的压缩存储5.4广义表的定义5.5广义表的存储结构5.6广义表的递归算法20矩阵的压缩存储通常，并不是直接用数组对矩阵进行存储，而是对其进行压缩存储，即多个值相同的元素只分配一个存储空间，值为0的元素不分配空间。采用压缩存储的矩阵分为两类：特殊矩阵和稀疏矩阵。21

12、特殊矩阵三角矩阵对称矩阵对角矩阵221.三角矩阵设是一个n阶下三角矩阵，当i

13、角矩阵27a00a010…………….0a10a11a120…………