数据结构课件(第5章)数组和广义表

《数据结构课件(第5章)数组和广义表》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第五章数组和广义表信阳师范学院计算机与信息技术学院5.1数组的定义5.3矩阵的压缩存储5.4广义表5.2数组的顺序表示和实现主要内容2021/6/152信阳师范学院计算机与信息技术学院基本内容：数组的定义和顺序存储；矩阵的压缩存储；广义表。学习要点：了解数组的逻辑结构；掌握以行或列序为主序的方式存储时，数组元素地址的计算方法；掌握特殊矩阵的压缩存储；了解广义表。2021/6/153信阳师范学院计算机与信息技术学院（2）每种数据结构中的数据元素，都是原子数据，不再进行分解；本章讨论三个方面的内容：数组、矩阵的压缩存储、广义表本章讨论的两种数据结构：数组和广义表，其共同特点是：1）从逻辑

2、结构上看它们，可看成是线性结构的一种扩展；2）数据元素本身也是一个数据结构。前4章介绍的数据结构共同特点：（1）都属于线性结构；引言2021/6/154信阳师范学院计算机与信息技术学院数组是由一组个数固定，类型相同的数据元素组成的阵列。Amn=a00a02……a1,n-1a10a11……a1,n-1………………am-1,0am-1,1am-1,n-1在行关系中aij直接前趋是aij-1aij直接后继是aij+1在列关系中aij直接前趋是ai-1jaij直接后继是ai+1j5.1数组的定义一维数组的特点：1个下标，ai的直接前驱是ai-1，直接后继是ai+1。二维数组的特点：2个下标，

3、每个元素ai,j受到两个关系（行关系和列关系）的约束：2021/6/155信阳师范学院计算机与信息技术学院N维数组的数据类型定义ADTARRAY{Ri={

4、0≤jk≤bk-1,1≤k≤n且k≠i,0≤ji≤bi-2,aj1,j2,…ji…jn,aj1,j2,…ji+1…jnD}数据关系：R={R1,R2，….Rn}D={aj1,j2…jn

5、n(>0)称为数组的维数，bi是数组第i维的长度，ji为数组元素的第i维下标，aj1,j2…jnElemset}构造数组、销毁数组、读数组元素、写数组元素基本操作：数据对象：ji=0,

6、...,bi-1,i=1,2,...n2021/6/156信阳师范学院计算机与信息技术学院初始化操作InitArray(&A,n,bound1,…,boundn)功能：参数合法，构造数组A，并返回OK；销毁操作DestroyArray(&A)功能：销毁数组A；3读元素操作Value(A,&e,index1,…,indexn)功能：若指定下标不越界，读指定下标的元素，用e返回并返回OK；4写元素操作Assign(A,e,index1,…,indexn)功能：若指定下标不越界，将e赋值给A指定的下标元素并返回OK。数组的基本操作2021/6/157信阳师范学院计算机与信息技术学院可看作是是

7、一个定长线性表，且它的每个数据元素也是一个定长线性表。例：Am×n=a00a01a02…a0,n-1a10a11a12…a1,n-1………am-1,0am-1,1am-1,2…am-1,n-1二维数组2021/6/158信阳师范学院计算机与信息技术学院a00a01a02…a0,n-1a10a11a12…a1,n-1………am-1,0am-1,1am-1,2…am-1,n-1(1)A=(α0,α1,…,αm-1)αi=(ai0,ai1,…,ai,n-1)0<=i<=m-1Am×n=α0α1…αm-1=二维数组2021/6/159信阳师范学院计算机与信息技术学院(2)A=(α0,α1,…,

8、αn-1)αj=(a0j,a1j,…,am-1,j)0<=j<=n-1Am×n=α0α1…αn-1=a00a01a02…a0,n-1a10a11a12…a1,n-1………am-1,0am-1,1am-1,2…am-1,n-12021/6/1510信阳师范学院计算机与信息技术学院二维数组的C语言表示：TypedefelemtypeArray1[n];TypedefArray1Array2[m];TypedefelemtypeArray[m][n];2021/6/1511信阳师范学院计算机与信息技术学院用一组连续的存储单元存放数组的数据元素。二维数组的两种顺序存储方式：（1）行序为主序（2

9、）列序为主序例：Am×n=a00a01a02…a0,n-1a10a11a12…a1,n-1………am-1,0am-1,1am-1,2…am-1,n-15.2数组的顺序表示和实现2021/6/1512信阳师范学院计算机与信息技术学院行序为主序：a00a01…a0n-1a10a11…a1n-1…am-1,0am-1,1…am-1,n-1数据元素的存储位置：loc(i,j)=loc(0,0)+aij之前的元素个数×LAm×n=a00a01a02…a0